模拟退火算法讲解课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,模拟退火算法,模拟退火算法,算法的提出,模拟退火算法最早的思想由,Metropolis,等（,1953,）提出，,1983,年,Kirkpatrick,等将其应用于组合优化。,算法的目的,解决,NP,复杂性,问题；,克服优化过程陷入局部极小；,克服初值依赖性。,算法的提出,什么是退火：,退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,什么是退火：,物理退火过程,加温过程,增强粒子的热运动，消除系统原先可能存在的非均匀态；,等温过程,对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；,冷却过程,使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,物理退火过程 加温过程增强粒子的热运动，消除系统原先可,热力学中的退火现象指物体逐渐降温时发生的物理現象：,温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，,annealing,）时，可达到最低能量状态；但如果快速降温（淬火，,quenching,），会导致不是最低能态的非晶形。,热力学中的退火现象指物体逐渐降温时发生的物理現象：,模仿自然界退火現象而得，利用了物理中固体物质的,退火过程,与一般,优化,问题的相似性,从某一初始,温度,开始，伴随温度的不断下降，结合,概率突跳,特性在解空间中,随机,寻找,全局最优解,模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般,数学表述,在温度,T,，分子停留在状态,r,满足,Boltzmann,概率分布,数学表述,模拟退火算法基本思想,：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率,1,停留在最优解。,在,同一个温度,T,，选定两个能量,E,1,E,2,，有,模拟退火算法基本思想：在一定温度下，搜索从一个状态随机地变,Boltzman,概率分布,告诉我们：,（,1,）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率,（,2,）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。,（,3,）随着温度的下降，能量最低状态对应概率越来越大；温度趋于,0,时，其状态趋于,1,Boltzman概率分布告诉我们：,Metropolis,准则（,1953,）,以概率接受新状态,固体在恒定温度下达到热平衡的过程可以用,Monte Carlo,方法,（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,Metropolis准则（1953）以概率接受新状态,Metropolis,准则（,1953,）,以概率接受新状态,若在温度,T,，当前状态,i,新状态,j,若,E,j,=randrom0,1,s,=,s,j,;,Until,抽样稳定准则满足；,退温,t,k,+1,=update(,t,k,),并令,k,=,k,+1,；,Until,算法终止准则满足；,输出算法搜索结果。,基本步骤,算法程序核心内容,三个函数,新状态,s,j,=Genete(,s,),if min1,exp-(,C,(,s,j,)-,C,(,s,)/,t,k,=randrom0,1,s,=,s,j,;,t,k,+1,=update(,t,k,),两个准则,抽样稳定准则（内循环终止准则）,算法终止准则（外循环终止准则）,算法程序核心内容,状态产生函数,原则,产生的候选解应遍布全部解空间,方法,在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生,状态产生函数,状态接受函数的产生,原则,(1),在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；,(2),随温度的下降，接受使目标函数上升的解的概率要逐渐减小；,(3),当温度趋于零时，只能接受目标函数下降的解。,方法,具体形式对算法影响不大,一般采用,min1,exp(-,C,/,t,),状态接受函数的产生,初温的设定,收敛性分析,通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；,初温应充分大；,实验表明,初温越大，获得高质量解的机率越大，但花费较多的计算时间；,初温的设定,初温产生方法,（,1,）均匀抽样一组状态，以各状态目标值得方差为初温；,（,2,）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；,（,3,）利用经验公式。,初温产生方法,温度更新函数,时齐算法的温度下降函数,（,1,），,越接近,1,温度下降越慢，且其大小可以不断变化；,（,2,），其中,t,0,为起始温度，,K,为算法温度下降的总次数。,温度更新函数,内循环终止准则，即,Metropolis,抽样稳定准则，用于决定在各温度下产生候选解的数目。,常用的抽样稳定准则包括：,(1),检验目标函数的均值是否稳定；,(2),连续若干步的目标值变化较小；,(3),按一定的步数抽样。,内循环终止准则，即Metropolis抽样稳定准则，用于决定,外循环终止准则，即算法的终止准则,模拟退火算法从初始温度开始，通过在每一温度的迭代和温度的下降，最后达到终止原则而停止。尽管有些原则有一定的理论指导，终止原则大多数是直观的。下面分几类讨论。,外循环终止准则，即算法的终止准则,(1),零度法,模拟退火算法的最终温度为零，因而最为简单的原则是：,给出一个较小的正数,，当温度小于这个数时，算法停止，表示已经达到最低温度。,模拟退火算法讲解课件,(2),循环总数控制法,这一原则为：总的下降次数为一定值,K,，当温度迭代次数达到,K,值时，停止运算。,(3),基于不改进规则的控制法,在一个温度和给定的迭代次数内设有改进当前的局部最优解，则停止运算。模拟退火算法的一个基本思想是跳出局部最优解，直观的结论是在较高的温度没能跳出局部最小解，则在低的温度跳出最优解的可能也比较小，由此产生上面的停止原则。,(2)循环总数控制法,(4),接受概率控制法,该方法与,(3),相同的思想。给定一个指针,P0,是一个比较小的数。除当前局部最优解以外，其它状态的接受概率都小于,P,时，停止计算。实现,(3),和,(4),时，记录当前局部最优解，给定一个固定的迭代次数，在规定的次数里没有离开局部最优解或每一次计算的接受概率都小于随机数,X,，就在这个温度停止迭代。,(4)接受概率控制法,模拟退火算法的优点,质量高；,初值鲁棒性强；,简单、通用、易实现。,模拟退火算法的缺点,由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,模拟退火算法的优点,TSP,城市坐标,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,TSP 城市坐标,模拟退火算法讲解课件,模拟退火算法讲解课件,模拟退火算法讲解课件,