模拟退火
(好久没有写博客,一写就是这么玄乎的东西......)
前言
- 对于这种十分神奇的近似算法
(xjb随机算法),我一向觉得这十分不靠谱。 - 然而,只有真正认真学习过这个
(极其富有魅力)的算法的人,才知道这个算法是多么的强(多么的不靠谱) - 那么,我就简单的介绍一下模拟退火。
算法的物理原理 (没什么用)
- PS:以下是摘自百度百科的物理原理介绍:
模拟退火算法来源于固体退火原理,将固体加温至充分高,再让其徐徐冷却,加温时,固体内部粒子随温升变为无序状,内能增大,而徐徐冷却时粒子渐趋有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。根据Metropolis准则,粒子在温度T时趋于平衡的概率为e(-ΔE/(kT)),其中E为温度T时的内能,ΔE为其改变量,k为Boltzmann常数。用固体退火模拟组合优化问题,将内能E模拟为目标函数值f,温度T演化成控制参数t,即得到解组合优化问题的模拟退火算法:由初始解i和控制参数初值t开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t值,算法终止时的当前解即为所得近似最优解,这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制,包括控制参数的初值t及其衰减因子Δt、每个t值时的迭代次数L和停止条件S。
- 是不是发现,有点看不懂呢?甚至有一点点懵逼呢?
- 其实,这些内容没什么太大意义只是用来看看的。
- 唯一有点用的,可能就是那个平衡概率吧。
算法在oi中的作用
- oi中存在许多无法在多项式时间内解决的问题,如经典的TSP问题, 求费马点等多种问题。这也就是人们所熟知的np难问题。
- 人们不能忍受在指数时间内达到正确的解。因为即使解是正确的,但可能到世界毁灭,这个解也跑不出。
- 所以,人们期望有一种时间复杂度低,但是却能得到近似解的算法。即使这个算法得出的答案可能不是完全正确的。
- 这时,模拟退火,爬山,遗传算法,蚁群算法就渐渐到了人们的关注中,显得尤为重要了。
- 总而言之,模拟退火的作用就是:在较短的时间内,得到十分接近的答案,或者得到的就是答案。
算法实现
- 在知乎还是哪有一个特别有趣的比喻,在一定程度上说明了爬山算法与模拟退火的实现:
- 爬山算法:兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。但是这座山不一定是珠穆朗玛峰。这就是爬山算法,它不能保证局部最优值就是全局最优值。
- 模拟退火:兔子喝醉了。它随机地跳了很长时间。这期间,它可能走向高处,也可能踏入平地。但是,它渐渐清醒了并朝最高方向跳去。这就是模拟退火。
- 从以上那毫无意义的物理原理,我们可以看出,模拟退火的主要步骤有几个:
- 设置初始温度\(T\),初始符合条件的答案;
- 通过某种神奇的方式,找到另一个符合条件的新状态;
- 分别将两个状态的答案计算出来,并作差得到\(\Delta E\)
- 根据题目要求,贪心的决定是否更换答案。即:选择最优解。
- 如果无法替换答案,则根据一定概率替换答案。即运用到上述的平衡概率\(exp(\Delta E / T)\)随机的决定是否替换。
- 每一次操作后,进行降温操作。即:将温度\(T\)乘上某一个系数,一般是\(0.985-0.999\)随具体题目
(随缘)定。
我们可以根据上述过程写出一段伪代码:
eps=1e-15;
T=初始温度;
while(T>eps)
{
now=从当前最优状态随机更新的一个状态;
delta=calc(now)-calc(ans);
if(delta与题目要求的满足更优)ans=now;
else if(exp(delta/T)*RAND_MAX>rand())ans=now;//PS:这里的delta前面可能要加'-';
T*=t0;//t0一般在0.985-0.999之间,根据具体题目时间,随缘调试。。。
}
- 这就是模拟退火的具体实现方式,应该代码已经不难实现了。
- PS:有一点需要注意的是,用平衡条件进行更新答案的时候,要根据题目判断\(\Delta E\)前要不要加\(-\),如果实在判断不出,就两种都试一试。如果其中一种出现特别大的答案,或很奇怪的答案,那就用另一种吧。要么就把那一行注释掉,看看答案的变化大不大。
- 那么,模拟退火就讲完了。具体的代码实现,就通过具体的题目来看吧。
例题
( 题目打完了,还没写题解。最近一篇篇加进来吧。)