模拟退火算法及其改进_蒋龙聪

第4卷第2期2007年4月　

工程地球物理学报

CHIN ESE J OU RNAL OF EN GIN EERIN G GEOP H YSICS

Vol 14,No 12Apr 1,2007

文章编号:1672—7940(2007)02—0135—06

模拟退火算法及其改进

蒋龙聪,刘江平

(中国地质大学地球物理与空间信息学院,武汉430074)

作者简介:蒋龙聪(1983—

),男,硕士研究生,现在主要从事地震数据处理和反演理论方法研究。E 2mail :longcja @https://www.wendangku.net/doc/d6240650.html, 刘江平(1957—

),男,教授,博士生导师,主要从事地震勘探的科研与教学工作。E 2mail :liujp @https://www.wendangku.net/doc/d6240650.html, 摘　要:借鉴遗传算法中的非均匀变异思想,用非均匀变异策略对当前模型扰动产生新的模型,对传统的模

拟退火算法提出了改进,通过多峰值函数数值优化测试结果表明,该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,大大加快了收敛速度,证实了该改进算法的有效性和高效性。

关键词:模拟退火算法;非均匀变异;数值最优化;反演

中图分类号:P631文献标识码:A

收稿日期:2006—

12—07R evised Simulated Annealing Algorithm

Jiang Longcong ,Liu Jiangping

(I nstitute of Geop hysics and Geomatics ,China Universit y of Geosciences ,W uhan 430074,China )

Abstract :Based on t he idea of non 2uniform mutation in genetic algorit hm ,we present a novel revised simulated annealing (RSA ),which used t he non 2uniform mutation to generate a new model f rom current model.Tested by some numerical f unctions ,RSA can search in t he large area for t he solutions in high temperat ure.Wit h t he lowering of t he temperat ure ,t he area of searching t he solutions will be gradually reduced and convergence will speed up.So t he re 2sult s p rove t he effectiveness of RSA.

K ey w ords :simulate annealing ;non 2uniform mutation ;numerical optimal ;inversion

1　引　言

人类对地球内部物理性质(包括速度、密度、电导率、温度等)以及矿产资源分布的了解,大多来自地表地质和地球物理、地球化学资料的反演和解释[1]。反演方法可以分为线性反演和非线性反演两种,线性反演已成为一套科学的反演理论,然而,绝大部分地球物理问题都是非线性的,并且实践表明,线性反演方法有容易陷入局部极值和依赖于初始值等缺点。因此,地球物理学者们不

断的尝试开发非线性反演方法,比如人工神经网

络[2]、小波多尺度反演[3]、模拟退火算法[4]等。

模拟退火算法是近年发展起来的全局最优化算法,其主要优点是;不用求目标函数的偏导数及解大型矩阵方程组,即能找到一个全局最优解,而且易于加入约束条件,编写程序简单。目前此法已开始用于解决非线性地球物理反问题,如波形反演、静校正、叠前偏移速度分析等非线性反演中,并取得了较好的效果。

然而,由于模拟退火法是建立在随机搜寻方法的基础上,要达到一定的精度要求,每一模型参

数的离散点必须足够大。每次迭代必须进行多次目标函数计算,因而在处理实际资料时计算效率不高,影响着它的广泛应用。为了提高模拟退火算法的计算效率,出现了许多改进的方法,如采用依赖温度的Cauchy或似Cauchy分布代替常规模拟退火方法中的高斯分布产生新模型,基于Cauchy分布产生新模型的优点是,高温状态下可进行大范围的搜索,低温状态下只在当前模型附近进行搜索,而且由于似Cauchy分布有一个平坦的“尾巴”,使其易于迅速跳出局部极值区。王山山等[5]将Cauchy分布和G ibbs分布结合起来产生新模型,使得反演过程更加合理,加快了反演过程的收敛,并且提高了算法的抗干扰能力。王凌等[6]详细研究函数优化中基于Cauchy分布的状态发生器SGC(State generator based on Cauchy dist ribution)和基于Gaussian分布的状态发生器SGG(State generator based on Gaussi2 an dist ribution)对SA(Simulated annealing)算法性能的影响。对分布机制的研究表明,SGC有利于大范围搜索和脱离极小区域,而SGG较适合于局部搜索。对不同复杂度的典型问题的仿真表明,优化简单单极小问题时SGC的优化效率优于基于SGG,优化复杂多极小或存在平坦区的简单问题时SGC的优化度和鲁棒性均优于SGG,进而利用对尺度参数的“退温”控制,提出了SGC 的改进策略,较大程度上提高了算法的优化度。

