模拟退火算法详解.pptx

模拟退火算法详解.pptx

《模拟退火算法详解.pptx》由会员分享，可在线阅读，更多相关《模拟退火算法详解.pptx（52页珍藏版）》请在冰点文库上搜索。

第二章模拟退火算法,现代优化计算,模拟退火算法及模型物理退火过程组合优化与物理退火的相似性模拟退火算法的基本思想和步骤模拟退火算法的马氏链描述马尔可夫链模拟退火算法与马尔可夫链模拟退火算法的关键参数和操作的设计状态产生函数状态接受函数初温温度更新函数内循环终止准则外循环终止准则,现代优化计算,模拟退火算法的改进模拟退火算法的优缺点改进内容一种改进的模拟退火算法模拟退火算法实现与应用30城市TSP问题（d*=423.741byDBFogel）模拟退火算法在管壳式换热器优化设计中的应用,现代优化计算,3.1模拟退火算法及模型,现代优化计算,算法的提出模拟退火算法最早的思想由Metropolis等（1953）提出，1983年Kirkpatrick等将其应用于组合优化。

算法的目的解决NP复杂性问题；克服优化过程陷入局部极小；克服初值依赖性。

3.1.1物理退火过程,3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程物理退火过程什么是退火：

退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。

3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程物理退火过程加温过程增强粒子的热运动，消除系统原先可能存在的非均匀态；等温过程对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；冷却过程使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。

3.1模拟退火算法及模型,3.1.1物理退火过程热力学中的退火现象指物体逐渐降温时发生的物理現象：

温度越低，物体的能量状态越低，到达足够的低点时，液体开始冷凝与结晶，在结晶状态时，系统的能量状态最低。

缓慢降温（退火，annealing）时，可达到最低能量状态；但如果快速降温（淬火，quenching），会导致不是最低能态的非晶形。

大自然知道慢工出细活：

缓缓降温，使得物体分子在每一温度时，能够有足够时间找到安顿位置，则逐渐地，到最后可得到最低能态，系统最稳定。

现代优化计算,3.1模拟退火算法及模型,3.1.1物理退火过程模仿自然界退火現象而得，利用了物理中固体物质的退火过程与一般优化问题的相似性从某一初始温度开始，伴随温度的不断下降，结合概率突跳特性在解空间中随机寻找全局最优解,现代优化计算,3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程数学表述在温度T，分子停留在状态r满足Boltzmann概率分布,3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程数学表述在同一个温度T，选定两个能量E1E2，有,1,0,模拟退火算法基本思想：

在一定温度下，搜索从一个状态随机地变化到另一个状态；随着温度的不断下降直到最低温度，搜索过程以概率1停留在最优解,3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程Boltzman概率分布告诉我们：

在同一个温度，分子停留在能量小状态的概率大于停留在能量大状态的概率温度越高，不同能量状态对应的概率相差越小；温度足够高时，各状态对应概率基本相同。

随着温度的下降，能量最低状态对应概率越来越大；温度趋于0时，其状态趋于1,数学表述若|D|为状态空间D中状态的个数，D0是具有最低能量的状态集合：

当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态的概率超出平均值1/|D|；当温度趋于0时，分子停留在最低能量状态的概率趋于1。

现代优化计算模拟退火算物理退火,法及模型过程,能量最低状态,非能量最低状态,3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程Metropolis准则（1953）以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。

3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程Metropolis准则（1953）以概率接受新状态若在温度T，当前状态i新状态j若EjEi，则接受j为当前状态；否则，若概率p=exp-（Ej-Ei）/kBT大于0,1）区间的随机数，则仍接受状态j为当前状态；若不成立则保留状态i为当前状态。

3.1模拟退火算法及模型,现代优化计算,3.1.1物理退火过程Metropolis准则（1953）以概率接受新状态p=exp-（Ej-Ei）/kBT在高温下，可接受与当前状态能量差较大的新状态；在低温下，只接受与当前状态能量差较小的新状态。

3.1模拟退火算法及模型,现代优化计算,3.1.2组合优化与物理退火的相似性相似性比较,3.1模拟退火算法及模型,现代优化计算,s=sj;,3.1.3模拟退火算法的基本思想和步骤基本步骤给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete（s）；ifmin1,exp-（C（sj）-C（s）/tk=randrom0,1Until抽样稳定准则满足；退温tk+1=update（tk）并令k=k+1；Until算法终止准则满足；输出算法搜索结果。

