模拟退火学习笔记

#原理：转移尝试

模拟退火的原理也和金属退火的原理近似：将热力学的理论套用到统计学上，将搜寻空间内每一点想像成空气内的分子；分子的能量，就是它本身的动能；而搜寻空间内的每一点，也像空气分子一样带有「能量」，以表示该点对命题的合适程度。演算法先以搜寻空间内一个任意点作起始：每一步先选择一个「邻居」，然后再计算从现有位置到达「邻居」的概率。

—— 百度百科

对应到 OI 上，就是每次随机出一个新解，如果这个解更优，则接受它，否则以一个与温度和与最优解的差相关的概率接受它。

每次转移尝试时需要先根据已知状态，通过随机的方式得到一个新的状态，记新状态与已知状态之间的能量（值）差为 $\Delta E$（$\Delta E\geqslant 0$），则发生状态转移（修改最优解）的概率为：

$$P(\Delta E)= \begin{cases} 1 & \text{新状态更优} \\ \large{e^{\frac{-\Delta E}{T}}} & \text{新状态更劣} \\ \end{cases}$$

#过程

模拟退火的过程有三个参数：初始温度 $T_0$，降温系数 $\Delta$，终止温度 $T_k$。

其中 $T_0$ 是一个比较大的数，$\Delta$ 是一个非常接近 $1$ 但是小于 $1$ 的数，$T_k$ 是一个接近 $0$ 的正数。

每次模拟退火的开始都要先让温度 $T = T_0$，然后再不断地进行转移尝试，尝试结束之后令 $T = \Delta \times T$，继续重复转移过程，直到 $T < T_k$ 时模拟退火过程结束，当前最优解即为最终的最优解。

为了使得解更为精确，我们通常不直接取当前解作为答案，而是将答案记为在退火过程中维护遇到的所有解的最优值。

#技巧

#玄学调参大法

在评测时可能会遇到以下情况：

1. 答案不正确，可以尝试：

   1. 多跑几遍模拟退火；
   2. 降低终止温度 $T_k$；
   3. 提高起始温度 $T_0$；
   4. 增大 $\Delta$ 的值（但不要使其 $\geq 1$）；
   5. 更改随机数种子。

2. 时间超限，可以尝试：

   1. 提高终止温度 $T_k$；
   2. 降低起始温度 $T_0$；
   3. 略微降低 $\Delta$ 的值。

如果实在不行，就该考虑写正解或者放弃这道题了。

#分块模拟退火

有时函数的峰很多，模拟退火难以跑出最优解。

此时可以把整个值域分成几段，每段跑一遍模拟退火，然后再取最优解。

注意块的大小不以 $\sqrt{n}$ 为佳，应根据每题的实际情况设定。

#卡时间

在 <ctime> 头文件中定义了一个名为 clock() 的函数，可以返回进程执行到当前时间时所用的粗略处理器时间。将此值除以 CLOCKS_PER_SEC 可转换为秒。

可以使用 while ((double)clock() / CLOCKS_PER_SEC < MAX_TIME) 来在超时前结束程序，MAX_TIME 应设置为一个略小于题目时限的秒数。