🌡️ 11-模拟退火与禁忌搜索¶
目标:掌握两条「单点 + 记忆」的元启发式主线——模拟退火 SA(接受劣解逃出局部最优)与 禁忌搜索 TS(记忆最近动作避免回头)。TSP 上手,面试考原理与调参。也顺带对比无记忆的随机重启。
§0 局部搜索的困境与两条出路¶
局部搜索(局部最优陷阱):从解出发,只朝「改进方向」移动 → 停在最近的局部最优,与全局最优可能相去甚远。
出路 1(SA):允许暂时变差——以概率接受劣解,温度高时概率大(全局探索),温度低时概率小(局部收敛)。 出路 2(TS):记住最近动作——最近做过的移动进禁忌表,短期内禁止回头,强制探索新区域。
邻域:TSP 用 2-opt(反转一段)或 swap(交换两城市)。邻域是启发式的设计自由度,见 §2。
核心概念¶
(a) 🗂️ 模拟退火与禁忌搜索知识地图¶
这篇讲"从局部最优逃跑"的两条路线:模拟退火用"高温乱逛、低温收敛"的物理过程接受坏解,禁忌搜索用"禁忌表 + 藐视准则"的记忆机制防止原地打转,两者都以 TSP 为例手写实现。
flowchart TB
Node1["🧠 局部搜索困境"]
Node1 --> Node2["🧠 邻域搜索"]
Node2 --> Node3["🧠 Metropolis 准则"]
Node3 --> Node4["🧠 温度与冷却调度"]
Node4 --> Node5["🧠 模拟退火流程"]
Node5 --> Node6["🧠 禁忌表"]
Node6 --> Node7["🧠 藐视准则"]
Node7 --> Node8["🧠 选型对比"]
Node8 --> Node9["🧠 TS 进阶变体"]
- 节点1(局部搜索困境):贪心爬山会停在第一个局部最优,随机重启没有记忆、反复掉进同一个坑;N=20 城市 TSP 让陷阱足够明显,引出两条"逃跑"路线。
- 节点2(邻域搜索):两个算法都基于"邻域":当前解做一个小改动(2-opt 交换两个城市)得到邻居,然后决定要不要跳到邻居。
- 节点3(Metropolis 准则):模拟退火的灵魂:更差的解以概率 exp(−Δ/T) 接受,Δ 越小(差得不多)或 T 越大(温度高)越敢接受;好解一定接受。
- 节点4(温度与冷却调度):温度按 T ← T·α 几何降温:高温段几乎什么都接受(全局乱逛逃出局部最优),低温段只接受改进(精细收敛);冷却太快容易卡,太慢太耗时。
- 节点5(模拟退火流程):初始化温度 → 每轮随机找邻居 → Metropolis 判定 → 降温 → 重复;TSP 上对比随机重启基线能直观看到 SA 找到更短环。
- 节点6(禁忌表):禁忌搜索记下最近做过的动作(如交换的城市对),短时间内禁止重做,防止在两个局部最优之间来回震荡;表长 tabu_len 是核心超参。
- 节点7(藐视准则):即使动作在禁忌表中,如果它能刷新全局最优就破例允许——"好到值得破戒",这是禁忌搜索不牺牲最优性的关键。
- 节点8(选型对比):SA 适合"允许随机、参数少"的场景,TS 适合"邻域清晰、要确定性记忆"的场景;表格给出何时用哪个,面试直接背。
- 节点9(TS 进阶变体):候选解集限缩、长期记忆/频率惩罚、与 SA 混合等变体是面试扩展;一句话:TS 是"带记忆的爬山"。
§0.1 配图:退火过程的直观动画¶
模拟退火的名字来自冶金「退火」:加热后缓慢冷却,原子从混乱排列到低能晶体。

图注:爬山法与模拟退火的轨迹动画对比——爬山被困在局部峰,SA 通过接受劣解翻过山谷 (来源:Wikimedia Commons,公有领域)。

