模拟退火

模拟退火

问题引入

\(\,n\,\)个有\(\,k\,\)维性质以及价值\(\,w\,\)的物品,放入\(\,m\,\)个有\(\,k\,\)维限制的背包中,求总价值最大值

爬山&贪心

这题有一个显而易见的错误做法,先把物品按某种神秘方式排序,然后贪心地放入背包

于是考虑乱搞,每次random_shuffle一下物品,再重新计算,取历史最优解,正确率就得到提高了,但期望得到正解的次数是\(\,n!\,\)级别的,和暴力没有区别

考虑优化,发现这是因为没有利用之前贪心得到的一些优秀特征,比如有一个没有代价的物品被移来移去就是毫无意义的

由此可以发现,应当减少每次移动的数量,把random_shuffle变成swap,这样效率没有改变,但是按神秘方式排序后得到正确结果的概率提高了,耗费在移动上的时间也减少了

模拟退火

随贪乱搞显然是不行的,必须继续优化,发现随机swap依然可能导致优秀特征的随机损失或无效的交换

为了避免这一问题,模拟退火以一定概率接受随机的修改

分两种情况考虑:

新解优于历史最优解:当然接受这次修改

新解不优于历史最优解:以\(e^{\frac{\Delta f}{T}}\)的概率接受新解

\(\,\Delta f\,\)表示新解与历史最优解的差,\(\,T\,\)是模拟退火的一个可变参数,具体地,

\[T_{next\,\,time}=T_{now}*\delta \]

\(\,\delta\,\)是一个常数,取值通常在\(\,[0.98,1]\,\),用来更新\(\,T\,\),也就是当前温度

这样比完全随机接受优是因为\(\,\Delta f\,\)表明答案劣化的越少越容易接受,\(\,T\,\)的设置则使得接受新解的概率越来越小,使得算法越来越接近朴素爬山

名字叫模拟退火是因为从物理上固体退火得到的启发

模板:

calc();//计算新解
renew();//随机刷新
recover();//还原刷新
SA()
{
    auto tmp;
    double T=;
    while(T>=eps)
    {
        renew();
        tmp=calc();//临时答案
        if(better(tmp,ans)) ans=tmp;//如果更优
        else if(exp((tmp-ans)/T)*RAND_MAX<=rand()) recover();//有可能接受
        T*=delta;//刷新温度
    }
}

while(clock()<=CLOCKS_PER_SEC*MAX_TIME) SA();//卡时调用,MAX_TIME比题目时限小一点

解释一下

\[e^{\frac{\Delta f}{T}}\,\ast\,RAND\,MAX\leq rand()\rightarrow e^{\frac{\Delta f}{T}}\leq 0.5 \]

就可以做到随机接受了

上一篇:【高等数学】第二章 导数与微分——第五节 函数的微分


下一篇:python assert断言函数