模拟退火
一、直观理解：高温时敢乱走，降温后细打磨
模拟退火（Simulated Annealing, SA）模仿金属退火：温度高时原子可大幅跃迁，温度降低后逐渐稳定在低能态。对应优化：
- 当前解 ，随机产生邻域解 ；
- 若 （最小化），则接受；
- 若变差，仍以概率 接受，从而有机会跳出局部最优；
- 按冷却计划降低温度 ，接受变差的概率越来越小，搜索趋于收敛。
SA 实现简单，对离散组合问题很常用，但同样无最优保证，结果依赖随机性与降温表。
定位（必读）：仅作兜底。TSP、排程等若有专用精确/近似算法或可建 MILP，应优先尝试。使用 SA 必须固定种子、多次运行，并与 2-opt 局部搜索等基线比较。
二、适用场景与优缺点
| 类型 | 说明 |
|---|---|
| 适用场景 | 大规模组合邻域结构清晰（路径、分配、开关向量）；目标可快速评价；精确法不可行；需要单线程易实现的元启发式。 |
| 核心优点 | 代码短；能接受上坡移动；理论在无限缓慢降温下有收敛结果（实践达不到）；参数相对直观。 |
| 局限与缺点 | 降温过快易冻在劣解；过慢浪费评价；连续高维不如有梯度方法；约束需罚函数或邻域内保持可行。 |
强制检查：是否已尝试问题结构算法？是否有局部搜索基线？能否报告 次实验？
三、核心原理
1. Metropolis 接受准则
2. 冷却计划
常见：
- 几何降温 ，；
- 每个温度层迭代 次再降温；
- 初温使初始接受率约 ；终温使上坡几乎不接受。
3. 邻域设计（决定成败）
| 问题 | 邻域例子 |
|---|---|
| 0-1 串 | 翻转 1～2 位 |
| TSP | 2-opt、交换两城 |
| 连续向量 | 高斯扰动，步长随 缩小 |
邻域应「小步可到达、大步偶尔可跳」。
4. 与爬山法
且不接受上坡即为爬山/局部搜索。SA 的价值在于可控的上坡。
四、关键决策
1. 基线
至少跑纯局部搜索（只接受改进）与随机重启。若 SA 不能稳定优于它们，说明邻域或降温有问题。
2. 可行性
优先设计保持可行的邻域（如 TSP 交换仍是回路）；否则重罚。
3. 预算
以目标评价次数为公平预算，与基线对齐。
4. 复现
rng(seed)；记录每次最终 与最好 。
5. 停用条件
问题可转化为凸或中小 MILP 时，改回精确方法。
五、MATLAB 示例
例：TSP 的模拟退火 + 2-opt 邻域，与贪心基线对比
% 随机城市坐标
rng(1);
n = 20;
XY = rand(n, 2);
dist = squareform(pdist(XY));
% 路径长度
tourLen = @(tour) sum(dist(sub2ind([n n], tour, tour([2:end 1]))));
% ---- 基线1：最近邻贪心 ----
function tour = nnTour(D)
n = size(D,1); un = true(1,n); tour = zeros(1,n);
tour(1) = 1; un(1) = false;
for k = 2:n
last = tour(k-1);
cand = find(un);
[~, j] = min(D(last, cand));
tour(k) = cand(j); un(cand(j)) = false;
end
end
tour0 = nnTour(dist);
len0 = tourLen(tour0);
fprintf("最近邻基线长度 = %.4f\n", len0);
% ---- 基线2：纯 2-opt 爬山 ----
function [tour, L] = twoOptHill(tour, D, maxIt)
n = numel(tour); L = sum(D(sub2ind([n n], tour, tour([2:end 1]))));
for it = 1:maxIt
improved = false;
for i = 1:n-2
for k = i+1:n-1
% 2-opt 逆转 i+1..k
a = tour(i); b = tour(i+1); c = tour(k); d = tour(mod(k,n)+1);
delta = D(a,c)+D(b,d) - D(a,b)-D(c,d);
if delta < -1e-12
tour(i+1:k) = tour(k:-1:i+1);
L = L + delta; improved = true;
end
end
end
if ~improved, break; end
end
end
[tourH, lenH] = twoOptHill(tour0, dist, 100);
fprintf("2-opt 爬山基线 = %.4f\n", lenH);
% ---- SA 多次运行 ----
nRuns = 12;
bestLens = zeros(nRuns,1);
seeds = 5000 + (1:nRuns);
for r = 1:nRuns
rng(seeds(r));
tour = tour0(randperm(n)); % 随机起点排列
L = tourLen(tour);
bestTour = tour; bestL = L;
T = mean(dist(:)); % 粗初温
alpha = 0.995;
maxEval = 20000;
for ev = 1:maxEval
i = randi(n-1); k = randi([i+1, n]);
% 提议 2-opt
a = tour(i); b = tour(i+1); c = tour(k); d = tour(mod(k,n)+1);
if k == n, d = tour(1); end
% 简化：随机交换两位置
p = randperm(n, 2);
tour2 = tour; tour2(p(1)) = tour(p(2)); tour2(p(2)) = tour(p(1));
L2 = tourLen(tour2);
dE = L2 - L;
if dE <= 0 || rand < exp(-dE / max(T, 1e-12))
tour = tour2; L = L2;
if L < bestL, bestL = L; bestTour = tour; end
end
T = alpha * T;
end
% 末端再抛光
[bestTour, bestL] = twoOptHill(bestTour, dist, 50);
bestLens(r) = bestL;
end
fprintf("SA+抛光 %d 次: best=%.4f mean=%.4f std=%.4f\n", ...
nRuns, min(bestLens), mean(bestLens), std(bestLens));
fprintf("种子: "); disp(seeds);
fprintf("相对最近邻改进 %.2f%%, 相对2-opt改进 %.2f%%\n", ...
100*(len0-min(bestLens))/len0, 100*(lenH-min(bestLens))/max(lenH,eps));
连续问题可用 simulannealbnd（Global Optimization Toolbox）：
fun = @(x) (x(1)^2+x(2)-11)^2 + (x(1)+x(2)^2-7)^2; % Himmelblau
lb = [-5,-5]; ub = [5,5];
vals = zeros(10,1);
for r = 1:10
rng(70+r);
opts = optimoptions("simulannealbnd", "Display", "off");
[~, vals(r)] = simulannealbnd(fun, [0,0], lb, ub, opts);
end
fprintf("simulannealbnd best/mean/std = %.4f / %.4f / %.4f\n", ...
min(vals), mean(vals), std(vals));
六、如何解释结果
必须写清：
- 选用 SA 的理由（精确法不可用之处）；
- 邻域、初温、降温、每温度迭代/总评价次数；
- 种子与多次运行分布；
- 与贪心、纯局部搜索的对比表；
- 最终解的可行性与业务含义；
- 「随机近优，非全局证明」。
七、常见误区
1. 降温过快
曲线上很快不接受上坡，等价于烂爬山。
2. 邻域不会产生多样性
交换算子设计失败时，SA 再好也无效。
3. 只展示一次最佳运气
必须统计。
4. 连续可微问题放弃 fmincon
有梯度时 SA 通常不是首选。
5. 无基线宣称「效果很好」
没有参照的「好」不可信。
6. 约束靠巨大罚却从不检查可行性
最终方案可能仍不可行。
八、小结
模拟退火的核心思想可以概括为：
在邻域中随机走动，用温度控制的 Metropolis 准则接受上坡移动，并通过降温从探索过渡到利用，以寻求近优解。
它是组合优化中常用的兜底元启发式。正确姿态是：结构算法优先、基线必比、种子必报、多次必跑，把 SA 当作「在预算内找更好可行解的工具」，而不是最优性证书。