模拟退火算法

定义

模拟退火算法是一种求解最优化问题的随机搜索方法，用于在解空间中找到目标函数的近似全局最优解。它把固体退火过程与一般优化问题对应起来：固体的内能被看作待优化的目标函数，温度被看作控制搜索随机程度的参数，粒子状态被看作问题的可行解^[1][3]。

与只能沿着目标函数下降方向前进的方法不同，模拟退火算法在每一步都会产生一个邻域内的候选解，并按照一条与温度相关的概率规则判断是否接受它。目标函数变好的解总是被接受，变差的解则以一定概率被接受，该概率随温度降低而减小。正是这种对较差解的有限接受，使搜索能够脱离局部最优^[2][4]。

原理

算法的物理背景是冶金中的退火：材料被加热到高温后缓慢冷却，原子有足够的热运动越过能量壁垒，最终落入能量较低的晶体结构；如果冷却过快，原子来不及重新排列，缺陷就被冻结下来^[2]。模拟退火算法把这一过程搬到计算中：解空间的每个点对应一种原子构型，目标函数值对应内能，温度控制搜索的接受范围^[5][4]。

算法在固定温度下的单步过程是：对当前解施加随机扰动得到新解，计算目标函数增量 $\Delta f$；若 $\Delta f < 0$，即新解更优，则无条件接受；若 $\Delta f \geq 0$，则以概率 $p = e^{-\Delta f / T}$ 接受，其中 $T$ 为当前温度。温度高时较大的恶化也被容许，温度低时只接受较小的恶化，温度趋近于零时几乎只接受改善解^[6][2]。

温度的下降方式由冷却进度表决定，常见形式包括几何降温 $T_{k+1} = \alpha T_k$（$\alpha$ 通常取 0.8 至 0.99）、对数降温、线性降温等。理论上对数降温可以保证渐近收敛到全局最优，但速度太慢；几何降温在实用中最常见。初始温度一般设得足够高，使搜索初期大部分恶化解都能被接受^[2][7]。

在固定温度下反复执行上述单步，状态序列构成一条马尔可夫链，其平稳分布与 $e^{-f(x)/T}$ 成正比；当温度趋近于零时，该分布的质量集中在目标函数的主要极小点上。这一性质把模拟退火算法与统计物理中的 Metropolis-Hastings 方法联系起来，也是其理论基础的来源^[6]。

flowchart TD

A[设置初始温度 T 与初始解 x] --> B[在邻域内产生新解 x']

B --> C[计算 Δf = f-x']

C --> D{Δf < 0 ?}

D -- 是 --> E[接受新解]

D -- 否 --> F[以概率 exp-Δf/T 接受新解]

E --> G{该温度下迭代足够?}

F --> G

G -- 否 --> B

G -- 是 --> H[按冷却进度表降低 T]

H --> I{满足停止条件?}

I -- 否 --> B

I -- 是 --> J[输出当前最优解]

发展历程

算法所依赖的接受准则源自 1953 年 N. Metropolis 及其合作者提出的蒙特卡洛抽样方法。他们在计算气体状态方程时引入按概率接受新状态的思路，被称为 Metropolis 准则，这一方法此后被广泛用于统计物理与数值计算^[1][8]。

1983 年，S. Kirkpatrick、C. D. Gelatt 与 M. P. Vecchi 在《科学》杂志上发表论文，明确把退火思想引入组合优化领域，并将其用于电路布线等多类问题。同一时期，V. Černý 也独立提出了类似方法。此后该算法扩展到连续函数优化，逐步成为一种通用优化算法^[4][9]。

20 世纪 80 年代后期，van Laarhoven 与 Aarts 出版专著系统整理了该算法的理论、冷却进度表设计与应用，标志着其从物理类比走向标准的最优化方法^[10]。1995 年前后，自适应模拟退火等改进形式出现，通过让降温策略与函数值或接受率相关联减少后期无效搜索^[9][3]。

进入 21 世纪后，研究者进一步把该算法与遗传算法等启发式方法结合，构造出遗传模拟退火算法等混合形式；并行与分布式实现也被用来缓解其计算耗时问题^[11][12]。

应用

模拟退火算法最早的大规模应用之一是超大规模集成电路（VLSI）设计。IBM 的研究者用它来安排芯片上元件的位置并优化连线，目标是在缩短连线长度的同时均衡连线分布；结合问题自身的启发式规则后，其结果明显优于随机布线方案^[13][1]。

在组合优化领域，该算法被广泛用于旅行商问题、0-1 背包问题、装箱问题与车辆路径问题等。对于城市数量较多的旅行商问题，可能的路径数量随规模呈阶乘式增长，精确求解困难，而模拟退火算法能在可接受的时间内给出接近最优的路线^[14][3]。

工程领域的使用还包括生产调度与车间作业排程、控制工程中的参数整定、物流配送路径优化以及结构设计中的离散变量优化。在这些问题中，目标函数往往不连续、不可导或带有复杂约束，梯度类方法难以直接使用^[15][16]。

在信号与信息处理方向，模拟退火算法被用于图像分割与图像复原、滤波器设计，以及从重力梯度数据估计海底地形等地球物理反演问题；在机器学习中则用于神经网络权重与结构的优化^[15][17]。

局限

模拟退火算法在理论上具有收敛到全局最优的性质，但这一结论依赖足够慢的降温过程。保证渐近收敛所需的逆对数降温在实用中过于缓慢，因此实际运行中通常无法确认所得结果就是全局最优解^[13][2]。

算法的收敛速度慢、执行时间长，是其被反复指出的缺点。由于每个温度下都要执行多次 Metropolis 抽样，问题规模较大时求解耗时可能高到不可接受，这也促使研究者发展并行与分布式的实现方案^[18][12]。

算法性能对初始解与参数设置较为敏感，初始温度、降温系数和每个温度下的迭代次数选择不当往往得不到满意结果，而这些参数通常需要针对具体问题通过实验反复调整^[19][15]。

算法本身带有随机性，对同一问题多次运行可能得到不同结果，无法像确定性方法那样复现同一输出^[20]。此外，当解空间中局部最优解与全局最优解之间障碍较高时，算法跳出该局部最优的可能性会变小，搜索有效性随之下降^[21]。

参见

• Metropolis 准则 —— 决定是否接受恶化新解的概率基准，是模拟退火算法的核心步骤。

• 蒙特卡洛方法 —— 模拟退火算法所依据的随机抽样思想来源。

• 遗传算法 —— 另一类启发式全局优化方法，常与模拟退火算法结合使用。

• 旅行商问题 —— 检验模拟退火算法求解组合优化问题的经典算例。

• 局部搜索 —— 模拟退火算法由以改进的搜索框架，容易陷入局部最优。

• 玻尔兹曼机 —— 在神经网络中引入模拟退火式随机接受机制的模型。