纪晨等[7]在模拟退火算法中引入均匀设计方法,Basu等[8]提出用试验方法确定临界温度,算法由稍高于临界温度开始,Press等[9]采用单纯形法与模拟退火算法相结合的综合算法,在不同程度上提高了模拟退火法的计算效率,然而在实际应用中还有待于提高。

随着多维分形(Multifractals)理论与应用研究日益受到重视,人们展开了关于这一理论的统计学研究。Tsallis给出了广义Boltzmann2G ibbs 统计理论及相应的G ibbs分布。基于这一理论, Penna提出了新的模拟退火方法,即由广义G ibbs分布给出新的接收概率计算表达式,用于求解推销员问题,表明这种方法在较高的温度就能收敛到全局极值,具有较高的计算效率。张霖斌等以广义Boltzmann2G ibbs统计理论为基础,采用非常快速模拟退火法中依赖于温度的似Cauchy分布产生新的扰动模型,提出了快速模拟退火算法FSA(Fast Simulated Annealing),进一步提高了模拟退火方法的计算效率[10]。

笔者借鉴遗传算法中的非均匀变异思想[11],用非均匀变异策略产生新的扰动模型,对传统的模拟退火算法进行了改进(Revised simulated an2 nealing,RSA),该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,能够大大加快收敛速度,通过对多峰值函数数值优化,测试结果表明该改进算法的有效性和高效性。

2　模拟退火原理及其改进

１　模拟退火原理

模拟退火算法(Simulated Annealing)源于统计物理学,据统计热力学,物体中的每个分子的状态服从G ibbs分布,即:

ρ(r

i)=

exp(-E(r i)

k T

)

∑M

j=1

exp(-E(r j)

k T

)

(1)

式中:E(r i)为第i个分子的能量函数;r i为第i个分子所处的状态;k为波耳兹曼常数,T表示温度;ρ(r i)为第i个分子的概率密度,为了方便起见令k=1。

模拟退火算法最早的思想是由Met ropolis 在1953年提出的,由K irkpat rick于1983年成功地应用在组合优化问题中,目前已经应用到各门学科中以解决非线性系统中的优化问题。SA法是局部搜索算法的扩展,它不同于局部搜索之处是以一定的概率选择领域中的最优值状态。理论上已经证明,它是一个全局最优算法,并且以概率1接近最优值。

算法源于对实际固体退火过程的模拟,即先将固体加温至充分高,再逐渐冷却。加温时,固体内部粒子变为无序状态,内能增大;而逐渐降温时,粒子趋于有序,在每个温度都达到平衡态,最后在常温时达到基态,内能减为最小。因此,算法实际上是将优化问题类比为退火过程中能量的最低状态,也就是温度达到最低点时,概率分布中具有最大概率的状态。

模拟退火算法的具体步骤如下:

631 工程地球物理学报(Chinese Journal of Engineering G eophysics) 第4卷　

1)给定模型每一个参数变化范围,在这个范围内随机选择一个初始模型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年提出了速度非常快的模拟退火算法V FSA(Very Fast Simulated annealing),在该算法中,采用了依赖于温度的似Cauchy分布产生新的模型[5],即

x′i=x i+y i(x i max-x i min)

y i=T k sgn(ξ-0.5)

×[(1+1/T k)|2ξ-1|-1](2)式中,x i为当前模型参数,x′i为扰动后的模型参数,ξ为(0,1)区间上的随机数,x i min,x i max为x i的取值范围,sgn为符号函数,y i称之为扰动因子。

笔者分析了快速模拟退火算法的改进扰动策略,提出了一种强化局部搜索能力的算法,该算法借鉴了遗传算法中的非均匀变异思想[11],用非均匀变异策略对当前模型参数扰动产生新的模型参数,即:

