模拟退火算法.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,模拟退火算法,Simulated Annealing Algorithm,SAA,1,模拟退火算法是什么？是怎样提出来的？,模拟退火算法（,Simulated Annealing,，,SA,）,是一种模拟物理退火的过程而设计的优化算法。,它的基本思想最早在,1953,年就被,Metropolis,提出，,但直到,1983,年,Kirkpatrick,等人才设计出真正,意义上的模拟退火算法并进行应用。,模拟退火算法的基本思想是怎样的？,模拟退火算法采用类似于物理退火的过程，,先在一个高温状态下（相当于算法随机搜索），然后逐渐退火，,在每个温度下（相当于算法的每一次状态转移）徐徐冷却,（相当于算法局部搜索），最终达到物理基态,（相当于算法找到最优解）。,2,简介,模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。,该算法在系统向着能量减小的趋势变化过程中，偶尔允许系统跳到能量较高的状态，以避开局部最小，最终稳定在全局最小。,3,简介,SAA,属于随机模拟算法,模拟统计物理学中物体加热后冷却这一退火过程而建立的,随机优化算法,，意图是避免陷入局部极小解，早期用于组合优化，后来发展成一种通用的优化算法。,4,基本思想,SAA是,基于,Mente Carlo迭代求解策略的一种随机寻优算法，其,出发点,是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。,另一方面，,结合爬山法和随机行走,。,SAA,在某一初温下，伴随温度参数的不断下降，结合概率突跳特性在解空间中随机寻找目标函数的全局最优解，即在局部优解能概率性地跳出并最终趋于全局最优。,模拟退火算法是一种通用的优化算法，目前已在工程中得到了广泛应用。,5,基本思路,首先在高温下进行搜索，此时各状态出现概率相差不大，可以很快进入“热平衡状态”，这时进行的是一种“粗搜索”，也就是大致找到系统的低能区域；,随着温度的逐渐降低，各状态出现概率的差距逐渐被扩大，搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。,6,一、模拟退火算法概述,二、模拟退火算法的马氏链描述及收敛性,三、模拟退火算法关键参数和操作设计,四、模拟退火算法的改进及其并行性,五、模拟退火算法的实现及应用,7,固体退火过程,Metropolis,准则,组合优化与物理退火的相似性,模拟退火算法的步骤,第一节 模拟退火算法概述,8,1 模拟退火算法,概述,算法的提出,模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。,Optimization by simulated annealing,IBM Research Report,算法的目的,解决,NP复杂性,问题,提供有效近似算法,；,克服优化过程陷入局部极小；,克服初值依赖性。,1.1,固体,退火过程,9,1,、源于对固体退火过程的模拟；,2,、采用,Metropolis,接受准则；,3,、用冷却进度表控制算法进程，使算法在多项式时间里给出一个近似解。,固体退火过程的物理图像和统计性质是,SAA,的,物理背景,；,Metropolis,接受准则使算法,跳离局部,最优“险井”；而冷却进度表的合理选择是算法应用的,前提,。,1 模拟退火算法,概述,1.1,固体,退火过程,算法的基础,10,1 模拟退火算法,概述,固体,退火过程,什么是退火：,退火,是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,1.1,固体,退火过程,11,固体退火是将固体加热至融化，再徐徐冷却使之凝固成规整晶体的热力学过程，属于热力学与统计物理研究的范畴。,由以下三部分组成：,加温过程,等温过程,冷却过程,固体在恒定温度下达到热平衡的过程！,12,1 模拟退火算法,概述,固体,退火过程,加温过程,增强粒子的热运动，,使其偏离平衡位置，目的是,消除系统原先可能存在的非均匀态；,等温过程,退火过程中要让温度慢慢降低，在每一个温度下要达到热平衡状态，,对于与环境换热而温度不变的封闭系统,满足自由能较少定律,，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；,冷却过程,使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构,。,当液体凝固为固体的晶态时退火过程完成。,1.1,固体,退火过程,13,1 模拟退火算法,概述,数学表述,在温度,T,，分子停留在状态,r,满足Boltzmann概率分布,温度低时能量低的微观状态概率大，温度趋于零时，,固体几乎处于概率最大能量最小的基态。,1.1,固体,退火过程,14,1 模拟退火算法,概述,数学表述,在,同一个温度,T,，选定两个能量,E,1,E,2,，有,在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。,1.1,固体,退火过程,0,15,1 模拟退火算法,概述,数学表述,若,|,D,|,为状态空间,D,中状态的个数，,D,0,是具有最低能量的状态集合：,(1),当温度很高时，每个状态概率基本相同，接近平均值,1/|,D,|,；,(2),状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值,1/|,D,|,；,(3),当温度趋于,0,时，分子停留在最低能量状态的概率趋于,1,。,1.1,固体,退火过程,能量最低状态,非能量最低状态,16,1 模拟退火算法,概述,Metropolis,准则（,1953,）,以概率接受新状态,固体在恒定温度下达到热平衡的过程可以用,Monte Carlo,方法,（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,1.,2,Metropolis准则,17,Monte Carlo,模拟退火过程,蒙特卡罗,(Monte Carlo),方法，或称计算机随机模拟方法，是一种基于“随机数”的计算方法。这一方法源于美国在第一次世界大战中研制原子弹的“曼哈顿计划”。该计划的主持人之一、数学家冯,诺伊曼用驰名世界的赌城,摩纳哥的,Monte Carlo,来命名这种方法，为它蒙上了一层神秘色彩。,18,Monte Carlo,方法,Monte Carlo,方法的基本思想很早以前就被人们所发现和利用。,早在,17,世纪，人们就知道用事件发生的“频率”来决定事件的“概率”。,Buffon,试验：,19,世纪人们用投针试验的方法来求解圆周率,。,本世纪,40,年代电子计算机的出现，特别是近年来高速电子计算机的出现，使得用数学方法在计算机上大量、快速地模拟这样的试验成为可能。,19,Monte Carlo,方法,用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见，而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其基本思想是一样的。,它需要一个良好的随机数源。这种方法往往包含一些误差，但是随着随机抽取样本数量的增加，结果也会越来越精确。,20,1 模拟退火算法,概述,Metropolis准则（1953）以概率接受新状态,若在温度,T,，当前状态,i,新状态,j,若,E,j,=randrom0,1,s,=,s,j,;,Until,抽样稳定准则满足；,退温,t,k,+1,=update(,t,k,),并令,k,=,k,+1,；,Until,算法终止准则满足；,输出算法搜索结果。,1.,4,模拟退火算法的步骤,32,1 模拟退火算法,概述,影响优化结果的主要因素,给定初温,t,=,t,0,，随机产生初始状态,s,=,s,0,，令,k,=0,；,Repeat,Repeat,产生新状态,s,j,=Genete(,s,),；,if min1,exp-(,C,(,s,j,)-,C,(,s,)/,t,k,=randrom0,1,s,=,s,j,;,Until,抽样稳定准则满足；,退温,t,k,+1,=update(,t,k,),并令,k,=,k,+1,；,Until,算法终止准则满足；,输出算法搜索结果。,1.,4,模拟退火算法的步骤,三函数两准则,初始温度,33,三函数两准则,状态产生函数,状态接受函数,退温函数,抽样稳定准则,退火结束准则,34,SAA,流程,确定,初温,随机给定,初始解,收敛准则,满足否？,输出结果,Y,抽样稳定准则,满足否？,由当前,状态产生,新状态,接受函数,成立否？,替换当前状态,Y,Y,N,N,N,退温,保持当前状态不变,关键环节,1,初温、初始解,2,状态产生函数,3,状态接受函数,4,退温函数,5,抽样稳定准则,6,收敛准则,35,36,SAA,特点,可以保证全局最优,特别适合组合优化问题,可以随机选择初始解,对问题本身没有特别要求，不会因为问题实例的改变影响性能,简单易行，通用性好,37,马氏链描述,收敛性,时齐算法收敛性,非时齐算法收敛性,渐近性态,第二节,SAA,的马氏链描述及收敛性,38,模拟退火算法,(SAA),是将物理退火过程与组合优化相结合的一种随机迭代寻优算法。,数学模型描述为,由某一较高初始温度开始，在给定的邻域结构中，模拟退火过程，利用概率特性与抽样策略在解空间中随机搜索，随着温度不断下降重复抽样，用来优化问题的解。,引言,39,设 为所有状态构成的解空间，,为,k,时刻状态变量的取值。,随机序列 称为,马氏链,若,满足,简记,（记忆遗忘功能）,2,SAA的,马氏链描述及收敛性,2,.,1,马尔,可夫（,Markov,）链,40,一步转移概率,n,步转移概率,有限状态马氏链,若解空间有限。,时齐马氏链,41,模拟退火算法,(SAA),的搜索进程：,算法从某一个初始状态开始后，每一步状态转移均是在当前状态的邻域中随机产生新状态，然后以一定概率进行接受的。,接受概率仅依赖于新状态和当前状态，并由温度加以控制。因此，,SAA,对应一个马氏链。,42,若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度。,时齐算法,非时齐算法,若无需各温度下算法均达到平稳分布，但温度需按照一定的速率下降。或称非平稳马氏链算法。,43,SAA,基础理论,马氏链模型,44,SAA,要实现全局收敛必须满足下列条件：,状态可达性,初值鲁棒性,极限分布存在性,收敛到最优解,温度不变，,M,链极限分布存在,温度渐近,0,，,M,链极限分布存在,对应马氏链的状态图是强连通的,对算法的最终结果不依赖于初值,45,定义,1,状态,i,可达状态,j,:,定义,2,平稳分布,:,称,为马氏链的平稳分布,若一步转移概率满足等式,2.2.1,时齐算法的收敛性,2,SAA的,马氏链描述及收敛性,2,.,2,收敛性分析,46,时齐模拟退火算法的收敛性,结论,：,结论,1,时齐模拟退火算法对应的有限状态马氏链存在平稳分布。,结论,2,当温度趋于,0,时，马氏链以概率,1,收敛到最优状态集，而收敛到非最优状态的概率为,0,。,实现途径：,通过各温度下各状态序列无限长得以实现！,47,2.2.2,非时齐算法的收敛性,收敛定理,48,对退温函数加以严格控制，可使得,SA,算法以概率,1,收敛到全局最优解。,可设计退温函数为,其中 ，则当 时，,SA,算法以概率,1,收敛到全局最优解。,49,2.2.3 SA,算法渐近性能的逼近,收敛可以保证，但是时间性能不好,收敛速度有待研究,50,第三节 模拟退火算法关键参数和操作的设计,三函数两准则,状态产生函数,状态接受函数,退温函数,抽样稳定准则,退火结束准则,从算法流程看,，,SA算法包括三函数两准则,初温,51,1,状态产生函数（邻域函数）,设计的出发点：,尽可能保证产生的候选解遍布全部解空间。,产生候选解的方式,候选解产生的概率分布,两部分,52,前者决定由当前解产生候选解的方式，后者决定在当前解产生的候选解中选择不同状态的概率。,候选解的产生方式由问题的性质决定，通常在当前状态的邻域结构内以一定概率方式产生，,而邻域函数和概率方式可以多样化设计，其中概率分布可以是均匀分布、正态分布、指数分布、柯西分布等。,53,2,状态接受函数,目的：,尽可能接受优化解,状态接受函数一般以概率的方式给出，不同接受函数的差别主要在于,接受概率,的形式不同。,54,固定温度下，接受使目标函数值下降的候选解的概率要大于使目标函数值上升的候选解的概率。,随温度的下降，接受使目标函数值上升的解的概率要逐渐减小。,当温度趋于零时，只能接受目标函数值下降的解。,设计状态接受概率，应遵循的原则：,55,3,初温,实验表明：,初温值只要选择充分大，获得高质量解的概率就大！但花费计算时间增加。,初温的选择要足够高。,初温的确定应折衷考虑优化质量和优化效率。,56,均匀抽样一组状态，选各状态目标值的方差,利用经验公式,随机产生一组状态，确定两,两状态间的最大目标值差，,然后依据差值，利用一定的,函数确定初温。,例如，,57,初始温度,温度更新函数,内循环终止准则,外循环终止准则,退火历程,(annealing schedule),58,4,温度更新函数,衰减量“以小为宜”,实验表明降温速度越慢，获得高质量解的几率越大，但花费的计算时间将同时增加。,温度高时下降的慢些，温度低时下降的快些。,即温度的下降方式，用于在外循环中修改温度值。,59,Nahar,及,Skiscim,等人把 划分成,K,个小区间，温度更新函数为,Kirkpatrick,首先提出,被,Johnson,Bonomi,及,Lutton,采用,取,0.5,至,0.99,之间,60,5,内循环终止准则,检验目标函数值的均值是否稳定,连续若干步目标函数值的变化较小,按一定的步数抽样,链长,（,Metropolis,抽样稳定准则）,用于决定在各温度下产生候选解的数目。,时齐算法,常用,Metropol,is,抽样稳定准则包括：,非时齐,SAA,：,每个温度下只产生一个或少量候选解,。,61,具体应与问题规模成比例,。,实验表明高温时迭代次数越多越好，低温时迭代次数可以适当减少,。,62,6,外循环终止准则,理论上,要求温度终值趋于零,设置终止温度的阀值,设置外循环迭代次数,(6-50),算法搜索到的最优值连续若干步保持不变,（算法终止准则）,用于决定算法何时结束。,通常的做法包括：,检验系统熵是否稳定,63,三个参数 、和 值均有显著影响。,总结,过大的 值、值和 值均能导致过长的,CPU,时间。因而在最终解的质量有待较大,值和 值予以保证的前提下，选取较小,的 值可以抑制,CPU,时间上升的态势。,64,模拟退火算法基本要素和设定方法,65,模拟退火算法是一种通用的随机搜索算法，它可用于解决众多的优化问题，并已经广泛的应用于其他领域。如,VLSL,设计、图像识别等。当待解决的问题复杂性较高，而且规模较大时，在对问题的领域知识甚少的情况下，采用模拟退火算法最合适。因为模拟退火算法不像其他确定型启发式算法那样，需要依赖于问题的领域知识来提高算法的性能。,66,但是，从另一方面来说，已知有关待解决问题的一些知识后，模拟退火算法却无法充分利用它们，这使得模拟退火算法的优点就成了缺点。如何把传统的启发式搜索方法和模拟退火随机搜索算法结合起来，这是一个有待研究的十分有意义的课题。,67,模拟退火算法在求解规模较大的实际问题时，往往存在以下缺点：,（,1,）收敛速度比较慢。,（,2,）尽管理论上只要计算时间足够长，模拟退火法就可以保证以概率,1,收敛于全局最优点。但是在实际算法的实现过程中，由于计算速度和时间的限制，在优化效果和计算时间二者之间存在矛盾，因而难以保证计算结果为全局最优点，优化效果不甚理想。,（,3,）在每一温度下很难判定是否达到了平衡状态。,68,为此，人们对模拟退火算法提出了各种各样的改进，其中包括并行模拟退火算法、快速模拟退火算法（,Cauchy,机）和对模拟退火算法中各个函数和参数的重新设计等。,69,SA,算法直接简单模拟固体退火。,特点：,思路清晰、原理简单、使用灵活、应用广泛,同时，由于其直接性和简单化，也存在不足与弊病，使其应用及性能受到一定影响。,第四节 模拟退火算法的改进及并行性,70,不同,p,值对,CHN144,实例测得 值,71,4 模拟退火算法的改进,及并行性,模拟退火算法的优点,质量高；,初值鲁棒性强；,简单、通用、易实现。,模拟退火算法的缺点,由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,4.1 模拟退火算法的优缺点,72,4 模拟退火算法的改进,及并行性,改进的可行方案,（,1,）设计合适的状态产生函数；,（,2,）设计高效的退火历程；,（,3,）避免状态的迂回搜索；,（,4,）采用并行搜索结构；,（,5,）避免陷入局部极小，改进对温度的控制方式；,（,6,）选择合适的初始状态；,（,7,）设计合适的算法终止准则。,4.2 改进内容,73,4 模拟退火算法的改进,及并行性,改进的方式,：增加某些新的环节,（1）增加升温或重升温过程，避免陷入局部极小；,（2）增加记忆功能（记忆“Best so far”状态）；,（3）增加补充搜索过程（以最优结果为初始解）；,（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；,（5）结合其它搜索机制的算法；,（6）上述各方法的综合。,4.2 改进内容,74,4 模拟退火算法的改进,及并行性,改进的思路,（,1,）记录“,Best so far”,状态，并即时更新；,（,2,）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续,m,1,步保持不变则认为,Metropolis,抽样稳定，若连续,m,2,次退温过程中所得最优解不变则认为算法收敛。,4.3 一种改进的模拟退火算法,75,4 模拟退火算法的改进,及并行性,改进的退火过程,（,1,）给定初温,t,0,，随机产生初始状态,s,，令初始最优解,s,*=,s,，当前状态为,s,(0)=,s,，,i,=,p,=0,；,（,2,）令,t,=,t,i,，以,t,，,s,*,和,s,(,i,),调用改进的抽样过程，返回其所得最优解,s,*,和当前状态,s,(,k,),，令当前状态,s,(,i,)=,s,(,k,),；,（,3,）判断,C,(,s,*),m,2,?,若是，则转第,(6),步；否则，返回第,(2),步；,（,6,）以最优解,s,*,作为最终解输出，停止算法。,4.3 一种改进的模拟退火算法,76,4 模拟退火算法的改进,及并行性,改进的抽样过程,（,1,）令,k=0,时的初始当前状态为,s,(0)=,s,(,i,),，,q,=0,；,（,2,）由状态,s,通过状态产生函数产生新状态,s,，计算增量,C,=,C,(,s,)-,C,(,s,),；,（,3,）若,C,C,(,s,)?,若是，则令,s,*,=,s,，,q,=0,；否则，令,q,=,q,+1,。若,C,0,，则以概率,exp(-,C,/,t,),接受,s,作为下一当前状态；,（,4,）令,k,=,k,+1,，判断,q,m,1,?,若是，则转第,(5),步；否则，返回第,(2),步；,（,5,）将当前最优解,s,*,和当前状态,s,(,k,),返回改进退火过程。,4.3 一种改进的模拟退火算法,77,TINA,Time-invariant noise algorithm,状态产生函数中扰动强度不随时间改变，而是和能量大小相关，能量大的扰动大，能量小的扰动小，能量为零，扰动也为零，算法停止。,78,MTRSA,单调升温,(Monotonic temperature rising)SA,在算法退火后期，温度很低且陷入局部极小解的时，算法很难跳出。因此，可以适当重新提高温度，促使算法跳出。,79,SAMG,记忆指导,SA(Simulated Annealing with Memmory Guidance,简记为,SAMG),增加一个记忆装置，存储算法计算过程产生的最好的解，以这个解为最终解。,80,自适应,SA,自适应,SA,算法,根据邻域搜索进展的反馈信息,自适应确定温度变化和邻域搜索强度,特点：,1),退火过程中温度参数变化符合幅值递减的下降总趋势,但不排除局部升温的可能,以保证寻求到合适的温度序列,避免陷入局部最优,;,2),算法的终止条件依据退火温度和邻域搜索进展状态设计,;,3),每一温度下算法的迭代次数随温度下降而递增,邻域搜索强度依其对目标函数的贡献动态分配,;,4),温度变化、邻域搜索和终止条件的控制机制由算法过程自动触发。,81,4 模拟退火算法的改进,及并行性,4.,4,并行性,1,、,操作并行性,：各个环节同时处理；,2,、,进程并行性,：同时多个算法运行；,3,、,空间并行性,：解空间分解分别处理，最终组合。,全过程并行性,子进程并行性,82,第五节 算法的实现与应用,83,引言,SAA,应用的一般形式：,从选定的初始解开始，在借助于控制参数,t,递减时产生的一系列,Markov,链中，利用一个新解产生装置和接受准则，重复进行包括“,产生新解,-,计算目标函数差,-,判断是否接受新解,-,接受,(,或舍弃,),新解,”这四个任务的实验，不断对当前解迭代，从而达到使目标函数,最优,的执行过程。,84,SAA,实现,通用框架,确定问题编码方案,设计初始温度、终止温度和温度下降策略（退温函数）,设计能量函数,设定稳定准则,设计产生新解的方式（状态产生函数）,设计,Metropolis,接受准则（状态接受函数）,生成初始状态,85,1,、数学模型,对问题的简明描述。,解空间,目标函数,初始解,所有,可能解,的集合，它限定了初始解选取和新解产生的范围,对问题的优化目标的数学描述，易计算，对应关系明确,算法开始迭代的起点，它的选取使算法能导出较好的最终解,5 模拟退火算法的实现与应用,5.1,应用的一般要求,86,2,、新解的产生和接受机制,产生新解,由产生装置从当前解的解空间中产生。,计算目标函数值之差,最快的方法是按增量计算。,判断新解是否被接受,准则,Metropolis,新解代替当前解,代替变换部分，修正目标函数值。,87,3,、温度更新函数,关键参数：初温、温度降低函数、马氏链长度、停止准则。,综合应用，达到最佳效果！,88,SAA,求解,TSP,关键问题,如何由旧的解产生新的解,方式很多,相邻两位置对换变动最小,任意两位置对换,单点位置移动,子排列位置移动,子排列反序,子排列位置移动且反序变动最大,理论已经证明上述所有方式都收敛,实际验证收敛性能差异很大,89,1,、组合优化问题的求解,数学模型,一个商人欲到 个城市推销商品，每两个城市 和 之间的距离为 ，如何选择一条道路使得商人每个城市走一遍后回到起点且所走路经最短。,5 模拟退火算法的实现与应用,5.,2,算法,的实现,90,解空间,目标函数,初始解,选为,91,新解的产生,1,、互换操作,(SWAP),随机交换两个不同城市的位置。,2,、逆序操作,(INV),两个不同随机位置的城市逆序。,3,、插入操作,(INS),随机选择某个城市插入到不同随机位置。,92,衰减函数,初值,马氏链长,停止准则,设计终止温度的阀值,设计外循环迭代次数,算法搜索到的最优值连续若干步保持不变,93,5 模拟退火算法的实现与应用,例,1,30城市TSP问题（,d,*,=423.741 by D B Fogel）,TSP Benchmark,问题,41 94;37 84;54 67;25 62;,7 64;2 99;68 58;71 44;54,62;83 69;64 60;18 54;22,60;83 46;91 38;25 38;24,42;58 69;71 71;74 78;87,76;18 40;13 40;82 7;62 32;,58 35;45 21;41 26;44 35;4 50,94,5,模拟退火算法的实现与应用,算法流程,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,95,5,模拟退火算法的实现与应用,初始温度的计算,for i=1:100,route=randperm(CityNum);,fval0(i)=CalDist(dislist,route);,end,t0=-(max(fval0)-min(fval0)/log(0.9);,例,1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,96,5,模拟退火算法的实现与应用,状态产生函数的设计,（,1,）互换操作，随机交换两个城市的顺序；,（,2,）逆序操作，两个随机位置间的城市逆序；,（,3,）插入操作，随机选择某点插入某随机位置。,例,1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,2,8,1,5,9,3,4,6,7,2,8,3,4,1,9,5,6,7,2,3,5,9,8,1,4,6,7,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,2,8,3,5,9,1,4,6,7,97,5,模拟退火算法的实现与应用,参数设定,截止温度,tf=0.01;,退温系数,alpha=0.90;,内循环次数,L=200*CityNum;,例,1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,98,5,模拟退火算法的实现与应用,运行过程,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,99,5,模拟退火算法的实现与应用,运行过程,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,100,5,模拟退火算法的实现与应用,运行过程,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,101,5,模拟退火算法的实现与应用,运行过程,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,102,5,模拟退火算法的实现与应用,运行过程,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,103,5,模拟退火算法的实现与应用,运行结果,例,1,30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,104,5,模拟退火算法的实现与应用,例,2,模拟退火求解背包问题,已知背包的装载量为,c,=8,，现有,n,=5,个物品，它们的重量和价值分别是,(2,3,5,1,4),和,(2,5,8,3,6),。试使用模拟退火算法求解该背包问题，写出关键的步骤。,求解：假设问题的一个可行解用,0,和,1,的序列表示，例如,i,=(1010),表示选择第,1,和第,3,个物品，而不选择第,2,和第,4,个物品。用模拟退火算法求解此例的关键过程如图所示：,105,运行步骤,106,问题：求,2,、函数优化问题的求解,（,1,）编码：解自身,（,2,）初始温度,100,终止温度,0,，降温策略,-1,（,3,）能量函数：,107,（,4,）,Metropolis,准则,P,i,/,P,j,=exp(,E,j,-,E,i,),/,T,k,=1,r,=0.6,（,5,）初始状态：,13,能量：,1024-169=855,（,6,）产生新状态：大范围高斯变异,新状态：,10,能量,:924,108,（,7,）选择：选择新状态,10,（,8,）重复步骤（,6,）（,7,）,1,次,（,9,）温度降低,1,度，重复上述操作直到温度降到最低，,或许就能够得到最优解！,109,数学模型,求最大值,110,111,传统的优化方法（局部优化）,共轭梯度法、拟牛顿法、单纯形方法,全局优化方法,漫步法（,Random Walk,）、模拟退火法、,GA,关于优化问题,112,模拟退火与传统迭代最优算法的比较：,（,1,）当系统在非零温度下时，从局部最优中跳出是非常可能的，因此不会陷入局部最优。,（,2,）系统最终状态的总特征可以在较高温度下看到，而状态的好的细节却在低温下表现，因此，模拟退火是自适应的。,113,全局优化方法,1,、不依赖于初始条件；,2,、不与求解空间有紧密关系，对解域，无可微或连续的要求。求解稳健，但收敛速度慢。能获得全局最优。适合于求解空间不知的情况,传统的优化方法,1,、依赖于初始条件。,2,、与求解空间有紧密关系，促使较快地收敛到局部解，但同时对解域有约束，如可微或连续。利用这些约束，收敛快。,3,、有些方法，如,Davison-Fletcher-Powell,直接依赖于至少一阶导数；共轭梯度法隐含地依赖于梯度。,比较：,114,