A.6 模拟退火

1.灵感来自金属退火

说起来，前面那些章节我们讲的都是深度学习模型怎么训练，这一章不妨换个角度，聊一类叫元启发式（metaheuristic）的搜索算法。深度学习里很多问题，说穿了就是在一片巨大的解空间里找一个让目标函数最小的参数组合，这种搜索思路其实是相通的。今天的主角叫模拟退火（Simulated Annealing），名字听着有点工业气息，原因也直白，它的灵感确实来自金属加工里的退火工艺。

退火是冶金里很古老的做法。铁匠把一块铁烧到通红，这时候金属内部的原子热运动非常剧烈，原子们几乎随处乱跑，整个晶格到处都是缺陷和错位。然后铁匠让铁慢慢冷却。温度降下来的时候，原子运动放缓，会一点一点自己排列到能量更低、更整齐的结晶位置上。冷却得越慢，最终得到的金属越均匀、越稳定，能量状态也越低。要是一下子淬到冷水里（这就是淬火），原子来不及重新排列就被冻在原地，得到的就是脆而硬、内部应力很大的材料。

模拟退火就是想把这件事搬到算法里来。我们把一个优化问题里解的好坏对应成金属的能量，把搜索过程对应成温度从高到低的冷却。高温的时候，我们允许算法到处乱走，即使走到比当前差的解也肯接受，温度慢慢降下来，算法就越来越挑剔，最后稳定在一个比较优的解上。这套对应关系大致就是物理退火的一个数学抽象。

我记得有本讲统计物理的科普书里提过，金属之所以要慢冷，是因为原子需要时间去试探各种各样的排列，急冷会让它们卡在一种乱糟糟的状态里出不来。这句话放在优化算法上几乎一模一样，等会儿我们讲局部最优的时候大家就会更有感觉。

2.局部最优是个老问题

讲模拟退火之前，我们得先说清楚它要解决的麻烦是什么。我们做优化，最朴素的办法叫贪心或者梯度下降，每一步都只往更好的方向走。这种做法简单直接，可是在复杂的解空间里走着走着，往往会卡在一个小山头的顶上（或者目标函数的谷底）。这座山头其实只是周围一小片区域里的最高点，放眼整片地形，它根本算不上什么，可算法每一步都只肯往上走，就再也下不去了，因为旁边所有方向都是下坡。这种位置就叫局部最优。

打个比方，小明去爬一座野山，他只会一个劲儿地往高处走，最后大概率停在某座小山包的顶上，自以为到了最高峰，其实真正的玉皇顶还在对面那座大山后面。他没有本事先下山再上山，自然就走不到真正的最高处。这就是纯贪心搜索的毛病。我记得有部讲登珠峰的电影，里头的向导反复强调登顶之前要先下到垭口再攀另一面，这跟我们要解决的问题是一个道理，有时候得先往下走，才能去到更高的地方。

模拟退火给这个毛病开出的方子很有意思，它允许算法有时候往下走一步，先离开那个小山包，再去试探别的方向。能不能往下走、走多远，全看一个叫温度的参数。这就引出了模拟退火的核心，也就是Metropolis准则。

3.Metropolis准则：差解也要按概率接受

Metropolis准则最早是物理学家Metropolis在1953年研究流体状态采样的时候提出来的，后来Kirkpatrick等人在1983年把它搬到了组合优化问题上，模拟退火这门算法这才正式成型。这个准则讲的其实是这么一件事，当我们试探性地走到一个新的解，而新解比当前解差的时候，我们并不直接拒绝它，先按一个概率来决定到底要不要接受。这个接受概率 $P$ 由下面这个式子给出：

$$P = \exp(-\Delta E / T)$$

