模拟退火

· · 算法·理论

:::epigraph[——Hongify] 模拟退火可是骗分的一把好手啊！ :::

（在博客查看？）

模拟退火是一种启发式、随机化的算法，用于在较大搜索空间中寻找近似最优解。\ 其灵感来自于金属冷却（即“退火”），高温时金属在高温、不稳定的状态，冷却后在低温、稳定的状态。

引入

我们考虑这个问题，如何找到函数 f(x) 的最小值。

采用爬山算法（即贪心），每次都取更优的状态，例如下面这个例子：

我们可以从 A 点下降到 H 点，从而找到最低点 H。

可是不是每个人都生在罗马，总会遇到这种情况：

如图，如果我们从 A 点出发，最后会到 B 点，即为局部最优解，可是全局最优解明显是在 C 点。

这样我们无法找到全局最优解。一味地下降不是好办法，那怎么办呢？

我们可以部分接受比现在更差的状态，从而跳出这个局部最优的“山谷”。

思想

以一定概率接受比当前状态差的新状态。

我们定义：

那么，接受新状态的概率 P 的表达式就是：

P=\begin{cases} 1 ,& \Delta \le 0 \\ e^{-\Delta / T} ,& \Delta > 0 \end{cases}

::::info[函数 e^x 的了解]

不难发现，当 x>0 时，e^x>1；当 x<0 时，0<e^x<1。

所以，（x<0 时）x 越小，e^x 越小。

将 x 替换为 - \frac{\Delta}{T}（\Delta >0），此时- \frac{\Delta}{T}<0，于是 0<e^{-\Delta / T}<1，可以用来表示一个概率。

注：对于不同的问题，条件可能会有所变化，这里以寻找函数最小值为例

代码实现

代码思路

我们会写一个评估函数calc()，用于计算当前状态的函数值，通常每道题都不一样。

接着是模拟退火主体函数sa()（也可以写成simulated_annealing()，都一样的），用于计算概率并调整状态。

最后是主函数main()，用于输入输出。

值得注意的是，由于模拟退火算法有随机的成分，不能保证每次都给出正确结果，所以在主函数中要循环多次。

具体代码

#include<bits/stdc++.h>
using namespace std;
int N,n;
double ans=1e8;
struct P
{
    double x,y;
}q[N];
double calc()
{
    double k;
    ......
    return k;
}

void sa()
{
    for(double t=1e5;t>1e-10;t*=0.996)//此处的1e5,1e-10,0.996都是常数，分别为初始温度，终止温度和降温系数
    {
        int a=......,b=......;
        double nw=calc();
        swap(q[a],q[b]);
        double nx=calc();
        ans=min(ans,nx);
        double d=nx-nw;
        if(!(d<0||exp(-d/t)*RAND_MAX>rand()))//判断优劣，以一定概率接受，这里是反着的写法
            swap(q[a],q[b]);
    }
}

int main()
{
    scanf("%d", &n);
    for(int i=1;i<=n;i++)scanf("%lf", &q[i].x);
    for(int i=1;i<=n;i++)scanf("%lf", &q[i].y);
    for(int i=1;i<=20;i++)sa();//多次模拟退火
    printf("%lf\n", ans);
    return 0;
}

如果想把评测机的时间跑满，也可以将第35行的代码换成下面这个：

//for(int i=1;i<=20;i++)sa();
while ((double)clock() / CLOCKS_PER_SEC < 0.9) sa();

可以让你在0.9秒的时限内跑完。不是1秒的原因我不说

调参

我们主要调初始温度，终止温度，降温系数和退火次数这几个参数。

模拟退火的灵魂就在于调参，不能过慢导致TLE，也不能过快导致错过最优解。

总之，需要调到合适的参数，使得模拟退火的性能与效率达到平衡。

模拟退火的弊端

模拟退火作为一种随机的算法，其答案并不保证完全准确，理论来说是有很小的概率出错的。在20次模拟退火中，大约有0.000095%的概率出错。正好碰到的话是运气好还是运气差呢？

有部分题目会故意卡模拟退火。相比之下正解不仅比模拟退火稳定，还比模拟退火更优。

模拟退火太夯啦，我就要用模拟退火！\ 结果TLE/WA……

还有些无法使用模拟退火解决的问题，例如无法写出评估函数的题目等。

后话

模拟退火足够无脑，个人还是很喜欢模拟退火的。\ 才不是因为我学了一点物理竞赛呢！