图注:模拟退火求解 TSP 的可视化——路径在高温阶段剧烈重组,低温阶段逐渐稳定成短环 (来源:Wikimedia Commons,公有领域)。
动画里的关键动作:注意 SA 有时会「往山上走」(接受更差的解)—— 这正是它能翻出局部最优的机制。温度高时这种「回头路」频繁;温度低时几乎不再发生。
§0.2 手算 Metropolis:温度如何决定接受率¶
设当前解代价 $L=100$,邻居代价 $L'=105$,即 $\Delta=+5$(更差):
| 温度 T | 接受概率 $\exp(-\Delta/T)=\exp(-5/T)$ | 行为 |
|---|---|---|
| 500(高温) | $e^{-0.01}\approx 0.99$ | 几乎必接受 → 全局乱逛 |
| 50(中温) | $e^{-0.1}\approx 0.90$ | 大概率接受 |
| 5(低温) | $e^{-1}\approx 0.37$ | 约 1/3 接受 |
| 0.5(极低温) | $e^{-10}\approx 4.5\times 10^{-5}$ | 几乎只接受改进 |
同理 $\Delta=+50$ 时:$T=50$ → $e^{-1}\approx 0.37$;$T=5$ → $e^{-10}\approx 0$。同温下越坏的解越难被接受——这个「温度 × 代价差」的双刻度正是 Metropolis 的精髓。
📌 面试快速推法:温度 $T$ 量级应与「典型代价差」同量级;$T_0$ 取问题规模的数倍, 让初始接受率约 80~95%。
import numpy as np
import matplotlib.pyplot as plt
plt.rcParams['font.sans-serif'] = ['Microsoft YaHei', 'SimHei', 'DejaVu Sans']
plt.rcParams['axes.unicode_minus'] = False
# ---------- TSP 实例(N=20 城市,让局部最优陷阱足够明显) ----------
N = 20
rng = np.random.default_rng(5)
cities = rng.random((N, 2)) * 10
dist = np.sqrt(((cities[:, None, :] - cities[None, :, :]) ** 2).sum(-1)) # 距离矩阵 d[i,j]
def tour_len(order):
# 封闭环长:相邻城市距离之和 + 最后回到起点
return sum(dist[order[i], order[(i + 1) % N]] for i in range(N))
def random_tour(r):
return r.permutation(N).tolist()
# ================= 基线:随机重启局部搜索(无记忆) =================
# 思想:反复随机初始化 + 贪心 2-opt 改进,各跑一次,取最好。
# 它没有「记忆」:每次重启都从零开始,容易反复掉进同一个局部最优。
def random_restart(restarts=25, steps=100, seed=0):
r = np.random.default_rng(seed)
best = np.inf
for _ in range(restarts):
cur = random_tour(r); L = tour_len(cur)
for _ in range(steps):
i, j = sorted(r.integers(0, N, size=2).tolist()) # 随机取一段 [i,j]
nxt = cur[:i] + cur[i:j + 1][::-1] + cur[j + 1:] # 2-opt:反转该段
nL = tour_len(nxt)
if nL < L: # 只接受改进
cur = nxt; L = nL
best = min(best, L)
return best
rr_len = random_restart()
print('随机重启局部搜索最优环长: %.2f' % rr_len)
plt.show()
# ================= 手写模拟退火(SA) =================
# 核心:Metropolis 准则——当前解 x,邻居 y,代价差 Δ = f(y)-f(x):
# 若 Δ < 0(更好)→ 一定接受
# 若 Δ ≥ 0(更差)→ 以概率 exp(-Δ/T) 接受(T 越大越敢接受坏解)
# 温度 T 从 T0 按 T ← T * alpha 几何降温:
# 高温段:几乎什么都接受 → 全局乱逛(逃出局部最优)
# 低温段:只接受改进 → 精细收敛(模拟淬火成晶体)
def sa_tsp(T0=50, alpha=0.998, iters=4000, seed=1):
r = np.random.default_rng(seed)
cur = random_tour(r); L = tour_len(cur)
best = L; best_tour = cur[:]
T = T0
hist = []
for _ in range(iters):
i, j = sorted(r.integers(0, N, size=2).tolist())
nxt = cur[:i] + cur[i:j + 1][::-1] + cur[j + 1:] # 2-opt 邻居
nL = tour_len(nxt)
delta = nL - L
# Metropolis 判定:改进必收;恶化按概率收(exp(-Δ/T) ∈ (0,1),Δ 越大越难收)
if delta < 0 or r.random() < np.exp(-delta / T):
cur = nxt; L = nL
if L < best: # 全程记录最优(降温后期可能回升)
best = L; best_tour = cur[:]
T *= alpha # 几何降温
hist.append(best)
return best, best_tour, np.array(hist)
sa_len, sa_tour, sa_hist = sa_tsp()
print('模拟退火最优环长: %.2f' % sa_len)
# ================= 手写禁忌搜索(TS) =================
# 核心三件套:
# 1) 禁忌表:记录最近做过/撤销的动作(swap 城市对),禁止立刻重做 → 防止在局部最优来回震荡
# 2) 藐视准则(aspiration):若禁忌动作能刷新全局最优,破例允许(好到值得破戒)
# 3) 邻域选择:每步考察整个 swap 邻域,选「非禁忌中最好」的动作执行
def ts_tsp(tabu_len=18, iters=4000, seed=2):
r = np.random.default_rng(seed)
cur = random_tour(r); L = tour_len(cur)
best = L; best_tour = cur[:]
# 禁忌矩阵:tabu[a,b] = 最早允许再次交换 (a,b) 的代数(0 = 不禁忌)
tabu = np.zeros((N, N), int)
hist = []
for it in range(iters):
best_move = None; best_nL = np.inf
for a in range(N): # 枚举 swap 邻域(全部城市对)
for c in range(a + 1, N):
if a == c: continue
nxt = cur[:]; nxt[a], nxt[c] = nxt[c], nxt[a] # 交换两城市位置
nL = tour_len(nxt)
# 禁忌判断:该城市对在禁忌期内,且不能刷新全局最优(藐视准则)→ 跳过
if tabu[a, c] > it and nL >= best - 1e-9:
continue
if nL < best_nL: # 选当前邻域里最好的合法动作
best_nL = nL; best_move = (a, c, nxt)
if best_move is None: # 邻域全被禁忌 → 随机一步(防死锁)
a, c = sorted(r.integers(0, N, size=2).tolist())
nxt = cur[:]; nxt[a], nxt[c] = nxt[c], nxt[a]
cur = nxt; L = tour_len(nxt)
else:
a, c, cur = best_move; L = best_nL
tabu[a, c] = it + tabu_len # 动作进禁忌表(到期自动解禁)
tabu[c, a] = it + tabu_len
if L < best: # 更新全局最优
best = L; best_tour = cur[:]
hist.append(best)
return best, best_tour, np.array(hist)
ts_len, ts_tour, ts_hist = ts_tsp()
print('禁忌搜索最优环长: %.2f' % ts_len)
print('随机重启 %.2f | SA %.2f | TS %.2f' % (rr_len, sa_len, ts_len))
assert sa_len < rr_len and ts_len < rr_len, 'SA/TS 应明显优于无记忆的随机重启'
# ========== 图:收敛曲线对比 ==========
fig, ax = plt.subplots(figsize=(7.4, 4.6))
ax.plot(sa_hist, lw=1.6, color='#C44E52', label='SA(Metropolis 接受劣解)')
ax.plot(ts_hist, lw=1.6, color='#4C72B0', label='TS(禁忌表+藐视准则)')
ax.axhline(rr_len, color='#8E8E93', ls='--', lw=1.2, label='随机重启(无记忆)%.2f' % rr_len)
ax.set_xlabel('迭代步'); ax.set_ylabel('当前最优环长')
ax.set_title('TSP:SA / TS 明显优于无记忆的随机重启', fontsize=12)
ax.legend(fontsize=9); ax.grid(alpha=0.3); plt.tight_layout(); plt.show()
§0.3 冷却调度(cooling schedule)的三种方案¶
温度怎么降,直接影响解的质量与速度,三种经典方案:
| 方案 | 公式 | 特点 |
|---|---|---|
| 几何降温 | $T_{k+1}=\alpha T_k$($\alpha=0.9\sim0.999$) | 最常用,指数衰减快 |
| 线性降温 | $T_k = T_0(1 - k/K)$ | 慢、可控,总步数固定 |
| 对数降温 | $T_k = T_0 / \ln(k+2)$ | 理论收敛保证(充分慢则概率 1 到全局最优),但慢到不实用 |
理论最优调度:Geman & Geman 证明当 $T_k \ge c/\ln(k+1)$ 时 SA 以概率 1 收敛到全局最优—— 但所需步数天文数字,实际工程都用几何降温 + 多次重启。
工程调参流程:
- 先跑几次看「当前最优」曲线:如果曲线后期还在快速下降 → 温度降太快/迭代太少;
- 如果后期曲线平但解不够好 → 初始温度太低(一开始就没探索开);
- 补救不重跑:RTR(restart-with-temperature)——到低温后升温再降,多次退火取最优。
📌 面试一句话:SA = 先乱逛(高温)后精修(低温);理论保证用对数调度, 实践用几何调度 + 重启。
§1 调参地图与原理深挖¶
SA 三参数:初始温度 $T_0$(足够大到能接受大部分劣解)、降温率 $\alpha$(0.9~0.999,越小越快越粗)、 迭代数(与 $T_0,\alpha$ 匹配,总步数 ≈ $\ln(T_f/T_0)/\ln\alpha$)。 Metropolis 的直觉:$\exp(-\Delta/T)$——$\Delta$ 大(很坏)几乎不接受,$T$ 大(高温)什么都接受。 数学上 SA 在理想降温计划下以概率 1 收敛到全局最优(Geman & Geman 1984,理论保证但不实用)。
TS 三件套:禁忌表长度 $L$(太短防不住回环,太长限制搜索,本讲 18,约 N)、 禁忌对象(TSP 常用城市对,也可用完整解/动作)、藐视准则(何时破例)。 TS 变体:随机化 TS、频率记忆(长期禁忌低频动作)、路径重连(path relinking)。
邻域设计是灵魂:2-opt 一次改 2 条边,swap 一次换 2 个位置——邻域大小、可改进幅度决定收敛速度与质量。
§1.1 禁忌搜索手撕流程(一步步照做)¶
TS 的代码比 SA 多一些簿记,但流程固定,背下来就能写:
初始化解 s、禁忌表 T(空)、最优解 s*
repeat:
# 1) 生成邻域 N(s)(所有合法动作产生的邻居)
# 2) 遍历 N(s),跳过「在禁忌表中且不满足藐视准则」的邻居
# 3) 选其中代价最小的非禁忌邻居 s'(即使它比 s 差)
# 4) 更新禁忌表:把 s→s' 这个动作记入表,过 tabu_len 代解禁
# 5) 若 f(s') < f(s*): s* = s'(藐视准则:好到可以破例)
# 6) s ← s';记录历史
until 达到迭代上限
与 SA 的本质区别:SA 用概率决定是否接受坏解;TS 用记忆强制绕开最近的坏动作—— TS 每一步都在邻域里选最好的可行(可能仍变差),但绝不允许立刻反悔。
📌 面试经典问题「TS 会不会卡死」:禁忌表保证了「有限步内不会回到同一解」 (动作被禁止),所以不会无限循环;邻域被全禁时的随机步是工程兜底。
§1.2 应用场景与选型对比(何时用哪个)¶
| 方法 | 擅长 | 缺点 | 典型场景 |
|---|---|---|---|
| 随机重启 | 简单快速 | 无记忆,重复探索 | 作为基线 |
| SA | 连续/离散通用、易实现 | 调参敏感、后期慢 | 布局、线路板设计、调度 |
| TS | 组合优化强、确定性好 | 禁忌表调参、邻域要快 | 车辆路径、排程、图着色 |
工程选型口诀:
- 只有目标函数值(黑箱)→ SA / GA / PSO 任选,看解空间类型;
- 组合/排序问题(TSP 类)→ TS 或 ACO(12 篇)通常比 SA 稳;
- 连续优化 → PSO / 进化策略;
- 追求可复现、少调参 → TS(无随机接受,结果确定性更强)。
💡 面试加分项:说完原理后补一句「我会先用随机重启拿基线,再对比 SA/TS, 阈值看 1% 以内差距」——展示工程判断力而不是只会背算法。
§1.3 TS 进阶变体(面试扩展)¶
知道变体名 + 一句话原理,就能应对「TS 还能怎么改」的追问:
- 随机化 TS:禁忌太长导致邻域全禁时随机大跳——简单有效,防止死锁;
- 频率记忆(frequency-based):除「近期禁做」之外,再记录「长期哪些动作做得太频繁」, 适度惩罚高频动作 → 强制搜索新区域(多样化);
- 候选列表:邻域太大时不全扫描,只评价格“最有希望”的一个子集(如最短路程对) → 大规模 TSP 的标配;
- 路径重连(path relinking):把两个精英解之间的路径走一遍,沿途收集更好解;
- GRASP:贪心随机化构造初始解 + 局部搜索,再套 TS 精化——经典混合框架。
TS 与 SA 的一个深层区别:SA 是马尔可夫链(只依赖当前态 + 随机转移), TS 是确定性 + 记忆的(邻域扫描是确定性的,禁忌表提供记忆)—— 这是面试「为什么 TS 可复现性好」的答案基础。
📌 一句话补充:TS 的「记忆」让它比 SA 更少走回头路;工程上 TS 对初值较敏感, 常配 GRASP 构造好起点。
§2 面试追问与自测¶
- Metropolis 准则的公式与直觉?为什么高温敢接受坏解?
- SA 参数怎么调?降温太快/太慢分别有什么后果?
- 禁忌表记什么?禁忌长度太短/太长?藐视准则何时用?
- SA vs TS vs 随机重启的本质区别?(概率接受 vs 强制记忆 vs 无记忆)
- 2-opt 是什么?为什么它很少破坏环结构?
自测清单
- 手写 Metropolis 判定(一行 if 条件)
- 手写禁忌表更新 + 邻域扫描 + 藐视准则
- 说出 SA/TS 各自防止「困在局部最优」的机制
- 复现本讲:SA/TS 均优于随机重启(断言已内置)
💡 下节预告:群体智能——12 粒子群与蚁群算法。