模拟退火算法

模拟退火

首先看一下度娘的定义

模拟退火算法(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

题解

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏程序人生 阅读快乐

[C数值算法]

本书编写了300多个实用而有效的数值算法C语言程序。其内容包括:线性方程组的求解,逆矩阵和行列式计算,多项式和有理函数的内插与外推,函数的积分和估值,特殊函数的...

6420
来自专栏互联网大杂烩

最优化模型 数据挖掘之优化模型

最短路径问题、网络最大流问题、最小费用最大流问题、最小生成树问题(MST)、旅行商问题(TSP)、图的着色问题。

14120
来自专栏机器人网

七步之内成为Python机器学习的大师

线上的Python的机器学习资源如此丰富,从哪开始?如何修炼?这篇文章让你从零开始,七步之内成为Python机器学习的大师。

13110
来自专栏AI2ML人工智能to机器学习

哈密尔顿,不变的爱

前面我们提到两大变( “变分の美” 和 “Legendre变变变” ), 那么一直在变的话,什么时候不再变呢? 这就是我们今天想概述的。 所谓物极必反, 又所...

18120
来自专栏AI科技评论

苹果机器学习开发日记:如何设计能在Apple Watch上实时运行的中文手写识别系统

AI 科技评论按:随着苹果机器学习日记(Apple ML Journal)的开放,苹果分享出的设计自己产品、运用机器学习解决问题的故事也越来越多。近日苹果在上面...

403110
来自专栏新智元

【ACL2016 终极盘点】终身成就奖得主:我还没玩深度学习

【新智元导读】在德国柏林召开的计算机语言顶级会议ACL2016将于当地时间明天(8月12日)闭幕。今天,大会公布了最佳论文,一篇关于词态学的论文获此殊荣。此外,...

36270
来自专栏新智元

【吐血整理】台湾大学李宏毅深度强化学习笔记(49PPT)

【新智元导读】来自台湾超受欢迎的李宏毅老师深层强化学习49页PPT以及笔记,熬夜整理,值得收藏。本文授权转载自Medium,作者Ivan Lee。

38630
来自专栏量子位

AI研发新药真有那么神?可能哈佛、斯坦福和阿斯利康实验室都在吹牛

安妮 李林 编译自 Medium 量子位 出品 | 公众号 QbitAI ? 近年来,向往着用AI研发新药的美好愿景,巨头纷纷投下了重注。 制药巨头赛诺菲和AI...

37870
来自专栏数说工作室

异常值检测

之前发过一篇讨论文章——异常值怎么整。 在原文评论区里(戳此→异常值怎么整?| 讨论)得到了各位大大的指教,数说君也受益匪浅,现在整理一下供大家参考: 聚类 ...

35850
来自专栏AI科技大本营的专栏

探索 | 神经网络到底是如何思考的?MIT精英们做了这么一个实验室来搞清楚

作者 | Larry Hardesty等 编译 | ziqi Zhang 没错!人工智能是很火,神经网络也很火,但你真的懂它吗?神经网络到底是怎么工作的?没有...

34090

扫码关注云+社区

领取腾讯云代金券