3.1模拟退火算法及模型,现代优化计算,s=sj;,影响优化结果的主要因素给定初温t=t0，随机产生初始状态s=s0，令k=0；RepeatRepeat产生新状态sj=Genete（s）；ifmin1,exp-（C（sj）-C（s）/tk=randrom0,1Until抽样稳定准则满足；,退温tk+1=update（tk）并令k=k+1；Until算法终止准则满足；输出算法搜索结果。

3.1.3模拟退火算法的基本思想和步骤,三函数两准则初始温度,3.1模拟退火算法及模型,现代优化计算,Step2内循环,Step3外循环Step3.1降温t=decrease（t）,Step3.2如不满足外循环停止条件，则转Step2；否则算法结束,达到迭代次数最优值连续若干步,保持不变,Step1设定初始温度t=tmax,任选初始解r=r01.目标函数均值稳定,2.连续若干步的目标,Step2.1从r的邻域中随机选一值个变解化较rt小,计算r和rt对应目标函数值,如rt对应目标函数值3较.固小定的，抽则样令步数r=rt;否则若exp（-（E（rt）-E（r）/t）random（0,1）,则令r=rt.Step2.2不满足内循环停止条件时1，.达重到复终止St温e度p2.1,3.1.3模拟退火算法的基本思想和步骤模拟退火算法的步骤,3.2模拟退火算法的马氏链描述,现代优化计算,3.2.1马尔科夫链定义,3.2模拟退火算法的马氏链描述,现代优化计算,3.2.1马尔科夫链定义一步转移概率：

n步转移概率：

若解空间有限，称马尔可夫链为有限状态；若，称马尔可夫链为时齐的。

3.2模拟退火算法的马氏链描述,现代优化计算,3.2.2模拟退火算法与马尔科夫链模拟退火算法对应了一个马尔可夫链模拟退火算法：

新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。

若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为非时齐算法。

分析收敛性,3.3模拟退火算法关键参数和操作的设计,现代优化计算,3.3.1状态产生函数原则产生的候选解应遍布全部解空间方法在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生,3.3模拟退火算法关键参数和操作的设计,现代优化计算,原则在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；随温度的下降，接受使目标函数上升的解的概率要逐渐减小；当温度趋于零时，只能接受目标函数下降的解。

方法具体形式对算法影响不大一般采用min1,exp（-C/t）,3.3.2状态接受函数,3.3模拟退火算法关键参数和操作的设计,现代优化计算,收敛性分析通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；初温应充分大；实验表明初温越大，获得高质量解的机率越大，但花费较多的计算时间；,3.3.3初温,3.3模拟退火算法关键参数和操作的设计,现代优化计算,3.3.3初温方法均匀抽样一组状态，以各状态目标值得方差为初温；随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；利用经验公式。

3.3模拟退火算法关键参数和操作的设计,现代优化计算,3.3.4温度更新函数时齐算法的温度下降函数，越接近1温度下降越慢，且其大小可以不断变化；，其中t0为起始温度，K为算法温度下降的总次数。

3.3模拟退火算法关键参数和操作的设计,现代优化计算,3.3.5内循环终止准则非时齐模拟退火算法每个温度下只产生一个或少量候选解时齐算法常用的Metropolis抽样稳定准则检验目标函数的均值是否稳定；连续若干步的目标值变化较小；按一定的步数抽样。

3.3模拟退火算法关键参数和操作的设计,现代优化计算,3.3.6外循环终止准则常用方法设置终止温度的阈值；设置外循环迭代次数；算法搜索到的最优值连续若干步保持不变；概率分析方法。

3.4模拟退火算法的改进,现代优化计算,模拟退火算法的优点质量高；初值鲁棒性强；简单、通用、易实现。

模拟退火算法的缺点由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。

3.4.1模拟退火算法的优缺点,3.4模拟退火算法的改进,现代优化计算,3.4.2改进内容改进的可行方案设计合适的状态产生函数；设计高效的退火历程；避免状态的迂回搜索；采用并行搜索结构；避免陷入局部极小，改进对温度的控制方式；选择合适的初始状态；设计合适的算法终止准则。

