模拟退火

金属工匠早在几千年前就知道：将金属加热到高温后缓慢冷却（退火），能使原子找到低能量的稳定排列，消除内部应力，使材料更坚韧。1983 年，IBM 研究员柯克帕特里克（Scott Kirkpatrick）、葛莱特（C. D. Gelatt）和韦奇（M. P. Vecchi）将这个物理过程翻译成了优化算法——模拟退火（Simulated Annealing），同年发表于《科学》杂志。

这个算法的核心洞见：允许优化过程偶尔"变差"，是为了最终找到更好的解。

破除误解：不是爬山法，也不是随机游走#

局部搜索（爬山法）：每步只接受更好的解，必然陷入局部最优。

随机游走：完全随机移动，没有方向性，极度低效。

模拟退火在两者之间：它有方向性地向更好的解移动，同时以一定概率接受更差的解，且这个概率随时间（温度）降低而减小。这种设计使算法在初期广泛探索，后期收敛到好的解。

它的真正源头：1953 年的 Metropolis 算法#

模拟退火常被当作 1983 年的发明，但它的数学心脏要早三十年。1953 年，洛斯阿拉莫斯实验室的 Metropolis 等五人（论文署名包括 Nicholas Metropolis、Marshall Rosenbluth、Edward Teller 等）提出了一种用计算机模拟物质热平衡的方法——后世称为"Metropolis 算法"：以概率 $e^{-\Delta E / T}$ 接受能量升高的状态，从而正确采样玻尔兹曼分布。

柯克帕特里克等人的洞见是把这套"模拟物理"的工具反过来用作"优化工具"：如果把"待优化的目标函数"当成"能量"，把"逐渐降温"当成"逐渐收紧搜索"，那么模拟物理退火的程序就变成了寻找最优解的算法。这是计算物理与组合优化之间一次漂亮的跨界——同一个数学公式，换一个解释，就从描述自然变成了改造工程。

核心算法#

模拟退火模仿统计力学中的玻尔兹曼分布（Boltzmann Distribution）：系统在温度 $T$ 时处于能量为 $E$ 的状态的概率正比于 $e^{-E/(k_B T)}$。

算法框架：

