模拟退火是一类随机化玄学算法,当一个问题的方案数量极大而且不是一个单峰函数时,我们常使用其求解。
而且一些最优化问题如果想不到正解可以用其玄学骗分(这才是重点)
退火是什么?
退火是一种金属热处理工艺,指的是将金属缓慢加热到一定温度,保持足够时间,然后以适宜速度冷却。目的是降低硬度,改善切削加工性;消除残余应力,稳定尺寸,减少变形与裂纹倾向;细化晶粒,调整组织,消除组织缺陷。准确的说,退火是一种对材料的热处理工艺,包括金属材料、非金属材料。而且新材料的退火目的也与传统金属退火存在异同。 —— 百度百科
概念:
- 温度(步长):每次从一个点开始随机,温度越大,考虑范围越大。
两类:初始温度\(T_0\),终止温度\(T_{end}\) - 衰减系数\(\lambda\):顾名思义。线性衰减效果不好,故采用指数级衰减,从零到一,越靠近一,找到正解概率越大,但也越接近无脑爆搜。
算法步骤:
简单来说,就是有更好的就把原来的丢了,如果没有就以一定概率跳到另一个上。
- 每一次迭代,在当前范围内随机一个点,求出该点函数值。
- 比较次随机点与当前函数值的大小关系\(\Delta=f_{new}-f_{present}\)
- 情况\(1\): \(\Delta <0\),跳到新点上。
- 情况\(2\): \(\Delta >0\),以一定概率(\(e^{-\frac{\Delta}{T}}\))跳到新点上。
为了更接近正解,减小误差,可以多跑几次。
code
void simulate_anneal()
{
PDD cur(rand(0,10000),rand(0,10000));
for(double t=1e4;t>1e-4;t*=0.99)
{
PDD np(rand(cur.x-t,cur.x+t),rand(cur.y-t,cur.y+t));
double dt=calc(np)-calc(cur);
if(exp(-dt/t)>rand(0,1)) cur=np;
}
}
习题选做:
P1337 【JSOI2004】 平衡点 / 吊打XXX
P2503 【HAOI2006】 均分数据
P4035 【JSOI2008】 球形空间产生器
P3878 【TJOI2010】分金币
P4274 【NOI2004】 小H的小屋
P5544 【JSOI2016】 炸弹攻击1