从算法到人工智能 · 第 20 课：模拟退火——给贪心算法装一个"允许退一步"的温度计

上一课我们搭了元启发算法的总纲，留下一个问题：贪心算法永远只接受"更好的解"，于是会卡在局部最优。这一课的主角——模拟退火（Simulated Annealing, SA），就是解决这个问题的第一种经典方案。

它的名字来自冶金退火：把金属加热到高温，再慢慢冷却，原子会逐渐排列成能量最低的稳定结构。如果冷却太快，会卡在亚稳态（对应算法的局部最优）；慢慢冷却，才有机会到达全局最优。

一、先看清敌人：局部最优陷阱

假设我们要找一个函数的最小值。下面是这个函数的样子（一维 Rastrigin 函数，故意有很多"坑"）：

import math

def f(x):
    """一维 Rastrigin 函数：全局最小在 x=0，f=0；四周一堆局部极小"""
    return x * x + 10 * (1 - math.cos(2 * math.pi * x))

它的形状是：一个深的全局最低点（x=0），四周布满浅坑（局部最低点）。

如果用一个"贪心爬山"——每次只往更低的地方走、一旦周围都比自己高就停——它会掉进最近的坑里，再也出不来：

def greedy_descent(f, x0, step=0.1, iters=200):
    x = x0
    for _ in range(iters):
        candidates = [x - step, x + step]      # 只看左右两个邻居
        # 只接受更低的邻居
        better = [c for c in candidates if f(c) < f(x)]
        if not better:
            break                              # 周围都比自己高 → 卡住
        x = min(better, key=f)
    return x, f(x)

print(greedy_descent(f, -4.0))   # 大概率卡在某个局部坑里，f 远大于 0

从 x=-4 出发，贪心很快滑进附近某个浅坑，然后"四周都比自己高"，就停在了局部最优——它到不了 x=0 那个全局最低点。

这就是我们要克服的：如何让算法在掉进坑里后，还有机会"爬出来"？

二、模拟退火的核心思想：允许接受更差的解

模拟退火的答案很简单，也很反直觉：

偶尔允许接受一个"更差"的解，接受的概率由"温度"控制；温度越高越敢冒险，温度越低越保守。

具体到每一步：

1. 在当前解附近，随机生成一个新候选解。
2. 如果新解更好（目标值更低）→ 一定接受。
3. 如果新解更差 → 以概率 exp(-Δ/T) 接受它。其中 Δ = 新解的目标值 − 当前目标值（Δ>0 表示变差），T 是当前温度。

这条接受准则叫 Metropolis 准则。看它怎么工作：

• Δ 越大（新解差得越多）→ exp(-Δ/T) 越小 → 越不可能接受坏解。
• T 越大（温度越高）→ exp(-Δ/T) 越大 → 越敢接受坏解，到处乱跳。
• T 慢慢降低 → 越来越保守，最终收敛到一个（希望是全局的）最优解。

三、完整算法骨架

import random, math

def simulated_annealing(f, x0, temp=10.0, cooling=0.995, iters=2000):
    """
    f       : 目标函数，越小越好
    x0      : 初始解
    temp    : 初始温度
    cooling : 降温系数，每次迭代温度 *= cooling
    iters   : 迭代次数
    返回 (best_x, best_val)：全程遇到的最优解
    """
    x = x0
    best_x, best_val = x, f(x)      # 单独记住全局最优
    T = temp

    for _ in range(iters):
        x_new = x + random.uniform(-1, 1)          # 1) 扰动：在附近随机挪一步
        delta = f(x_new) - f(x)                    # 2) 计算变化量

        if delta < 0 or random.random() < math.exp(-delta / T):
            x = x_new                             # 3) 更好则收，更差则按概率收

        if f(x) < best_val:                        # 4) 更新全局最优
            best_x, best_val = x, f(x)

        T *= cooling                               # 5) 降温

    return best_x, best_val

random.seed(42)
best_x, best_val = simulated_annealing(f, -4.0)
print(f"x={best_x:.4f}  f={best_val:.4f}")   # 期望 f 接近 0

对比贪心：贪心卡在局部坑里出不来；模拟退火温度高的时候乱跳，能跳出浅坑，随着温度降低逐渐锁定到全局最低点。

四、温度这条曲线，是模拟退火的灵魂

模拟退火的效果，几乎完全由降温曲线决定。三个参数各有讲究：

