杂项专题-学习笔记：模拟退火

2023-10-23 19:34:16

杂项专题-学习笔记：模拟退火

1. 前言
2. 详解
3. 总结
4. 参考资料

1. 前言

模拟退火，是一种随机化算法，OI 中经常用来骗分，我因为不知道这算啥所以把它放在杂项里面了（貌似题目有点奇怪）。

模拟退火这个算法是根据金属退火原理发明的。

2. 详解

首先我们知道一般的二分 / 三分是根据当前决策点是否最优决定往哪边走的，换句话说如果当前点不优那么我们就不选取这个点。

然而这样很容易被限制在局部最优解上，如下图：

如果我们当前已知最优解是绿色，目前求出了个蓝色，不优然后我们往左边走了，就会舍弃掉真正的最优解红色。

因此我们需要模拟退火来取得最优解。

讲模拟退火首先我们需要知道金属退火：

将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。——百度百科

简称：温度高的时候运动幅度大，温度低的时候运动幅度小，最后达到稳定。

假设我们现在是在一个区间上求最小值，对应到我们的算法上来，具体运行步骤是这样的：

首先确定一个初始温度 t 0 ∈ [ 2000 , 6000 ] t_0 \in [2000,6000] t0∈[2000,6000]（特殊情况调参时可能会超出范围，下同），一个末端温度 t E n d ∈ [ 1 0 − 18 , 1 0 − 10 ] t_{End} \in [10^{-18},10^{-10}] tEnd∈[10−18,10−10]（足够小但是要大于 0），一个变化量 Δ t \Delta t Δt（略小于 1）。
设上一次我们选取的点是 x x x，这一次我们在 x x x 周围生成一个点 x ′ x' x′，其中 ∣ x ′ − x ∣ |x'-x| ∣x′−x∣ 是关于 t 0 t_0 t0 的一个函数， t 0 t_0 t0 越大这个值越大， t 0 t_0 t0 越小这个值越小。
设当前最优解 a n s ans ans，我们基于 x ′ x' x′ 算出了一个答案 s u m sum sum，如果 s u m < a n s sum<ans sum<ans 那么 a n s ← s u m , x ← x ′ ans \leftarrow sum,x \leftarrow x' ans←sum,x←x′，否则我们需要概率选取这个解，记函数 f ( s u m − a n s , t 0 ) = e a n s − s u m t 0 f(sum-ans,t_0)=e^{\frac{ans-sum}{t_0}} f(sum−ans,t0)=et0ans−sum，再随机一个 ( 0 , 1 ) (0,1) (0,1) 内的实数 p p p，如果 f ( s u m − a n s , t 0 ) < p f(sum-ans,t_0)<p f(sum−ans,t0)<p 那么我们接受这个点， x ← x ′ x \leftarrow x' x←x′，代码实现时可以写 exp(1.0 * (ans-sum)/t0)。

需要注意的是，我们的 x ′ x' x′ 是基于接受的最优解 x x x 生成的。

放上一张著名的图以供理解：

结合这张图分析一下上面的过程：

选取 x ′ x' x′ 的时候我们是在当前已知的最优解位置 x x x 上选取的，并且温度越小两者距离越小，也就是金属退火中的随着温度降低粒子运动速度越低。
我们接受答案的时候由于随着温度的降低，当前的非最优解被接受的概率也越来越小，因此答案也会逐渐稳定。

然后是关于 f f f 函数选取的问题，取 e x e^{x} ex 拿来做 f f f 是因为 e x e^{x} ex 是个增函数且 x < 0 x<0 x<0 时 f ∈ ( 0 , 1 ) f \in (0,1) f∈(0,1)，我们的目标是随着温度 t 0 t_0 t0（也就是分母）的降低概率逐渐减小，利用这一点来决定 f f f 和随机出来的实数中间的符号就不会弄错了。

注意利用这一点的时候需要保证 f f f 上的指数是个负数，也就是说求最小值的时候接受非最优解时 f = e a n s − s u m t 0 f=e^{\frac{ans-sum}{t_0}} f=et0ans−sum，求最大值时 f = e s u m − a n s t 0 f=e^{\frac{sum-ans}{t_0}} f=et0sum−ans，但宗旨就是 f < 0 f<0 f<0 并且 t 0 t_0 t0 越大概率越小。

代码还是很简单的，因为你选出 x ′ x' x′ 之后计算 s u m sum sum 还是比较直观的。

例题：P3878 [TJOI2010]分金币

这道题有别的做法，但是这里讲一下模拟退火怎么做。

每次我们随两个点 x ∈ [ 1 , m i d ] , y ∈ [ m i d + 1 , n ] , m i d = ⌊ n 2 ⌋ x \in [1,mid],y \in [mid + 1,n],mid=\lfloor\dfrac{n}{2}\rfloor x∈[1,mid],y∈[mid+1,n],mid=⌊2n⌋，然后看下要不要交换，交换之后答案变小就换，否则就概率性交换，就这么简单。

