模拟退火算法综述 作业.doc

西安理工大学研究生课程论文/研究报告课程名称： 现代优化计算方法 课程代号： 030219 任课教师： 张广鹏 论文/研究报告题目： 模拟退火算法综述 完成日期： 2012 年 8 月 1 日学 科： 机械设计制造及其自动化 学 号： 1108020124 姓 名： 张勇 成 绩： 模拟退火算法综述摘要: 本文综合介绍模拟退火算法的基本原理、研究进展，实现形式、以及模拟退火算法的应用，发展前景，存在的问题及主要的解决方法，对模拟退火算法给出一个简明、全面、客观的综合评价。关键字：模拟退火算法；冷却进度表；退火策略；组合优化问题Abstract：This paper introduces simulated annealing algorithm basic principle, research progress, implementation form, and the simulated annealing algorithm application, prospect of development, existing problems and the main solutions, the simulated annealing algorithm gives a concise, comprehensive, objective evaluation.Key words：Simulated Annealing Algorithm；Cooling schedule；Annealing strategy；Combinatorial Optimization Problem一、 前言模拟退火算法的原理来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。在实际问题上也就是达到了最优解。根据Metropolis准则，粒子在温度T时趋于平衡的概率为e-E/(kT)，其中E为温度T时的内能，E为其改变量，k为Boltzmann常数。用固体退火模拟组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法：由初始解i和控制参数初值t开始，对当前解重复“产生新解计算目标函数差接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表(Cooling Schedule)控制，包括控制参数的初值t及其衰减因子t、每个t值时的迭代次数L和停止条件S。二、 模拟退火算法的研究进展模拟退火算法（SA）最早见于IBM托马斯.J.沃森研究中心的S.Kirkpatrick 等人的文章, 他们在对组合优化进行研究后, 根据迭代改进的思想提出了“模拟退火算法”。模拟退火算法的实现主要先是建立数学模型，包括要确定解空间，确立目标函数和初始解；在产生新解的时候要符合某种接受机制；最后由接受准则使新解更优或是恶化。在模拟退火算法的发展进程中，Metropolis等人对固体在恒定温度下达到热平衡过程的模拟也给他们以启迪：应该把Metropolis准则引入到优化过程中来。在国内，模拟退火算法应用最早是管梅古教授于1962年提出的CPP问题并且给出了一个解法。在1990年姚新教授通过参数对SA的收敛性；初始温度T0的选取；冷却调度表以及模拟退火算法中止条件的分析，合理阐述了模拟退火算法的一些优缺点。在当代，模拟退火算法又进一步广发的发展，利用的领域也逐步涵盖了各种领域，并且由一些学者逐渐改进了模拟退火算法，例如：2006年由蒋龙聪教授借鉴遗传算法中的非均匀变异思想,用非均匀变异策略对当前模型扰动产生新的模型,对传统的模拟退火算法提出了改进,通过多峰值函数数值优化测试结果表明,该算法在高温的时候能够进行大范围的搜索,随着温度的降低,逐渐缩小解的搜索范围,大大加快了收敛速度,证实了该改进算法的有效性和高效性。还有一系列的模拟退火算法在公交排班优化的研究;对土地利用分区优化方法，在混流装备投产中的应用；注塑机增力机构优化的研究；变压器的状态监测研究等等。由SCI创建的引文报告如下:由上述引文报告可得出近些年模拟退火的发展与应用有了井喷式的发展并应用于各种领域。三、 模拟退火算法的实现形式模拟退火算法的实现需要通过建立数学模型，要确立新解的产生和接受机制，冷却进度表和伪程序。1. 数学模型:由解空间、目标函数和初始解三部分组成。1) 解空间:对所有可能解均为可行解的问题定义为可能解的集合,对存在不可行解的问题,或限定解空间为所有可行解的集合,或允许包含不可行解但在目标函数中用罚函数(Penalty Function)惩罚以致最终完全排除不可行解;2) 目标函数:对优化目标的量化描述,是解空间到某个数集的一个映射,通常表为若干优化目标的一个和式,应正确体现问题的整体优化要求且较易计算,当解空间包含不可行解时还应包括罚函数项;3) 初始解:是算法迭代的起点,试验表明,模拟退火算法是健壮的(Robust),即最终解的求得不十分依赖初始解的选取,从而可任意选取一个初始解。2. 新解的产生和接受机制:由四个步骤构成一轮试验。首先,按某种随机机制由当前解产生一个新解,通常通过简单变换(如对部分元素的置换、互换或反演等)产生,可能产生的新解构成当前解的邻域;其次,计算新解伴随的目标函数差,一般由变换的改变部分直接求得;第三,由接受准则,即新解更优,或恶化但满足Metropolis准则,判断是否接受新解,对有不可行解而限定解空间仅包含可行解时,还需先判断其可行性;最后,满足接受准则时进行当前解和目标函数值的迭代,否则舍弃新解。3. 冷却进度表:即(t,t, L, S)。应使得t充分大且衰减得充分慢、L足够大,S通常选为解在连续M个Mapkob链中无任何改变时终止算法。4. 伪程序:用k=M表示停止条件, Generate(j from i)表示从当前解i产生新解j的产生过程,Random为0, 1内均匀分布的随机数,则算法的伪程序如下:PROCEDURE Anneal(t,t,L,M,VAR i);BEGINk:=0;REPEATAccept:=FALSE;FOR p:=1 TO L DOBEGINGenerate(j from i );f:=f(j)-f(i);求最大值时改为f:=f(i)-f(j)IF(fRandom)THEN BEGIN i:=j;f:=f+f;Accept:=TRUE ENDEND;IF NOT Accept THEN k:=k+1 ELSE k:=0UNTIL k=MEND;四、 模拟退火算法的应用与发展前景研究及实际应用得出，模拟退火算法有以下特性：1. 高效性：与局部援索算法相比，模拟退火算法可望在较短时间里求得更优近似解。模拟退火算法允许任意选取初始解和随机数序列，又能得出较优近似解，因此应用算法求解优化问题的前期工作量大大减少。2. 健壮性（Robust）： 在可能影响模拟退火算法实验性能的诸因素中，问题规模n的影响最为显著; n的增大导致搜索范围的绝对增大，会使CPU时间增加；而对于解空间而言，搜索范围又因n的增大而相对减小，将引起解质量的下降，但SAA的解和CPU时间均随n增大而趋于稳定，且不受初始解和随机数序列的影响。SAA不会因问题的不同而蜕变。3. 通用性和灵活性：模拟退火算法能应用于多种优化问题，为一个问题编制的程序可以有效地用于其它问题。SAA的解质与CPU时间呈反向关系，针对不同的实例以及不同的解质要求，适当调整冷却进度表的参数值可使算法执行获得最佳的“解质时间”关系。由以上模拟退火算法的特性可以看出模拟退火算法随着时代的发展广泛应用于各种领域，在科学分类上：几乎毫无盲点应用于自然科学工程技术；人文与社会科学，各个分支。对于模拟退火算法主要还是其对生活，工程之类的应用。 所以模拟退火算法在当代学者的研究下有很广阔的发展前景，可以更好的利用它更高精度的解决实际问题。五、 存在的问题和主要解决方法1. 模拟退火算法存在的问题：返回一个高质近似解的时间花费较多，当问题规模不可避免地增大时，难于承受的运行时间将使算法丧失可行性。因此，必须探求改进算法实验性能、提高算法执行效率的可行途径，2. 主要解决方法：1) 选择适当的邻域结构和随机数序列可以提高解质并缩减运行时间，这需要大量试验。适合于对优化问题较了解的优化控制问题。2) 选择合理的冷却进度表可使算法的执行过程更为有效。这将在后面详细讨论。3) 模拟退火算法（SAA）的执行过程是一系列“产生新解判断接受舍弃”的迭代过程，提高各个环节的时效可以缩减运行时间，而不会影响最终解的质量。4) 改变算法进程的各种变异方法，如有记忆的SAA（记取算法进程中的最优近似解）、回火退火法（在解质不能改进时使控制参数值增大以跳离“陷井”）、加温退火法（先升温后退火）等，这将在后面详细讨论。5) 大规模并行计算能够真正缩减算法的运行时间。 3. 有待于解决的问题：1) 模拟退火算法(SA)的控制参数对算法性能有一定的影响，至今还没有一个适合各种问题的参数选择方法，只能依赖于问题进行确定。对于这些参数的选择还需要进一步研究，确定适合优化问题的参数选择范围。2) 模拟退火算法的应用虽然非常广泛，但它的理论还不够完善，故而阻碍发展，因此有必要深入其理论研究。3) 寻求新的数学工具和分析方法，建立算法复杂性、收敛性和鲁棒性的分析研究理论，对算法收敛速度和优化度进行估计。4) 基于数学和计算机进行研究，尤其是算法的比较研究，提供控制参数选取的理论指导和规律性结论，提出搜索进入局部极小的合理判断准则。参考文献【1】 冯玉蓉；模拟退火算法的研究及其应用d【2】 卢开澄，组合数学一算法与分析，北京:清华大学出版社，1983.【3】 高尚，模拟退火算法中的退火策略研究j航空计算技术，第32卷第4期2002年【4】 谢云，模拟退火算法综述j，微计算机信息，第14卷第5期，1998年【5】 庞峰，模拟退火算法的原理及算法在优化问题上的应用d，中国优秀硕士学位论文全文数据库，2006年【6】 蒋龙聪,刘江，模拟退火算法及其改进j，工程地球物理学报，第4卷第2期，2007年【7】 王向红，模拟退火算法在营养配餐优选系统中的研究与应用d中国优秀硕士学位论文全文数据库，2011年【8】 王薇,曾光明,何理.用模拟退火算法估计水质模型参数J.水利学报,2004,11(6):6167.【9】 Kirkpatrick S, Gelatt Jr C D, Vecchi M P. Optimi-zation by simulated annealingJ.Science, 1983,220(13):671680【10】 Basu A, Frazer L. Rapid determination of the criticaltemperature in simulated annealing inversionJ.Sci-ence, 1990,249(21):14091412.【11】 ZHOU Kang，GAO Zun-hai，XU Jin An algorithm of DNA compu-ting on 0-1 planning problemJ Advances in Systems Science and Applications，2005，5( 4) : 587-593【12】 李文勇，李泉永：基于模拟退火的全局优化算法桂林电子工业学院学报2001年1月，第21卷第2期【13】 Yip，PuiChiv，PhDThe role of regional guidance in optimi