零基础学启发式算法(4)-模拟退火 (Simulated Annealing)
2022/2/23 20:53:02
本文主要是介绍零基础学启发式算法(4)-模拟退火 (Simulated Annealing),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
一、模拟退火 (Simulated Annealing)
模拟退火 (Simulated Annealing) 其实是一种贪心算法,但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率来接受一个比当前解要差的解,因此有可能会跳出这个局部的最优解,达到全局的最优解。
模拟退火算法源自于对热力学中退火过程的模拟,在给定一个初始温度下,通过不断降低温度,使得算法能够在多项式时间内得到一个近似最优解。
二、模拟退火算法的步骤描述如下:
对于一个优化问题 min f(x),
-
给定一个初始可行解 x0,初始温度 T0 和终止温度 Tf,令迭代计数为 k。
-
随机选取一个邻域解 xk,计算目标函数增量 Δf=f(xk)−f(x)。
若 Δf<0,则令 x=xk;
否则生成随机数 ξ=U(0,1),若随机数小于转移概率 P(Δf,T),则令 x=xk。
-
降低温度 T。
-
若达到最大迭代次数 kmax 或最低温度 Tf,则停止算法
否则转至步骤 2。
整个算法的伪代码如下:
流程图
在进行邻域搜索的过程中,当温度较高时,搜索的空间较大,反之搜索的空间较小。
类似的,当 Δf>0 时,转移概率的设置也同当前温度的大小成正比。
三、常用的降温函数有两种:
-
Tk+1=Tk∗r,其中 r∈(0.95,0.99),r 设置的越大,温度下降越快。
-
Tk+1=Tk−ΔT,其中 ΔT 为每一步温度的减少量。
https://leovan.me/cn/2019/04/heuristic-algorithms/
https://www.sohu.com/a/161813051_206216
https://blog.csdn.net/weixin_42398658/article/details/84031235
这篇关于零基础学启发式算法(4)-模拟退火 (Simulated Annealing)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南