降温系数尤其关键：cooling=0.995 意味着每一步温度乘 0.995，2000 步后温度约降到初始的 0.995^2000 ≈ 0.000045。这个"慢冷却"正是"退火"二字的由来。

温度是按几何级数下降的：每迭代一次就乘一次 cooling。cooling 越接近 1，降温越慢：

T_fast = 10.0 * (0.90 ** 100)     # 100 步后
T_slow = 10.0 * (0.999 ** 100)    # 100 步后
print(f"cooling=0.90  100 步后 T={T_fast:.6f}")
print(f"cooling=0.999 100 步后 T={T_slow:.6f}")

降温太快（cooling 小）：温度几步就归零，Metropolis 准则里 exp(-Δ/T) 在 T→0 时对任何 Δ>0 都趋近 0，等于不再接受坏解、退化成贪心，有卡在局部最优的风险。
降温太慢（cooling 大）：长时间停在高温、还在到处乱跳，收敛慢、浪费迭代。
工程上常取 0.9~0.999，再配合足够的迭代次数来平衡。本例里两个 cooling 恰好都能找到全局最低点，是因为一维 Rastrigin 从 -4 出发、步长 ±1 时搜索已足够充分；换成更难的组合优化（下一节 TSP）或减少迭代，降温过快卡住的风险就会显现。

五、经典应用：旅行商问题（TSP）

模拟退火最经典的主场，是组合优化——解是"一组选择"，而不是连续的数字。以旅行商问题为例：拜访 n 个城市，每条路线是一个解，目标是总路程最短。

import random, math

def total_distance(route, dist):
    """计算路线总长度（回到起点）"""
    d = 0
    for i in range(len(route)):
        d += dist[route[i]][route[(i + 1) % len(route)]]
    return d

def tsp_simulated_annealing(dist, temp=100.0, cooling=0.995, iters=5000):
    n = len(dist)
    route = list(range(n))
    random.shuffle(route)                          # 随机起点
    best_route, best_d = route[:], total_distance(route, dist)
    T = temp
    for _ in range(iters):
        # 扰动：随机交换两个城市的位置
        i, j = random.sample(range(n), 2)
        new_route = route[:]
        new_route[i], new_route[j] = new_route[j], new_route[i]
        delta = total_distance(new_route, dist) - total_distance(route, dist)
        if delta < 0 or random.random() < math.exp(-delta / T):
            route = new_route
        d = total_distance(route, dist)
        if d < best_d:
            best_route, best_d = route[:], d
        T *= cooling
    return best_route, best_d

# 5 个城市的距离矩阵（对称）
D = [
    [0, 3, 4, 2, 7],
    [3, 0, 4, 6, 3],
    [4, 4, 0, 5, 8],
    [2, 6, 5, 0, 6],
    [7, 3, 8, 6, 0],
]
random.seed(7)
best, d = tsp_simulated_annealing(D)
print(f"最优路线 {best}  总距离 {d}")

对比上一课的连续函数版，你会发现骨架一模一样，只有两处不同：

• 扰动：从"挪一个实数"换成"交换两个城市"。
• 评估：从 f(x) 换成 total_distance(route)。

这正是"元"启发算法的意义：换掉"解的表达"和"扰动方式"，同一个搜索框架就能迁移到完全不同的问题上。

六、模拟退火的优缺点

总结它的定位：比贪心聪明（能跳出局部最优），比穷举快（不用遍历所有解），是"时间换质量"的高性价比选择。

七、小结

1. 贪心卡在局部最优，是因为它"只进不退"；模拟退火靠 Metropolis 准则允许偶尔接受更差解，从而跳出局部坑。
2. 温度 T 是核心：T 高时大胆乱跳，T 慢慢降低后收敛；降温太快等于"淬火"，会卡在亚稳态。
3. 模拟退火是"单解型"元启发——始终只维护一个解，与下一课"维护一群解"的遗传算法形成对照。

八、动手实验

1. 感受降温：把第四节的 cooling 分别改成 0.90、0.995、0.999，各跑 5 次，看最终 f 值差多少，体会"慢冷却"为什么重要。
2. 换个函数：把 f(x) 换成 f(x) = x*x + 10*math.sin(x)（定义域 [-10, 10]），看看模拟退火能不能找到比贪心更低的点。
3. 改扰动尺度：把扰动从 random.uniform(-1, 1) 改成 random.uniform(-0.1, 0.1) 再跑，观察收敛速度和解的质量有什么变化——这对应"每一步走多大"的权衡。