x′i=x i+y i(x i max-x i min)

y ic=r(1-t/N)λsgn(r-0.5)(3)其中,r为(0,1)之间的随机数,t为当前温度,N 为最大迭代次数,N与最大温度、最低温度有关,λ是确定非均匀性程度的常数,也称之为形状因子。(3)式表明,在高温时期,搜索的范围比较广,随着温度的降低,逐渐缩小搜索范围,为此,分析了当λ=015,1,2,5,10时相应的y ic值,指导实际计算中如何取值,并且跟(2)式y i做了对比分析(图1)。

从图1可以得出,随着迭代次数的增加(即温度的降低),y ic的值逐渐减小,也即缩小了搜索范围,加强了局部搜索的能力,常规的模拟退火算法和快速模拟退火算法都是随机进行大范围的搜索,而且,当形状因子λ越大,越容易进行局部搜索,因此,在实际计算中,要合理地控制好λ值,λ太大容易陷入局部极值中,Michalewicz的建议和笔者的数值模拟表明是λ取[2,5]是比较好的。随着温度的降低,新接收的模型越来越接近真实的求解模型,因此,加强局部搜索更有利于提高算法的收敛性能。

21212　接收概率

对于接受概率,快速模拟退火算法采用广义G ibbs分布产生接收概率P,即

P=[1-(1-h)ΔE/T]1/[1-h](4)式中ΔE表示能量差,T表示温度,h为一实数。按照(4)式计算得到的概率进行判断是否接收新模型,该式只考虑了能量的绝对变化,然而,物体由熔化状态逐渐冷却至结晶状态所出现的相变规则,必须考虑能量的相对变化,为此顾汉明等[12]对此进行了修正,即:

P=[1-(hΔE/T)(Eα1/Eβ)]1/h(5)式中,E为新模型的目标函数,E1为当前模型的目标函数,α,β为非负实数。

21213　降温方式

对于退火方案,实践表明,T取指数变化的模式比较切合退火的实质。Ingber给出的快速退火算法中的退火方式为

T(K)=T0exp(-C K1/N)(6)式中:T0为初始温度,K为迭代次数,C为给定的常数,N为待反演的参数的个数。该式子也可以改成

T(K)=T0αk1/N(7)通常选择017≤α≤1,在本文中,用1代替1/N,α取为0199。

在改进的算法中RSA,采用(3)式对当前模型扰动产生新的模型,新模型按照(5)进行接收,按照(7)式缓慢降温。用Matlab语言编写了本文中的算法,用于数值优化试验。

731

　第2期 蒋龙聪等:模拟退火算法及其改进

图1　扰动因子随迭代次数变化的曲线

(a)为常规模拟退火的扰动;(b)、(c)、(d)、(e)、(f)为λ=0.5,1,2,5,10

Fig.1　Perturbation factor via iterative number

3　数值优化

为了验证改进的算法的有效性,选取三个多峰值函数作为测试对象,计算该函数的最小值。用改进的模拟退火算法和普通模拟退火算法对三个函数各运行20次,收敛曲线为采用局部策略之后的局部最优收敛曲线。3.1　函数1:Shuber函数

f1(x1,x2)=∏

2

k=1

∑5

i=1

i cos[(i+1)x k+i]

(8)

x k∈(-10,10)该函数有全局最小值-1861731,用改进的算法(RSA)求取该函数的最小值,运行20次,每次都能找到全局最小值,而常规的模拟退火算法12次找不到全局最小值,8次

831 工程地球物理学报(Chinese Journal of Engineering G eophysics) 第4卷　

找到全局最小值,常规模拟退火易陷入局部极小值。初始温度为10000,最小温度为010001,马尔科夫链长度为3,λ为5,初始值x 1、x 2同时为-10。采用了记忆方法,记忆了搜索过程中每一温度下的局部最优解,收敛过程如图2-图4

。

3.2　函数2:De Jong 函数

f 2(x 1,x 2)=100(x 2

1-x 2)

2

+(1-x 1)

2

-2.048≤x i ≤2.048

(9)函数在(x 1,x 2)=(1,1)处有一个全局最小值0。

