3. 模拟退火算法：从物理退火到全局优化

模拟退火（Simulated Annealing, SA）是我个人非常偏爱的一种算法。为什么？因为它背后的思想实在太直观了——说白了，就是把金属热处理工艺里的「退火」过程，搬到了数学优化里。你想想看，一块烧红的铁，慢慢冷却下来，原子会排列成能量最低的晶体结构。那我们的优化问题，能不能也这样「冷却」出全局最优解？

答案是肯定的。1983年，Kirkpatrick等人把这个想法变成了算法。今天我们就来拆解它。

3.1 物理退火的启发

先聊聊物理退火是怎么回事。金属加热到高温后，原子剧烈运动，系统处于高能状态。然后缓慢降温，原子逐渐趋于有序排列。如果降温速度足够慢，最终会形成完美的晶体——也就是全局能量最低的状态。

映射到优化问题：

物理退火	模拟退火算法
系统状态	可行解
能量	目标函数值
温度	控制参数（接受劣解的概率）
缓慢降温	温度衰减函数
晶体结构（基态）	全局最优解

这个映射非常漂亮。核心思想是：在搜索初期允许算法「犯错」——接受更差的解，从而跳出局部最优；随着搜索进行，犯错概率逐渐降低，最终收敛到全局最优。

3.2 Metropolis准则：接受还是拒绝？

这是模拟退火的核心决策机制。每次迭代，我们从当前解 x 生成一个新解 x'，计算能量差 ΔE = f(x') - f(x)。然后按以下规则决定是否接受：

• 如果 ΔE < 0（新解更好）：无条件接受。
• 如果 ΔE ≥ 0（新解更差）：以概率 P = exp(-ΔE / T) 接受。

这个概率公式就是 Metropolis 准则。温度 T 越高，接受劣解的概率越大；温度趋近于 0 时，概率趋近于 0，算法退化为贪心搜索。

我在项目中遇到过一个问题：初始温度设得太低，算法几乎不接受劣解，结果陷入了局部最优。后来我养成了一个习惯——先用随机采样估算一下目标函数值的波动范围，再据此设定初始温度。

3.3 温度衰减函数

温度怎么降？这直接决定了算法的搜索行为。常用的衰减函数有几种：

衰减方式	公式	特点
指数衰减	Tk+1 = α · Tk，α ∈ (0.8, 0.99)	最常用，降温快，α 控制衰减速度
对数衰减	Tk = T0 / log(1 + k)	理论收敛性最好，但降温极慢
线性衰减	Tk = T0 - β · k	简单直观，但需要预设迭代次数
自适应衰减	根据接受率动态调整	灵活，但实现复杂

我个人习惯用指数衰减，α 取 0.95 左右。为什么？因为它在搜索质量和计算效率之间取得了很好的平衡。对数衰减虽然理论完美，但实际中你等不起——我曾经试过一次，跑了三天还没收敛到可接受的范围。

3.4 算法流程

把上面这些拼起来，就是完整的模拟退火算法流程。我习惯用伪代码来描述，清晰明了：

1. 初始化：生成初始解 x，设定初始温度 T₀，终止温度 T_min，衰减系数 α
2. 外循环（温度循环）：
   while T > T_min:
       3. 内循环（马尔可夫链）：
          for i = 1 to L:  // L 为每个温度下的迭代次数
              4. 生成新解 x'（在当前解附近扰动）
              5. 计算 ΔE = f(x') - f(x)
              6. 应用 Metropolis 准则：
                  if ΔE < 0:
                      x = x'  // 接受更好解
                  else:
                      if random(0,1) < exp(-ΔE / T):
                          x = x'  // 以概率接受劣解
          end for
       7. 降温：T = α * T
   end while
8. 输出最优解 x_best

嗯，这里要注意内循环的迭代次数 L。L 太小，每个温度下的搜索不充分；L 太大，计算量暴增。我一般设 L 为问题维度的 10~100 倍，或者根据接受率动态调整——当接受率低于 10% 时，说明这个温度下已经很难找到更好的解了，可以提前降温。

3.5 参数调优：避坑指南

模拟退火有四个关键参数：初始温度 T₀、终止温度 T_min、衰减系数 α、内循环次数 L。调参是门手艺活，我踩过不少坑。

下面是我总结的参数调优策略：

参数	调优方法	参考范围
T₀	随机采样 100~1000 个解，计算目标函数值的标准差 σ，设 T₀ = k·σ，k 取 5~20	使初始接受率在 0.8~0.95
T_min	设为一个很小的正数，或当连续多次迭代最优解无改善时终止	1e-3 ~ 1e-8
α	从 0.95 开始，观察收敛曲线，若收敛太快则增大，太慢则减小	0.85 ~ 0.99
L	设为问题维度的 10~100 倍，或根据接受率动态调整	100 ~ 10000

3.6 核心逻辑流程图

下面这张 SVG 图展示了模拟退火算法的核心逻辑。我把它画成了流程图，方便你理解整个决策链条。

3.7 实际应用中的注意事项

最后聊几个实战中容易忽略的点：

• 邻域结构设计：新解的生成方式直接影响搜索效率。对于连续问题，我常用高斯扰动；对于离散问题，交换或反转操作更合适。邻域太大，搜索太随机；邻域太小，容易陷入局部。
• 重启策略：如果发现算法陷入停滞，可以保存当前最优解，然后重新加热到较高温度再冷却。这相当于给了算法第二次机会。
• 并行化：模拟退火天然适合并行。多个独立链同时搜索，定期交换最优解，能显著提升收敛速度。