模拟退火算法(simulated annealing,SA)

2022-10-08 13:39:43 浏览:588

定义

模拟退火算法(simulated annealing,SA),最早是由Metropolis受退火工艺启发所提出的,它是一种基于Monte Carlo迭代求解策略的随机寻优算法。它可以使系统有可能从局部最小处跳出,即能克服优化过程陷人局部极小;或者使系统克服初值依赖性。而算法的灵感来源于“退火工艺”,金属退火工艺的过程分为三步,分别是:加温、等温及冷却。整个退火过程是首先给金属加热到一定高温,使之打破原来的分子排布状态而处于随机分布的状态;持续这个状态一段时间后,系统会发生轻微的变化;然后随着对温度的缓慢降低,系统的分子排布状态逐渐会趋于平稳的状态,最终就会得到结构较的金属晶体,另外如果降温速度过快,淬火现象就会产生,那么得到的金属晶体就会出现结构缺陷。 由于金属退火工艺与常见的优化问题之间存在异曲同工之处,所以近年来该算法在某些常见的组合优化问题都有使用,该算法相对于其他优化算法具有更大的优点。模拟退火方法以Metropolis概率准则,在可行解的空间内进行随机搜索,反复抽样比较两次评价函数的差值从而决定是否保留新的解,进而得到全局最优。其中模拟退火算法的关键在于Metropolis准则,该准则是以一定的概率接收一些使结果变差的边沿状态,从而能够跳出局部最优。模拟退火算法相对于其他优化算法,对于目标函数的要求并非苛刻,能够在较大的概率下求得最优解,同时陷入局部最优解的概率低。对于连续型变量或者离散型变量均适用,同时对于目标函数和限制条件并没有任何要求。

原理

其算法流程图如图所示。

模拟退火算法(simulated annealing,SA)
当系统处于状态 xold 时,由于受到外界影响产生扰动后,其状态变为 xnew ,而系统的 目标函数也会从 f xold 变成 f xnew  ,系统由状态 xold 变为状态 xnew 的接受概率 P:

模拟退火算法(simulated annealing,SA)

如果两个目标函数的差值f  0 ,则接收 xnew 的状态为当前状态;如果两个目标函数的差值f <0,则根据 Metropolis 准则以概率接收一些使结果变差的边沿状态,判断是否接收xnew 的状态为当前状态。产生一个在(0~1)的均匀分布的随机数q ,比较根据 Metropolis 准则,即公式(4.1)所计算的随机数 p 和q 的大小,根据两者值进行下一步状态的运行处理:当 p  q时,接收 xnew 的状态为当前状态;否则继续保留状态 xold 为当前状态;p和随机数q 多次进行比较和状态迁移后,就达到了当前温度的平衡状态;然后继续降低温度,寻找每个当前温度下的平衡状态;重复上述过程,即使得最终“退火”的温度接近零摄氏度,这也就是跳出局部极值获得最大值的过程。

参考文献

[1] 卢宇婷, 林禹攸, 彭乔姿,等. 模拟退火算法改进综述及参数探究[J]. 大学数学, 2015,31(6):96-103.
[2] Metropolis N, Rosenbluth A W, Rosenbluth M N, et al. Equation of State Calculations by Fast Computing Machines[J]. Journal of Chemical Physics, 1953, 21(6):1087-1092.
[3] 李树有, 都志辉, 吴梦月,等. 模拟退火算法的并行实现及其应用[J]. 物理学报, 2001,50(7):1260-1263.
[4] 魏延, 谢开贵. 模拟退火算法[J]. 红河学院学报, 1999(4):7-11
[5] 罗静. 空间光耦合自动对准技术研究[D]. 陕西:西安理工大学,2018.

基础光学

作          者: 泮桥成像光电商城

出          处: https://www.ipanqiao.com/entry/978

版          权:本文版权归泮桥成像光电商城所有

免责声明:本文中使用的部分文字内容与图片来自于网络,如有侵权,请联系作者进行删除。

转          载:欢迎转载,但必须保留上述声明;必须在文章中给出原文链接;否则必究法律责任。

Copyright © 2019-2022 南京超维景生物科技有限公司 版权所有 www.ipanqiao.com苏ICP备20009590号-1
联系我们
立即做合同
微信客服
电话咨询

400-998-9826

17302548620

快速留言

泮桥成像光电商城专业人员会在24小时之内联系您

关闭 提交