用两种算法计算该函数最小值,各运行20次,改进后的模拟退火算法每次都能找到全局最小值,而普通的模拟退火算法13次找到全局最小值。初始温度为10000,最小温度为010001,马尔科夫

链长度为3,

λ为5,初始值x 1,x 2同时为-21048。3.3　函数3:Easom 函数　f 3(x 1,x 2)=-co s (x 1)cos (x 2)e -(

x 1-π)2

-(

x 1-π)2

-100≤x i ≤100

(10)函数在(x 1,x 2)=(π,π

)处有一个全局最小值-1.用两种算法计算该函数的最小值,各运行20次,改进后的模拟退火算法18次找到全局最小值,两次陷入函数值0中,普通的模拟退火算法12次找到全局最小值,8次陷入函数值0中。初始温度为10000,最小温度为010001,马尔科夫链长度为3,

λ为3,初始值x 1,x 2同时为-100。随着温度的下降,函数值逐渐靠近全局最优解,此时宜采用局部搜索方法,因此改进后的模拟退火算法能够很快搜索到全局最优解,而常规的模拟退火算法由于是对解空间的解随机扰动,很容易在很长时间内,搜索不到比当前局部最优解更好的解,对三个函数的测试表明了该点。

4　结　语

1)改进的模拟退火算法相对于常规的模拟退

火算法,加强了局部搜索功能,更有利于提高算法

的收敛速度,数值优化结果证实改进算法的有效性和高效性。

2)对于改进的算法,λ的选择至关重要,λ太大容易陷入局部最小值,λ太小则降低了收敛速度,因此要通过测试再决定取λ的值。

3)从本质上讲,模拟退火算法属于蒙特卡罗方法,它用随机的方法代替了线性反演中的步长,相对于线性反演来讲,模拟退火算法的执行效率还是远远不及线性反演,因此,如何考虑将线性反演与非线性反演结合起来,相互利用对方的优势,并且用于实际反演中将是接下来重点研究的对象。参考文献:

[1]王家映.地球物理反演理论[M ].北京:高等教育出版

9

31　第2期 蒋龙聪等:模拟退火算法及其改进

社,20001

[2]徐海浪,吴小平.电阻率二维神经网络反演[J].地球物

理学报,2006,49(2):584～5891

[3]徐义贤,王家映.大地电磁多尺度反演[J].地球物理学

报,1998,41(5):704～7111

[4]姚姚.地球物理非线性反演模拟退火法的改进[J].地

球物理学报,1995,38(5):643～6501

[5]王山山,李灿平,李青仁,等.快速模拟退火地震反演

[J].地球物理学报,1995,38(增刊1):123～1341 [6]王凌,郑大钟.基于Cauchy和G aussian分布状态发

生器的模拟退火算法[J].清华大学学报(自然科学版),2000,40(9):109～1121

[7]纪晨,姚振兴.用于地球物理反演的均匀设计优化算

法[J].地球物理学报,1996,39(2):233～242.

[8]Basu A,Frazer L.Rapid determination of the critical

temperature in simulated annealing inversion[J].S ci2 ence,1990,249(21):1409～1412.

[9]Press W H,Vetterling W T,Teukolsky S A,et al.

Simulated annealing optimization over continus space [J].Com p uters in Physics,1991(5):426～429. [10]张霖斌,姚振兴,纪晨,等.快速模拟退火算法及应用

[J].石油地球物理勘探,1997,32(5):654～660. [11]Michalewicz Z.演化程序—遗传算法和数据编码的结

合[M].北京:科学出版社,2000.

[12]顾汉明,江涛,王家映.改进的模拟退火方法进行

AVO岩性参数反演[J].地球科学,1999,24(4):418

～422.

[13]钟守楠.遗传算法的收敛性与编码[J].武汉水利电力

大学学报,2000,33(1):108～112.

[14]张宏兵,尚作萍,谭胜章,等.波阻抗反演的快速模拟

退火算法[J].河海大学学报,2005,33(4):434～437.

[15]M D Martínez,X Lana,J Olarte etc.Inversion of

Rayleigh wave phase and group velocities by simula2 ted annealing[J].Physics of the Earth and Planeta2 ry I nteriors,2000,122(1):3～17.

