模拟退火

What · 是什么

模拟退火（Simulated Annealing, SA）是一种随机化元启发式优化算法，灵感来自金属退火：将金属缓慢加热再以适宜速度冷却以消除内应力。算法把目标函数视为'能量函数'E，从一个随机状态出发，每一步在邻域随机生成新状态；新状态更优则无条件接受；更差则以概率 e^(-ΔE/T) 接受（Metropolis 准则），其中 ΔE 是能量差（≥0），T 是当前温度。温度初始为较大值 T0，每步乘以降温系数 d（略小于 1），直到低于终止温度 Tk。因能以一定概率接受劣解，SA 可以跳出局部最优，在'方案数量极大甚至无穷且非单峰'的问题中非常有效。最终答案通常取整个过程中遇到的最优状态，而非结束时状态。

Why · 为什么

How · 实现

伪代码

# 通用 SA 框架 (求最小化 E)
T = T0; u = 0.99; Tk = 1e-4
s = 随机初始状态; E = E(s)
s_best, E_best = s, E
while T > Tk:
    s_next = 在 s 邻域随机生成
    E_next = E(s_next)
    if E_next < E 或 random() < exp(-(E_next-E)/T):
        s, E = s_next, E_next
        if E < E_best: s_best, E_best = s, E
    T *= u
return s_best, E_best

Python 实现

import math
import random


class SA:
    """通用模拟退火框架: 最小化 energy 函数.
    用户需实现: initial_state(), neighbor(s), energy(s)
    """

    def __init__(self, initial_state, energy, neighbor,
                 T0=1000.0, u=0.999, Tk=1e-6):
        self.energy = energy
        self.neighbor = neighbor
        self.T0, self.u, self.Tk = T0, u, Tk

    def run(self, state):
        E = self.energy(state)
        best_s, best_E = state, E
        T = self.T0
        while T > self.Tk:
            nxt = self.neighbor(state)
            nE = self.energy(nxt)
            dE = nE - E
            if dE < 0 or random.random() < math.exp(-dE / T):
                state, E = nxt, nE
                if E < best_E:
                    best_s, best_E = state, E
            T *= self.u
        return best_s, best_E


def tsp_sa(cities, iters=None):
    """TSP 近似解: 状态=访问顺序, 邻域=交换两个城市位置.
    返回 (best_tour, best_dist)
    """
    n = len(cities)

    def dist(i, j):
        return math.hypot(cities[i][0] - cities[j][0], cities[i][1] - cities[j][1])

    tour = list(range(n))
    random.shuffle(tour)

    def energy(t):
        return sum(dist(t[i], t[(i + 1) % n]) for i in range(n))

    def neighbor(t):
        nt = t[:]
        a, b = random.sample(range(n), 2)
        nt[a], nt[b] = nt[b], nt[a]
        return nt

    sa = SA(tour, energy, neighbor, T0=100, u=0.999, Tk=1e-3)
    best_t, best_d = sa.run(tour)
    return best_t, best_d


if __name__ == "__main__":
    random.seed(1)

    # 1) 单峰二次函数: 应逼近全局最小点 x*=2
    def e1(x):
        return (x - 2.0) ** 2

    sa = SA(50.0, e1, lambda x: x + random.uniform(-3, 3), T0=30, u=0.99, Tk=1e-3)
    s, E = sa.run(50.0)
    assert abs(s - 2.0) < 0.05, s

    # 2) 有局部最优的震荡函数: f(x)=sin(x) + 0.1x, 区间 [0,20]
    # 期望 SA 能找到接近全局最优的点(约 1.57 附近 sin 最大)
    def e2(x):
        return -(math.sin(x) + 0.1 * x)

    sa2 = SA(3.0, e2, lambda x: min(20, max(0, x + random.uniform(-2, 2))),
             T0=10, u=0.995, Tk=1e-3)
    s2, _ = sa2.run(3.0)
    # 全局最大在 x≈1.57 (sin峰) 或接近 20 处; 允许 SA 找到任一峰(近似)
    # 这里用多次运行确保找到 sin 主峰
    best = None
    for _ in range(30):
        r, _ = SA(5.0, e2, lambda x: min(20, max(0, x + random.uniform(-2, 2))),
                  T0=10, u=0.995, Tk=1e-3).run(5.0)
        val = -(e2(r))
        if best is None or val > best:
            best = val
    assert best > 0.95, best  # sin 主峰值约 1.157

    # 3) TSP 小实例: 正方形四顶点, 最优=周长 4
    cities = [(0, 0), (1, 0), (1, 1), (0, 1)]
    best_t, best_d = tsp_sa(cities)
    assert best_d < 4.01, best_d  # 应收敛到正方形周长 4

    print("simulated-annealing tests passed")

易错点

• Metropolis 接受概率用错符号（ΔE 取负）会反向接受
• ΔE 未取非负值 / T 为 0 时 exp 除零崩溃
• 答案应取全程最优 best_s 而非最终状态
• u 太大(≈1)收敛极慢易 TLE；太小退火不充分仍困局部最优
• 不卡时、不跑多轮，单次运行结果不可靠

例题

信源

• OI Wiki✓ https://oi-wiki.org/misc/simulated-annealing/
• CP-Algorithms✓ https://cp-algorithms.com/num_methods/simulated_annealing.html
• Wikipedia✓ https://en.wikipedia.org/wiki/Simulated_annealing