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

《数学建模模拟退火算法.pptx》由会员分享，可在线阅读，更多相关《数学建模模拟退火算法.pptx（49页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 物理退火过程物理退火过程物理退火过程物理退火过程 组合优化与物理退火的相似性组合优化与物理退火的相似性组合优化与物理退火的相似性组合优化与物理退火的相似性 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤 3.2 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述 马尔可夫链马尔可夫链马尔可夫链马尔可夫链 模拟退火算法与马尔可夫链模拟退火算法与马尔可夫链模拟退火算法与马尔可

2、夫链模拟退火算法与马尔可夫链 3.3 3.3 模拟退火算法的关键参数和操作的设模拟退火算法的关键参数和操作的设模拟退火算法的关键参数和操作的设模拟退火算法的关键参数和操作的设计计计计 状态产生函数状态产生函数状态产生函数状态产生函数 状态接受函数状态接受函数状态接受函数状态接受函数 初温初温初温初温 温度更新函数温度更新函数温度更新函数温度更新函数 内循环终止准则内循环终止准则内循环终止准则内循环终止准则 外循环终止准则外循环终止准则外循环终止准则外循环终止准则 智能优化计算智能优化计算浙江大学第2页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的

3、改进 模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点 改进内容改进内容改进内容改进内容 一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法3.5 3.5 模拟退火算法实现与应用模拟退火算法实现与应用模拟退火算法实现与应用模拟退火算法实现与应用 城市城市城市城市TSPTSP问题（问题（问题（问题（d*=423.741 by D B Fogeld*=423.741 by D B Fogel）模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法

4、在管壳式换热器优化设计中的应用智能优化计算智能优化计算浙江大学第3页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学w算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等（等（1953）提出，提出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。w算法的目的算法的目的 解决解决NP复杂性复杂性问题；问题；克服优化过程陷入局部极小；克服优化过程陷入局部极小；克服初值依赖性。克服初值依赖性。物理退火过程物理退火过程物理退火过程物理退火过程第4页/

5、共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学w物理退火过程物理退火过程 什么是退火：什么是退火：退火是指将固体加热到足够高的温度，使分子呈随退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以机排列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。低能状态排列，固体达到某种稳定状态。物理退火过程物理退火过程物理退火过程物理退火过程第5页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能

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

7、过程物理退火过程第6页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学w数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分概率分布布 物理退火过程物理退火过程物理退火过程物理退火过程第7页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学w数学表述数学表述 在在同一个温度同一个温度T，选定两个能量，选定两个能量E1E2，有，有 在同一个温度，分子停留在能量小的状态的概率比在同一个温度

8、，分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。停留在能量大的状态的概率要大。物理退火过程物理退火过程物理退火过程物理退火过程0第8页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学w数学表述数学表述 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具有最低能是具有最低能量的状态集合：量的状态集合：当温度很高时，每个状态概率基本相同，接近平均当温度很高时，每个状态概率基本相同，接近平均值值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状态空间存在超过两个不同能量时，具有

9、最低能量状态的概率超出平均值状态的概率超出平均值1/|D|；当温度趋于当温度趋于0时，分子停留在最低能量状态的概率时，分子停留在最低能量状态的概率趋于趋于1。物理退火过程物理退火过程物理退火过程物理退火过程能量最低状态能量最低状态 非能量最低状态非能量最低状态第9页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学wMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法方法（计算机随机模拟方

10、法）加以模拟，虽（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确然该方法简单，但必须大量采样才能得到比较精确的结果，计算量很大。的结果，计算量很大。物理退火过程物理退火过程物理退火过程物理退火过程第10页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学wMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，当前状态，当前状态i 新状态新状态j 若若Ej=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温

11、tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤第14页/共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算浙江大学w影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温t=t0，随机产生初始状态，随机产生初始状态s=s0，令，令k=0；Repeat Repeat 产生新状态产生新状态sj=Genete(s)；if m

12、in1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤三函数两准则三函数两准则初始温度初始温度第15页/共49页3.2 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述 智能优化计算智能优化计算浙江大学w定义定义 马尔

13、科夫链马尔科夫链马尔科夫链马尔科夫链第16页/共49页3.2 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述 智能优化计算智能优化计算浙江大学w定义定义 一步转移概率：一步转移概率：n步转移概率：步转移概率：若解空间有限，称马尔可夫链为若解空间有限，称马尔可夫链为有限状态有限状态；若若 ，称马尔可夫链为，称马尔可夫链为时齐的时齐的。马尔科夫链马尔科夫链马尔科夫链马尔科夫链第17页/共49页3.2 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述 智能优化计算智能优化计算浙江大学w模

14、拟退火算法对应了一个马尔可夫链模拟退火算法对应了一个马尔可夫链 模拟退火算法：新状态接受概率仅依赖于新状态和模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。当前状态，并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为稳分布，然后下降温度，则称为时齐算法时齐算法；若无需各温度下算法均达到平稳分布，但温度需按若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为一定速率下降，则称为非时齐算法非时齐算法。w分析收敛性分析收敛性 模拟退火算法与马尔科夫链模拟退火算法与马尔科夫链模拟退火

