模拟退火笔记(详细)

别着急,干货在最后面!!!(本文用c++实现)

很多人都学过贪心,但是贪心在一些情况并不适用,比如:

模拟退火笔记(详细)

已知我们从黄色出发,找最小值。

贪心策略当然是一直往函数大小减小的地方偏移——但是,万一不是单峰呢?我们会陷入如图的蓝色中无法自拔。

肯能你会想到:随机找一个点出发,然后贪心找最小值?多随机几遍,然后求全局最小值?

你会发现复杂度暴增!!!!!!!!——所以如何处理这种问题呢?

模拟退火:啊,对对对~

是的!模拟退火就是一种类似于随机化贪心的一个算法,在OI界也小有名气(冥器)!(如题[NOIP2021] 方差

原理图:

模拟退火笔记(详细)

如图:在物理应用中分子排布可能是紊乱的,如果我们将它升温然后缓慢降温,就可以生成完美的晶形!

所以我们立刻(啊,对对对~)能设定模拟退火的参数:

1.初始温度 T (1000-7000)

2.末尾温度 P(1e-5~1e-15)

3.降温系数 K (0.91~0.9975)

4.状态空间(被降温物体) S

5.当前能量 E ( new )

6.全局能量 E ( old )

一:Metropolis准则 - 以概率接受新状态:

 

模拟退火笔记(详细)

 

 

这就是物理(化学)方面类似的推论——一定概率的更新。

什么意思呢?

我们已知:当前能量 E ( new ) , 全局能量 E ( old ),那么我们的目标是什么,不就是减少目前的能量吗?

所以:当当前能量少于全局能量(即更新前的能量),那么我们有概率为 1 的更新概率;

      当当前能量大于全局能量(即更新前的能量),那么我们有概率为 exp( - (E( new )-E( old ))/T) 的更新概率 ( T为当前温度) ;

注意:有时候也不一定以以上方式更新,这只是比较妥的做法,概率方面是可以自己定的,但是一定以当前能量与全局能量的关系来设定的。(除非直接暴力的随机算法)

二:

那么怎么生成新的当前温度呢?,以生成小数为例:

当前将更新温度=全局温度+(rand()*2-RAND_MAX)*t;
if(不在状态空间内){
    当前将更新温度=fmod(当前将更新温度,状态空间大小)
}

  即:在当前状态的邻域结构内以一定概率方式(均匀分布、正态分布、指数分布等)产生。

三:温度更新函数

若固定每一温度,算法均计算至平稳分布,然后下降温度,则称为时齐算法;

若无需各温度下算法均达到平稳分布,但温度需按一定速率下降,则称为非时齐算法。

本人用的:

T*=K;

四:内循环终止准则 

本人使用的:

(t>1e-15)//可以改大一点

其他常用方法:

    (1)设置终止温度的阈值。

    (2)设置外循环迭代次数。

    (3)算法搜索到的最优值连续若干步保持不变。

    (4)概率分析方法。

五:实现流程图:

模拟退火笔记(详细)

 

 

注意:以下是我自己总结的退火口诀:

初始温度小心设(1000-3000),又粗又大wa一脸

多次sa更保险,忘了卡时直接T[if((double)clock()/CLOCKS_PER_SEC>=0.993)]

退火系数大胆设,不过0.9975会很厄

全局、状态不一样,全局必须菊部优

百年骗分一场空,不开srand见祖宗

退火需谨慎,退火不规范,灵封两行泪

然后是[NOIP2021]方差的实现(玄学万岁):

#include <bits/stdc++.h>
using namespace std;
#define LL long long
const int N=1e5+10;
const double dw=0.9975;
int a[N],n,c[N];
long long ans;
bool cmp(int a,int b){
    return a>b;
}
LL en(){
    LL em=0;
    LL ranss=0;
    for(int i=2;i<=n;i++){
        a[i]=a[i-1]+c[i];
    }
    for(int i=1;i<=n;i++){
        em+=(long long)a[i]*a[i];
    }em=(long long)em*n;
    for(int i=1;i<=n;i++){
        ranss=(long long)ranss+a[i];
    }ranss=(long long)ranss*ranss;
    return (long long)(em-ranss);
}
void sa(){
    double t=1000;
    while(t>1e-15){
        if((double)clock()/CLOCKS_PER_SEC>=0.993){
            cout<<ans;
            exit(0);
        }
        int x=rand()%(n-1)+2,y=rand()%(n-1)+2;
        while(x==y)x=rand()%(n-1)+2;
        swap(c[x],c[y]);
        LL m=en(),dt=ans-m;
        if(dt>0){
            ans=m;
        }else if((double)rand()>=(double)RAND_MAX*(double)exp((double)dt/t)){
            swap(c[x],c[y]);
        }
        t*=dw;
    }
}
int main(){
    srand((unsigned)time(0));
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        c[i]=a[i]-a[i-1];
    }
    sort(c+2,c+n/2+1,cmp);
    sort(c+n/2+1,c+n+1);
    ans=en();
    while(1)sa();
}

 

上一篇:探究struct中每个类型内存容量的大小及总内存大小的关系


下一篇:kubernetes环境宿主机异常关机导致重新部署harbor失败解决案例