Skip to content

模拟退火学习笔记

笔记约 1.1 千字
# 随机化 # 模拟退火
检测到 KaTeX 加载失败，可能会导致文中的数学公式无法正常渲染。

模拟退火算法（Simulate Anneal，SA）是一种通用概率演算法，用来在一个大的搜寻空间内找寻命题的最优解。模拟退火是由 S.Kirkpatrick, C.D.Gelatt 和 M.P.Vecchi 在 1983 年所发明的。V.Černý 在 1985 年也独立发明此演算法。模拟退火算法是解决 TSP 问题的有效方法之一。

模拟退火的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法是一种通用的优化算法，其物理退火过程由加温过程、等温过程、冷却过程这三部分组成。

—— 百度百科

简单来说，模拟退火是一种随机化算法。当一个问题的方案数量极大（甚至是无穷的）而且不是一个单峰函数时，我们常使用模拟退火求解。

#原理：转移尝试

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

—— 百度百科

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

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

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

#过程

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

其中 T0T_0 是一个比较大的数，Δ\Delta 是一个非常接近 11 但是小于 11 的数，TkT_k 是一个接近 00 的正数。

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

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

#技巧

#玄学调参大法

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

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

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

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

    1. 提高终止温度 TkT_k；
    2. 降低起始温度 T0T_0；
    3. 略微降低 Δ\Delta 的值。

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

#分块模拟退火

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

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

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

#卡时间

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

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