数学建模模拟退火算法.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 模拟退火算法,智能优化计算,浙江大学,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 外循环终止准则,智能优化计算,浙江大学,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.1 模拟退火算法及模型,智能优化计算,浙江大学,算法的提出,模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。,算法的目的,解决,NP复杂性,问题；,克服优化过程陷入局部极小；,克服初值依赖性。,3.1.1 物理退火过程,3.1 模拟退火算法及模型,智能优化计算,浙江大学,数学表述,在温度,T,，分子停留在状态,r,满足Boltzmann概率分布,3.1.1 物理退火过程,3.1 模拟退火算法及模型,智能优化计算,浙江大学,数学表述,在,同一个温度,T,，选定两个能量,E,1,E,2,，有,在同一个温度，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。,3.1.1 物理退火过程,0,3.1 模拟退火算法及模型,智能优化计算,浙江大学,数学表述,若|,D,|为状态空间,D,中状态的个数，,D,0,是具有最低能量的状态集合：,当温度很高时，每个状态概率基本相同，接近平均值1/|,D,|；,状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|,D,|；,当温度趋于0时，分子停留在最低能量状态的概率趋于1。,3.1.1 物理退火过程,能量最低状态 非能量最低状态,3.1 模拟退火算法及模型,智能优化计算,浙江大学,Metropolis准则（1953）以概率接受新状态,固体在恒定温度下达到热平衡的过程可以用,Monte Carlo方法,（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。,3.1.1 物理退火过程,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 模拟退火算法的基本思想和步骤,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 模拟退火算法的基本思想和步骤,三函数两准则,初始温度,3.2 模拟退火算法的马氏链描述,智能优化计算,浙江大学,定义,3.2.1 马尔科夫链,3.2 模拟退火算法的马氏链描述,智能优化计算,浙江大学,定义,一步转移概率：,n,步转移概率：,若解空间有限，称马尔可夫链为,有限状态,；,若 ，称马尔可夫链为,时齐的,。,3.2.1 马尔科夫链,3.2 模拟退火算法的马氏链描述,智能优化计算,浙江大学,模拟退火算法对应了一个马尔可夫链,模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。,若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为,时齐算法,；,若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为,非时齐算法,。,分析收敛性,3.2.2 模拟退火算法与马尔科夫链,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,原则,产生的候选解应遍布全部解空间,方法,在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生,3.3.1 状态产生函数,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,原则,(1)在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；,(2)随温度的下降，接受使目标函数上升的解的概率要逐渐减小；,(3)当温度趋于零时，只能接受目标函数下降的解。,方法,具体形式对算法影响不大,一般采用min1,exp(-,C,/,t,),3.3.2 状态接受函数,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,收敛性分析,通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；,初温应充分大；,实验表明,初温越大，获得高质量解的机率越大，但花费较多的计算时间；,3.3.3 初温,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,方法,（1）均匀抽样一组状态，以各状态目标值得方差为初温；,（2）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；,（3）利用经验公式。,3.3.3 初温,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,时齐算法的温度下降函数,（1），,越接近1温度下降越慢，且其大小可以不断变化；,（2），其中,t,0,为起始温度，,K,为算法温度下降的总次数。,3.3.4 温度更新函数,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,非时齐模拟退火算法,每个温度下只产生一个或少量候选解,时齐算法常用的Metropolis抽样稳定准则,（1）检验目标函数的均值是否稳定；,（2）连续若干步的目标值变化较小；,（3）按一定的步数抽样。,3.3.5 内循环终止准则,3.3 模拟退火算法关键参数和操作的设计,智能优化计算,浙江大学,常用方法,（1）设置终止温度的阈值；,（2）设置外循环迭代次数；,（3）算法搜索到的最优值连续若干步保持不变；,（4）概率分析方法。,3.3.6 外循环终止准则,3.4 模拟退火算法的改进,智能优化计算,浙江大学,模拟退火算法的优点,质量高；,初值鲁棒性强；,简单、通用、易实现。,模拟退火算法的缺点,由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。,3.4.1 模拟退火算法的优缺点,3.4 模拟退火算法的改进,智能优化计算,浙江大学,改进的可行方案,（1）设计合适的状态产生函数；,（2）设计高效的退火历程；,（3）避免状态的迂回搜索；,（4）采用并行搜索结构；,（5）避免陷入局部极小，改进对温度的控制方式；,（6）选择合适的初始状态；,（7）设计合适的算法终止准则。,3.4.2 改进内容,3.4 模拟退火算法的改进,智能优化计算,浙江大学,改进的方式,（1）增加升温或重升温过程，避免陷入局部极小；,（2）增加记忆功能（记忆“Best so far”状态）；,（3）增加补充搜索过程（以最优结果为初始解）；,（4）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；,（5）结合其它搜索机制的算法；,（6）上述各方法的综合。,3.4.2 改进内容,3.4 模拟退火算法的改进,智能优化计算,浙江大学,改进的思路,（1）记录“Best so far”状态，并即时更新；,（2）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续,m,1,步保持不变则认为Metropolis抽样稳定，若连续,m,2,次退温过程中所得最优解不变则认为算法收敛。,3.4.3 一种改进的模拟退火算法,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 一种改进的模拟退火算法,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 一种改进的模拟退火算法,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,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,算法流程,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,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）,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,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,参数设定,截止温度 tf=0.01;,退温系数 alpha=0.90;,内循环次数 L=200*CityNum;,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,运行过程,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,运行过程,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,运行过程,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,运行过程,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,运行过程,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,运行结果,3.5.1 30城市TSP问题（,d,*,=423.741 by D B Fogel）,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,换热器模型,两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰(谷)的，具有很多局部最优解。,3.5.2 模拟退火算法在管壳式换热器优化设计中的应用,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,优化目标,以换热器系统的总费用年值最小作为优化设计的目标。,其中，,f,1,(,X,)是两级换热器的初始投资，,f,2,(,X,)是两级换热器年维护费(包括除垢、保养、维修等)，,f,3,(,X,)是冷却水资源费以及管程压降能耗费，,f,4,(,X,)是壳程压降能耗费。,3.5.2 模拟退火算法在管壳式换热器优化设计中的应用,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 模拟退火算法在管壳式换热器优化设计中的应用,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,应用模拟退火算法解决优化设计,状态表示12个变量的实数表示；,初始温度100；,结束温度0.001；,状态产生函数 ，,为扰动幅度参数，,为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。,降温因子0.98；,马氏链长度1200。,3.5.2 模拟退火算法在管壳式换热器优化设计中的应用,3.5 模拟退火算法的实现与应用,智能优化计算,浙江大学,优化结果,优化目标值0.25565E06,独立变量取值,3.5.2 模拟退火算法在管壳式换热器优化设计中的应用,第三章 结束,智能优化计算,浙江大学,