资源描述：
《模拟退火算法及其改进_刘怀亮.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第4卷第6期广州大学学报(自然科学版)Vol.4No.62005年12月JournalofGuangzhouUniversity(NaturalScienceEdition)Dec.2005文章编号:1671-4229(2005)06-0503-04模拟退火算法及其改进刘怀亮(广州大学信息与机电工程学院,广东广州510006)摘要:介绍了模拟退火算法的背景、原理和具体实现方法,分析了它的不足之处,讨论了它的改进措施,并进行了仿真实验验证.关键词:模拟退火算法;组合优化问题;全局优化算法;算法改进;算法实现中图分类号:TP15文献标识码:A将该思想引入组合优化
2、理论,解决了许多诸如VL-0引言SI等大规模优化设计问题.近年来该算法引起了巨型计算机系统设计、大规模集成电路优化、图像自然科学、管理科学和工程技术领域里存在处理、生物学、分子物理和化学、数值分析、复杂布大量的组合优化问题,其求解时间随问题规模呈局等领域广泛的重视.指数级增长,当规模稍大时就会因时间限制而失112算法原理去可行性,对这类问题的解决具有重要的理论和模拟退火算法是源于物理中固体物质的退火现实意义.人们提出了许多近似算法,但这些算法过程的原理.在热力学中将系统(如处于溶化状态或者由于过于注意个别问题的特征而缺乏通用的合金或晶体)缓慢冷却的过程称为/
3、退火0,在这一性,或者因为所得解强烈地依赖初始解的选取而过程中原子失去热动力时有充裕的时间重新分布缺乏实用性,而更为主要的是这些算法虽然解决并达到有序状态,从而使系统达到最低能量状态.了局部搜索的最优但却很难达到全局最优.在/退火0过程中系统的能量服从Boltzmann概模拟退火算法(SimulatedAnnealingAlgorithm)率分布,即系统依概率P(E)处于任一能量为E就是对其中的局部搜索算法(LocalSearchAlgo-的热平衡状态:rithm)进行改进而提出的.模拟退火算法将组合优P(E)=exp(-E/(HT))(1)化问题与统计力学
4、中的热平衡问题类比,另辟了其中E为能量,T为温度,H为Boltzmann常一条求解最优化问题的新途径,它可通过模拟退数,该式说明随着温度T的降低,系统处于高能E火过程,找到全局或逼近全局的最优解.状态的概率随之减小,这就是退火规律.模拟退火算法首先要确定一个能量函数即目1模拟退火算法概述标函数,求解最优化问题一般通过Metropolis抽样和/退火0两个过程来实现.Metropolis抽样过程是111算法的提出在某一给定温度T的情况下,对解的状态空间进模拟退火算法(SA)又称为模拟冷却法、统计行随机抽样,当能量降低即$E<0时,接受当前冷却法、Monte-C
5、arlo退火法、随机松弛法和概率状态,当$E>0时,则根据概率爬山法等.模拟退火算法是一种新的统计优化方P($E)=exp(-$E/T)(2)[1]法,其思想最早是由MetropolisN等人借鉴统计有条件地接受当前状态.热力学中物质退火方法而提出的.1983年Kirk-经过充分的抽样之后,类似于热力学系统达[2]patrick等人开展了一些富有成效的工作,成功地到当前温度的平衡状态,最优化过程也将在降低收稿日期:2004-09-23;修回日期:2005-09-13作者简介:刘怀亮(1976-),男,硕士,主要从事分布式人工智能、数据挖掘、数据库等研究.50
6、4广州大学学报(自然科学版)第4卷目标函数的过程中跳出误差曲面的局部极小点.C(S.)-C(S(k));退火过程则是使系统的温度降低,即使(3)若$C<0,则接受S.为下一个当前解;若Tm0,则按概率exp(-$C/T)接受T.为下一个m为迭代次数.当前解.若S.被接受,则S(k+1)=S,否则S(k在新的温度条件下,继续Metropolis抽样过程.+1)=S(k);重复进行抽样和退火过程,直到满足收敛条件.(4)K=K+1,由某个给定的收敛准则,判断算法类似于固体退火必须/徐徐0降温,才能使固是否应该中止.如果是,则转第5步,否则转
7、第2步;体在每一温度下都达到热平衡,最终趋于全局能(5)将当前解返回给调用它的退火过程算法.量最小的基态而不是位于局部极小点.113算法的基本组成3模拟退火算法的不足之处模拟退火算法的基本组成可以分为:(1)产生机制:以一定的概率选择一种解,这模拟退火法是在一系列递减温度下产生的点个概率函数称为生成函数;列,理论上可以看作是一系列的马尔可夫链(2)接受准则:以一定的概率接受代价函数值(MarkovChains).在某一温度下多次重复Metropo-的偶然上升,这个概率函数称为接受函数;lis过程,目标函数值的分布规律将满足玻尔兹曼(3)控制参数:以一定的冷却
8、方式退火,实际分布规律.如果系统温度以足够慢的速率下