15、算法与马尔科夫链模拟退火算法与马尔科夫链第18页/共49页3.3 3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w原则原则 产生的候选解应遍布全部解空间产生的候选解应遍布全部解空间w方法方法 在当前状态的邻域结构内以一定概率方式（均匀分在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生布、正态分布、指数分布等）产生 状态产生函数状态产生函数状态产生函数状态产生函数第19页/共49页3.3 3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和

16、操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w原则原则 (1)在固定温度下，接受使目标函数下降的候选解的在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；概率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率随温度的下降，接受使目标函数上升的解的概率要逐渐减小；要逐渐减小；(3)当温度趋于零时，只能接受目标函数下降的解。当温度趋于零时，只能接受目标函数下降的解。w方法方法 具体形式对算法影响不大具体形式对算法影响不大 一般采用一般采用min1,exp(-C/t)状态接受函

17、数状态接受函数状态接受函数状态接受函数第20页/共49页3.3 3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w收敛性分析收敛性分析 通过理论分析可以得到初温的解析式，但解决实际通过理论分析可以得到初温的解析式，但解决实际问题时难以得到精确的参数；问题时难以得到精确的参数；初温应充分大；初温应充分大；w实验表明实验表明 初温越大，获得高质量解的机率越大，但花费较多初温越大，获得高质量解的机率越大，但花费较多的计算时间；的计算时间；初温初温初温初温第21页/共49页3.3 3

18、.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w方法方法 （1）均匀抽样一组状态，以各状态目标值得方差）均匀抽样一组状态，以各状态目标值得方差为初温；为初温；（2）随机产生一组状态，确定两两状态间的最大）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；目标值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。）利用经验公式。初温初温初温初温第22页/共49页3.3 3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计

19、模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w时齐算法的温度下降函数时齐算法的温度下降函数 （1），越接近越接近1 1温度下降越慢，温度下降越慢，且其大小可以不断变化；且其大小可以不断变化；（2），其中，其中t0为起始温度，为起始温度，K为算法温度下为算法温度下降的总次数。降的总次数。温度更新函数温度更新函数温度更新函数温度更新函数第23页/共49页3.3 3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w非时齐模拟退火算法

20、非时齐模拟退火算法 每个温度下只产生一个或少量候选解每个温度下只产生一个或少量候选解w时齐算法时齐算法常用的常用的Metropolis抽样稳定准则抽样稳定准则 （1）检验目标函数的均值是否稳定；）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；）连续若干步的目标值变化较小；（3）按一定的步数抽样。）按一定的步数抽样。内循环终止准则内循环终止准则内循环终止准则内循环终止准则第24页/共49页3.3 3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算浙江大学w常用方法常用方法

21、 （1）设置终止温度的阈值；）设置终止温度的阈值；（2）设置外循环迭代次数；）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法。）概率分析方法。外循环终止准则外循环终止准则外循环终止准则外循环终止准则第25页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算浙江大学w模拟退火算法的优点模拟退火算法的优点 质量高；质量高；初值鲁棒性强；初值鲁棒性强；简单、通用、易实现。简单、通用、易实现。w模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、

22、较慢的降温速率、较低由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此的终止温度，以及各温度下足够多次的抽样，因此优化过程较长。优化过程较长。模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点第26页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算浙江大学w改进的可行方案改进的可行方案 （1）设计合适的状态产生函数；）设计合适的状态产生函数；（2）设计高效的退火历程；）设计高效的退火历程；（3）避免状态的迂回搜索；）避免状态的迂回搜索；（4）采用并行搜索

23、结构；）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；）选择合适的初始状态；（7）设计合适的算法终止准则。）设计合适的算法终止准则。改进内容改进内容改进内容改进内容第27页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算浙江大学w改进的方式改进的方式 （1）增加升温或重升温过程，避免陷入局部极小；）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆）增加记忆功能（记忆“Best so far”状态）；状态）；（3）增加补充

24、搜索过程（以最优结果为初始解）；）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；接受区域内的最优状态；（5）结合其它搜索机制的算法；）结合其它搜索机制的算法；（6）上述各方法的综合。）上述各方法的综合。改进内容改进内容改进内容改进内容第28页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算浙江大学w改进的思路改进的思路 （1）记录）记录“Best so far”状态，并即时更新；状态，并即时更新；（2）设置双阈值，使得

25、在尽量保持最优性的前提下）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续减少计算量，即在各温度下当前状态连续 m1 步保持步保持不变则认为不变则认为Metropolis抽样稳定，若连续抽样稳定，若连续 m2 次退温次退温过程中所得最优解不变则认为算法收敛。过程中所得最优解不变则认为算法收敛。一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法第29页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算浙江大学w改进的退火过程改进的退火过程 （1）给定初温）给定

