概述
-
模拟退火是一种模拟物理学中材料退火现象的近似算法。
-
在物理的退火过程中,随着温度的逐渐降低,各粒子的能量会趋向性地稳定在最小值附近(但也有概率反常升高)。
-
于是我们尝试构建一种算法来模拟退火过程,对于每个状态,其估价函数越好,“能量”越低,反之亦然。
-
而温度就是体系活跃程度,即愿意改变状态的程度的标量。
思路
-
爬山算法的一个致命问题就在于,找到局部最优解后难以跳出其局限。
-
投放大量状态固然不失为一种选择,但显然只是一种补救而已。
-
我们能不能设法设计某种算法,其中的状态有一定的概率向不优(指估价函数)的状态转移过去?
-
于是有了模拟退火。
实现原理
-
开始时随机生成多个初始状态,并设置初始温度 \(T_0\),降温系数 \(D\)(通常 \(\in [0.985,0.999]\)),终止温度 \(T_k\)。
-
模拟退火算法的表现基本不依赖初始状态的状态,但可能依赖数量。
-
温度 \(T\) 是当前体系的一个标量,它标示着当前体系的活跃程度,也即愿意转移的程度(即使转移目标是一个较差解)。
-
模拟退火算法的表现比较依赖初始温度,原则上讲总体退火轮数越多效果会越好,但也越慢。
-
-
每轮我们依次枚举所有状态,从它们出发尝试扩展下一轮的状态。
-
对于每个被扩展出的状态,转移到它的概率是如下的函数:
-
其中 \(e\) 为自然对数的底,\(\Delta E=E_{to}-E\)。模拟退火中我们认为 \(E\) 越小的状态越优。
-
观察公式会发现,
-
当 \(\Delta E\leqslant 0\),即目标状态不劣于当前状态:一定转移,因为 \(P\geqslant e^0=1\)。
-
当 \(\Delta E>0\),即目标状态劣于当前状态:
-
\(e^\frac{-\Delta E}{T}=\dfrac{1}{e^\frac{\Delta E}{T}}=\dfrac{1}{\sqrt[T]{e^{\Delta E}}}\)
-
可以看出,\(\Delta E\) 越大即这一转移越差,分母越大,转移概率越小。
-
\(T\) 越大即温度越高,体系越活跃,分母越小,转移概率越大。
-
-
-
每轮结束时,令 \(T=T\times D\)。若 \(T<T_k\) 则结束。
-
由于模拟退火有可能最终解没有过程解优,我们一般维护遇到过的所有解的最优解。
-
由于最后的解可能不够精确,一般在退火完毕后做少量随机扰动。
例题
P1337 [JSOI2004] 平衡点
- 直接放代码吧。充当一个模拟退火的示范代码。
ld x,y;
il void SA(){
ld T=1e7,D=0.997,Tk=1e-9,tx,ty,delta;
x=rd01(),y=rd01();
while(T>Tk){
tx=x+zfrd()*rd01()*T;
ty=y+zfrd()*rd01()*T;
delta=calc(tx,ty)-calc(x,y);
if(exp(-delta/T)>rd01()) x=tx,y=ty;
T*=D;
}
For(i,1,10000) calc(x+zfrd()*rd01()*0.1,y+zfrd()*rd01()*0.1);
return;
}
标签:状态,tx,rd01,模拟退火,Delta,转移
From: https://www.cnblogs.com/weixin2024/p/17053170.html