模拟退火进阶

做了相当一部分的退火题练手，现在才算刚刚入了门。

于是做一个经验总结。

随机函数

有没有觉得 $rand()$ 莫名的不好用？我们在此为您推荐

\[mt19937!\]

在支持 $c++14$ 的环境下，可以生成更大的随机数，而且更快，岂不美哉？

实用展示

mt19937 rd_ori(time(0)+114514);
template<class T>
inline T rd(T L,T R){
	return std::uniform_int_distribution<T>(L,R)(rd_ori);
}

这样调用 $rd(l,r)$ 就能生成范围内的随机数了，这比 $mod$ 来 $mod$ 还是方便了很多。

然后对于暴刷数列排列的，我们还有 $shuffle$ 可以用。

好这个我们不多说了，进下一个环节。

基本参数

1.温度系数

我们一般选取一个 $1000$ 左右的初始温度，然后以一个越接近 $1$ 越好的降温系数降温，最后再以一个 $1\times 10^{-6}$ ~ $1\times 10^{-15}$ 的数作为终止温度。

由于我们选取新的方案的浮动程度是依照温度来的，也即温度越高浮动越剧烈，于是并不是所以的题我们都初始温度选取 $1000$.

为了方便，我们称初始温度为 $tst$ ,当前温度为 $tem$ ,结束温度为 $ted$ ,降温系数为 $dt$.

当我们不需要过大范围的浮动，或者我们希望程序不飞到特别邪教的点，我们将 $tst=1$ 左右，让其相对稳定的浮动。我们还可以控制步长为一个数，而非随机。

当然我们有的题的方案选择与温度无关，像非计算几何题的模拟退火。

这时我们温度选择只影响我们勉强的选择劣解，于是只要正常弄即可。

一般来说，我们选择相对小的终止温度，除非你发现当你温度较小的时候你的退火是 $meaningless$ 的。（像完全没有任何方案更新的情况）

对于时间充裕的情况，我们一般降温系数取 $0.99999$ ，否则可以选取 $0.9927$ 或 $0.9967$

总得来说就是要能够随机应变。

2.劣解接受率

我们采用传统的 $exp(-\frac{\Delta}{t} )$ 为接受劣解的概率，当然若是优解，我们必定接受。

其中 $\Delta$ 为新解与全局最优解的差值。（但是有的题是与当前解的差值）

但是显然在有些情况下我们不考虑接受劣解，直接整爬山可能更优秀，可以分析一下解与方案的函数走势，然后根据单调性选择。

当然一些情况下，我们采用启发式的接受率，不过前提是你需要保证启发式的正确性和最优性，否则可能聪明反被聪明误，导致陷入次优解无法自拔。

有的时候两个方案的解相同，比如都是 $0$ ,我们需要为其专门构造趋向于获得答案的方向的劣解接受函数。如 [JSOI2016]炸弹攻击1

顺便推荐一个题单

3.方案选取

在不能保证启发式的最优性和正确性的情况下，考虑完全随机。否则还是容易陷入次优解无法自拔。

前面提到了可以控制步长，我们还可以大乱跳，不过用得少。

这里没太多好说的。尽量在当前解附近按照温度选即可。

4.退火次数

有的时候我们跑一遍退火不一定得到正确答案，所以我们跑多次。

但是发现这样弄容易 TLE。

所以我们考虑添加一个卡时间用的操作。

我们在里面判断一下 $(clock()/1000)>lim$ 是否成立，成立就直接快进到输出答案。这里除 $1000$ 是为了适应 $linux$ ,window下不比这样，提交的时候改一下就好。然后记得退出的时候留 $50$ ~ $100ms$ 给他做一个收尾，免得TLE（输出多的时候还要再多分配一些）。如果不超时，我们直接 $while(1)$.

5.少许优化

先考虑在算法上的优化，跑得越快，跑得越多，于是更可能正确。

比如我们可以用退火配合一些 $dp$ 之类的算法来提高正确性。

然后对于我们的初始方案，我们以启发式来选择。只要不选得过于离谱都是对答案有益的。