最近对人类智慧比较感兴趣,于是学了一下这之中臭名昭著比较有名的 %你退货 模拟退火.
看不懂的定义
模拟退火算法来源于固体退火原理,
是一种基于概率的算法,将固体加温至充分高,再让其徐徐冷却,
加温时,固体内部粒子随温升变为无序状,内能增大,
而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小.
(别猜了就是从百度粘的)
(看个乐呵就行,没用)
个人理解
百度百科写的很反人类,但实际上这个算法非常亲民(除了调参的时候).
实际就是一种受自然现象启发发明的效率很高的随机化算法.
(像这样的算法还有很多,包括但不限于遗传算法)
大致过程
我们可以认为是在一条函数图像(一般是多峰)上有一定策略地跳来跳去.
为了便于理解,我们接下来会把这个函数图像比作一座山.
首先我们需要随便确定一个起始点(一般是选择原始数据的平均数),
然后就开始退火.
一般能模拟退火的题都会有两种东西:
一种是 '状态' ,也就是山上的点.
一种是 '结果' ,也就是当前点所在的"高度".
我们会基于当前状态点随机的跳来跳去.
对于更优的点,我们一定会接受.
而对于不更优的点呢?我们 概率接受 它.
为什么不是一定不接受?
想一个很简单的问题:高度比较高的地方就一定离山顶近吗?
显然不.
所以相比于完全贪心的爬山算法,模拟退火最大的特点就在此:
我们会以一定概率接受一个比当前状态不更优的点.
这个概率函数为
参数
模拟退火的框架大概是这样的:
const ldb down=0.996;
const ldb edge=RAND_MAX;
#define ldb long double
//请务必注意你变量的类型
//作者曾不止一次因为ldb写成int调了半天
void SA()
{
ldb T=3000;//初始温度
while(T>=1e-15)
{
int ex=x+rnd();// 随机化得到新状态
int eans=energy(ex);//求这个新状态对应的结果
int D=eans-ans;//新结果与原结果的差值
if(D<0)
x=ex,ans=eans;//新结果更优,接受
else if(exp(-D/T)*edge>rnd())
x=ex;//否则一定概率接受这个状态
T*=down;//降温
}
}
可以发现里面有很多参数,包括但不限于
\(T\)(初始温度),\(1e-15\)(终止温度),\(down\)(退火速度).
在实际的题目中,我们会不断地改变他们的值以控制运行时间或是提高正确率.
这个过程叫调参,可以认为是整个模拟退火中最麻烦的一部分.
一 些 例 题
P1337 [JSOI2004] 平衡点 / 吊打XXX
著名的模拟退火板子题.枚举的是重心的位置.
根据一些除了作者人人都会的物理知识,由重心产生的答案是最小的.
码
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define endl '\n'
const int N=1017000;
const int edge=RAND_MAX;
#define ldb long double
#define Croll(i,l,r) for(int i=l;i<=r;++i)
#define Troll(i,l,r) for(int i=l;i>=r;--i)
//////////
const ldb down=0.996;
int n;
struct starfield
{int x,y,w;}o[N];
void SA();
ldb ansx,ansy,answ;
ldb heart(ldb,ldb);
//////////
il int read();
//////////
int main()
{
srand(time(0));
n=read();
Croll(i,1,n)
{
o[i]={read(),read(),read()};
ansx+=o[i].x,ansy+=o[i].y;
}
ansx/=n;ansy/=n;
answ=heart(ansx,ansy);
SA();SA();SA();SA();
SA();SA();SA();SA();
SA();SA();SA();SA();
SA();SA();SA();SA();
//矩阵加速()
printf("%.3Lf %.3Lf",ansx,ansy);
return 0;
}
//////////
void SA()
{
ldb T=3000;
while(T>1e-15)
{
ldb ex=ansx+(rand()*2-edge)*T;
ldb ey=ansy+(rand()*2-edge)*T;
// cout<<ex<<" "<<ey<<endl;
if(ex>10000||ey>10000||ex<-10000||ey<-10000)
{
T*=down;
continue;
}
ldb ew=heart(ex,ey);
ldb De=ew-answ;
if(De<0)
{
ansx=ex;ansy=ey;
answ=ew;
}
else if(exp(-De/T)*edge>rand())
{
ansx=ex;ansy=ey;
}
T*=down;
}
}
ldb heart(ldb x,ldb y)
{
ldb ans=0,dx,dy;
Croll(i,1,n)
{
dx=x-o[i].x;
dy=y-o[i].y;
ans+=sqrt(dx*dx+dy*dy)*o[i].w;
}
return ans;
}
//////////
il int read()
{
int f=1,x=0;char w=getchar();
while(w<'0'||w>'9')
{if(w=='-')f=-1;w=getchar();}
while(w>='0'&&w<='9')
{x=(x<<3)+(x<<1)+(w^48);w=getchar();}
return f*x;
}
P2210 Haywire
个人感觉这道题比较有代表性.
这道题代表了模拟退火能处理的第二类问题:
通过改变序列元素的顺序得到答案.
码
#include<bits/stdc++.h>
using namespace std;
#define il inline
#define endl '\n'
const int N=1017;
#define lol long long
#define ldb long double
#define Croll(i,l,r) for(int i=l;i<=r;++i)
#define Troll(i,l,r) for(int i=l;i>=r;--i)
//////////
#define fr first
#define sc second
#define PII pair <int,int>
const ldb down=0.996;
const int edge=RAND_MAX;
mt19937 rnd(19280817);
//////////
int n,tot;
PII frd[N];
int pos[N];
void SA();
int ans;
int energy();
//////////
il int read();
//////////
int main()
{
n=read();
Croll(i,1,n)
{
int f1=read(),f2=read(),f3=read();
if(f1>i)
frd[++tot]={i,f1};
if(f2>i)
frd[++tot]={i,f2};
if(f3>i)
frd[++tot]={i,f3};
}
Croll(i,1,n)
pos[i]=i;
ans=energy();
SA();SA();SA();SA();
SA();SA();SA();SA();
SA();SA();SA();SA();
SA();SA();SA();SA();
cout<<ans<<endl;
return 0;
}
//////////
void SA()
{
ldb T=3000;
while(T>1e-15)
{
int rx=rnd()%n+1,ry=rnd()%n+1;
swap(pos[rx],pos[ry]);
int e=energy();
int D=e-ans;
if(D<0)
ans=e;
else if(exp(-D/T)*edge<rnd())
swap(pos[rx],pos[ry]);
//注意:这里的意思是,1-exp(-D/T)的概率变回原状态,等价于exp(-D/T)的概率接受当前状态
T*=down;
}
}
int energy()
{
int dis=0;
Croll(i,1,tot)
{
int x=frd[i].fr,y=frd[i].sc;
dis+=abs(pos[x]-pos[y]);
}
return dis;
}
//////////
il int read()
{
int f=1,x=0;char w=getchar();
while(w<'0'||w>'9')
{if(w=='-')f=-1;w=getchar();}
while(w>='0'&&w<='9')
{x=(x<<3)+(x<<1)+(w^48);w=getchar();}
return f*x;
}