[16]王薇,曾光明,何理.用模拟退火算法估计水质模型

参数[J].水利学报,2004,11(6):61～67.

[17]金炳尧.最新优化技术中的若干新技术[J].科技通

报,2000,16(2):119～1241

[18]邢文训,谢金星.现代优化计算方法[M].北京:清华

大学出版社,19991

[19]Kirkpatrick S,Gelatt J r C D,Vecchi M P.Optimi2

zation by simulated annealing[J].S cience,1983,220

(13):671～6801

[20]Mantawy A H,Abdel2Magid,Y oussef L,et al.A

simulated annealing algorithm for unit commitment [J].I E E E T ransactions on Power S ystems,1998, 13(1):197～2051

[21]杨东,于桂荣.基于模拟退火算法预测储层参数[J].

沈阳航空工业学院学报.2005,22(1):76～77. [22]唐立山,谢云,尤矢勇,等.非数值并行算法[M].北

京:科学出版社,1994.

041 工程地球物理学报(Chinese Journal of Engineering G eophysics) 第4卷　

模拟退火算法原理及改进

作者简介：李香平（１９７８￣），男，湖北监利人，中国地质大学计算机学院硕士研究生，研究方向为科学研究与可视化；张红阳（１９８２￣），男，湖北咸宁 人，中国地质大学计算机学院硕士研究生，研究方向为数据挖掘与数据仓库。 模拟退火算法原理及改进 李香平，张红阳 （中国地质大学计算机学院，湖北武汉４３００７４） 摘 要：模拟退火算法是一种强大的随机搜索算法，能应用于许多前提信息很少的问题，能渐进地收敛于最优值。对 ＳＡ算法进行了介绍，论述了ＳＡ算法的原理并对算法进行了改进，展示了计算实验的结果。 关键词：模拟退火；全局优化中图分类号：ＴＰ３１２ 文献标识码：Ａ 文章编号：１６７２－７８００（２００８）０４－００４７－０２ ０引言 近年来，传统的单一算法越来越不适应大规模非线性规划 问题。它们要求目标函数是可微的和收敛的。ＳＡ能很好地弥补它们的缺陷。 从用于统计力学的ＭｏｎｔｅＣａｒｌｏ方法上受到启发，ＳＡ算法在 １９８３被Ｋｉｒｋｐａｔｒｉｃｋ提出来。对比传统局部搜索算法，ＳＡ在搜索 时会在搜索空间上下移动而不依赖初始条件，擅长解决多维问题。此外，它能处理任意程度的非线性、 不连续和随机的问题。能处理任意边界和约束的评估函数。因此，它能轻易处理有脊背和高地的函数。只要初温高、退火表适当，它就能得到全局最优。ＳＡ成功应用于组合优化、神经网络、图像处理和代码设计。 １模拟退火算法原理 组合优化问题是在给定的约束条件下，求目标函数的最值 的问题。设（Ｓ，ｆ）是组合优化问题的一个实例，ｉｏｐｔ∈Ｓ若对所有 ｉ∈Ｓ，都有ｆ（ｉｏｐｔ）≥ｆ（ｉ），则称ｆ（ｉｏｐｔ）≤ｆ（ｉ）为ｍｉｎｆ（ｉ）的最优解。 ＳＡ来源于物理热力学原理，综合了固体退火与组合优化 之间的类似性。类似固体的复杂系统，先被加热到一个物质粒子能自由移动的很高的温度，当它慢慢冷却时，它的能量减少。如果“冷却”过程足够慢，系统将忽略局部稳定构造，到达能量最低状态，即基态。 在模拟的每一步中，新解的产生按照Ｍｅｔｒｏｐｏｌｉｓｔｒａｎｓｉｔｉｏｎ法则，一个新的状态从现有的状态中产生，这个法则能以一定的概率接受能量上升（即产生劣解）的新状态，而能量下降是优化的总目的。法则如下所示： ｐ（ｘ＝＞ｙ）＝ １， ｆ$%ｙ≤ｆ$%ｘｅｘｐ－ｆ$% ｘｆ$%ｙ $ % ， ｏｔｈｅｒｗｉｓ&ｅ ｆ是系统能量，ｔ是温度。ＳＡ的一般框架： Ｇｅｎｅｒａｔｅｄｉｎｉｔｉａｌｓｔａｔｅａｔｒａｎｄｏｍ；Ｇｅｎｅｒａｔｅｄｉｎｉｔｉａｌｔｅｍｐｅｒａｔｕｒｅ；ＲＥＰＥＡＴＲＥＰＥＡＴ ｙ＝ｇｅｎｅｒａｔｅ（，）； ＩＦａｃｃｅｐｔ（，ｙ，）ＴＨＥＮ＝ｙ ＵＮＴＩＬ＇ｉｎｎｅｒｌｏｏｐｓｔｏｐｃｒｉｔｅｒｉｏｎ＇ｓａｔｉｓｆｉｅｄ 为了提高ＳＡ的性能，我们应该仔细处理控制参数的协调。（１）初始温度的选择。初始温度太高会花费高昂的计算时间，太低会拒绝劣解的接受，会丢失ＳＡ全局优化的优点。本文提出了一个初始温度的公式： ｔ０＝’ｆ＋ ｌｎｘ －１ ’ｆ＋ 是函数增量的平均值，χ 是初始的接受概率。（２）温度降低策略。温度降低越快，陷入局部的概率就越大。然而，温度降低太慢会导致算法速度慢得不能接受。本文采用了一种快速的非线性降低法： ｔｋ＝ ｔ０ １＋ｋ ｋ＝１，２，３，…… （３）适当的邻域结构。在退火期间，步长太小导致算法在探索相位空间效率低，太大新解总被拒绝。在持续优化时，新的等价值均一地按间距分布在以ｘｉ的坐标为中心的邻域中，沿轴的间距的一半被看作步长向量ξ。当点落在ｆ的定义域内时，就随机产生新解。 （４）终止标准。内循环是单一温度下在各种条件下Ｍａｒｃｏｖ链的一种渐进接近全局最优的模拟实现，即循环Ｍａｒｃｏｖ链长次数结束。外循环取某个温度ｔ作为算法终止标准，或者是迭代若 软件导刊 ＳｏｆｔｗａｒｅＧｕｉｄｅ 第７卷第４期 ２００８年４月Ｖｏｌ．７Ｎｏ．４Ａｐｒ．２００８

