第20卷第2期2005年6月 柳 州 师 专 学 报JournalofLiuzhouTeachersCollegeVol.20No.2June2005
一种有效的全局优化算法———模拟退火算法
汪灵枝,周优军
(柳州师范高等专科学校数学与计算机科学系,广西柳州,545004)
摘 要:模拟退火算法是有效的全局优化算法,本文讨论了模拟退火算法发展过程及其理论依据,利用MAT2
LAB语言编写程序并测试分析,认为算法本身可进一步改进,提出了算法改进思路和方法。
关键词:模拟退火算法;全局优化;程序
中图分类号:O224 文献标识码:A 文章编号:1003-7020(2005)02-0120-04
1引言0,,最后系统状,.,,最终趋于平衡状态.因此,控制参数t经缓慢衰减,才能确保模拟退火算法最终优化问题的整体最优解.具体步骤如下[1]:
(1)给定模型每一个参数变化范围,在这个范围内随机
模拟退火(SimulatedAnnealing,简称SA)算法是基于蒙特卡罗(MonteCarlo)法.算法思想最早在1953年由N.S.patrick等人和V..,另辟了组合优化问题的新途径.其出发点是物理学中的退火过程,即在对固体物质进行退火处理时,通常是先将它加温,使其粒子可自由运动,然后降温,粒子逐渐形成低能态的晶体,若在凝结点附近温度下降得足够慢,则固体物质一定会形成最低能量的基态.
退火的概念最初是人们为了研究组合优化问题而提出的,算法用于解决组合优化问题则是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性.通过设定一初温和初态,伴随温度的不断下降,结合概率突跳特性在解空间中通过邻域函数进行随机搜索,最终得到全局最优.模拟退火算法是一种通用的优化算法,目前已在工程中得到了广泛的应用,诸如VLSI、生产调度、控制工程、机器学习、神经网络、图象处理等领域.
2算法基本原理和程序实现2.1基本原理
选择一个初始模型m0,并计算相应的目标函数值E(m0).
(2)对当前模型进行扰动产生一个新模型m,计算相应
的目标函数值E(m),得到
△E=E(m)-E(m0).
(1)
(3)若△E<0,则新模型m被接受;若△E>0,则新模型m按概率P=exp(-△E/T)进行接受,T为温度.当模型被
接受时,置m0=m,E(m0)-E(m).
(4)在温度T下,重复一定次数的扰动和接收过程,即重(3).复步骤(2)、
(5)缓慢降低温度T.
(6)重复步骤(2)、(5),直至收敛条件满足为止.SA算法实质上分两次循环,随机扰动产生新模型并计
算目标函数(或称能量)的变化;决定新模型是否被接受.由于算法初温设计在高温条件,这使得E增大的模型可能被接受,因而能舍去局部极小值,通过缓慢地降低温度,算法最终能收敛到全局最优点.
从上述步骤可看出模拟退火算法依据Metropolis准则接受新解,为此除了接受优化解外,还在一定限度内接受恶化解,这正是SA算法与局部搜索算法的本质区别所在.开始时候值大,可能接受较差的恶化解;随着t的减小,则只能接受好的恶化解;最后在t值趋于零时,就不再接受恶化解了,从而使得SA能从局部最优的“陷阱”中跳出,最后得到全局最
模拟退火算法的基本思想是从一给定解开始,从邻域中随机产生另一个解,接受Metropolis准则允许目标函数在有限范围内变坏,它由一控制参数t决定,其作用类似于物理过程中的温度T,对于控制参数的每一取值,算法持续进行“产生—判断—接受或舍弃”的迭代过程,对应着固体在某一恒定温度下趋于热平衡的过程.经过大量的解变换后,可以求得给定控制参数t值时优化问题的相对最优解.然后减小控制参数t的值,重复执行上述迭代过程,当控制参数逐渐
收稿日期:2005-03-23
作者简介:汪灵枝(1974—),男,广西象州人,讲师,研究方向:启发式算法;周优军(1974—),男,广西全州人,讲师。
12

2 June 2005 一种有效的全局优化算法 ) ) ) 模拟退火算法汪灵枝, 周优军 (柳州师范高等专科学校 数学与计算机科学系, 广西 柳州, 545004) 摘要: 模拟退火算法...
一种有效的全局优化算法_模拟退火算法_汪灵枝 暂无评价
数值计算结果表明, 采用新的温度更新函数及相应的概率密 度函数的模拟退火算法可以进一步提高求解全局优化问题的计算效率, 是一种高效的模拟退火全局优化 算法。 2 ...
模拟退火算法是目前发展较快的智能优化算法,是一种以概率l收敛于全局最优解的全局优化算法。文中讨论了全局查询优化的过程以及模拟退火算法在全局查询优化中的应用,并...
初始解状态 S(是算法迭代的 起点)无关; 模拟退火算法具有渐近收敛性, 已在理论上被证明是一种以概率 l 收 敛于全局最优解的全局优化算法;模拟退火算法具有...
[键入文字] [键入文字] 模拟退火算法摘要:本文采用一种模拟退火算法(SAA) ,...[3] 杨若黎,顾基发.一种高效的模拟退火全局优化算法.系统工程理论与实践[J]...
混沌模拟退火算法,数值实验表明算法是有效的,同时阐述了混沌模拟退火算法有效性的...且求解的优化问题规模相对较小.目前 还没有一种广泛适用的确定性全局优化算法,...
,它是近年来提出的一种适合于解决大规模组合优化问题的通用而有效的近似算法。...模拟退火算法具有渐近收敛性,已在理论上被证明是一种以概率l 收敛于全局最优解...
优化算法-模拟退火算法_数学_自然科学_专业资料。包含两个优化算法,爬山算法,...接受一个比当前解要差的 解,因此有可能会跳出这个局部的最优解,达到全局的最...
模拟退火算法是近年发展起来的全局最优化 算法, 其主要优点是; 不用求目标函数的偏导数及 解大型矩阵方程组, 即能找到一个全局最优解, 而 且易于加入约束条件,...
热门文档