2. 模拟退火核心原理
模拟退火（Simulated Annealing, SA）是一种受固体退火过程启发的随机搜索算法。要真正用好它，不能只记住“温度下降、随机扰动、按概率接受”这几句口号，而应理解它为什么能在组合优化中跳出局部最优。本节围绕四个核心问题展开：物理退火与算法之间的类比关系、Metropolis 准则的数学含义、状态接受概率如何随温度变化，以及温度参数在整个算法流程中扮演的角色。
一、物理退火类比：从熔融金属到解空间搜索
在冶金学中，退火的操作是：先将金属加热到高温使其熔化，此时原子处于高能、无序的剧烈运动状态；随后缓慢降温，原子有足够时间重新排列，逐步落入低能晶格结构，最终形成内应力小、结构稳定的晶体。如果降温过快（淬火），原子来不及调整，会被冻结在亚稳态，形成缺陷较多的结构。
模拟退火把这一过程映射到优化问题上，对应关系如下：
- 物质状态 → 问题的一个候选解（状态）x；
- 内能 E → 目标函数值 f(x)，组合优化中通常求最小化；
- 温度 T → 控制搜索随机性的参数，从高温逐步降低；
- 热运动/扰动 → 对当前解施加邻域操作，产生新解 x′；
- 平衡态 → 在固定温度下反复采样后，解趋于该温度下的分布稳定；
- 缓慢降温 → 降温调度（cooling schedule），决定算法收敛行为。
这个类比的关键启示是：高温阶段允许“变差”，低温阶段趋于“保守”。正是这种由宽到严的接受策略，使算法前期能大范围探索，后期能精细收敛。
二、Metropolis 准则：如何决定接不接受新解
假设当前解为 x，目标函数值为 f(x)，通过邻域操作得到新解 x′，其值为 f(x′)。定义能量差：
ΔE = f(x′) − f(x)这里约定最小化目标函数，因此 ΔE < 0 表示新解更优，ΔE ≥ 0 表示新解不优于当前解。Metropolis 准则给出的接受规则是：
- 若 ΔE < 0：新解更优，无条件接受，令 x ← x′；
- 若 ΔE ≥ 0：新解不优，以概率 P = exp(−ΔE / T) 接受，否则保留原解。
实现时，生成一个 [0,1) 区间上的均匀随机数 r，若 r < P 则接受，否则拒绝。注意 T 必须为正数，且 ΔE 与 T 的量纲要匹配——若目标函数值动辄上千，而温度只取 1 左右，则 exp(−ΔE/T) 会迅速下溢为 0，算法退化为纯贪心。
Metropolis 准则的深刻之处在于：它不是简单地拒绝变差的解，而是按“变差程度”和“当前温度”给出一个受控的接受概率。这使算法在状态空间中按照玻尔兹曼分布进行采样，从而在理论上具备跳出局部最优的能力。
三、状态接受概率：温度如何调节“冒险程度”
接受概率 P = exp(−ΔE / T) 有两个自变量，其行为非常直观：
- ΔE 越大（新解越差），P 越小，越难被接受；
- T 越高，同样的 ΔE 对应的 P 越大，算法越“敢冒险”；
- 当 T → ∞ 时，P → 1，几乎接受任何新解，相当于随机游走；
- 当 T → 0 时，P → 0，只接受更优解，退化为局部搜索（爬山法）。
下面这张图展示了 Metropolis 接受判断的信号流与不同温度下的概率曲线关系，帮助建立“温度—概率—搜索行为”的直观联系。
从图中可以读出三条实践要点。第一，高温时曲线平缓，即使 ΔE 较大也有可观接受概率，算法表现为大范围探索；第二，低温时曲线陡降，稍差的解几乎不被接受，算法表现为局部精修；第三，温度必须与目标函数的数值尺度匹配，否则曲线会整体贴边，失去调节作用。
四、温度参数的作用与降温调度
温度 T 是模拟退火中唯一直接控制“探索—利用”平衡的参数。它不是一个固定值，而是一条随迭代递减的序列 T₀, T₁, T₂, …。常见做法是指数降温：
T(k) = T0 * alpha^k // alpha 通常取 0.90 ~ 0.99
或 T(k) = T0 / (1 + k) // 线性/倒数降温初始温度 T₀ 的选取原则是：使初始接受率处于较高水平（经验上可让约 70%～90% 的劣解被接受），可通过少量试探运行估计。终止温度 T_end 通常取到“劣解几乎不被接受”的量级，例如使 exp(−ΔE_avg / T_end) 小于 0.01。降温过快会导致早熟收敛，降温过慢则计算开销大。工程上常配合每个温度下的迭代次数 L（马尔可夫链长度）一起设定，保证在每一温度层充分采样后再降温。
五、算法流程框架
把上述要素串起来，模拟退火的标准流程是：初始化温度 T = T₀ 与初始解 x；在外层循环中，对当前温度执行 L 次内层迭代——每次通过邻域操作产生 x′，计算 ΔE，按 Metropolis 准则决定是否接受；内层结束后按调度降低温度；当温度低于 T_end 或达到最大迭代次数时停止，输出历史最优解。需要强调的是，算法应单独记录历史最优解 x_best，因为当前解在高温阶段可能暂时变差，最终输出不能直接取当前解。
理解本节原理后，后续实现中的邻域设计、参数整定与收敛判断，都将围绕“温度控制随机性、Metropolis 准则控制接受”这一核心机制展开。