模拟退火

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

爬山法每一步只接受更好的邻居，路径单调下降，看起来最「聪明」，却会在第一个盆地底停住。只要能量地形不是单峰，这个停住就几乎必然发生；你从当前值无法判断外面是否还有更深的谷。它缺的不是勇气，而是一条允许暂时变差、从而翻过山脊的规则。

纯随机游走每一步在合法状态里乱跳，理论上能到任何地方，却把已经发现的好区域立刻忘掉。没有「更好就一定接受」的偏置，也没有随时间收紧的温度，搜索预算会耗在近似均匀的撒点上。它缺的不是随机性，而是方向。

模拟退火夹在两者之间：更好的邻居永远接受，更差的邻居按 $e^{-\Delta E/T}$ 接受，且这个概率随温度下降而减小。高温时它像带着偏置的探索，低温时它越来越像爬山。它既不是贪心，也不是掷骰子碰运气——Metropolis 准则给出的，是一条随温度连续变形的接受规则。

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

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

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

当年的计算跑在 MANIAC 上，对象是二维硬球的物态方程，论文报告了 224 个粒子的模拟。Metropolis 准则要保证的是采样：链的平稳分布等于玻尔兹曼分布，能量升高的构型必须被按正确频率接受，否则压强和密度都会算偏。它当时不是爬山，也不是找基态；把同一公式改读成优化，是三十年后的事。Černý 1985 年在旅行商问题上独立给出热力学类比，说明这条跨界对统计物理背景的人是自然的，Kirkpatrick 等人的 Science 论文则把它命名为模拟退火并推到 VLSI 布局这类工程问题上。

核心算法#

模拟退火模仿统计力学中的玻尔兹曼分布（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}$ 衰减得足够和缓，使每个状态在无穷时间中被访问无穷多次，理论上没有任何陷阱能永远困住它。代价同样清楚：这个"足够慢"比任何实际问题允许的时间都慢，保证全局最优所需的时间并不比穷举好多少。这就是理论保证与工程实践之间那道不可调和的缝——工程上用指数冷却，等于主动放弃"必然最优"，换取"足够好且足够快"。

Geman 与 Geman 给出的是充分条件。Hajek 在 1988 年把对数冷却的关键常数钉死：若 $T_k = c/\log(1+k)$，则 $c$ 必须不小于最深那个非全局局部最优的深度，状态才会依概率收敛到全局最优集。这里的深度不是目标函数值之差，而是沿邻域走、翻出该盆地所必须越过的最低壁垒。

工程常用的指数冷却明确不满足这条慢条件，所以它不该被说成「理论上保证最优的实用算法」。冷却计划只规定温度何时收紧；邻域结构才规定你能翻哪些壁垒，两者必须一起看。

典型应用：旅行商问题#

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

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

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

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

这些应用有一个共同点：解可以定义成「当前构型加一个小改动」，能量是可计算的标量。没有这种邻域，模拟退火就没有可走的图，温度再精致也无处着力。它适合的是组合地形上的局部搜索，而不是把搜索空间当成可以任意跳跃的黑盒。

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

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

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

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

邻域还决定这件事到底是不是局部搜索。若一步就能跳到状态空间里几乎任意一点，温度机制会退化成带接受率的随机跳；若邻域把图切成互不连通的碎片，高温也走不出自己的连通片。旅行商的 2-opt 每次只改两条边，长度变化平滑，接受率才能被温度细调——它不是「随机试一条新路线」，而是在当前回路的附近做小改动。

换一组更猛的扰动，典型能量差变大，同一张冷却表会突然显得太冷或太热。设计模拟退火，首先是在设计一张可走的图，其次才是在这张图上调节温度。

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

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

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

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

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

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

温度、冷却和邻域必须成套标定，因为接受率是 $\Delta E$ 与 $T$ 的比，而 $\Delta E$ 由邻域决定。只抄一张指数冷却的表，等于假装所有问题的能量台阶一样高。标定错了，算法会变成另一种东西：要么过早冻成爬山，要么一直接近随机接受。

代价与争议#

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

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

与遗传算法的比较：

两者都属于元启发式算法，没有普遍的优劣之分——"没有免费的午餐定理"（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.
• Černý, V. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications 45 (1985): 41–51.
• Hajek, B. Cooling Schedules for Optimal Annealing. Mathematics of Operations Research 13, no. 2 (1988): 311–329.
• 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.