3.4模拟退火算法的改进,现代优化计算,3.4.2改进内容改进的方式增加升温或重升温过程，避免陷入局部极小；增加记忆功能（记忆“Bestsofar”状态）；增加补充搜索过程（以最优结果为初始解）；对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；结合其它搜索机制的算法；上述各方法的综合。

3.4模拟退火算法的改进,现代优化计算,3.4.3一种改进的模拟退火算法改进的思路记录“Bestsofar”状态，并即时更新；设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定，若连续m2次退温过程中所得最优解不变则认为算法收敛。

3.4模拟退火算法的改进,现代优化计算,3.4.3一种改进的模拟退火算法改进的退火过程给定初温t0，随机产生初始状态s，令初始最优解s*=s，当前状态为s（0）=s，i=p=0；令t=ti，以t，s*和s（i）调用改进的抽样过程，返回其所得最优解s*和当前状态s（k），令当前状态s（i）=s（k）；判断C（s*）m2?

若是，则转第（6）步；否则，返回第

（2）步；以最优解s*作为最终解输出，停止算法。

3.4模拟退火算法的改进,现代优化计算,3.4.3一种改进的模拟退火算法改进的抽样过程令k=0时的初始当前状态为s（0）=s（i），q=0；由状态s通过状态产生函数产生新状态s，计算增量C=C（s）-C（s）；若CC（s）?

若是，则令s*=s，q=0；否则，令q=q+1。

若C0，则以概率exp（-C/t）接受s作为下一当前状态；令k=k+1，判断qm1?

若是，则转第（5）步；否则，返回第

（2）步；将当前最优解s*和当前状态s（k）返回改进退火过程。

3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）TSPBenchmark问题4194;3784;5467;2562;764;299;6858;7144;5462;8369;6460;1854;2260;8346;9138;2538;2442;5869;7171;7478;8776;1840;1340;827;6232;5835;4521;4126;4435;450,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）算法流程,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）初始温度的计算fori=1:

100route=randperm（CityNum）;fval0（i）=CalDist（dislist,route）;endt0=-（max（fval0）-min（fval0）/log（0.9）;,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）状态产生函数的设计互换操作，随机交换两个城市的顺序；283591467281593467逆序操作，两个随机位置间的城市逆序；283591467283419567插入操作，随机选择某点插入某随机位置。

283591467235981467,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）参数设定截止温度tf=0.01;退温系数alpha=0.90;内循环次数L=200*CityNum;,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）运行过程,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）运行过程,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）运行过程,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）运行过程,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）运行过程,3.5模拟退火算法的实现与应用,现代优化计算,3.5.130城市TSP问题（d*=423.741byDBFogel）运行结果,3.5模拟退火算法的实现与应用,现代优化计算,3.5.2模拟退火算法在管壳式换热器优化设计中的应用换热器模型两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰（谷）的，具有很多局部最优解。

3.5模拟退火算法的实现与应用,现代优化计算,其中，f1（X）是两级换热器的初始投资，f2（X）是两级换热器年维护费（包括除垢、保养、维修等），f3（X）是冷却水资源费以及管程压降能耗费，f4（X）是壳程压降能耗费。

3.5.2模拟退火算法在管壳式换热器优化设计中的应用优化目标以换热器系统的总费用年值最小作为优化设计的目标。

3.5模拟退火算法的实现与应用,现代优化计算,3.5.2模拟退火算法在管壳式换热器优化设计中的应用优化目标经过分析，优化问题的独立变量共12个，分别是一级换热器煤油出口温度t2、冷却水流量G1、两个换热器的管内径d1，d2和管间距S1，S2、折流板间距B1，B2、折流板开口角1，2、单管长度L1，L2。

3.5模拟退火算法的实现与应用,现代优化计算,3.5.2模拟退火算法在管壳式换热器优化设计中的应用应用模拟退火算法解决优化设计状态表示12个变量的实数表示；初始温度100；结束温度0.001；状态产生函数，为扰动幅度参数，为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。

降温因子0.98；马氏链长度1200。

3.5模拟退火算法的实现与应用,现代优化计算,3.5.2模拟退火算法在管壳式换热器优化设计中的应用优化结果优化目标值0.25565E06独立变量取值,第三章结束,现代优化计算,