GitHub：CodeBase-of-Plozia

Code：

/*
========= Plozia =========
    Author:Plozia
    Problem:P3878 [TJOI2010]分金币
    Date:2022/1/27
========= Plozia =========
*/

#include <bits/stdc++.h>
std::mt19937 rng(std::random_device{}());

typedef long long LL;
const int MAXN = 30 + 5;
int t, n;
LL a[MAXN], ans, sum, fir, sec;

int Read()
{
    int sum = 0, fh = 1; char ch = getchar();
    for (; ch < '0' || ch > '9'; ch = getchar()) fh -= (ch == '-') << 1;
    for (; ch >= '0' && ch <= '9'; ch = getchar()) sum = sum * 10 + (ch ^ 48);
    return sum * fh;
}
int Max(int fir, int sec) { return (fir > sec) ? fir : sec; }
int Min(int fir, int sec) { return (fir < sec) ? fir : sec; }
LL Abs(LL x) { return (x < 0) ? -x : x; }

void SA()
{
    double t0 = 6081, tEnd = 1e-14, Deltat = 0.995;
    for (; t0 >= tEnd; t0 *= Deltat)
    {
        int x = rng() % (n >> 1) + 1, y = n - rng() % ((n >> 1) + (n & 1));
        sum = Abs(fir - (a[x] << 1) + (a[y] << 1) - sec);
        if (sum < ans) { ans = sum; fir = fir - a[x] + a[y]; sec = sec - a[y] + a[x]; std::swap(a[x], a[y]); }
        else if (exp((ans - sum) / t0) > (rng() * 1.0 / ((1u << 31) - 1 + (1u << 31)))) { fir = fir - a[x] + a[y]; sec = sec - a[y] + a[x]; std::swap(a[x], a[y]); }
    }
}

int main()
{
    t = Read();
    while (t--)
    {
        n = Read(); ans = sum = fir = sec = 0;
        for (int i = 1; i <= n; ++i)
        {
            a[i] = Read();
            if (i <= (n >> 1)) fir += a[i];
            else sec += a[i];
        }
        if (n == 1) { printf("%lld\n", a[1]); continue; }
        ans = Abs(fir - sec);
        for (int i = 1; i <= 20; ++i) SA();
        printf("%d\n", ans);
    }
    return 0;
}

需要注意的是，退火并不能保证每次都出正解（毕竟是个随机化算法），所以这里给出几种出正解的方法：

多跑几遍退火，得出正解。
必要的时候可以卡时间，设 StartTime=clock() 表示程序开始运行的时间，那么 (clock-StartTime)/CLOCKS_PER_SEC 可以得到当前程序运行的时间（以秒为单位），其中 CLOCKS_PER_SEC 是一个系统内置的常量，每个系统有所不同。
得到这个值之后就可以根据这道题的时间限制来决定卡多久，比如说 1s 的话可以让这个值小于 0.98s，到了就输出答案强制结束。
特别注意卡时间的时候要算好这次执行到这个语句与下次执行到这个语句中间的时间间隔，免得出现 1.001s -> TLE 的情况。
调参， t 0 , t E n d , Δ t t_0,t_{End},\Delta t t0,tEnd,Δt 都可以调，注意调参要小调不要大调，因为一点点的改动都会引起答案的巨大变化。

这里给出一个模拟退火的通用代码：

// 以求最小值为例
void SA()
{
    for (double t0 = /*自己定*/; t0 >= /*tEnd,自己定*/; t0 *= /*Deltat,自己定*/)
    {
        /* 计算 x'，下面是一个例子*/
        x_ = (x + (int)(rng() % n * t0 / /*最开始的 t0*/)) % n;
        Calc(); // 计算 sum
        if (sum < ans) { ans = sum; x = x_; }
        else if (exp((ans - sum) / t0) > (rng() * 1.0 / ((1u << 31) - 1 + (1u << 31)))) { ans = sum; x = x_; }
    }
}

退火还是好写的，也简单，求最值的问题都可以拿来写，但是符号不要写错，以及某些人会写成爬山算法（主要是没有严格遵守退火原理），注意一下即可。

3. 总结

退火是一种高效的骗分方式，可以用于各种求最值的问题，没思路就上退火尤其是考场上。

但是退火有几个易错点：

符号不要弄错，以及有没有严格遵守退火原理（注意是原理，写法可以不同）。
卡时间有没有卡错，有没有可能出现 1.001s -> TLE 的情况。
卡时间的时候有没有除以 CLOCKS_PER_SEC，这个博主有经历，2021 年 NOIp 的时候 T3 因为忘除了直接整道题挂掉，痛失一等。

码农公寓