模拟退火

番外

曾经看CY用模拟退火大杀四方，所以今天也来看一下这个算法，看了之后相见恨晚啊！我也不晓得为什么这么晚才学，多么优秀~~(暴力)~~的东西，QwQ

在这里声明并不是完全原创，大部分选自Darth_Che 的博客，

介绍

简介

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

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

原理

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

其实上面的可以不用看

简单的说，模拟退火就是在一种一定范围内求多峰函数最值的算法。它在模拟温度降低的同时得出新解，温度越高，解的变化量越大，随着温度的逐渐降低，解的变化量也渐渐变小，并越发集中在最优解附近。最后温度达到了我们设置的最低温，对应到物理学上也就是结晶了，这时，我们可以认为当前我们取得的解就是最优解，当然也可能不是，整个算法也就终止了。

实现

为了模拟退火，我要定义几个变量 当前最优解 $E_0$ ，新解 $E$ ，解的变动量 $\triangle E$ （ $E$ 与 $E_0$ 的差，注意这里可正可负），上一个被接受的解 $E_1$ ，初温 $T_0$ ，末温$T_k$ ，当前温度 $T$ ，温度变动量 $\triangle$

模拟退火的过程如图所示

$E$ 本来在大幅度的摆动，但随着 $T$ 的降低，摆动幅度也越来越小，也就越来越接近最优解，从 $T_0$ 开始，每次乘上 $\triangle$ 得到 $T$ ，如果 $T$ 小于 $T_k$ 则终止降温。 $T_0$ 我一般设置在 $1000 - 5000$左右， $\triangle$则是一个略小于$1$的常数，而 $T_k$ 一般设置在$1e-8$到$1e-15$ 之间(或者另外一个极小的数)。

在降温的同时，我们在 $E_1$ （不一定是最优解 $E_0$ ）的基础上扰动产生新解 $E$ ，需要注意的是扰动大小随温度的降低而变小，因为在温度高的时候，解的变化量非常大，这时的任务是在全局范围中找到最优解的大致位置，随着温度的降低，解渐渐稳定，这时的任务是确定最优解的准确位置。关键是每次得出新解以后，我们以什么原则，或者说什么概率来接受它呢？

这时就要用到 Metropolis 准则。简单说来，假设我们的目标是求最小值，如果 $E$ 小于 $E_0$ ，也就是 $\triangle E$ 小于 $0$ ，我们就接受当前解，因为它优于之前的最优解，非常显然。而如果 $\triangle E$ 大于 $0$ ，也就是我们遇到了一个更劣的解，我们也要以一定的概率来接受它，因为我们要找的一个多峰函数的全局最小值，因此就不能局限于一个局部的凹函数。而这个概率是 $\exp(− \triangle E/T)$

$\exp(-\triangle E/T)=e^{- \triangle E/T}$

可以这样玄学理解一下：对于 $\triangle E$ ，如果它较大，即我们遇到了一个劣得多的解，那我们接受它的概率就相对较小，因为 $- \triangle E$ 较小；而如果 $\triangle E$ 较小，即我们遇到了一个较劣的解，我们接受它的概率就较大，因为 $- \triangle E$ 较大。对于 $T$ ，随着时间的增加， $T$ 变得越来越小，因此我们把 $- \triangle E$ 除以 $T$ ，这样接受的概率就随着温度的降低而越来越小。而对于整个式子，当 $T$ 较大的时候，我们会接受大部分的解，当 $T$ 较小的时候，我们就只会接受 $\triangle E$ 较小的解。

大致就是这个样子的：

到这里我们也就知道，模拟退火算法的速度和结果受参数（ $T_0$ ， $T_k$ ， $\triangle$ 还有随机数种子）的影响非常大，是一个玄学的算法，时间复杂度也是$O$(玄学) 。

我们就可以通过调参，也就是调整$T_0$ ， $T_k$ ， $\triangle$来控制模拟退火的复杂度。

显然，模拟退火刷一次有太大的偶然性，所以我们选择刷多次，3次5次，如果有时间的话可以刷100次。QwQ

例题

UVA10228 A Star not a Tree? (opens new window)

题面是英文的，大概就是给出N个点，叫你求他们的费马点，也就是到每个点的距离之和最小。这道题可以直接上模拟退火的板子。

#include<iostream>
#include<cstdio>
#include<stdlib.h>
#include<iomanip>
#include<cmath>
#define R register
#define rep(i,a,b) for(R int i=a;i<=b;i++)
#define delta 0.996
#define maxn 50005
using namespace std;

inline int read() {
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9') {if(ch=='-') f=-f;ch=getchar();}
    while('0'<=ch&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*f;
}

struct node{
    double x,y;
}poi[maxn];
int T,n;
double ansx,ansy,ax,ay,ans,t;

void clear() {
    ax=0,ay=0;
    ans=1e8;
}

double calculate(double x,double y) {  
    double res=0;
    rep(i,1,n) {
        double dx=x-poi[i].x,dy=y-poi[i].y;
        res+=sqrt(dx*dx+dy*dy);
    }
    return res;
}

void simulate_anneal() {
    double x=ansx,y=ansy;
    t=3000; //设置初始温度
    while(t>1e-15) {
        double X=x+((rand()<<1)-RAND_MAX)*t;  //每次的该变量与 现在的温度 t 有关
        double Y=y+((rand()<<1)-RAND_MAX)*t;
        double now=calculate(X,Y); // 计算答案
        double Delta=now-ans;  // 计算 E 的该变量
        if(Delta<0) { // 选择是否接受
            ansx=X,ansy=Y;
            x=X,y=Y;
            ans=now;
        } else {
	        if(exp(-Delta/t)*RAND_MAX>rand()) 
		        x=X,y=Y;
		}
        t*=delta;  //降温
    }
}

void work() {//进行五次退火
    ansx=ax/n,ansy=ay/n;
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
    simulate_anneal();
}

int main() { 
    srand(1e9+7);  // 随机化种子填一个幸运数字
    T=read();
    rep(i,1,T) {
        n=read();
        clear();
        rep(j,1,n) {
            poi[j].x=read(),poi[j].y=read();
            ax+=poi[j].x,ay+=poi[j].y;
        }
        work();  //开始退火
        cout<<round(ans)<<'\n';
        if(i!=T) cout<<'\n';
    }
    return 0;
}

总的来说模拟退火是一个非常玄学的算法，能想到正解就少用吧