这里的 $\exp$ 是以自然常数 $e\approx 2.718$ 为底的指数函数。$\Delta E$ 表示新解的能量比当前解高出多少（在优化问题里，能量通常就是我们想最小化的目标函数值，所以 $\Delta E$ 大于零就意味着新解更差）。$T$ 就是当前温度，是一个正数。整个式子的意思是，新解变差的幅度 $\Delta E$ 越大，接受概率 $P$ 越低，而当前温度 $T$ 越高，接受概率 $P$ 越接近 $1$（也就是几乎照单全收）。

我们手动走几步感受一下。假设当前温度 $T=100$，新解比当前解差了 $\Delta E=10$，那么接受概率就是 $P=\exp(-10/100)=\exp(-0.1)\approx 0.905$，大概九成的差解都会被收下，相当宽松。温度降到 $T=10$ 的时候，同样的 $\Delta E=10$，$P=\exp(-10/10)=\exp(-1)\approx 0.368$，只剩大约三成七的概率，算法明显变挑剔了。再往下，温度降到 $T=1$，那 $P=\exp(-10/1)=\exp(-10)\approx 0.000045$，几乎为零，差解就基本进不来了。

这样大家就看得出来了，温度高的时候算法很敢冒险，差解也愿意收，四处试探不设防，温度低下来以后，算法越来越像贪心，只肯接受更好的解，慢慢收敛到一个地方稳定下来。这条从宽到严的过渡，正是模拟退火能跳出局部最优的关键。温度高时偶尔往下走的那几步，让算法有机会离开小山包，去攀另一座更高的山峰。

4.温度怎么降才合适

讲完准则，温度怎么从高降到低就成了下一个要紧的问题，这一步叫温度调度（temperature schedule）。调度方式选得好不好，直接决定算法能不能找到好的解。

最常见的是指数降温。设初始温度为 $T_0$（一开始的温度，是个比较大的正数），每一步把温度乘上一个略小于 $1$ 的降温系数 $\alpha$（$\alpha$ 通常取 $0.95$ 这样的值，是个介于 $0$ 和 $1$ 之间的常数），那么第 $k$ 步的温度就是：

$$T_k = T_0 \cdot \alpha^k$$

$k$ 是迭代的步数编号。这种降温方式简单好实现，所以用得最多。除了指数降温，还有线性降温（每步温度减去一个固定的值），或者更讲究一点的自适应降温（根据当前接受率动态调整），不过原理都差不多，核心就是温度单调往下走。

调温度这件事，两边都不好走。降温太快（$\alpha$ 太小，比如取 $0.5$），温度一下子就掉到底，算法还没怎么探索就被冻住了，多半会卡在一个糟糕的局部最优里，这就回到我们前面讲的淬火。降温太慢（$\alpha$ 取 $0.999$），算法是探索充分了，可温度一直降不下来，收敛速度慢得让人等不起，时间成本上不划算。

工程上有条经验做法，每个温度都让算法跑够一定步数（比如 $L$ 步，$L$ 是每个温度下的迭代次数），让当前温度下的探索尽量充分，再进入下一个温度。初始温度 $T_0$ 一般选得让初始接受率在 $0.8$ 上下，也就是说一开始大约八成的差解都会被接受，给探索留足余地。终止条件通常是温度低到某个阈值（比如 $T<0.01$），或者连续若干个温度都没有改进，就可以停了。

5.完整的算法流程

我们把前面这些拼起来，模拟退火的完整流程大概长这样。

第一步，初始化。随便挑一个解 $s$（$s$ 是当前解，可以是一组参数，也可以是一条路径），设初始温度 $T=T_0$。

第二步，在 $s$ 附近找一个候选解 $s'$（$s'$ 是通过对 $s$ 做一个小的扰动得到的，比如交换路径里两个城市的顺序）。

