模拟退火算法详解

已剪辑自: https://zhuanlan.zhihu.com/p/266874840

一个由金属退火启发的算法!

本文主要内容：

• 金属退火的原理
• 模拟退火算法机制
• 模拟退火的流程
• 模拟退火的应用
• 算法小结

1.金属退火的原理

金属退火是将金属加热到一定温度，保持足够时间，然后以适宜速度冷却(通常是缓慢冷却，有时是控制冷却)的一种金属热处理工艺。模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。

如上图，处在低温状态时，固体中分子具有的内能很低，在原本的位置上做小范围的振动。若是将固体加热到一定温度，分子内能将会增加，热运动加剧，分子排列的无序度增加。此时再将温度缓缓降低，在每个温度都达到平衡态（即准静态过程），分子具有的能量逐渐降低，最终回归到有序排列的状态，分子内能也跟着降到最低。

2.模拟退火算法机制

模拟退火算法(Simulated Annealing,SA)最早的思想是由N. Metropolis等人于1953年提出。1983年,S. Kirkpatrick等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。

介绍模拟退火前，还是有必要先介绍爬山算法。

爬山算法

爬山算法是一种简单的贪心搜索算法，该算法每次从当前解的临近解空间中选择一个最优解作为当前解，直到达到一个局部最优解。

爬山算法实现很简单，其主要缺点是会陷入局部最优解，而不一定能搜索到全局最优解。如上图所示：假设C点为当前解，爬山算法搜索到A点这个局部最优解就会停止搜索，因为在A点无论向那个方向小幅度移动都不能得到更优的解。

模拟退火核心思想

模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。如下图：

这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来。将温度T当作控制参数，目标函数值f视为内能E，而固体在某温度T时的一个状态对应一个解xix_{i}，然后算法试图随着控制参数T的降低，使目标函数f(内能E)也逐渐降低，直至趋于全局最小值（退火中低温时的最低能量状态），就像金属退火过程一样。

关于爬山算法与模拟退火，有一个有趣的比喻：

• 爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。
• 模拟退火：兔子喝醉了。它随机地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，它渐渐清醒了并朝最高方向跳去。这就是模拟退火。

模拟退火数学原理

从上面我们知道，会结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，那么具体的更新解的机制是什么呢？如果新解比当前解更优，则接受新解，否则基于Metropolis准则判断是否接受新解。接受概率为：

P={1, Et+1<Ete−(Et+1−Et)kT, Et+1≥Et P = \begin{cases} 1,~~~~~~~~~~~~~~~~~ E_{t+1} \lt E_{t} \ e^{\frac{-(E_{t+1} - E_{t})}{kT}},~~~~ E_{t+1} \ge E_{t} \end{cases} \

如上公式，假设当前时刻搜索的解为xtx_{t}，对应的系统能量(目标函数)为EtE_{t}，对搜索点施加随机扰动，产生新解xt+1x_{t+1}，相应地，系统能量为Et+1E_{t+1}，那么系统对搜索点从xtx_{t}到xt+1x_{t+1}转变的接受概率就为上公式。具体以下图为例：

假设开始状态在A，随着迭代次数更新到B局部最优解，这时发现更新到B时，能量比A要低，则说明接近最优解了，因此百分百转移，状态到达B后，发现下一步能量上升了，如果是梯度下降则是不允许继续向前的，而这里会以一定的概率跳出这个坑，这个概率和当前的状态、能量等都有关系，如果B最终跳出来了到达C，又会继续以一定的概率跳出来，直到到达D后，就会稳定下来。

3.模拟退火的流程

算法实质分两层循环，在任一温度水平下，随机扰动产生新解，并计算目标函数值的变化，决定是否被接受。由于算法初始温度比较高，这样，使E增大的新解在初始时也可能被接受，因而能跳出局部极小值，然后通过缓慢地降低温度，算法就最终可能收敛到全局最优解，具体流程为：

1. 令T=T0T = T_{0},表示开始退火的初始温度，随机产生一个初始解x0x_{0},并计算对应的目标函数值E(x0)E(x_{0});
2. 令T=kTT = kT,其中k取值0到1之间，为温度下降速率；
3. 对当前解xtx_{t}施加随机扰动，在其邻域内产生一个新解xt+1x_{t+1}，并计算对应的目标函数值E(xt+1)E(x_{t+1}),计算

ΔE=E(xt+1)−E(xt) \Delta E = E(x_{t+1}) - E(x_{t}) \

1. 若ΔE<0\Delta E \lt 0,接受新解作为当前解，否则按照概率e−ΔE/kTe^{- \Delta E/kT}判断是否接受新解；
2. 在温度T下，重复L次扰动和接受过程，即执行步骤3和4；
3. 判断温度是否达到终止温度水平，若是则终止算法，否则返回步骤2.

具体流程图如下：

其中有几个需要注意的点：

• 初始点的选取对算法结果有一定的影响，最好是多次运行对结果进行综合判断。
• 在算法运行初期，温度下降快，避免接受过多的差结果。当运行时间增加，温度下降减缓，以便于更快稳定结果。
• 当迭代次数增加到一定次数时，结果可能已经达到稳定，但是距离算法结束还有一段时间。在设计程序时应该加入适当的输出条件，满足输出条件即可结束程序。

4.模拟退火的应用

模拟退火算法作为一种通用的随机搜索算法，现已广泛用于VLSI设计、图像识别和神经网计算机的研究。模拟退火算法的应用如下：

• 模拟退火算法在VLSI设计中的应用
  利用模拟退火算法进行VLSI(Very Large Scale Integration,超大规模集成电路)的最优设计，是目前模拟退火算法最成功的应用实例之一。用模拟退火算法几乎可以很好地完成所有优化的VLSI设计工作。如全局布线、布板、布局和逻辑最小化等等。

• 模拟退火算法在图像处理中的应用
  模拟退火算法可用来进行图像恢复等工作，即把一幅被污染的图像重新恢复成清晰的原图，滤掉其中被畸变的部分。因此它在图像处理方面的应用前景是广阔的。
• 模拟退火算法在神经网计算机中的应用
  模拟退火算法具有跳出局部最优陷阱的能力。在Boltzmann机中，即使系统落入了局部最优的陷阱，经过一段时间后，它还能再跳出来，系统最终将往全局最优值的方向收敛。

• 模拟退火算法的其他应用
  除了上述应用外，模拟退火算法还用于其它各种组合优化问题，如TSP和Knapsack问题等。大量的模拟实验表明，模拟退火算法在求解这些问题时能产生令人满意的近似最优解，而且所用的时间也不很长。

5.小结

总之，模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。算法从某一较高初温出发，伴随温度参数的不断下降,结合一定的概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。

至此，本文从金属退火的原理，爬山算法，模拟退火算法思想以及原理，到模拟退火的流程和应用方面对模拟退火算法进行了简单的阐述，希望对大家有所帮助。

♥点个赞再走呗♥