初始化：随机解 x，温度 T = T_max
重复：
  从 x 的邻域随机选取候选解 x'
  计算能量差 ΔE = E(x') - E(x)
  若 ΔE < 0（x' 更好）：接受 x'
  若 ΔE >= 0（x' 更差）：以概率 exp(-ΔE / T) 接受 x'
  按冷却计划降低 T
直到 T 足够低或达到迭代上限
```

接受概率公式：

$$P(\text{accept}) = \begin{cases} 1 & \text{if } \Delta E < 0 \\ e^{-\Delta E / T} & \text{if } \Delta E \geq 0 \end{cases}$$

当温度 $T$ 很高时，$e^{-\Delta E / T} \approx 1$，几乎接受所有解（大范围探索）。

当温度 $T$ 趋近于零时，$e^{-\Delta E / T} \approx 0$，几乎只接受改进（收敛到局部最优）。

为什么是这个接受公式，而不是别的？因为它不是拍脑袋的启发式，而是精确复刻了平衡态统计力学的结论：在温度 $T$ 达到热平衡的系统，处于能量 $E$ 状态的概率正比于 $e^{-E/(k_B T)}$；两个能量相差 $\Delta E$ 的状态，平衡种群之比恰为 $e^{-\Delta E / T}$。Metropolis 接受准则被构造出来，正是为了让模拟产生的状态分布与这个玻尔兹曼分布一致。高温时分布接近均匀，各种构型几乎等可能（探索）；低温时分布集中到最低能构型附近（利用）。退火的本质，是让系统依次经过一系列平衡分布，而不是直接冲向最低点。

冷却计划的重要性#

冷却计划（Cooling Schedule）决定温度如何随时间下降，是影响算法性能的关键：

理论上，若温度按对数计划降低，模拟退火能以概率 1 收敛到全局最优（S. Geman & D. Geman, 1984）——但所需时间在实际中不可接受。工程中使用的是折中方案，收敛到"足够好"的解。

为什么偏偏是对数形式？Geman 与 Geman 的条件大致是 $T_k \geq \Gamma / \log(1 + k)$，其中 $\Gamma$ 是与问题能量地形中最深壁垒相关的常数。直觉是这样的：要保证找到全局最优，算法必须永远保留"爬出最深的局部最优陷阱"的可能。翻过高度为 $\Delta$ 的能垒，单步接受概率是 $e^{-\Delta / T}$。指数冷却下温度下降太快，若干步之后这个概率小到在剩余计算时间里实际为零——链被"冻死"在某个盆地里，收敛保证随之作废。对数冷却慢到让 $e^{-\Delta / T_k}$ 衰减得足够和缓，使每个状态在无穷时间中被访问无穷多次，理论上没有任何陷阱能永远困住它。代价同样清楚：这个"足够慢"比任何实际问题允许的时间都慢，保证全局最优所需的时间并不比穷举好多少。这就是理论保证与工程实践之间那道不可调和的缝——工程上用指数冷却，等于主动放弃"必然最优"，换取"足够好且足够快"。

典型应用：旅行商问题#

旅行商问题（TSP）：给定 $n$ 个城市，找一条访问每个城市恰好一次并回到起点的最短回路。

TSP 是 NP 难问题，$n = 100$ 时精确解法在宇宙寿命内无法穷举。模拟退火的处理方式：

• 状态空间：所有城市的排列
• 邻域操作：随机反转路径中的一段（2-opt 移动）
• 能量函数：路径总长度
• 结果：通常能在秒级时间内找到接近最优解 1–5% 以内的解

模拟退火曾用于设计早期 VLSI 芯片布局（这正是柯克帕特里克等人 1983 年论文的最初动机：在芯片上摆放成千上万个元件、使连线总长最短，是一个巨大的组合优化问题），以及作业车间调度、网络拓扑优化、蛋白质构象搜索等问题。它至今仍是工程师手边一件"几页代码就能跑、不需要问题有任何良好数学结构"的通用工具——这正是它历久不衰的原因。

邻域结构：真正的设计自由度#

冷却计划常被当成模拟退火的全部学问，但实践中更影响成败的是邻域结构——"从当前解走一步能到达哪些解"。它定义了搜索空间的拓扑，等价于决定算法在一张什么样的图上行走。

• 邻域太大：每步几乎随机跳，退化成低效的随机游走，温度机制失去意义。
• 邻域太小：图被切成许多孤岛，算法轻易被困在出发的盆地里。
• 好的邻域让"能量相近的解彼此相邻"：TSP 的 2-opt（反转一段路径）之所以经典，是因为它每次只改动两条边，路径长度的变化 $\Delta E$ 小而平滑，温度才能精细地控制接受率。

邻域还决定了温度的量纲：典型 $\Delta E$ 的量级就是 $T$ 该有的量级。换一组邻域操作，整个冷却计划要重新标定——这就是为什么模拟退火的调参经验难以跨问题直接搬运。

调参的直觉：温度该怎么设#

模拟退火最让新手头疼的是参数，但背后的直觉其实很物理。

初始温度 $T_\text{max}$ 要足够高，使算法在开始时几乎"什么都接受"——一个常用的经验做法是：先随机走几步，统计能量差的典型量级，再把 $T_\text{max}$ 设成让初始接受率约 80%–90% 的值。温度太低，算法一开始就被困在出发点附近；太高，则前期纯属浪费。

冷却速率 $\alpha$（指数冷却中常取 0.90–0.99）决定"耐心"：越接近 1，降温越慢、探索越充分、也越慢。

每个温度下的迭代次数让系统在该温度上"达到热平衡"再降温，否则等于没充分探索就提前收紧。

这里有一个深刻的权衡：理论保证（对数冷却下以概率 1 收敛到全局最优）要求近乎无限的时间；工程实践则在"解的质量"和"计算预算"之间做交易。换句话说，模拟退火不承诺最优，它承诺的是"在你愿意花的时间内，给你一个相当好的解"。

代价与争议#

参数敏感：初始温度、冷却速率和终止条件对结果影响极大，需要大量试验调参，且对不同问题往往需要重新调参。

无收敛保证（实践中）：理论上的收敛保证要求对数冷却，这在实际中不可行。工程应用是在有限时间内找到"好"解，但不保证是全局最优。

与遗传算法的比较：

两者都属于元启发式算法，没有普遍的优劣之分——"没有免费的午餐定理"（No Free Lunch Theorem）告诉我们，对所有问题平均来看，没有任何启发式算法优于随机搜索。

如果一定要在两者之间分工，经验规律是：模拟退火擅长"精修"，遗传算法擅长"组装"。当解空间有较好的局部结构——好解附近往往还是好解（调度、布局、连续参数优化大多如此）——单点搜索加温度控制就能高效收敛。当问题的优势来自模块组合——把甲方案的一个部件和乙方案的一个部件拼起来可能产生质的飞跃——种群的交叉操作提供了单点突变给不了的"积木重组"能力。工程实践里两者也常串成流水线：先用遗传算法做全局探索，圈出若干有希望的区域，再用模拟退火在每个区域内精修到局部最优。

跨域连接#

• 热力学定律：接受概率直接照搬玻尔兹曼分布：温度越高，越容易接受能量升高的状态。降温的意义是让系统始终近似停在当前温度的平衡分布上——降太快，系统来不及重新平衡，就被冻在出发点附近的构型里。冷却计划不是调参技巧，它决定了近似的是哪个分布。
• 金属与合金：算法名字有一个字面的冶金对应。缓慢冷却让原子有时间重排、位错与残余应力被消除；淬火则把缺陷原样冻住。"快冷会卡在局部最优"在真实材料里不是比喻，它就是硬而脆的那块金属。
• 蒙特卡洛方法：那条接受准则原本是用来采样平衡态分布的，属于"模拟自然"的工具。把目标函数当成能量、把降温当成收紧搜索，同一个公式就从描述变成了改造——这是一次纯粹的重新解释，公式一个字没改。
• 随机过程：在足够慢的对数冷却下，可以证明以概率一收敛到全局最优；但所需时间在任何实际预算里都不可接受。理论保证与工程可行在这里明确分家：工程用的指数冷却不承诺最优，只承诺"在你愿意花的时间内给一个相当好的解"。
• 蛋白质折叠：能量地形的形状决定了搜索能否成功。真实的折叠地形不是高维乱地，而是带有整体偏置的漏斗，所以体系能在极短时间里找到低能构型。这反过来给算法划了界：模拟退火的效率主要由地形结构决定，而不由算法本身决定。

参考文献#

• Kirkpatrick, S., Gelatt, C. D. & Vecchi, M. P. Optimization by Simulated Annealing. Science 220, no. 4598 (1983): 671–680.
• Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H. & Teller, E. Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics 21, no. 6 (1953): 1087–1092.
• Geman, S. & Geman, D. Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images. IEEE Transactions on Pattern Analysis and Machine Intelligence 6, no. 6 (1984): 721–741.
• Wolpert, D. H. & Macready, W. G. No Free Lunch Theorems for Optimization. IEEE Transactions on Evolutionary Computation 1, no. 1 (1997): 67–82.

延伸阅读#

• Aarts, E. & Korst, J. Simulated Annealing and Boltzmann Machines. Wiley, 1989.
• Johnson, D. S. & McGeoch, L. A. The Traveling Salesman Problem: A Case Study. In Local Search in Combinatorial Optimization. Wiley, 1997.