资源描述：
《全局优化算法自适应模拟退火_遗传算法的研究_樊叔维.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第7卷第4期光学精密工程Vol.7,No.41999年8月OPTICSANDPRECISIONENGINEERINGAugust,1999文章编号1004-924X(1999)04-0016-06全局优化算法自适应模拟退火-遗传算法的研究樊叔维张兴志(中国科学院长春光学精密机械研究所长春130022)摘要对模拟退火法和遗传算法作了简要叙述,并深入分析了模拟退火法和遗传算法的寻优特性,指出了模拟退火法存在的不足及遗传算法的优良特性,从而引入了自适应模拟退火-遗传算法,并定性分析了该算法的可行性。关键词模拟退火遗
2、传算法中图分类号O439文献标识码A1模拟退火法的基本原理模拟退火法(Simulatedannealing,SA)是模拟热力学中经典粒子系统的降温过程,来求解规划问题的极值。当孤立粒子系统的温度以足够慢的速度下降时,系统近似处于热力学平衡状态,最后系统将达到本身的最低能量状态,即基态,这相当于能量函数的全局极小点。由于模拟退火法能够有效地解决大规模的组合优化问题,且对规划问题的要求极小,因此引起研究人员的极大兴趣。在光学设计领域中,该方法已成为一种极具发展前景的一种优化方[1-3]法,可以预料,该方法的成功应
3、用将促使光学设计进一步向智能化发展。模拟退火法的基本原理如下:(1)给定初始温度T0,及初始点,计算该点的函数值f(x)。(2)随机产生扰动$x,得到新点xc=x+$x,计算新点函数值f(xc),及函数值差$f=f(xc)-f(x)。(3)若$f[0,则接受新点,作为下一次模拟的初始点;$f(4)若$f>0,则计算新点接受概率:p($f)=exp(-),产生[0,1]区间上均匀K#T分布的伪随机数r,rI[0,1],如果p($f)r,则接受新点作为下一次模拟的初始点;否则放弃新点,仍取原来的点作为下一次模拟
4、的初始点。收稿日期:1998-06-25修稿日期:1999-01-104期樊叔维等:全局优化算法自适应模拟退火-遗传算法的研究17以上步骤称为Metropolis过程。按照一定的退火方案逐渐降低温度,重复Metropolis过程,就构成了模拟退火优化算法,简称模拟退火法。当系统温度足够低时,就认为达到了全局最优状态。按照热力学分子运动理论,粒子作无规则运动时,它具有的能量带有随机性,温度较高时,系统的内能较大,但是对某个粒子而言,它所具有的能量可能较小。因此算法要记录整个退火过程中出现的能量较小的点。在模拟退
5、火优化算法中,降温的方式对算法有很大影响。如果温度下降过快,可能会丢失极值点;如果温度下降过慢,算法的收敛速度又大大降低。为了提高模拟退火优化算法的有效性,许多学者提出了多种退火方案,有代表性的有:T0(1)经典退火方式:降温公式为:T(t)=;特点是温度下降很缓慢,因此,算法的ln(1+t)收敛速度也是很慢的。T0(2)快速退火方式:降温公式为:T(t)=;这种退火方式的特点是在高温区,温度1+At的下降是比较快的,而在低温区,降温的速率较小。这符合热力学分子运动理论中,某粒子在高温时,具有较低能量的概率要
6、比在低温时小得多,因此寻优的重点应在低温区。式中A可以改善退火曲线的形态。2模拟退火方法存在的不足通过分析模拟退火法的基本原理,可知,模拟退火法在一系列递减温度下产生的点列,从理论上讲,可以看作是一系列的马尔可夫链(MarkovChains)。在某一温度下多次重复Metropolis过程,目标函数值的分布规律将满足玻尔兹曼分布规律。如果系统温度以足够慢的速率下降,玻尔兹曼分布就趋向收敛于全局最小状态的均匀分布。也就是说,若按照一定的条件产生无限长的马尔可夫链,模拟退火法就能保证以概率1.0收敛于全局极小点,该
7、结论已被文献[4]证明。文献[4]指出,在某一温度下,只要计算时间足够长,也就是马尔可夫链足够长,其起始点的函数值将以很高的概率低于终止点的函数值,即求得全局最小点。通过上面的分析可以看出,模拟退火法主要存在以下不足:(1)尽管理论上只要计算时间足够长,模拟退火法就可以保证以概率1.0收敛于全局最优点。但是在实际算法的实现过程中,由于计算速度和时间的限制,在优化效果和计算时间二者之间存在矛盾,因而难以保证计算结果为全局最优点,优化效果不甚理想。(2)在每一温度下很难判定是否达到了平衡状态,即马尔可夫链的长度不
8、易控制,反应到算法上,就是Metropolis过程的次数不易控制。(3)模拟退火算法中的两种退火方式,T始终按照优化前给定的规律变化而没有修正,这是不科学的。为了解决模拟退火法存在的不足,台湾学者Feng-TseLin等人曾提出了用遗传算法的优点来改进模拟退火算法的模拟退火-遗传算法。本文将在退火过程中综合考虑计算结果及搜索路径而确定T的取值方法的自适应模拟退火法与遗传算法相结合,形成自适应模拟退火
