如何用随机方法求解组合优化问题（四）-Toy模板网

这篇具有很好参考价值的文章主要介绍了如何用随机方法求解组合优化问题（四）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

模拟退火算法中的退火过程是什么

这是一篇笔记，是对于B站up主马少平的视频（第四篇如何用随机方法求解组合优化问题（四））的学习与记录。

这篇笔记还没有介绍到模拟退火算法，而是记录退火这一物理过程以及相关的公式。

最主要的内容是如何将退火过程的特点迁移到后续的算法设计中。

退火是什么

退火是固体物理学中的一个概念，它描述了固体材料在高温下逐渐冷却的过程，以使其从高能态逐渐转变为低能态。这个概念在模拟退火算法中得到了应用，用于寻找问题的最优解。

退火有以下过程：

加热阶段（高温阶段）：在退火过程开始时，固体物体会被加热到非常高的温度。高温会使原子或分子的热运动剧烈，突破原本的位置限制。这种高温状态下，固体处于高能态，原子或分子的位置非常不稳定。
冷却阶段（退火阶段）：随着时间的推移，温度逐渐降低。在温度逐渐降低的过程中，原子或分子的热运动减缓，逐渐趋向于更稳定的位置。随着温度的降低，固体会逐渐从高能态转变为低能态，原子或分子逐渐排列成更有序的结构。
冷却到基底温度（低温阶段）：当温度足够低时，固体达到了最低能态，原子或分子的运动几乎停止，形成了稳定的结晶态。此时，固体的内部结构和排列达到了最优状态，对应着系统的全局最优解。

在模拟退火算法中，这个物理过程被用来模拟在解空间中寻找最优解的过程。算法从一个初始解（高温状态）开始，随机生成新的解（状态），并根据一定的准则决定是否接受新解。随着算法的迭代，模拟退火算法会逐渐减小“温度”，也就是接受劣解的概率，从而使算法在解空间中逐渐趋向于全局最优解，就像实际的退火过程一样。

退火过程

在退火过程中，状态转换的标准为：

如果 \(\Delta E \le 0\) ，则新状态被接受；
如果 \(\Delta E > 0\) ，则新状态被接受的概率为：

\[P = e^{-\frac{\Delta E}{KT}} \]

其中 \(\Delta E\) 是新状态的内能和初始状态的内能的差值，\(T\) 是绝对温度，\(K>0\) 是玻尔兹曼常数。

在给定的温度 \(T\) 下，当进行足够多次的状态转换后，系统将达到一种热平稳状态。

此时系统处于某个状态 \(i\) 的概率 \(P_i(T)\) 由 Boltzmann 分布给出：

\[P_i(T)=\frac{e^{-\frac{E(i)}{KT}}}{Z_T} \]

其中 \(Z_T=\sum\limits_{j\in S}e^{-\frac{E(j)}{KT}}\) 为归一化因子。

退火过程分析

同一温度下两个内能不同的状态

假设两个状态的内能 \(E(i)<E(j)\)：

\[\begin{align*} P_i(T)-P_j(T) &= \frac{e^{-\frac{E(i)}{KT}}}{Z_T} - \frac{e^{-\frac{E(j)}{KT}}}{Z_T} \\ &= \frac{1}{Z_T}e^{-\frac{E(i)}{KT}} \left( 1-\frac{e^{-\frac{E(j)}{KT}}}{e^{-\frac{E(i)}{KT}}} \right ) \\ &= \frac{1}{Z_T}e^{-\frac{E(i)}{KT}} \left ( 1-e^{-\frac{E(j)-E(i)}{KT}} \right ) \end{align*} \]

因为 \(E(i)<E(j)\)，可以推出\(0<e^{-\frac{E(j)-E(i)}{KT}}<1\)，于是有 \(P_i(T)-P_j(T) >0\)，即 \(P_i(T)>P_j(T)\)

结论：在任何温度 \(T\) 下，系统处于低内能的状态的概率大于处于高内能的状态的概率。

高温下的情况

\[\begin{align*} \lim_{T\to \infty}P_i(T) &= \lim_{T\to \infty} \left[ \frac{e^{-\frac{E(i)}{KT}}}{\sum\limits_{j\in S}e^{-\frac{E(j)}{KT}}} \right ] \\ &= \frac{1}{|S|} \end{align*} \]

其中 \(|S|\) 表示系统所有可能的状态数。

结论：当温度趋近于无穷大时，系统处于各个状态的概率相等，处于均匀分布，与所处状态的内能无关。

低温下的情况

\[\begin{align*} \lim_{T\to 0}P_i(T) &= \lim_{T\to 0} \left[ \frac{e^{-\frac{E(i)}{KT}}}{\sum\limits_{j\in S}e^{-\frac{E(j)}{KT}}} \right] = \lim_{T\to 0} \left[ \frac{e^{-\frac{E(i)-E_m}{KT}}}{\sum\limits_{j\in S}e^{-\frac{E(j)-E_m}{KT}}} \right] \\ &= \lim_{T\to 0} \left[ \frac{e^{-\frac{E(i)-E_m}{KT}}}{\sum\limits_{j\in S_m}e^{-\frac{E(j)-E_m}{KT}}+\sum\limits_{j\notin S_m}e^{-\frac{E(j)-E_m}{KT}}} \right] = \lim_{T\to 0} \left[ \frac{e^{-\frac{E(i)-E_m}{KT}}}{\sum\limits_{j\in S_m}e^{-\frac{E(j)-E_m}{KT}}} \right] \\ &= \begin{cases} \frac{1}{|S_m|}, & if \quad i\in S_m \\ 0, & if \quad i \notin S_m \end{cases} \end{align*} \]

其中 \(S_m\) 表示系统最小内能状态的集合，\(E_m\) 表示系统的最小内能。

结论：当温度趋近于绝对0度时，系统以等概率趋近于几个内能最小的状态之一，而系统处于其它状态的概率为0。即系统达到内能最小状态的概率为1。

温度缓慢下降时的情况

\[\begin{align*} \frac{\partial P_i(T)}{\partial T} &= \frac{\partial}{\partial T} \left[ \frac{e^{-\frac{E(i)}{KT}}}{Z_T} \right] \\ &= \frac{P_i(T)}{KT^2}[E(i)-\overline{E_T}] \begin{cases} >0 \quad if \ E(i)>\overline{E_T}, \quad 高能状态 \\ <0 \quad if \ E(i)<\overline{E_T}, \quad 低能状态 \end{cases} \end{align*} \]

其中 \(\overline{E_T}=\sum\limits_{j\in S}E(j)P_j(T)\) 为状态内能的平均值。

结论：系统处于低能状态的概率随着温度的下降单调上升，而系统处于高能状态的概率随着温度的下降单调下降。

分析：

随着温度的缓慢下降，由于处于低能状态的概率越来越大，处于高能状态的概率越来越小，导致状态的内能平均值 \(\overline{E_T}\) 随温度下降而下降，从而使得更多的状态属于高能状态，越来越少的状态属于低能状态。最终，当温度降低到趋近于绝对0度时，只有具有最小内能的状态才属于低能状态。
这也从另一个角度说明了当温度趋近于绝对0度时，为什么系统处于最小内能状态的概率为1，这与我们前面的分析是一致的。