模拟退火是什么？像金属冷却一样慢慢找到最优解

模拟退火（Simulated Annealing，SA）是一种用来寻找全局最优解的随机优化算法，由 Scott Kirkpatrick、C. Daniel Gelatt 和 Mario Vecchi 在 1983 年发表于《科学》杂志的论文中提出，Vlado Černý 在 1985 年也独立地提出了类似的方法。它的灵感来源于冶金中的“退火”工艺。

来自冶金的灵感

在冶金中，退火是把金属加热到很高的温度，然后让它缓慢地冷却。在高温下，金属中的原子能量很高，可以自由地移动；随着温度慢慢地降低，原子逐渐地“安顿”下来，排列成规则的、能量很低的晶体结构，金属变得更加坚韧、内部缺陷更少。如果冷却得太快，比如直接把高温的金属放进冷水中淬火，原子来不及找到最好的位置，就会被“冻结”在一种杂乱的、能量较高的状态中。模拟退火借用了这个过程：把要优化的目标函数看作“能量”，把寻找最优解看作寻找能量最低的状态。

算法是怎么工作的

算法从一个初始解和一个较高的“温度”开始，然后反复地执行以下步骤：在当前解的附近随机地产生一个新的候选解，比如在旅行商问题中随机地交换两个城市的访问顺序；计算新解与当前解的目标函数值之差；如果新解更好，就接受它，移动到新解；如果新解更差，并不是直接拒绝，而是以一定的概率接受它，这个概率随着新解变差的程度增大而减小，随着温度的升高而增大，具体等于“负的能量差除以温度”的指数。这个接受规则来自 1953 年 Metropolis 等人在模拟物理系统时提出的方法，被称为 Metropolis 准则。每进行若干次这样的尝试之后，就按照一定的规则降低温度，比如每次乘以 0.95。随着温度不断地降低，接受更差的解的概率越来越小，算法逐渐变得“保守”，最终稳定在一个很好的解上。

为什么要接受更差的解

这是模拟退火最关键的设计。普通的局部搜索方法，比如爬山法，只接受更好的解，就像一个只会往高处走的登山者，一旦到达某个小山头，四周都是下坡，就停下来了，但这个小山头很可能不是最高的山峰，这就是陷入了局部最优。模拟退火在高温的时候，愿意以较大的概率接受更差的解，就像登山者有时愿意先往下走一段路，才有机会翻越山谷、登上更高的山峰。在搜索的早期，温度高，算法能够在很大的范围内自由地探索；到了后期，温度低，算法几乎只接受更好的解，在一个有希望的区域中进行精细的搜索。这样就在“探索”和“利用”之间取得了平衡。

冷却速度的选择

降温的方式，也叫冷却计划，对算法的效果至关重要。理论上可以证明，如果降温足够缓慢，比如按照对数的速度降温，模拟退火能以趋近于 1 的概率找到全局最优解，但这样的速度在实际中慢得无法接受。在实践中，通常采用每次乘以一个略小于 1 的系数的方式降温，并需要在解的质量和计算时间之间进行权衡：降温太快，容易陷入局部最优；降温太慢，计算时间太长。初始温度、每个温度下的尝试次数、终止的条件，也都需要根据具体的问题来调节。

应用

模拟退火实现简单、适用面广，不需要目标函数可导，特别适合那些组合优化问题。Kirkpatrick 等人在原论文中就把它用于计算机芯片的布局和布线设计，以及旅行商问题。此后它被广泛地应用于：电路和芯片的布局设计、生产调度和排班、车辆路径规划、图像处理和复原、蛋白质结构预测，以及机器学习中的超参数搜索和特征选择等。它与遗传算法、禁忌搜索、粒子群优化等一起，是最常用的启发式全局优化方法之一。量子退火则借鉴了类似的思想，利用量子隧穿效应来帮助跳出局部最优。