计算科学 - 使用模拟退火找到全局最优值之前的预期步数 - 吾爱随笔录

我正在阅读关于模拟退火的技术报告：关于模拟退火的收敛时间，作者是 Sanguthevar Rajasekaran。您可以通过此链接找到它。

给定是图，其顶点是给定问题的可能解，是邻居之间的边集，目标是证明 SA 的收敛性。为此，作者假设的直径、其度数和顶点之间的最大能量差分别表示为、和。 $G=(V, E)$ $E$ $G$ $G$ $D$ $d$ $\Delta$

第 6 页有一个引理：

如果是中的任何状态，则从开始访问全局最优状态之前的预期步数为。 $X$ $V$ $X$ $\le (\frac 1 d \times e^{-\Delta / T})^{-D}$

之后访问邻居的概率为： $S_j$ $S_i$

\frac{1}{d} \times e^{\frac{- Δ E}{T}}

$\frac 1 d \times e^{\frac{-\Delta E}{T}}$ 其中是选择 S_i 的所有 d 个邻居的 S_j 的概率并且 ^ \是实际移动到它的概率。在模型中保持不变。

\frac{1}{d}

$\frac 1 d$

S_{j}

$S_j$

d

$d$

S_{i}

$S_i$

e^{\frac{- Δ E}{T}}

$e^{\frac{-\Delta E}{T}}$

T

$T$

在引理的证明中，作者确定从任意状态的概率为并完成证明： $g$ $X$ $\ge [\frac 1 d \times e^{-\frac \Delta T}]^D$

这意味着之前的预期步数是。 $g$ $\le [d e^{\frac \Delta T}]^D$

有人愿意解释我们如何估算步数吗？我坚持下去，但我真的，真的很想弄清楚这一点。:)