模拟退火算法及其改进_蒋龙聪

第4卷第2期2007年4月　 工程地球物理学报 CHIN ESE J OU RNAL OF EN GIN EERIN G GEOP H YSICS Vol 14,No 12Apr 1,2007 文章编号:1672—7940(2007)02—0135—06 模拟退火算法及其改进 蒋龙聪,刘江平 (中国地质大学地球物理与空间信息学院,武汉430074) 作者简介:蒋龙聪(1983— ),男,硕士研究生,现在主要从事地震数据处理和反演理论方法研究。E 2mail :longcja @https://www.wendangku.net/doc/d6240650.html, 刘江平(1957— ),男,教授,博士生导师,主要从事地震勘探的科研与教学工作。E 2mail :liujp @https://www.wendangku.net/doc/d6240650.html, 摘　要:借鉴遗传算法中的非均匀变异思想,用非均匀变异策略对当前模型扰动产生新的模型,对传统的模 拟退火算法提出了改进,通过多峰值函数数值优化测试结果表明,该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,大大加快了收敛速度,证实了该改进算法的有效性和高效性。 关键词:模拟退火算法;非均匀变异;数值最优化;反演 中图分类号:P631文献标识码:A 收稿日期:2006— 12—07R evised Simulated Annealing Algorithm Jiang Longcong ,Liu Jiangping (I nstitute of Geop hysics and Geomatics ,China Universit y of Geosciences ,W uhan 430074,China ) Abstract :Based on t he idea of non 2uniform mutation in genetic algorit hm ,we present a novel revised simulated annealing (RSA ),which used t he non 2uniform mutation to generate a new model f rom current model.Tested by some numerical f unctions ,RSA can search in t he large area for t he solutions in high temperat ure.Wit h t he lowering of t he temperat ure ,t he area of searching t he solutions will be gradually reduced and convergence will speed up.So t he re 2sult s p rove t he effectiveness of RSA. K ey w ords :simulate annealing ;non 2uniform mutation ;numerical optimal ;inversion 1　引　言 人类对地球内部物理性质(包括速度、密度、电导率、温度等)以及矿产资源分布的了解,大多来自地表地质和地球物理、地球化学资料的反演和解释[1]。反演方法可以分为线性反演和非线性反演两种,线性反演已成为一套科学的反演理论,然而,绝大部分地球物理问题都是非线性的,并且实践表明,线性反演方法有容易陷入局部极值和依赖于初始值等缺点。因此,地球物理学者们不 断的尝试开发非线性反演方法,比如人工神经网 络[2]、小波多尺度反演[3]、模拟退火算法[4]等。 模拟退火算法是近年发展起来的全局最优化算法,其主要优点是;不用求目标函数的偏导数及解大型矩阵方程组,即能找到一个全局最优解,而且易于加入约束条件,编写程序简单。目前此法已开始用于解决非线性地球物理反问题,如波形反演、静校正、叠前偏移速度分析等非线性反演中,并取得了较好的效果。 然而,由于模拟退火法是建立在随机搜寻方法的基础上,要达到一定的精度要求,每一模型参

