hi,你好!欢迎访问本站!登录
本站由网站地图腾讯云宝塔系统阿里云强势驱动
当前位置:首页 - 教程 - 杂谈 - 正文 君子好学,自强不息!

[随机化算法] 听其自然?浅谈Simulate Anneal模拟退火算法

2019-11-18杂谈搜奇网28°c
A+ A-

Simulate Anneal模仿退火算法,是一种用于获得最优解的随机化算法。

假如能够打一手美丽的随机化搜刮,或许当你面临束手无策的仙人题时就有一把趁手的武器了。

这篇题解将教你什么?SA的基础思路,什么时刻能用SA。

题目是浅谈,所以本篇博客参杂了些许个人简介,如有疑问或贰言,迎接提出斧正。

我也很谢谢你们给出的发起,它们真的能让我变好、变强。

那末我们进入本篇正题。

 

1. 什么是模仿退火:

模仿退火是一种在宽大的搜刮空间寻觅最优解的随机化算法。我们看名字就邃晓,这个算法着实模仿物理中退火的历程。学问许多时刻都是相通的,我们进修的大部份学问都是有效的。

为何经由过程模仿退火的历程能够得出最优解呢?在物理中,固体物资的退火历程和平常的组合优化题目有着很高的相似度。

 

2. 模仿退火基础要素:

满足这些你就能够将SA算法愉快地嵌入你的顺序里了。

第一个要素就是状况空间和状况的发生函数,我们须要有一个搜刮空间,而且局限较大。

什么是搜刮空间呢?我们进修搜刮的时刻应当打仗过,我们的搜刮算法实质就是在题目的求解空间中举行遍历,寻觅最优解。模仿退火的状况空间也相似,它就是我们自定义出来的最优解的有限鸠合。

我们光有状况空间还不够啊,我们真正须要的是状况。学函数的时刻,先生就说过了,一个函数要有“域”。我们的状况空间就是状况发生函数的“域”。而我们假如想写一个好的退火,我们的搜刮空间要充足大,充足让函数生成差别的新解。

第二个就是候选解,我们在状况空间内经由过程生成的随机数在肯定密度内随机挑选我们的候选解。

实在另有一条是几率散布,大部份采纳匀称散布,少数状况我们会用到指数散布。

至于状况转移几率,我现在打仗到的SA算法一切采纳了Metropolis原则,我接下来会引见它。

 

3. 模仿退火基础流程:

一. 由一个状况发生函数从当前解发生一个新解,平常采纳增量组织(即由原解加上/减去发生函数发生的值)来获得。

二. 盘算新解的目的函数差Δt'。

三. 推断新解是不是被接收,

这里引见Metropolis原则:若Δt'<0,我们接收它,不然以exp(-Δt'/T)的多项式几率接收它。

**T是我们模仿退火历程当中的温度**

四. 当新解被接收时,用新解替代当前解,不然继承下一轮实验。

 

4. 模仿退火中的参数掌握:

调参能够说是SA算法最难的部份,也是决议你的算法得分率的部份。

这里分享一下仙人FlashHu(LCT导师Orz)写SA时调参的履历,我总结了一下就是如许:

关于eps,能够依据数据局限和精度请求大略获得eps的也许大小,手动微调能够获得终究的eps。

关于T和ΔT(温度的变化率,平常在0.95-0.99间),先开大一点跑出最优解,然后一边退火一边输出当前的T、ans等信息,大抵感觉解的下落速度,越匀称示意参数越好(仙人称之为观察法)

 

5. 注重事项:

SA能够会堕入当前解卡在部分最小的状况,也就是如许:

图中,赤色是我们的当前解,蓝色是我们的最优解,赤色的线代表SA算法获得的新解,我们会发明,假如参数不佳,我们就有能够涌现卡在部分最优解的状况。自身算法的设想就有防备这一种状况,还记得吗?Metropolis原则,就算这不是最优解,我们也以肯定几率接收它(答案不更新),就是为了防备这类状况,然而在参数不佳的状况下,它仍能够发生。所以我们要革新对温度的掌握体式格局。

这里还是以那道典范到不能再典范的模仿退火模板做例题:平衡点/吊打xxx

这里直接贴上代码,关于算法中须要注重的处所我会打上解释。

#include<bits/stdc++.h>
#define down 0.997//ΔT,模仿冉冉降温 
using namespace std;
inline int read(){
    int data=0,w=1;char ch=0;
    while(ch!='-' && (ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')w=-1,ch=getchar();
    while(ch>='0' && ch<='9')data=data*10+ch-'0',ch=getchar();
    return data*w;
}
int n;
struct point{
    int x,y,w;
}object[2019];//物体信息 
double ansx,ansy,answ;//答案 
double energy(double x,double y){//物理学学问:能量总和越小越稳固 
    double r=0,dx,dy;
    for(int i=1;i<=n;i++){
        dx=x-object[i].x;dy=y-object[i].y;
        r+=sqrt(dx*dx+dy*dy)*object[i].w;//力臂乘重力 
    }
    return r;
}
void SA(){
    double t=3e3+10;//初始温度要高 
    while(t>1e-15){//exp略大于0 
        double ex=ansx+(rand()*2-RAND_MAX)*t;
        double ey=ansy+(rand()*2-RAND_MAX)*t;
        double ew=energy(ex,ey);
        double de=ew-answ;
        if(de<0){//此答案更优 
            ansx=ex;ansy=ey;answ=ew;
        }else if(exp(-de/t)*RAND_MAX>rand()){//Metropolis原则,以多项式几率接收 
            ansx=ex;ansy=ey;
        }t*=down;//逐渐降温 
    }
}
void solve(){
    SA();SA();SA();SA();SA();
}
int main(){
    n=read();
    for(int i=1;i<=n;i++){
        object[i].x=read();object[i].y=read();object[i].w=read();
        ansx+=object[i].x;ansy+=object[i].y;
    }
    ansx/=n;ansy/=n;//设平均值为初值 
    answ=energy(ansx,ansy);
    solve();
    printf("%.3lf %.3lf\n",ansx,ansy);
    return 0;
}

游戏完毕。

  选择打赏方式
微信赞助

打赏

QQ钱包

打赏

支付宝赞助

打赏

  移步手机端
[随机化算法] 听其自然?浅谈Simulate Anneal模拟退火算法

1、打开你手机的二维码扫描APP
2、扫描左则的二维码
3、点击扫描获得的网址
4、可以在手机端阅读此文章
未定义标签

本文来源:搜奇网

本文地址:https://www.sou7.cn/281994.html

关注我们:微信搜索“搜奇网”添加我为好友

版权声明: 本文仅代表作者个人观点,与本站无关。其原创性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容、文字的真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。请记住本站网址https://www.sou7.cn/搜奇网。

发表评论

选填

必填

必填

选填

请拖动滑块解锁
>>