模拟退火

蒟蒻到现在才学会模拟退火……

我太菜了……

简介

模拟退火(SA),是一种随机化算法。

在介绍模拟退火前,先要介绍爬山算法。

爬山算法是一种简单的贪心搜索算法,该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解。

爬山算法实现很简单,其主要缺点是会陷入局部最优解,而不一定能搜索到全局最优解。

当最优解是这种单峰时候,显然爬山算法可以求出全局最优解。

但是假如下图这个样子:

从最左边或者C点开始爬山的话,到B点就停止了,得不到全局最优解A。但是我们引入随机化,每次以一定的概率从各个位置开始爬山,假如随机到D点这类的点时候,就可以得到最优解了!

维基百科对模拟退火的描述是这样的:

模拟退火是一种通用概率算法,常用来在一定时间内寻找在一个很大搜寻空间中的近似最优解。模拟退火是S. Kirkpatrick, C. D. Gelatt和M. P. Vecchi在1983年所发明。而V. Černý在1985年也独立发明此算法。

模拟退火来自冶金学的专有名词退火。退火是将材料加热后再经特定速率冷却,目的是增大晶粒的体积,并且减少晶格中的缺陷。材料中的原子原来会停留在使内能有局部最小值的位置,加热使能量变大,原子会离开原来位置,而随机在其他位置中移动。退火冷却时速度较慢,使得原子有较多可能可以找到内能比原先更低的位置。

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

可以证明,模拟退火算法所得解依概率收敛到全局最优解

原理

模拟退火,就是模拟金属退火的过程寻找最优解。

金属退火是,先将金属加热到一定温度,再以特定的速度冷却。

在OI中,模拟退火也是如此,每次得到一个新的解,假如这个解更优,就作为当前最优解,否则和当前最优解做差,得的差记做$\Delta E$,以特定一个概率作为当前最优解。

根据热力学原理,这个概率为

其中$k$是一个随机数。这条公式说白了就是:温度越高,出现一次能量差为$\Delta E$的降温的概率就越大;温度越低,则出现降温的概率就越小。又由于恒有$\Delta E<0$(否则就不叫退火了),因此$\frac{\Delta E}{kT}<0$,所以$P(\Delta E)$的函数取值范围是$(0,1)$ 。

过程

简单来说就是降温,每次以特定的速度降低温度。

降温过程有3个参数:

初始温度$T_0$,降温系数$\Delta$,停止温度$T_{min}$。

先令当前温度$T=T_0$,每次用$T=T\cdot\Delta$迭代更新$T$来降温,当$T<T_{min}$时候,降温结束。

过程就像下面这样:

随着温度降低,当前最优解逐渐趋于全局最优解。

显然,时间复杂度$O(\text{玄学})$。

当然,次数越多越容易得到最优解。

代码

拿一道例题说明。

洛谷P1337 [JSOI2004]平衡点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<vector>

using LL=long long;
using LD=long double;

const int inf=0x7fffffff;
const LL linf=0x7fffffffffffffff;

const double delta=0.993;//降温系数
const double T=2000;//初始温度

int n;
double ansx,ansy;//用于更新答案
double ans=1e18;//当前最优解

struct ThingsNode
{
double x,y;
int weight;
};

std::vector<ThingsNode> Things;

double Ep(double x,double y)//求出某点为绳结时候所有重物重力势能总和
{
double sum=0;
for(auto it : Things)
{
double delta_x=x-it.x,delta_y=y-it.y;
sum+=sqrt(delta_x*delta_x+delta_y*delta_y)*it.weight;
/*根据E=mgh,g是常数忽略,h可以根据两点距离公式求得。*/
}
return sum;
}

void simulate_anneal()//模拟退火
{
double x=ansx,y=ansy,t=T;
while(t>1e-14)
{
//随机一个点坐标
double tx=ansx+(rand()*2-RAND_MAX)*t;
double ty=ansy+(rand()*2-RAND_MAX)*t;
/* -RAND_MAX <= tx,ty <= RAND_MAX */
double now=Ep(tx,ty);
double Delta=now-ans;
if(Delta<0)//新的解比当前最优解更优
{
x=tx,y=ty;
ansx=x,ansy=y;
ans=now;
}
else if(exp(-Delta/t)>rand()/RAND_MAX)//以某个概率更新答案
x=tx,y=ty;
t*=delta;//降温
}
}

void Solve()
{
simulate_anneal();
simulate_anneal();
simulate_anneal();
/*多来几次*/
}

int main()
{
srand(19260817);//某个大质数(逃
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
double x,y;
int w;
scanf("%lf%lf%d",&x,&y,&w);
Things.push_back((ThingsNode){x,y,w});
}
Solve();
printf("%.3lf %.3lf\n",ansx,ansy);
return 0;
}

随机化

模拟退火是随机化算法。

结果会受到srand()的值不同而影响,当多次提交AC不了时候可以试一试换一换srand()的值。

要注意调整合适的降温系数和初始温度。上面那个题系数调了好多值,在$\Delta=0.993$时候AC了。初始温度$T_0$可以大一些。

我在洛谷上面提交了好几次才找到了最佳的降温系数。

在时间允许的情况下尽量多做几次退火。

会正解的时候就不要使用这种非常不稳定的随机化算法。