模拟退火算法报告

模 拟退火算法 一 定义 1 概念 什么是退火？在热力学上，退火现象指物体逐渐降温的物理现象，温度愈低，物体的能量状态会低；够低后，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。大自然在缓慢降温（亦即，退火）时，可“找到”最低能量状态：结晶。但是，如果过程过急过快，快速降温（亦称「淬炼」）时，会导致不是最低能态的非晶形。如下图所示，首先（左图）物体处于非晶体状态。我们将固体加温至充分高（中图），再让其徐徐冷却，也就退火（右图）。加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小（此时物体以晶体形态呈现）。 似乎，大自然知道慢工出细活：缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最安稳。 模拟退火算法(SA)最早的思想是由N. Metropolis 等人于1953年提出。1983 年,S. Kirkpatrick 等成功地将退火思想引入到组合优化领域。它是基于Monte-Carlo 迭代求解策略的一种随机寻优算法，其出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。模拟退火算法从某一较高初温出发，伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部最优解能概率性地跳出并最终趋于全局最优。 模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。在迭代更新可行解时，以一定的概率来接受一个比当前解要差的解，因此有可能会跳出这个局部的最优解，达到全局的最优解。以下图为例，假定初始解为左边蓝色点A ，模拟退火算法会快速搜索到局部最优解B ，但在搜索到局部最优解后，不是就此结束，而是会以一定的概率接受到左边的移动。也许经过几次这样的不是局部最优的移动后会到达全局最优点D ，于是就跳出了局部最小值。 根据热力学的原理，在温度为T 时，出现能量差dE 的降温的概率为P(dE)，表示 为: ()?? ? ??=kT dE E P ex p d 。其中k 是波尔兹曼常数，值为-2310×13)1.3806488(=k ，exp 表示自然指数，且dE<0。因此dE/kT<0，所以P(dE)函数的取值范围是(0,1)。满足概率密度函数的定义。其实这条公式更直观意思就是：温度越高，出现一次能量差为P(dE)的降温的概率就越大；温度越低，则

关于模拟退火算法及其影响因素的研究

关于模拟退火算法及其影 ｉ《＿■ ＳＩＬＩＣＯＮＶ ＶＡＬＬＥ工响因素的研究 邓超陈文宣王树青 （东莞南博职业技术学院广东东莞５２３０８３）信毫科学 插要：通过使用模拟退火算法模拟逼近函数：ｙ＝ｘ＋ｃｏｓｘ＋ｉ开展实验，并在实验过程中对模拟退火算法的影响因素进行比较ｔ并提出相应的改进方案，直观的将两者的差别体现出来。 关键词：模拟退火算法；权系数；阀值：神经网络结构；ＭＡＴＬＡＢ 中圈分类号：ＴＰ３文献标识码：Ａ文章编号ｚ１６７１－７５９７（２０１０）０４１００４５－－０１ １鬟拟量火算法的基本曩客 模辛｝ｌ退火算法最初的思想［自Ｍｅｔｒｏｐｏｌｉｓ在１９５３年提出，其来源统计物理学中对于固体退火过程的模拟。他采用Ｍｅｔｒｏｐｏｌｉｓ准则接收新解，用冷去系数的参数对算法进程进行控制。使得算法在多项时间里得出最优解．２对曩板退火算法进行试ｔ研究 １）用模拟退火算法模拟逼近函数：ｙ＝ｘ＋ｃｏｓｘ＋１并对神经网络的权系数、阀值进行学习其神经网络结构为１—３－４＿３—１． ２）具体试验过程如下： 模拟退火算法的实现主要采用了¨ＴＬＡＢ软件，利用其中的神经网络工具箱进行编程模拟．在网络ＵＵｌ练方面，隐层采用ｌｏｇｓｉｇ（厂（ｊ）＝＿—二—＿＿－） Ｈ’ａ烈一哪函数作为传递函数。在输出层方面采用线性输出函数ｉｍｒｅｌｉｎ（，（善）＝＃）．降温函数采用ｔ＝＾ｔ． ①给定的学习样本、初始温度、结柬温度及降温速率＾． ＠在某一温度下．以正态分布（Ｍａｔｌａｂ中用ｒａｎｄｎ）生成函数产生新的权系数增量△翻。‘虬．＝缈＋△翻生成新的权系数。 ③根据代价函数求出神经网络的输出偏差Ｅ∥ｔ 胛＝；（歹一ｙ）２． ＠如果Ｐ，ｒＳ０，则取翻ｒ＋ｌ为新值，即ｑ＝够＋ｌ? ⑤如果Ｐ玎＞ｏ，采用接收函数：Ｂ（ｉ）＝［Ｉ＋ｅ＝Ｖ／‘】＿１ 以其值和［０，ｌ】随机数ｄ进行比较： 若Ｂ（ｉ）＞ｄ。则Ｃｄ＝够．。；， 若Ｂ（ｉ）≤ｄ，则国不变。 ＠以ｔ：ｘｔ修改参数ｔ．即缓慢降温。返回②执行． ３）试验生产的原函数和网络输出图如下： ４）结果分析ｔ 由学习的结果来看，学习的曲线和原曲线相差较大，而且函数收敛得很慢．其原因是模拟退火法的初始参数包括初温ｔＯ，结束温度ｔｆ’衰减温度ｄｅｌｔａＴ及控制内循环的马尔可夫链长Ｌ的选择对整个结果产生较大影响。 ３樱报遗火法的改盛可行性方毫 １）设计合适的状态产生函数：设计高效的退火历程；避免状态的迂回搜索；采用并行搜索结构：改进对温度的控制方式；选择合适的初始状态；设计合适的算法终止准则。 ２）也可通过增加某些来实现：如增加升温或重升温过程；增加记忆功能｛增加朴充搜索过程。 ４－｝墨横挂鼍火算法的实验改进方囊 ”对原算法的神经喇络结构进行更改．由卜３－４—３一ｌ改为卜１０一ｈ ２）调整即网络训练参数：具体为添加代码为： ｎｅｔ．ｔｒａｉｎＰａｒａＬｅｐｏｃｈｓ２３０００： ｎｅｔ．ｔｒａｉｎＰａｒ∞．ｇｏａｌ＝０．００２： ｎｅｔ．ｔｒａｉｎＰａｒａｎＩｒ２０．０ｌ： Ｉ开始训练 ｎｅｔ２ｔｒａｉｎ（ｎｅｔ，ｘ．ｙ）：） 在对原算法改进后试验产生的原函数和网络输出图如下（改进处在源程序中体现）： 由结果可以看到，改进后的算法收敛速度加快，函数的逼近和精度都已经较高。 参考文献： 【ｌ】王士同、陈剑夫等编著。问题求解的人工智能神经网络方法ｒ气象出版社． ［２］焦李成．神经网络系统理论，西安，西安电子科技大学出版社，１９９６．６． 作者简介： 邓超（１９７９－），男．汉族．广东省韶关市人，硕士．东莞南博职业技术 学院助教，研究方向；神经网络?　万方数据