第三步，算能量差 $\Delta E = E(s') - E(s)$，这里的 $E(\cdot)$ 就是我们要最小化的目标函数（能量函数）。

第四步，决定要不要接受 $s'$。如果 $\Delta E < 0$（新解更好），直接接受，如果 $\Delta E \geq 0$（新解更差或者持平），就按概率 $P=\exp(-\Delta E/T)$ 决定接不接受。具体做法是生成一个 $0$ 到 $1$ 之间的随机数 $r$，如果 $r < P$ 就接受，否则留在原地。

第五步，重复第二步到第四步 $L$ 次，然后把温度降一点（比如 $T\leftarrow T\cdot\alpha$）。

第六步，温度降到阈值以下就停，输出当前找到的最好解。

整个流程其实非常简洁，几十行代码就能写出来，这是模拟退火很讨人喜欢的地方。它的核心就是Metropolis准则加上一个温度调度，剩下的都是工程细节。

6.优缺点要心里有数

任何算法都有自己的脾气，模拟退火也不例外，我们不妨把它的长短处都摊开看。

先说优点。第一，实现简单，前面那段流程就看得出来，比不少元启发式算法都要清爽。第二，能逃离局部最优，这一点归功于概率接受机制，是它区别于纯贪心最大的长处。第三，几乎什么目标都能套，目标函数不需要可导，甚至不连续都行，只要能算出能量值就能用，这让它能处理很多梯度下降无能为力的组合优化问题。

再说缺点。第一，要调的参数不少，初始温度 $T_0$、降温系数 $\alpha$、每个温度的迭代步数 $L$、终止温度，这几个参数选得好不好，对最终效果影响很大，并没有一套通吃所有问题的配方，得靠经验和实验去磨。第二，收敛速度偏慢，尤其在复杂问题上，往往要跑很久才能得到一个像样的解，急着出结果的时候不太顶用。第三，不保证找到全局最优，它只是给了更大的机会逃离局部最优，并不能承诺一定走到全局最高点，运气不好的时候还是会落在次优解上。

我记得小张去年准备秋招面一家搜索公司的算法岗，就被问到模拟退火调温度的经验，他当时讲不出个所以然，回来狠狠补了一通。这三条缺点，面试的时候要是答得出来，面试官多半会觉得你是真用过这个算法，而不只是背过一个名字。

7.几个经典应用场景

模拟退火最适合处理的，是那些解空间巨大、目标函数形状复杂、又难以求导的组合优化问题。我们挑几个最经典的说说。

最有名的例子是旅行商问题（Traveling Salesman Problem，简称TSP）。问题是这样的，给定一批城市和它们两两之间的距离，求一条经过每个城市恰好一次又回到起点的最短回路。听起来朴素，可城市数一多，所有可能的回路数量是阶乘级增长的，10个城市就有 $181440$ 条不同的回路，30个城市的回路数更是飙升到 $10^{30}$ 这个量级，暴力枚举根本走不通。模拟退火在这里就很合用，把回路长度当作能量 $E$，扰动方式就是随机交换路径里两段，按Metropolis准则走，温度慢慢降，经常能找到一条非常短的回路。我之前看过一篇讲物流配送调度的文章，里头说某家快递公司就用模拟退火给车辆规划路线，一年省下来的里程数相当可观。

第二个例子来自芯片设计。VLSI（超大规模集成电路）的物理设计里有一个步骤叫布局布线，要把成千上万个逻辑单元放到芯片上合适的位置，再用导线连起来，目标是最小化芯片面积、布线总长和信号延迟。这同样是一个解空间巨大、目标函数极其复杂的组合优化问题，而且目标函数根本没法求导。Kirkpatrick他们1983年那篇开创性的论文，用的正是VLSI布局作为示例，效果比当时主流的方法都要好，模拟退火也从此在EDA（电子设计自动化）行业扎下了根。小明如果去一家芯片公司实习，写布局工具的时候八成会碰到它。

除了这两个经典场景，模拟退火还常见于车间调度（怎么排机床的加工顺序）、图划分、神经网络的结构搜索，甚至蛋白质折叠的早期研究中也用过。凡是那种解空间太大、目标函数又乱的问题，都可以试一试模拟退火。有位长跑运动员曾经形容自己的训练节奏，说前半程要敢于压住速度去试探身体状态，后半程再逐步加力逼近极限，这套从宽到严的策略，跟模拟退火的降温调度其实意外地神似。

8.和遗传算法比一比脾气

最后我们把模拟退火和另一种很有名的元启发式算法，遗传算法（Genetic Algorithm，简称GA），放在一起比一比。遗传算法的灵感来自生物进化，它维护一群体解（叫种群），用选择、交叉（让两个解交换部分信息产生新解）和变异（随机改动解的一部分）这些操作让群体一代代演化，靠适应度（fitness，衡量解好坏的指标，越高越好）来挑选优胜者。它的核心概念还包括染色体（chromosome，一个解的编码形式）。

两种算法的目标是一样的，都是在巨大的解空间里找好解，可脾气差别不小。模拟退火是单点搜索，始终只维护一个当前解，靠Metropolis准则决定往哪儿走，逻辑简单，参数也少。遗传算法是群体搜索，同时维护一群解，靠群体里的信息交换来探索，理论上更不容易陷入局部最优，可实现复杂，参数更多（种群大小、交叉概率、变异概率等等），算起来也更吃资源。

打个不太严谨的比方。模拟退火像一位独自探险的登山者，靠一根手杖一步一步试探，偶尔赌一把往下走，整体轻便灵活。遗传算法像一支搜山队，人手多、信息互通，能同时摸好几条山脊，可队形和调度的开销也大。哪种更合适，要看具体问题的规模、对解质量的要求和能接受的计算时间。一般来说，问题不大、想快速上手，模拟退火往往更省心，问题特别复杂、又愿意花算力去搜，遗传算法的群体优势就显出来了。其实工程里还有把两者混着用的，叫混合元启发式，取长补短，这也是当前一个研究热点。

练习

Q1. 模拟退火的Metropolis准则 $P=\exp(-\Delta E/T)$ 里，$\Delta E$ 和 $T$ 各代表什么？温度高和温度低时，算法对"更差的解"态度有什么不同？

$\Delta E$ 是新解比当前解高出多少的能量（$\Delta E>0$ 表示新解更差），$T$ 是当前温度（正数）。温度高时 $\exp(-\Delta E/T)$ 接近1，算法很敢冒险、九成差解都愿意收、四处试探不设防；温度低时这个概率变得很小，算法越来越像贪心、只肯接受更好的解，慢慢收敛稳定。这条从宽到严的过渡，正是模拟退火能跳出局部最优的关键——高温时偶尔往下走的那几步让算法离开小山包，去攀另一座更高的山峰。

Q2. 指数降温 $T_k=T_0\cdot\alpha^k$ 里，降温系数 $\alpha$ 取太大（如0.999）和取太小（如0.5）分别有什么问题？

$\alpha$ 太小（降温太快，如0.5）温度一下子掉到底，算法还没怎么探索就被冻住，多半卡在糟糕的局部最优里，这就是"淬火"；$\alpha$ 太大（降温太慢，如0.999）算法探索是充分了，可温度一直降不下来，收敛速度慢得让人等不起，时间成本上不划算。所以 $\alpha$ 通常取0.95左右，在"充分探索"和"及时收敛"之间取折中，配合每个温度跑够一定步数再降温。

Q3. 易错点：模拟退火能"逃离局部最优"，是不是就一定能找到全局最优？

不能保证。模拟退火只是给了更大的机会逃离局部最优——靠Metropolis准则在高温时按概率接受差解，让它有办法先下山再上山。但它不承诺一定走到全局最高点，运气不好（比如温度调度没调好、初始解太差）还是会落在次优解上。它和遗传算法一样是随机算法，每次跑结果都可能不同，要靠调参（初始温度 $T_0$、降温系数 $\alpha$、每温度迭代步数 $L$）和多次运行来提升找到好解的概率，没有一招通吃所有问题的配方。