模拟退火算法详解.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第二章 模拟退火算法,现代优化计算,1,3.1,模拟退火算法及模型,3.1.1,物理退火过程,3.1.2,组合优化与物理退火的相似性,3.1.3,模拟退火算法的基本思想和步骤,3.2,模拟退火算法的马氏链描述,3.2.1,马尔可夫链,3.2.2,模拟退火算法与马尔可夫链,3.3,模拟退火算法的关键参数和操作的设计,3.3.1,状态产生函数,3.3.2,状态接受函数,3.3.3,初温,3.3.4,温度更新函数,3.3.5,内循环终止准则,3.3.6,外循环终止准则,现代优化计算,2,3.4,模拟退火算法的改进,3.4.1,模拟退火算法的优缺点,3.4.2,改进内容,3.4.3,一种改进的模拟退火算法,3.5,模拟退火算法实现与应用,3.5.1 30,城市,TSP,问题（,d*=423.741 by D B Fogel,）,3.5.2,模拟退火算法在管壳式换热器优化设计中的应用,现代优化计算,3,3.1,模拟退火算法及模型,现代优化计算,算法的提出,模拟退火算法最早的思想由,Metropolis,等（,1953,）提出，,1983,年,Kirkpatrick,等将其应用于组合优化。,算法的目的,解决,NP,复杂性,问题；,克服优化过程陷入局部极小；,克服初值依赖性。,3.1.1,物理退火过程,4,3.1,模拟退火算法及模型,现代优化计算,物理退火过程,什么是退火：,退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。,3.1.1,物理退火过程,5,3.1,模拟退火算法及模型,现代优化计算,物理退火过程,加温过程,增强粒子的热运动，消除系统原先可能存在的非均匀态；,等温过程,对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；,冷却过程,使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。,3.1.1,物理退火过程,6,热力学中的退火现象指物体逐渐降温时发生的物理現象：,温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。缓慢降温（退火，,annealing,）时，可达到最低能量状态；但如果快速降温（淬火，,quenching,），会导致不是最低能态的非晶形。,大自然知道,慢工出细活,：,缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。,3.1,模拟退火算法及模型,3.1.1,物理退火过程,现代优化计算,7,模仿自然界退火現象而得，利用了物理中固体物质的,退火过程,与一般,优化,问题的相似性,从某一初始,温度,开始，伴随温度的不断下降，结合,概率突跳,特性在解空间中,随机,寻找,全局最优解,3.1,模拟退火算法及模型,3.1.1,物理退火过程,现代优化计算,8,3.1,模拟退火算法及模型,现代优化计算,数学表述,在温度,T,，分子停留在状态,r,满足,Boltzmann,概率分布,3.1.1,物理退火过程,9,3.1,模拟退火算法及模型,现代优化计算,数学表述,在,同一个温度,T,，选定两个能量,E,1,E,2,，有,3.1.1,物理退火过程,0,模拟退火算法基本思想,：在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率,1,停留在最优解,10,3.1,模拟退火算法及模型,3.1.1,物理退火过程,现代优化计算,Boltzman,概率分布,告诉我们：,（,1,）在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率,（,2,）温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。,（,3,）随着温度的下降，能量最低状态对应概率越来越大；温度趋于,0,时，其状态趋于,1,11,3.1,模拟退火算法及模型,现代优化计算,数学表述,若,|,D,|,为状态空间,D,中状态的个数，,D,0,是具有最低能量的状态集合：,当温度很高时，每个状态概率基本相同，接近平均值,1/|,D,|,；,状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值,1/|,D,|,；,当温度趋于,0,时，分子停留在最低能量状态的概率趋于,1,。,3.1.1,物理退火过程,能量最低状态 非能量最低状态,12,3.1,模拟退火算法及模型,现代优化计算,Metropolis,准则（,1953,）,以概率接受新状态,固体在恒定温度下达到热平衡的过程可以用,Monte Carlo,方法,（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,3.1.1,物理退火过程,13,3.1,模拟退火算法及模型,现代优化计算,Metropolis,准则（,1953,）,以概率接受新状态,若在温度,T,，当前状态,i,新状态,j,若,E,j,=randrom0,1,s,=,s,j,;,Until,抽样稳定准则满足；,退温,t,k,+1,=update(,t,k,),并令,k,=,k,+1,；,Until,算法终止准则满足；,输出算法搜索结果。,3.1.3,模拟退火算法的基本思想和步骤,17,3.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,算法终止准则满足；,输出算法搜索结果。,3.1.3,模拟退火算法的基本思想和步骤,三函数两准则,初始温度,18,3.1,模拟退火算法及模型,现代优化计算,3.1.3,模拟退火算法的基本思想和步骤,Step1,设定初始温度,t=tmax,任选初始解,r=r0,Step2,内循环,Step2.1,从,r,的邻域中随机选一个解,rt,计算,r,和,rt,对应目标函 数值,如,rt,对应目标函数值较小，则令,r=rt;,否则若,exp(-(E(rt)-E(r)/t)random(0,1),则令,r=rt.,Step2.2,不满足内循环停止条件时，重复,Step2.1,Step3,外循环,Step3.1,降温,t=decrease(t),Step3.2,如不满足外循环停止条件，则转,Step2,；否则算法结束,1.,达到终止温度,2.,达到迭代次数,3.,最优值连续若干步保持不变,1.,目标函数均值稳定,2.,连续若干步的目标值变化较小,3.,固定的抽样步数,模拟退火算法的步骤,19,3.2,模拟退火算法的马氏链描述,现代优化计算,定义,3.2.1,马尔科夫链,20,3.2,模拟退火算法的马氏链描述,现代优化计算,定义,一步转移概率：,n,步转移概率：,若解空间有限，称马尔可夫链为,有限状态,；,若 ，称马尔可夫链为,时齐的,。,3.2.1,马尔科夫链,21,3.2,模拟退火算法的马氏链描述,现代优化计算,模拟退火算法对应了一个马尔可夫链,模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。,若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为,时齐算法,；,若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为,非时齐算法,。,分析收敛性,3.2.2,模拟退火算法与马尔科夫链,22,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,原则,产生的候选解应遍布全部解空间,方法,在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生,3.3.1,状态产生函数,23,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,原则,(1),在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；,(2),随温度的下降，接受使目标函数上升的解的概率要逐渐减小；,(3),当温度趋于零时，只能接受目标函数下降的解。,方法,具体形式对算法影响不大,一般采用,min1,exp(-,C,/,t,),3.3.2,状态接受函数,24,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,收敛性分析,通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；,初温应充分大；,实验表明,初温越大，获得高质量解的机率越大，但花费较多的计算时间；,3.3.3,初温,25,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,方法,（,1,）均匀抽样一组状态，以各状态目标值得方差为初温；,（,2,）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；,（,3,）利用经验公式。,3.3.3,初温,26,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,时齐算法的温度下降函数,（,1,），,越接近,1,温度下降越慢，且其大小可以不断变化；,（,2,），其中,t,0,为起始温度，,K,为算法温度下降的总次数。,3.3.4,温度更新函数,27,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,非时齐模拟退火算法,每个温度下只产生一个或少量候选解,时齐算法,常用的,Metropolis,抽样稳定准则,（,1,）检验目标函数的均值是否稳定；,（,2,）连续若干步的目标值变化较小；,（,3,）按一定的步数抽样。,3.3.5,内循环终止准则,28,3.3,模拟退火算法关键参数和操作的设计,现代优化计算,常用方法,（,1,）设置终止温度的阈值；,（,2,）设置外循环迭代次数；,（,3,）算法搜索到的最优值连续若干步保持不变；,（,4,）概率分析方法。,3.3.6,外循环终止准则,29,3.4,模拟退火算法的改进,现代优化计算,模拟退火算法的优点,质量高；,初值鲁棒性强；,简单、通用、易实现。,模拟退火算法的缺点,由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,3.4.1,模拟退火算法的优缺点,30,3.4,模拟退火算法的改进,现代优化计算,改进的可行方案,（,1,）设计合适的状态产生函数；,（,2,）设计高效的退火历程；,（,3,）避免状态的迂回搜索；,（,4,）采用并行搜索结构；,（,5,）避免陷入局部极小，改进对温度的控制方式；,（,6,）选择合适的初始状态；,（,7,）设计合适的算法终止准则。,3.4.2,改进内容,31,3.4,模拟退火算法的改进,现代优化计算,改进的方式,（,1,）增加升温或重升温过程，避免陷入局部极小；,（,2,）增加记忆功能（记忆“,Best so far”,状态）；,（,3,）增加补充搜索过程（以最优结果为初始解）；,（,4,）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；,（,5,）结合其它搜索机制的算法；,（,6,）上述各方法的综合。,3.4.2,改进内容,32,3.4,模拟退火算法的改进,现代优化计算,改进的思路,（,1,）记录“,Best so far”,状态，并即时更新；,（,2,）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续,m,1,步保持不变则认为,Metropolis,抽样稳定，若连续,m,2,次退温过程中所得最优解不变则认为算法收敛。,3.4.3,一种改进的模拟退火算法,33,3.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,*,作为最终解输出，停止算法。,3.4.3,一种改进的模拟退火算法,34,3.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,),返回改进退火过程。,3.4.3,一种改进的模拟退火算法,35,3.5,模拟退火算法的实现与应用,现代优化计算,3.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,36,3.5,模拟退火算法的实现与应用,现代优化计算,算法流程,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,37,3.5,模拟退火算法的实现与应用,现代优化计算,初始温度的计算,for i=1:100,route=randperm(CityNum);,fval0(i)=CalDist(dislist,route);,end,t0=-(max(fval0)-min(fval0)/log(0.9);,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,38,3.5,模拟退火算法的实现与应用,现代优化计算,状态产生函数的设计,（,1,）互换操作，随机交换两个城市的顺序；,（,2,）逆序操作，两个随机位置间的城市逆序；,（,3,）插入操作，随机选择某点插入某随机位置。,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,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,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,39,3.5,模拟退火算法的实现与应用,现代优化计算,参数设定,截止温度,tf=0.01;,退温系数,alpha=0.90;,内循环次数,L=200*CityNum;,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,40,3.5,模拟退火算法的实现与应用,现代优化计算,运行过程,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,41,3.5,模拟退火算法的实现与应用,现代优化计算,运行过程,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,42,3.5,模拟退火算法的实现与应用,现代优化计算,运行过程,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,43,3.5,模拟退火算法的实现与应用,现代优化计算,运行过程,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,44,3.5,模拟退火算法的实现与应用,现代优化计算,运行过程,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,45,3.5,模拟退火算法的实现与应用,现代优化计算,运行结果,3.5.1 30,城市,TSP,问题（,d,*,=423.741 by D B Fogel,）,46,3.5,模拟退火算法的实现与应用,现代优化计算,换热器模型,两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰,(,谷,),的，具有很多局部最优解。,3.5.2,模拟退火算法在管壳式换热器优化设计中的应用,47,3.5,模拟退火算法的实现与应用,现代优化计算,优化目标,以换热器系统的总费用年值最小作为优化设计的目标。,其中，,f,1,(,X,),是两级换热器的初始投资，,f,2,(,X,),是两级换热器年维护费,(,包括除垢、保养、维修等,),，,f,3,(,X,),是冷却水资源费以及管程压降能耗费，,f,4,(,X,),是壳程压降能耗费。,3.5.2,模拟退火算法在管壳式换热器优化设计中的应用,48,3.5,模拟退火算法的实现与应用,现代优化计算,优化目标,经过分析，优化问题的独立变量共,12,个，分别是一级换热器煤油出口温度,t,2,、冷却水流量,G,1,、两个换热器的管内径,d,1,，,d,2,和管间距,S,1,，,S,2,、折流板间距,B,1,，,B,2,、折流板开口角,1,，,2,、单管长度,L,1,，,L,2,。,3.5.2,模拟退火算法在管壳式换热器优化设计中的应用,49,3.5,模拟退火算法的实现与应用,现代优化计算,应用模拟退火算法解决优化设计,状态表示,12,个变量的实数表示；,初始温度,100,；,结束温度,0.001,；,状态产生函数,，,为扰动幅度参数，,为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。,降温因子,0.98,；,马氏链长度,1200,。,3.5.2,模拟退火算法在管壳式换热器优化设计中的应用,50,3.5,模拟退火算法的实现与应用,现代优化计算,优化结果,优化目标值,0.25565E,06,独立变量取值,3.5.2,模拟退火算法在管壳式换热器优化设计中的应用,t,2,G,1,Kg/s,d,1,mm,S,1,mm,B,1,m,1,弧度,64.41941,5.97166,15.57163,34.09716,0.92436,1.93421,L,1,m,d,2,mm,S,2,mm,B,2,m,2,弧度,L,2,m,5.94234,16.77935,27.74012,0.72953,2.19928,5.78314,51,第三章 结束,现代优化计算,52,