3. 模拟退火算法：物理退火启发、算法流程、温度衰减策略
模拟退火，这个名字听起来挺玄乎。说白了，它就是从金属退火这个物理过程里偷师学来的。
我记得刚入行那会儿，带我的老工程师跟我说：“你想想看，一块烧红的铁，你直接扔冷水里淬火，它容易裂；你要是让它慢慢降温，它反而更结实。” 我当时就想，这跟算法优化有什么关系？后来才明白，这恰恰是全局优化最核心的思想——先接受一些“坏”的解，才有机会跳出局部最优。
3.1 物理退火与算法优化的映射关系
我们先看看物理退火是怎么回事。金属被加热到高温时，内部粒子变得非常活跃，可以自由移动。随着温度缓慢下降，粒子逐渐趋于有序排列，最终形成能量最低的稳定晶格结构。
模拟退火算法把这个过程抽象成了数学模型：
| 物理退火 | 模拟退火算法 |
|---|---|
| 粒子状态 | 问题的可行解 |
| 系统能量 | 目标函数值 |
| 温度 | 控制参数（决定接受差解的概率） |
| 缓慢降温 | 温度衰减策略 |
| 最低能量状态 | 全局最优解 |
这个映射非常巧妙。物理退火中，高温时粒子可以“乱跑”，对应算法在早期可以接受较差的解；低温时粒子趋于稳定，对应算法后期只接受更好的解。
核心思想：模拟退火通过概率性接受差解，避免算法过早陷入局部最优。这是它与贪心算法、梯度下降法最本质的区别。
3.2 算法流程：从高温到低温的旅程
模拟退火的流程其实不复杂。我习惯把它分成四个阶段：
- 初始化：设定初始温度 T₀、终止温度 T_end、温度衰减系数 α，随机生成初始解 x₀。
- 内循环：在当前温度下，反复进行“产生新解 → 计算能量差 → 决定是否接受”的过程。
- 降温：按照衰减策略降低温度。
- 终止判断：如果温度低于 T_end 或连续多次没有改进，输出当前最优解。
这里最关键的是第二步——接受准则。它用的是 Metropolis 准则：
if ΔE < 0:
接受新解（能量降低，肯定要接受）
else:
以概率 P = exp(-ΔE / T) 接受新解（能量升高，但有一定概率接受）为什么会这样？你想想看，如果能量升高就一律拒绝，那不就是爬山法吗？模拟退火的精髓就在于，温度高的时候，接受差解的概率大；温度低的时候，接受差解的概率小。这个概率由 exp(-ΔE / T) 控制。
我的经验：内循环的次数很关键。次数太少，在当前温度下探索不充分；次数太多，计算量暴增。我一般设置为问题规模的 10-100 倍，或者用“接受次数达到一定阈值”作为内循环终止条件。
3.3 温度衰减策略：降温的艺术
温度怎么降，直接决定了算法能不能找到全局最优。我见过不少项目，算法跑不出来，问题就出在降温策略上。
常用的衰减策略有三种：
| 策略名称 | 公式 | 特点 | 适用场景 |
|---|---|---|---|
| 指数衰减 | Tₖ₊₁ = α · Tₖ | 降温快，早期探索充分，后期收敛快 | 大多数通用问题 |
| 对数衰减 | Tₖ = T₀ / ln(k + 1) | 降温极慢，理论上保证收敛到全局最优 | 理论分析、小规模问题 |
| 线性衰减 | Tₖ = T₀ - β · k | 降温均匀，但后期温度可能降得太快 | 对实时性要求高的场景 |
我个人最常用的是指数衰减，α 取 0.85 到 0.99 之间。α 越接近 1，降温越慢，搜索越精细，但耗时也越长。
避坑指南：我曾经在一个 TSP 问题（旅行商问题）上，把 α 设成了 0.8，结果跑了 5 分钟就收敛了，但解的质量很差。后来改成 0.95，跑了 20 分钟，解的质量提升了 30%。所以，α 的选择要在“搜索质量”和“计算时间”之间做权衡。
3.4 模拟退火核心流程图
下面这张图把整个流程串起来了。你可以对照着看，每一步做什么，一目了然。
3.5 一个简单的代码示例
光说不练假把式。下面是一个求解函数 f(x) = x² 最小值的模拟退火实现。虽然问题简单，但代码结构是通用的。
import math
import random
def simulated_annealing(initial_temp, end_temp, alpha, max_iter):
# 初始化
current_x = random.uniform(-10, 10)
current_energy = current_x ** 2
best_x = current_x
best_energy = current_energy
T = initial_temp
while T > end_temp:
# 内循环
for _ in range(max_iter):
# 产生新解（在当前解附近扰动）
new_x = current_x + random.uniform(-1, 1)
new_energy = new_x ** 2
# 计算能量差
delta_e = new_energy - current_energy
# Metropolis 准则
if delta_e < 0:
current_x = new_x
current_energy = new_energy
# 更新全局最优
if new_energy < best_energy:
best_x = new_x
best_energy = new_energy
else:
# 以概率接受差解
if random.random() < math.exp(-delta_e / T):
current_x = new_x
current_energy = new_energy
# 降温
T *= alpha
return best_x, best_energy
# 运行
best_x, best_energy = simulated_annealing(
initial_temp=100,
end_temp=0.01,
alpha=0.95,
max_iter=100
)
print(f"最优解: x = {best_x:.4f}, f(x) = {best_energy:.4f}")小技巧：实际项目中，初始温度 T₀ 的设置很重要。我一般会先随机跑几十次，统计目标函数值的波动范围，然后把 T₀ 设成这个范围的 10-20 倍。这样能保证早期有足够的探索能力。
3.6 模拟退火的优缺点
| 优点 | 缺点 |
|---|---|
| 理论上能收敛到全局最优 | 收敛速度慢，尤其在大规模问题上 |
| 对目标函数没有连续性要求 | 参数（T₀, α, 内循环次数）调优困难 |
| 实现简单，容易并行化 | 结果不稳定，每次运行可能不同 |
| 适合离散和连续优化问题 | 对初始解敏感 |