原创

模拟退火算法

模拟退火

首先看一下度娘的定义

模拟退火算法(Simulate Anneal,SA)是一种通用概率演算法,用来在一个大的搜寻空间内找寻命题的最优解

模拟退火是一种非常好用的随机化算法,它是爬山算法的改进版

爬山算法的思想就是一个劲的找最优解,如果接下来的任何状态都比当前状态差,那么就停止

但是这样显然是错误的,比如下面这种情况

爬山找到A点之后就GG了,但是模拟退火算法会以一定的概率走向F,进而走向B,找到更优的解

至于这里为什么叫做“退火”,还要从物理学说起

在热力学上,退火(annealing)现象指物体逐渐降温的物理现象,温度愈低,物体的能量状态会低;够低后,液体开始冷凝与结晶,在结晶状态时,系统的能量状态最低。大自然在缓慢降温(亦即,退火)时,可“找到”最低能量状态:结晶。但是,如果过程过急过快,快速降温(亦称「淬炼」,quenching)时,会导致不是最低能态的非晶形。

这里的最低能量状态,也就是我们题目中的最优解

实现

因为要模拟退火的过程,因此我们先定义一些变量

T:当前温度,由高温到低温,代表算法进行到了什么程度,一般为double类型

\Delta T:每次温度的变化率,一般取0.95 - 0.99,模拟缓慢降温的过程(上一次的温度乘温度变换率即为这一次的温度)

f(x) 当前状态对应的值

上面我们提到,模拟退火会以一定的概率转移到比当前差的解,那么这个概率是多少呢?科学家经过分析,当这个概率为e^{\frac{\Delta f}{T}}时最优

那么根据退火的过程,我们不难得到模拟退火的算法流程

  1. 枚举温度T
  2. 计算出下一步的状态
  3. 若下一步的状态比当前状态优或者满足进行转移的条件,进行转移
  4. 降温

因为模拟退火算法具有偶然性,因此我们一般需要对一个问题进行多次模拟退火算法

至于温度的设定,以及执行算法次数的确定,这个需要看rp依题目而定

听说模拟退火在计算几何中有非常重要的应用,但是本蒟蒻现在连叉积都不会,所以这一块等以后再补吧

题目

两道很水不错的题目

洛谷P1337

题解

洛谷P2503

题解

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 模拟退火算法

    attack
  • 线性筛莫比乌斯函数

    1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cmath...

    attack
  • 洛谷P2852 [USACO06DEC]牛奶模式Milk Patterns

    题目描述 Farmer John has noticed that the quality of milk given by his cows varies f...

    attack
  • 模拟退火算法

    attack
  • 比较13种算法在165个数据集上的表现,你猜哪个最好?

    量化投资与机器学习微信公众号
  • java设计模式之状态模式,策略模式的孪生兄弟

    状态模式(State Pattern)中,类的行为是基于它的状态改变的,状态之间的切换,在状态A执行完毕后自己控制状态指向状态B,状态模式是不停的切换状态执行,...

    用户4361942
  • Flink 状态管理与 Checkpoint 机制

    相对于其他流计算框架,Flink 一个比较重要的特性就是其支持有状态计算。即你可以将中间的计算结果进行保存,并提供给后续的计算使用:

    zhisheng
  • 初学者该使用哪一种算法?

    导语:初学者都很疑惑,在这么多算法当中,到底到一个算法才能很好的解决自己所遇到的问题呢?这事实上取决于很多种因素。 ? 首先是数据的大小和质量 可用的计算时间...

    IT派
  • 荐读|初学者如何选择合适的机器学习算法

    文主要的目标读者是机器学习爱好者或数据科学的初学者,以及对学习和应用机器学习算法解决实际问题抱有浓厚兴趣的读者。 面对大量的机器学习算法,初学者通常会问自己一...

    灯塔大数据
  • 教程 | 初学者如何选择合适的机器学习算法(附速查表)

    选自sas 机器之心编译 参与:黄小天、蒋思源、吴攀 本文主要的目标读者是机器学习爱好者或数据科学的初学者,以及对学习和应用机器学习算法解决实际问题抱有浓厚兴趣...

    机器之心

扫码关注云+社区

领取腾讯云代金券