浅谈玄学算法——模拟退火

> 由于作者写这篇文章时水平并不高（虽然现在也不高），因此文中可能有许多错误，请谨慎观看。欢迎评论或私信指出。 > > update on 2021.11.20：修改了一些内容。 > > update：作者退役很久啦，还是建议去看别人的文章 # 初级篇 本篇讲解模拟退火的基本概念。 如果您已经了解模拟退火的基本概念，您可以跳过这一段。 ## 简介 > 模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由S.Kirkpatrick, C.D.Gelatt和M.P.Vecchi在1983年所发明的。V.Čern&yacute;在1985年也独立发明此演算法。模拟退火算法是解决TSP问题的有效方法之一。 > 模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。 > ——百度百科 简单说，模拟退火是一种随机化算法。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们可以使用模拟退火求解。 它与爬山算法最大的不同是，在寻找到一个局部最优解时，赋予了它一个跳出去的概率，也就有更大的机会能找到全局最优解。 模拟退火算法一般在提交答案题中使用，有时也可以用来乱搞。 ## 原理 > 模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有“能量”，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个“邻居”，然后再计算从现有位置到达“邻居”的概率。 > ——百度百科 要将模拟退火，首先要知道[金属退火](https://baike.baidu.com/item/%E9%80%80%E7%81%AB/1039313?fr=aladdin)。 简单来说，就是将金属加热到一定温度，保持足够时间，然后以适宜速度冷却。 对应到 OI 上，就是每次随机出一个新解，如果这个解更优，则接受它，否则以一个与温度和与最优解的差相关的概率接受它。 ## 过程 ### 降温 模拟退火时有三个参数，分别是初始温度 $T_0$、降温系数 $\Delta$、终止温度 $T_k$。 其中，$T_0$ 是一个比较大的数，$\Delta$ 是一个略小于 $1$ 的正数，$T_k$ 是一个略大于 $0$ 的正数。 我们先让温度 $T=T_0$，然后每次降温时 $T$ 乘上 $\Delta$，直到 $T\leq T_k$ 为止。 大致过程如下：  可以看出，随着温度的降低，解逐渐稳定下来，并逐渐集中在最优解附近。 ### 生成新解 在当前解的基础上生成一个新解。这里的方式很多，需要根据题目具体情况选定。 > 按道理来说这个新解在原来的解的基础上变化的程度是和 $T$ 有关的，$T$ 越大变化的程度越大。但是有时候这难以实现所以可以不这么搞。 ### 调整 如果新解更优，接受这个解。 否则我们以一定概率接受这个解。设 $\Delta W$ 为新解和当前解的差（$\Delta W > 0$）。我们希望的是：$T$ 越大时概率越大，$\Delta W$ 越小时概率越小。我们选择 $e^{-\frac{\Delta W}{rT}}$ 作为概率，这里的 $r$ 是一个随机数。 当然，如果 $\Delta W$ 很大或很小的话这样子就可能会出问题。我们可以通过合理选择 $r$ 的范围来解决问题。 ### 其它 程序开始时，我们要先`srand(一个常数)`。这个常数可以决定分数。你可以使用 233333，2147483647，~~甚至某个八位质数~~。 一遍模拟退火往往无法跑出最优解，所以可以多跑几遍。 可以用一个全局变量记录所有跑过的模拟退火的最优解，每次从那个最优解开始继续模拟退火，可以减小误差。 # 进阶篇 本篇讲解模拟退火的实际应用。 ## 如何调参 $r$ 的范围、$\Delta$、$T_0$，$T_k$ 等都会决定你的分数。 我们探讨一下模拟退火的~~玄学~~调参。 Q：答案不是最优的怎么办？ A：有以下几种方法：调大 $\Delta$、调整 $T_0$ 和 $T_k$，以及多跑几遍模拟退火。 当您的程序跑的比较快时，可以选择多跑几遍模拟退火，或者调大 $\Delta$，从而增大得到最优解的概率。 Q：还是跑不出最优解怎么办？ A：~~那可能是您太非了~~尝试更换随机数种子，或者`srand(rand())`，总之，总有可能跑出正解。 Q：我是非酋，交了两页也没有用模拟退火AC，怎么办？ A：~~您还是选择打正解吧。~~ ## 例题 这里以[洛谷1337 [JSOI2004]平衡点 / 吊打XXX](https://www.luogu.org/problemnew/show/P1337)为例，讲解模拟退火的实际应用。 题目要使整个系统的能量最小。那么我们只要用模拟退火跑出这个最小值即可。 ```cpp #include <bits/stdc++.h> #define re register using namespace std; inline int read() { //读入优化 int X=0,w=1; char c=getchar(); while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); } while (c>='0'&&c<='9') X=(X<<3)+(X<<1)+c-'0',c=getchar(); return X*w; } struct node { int x,y,w; }; node a[1010]; int n,sx,sy; double ansx,ansy; //全局最优解的坐标 double ans=1e18,t; //全局最优解、温度 const double delta=0.993; //降温系数 inline double calc_energy(double x,double y) { //计算整个系统的能量 double rt=0; for (re int i=1;i<=n;i++) { double deltax=x-a[i].x,deltay=y-a[i].y; rt+=sqrt(deltax*deltax+deltay*deltay)*a[i].w; } return rt; } inline void simulate_anneal() { //模拟退火主过程 double x=ansx,y=ansy; t=2000; //初始温度 while (t>1e-14) { double X=x+((rand()<<1)-RAND_MAX)*t; double Y=y+((rand()<<1)-RAND_MAX)*t; //得出一个新的坐标 double now=calc_energy(X,Y); double Delta=now-ans; if (Delta<0) { //接受 x=X,y=Y; ansx=x,ansy=y,ans=now; } else if (exp(-Delta/t)*RAND_MAX>rand()) x=X,y=Y; //以一个概率接受 t*=delta; } } inline void Solve() { //多跑几遍模拟退火，减小误差 ansx=(double)sx/n,ansy=(double)sy/n; //从平均值开始更容易接近最优解 simulate_anneal(); simulate_anneal(); simulate_anneal(); } int main() { srand(1******7); srand(rand()); srand(rand()); //玄学srand n=read(); for (re int i=1;i<=n;i++) { a[i].x=read(),a[i].y=read(),a[i].w=read(); sx+=a[i].x,sy+=a[i].y; } Solve(); printf("%.3f %.3f\n",ansx,ansy); return 0; } ``` 这份代码跑了 476 ms，可以通过，而且时间比较充裕。 # 实用篇 本篇讲解模拟退火的一些魔改。 ## 在不会TLE的情况下尽量多地跑模拟退火 我们知道，有一个`clock()`函数，返回程序运行时间。 那么这样即可： ```cpp while ((double)clock()/CLOCKS_PER_SEC<MAX_TIME) 模拟退火(); ``` 其中`MAX_TIME`是一个自定义的略小于题目时间限制的数。 ## 分块模拟退火 我们发现，有时候模拟退火是不好用的，比如函数的峰很密集的情况。这时可以把值域划成几块，然后每块分别跑一遍退火。 ## 小结 以上就是关于模拟退火的一些基本内容了。大家不难看出，这个算法还是很玄学的。 正式比赛中不建议在除了要随机化的提答题中使用，除非你只是想骗分。