一种有效的全局优化算法_模拟退火算法
第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)若△E0,则新模型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.2程序实现与测试
退火计算过程中具体参数设置为:初始温度T0=100000,终止温度T1=1,退火过程为指数形式Tn-1=0.9Tn,在相同温度下重复计算100、300次计算结果如图1和2.
从图1和图2的结果可以看出,在模拟退火优化过程中,其最终搜寻到最优解f(0,0)=0,内循环次数在很大程度上影响其寻优时间,100次循环在90秒时达到最优,而内循环300次时在60秒达到最优,这也正是模拟退火算法中Me2
tropolis抽样准则的体现,内循环较多时,在相同温度下最后
根据上述计算步骤,针对优化测试函数
222
minf(x1,x
2)=100(x1-x2)+(1-x1),
利用软件MATLAB编写模拟退火计算程序,计算程序如下:
X1=[1.01.0]whileT>T1
fort=1:k
vare1=1003(x1(1)3x1(1)-x1(2)).^2+(1-x1
(1)).^2;
迭代较容易达到Markov平稳链,结果也容易收敛到最优解.
为充分比较算法的有效性,本文将其重复1000次运行,其每次运行结果如图3,从图3可以看出,它的绝大多数结果都将趋于函数最优解0,但也有一部分结果出现振荡且与最优结果的差距较大,这说明模拟退火算法的结果有时会出现恶化,影响收敛到最优解
.
x2(1)=x1(1)+0.23(rand-0.5); x2(2)=x1(2)+0.23(rand-0.5);
vare2=1003(x2(1)3x2(1)-x2(2)).^2+(1-x2
(1)).^2;
if(vare2-vare1)
elseifexp((vare1-vare2)/T)>rand x1=x2; end
ret(t,N)=(1)x11)-(2)).^2+(1
-x1(1)).^2;
end
se(N,:)=x1;N=N+1;T=a3T;
end
图3 模拟退火算法1000运行结果
3算法不足与发展
模拟退火算法具有很强的全局优化搜索能力,不受搜索空间的限制假设约束,不要求具备连续性、可导性或单峰等假设,算法不但可往好的方向走,也可往差的方向走,即能以一定的概率接受目标函数值不太好的状态,这使得算法即便落入局部最优的陷阱中,理论上经过足够长的时间后也可跳出来,从而收敛到全局最优解.这意味着,算法形成足够高的初始温度,缓慢的退火速度,大量的迭代次数及同一温度下
图1 循环100
次优化结果
足够的扰动次数.由此可看到,算法的不足也是很明显的.它主要缺点就是解的质量与求解时间长之间的矛盾.为得到一个好的近似最优解,需要进行反复迭代运算,当问题的规模不可避免地增大时,缺乏可行的解决途经.因此,SA的效率问题一直是算法真正走向实用的最大障碍.
针对算法的“先天性不足”,在确保一定要求的优化质量基础上,改进和发展传统模拟退火算法,克服其计算时间长、效果较低的缺点,成为众人关注的热点问题.目前研究的方向大致有三类:
3.1改进、升级SA算法
图2 循环300次优化结果
模拟退火算法关键参数主要有状态产生函数、状态接受函数、初温、温度更新函数等.改进算法主要就是调试、改进其中某部分函数,使其更接近自然现象,现大致归纳为三个
121
第20卷第2期
方面:
(1)改进状态产生函数
柳 州 师 专 学 报2005年6
月
法;黄临平、管志宁[13]采用改进的SA算法,利用Merropolis试验方法安排模型的转移,借助于SM的模型搜索规则,有效将SA和下降SM结合起来,提出了应用局部方法的最佳时机等.
(3)模拟退火算法和神经网络(ANN)、混沌算法(CS)结
[2]
Ingber采用依赖温度的似Cauchy分布来代替常规模
拟退火方法中的高斯分布,提出了非常快速模拟退火算法
(VFSA).由于似Cauchy分布有一平坦的“尾巴”,使其易于
迅速跳出局部极值,加快了SA算法的收敛速度;陈华根等[3]进一步将VFSA的退火温度和模型扰动方式进行改进,提出了改进的VFSA,简称MVFSA.
(2)改进状态接受函数
Bohachevsky将接受概率修改成:
g
P=min{1,exp(-βE△E)},
合
严又生[14]利用广义模拟退火算法(GSA)能将非线性多极值目标函数较快收敛于全局极值的特点,替换人工神经元网络学习过程中基于梯度下降原理的误差反向传播算法(算法),该方法将由神经元网络的学习输出与期望输出之差的平方和构成的目标函数视为一整体能量系统,模拟物理学金属退火处理过程,调整网络中的连接权,使得系统的能量尽可能收敛到全局极小;杨龙等[15]将BP网络与SA结合来克服神经网络陷于局部极小的缺点;Carlos等[16]将BP算法与
VFSA结合,VFSA;王凌等
[17]
[4]
提出了广义模拟退火算法(GSA);Tallies[5]给出了广义Boltz2
mann2Gibbs统计理论及相应的Gibbs分布.基于这一理论,Pena提出新的模拟退火方法,即由广义Gibbs分布给出新
[6]
的接收概率计算表达式,这种方法在较高的温度就能收敛到全局极值,具有较高的计算效率.
(3)改进温度更新函数Basu等
[7]
(ACNN)模型,
,利用其遍历性在解空
,,再由退火策略控制混沌动态逐渐消失并产生逆分岔,一旦逆分岔过程结束便转入HNN极度优化;邹恩等[18]提出混沌模拟退火算法,将CS和SA结合学习模糊神经网络的结构和参数,首先将混沌变量引入模糊神经网络参数的优化计算中,利用混沌变量的遍历性寻优,根据性能指标寻找较优的模糊神经网络控制器,然后再混沌优化确定的网络基础上,把经混沌搜索后得到的全局次优解作为模拟退火学习算法的初始值,再用模拟退火方法进一步学习网络的隶属函数和权值参数,找到一个全局最优的网络.
3.3混合最优化算法
临界温度开始,.
此外,,例如增加记忆功能,,增加搜索策略等.
3.2结合其它算法,混合优化SA算法
工程的全局优化问题存在大规模、高维、非线性、非凸等复杂性,而且存在大量局部极小.单一结构和机制的算法一般难以实现高效优化.有机结合单纯形(SM)、遗传(GA)、进化(EC)、人工神经网络(ANN)等算法,混合发展SA算法,既符合自然界对立和统一的本质,又能有效地提高计算效率,取得理想的效果.
(1)模拟退火算法和进化算法,特别是和遗传算法的结
混合最优化算法是以模拟退火算法和遗传算法作为其基础,将不同算法在优化机制、进程、搜索行为、操作上进行有机结合,达到全局最优.作为近年来发展起来的数据处理方法,它综合了局部最优化算法和全局最优化算法的优点,有效克服了它们的缺点,不仅在可以提高计算速度,而且在改善解的质量方面有着很好的效果.
目前,混合最优化算法是信号处理、自动控制、模式识别以及地球物理数据处理的研究热点,正得到越来越广泛的应用.基于模拟退火算法的混合最优化算法目前主要有这几种组合形式:模拟退火算法与线性化方法结合、模拟退火算法与共轭梯度结合、模拟退火算法与单纯形法和均匀设计结合、模拟退火算法与人工智能神经网络结合等.
4结论
合
80年代末,人们开始将注意力投向SA和GA的结合,较
典型的有:SirangD.J.和WeisserD.J.的“面向一致化热动态
)[8],Bo2算子”(“To2wardaunifiedthermodynamicoperator”sesniukT.和EbelingW.的“玻尔兹曼、达尔文和黑格尔策略(用于优化问题”“Boltzmann2DarwinandHeackel2strategiesin)optimizationproblems”
[9]
,GoldbergD.E.和MahfoudS.W.等
人的并行再生模拟退火算法(PRSA)[10];王凌等等和张讲社等分别提出了GASA混合策略克服了收敛缓慢和易早熟的缺点,在文献[1]中王凌对GASA算法的设计和应用做了详细的探讨.
(2)模拟退火算法和单纯形法及均匀设计方法结合
模拟退火算法作为一种有效的全局优化算法,正以其思路清晰、原理简单、使用灵活得到广泛地应用.随着全局优化技术不断发展,新的优化机制、技术和方法不断涌现,作为基础算法的模拟退火算法亦可充分发挥其串行优势,自身不断改进的同时不断与新的优秀算法结合,得出更合理、有效的混合优化算法.
纪晨等[11]将均匀设计、SA、SM相结合提出了一种全局优化迭代算法;艾双印等[12]利用单纯形的3个步骤(反映、扩展和压缩)加上自适应的随机扰动来形成中间模型和新模型,选择由Rothman建议的退火规则,模型接受概率选用
Laarhoven等建议的接受概率,得到了一种很有效的反演方
122
汪灵枝,周优军:一种有效的全局优化算法———
模拟退火算法
参考文献:
[1]王凌.智能优化算法及其应用[M].北京:清华大学出版社,2001:19—21.
[2]IngberL..Veryfastsimulatedreanimating[J].Mathcomputemodeling,1989,(12):967—973.[3]陈华根等.模拟退火算法机理研究[J].同济大学学报(自然科学版),2004,32(6):802—804.
[4]IhorO.Bohachevskyal.Generalizedannealingforfunctionoptimization[J].Technometrics,1986,(28):209—217.[5]TsallisC..PossiblegeneralizationofBoltzmann2Gibbsstatistics[J].J.statphy,1988,(52):479—487.[6]PennaT.J.P..TravelingsalesmanproblemandTallishstatistics[J].PhysReve,1995,(51):R1—R3.
[7]BasuA.,FrazerL..Rapiddeterminationofthecriticaltemperatureinsimulatedannealinginversion[J].Science,1990,(249):1409—1412.[8]SiragD.J,WeisserD.J..Towardunifiedthermodynamicgeneticoperator[J].ProcintConfonGeneticAlgorithmsandTheirApplications,ErbumAssocination,Hillsdale,N.J.,1987:208,941—943.
[9]BoseniukT.,EbelingW..Boltzmann2Darwin2andHeackel2strategicsinoptimizationproblems[J].ProcintConfinparallelproblemsolvingfromnature,NewYork,1990:245,1010—1012.
[10]MahfoudS.W.,GolbergD.E..AGeneticAlgorithmforparallelsimulatedannealing[J].ProcintConfinparallelproblemsolvingfromnature,Netherland,1992:260,1511—1514.
[11]纪晨,姚振兴.用于地球物理反演的均匀设计优化算法[J].地球物理学报,1996,39(2):234—241.[12]艾印双,刘鹏程,郑天愉.自适应全局混合反演[J].中国科学(D辑),1998,28(2)105—110.[13]黄临平,管志宁.重磁位场综合优化解释方法研究及其应用[J].,1999,(4):[14]严又生.基于广义模拟退火算法的人工神经网络学习算法[J].,1996,31(4):[15]杨龙,杜亚军.BP].25(:97106.
[16]CarlosCalder,OrrMacias,Mrinal.Sen,offa.Anetworksforparameterestimationingeophysics[J].CeophysicalPros2pecting,2000,(48):21—[17]王凌,郑大钟.[J].控制理论与应用,2000,17(1):139—142.
[18]邹恩等.———混沌模拟退火学习法[J].中南大学学报(自然科学版),2004,35(3):444—446.
(责任编辑:梁文杰)
SimulatedAnnealingAlgorithm:AValidGlobalOptimizationAlgorithm
WANGLing2zhi,ZHOUYou2jun
(DepartmentofMathematicsandComputerScience,LiuzhouTeachersCollege,Liuzhou,Guangxi545004,China)
Abstract:SimulatedAnnealingAlgorithmisakindofvalidglobaloptimizationAlgorithm.MakinguseoftheMATLABlanguageplaitwritestheprocedurecombinestestanalysis,theauthorsdiscussthedevelopment,theoryfoundation,andtheythinkthecalculationcanstillbefurtherimproved,andputforwardsomeimprovementinthethinkingandthesolution.
Keywords:SimulatedAnnealingAlgorithm;globaloptimization;program
123