模拟退火 SA · 深度手册

分类：优化类 ｜难度：★★☆ 进阶｜编号：sa

一、这是什么（一句话用途）

组合 / 非线性全局优化（调度 / TSP / 布局）

二、核心思想

模拟退火（Simulated Annealing）借用了冶金中"退火"的物理直觉：把金属加热后再缓慢冷却，原子才能找到能量最低的晶格排列。算法把"解的质量"类比为"系统能量"，在搜索初期允许以一定概率接受更差的解（像高温下原子乱跳），从而跳出局部最优；随着"温度"逐渐降低，接受劣解的概率变小，最终收敛到（近似）全局最优。它对目标函数是否可微、是否连续都无要求，特别适合组合优化（调度、TSP、布局）。

三、数学原理与推导

在当前解 $x$ 的邻域产生新解 $x'$ ，能量差 $\Delta E=E(x')-E(x)$ 。

Metropolis 接受准则：

$P(\text{接受 }x')=\begin{cases}1, & \Delta E<0\\ e^{-\Delta E/T}, & \Delta E\ge0\end{cases}$

温度按降温 schedule 更新，如 $T_{k+1}=\alpha T_k$ （ $\alpha\in(0,1)$ 接近 1）或 $T_k=T_0/\ln(1+k)$ 。

物理背景：在温度 $T$ 下系统处于能量 $E$ 状态的概率服从 Boltzmann 分布 $\propto e^{-E/T}$ 。当 $T\to0$ ，分布集中于全局最小能量态；有限温度下以 $e^{-\Delta E/T}$ 概率接受劣解，使算法能翻越能量壁垒脱离局部极小。

四、建模 / 求解步骤

初始化解与温度 T
邻域产生新解
按 Metropolis 判接受
降温 T=αT
迭代至收敛

五、关键公式速查

P(接受劣解)=exp(−ΔE/T)

六、典型示例

工厂车间排产、相机位布局等组合优化。

完整算例（数字演示，照着算一遍）

场景：min f(x)=x², x∈[−5,5]，T0=10, α=0.95。

过程：从 x=4 出发，接受劣解概率 e^{−Δ/T} 随降温减小；1000 步后 x*≈0.02, f*≈0.0004。

结论：模拟退火以概率跳出局部，收敛到全局 0。

七、Python 实现示例

import os, numpy as np
import pandas as pd
HERE = os.path.dirname(os.path.abspath(__file__))
df = pd.read_csv(os.path.join(HERE,"..","datasets","sa.csv"))
cities = df[["x","y"]].to_numpy(dtype=float)
D = np.linalg.norm(cities[:,None]-cities[None,:], axis=2)
rng=np.random.default_rng(1)
order=list(range(len(cities))); rng.shuffle(order)
def length(p): return sum(D[p[i],p[(i+1)%len(p)]] for i in range(len(p)))
T=100; best=order[:]; bestL=length(order)
while T>1e-2:
    i,j=rng.integers(0,len(order),2)
    o=order[:]; o[i],o[j]=o[j],o[i]
    if length(o)<length(order) or rng.random()<np.exp((length(order)-length(o))/T):
        order=o
    if length(order)<bestL: best, bestL=order[:], length(order)
    T*=0.95
print("最短巡回长度=%.2f"%bestL)

配套文件：py_sa.py（需 numpy / pandas；与下方数据集配套练习）

八、MATLAB 实现示例

%% 模拟退火 TSP 示例（MATLAB/Octave）
df = readtable('..\datasets\sa.csv');
cities = table2array(df(:,2:3));
D = pdist2(cities,cities);
rng(1); order=randperm(height(cities));
lenF = @(p) sum(diag(D(p,p([2:end,1]))));
T=100; best=order; bestL=lenF(order);
while T>1e-2
  i=randi(length(order)); j=randi(length(order)); o=order; o([i,j])=o([j,i]);
  if lenF(o)<lenF(order) || rand<exp((lenF(order)-lenF(o))/T), order=o; end
  if lenF(order)<bestL, best=order; bestL=lenF(order); end
  T=T*0.95;
end
fprintf('最短巡回长度=%.2f\n', bestL);

配套文件：m_sa.m（基础 MATLAB / Octave 即可运行）

九、练手数据集（可下载）

10 个城市平面坐标。用于模拟退火求解 TSP 最短巡回。

字段：city, x, y
行数：10 行
下载：sa.csv

十、常见误区与避坑清单

初温 / 降温系数要调
迭代次数不足易早熟
邻域设计影响大

十一、结果怎么解读

历史最优解即结果。

十二、常与谁搭配

与 GA 同类启发式。

十三、论文写作技巧（怎么把它写进论文）

把 模拟退火 SA 写进论文，核心不是堆公式，而是讲清「为什么用它、结果怎么呈现、如何对比」三件事。

1. 动机怎么写（为什么用它而不是别的）

先把问题「数学化」：决策变量、目标函数、约束条件——这一步写清楚比算法本身更重要。再说明为何用模拟退火 SA 求解：连续可导用梯度 / 解析法，组合 / 非凸 / 黑箱用启发式（GA / PSO / SA）。

2. 结果怎么写（图表与指标）

放「收敛曲线（迭代 vs 目标值）」+「最优解参数表」+「约束是否满足」三件套。若是多目标，放 Pareto 前沿散点图。

3. 可直接套用的写作话术

中文模板：针对<问题>，本文采用 模拟退火 SA 进行组合 / 非线性全局优化（调度 / TSP / 布局）。该方法能够自动刻画<优势>，在处理<场景>时相较<对比方法>更具<特点>。
英文模板：To address , we adopt 模拟退火 SA to 组合 / 非线性全局优化（调度 / TSP / 布局）. Benefiting from its ability to , it outperforms on .

4. 同类易踩的写作坑

务必说明约束是否全部满足、是否陷入局部最优（可多次随机初始化对比）；别把无约束结果当约束最优报。

5. 典型论文段落范例（可直接参考 / 改写）

下面是一段可直接套用的论文表述，已按本算法定制，填空处（…）替换成你的真实数值即可。

将配送中心选址建模为带容量约束的总成本最小化问题，本文采用模拟退火 SA 求解，得到 5 个选址及其服务分配方案，目标值较贪婪启发式降低 12.4%，且全部约束满足。

We formulate the distribution center location as a total-cost minimization problem with capacity constraints and solve it via 模拟退火 SA, yielding 5 sites and their service assignments. The objective is 12.4% lower than a greedy heuristic while satisfying all constraints.

十四、相关手册（延伸阅读）

遗传算法 GA · 优化类

十五、本手册导航

上一篇：整数规划 · 优化类
下一篇：遗传算法 GA · 优化类
返回：算法深度手册库｜资料站首页

本手册由「算法深度手册生成器」自动产出，配套提供 Python / MATLAB 双版本示例与可下载练手数据集。