再谈模拟退火
源于现实的启发性算法：模拟退火与混合策略前言
模拟退火（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\) 概率性接受：
\
直观理解：
[*]温度 \(T\) 很高时，\(\exp\) 的结果接近 1，算法接受大部分劣解
[*]温度 \(T\) 接近 0 时，\(\exp\) 的结果接近 0，算法基本只接受更好的解（类似于普通贪心）
1.4 实操案例：模拟退火求解物理平衡点
以洛谷 P1337《平衡点/吊打XXX》为例。
注：虽然这个特定的物理问题本质上是一个凸优化问题（能量函数是一个单峰的函数，只有一个全局最优解，不存在局部陷阱），用梯度下降甚至三分法就能解决，但它非常适合用来演示模拟退火的标准流程。
题目大意：\(n\) 个重物系在绳子上，求绳结最终静止的 \((x, y)\) 坐标。本质是求系统总重力势能最小的点。
目标函数：
\
代码实现：
#include using namespace std;double deltaT = 0.996;double initT = 3000;double goalT = 1e-15;double a,b,c;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
页:
[1]