企业网站推广网站,注册qq空间网站,中国建设劳动学会监制网站,制作app需要学什么模拟退火算法(simulated annealing#xff0c;SA)是20世纪80年代初期发展起来的一种求解大规模组合优化问题的随机性方法。它以优化问题的求解与物理系统退火过程的相似性为基础#xff0c;利用Metropolis算法并适当地控制温度的下降过程实现模拟退火#xff0c;从而达到求解…
模拟退火算法(simulated annealingSA)是20世纪80年代初期发展起来的一种求解大规模组合优化问题的随机性方法。它以优化问题的求解与物理系统退火过程的相似性为基础利用Metropolis算法并适当地控制温度的下降过程实现模拟退火从而达到求解全局优化问题的目的。
它具有适用范围广 ,求得全局最优解的可靠性高 ,算法简单 ,便于实现等优点。模拟退火算法在搜索策略上与传统的随机搜索方法不同 ,它不仅引入了适当的随机因素 ,而且还引入了物理系统退火过程的自然机理。 这种自然机理的引入使模拟退火算法在迭代过程中不仅接受使目标函数值变“好”的试探点 ,而且还能够以一定的概率接受使目标函数值变“差”的试探点,接受概度随着温度的下降逐渐减小。模拟退火算法的这种搜索策略有利于避免搜索过程因陷入局部最优解而无法自拨的弊端 ,有利于提高求得全局最优解的可靠性。
本文将对模拟退火算法原理进行讲解并给出其代码实现。
00 文章目录 1 模拟退火算法原理 2 问题导入 3 MATLAB程序实现 4 展望
01 模拟退火算法原理 模拟退火算法最早由 Kirkpatrick 等应用于组合优化领域它是基于蒙特卡罗迭代求解策略的一种随机寻优算法它借鉴了物理上金属退火的原理即将热力学的理论套用到统计学上其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
SA算法的基本思想是从选定的初始解开始在借助于控制参数t递减时产生的一系列Markov链中利用一个新解产生装置和接受准则重复进行“产生新解 一计算目标函数差一判断是否接受新解一接受或舍弃新解”不断对当前解迭代从而使目标函数最优的执行过程。由于固体退火必须缓慢降温才能使固体在每一温度下都达到热平衡最终趋于平衡状态。因此控制参数t的值必须缓慢衰减才能确保模拟退火算法最终趋于优化问题的整体最优解。 模拟退火算法结合概率突跳特性在解空间中随机寻找目标函数的全局最优解即局部最优解能概率性地跳出并最终趋于全局最优。模拟退火算法是一种通用的优化算法理论上算法具有概率的全局优化性能。 其求解步骤如下: (1) 从可行解空间中任选一初始状态x0计算其目标函数值f(x0)并选择初始控制温度T0和马尔可夫链的长度 (2) 在可行解空间中产生一个随机扰动用状态产生函数产生一个新状态x1计算其目标函数值f(x1) (3) 根据状态接受函数判断是否接受如果f(x1)f(x0)则接受新状态x1为当前状态否则按Metropolis准则判断是否接受x1若接受则令当前状态等于x1若不接受则令当前状态等于x0 (4) 根据某个收敛准则判断抽样过程中是否终止是则转5否则转2 (5) 按照某个温度冷却方案降低控制温度T (6) 根据某个收敛准则判断退火是否终止是则转7否则转2 (7) 当前解作为最优解输出
02 问题导入 引入一个多峰的非线性函数来验证SA算法的性能函数如下
其图像如下
其极限位置是在(0,0)附近取得极大值极大值为1.0054
03 MATLAB程序实现 按照算法的求解步骤其部分主程序如下
完整程序可在评论区或私信我你的邮箱我看到了会发你
执行程序后得到如下结果 由于模拟退火的迭代机制与前面介绍过的算法不同因此通常模拟退火算法迭代次数是很大的但由于它的比较方式是两两比较因此迭代速度是很快的。
04 展望 4.1 传统模拟退火算法局限性 虽然模拟退火算法存在有限度地接受劣解、可以跳出局部最优解、原理简单、使用灵活、适合求解出优化问题的全局最优或近似全局最优解等优点但它明显地存在以下缺点 (1)求解时间太长。在变量多、目标函数复杂时 为了得到一个好的近似解控制参数T需要从一个较大的值开始并在每一个温度值T下执行多次 Metropolis算法因此迭代运算速度慢。 (2)温度T的初值和减小步长较难确定。如果T的初值选择较大减小步长太小虽然最终能得到较好的解但算法收敛速度太慢如果T的初值选择较小 减小步长过大很可能得不到全局最优解。 (3)搜索过程中由于执行概率接受环节而遗失当前遇到的最优解。 4.2 模拟退火算法改进[1] 模拟退火算法理论上是用一个马尔科夫链描述模拟退火算法的变化过程因此具有全局最优性。实际应用中的模拟退火算法是一个启发式算法。它有诸多的参数需要调整如起始温度温度下降的方案、固定温度式的迭代 长度及终止规则等这样就需要人为地调整。
在确保一定要求的优化质量基础上提高模拟退火算法的搜索效率(时间性能)是对SA算法进行改进的主要内容。可行的方案包括 (1)增加升温或重升温过程。在算法进程的适当时机将温度适当提高从而可激活各状态的接受概率以调整搜索进程中的当前状态避免算法在局部极小解处停滞不前。 (2)增加记忆功能。为避免搜索过程中由于执行概率接受环节而遗失当前遇到的最优解可通过增加存储环节将“Best So Far”的状态记忆下来。 (3)增加补充搜索过程。即在退火过程结束后以搜索到的最优解为初始状态再次执行模拟退火过程或局部趋化性搜索。 (4)对每一当前状态采用多次搜索策略以概率接受区域内的最优状态而非标准SA的单次比较方 式。 (5)结合其他搜索机制的算法如遗传算法、混沌搜索等。
参考文献 [1]朱颢东,钟勇.一种改进的模拟退火算法[J].计算机技术与发展,2009,19(06):32-35.
另如果有伙伴有待解决的优化问题各种领域都可可以发我我会选择性的更新利用优化算法解决这些问题的文章。
如果这篇文章对你有帮助或启发可以点击右下角的赞(ง •̀_•́)ง(不点也行)若有定制需求可私信作者。
