再谈模拟退火

源于现实的启发性算法：模拟退火与混合策略

前言

模拟退火（Simulated Annealing, SA）在算法竞赛圈素来以“玄学”著称，广泛地被用于骗分。这类方法看似不需要过多思考，参数一设，成败全看天命（和脸黑不黑）。
但在我上大学接触机器学习后，发现这个被戏称为“骗分大法”的算法，其实有着严谨的理论。更有意思的是，如果将它与梯度下降结合，就能搞出一种强力混合算法。
一、模拟退火算法：源于热力学的全局优化方法

1.1 物理溯源：从固体退火到算法抽象

模拟退火的灵感来自于固体退火这一工艺流程，主要有两个阶段：

• 升温阶段：将固体加热至高温，粒子获得足够能量，处于无序的高能量状态（对应算法中的随机乱跑）；
  
• 降温阶段：缓慢且稳定降低温度，粒子热运动减弱，最终形成规则晶体（对应算法收敛到最优解）。
  

算法层面将这一过程抽象为：

• 能量：目标函数值（Function Loss）。我们的目标是让能量越低越好（最小化问题）；
  
• 温度：控制探索（Exploration）与利用（Exploitation）权衡的核心参数。高温时“瞎逛”寻找新大陆，低温时“内卷”精细打磨；
  
• 状态转移：从当前解生成邻域新解，并决定是否接受它。
  

值得注意的是，粒子热运动本质上都是通过统计学来预测的，所以存在一种可能即粒子能量可能反常升高，而这是模拟退火能够不同于其他算法的核心所在，即在温度下降过程中有一定概率接受劣解（比当前最优解差的解）。
1.2 算法核心流程拆解

流程严格对应物理退火，分为五步：

• 初始化：设定初始解、初始温度 \(T_0\)、衰减系数 \(\alpha\)、终止温度 \(T_{end}\)；
  
• 迭代降温：在当前温度下，多次生成邻域新解；
  
• Metropolis判定：关键一步！决定是否接受新解；
  
• 温度衰减：\(T = T \times \alpha\)，逐步收缩探索范围；
  
• 终止输出：温度降至冰点，输出历史最优解。
  

1.3 核心公式：Metropolis接受准则

这是模拟退火能够跳出局部最优解的关键。设当前能量 \(E_{now}\)，新解能量 \(E_{new}\)，能量差 \(\Delta E = E_{new}-E_{now}\)：

• 若 \(\Delta E < 0\)：新解更优（能量降低），无条件接受；
  
• 若 \(\Delta E \geq 0\)：新解更劣（能量升高），以概率 \(P\) 概率性接受：
  \[P = \exp\left(-\frac{\Delta E}{T}\right) \]
  

直观理解：

• 温度 \(T\) 很高时，\(\exp\) 的结果接近 1，算法接受大部分劣解
  
• 温度 \(T\) 接近 0 时，\(\exp\) 的结果接近 0，算法基本只接受更好的解（类似于普通贪心）
  

1.4 实操案例：模拟退火求解物理平衡点

以洛谷 P1337《平衡点/吊打XXX》为例。
注：虽然这个特定的物理问题本质上是一个凸优化问题（能量函数是一个单峰的函数，只有一个全局最优解，不存在局部陷阱），用梯度下降甚至三分法就能解决，但它非常适合用来演示模拟退火的标准流程。
题目大意：\(n\) 个重物系在绳子上，求绳结最终静止的 \((x, y)\) 坐标。本质是求系统总重力势能最小的点。
目标函数：

\[E(x,y) = \sum_{i=1}^n w_i \cdot \sqrt{(x-x_i)^2+(y-y_i)^2} \]
代码实现：
[code]#include using namespace std;double deltaT = 0.996;double initT = 3000;double goalT = 1e-15;double a[10001],b[10001],c[10010];int n;inline double cal(double x,double y){        double sum = 0;        for (int i=1;i=goalT){                double newx = nowx+(rand()*2-RAND_MAX)*nowT;                double newy = nowy+(rand()*2-RAND_MAX)*nowT;                double newans = cal(newx,newy);                if (newans= l){                                nowx = newx;                                nowy = newy;                                nowans = cal(nowx,nowy);                        }                }                nowT*=deltaT;        }        return {nowx,nowy};}signed main(){        srand(time(0));        cin>>n;        double x1 = 0,y1 = 0;        for (int i=1;i>a>>b>>c;                x1+=a;                y1+=b;        }        pair ans;        double minn = 10000000000.0;        for (int i=1;ical(tmp.first,tmp.second)){                        ans = tmp;                        minn = cal(tmp.first,tmp.second);                }        }                cout