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