© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net第4卷第2期2007年4月 工程地球物理学报CHINESEJOURNALOFENGINEERINGGEOPHYSICSVol14,No12Apr1,2007
文章编号:1672—7940(2007)02—0135—06
模拟退火算法及其改进蒋龙聪,刘江平(中国地质大学地球物理与空间信息学院,武汉430074)
作者简介:蒋龙聪(1983—),男,硕士研究生,现在主要从事地震数据处理和反演理论方法研究。E2mail:longcja@gmail.com
刘江平(1957—),男,教授,博士生导师,主要从事地震勘探的科研与教学工作。E2mail:liujp@cug.edu.cn
摘 要:
借鉴遗传算法中的非均匀变异思想,用非均匀变异策略对当前模型扰动产生新的模型,对传统的模
拟退火算法提出了改进,通过多峰值函数数值优化测试结果表明,该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,大大加快了收敛速度,证实了该改进算法的有效性和高效性。关键词:
模拟退火算法;非均匀变异;数值最优化;反演
中图分类号:P631文献标识码:A收稿日期:
2006—12—07
RevisedSimulatedAnnealingAlgorithmJiangLongcong,LiuJiangping(InstituteofGeophysicsandGeomatics,ChinaUniversityofGeosciences,Wuhan430074,China)
Abstract:Basedontheideaofnon2uniformmutationingeneticalgorithm,wepresentanovelrevisedsimulatedannealing(RSA),whichusedthenon2uniformmutationtogenerateanewmodelfromcurrentmodel.Testedbysomenumericalfunctions,RSAcansearchinthelargeareaforthesolutionsinhightemperature.Withtheloweringofthetemperature,theareaofsearchingthesolutionswillbegraduallyreducedandconvergencewillspeedup.Sothere2sultsprovetheeffectivenessofRSA.Keywords:simulateannealing;non2uniformmutation;numericaloptimal;inversion
1 引 言人类对地球内部物理性质(包括速度、密度、电导率、温度等)以及矿产资源分布的了解,大多来自地表地质和地球物理、地球化学资料的反演和解释[1]。反演方法可以分为线性反演和非线性反演两种,线性反演已成为一套科学的反演理论,
然而,绝大部分地球物理问题都是非线性的,并且实践表明,线性反演方法有容易陷入局部极值和依赖于初始值等缺点。因此,地球物理学者们不断的尝试开发非线性反演方法,比如人工神经网络[2]、小波多尺度反演[3]、模拟退火算法[4]等。模拟退火算法是近年发展起来的全局最优化算法,其主要优点是;不用求目标函数的偏导数及解大型矩阵方程组,即能找到一个全局最优解,而且易于加入约束条件,编写程序简单。目前此法已开始用于解决非线性地球物理反问题,如波形反演、静校正、叠前偏移速度分析等非线性反演中,并取得了较好的效果。然而,由于模拟退火法是建立在随机搜寻方法的基础上,要达到一定的精度要求,每一模型参© 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net
数的离散点必须足够大。每次迭代必须进行多次目标函数计算,因而在处理实际资料时计算效率不高,影响着它的广泛应用。为了提高模拟退火算法的计算效率,出现了许多改进的方法,如采用依赖温度的Cauchy或似Cauchy分布代替常规模拟退火方法中的高斯分布产生新模型,基于Cauchy分布产生新模型的优点是,高温状态下可进行大范围的搜索,低温状态下只在当前模型附近进行搜索,而且由于似Cauchy分布有一个平坦的“尾巴”,使其易于迅速跳出局部极值区。王山山等[5]将Cauchy分布和Gibbs分布结合起来产生新模型,使得反演过程更加合理,加快了反演过程的收敛,并且提高了算法的抗干扰能力。王凌等[6]详细研究函数优化中基于Cauchy分布的状态发生器SGC(StategeneratorbasedonCauchydistribution)和基于Gaussian分布的状态发生器SGG(StategeneratorbasedonGaussi2andistribution)对SA(Simulatedannealing)算法性能的影响。对分布机制的研究表明,SGC有利于大范围搜索和脱离极小区域,而SGG较适合于局部搜索。对不同复杂度的典型问题的仿真表明,优化简单单极小问题时SGC的优化效率优于基于SGG,优化复杂多极小或存在平坦区的简单问题时SGC的优化度和鲁棒性均优于SGG,进而利用对尺度参数的“退温”控制,提出了SGC的改进策略,较大程度上提高了算法的优化度。纪晨等[7]在模拟退火算法中引入均匀设计方法,Basu等[8]提出用试验方法确定临界温度,算法由稍高于临界温度开始,Press等[9]采用单纯形法与模拟退火算法相结合的综合算法,在不同程度上提高了模拟退火法的计算效率,然而在实际应用中还有待于提高。随着多维分形(Multifractals)理论与应用研究日益受到重视,人们展开了关于这一理论的统计学研究。Tsallis给出了广义Boltzmann2Gibbs统计理论及相应的Gibbs分布。基于这一理论,Penna提出了新的模拟退火方法,即由广义Gibbs分布给出新的接收概率计算表达式,用于求解推销员问题,表明这种方法在较高的温度就能收敛到全局极值,具有较高的计算效率。张霖斌等以广义Boltzmann2Gibbs统计理论为基础,采用非常快速模拟退火法中依赖于温度的似Cauchy分布产生新的扰动模型,提出了快速模拟退火算法FSA(FastSimulatedAnnealing),进一步提高了模拟退火方法的计算效率[10]。笔者借鉴遗传算法中的非均匀变异思想[11],
用非均匀变异策略产生新的扰动模型,对传统的模拟退火算法进行了改进(Revisedsimulatedan2nealing,RSA),该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,能够大大加快收敛速度,通过对多峰值函数数值优化,测试结果表明该改进算法的有效性和高效性。
2 模拟退火原理及其改进１ 模拟退火原理模拟退火算法(SimulatedAnnealing)源于统计物理学,据统计热力学,物体中的每个分子的状态服从Gibbs分布,即:
ρ(r
i)
=
exp(-E(ri)kT)
∑Mj=1exp(-E(rj)kT)
(1)
式中:E(r
i)为第i个分子的能量函数;ri为第i个
分子所处的状态;k为波耳兹曼常数,T表示温度;ρ(r
i)为第i个分子的概率密度,为了方便起见
令k=1。模拟退火算法最早的思想是由Metropolis
在1953年提出的,由Kirkpatrick于1983年成功地应用在组合优化问题中,目前已经应用到各门学科中以解决非线性系统中的优化问题。SA法是局部搜索算法的扩展,它不同于局部搜索之处是以一定的概率选择领域中的最优值状态。理论上已经证明,它是一个全局最优算法,并且以概率1接近最优值。算法源于对实际固体退火过程的模拟,即先将固体加温至充分高,再逐渐冷却。加温时,固体内部粒子变为无序状态,内能增大;而逐渐降温时,粒子趋于有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。因此,算法实际上是将优化问题类比为退火过程中能量的最低状态,也就是温度达到最低点时,概率分布中具有最大概率的状态。模拟退火算法的具体步骤如下:
631 工程地球物理学报(ChineseJournalofEngineeringGeophysics) 第4卷 © 1994-2010 China Academic Journal Electronic Publishing House. All rights reserved. http://www.cnki.net1)给定模型每一个参数变化范围,在这个范围内随机选择一个初始模型m0,并计算相应的目标函数值E(m0);2)对当前模型进行扰动产生一个新模型m,计算相应的目标函数值E(m),得到ΔE=E(m)-E(m0)3)若ΔE<0,则新模型m被接受;若ΔE>0,则新模型m按概率P=exp(-ΔE/T)进行接受,T为温度。当模型被接受时,置m0=m;4)在温度T下,重复一定次数的扰动和接受过程,即重复步骤2)、3);5)缓慢降低温度T;6)重复步骤2)、5),直至收敛条件满足为止。为了避免最好的解在优化过程中被忽略掉,可以稍做改进,即在整个搜索过程中随时记下最好的值,因为该法的特点决定了最后的优化值并不一定就是最优的值,而只能是较优值。1 算法的改进21211 模型扰动模拟退火算法中新模型的产生是对当前模型进行扰动得到的,这个扰动是用随机函数控制的。Ingher于1989年提出了速度非常快的模拟退火算法VFSA(VeryFastSimulatedannealing),在该算法中,采用了依赖于温度的似Cauchy分布产生新的模型[5],即x′i=xi+yi(ximax-ximin)yi=Tksgn(ξ-0.5)×[(1+1/Tk)|2ξ-1|-1](2)式中,xi为当前模型参数,x′i为扰动后的模型参数,ξ为(0,1)区间上的随机数,ximin,ximax为xi的取值范围,sgn为符号函数,yi称之为扰动因子。笔者分析了快速模拟退火算法的改进扰动策略,提出了一种强化局部搜索能力的算法,该算法借鉴了遗传算法中的非均匀变异思想[11],用非均匀变异策略对当前模型参数扰动产生新的模型参数,即:x′i=xi+yi(ximax-ximin)yic=r(1-t/N)λsgn(r-0.5)(3)其中,r为(0,1)之间的随机数,t为当前温度,N为最大迭代次数,N与最大温度、最低温度有关,λ是确定非均匀性程度的常数,也称之为形状因子。(3)式表明,在高温时期,搜索的范围比较广,随着温度的降低,逐渐缩小搜索范围,为此,分析了当λ=015,1,2,5,10时相应的yic值,指导实际计算中如何取值,并且跟(2)式yi做了对比分析(图1)。