3. 模拟退火算法：物理背景、Metropolis准则、算法流程、温度衰减策略、代码实现与调参
3.1 物理背景：从铁匠铺到优化算法
模拟退火这个名字，其实是从冶金学里借来的。我当年第一次听到这个名词时，第一反应是：这跟打铁有什么关系？
你想想看，铁匠要把一块生铁锻造成一把好刀，得先把铁烧得通红，让原子获得足够能量四处乱跑，然后再慢慢冷却。冷却快了，原子来不及排列整齐，铁就变脆；冷却慢了，原子有足够时间找到能量最低的晶格位置，铁就变得坚韧。这个过程，就叫「退火」。
1983年，Kirkpatrick等人把这套物理过程搬到了优化领域。他们发现：组合优化问题里的「最优解」，就相当于金属晶体里的「最低能量状态」。而搜索过程中偶尔接受差解，就相当于高温下原子随机跳动——这恰恰是跳出局部最优的关键。
核心思想： 模拟退火算法通过控制「温度」参数，在搜索早期允许算法接受较差的解（探索），随着温度降低逐渐只接受更好的解（利用），最终收敛到全局最优附近。
3.2 Metropolis准则：接受还是拒绝？
这是模拟退火的心脏。说白了，就是回答一个问题：新解比当前解差，我到底要不要接受它？
Metropolis准则给出了一个概率公式：
P(接受差解) = exp( -ΔE / T )其中：
- ΔE = 新解的目标函数值 - 当前解的目标函数值（对于最小化问题，ΔE > 0 表示新解更差）
- T = 当前温度
这个公式告诉我们三件事：
- ΔE 越小（差得不远），接受概率越大
- T 越高（温度高），接受概率越大
- ΔE 为负（新解更好），直接接受，概率为1
我的经验： 在实际项目中，我习惯把 ΔE 归一化到目标函数值的量级范围内，否则 exp(-ΔE/T) 很容易溢出或趋近于0。比如目标函数值在 1e4 量级，ΔE 动辄几百上千，T 如果设成 100，exp(-10) ≈ 0.000045，几乎永远不接受差解——那跟爬山法就没区别了。
3.3 算法流程：三步走
模拟退火的流程其实很简洁，我把它总结成三步：
- 初始化：设定初始温度 T₀、终止温度 T_end、衰减率 α，随机生成初始解 x₀
- 外循环（降温）：在每个温度下，执行内循环；然后按衰减策略降温
- 内循环（搜索）：在当前温度下，重复 N 次：
- 从当前解 x 生成邻域解 x'
- 计算 ΔE = f(x') - f(x)
- 如果 ΔE < 0，接受 x'
- 否则，以概率 exp(-ΔE/T) 接受 x'
当温度降到 T_end 以下，或者连续若干次降温都没有改进时，算法终止。
我曾经踩过的坑： 内循环次数设得太少。有一次做旅行商问题（TSP），我设了内循环次数 = 城市数量，结果算法跑出来跟随机搜索差不多。后来改成 10 倍城市数量，效果才明显改善。内循环次数决定了「在当前温度下充分探索」的程度，太少等于没降温就急急忙忙收工。
3.4 温度衰减策略：怎么降温？
降温策略直接影响算法能不能找到好解。我整理了几种常见策略：
| 策略名称 | 公式 | 特点 | 适用场景 |
|---|---|---|---|
| 指数衰减 | T = T₀ × αk | 最常用，α 通常取 0.85~0.99 | 通用场景，调参简单 |
| 线性衰减 | T = T₀ - k × ΔT | 降温快，容易陷入局部最优 | 对解质量要求不高、追求速度 |
| 对数衰减 | T = T₀ / ln(1 + k) | 理论收敛性最好，但太慢 | 学术研究、小规模问题 |
| 自适应衰减 | 根据接受率动态调整 | 效果好，但实现复杂 | 工业级应用、调参经验丰富 |
我个人最常用的是指数衰减，α 取 0.95 左右。为什么？因为它在「降温速度」和「搜索质量」之间取得了不错的平衡。α 太大（比如 0.999），降温太慢，跑起来急死人；α 太小（比如 0.8），降温太快，跟没退火一样。
一个实用技巧： 我习惯在代码里加一个「回温」机制——如果连续若干次降温都没有改进，就把温度回升到上一个有效温度。这相当于给算法一次「重启」的机会，有时候能救回来。
3.5 代码实现：Python 实战
下面是一个完整的模拟退火实现，用来求解一个简单的函数最小值问题。我尽量把注释写清楚，方便你直接拿去改。
import numpy as np
import matplotlib.pyplot as plt
def objective(x):
"""目标函数：f(x) = x^2 + 4*sin(5x) + 0.1*x"""
return x**2 + 4*np.sin(5*x) + 0.1*x
def simulated_annealing(
x0, # 初始解
T0=100, # 初始温度
T_end=1e-3, # 终止温度
alpha=0.95, # 衰减率
inner_iters=100, # 内循环次数
step_size=0.5 # 邻域搜索步长
):
x_current = x0
f_current = objective(x_current)
x_best = x_current
f_best = f_current
T = T0
history = []
while T > T_end:
for _ in range(inner_iters):
# 生成邻域解：在当前解附近随机扰动
x_new = x_current + np.random.uniform(-step_size, step_size)
f_new = objective(x_new)
delta = f_new - f_current
# Metropolis 准则
if delta < 0:
x_current = x_new
f_current = f_new
else:
p = np.exp(-delta / T)
if np.random.rand() < p:
x_current = x_new
f_current = f_new
# 记录全局最优
if f_current < f_best:
x_best = x_current
f_best = f_current
history.append((T, f_best))
T *= alpha # 指数衰减
return x_best, f_best, history
# 运行
x_opt, f_opt, hist = simulated_annealing(x0=2.0)
print(f"最优解: x = {x_opt:.4f}, f(x) = {f_opt:.4f}")调参建议： 这段代码里，step_size 很关键。设太大，新解可能跳到很远的地方，算法像无头苍蝇；设太小，只能在原地打转，探索能力不足。我一般从 step_size = 0.1 * (变量取值范围) 开始试，然后根据接受率调整——理想接受率在 0.4~0.6 之间。
3.6 调参实战：四个关键旋钮
模拟退火的调参，说白了就是拧四个旋钮。我按重要性排个序：
- 初始温度 T₀：太高了浪费时间，太低了直接变爬山法。一个经验法则是：让初始接受率在 0.8 左右。你可以先跑一小段，统计一下差解的 ΔE 均值，然后反推 T₀。
- 衰减率 α：0.85~0.99 之间。α 越大，搜索越精细，但耗时越长。我一般从 0.95 开始调。
- 内循环次数：跟问题规模正相关。对于 100 维的问题，内循环 500~1000 次不算多。
- 邻域生成方式：这是最容易被忽略的。对于连续问题，高斯扰动 vs 均匀扰动差别很大；对于离散问题，交换、反转、插入等操作的选择直接影响搜索效率。
我曾经犯过的错： 有一次做排产优化，我用了均匀扰动生成邻域解，结果算法总是在几个局部最优之间来回跳，就是找不到全局最优。后来改成高斯扰动（标准差随温度降低而减小），效果立竿见影。邻域生成方式一定要跟问题结构匹配，这是模拟退火调参里最「艺术」的部分。
3.7 知识结构总览
下面这张图把模拟退火的核心脉络串起来了，方便你对照复习。
3.8 小结
模拟退火是我个人非常喜欢的一种算法。它不要求目标函数可导，不要求凸性，实现起来也不复杂。但它的「温柔」也意味着——如果你不认真调参，它可能跑得比随机搜索还差。
记住三个关键点：Metropolis准则给了你跳出局部最优的勇气，温度衰减策略决定了你能走多远，邻域生成方式决定了你每一步踩得准不准。把这三点吃透了，模拟退火就是你工具箱里一把趁手的兵器。