26、初温t0，随机产生初始状态，随机产生初始状态s，令初始最优解，令初始最优解s*=s，当前状态为当前状态为s(0)=s，i=p=0；（2）令）令t=ti，以，以t，s*和和s(i)调用改进的抽样过程，返回其所得调用改进的抽样过程，返回其所得最优解最优解s*和当前状态和当前状态s(k)，令当前状态，令当前状态s(i)=s(k)；（3）判断）判断C(s*)m2?若是，则转第若是，则转第(6)步；否则，返回第步；否则，返回第(2)步；步；（6）以最优解）以最优解s*作为最终解输出，停止算法。作为最终解输出，停止算法。一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算

27、法第30页/共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算浙江大学w改进的抽样过程改进的抽样过程 （1）令）令k=0时的初始当前状态为时的初始当前状态为s(0)=s(i)，q=0；（2）由状态）由状态s通过状态产生函数产生新状态通过状态产生函数产生新状态s，计算增量，计算增量C=C(s)-C(s)；（3）若）若CC(s)?若是，则令若是，则令s*=s，q=0；否则，令；否则，令q=q+1。若。若C0，则以，则以概率概率exp(-C/t)接受接受s作为下一当前状态；作为下一当前状态；（4）令）令k=k+1，判断，判断qm1

28、?若是，则转第若是，则转第(5)步；否则，返回步；否则，返回第第(2)步；步；（5）将当前最优解）将当前最优解s*和当前状态和当前状态s(k)返回改进退火过程。返回改进退火过程。一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法第31页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学 城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）wTSP Benchma

29、rk 问题问题 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第32页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w算法流程算法流程 城市城市城市城市TSPTSP问题（问题（问题（问题（

30、d d*=423.741 by D B Fogel=423.741 by D B Fogel）第33页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w初始温度的计算初始温度的计算 for i=1:100 route=randperm(CityNum);fval0(i)=CalDist(dislist,route);end t0=-(max(fval0)-min(fval0)/log(0.9);城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fo

31、gel=423.741 by D B Fogel）第34页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w状态产生函数的设计状态产生函数的设计 （1）互换操作，随机交换两个城市的顺序；）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。）插入操作，随机选择某点插入某随机位置。城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=42

32、3.741 by D B Fogel）283591467283591467283591467281593467283419567235981467第35页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w参数设定参数设定 截止温度截止温度 tf=0.01;退温系数退温系数 alpha=0.90;内循环次数内循环次数 L=200*CityNum;城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第

33、36页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w运行过程运行过程 城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第37页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w运行过程运行过程 城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B

34、Fogel=423.741 by D B Fogel）第38页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w运行过程运行过程 城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第39页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w运行过程运行过程 城市城市城市城市TSPTSP问题（问

35、题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第40页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w运行过程运行过程 城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第41页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学

36、w运行结果运行结果 城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）第42页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w换热器模型换热器模型 两级管壳式换热器组成的换热器系统，数学模型高两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰度非线性，其目标函数通常是多峰(谷谷)的，具有很的，具有很多局部最优解。多局部最优解。模拟退火算法在管壳式换热器优化设计中的应用模

37、拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用第43页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w优化目标优化目标 以换热器系统的总费用年值最小作为优化设计的目以换热器系统的总费用年值最小作为优化设计的目标。标。其中，其中，f1(X)是两级换热器的初始投资，是两级换热器的初始投资，f2(X)是两是两级换热器年维护费级换热器年维护费(包括除垢、保养、维修等包括除垢、保养、维修等)，f3(X)是冷却水资源费以及

38、管程压降能耗费，是冷却水资源费以及管程压降能耗费，f4(X)是是壳程压降能耗费。壳程压降能耗费。模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用第44页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w优化目标优化目标 经过分析，优化问题的独立变量共经过分析，优化问题的独立变量共12个，分别是一个，分别是一级换热器煤油出口温度级换热器煤油出口温度t2、冷却水流量、冷却水流

39、量G1、两个换热、两个换热器的管内径器的管内径d1，d2和管间距和管间距S1，S2、折流板间距、折流板间距B1，B2、折流板开口角、折流板开口角1，2、单管长度、单管长度L1，L2。模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用第45页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算浙江大学w应用模拟退火算法解决优化设计应用模拟退火算法解决优化设计 状态表示状态表示12个变量的

40、实数表示；个变量的实数表示；初始温度初始温度100；结束温度结束温度0.001；状态产生函数状态产生函数 ，为扰动幅度参数，为扰动幅度参数，为随机扰动变量，随机扰动可服从柯西、高斯、均为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。匀分布。降温因子降温因子0.98；马氏链长度马氏链长度1200。模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用第46页/共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智

41、能优化计算智能优化计算浙江大学w优化结果优化结果 优化目标值优化目标值0.25565E06 独立变量取值独立变量取值 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用t2G1Kg/sd1mmS1mmB1m1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2m2弧度L2m5.9423416.7793527.740120.729532.199285.78314第47页/共49页第三章第三章 结束结束智能优化计算智能优化计算浙江大学第48页/共49页感谢您的观看！第49页/共49页