《第三章模拟退火算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第三章模拟退火算法精选PPT.ppt（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三章 模拟退火算法第1页，本讲稿共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程 3.1.2 3.1.2 组合优化与物理退火的相似性组合优化与物理退火的相似性组合优化与物理退火的相似性组合优化与物理退火的相似性 3.1.3 3.1.3 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤 3.2 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述 3.2.1
2、3.2.1 马尔可夫链马尔可夫链马尔可夫链马尔可夫链 3.2.2 3.2.2 模拟退火算法与马尔可夫链模拟退火算法与马尔可夫链模拟退火算法与马尔可夫链模拟退火算法与马尔可夫链 3.3 3.3 模拟退火算法的关键参数和操作的设计模拟退火算法的关键参数和操作的设计模拟退火算法的关键参数和操作的设计模拟退火算法的关键参数和操作的设计 3.3.1 3.3.1 状态产生函数状态产生函数状态产生函数状态产生函数 3.3.2 3.3.2 状态接受函数状态接受函数状态接受函数状态接受函数 3.3.3 3.3.3 初温初温初温初温 3.3.4 3.3.4 温度更新函数温度更新函数温度更新函数温度更新函数 3.3
3、.5 3.3.5 内循环终止准则内循环终止准则内循环终止准则内循环终止准则 3.3.6 3.3.6 外循环终止准则外循环终止准则外循环终止准则外循环终止准则 智能优化计算智能优化计算山东大学威海分校信息工程学院 2009年 第2页，本讲稿共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进 3.4.1 3.4.1 模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点 3.4.2 3.4.2 改进内容改进内容改进内容改进内容 3.4.3 3.4.3 一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的
4、模拟退火算法3.5 3.5 模拟退火算法实现与应用模拟退火算法实现与应用模拟退火算法实现与应用模拟退火算法实现与应用 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d*=423.741 by D B Fogeld*=423.741 by D B Fogel）3.5.2 3.5.2 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用智能优化计算智能优化计算山东大学威海分校信息工程学院 2009年 第3页，本讲稿共49页3.1 模拟退火算法及模
5、型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算w算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等（等（1953）提出，）提出，1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。w算法的目的算法的目的 解决解决NP复杂性复杂性问题；问题；克服优化过程陷入局部极小；克服优化过程陷入局部极小；克服初值依赖性。克服初值依赖性。3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程山东大学威海分校信息工程学院 2009年 第4页，本讲稿共49页3.1 模拟退火算法及模型模拟退火算
6、法及模型 智能优化计算智能优化计算w物理退火过程物理退火过程 什么是退火：什么是退火：退火是指将固体加热到足够高的温度，使分子呈随机排退火是指将固体加热到足够高的温度，使分子呈随机排列状态，然后逐步降温使之冷却，最后分子以低能状列状态，然后逐步降温使之冷却，最后分子以低能状态排列，固体达到某种稳定状态。态排列，固体达到某种稳定状态。3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程山东大学威海分校信息工程学院 2009年 第5页，本讲稿共49页3.1 模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算w物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动
7、，消除系统原先可能存在的增强粒子的热运动，消除系统原先可能存在的非均匀态；非均匀态；等温过程等温过程对于与环境换热而温度不变的封闭系统，系对于与环境换热而温度不变的封闭系统，系统状态的自发变化总是朝自由能减少的方向进行，当自统状态的自发变化总是朝自由能减少的方向进行，当自由能达到最小时，系统达到平衡态；由能达到最小时，系统达到平衡态；冷却过程冷却过程使粒子热运动减弱并渐趋有序，系统能使粒子热运动减弱并渐趋有序，系统能量逐渐下降，从而得到低能的晶体结构。量逐渐下降，从而得到低能的晶体结构。3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程山东大学威海分校信息工程学院 200
8、9年 第6页，本讲稿共49页3.1 模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算w数学表述数学表述 在温度在温度T，分子停留在状态，分子停留在状态r满足满足Boltzmann概率分布概率分布 3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程山东大学威海分校信息工程学院 2009年 第7页，本讲稿共49页3.1 模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算w数学表述数学表述 在在同一个温度同一个温度T，选定两个能量，选定两个能量E1E2，有，有 在同一个温度，分子停留在能量小的状态的概率比停留在能在同一个温度，分子停留在能量小的状态的概
9、率比停留在能量大的状态的概率要大。量大的状态的概率要大。3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程0山东大学威海分校信息工程学院 2009年 第8页，本讲稿共49页3.1 模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算w数学表述数学表述 若若|D|为状态空间为状态空间D中状态的个数，中状态的个数，D0是具有最低能量的状是具有最低能量的状态集合：态集合：当温度很高时，每个状态概率基本相同，接近平均值当温度很高时，每个状态概率基本相同，接近平均值1/|D|；状态空间存在超过两个不同能量时，具有最低能量状状态空间存在超过两个不同能量时，具有最低能量状态的
10、概率超出平均值态的概率超出平均值1/|D|；当温度趋于当温度趋于0时，分子停留在最低能量状态的概率趋于时，分子停留在最低能量状态的概率趋于1。3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程能量最低状态能量最低状态 非能量最低状态非能量最低状态山东大学威海分校信息工程学院 2009年 第9页，本讲稿共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算wMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用
11、Monte Carlo方方法法（计算机随机模拟方法）加以模拟，虽然该方法简（计算机随机模拟方法）加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，计算单，但必须大量采样才能得到比较精确的结果，计算量很大。量很大。3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程山东大学威海分校信息工程学院 2009年 第10页，本讲稿共49页3.1 模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算wMetropolis准则（准则（1953）以概率接受新状态以概率接受新状态 若在温度若在温度T，当前状态，当前状态i 新状态新状
12、态j 若若Ej=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。3.1.3 3.1.3 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤山东大学威海分校信息工程学院 2009年 第14页，本讲稿共49页3.1 3.1 模拟退火算法及模型模拟退火算法及模型 智能优化计算智能优化计算w影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温t=t0，随机产生
13、初始状态，随机产生初始状态s=s0，令，令k=0；Repeat Repeat 产生新状态产生新状态sj=Genete(s)；if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足；抽样稳定准则满足；退温退温tk+1=update(tk)并令并令k=k+1；Until 算法终止准则满足；算法终止准则满足；输出算法搜索结果。输出算法搜索结果。3.1.3 3.1.3 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤三函数两准则三函数两准则初始温度初始温度山东大学威海分校信息工程
14、学院 2009年 第15页，本讲稿共49页3.2 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述 智能优化计算智能优化计算w定义定义 3.2.1 3.2.1 马尔科夫链马尔科夫链马尔科夫链马尔科夫链特性：马氏链具有记忆遗忘特性，它只记忆前一时刻的状态。山东大学威海分校信息工程学院 2009年 第16页，本讲稿共49页3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述模拟退火算法的马氏链描述 智能优化计算智能优化计算w定义定义 一步转移概率：一步转移概率：n步转移概率：步转移概率：若解空间有限，称马尔可夫链为若解空间有限，称马尔可夫链为有限状态有限状态；若
15、若 ，称马尔可夫链为，称马尔可夫链为时齐的时齐的。3.2.1 3.2.1 马尔科夫链马尔科夫链马尔科夫链马尔科夫链山东大学威海分校信息工程学院 2009年 第17页，本讲稿共49页3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述 智能优化计算智能优化计算w模拟退火算法对应了一个马尔可夫链模拟退火算法对应了一个马尔可夫链 模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，模拟退火算法：新状态接受概率仅依赖于新状态和当前状态，并由温度加以控制。并由温度加以控制。若固定每一温度，算法均计算马氏链的变化直至平稳分布，若固定每一温度，算法均计算马氏链的变化直至平稳分布，然后下降温度，则称为然
16、后下降温度，则称为时齐算法时齐算法；若无需各温度下算法均达到平稳分布，但温度需按一定若无需各温度下算法均达到平稳分布，但温度需按一定速率下降，则称为速率下降，则称为非时齐算法非时齐算法。w分析收敛性分析收敛性 3.2.2 3.2.2 模拟退火算法与马尔科夫链模拟退火算法与马尔科夫链模拟退火算法与马尔科夫链模拟退火算法与马尔科夫链山东大学威海分校信息工程学院 2009年 第18页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算w原则原则 产生的候选解应遍布全部解空间产生的候选解应遍布全部解空间w方法方法 在当前状态的邻域结构内以一定
17、概率方式（均匀分布、在当前状态的邻域结构内以一定概率方式（均匀分布、正态分布、指数分布等）产生正态分布、指数分布等）产生 3.3.1 3.3.1 状态产生函数状态产生函数状态产生函数状态产生函数山东大学威海分校信息工程学院 2009年 第19页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算w原则原则 (1)在固定温度下，接受使目标函数下降的候选解的概在固定温度下，接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率；率要大于使目标函数上升的候选解概率；(2)随温度的下降，接受使目标函数上升的解的概率要逐渐随温度的下降
18、，接受使目标函数上升的解的概率要逐渐减小；减小；(3)当温度趋于零时，只能接受目标函数下降的解。当温度趋于零时，只能接受目标函数下降的解。w方法方法 具体形式对算法影响不大具体形式对算法影响不大 一般采用一般采用min1,exp(-C/t)3.3.2 3.3.2 状态接受函数状态接受函数状态接受函数状态接受函数山东大学威海分校信息工程学院 2009年 第20页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算w收敛性分析收敛性分析 通过理论分析可以得到初温的解析式，但解决实际问题时难通过理论分析可以得到初温的解析式，但解决实际问题时
19、难以得到精确的参数；以得到精确的参数；初温应充分大；初温应充分大；w实验表明实验表明 初温越大，获得高质量解的机率越大，但花费较多的初温越大，获得高质量解的机率越大，但花费较多的计算时间；计算时间；3.3.3 3.3.3 初温初温初温初温山东大学威海分校信息工程学院 2009年 第21页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算w方法方法 （1）均匀抽样一组状态，以各状态目标值的方差为）均匀抽样一组状态，以各状态目标值的方差为初温；初温；（2）随机产生一组状态，
20、确定两两状态间的最大目标）随机产生一组状态，确定两两状态间的最大目标值差，根据差值，利用一定的函数确定初温；值差，根据差值，利用一定的函数确定初温；（3）利用经验公式。）利用经验公式。3.3.3 3.3.3 初温初温初温初温山东大学威海分校信息工程学院 2009年 第22页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计数值计算估计方法示例智能优化计算智能优化计算山东大学威海分校信息工程学院 2009年 第23页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算w时齐算法的温度下降函数时齐算法
21、的温度下降函数 （1），越接近越接近1 1温度下降越慢，且其大小温度下降越慢，且其大小可以不断变化；可以不断变化；（2），其中，其中t0为起始温度，为起始温度，K为算法温度下降为算法温度下降的总次数。的总次数。3.3.4 3.3.4 温度更新函数温度更新函数温度更新函数温度更新函数山东大学威海分校信息工程学院 2009年 第24页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化计算智能优化计算w非时齐模拟退火算法非时齐模拟退火算法 每个温度下只产生一个或少量候选解每个温度下只产生一个或少量候选解w时齐算法时齐算法常用的常用的Metropolis抽
22、样稳定准则抽样稳定准则 （1）检验目标函数的均值是否稳定；）检验目标函数的均值是否稳定；（2）连续若干步的目标值变化较小；）连续若干步的目标值变化较小；（3）按一定的步数抽样（固定长度）。）按一定的步数抽样（固定长度）。（4）有接受和拒绝的比率控制跌代步数（比如给定一）有接受和拒绝的比率控制跌代步数（比如给定一个跌代步长上限个跌代步长上限U和接受比率指标和接受比率指标R）3.3.5 3.3.5 内循环终止准则内循环终止准则内循环终止准则内循环终止准则山东大学威海分校信息工程学院 2009年 第25页，本讲稿共49页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计智能优化
23、计算智能优化计算w常用方法常用方法 （1）设置终止温度的阈值；）设置终止温度的阈值；（2）设置外循环迭代次数；）设置外循环迭代次数；（3）算法搜索到的最优值连续若干步保持不变；）算法搜索到的最优值连续若干步保持不变；（4）概率分析方法）概率分析方法(接受概率控制法）。接受概率控制法）。3.3.6 3.3.6 外循环终止准则外循环终止准则外循环终止准则外循环终止准则山东大学威海分校信息工程学院 2009年 第26页，本讲稿共49页3.4 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算w模拟退火算法的优点模拟退火算法的优点 质量高；质量高；初值鲁棒性强；初值鲁棒性强；简单、通用、易实
24、现。简单、通用、易实现。w模拟退火算法的缺点模拟退火算法的缺点 由于要求较高的初始温度、较慢的降温速率、较低的由于要求较高的初始温度、较慢的降温速率、较低的终止温度，以及各温度下足够多次的抽样，因此优化终止温度，以及各温度下足够多次的抽样，因此优化过程较长。过程较长。3.4.1 3.4.1 模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点山东大学威海分校信息工程学院 2009年 第27页，本讲稿共49页3.4 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算w改进的可行方案改进的可行方案 （1）设计合适的状态产生函数；）设计合适的状态产生函数；（2）
25、设计高效的退火历程；）设计高效的退火历程；（3）避免状态的迂回搜索；）避免状态的迂回搜索；（4）采用并行搜索结构；）采用并行搜索结构；（5）避免陷入局部极小，改进对温度的控制方式；）避免陷入局部极小，改进对温度的控制方式；（6）选择合适的初始状态；）选择合适的初始状态；（7）设计合适的算法终止准则。）设计合适的算法终止准则。3.4.2 3.4.2 改进内容改进内容改进内容改进内容山东大学威海分校信息工程学院 2009年 第28页，本讲稿共49页3.4 3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算w改进的方式改进的方式 （1）增加升温或
26、重升温过程，避免陷入局部极小；）增加升温或重升温过程，避免陷入局部极小；（2）增加记忆功能（记忆）增加记忆功能（记忆“Best so far”状态）；状态）；（3）增加补充搜索过程（以最优结果为初始解）；）增加补充搜索过程（以最优结果为初始解）；（4）对每一当前状态，采用多次搜索策略，以概率接）对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态；受区域内的最优状态；（5）结合其它搜索机制的算法；）结合其它搜索机制的算法；（6）上述各方法的综合。）上述各方法的综合。3.4.2 3.4.2 改进内容改进内容改进内容改进内容山东大学威海分校信息工程学院 2009年 第29页，本讲稿共49页
27、3.4 模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算w改进的思路改进的思路 （1）记录）记录“Best so far”状态，并即时更新；状态，并即时更新；（2）设置双阈值，使得在尽量保持最优性的前提下减少计）设置双阈值，使得在尽量保持最优性的前提下减少计算量，即在各温度下当前状态连续算量，即在各温度下当前状态连续 m1 步保持不变则认为步保持不变则认为Metropolis抽样稳定，若连续抽样稳定，若连续 m2 次退温过程中所得最优次退温过程中所得最优解不变则认为算法收敛。解不变则认为算法收敛。3.4.3 3.4.3 一种改进的模拟退火算法一种
28、改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法山东大学威海分校信息工程学院 2009年 第30页，本讲稿共49页3.4 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算w改进的退火过程改进的退火过程 （1）给定初温）给定初温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*
29、)m2?若是，则转第若是，则转第(6)步；否则，返回第步；否则，返回第(2)步；步；（6）以最优解）以最优解s*作为最终解输出，停止算法。作为最终解输出，停止算法。3.4.3 3.4.3 一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法山东大学威海分校信息工程学院 2009年 第31页，本讲稿共49页3.4 模拟退火算法的改进模拟退火算法的改进智能优化计算智能优化计算w改进的抽样过程改进的抽样过程 （1）令）令k=0时的初始当前状态为时的初始当前状态为s(0)=s(i)，q=0；（2）由状态）由状态s通过状态产生函数产生新状态通过状态产生函数产生新状态s
30、，计算增量，计算增量C=C(s)-C(s)；（3）若）若C0，则接受，则接受s作为当前解，并判断作为当前解，并判断C(s)0，则以概率，则以概率exp(-C/t)接受接受s作为下一当前状态；作为下一当前状态；（4）令）令k=k+1，判断，判断qm1?若是，则转第若是，则转第(5)步；否则，返回第步；否则，返回第(2)步；步；（5）将当前最优解）将当前最优解s*和当前状态和当前状态s(k)返回改进退火过程。返回改进退火过程。3.4.3 3.4.3 一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法山东大学威海分校信息工程学院 2009年 第32页，本讲稿共4
31、9页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）wTSP 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;5
32、8 35;45 21;41 26;44 35;4 50山东大学威海分校信息工程学院 2009年 第33页，本讲稿共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w算法流程算法流程 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第34页，本讲稿共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能
33、优化计算w初始温度的计算初始温度的计算 for i=1:100 route=randperm(CityNum);fval0(i)=CalDist(dislist,route);end t0=-(max(fval0)-min(fval0)/log(0.9);3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第35页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w状态产生函数的设计
34、状态产生函数的设计 （1）互换操作，随机交换两个城市的顺序；）互换操作，随机交换两个城市的顺序；（2）逆序操作，两个随机位置间的城市逆序；）逆序操作，两个随机位置间的城市逆序；（3）插入操作，随机选择某点插入某随机位置。）插入操作，随机选择某点插入某随机位置。3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）283591467283591467283591467281593467283419567235981467山东大学威海分校信息工程学院 2009年 第36页，本
35、讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w参数设定参数设定 截止温度截止温度 tf=0.01;退温系数退温系数 alpha=0.90;内循环次数内循环次数 L=200*CityNum;3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第37页，本讲稿共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w运行过程运行过程 3.5.1
36、303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第38页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w运行过程运行过程 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年
37、第39页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w运行过程运行过程 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第40页，本讲稿共49页3.5 3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w运行过程运行过程 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B
38、Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第41页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w运行过程运行过程 3.5.1 303.5.1 30城市城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第42页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w运行结果运行结果 3.5.1 303.5.1 30城市
39、城市城市城市TSPTSP问题（问题（问题（问题（d d*=423.741 by D B Fogel=423.741 by D B Fogel）山东大学威海分校信息工程学院 2009年 第43页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w换热器模型换热器模型 两级管壳式换热器组成的换热器系统，数学模型高度非线两级管壳式换热器组成的换热器系统，数学模型高度非线性，其目标函数通常是多峰性，其目标函数通常是多峰(谷谷)的，具有很多局部最优解。的，具有很多局部最优解。3.5.2 3.5.2 模拟退火算法
40、在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院 2009年 第44页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w优化目标优化目标 以换热器系统的总费用年值最小作为优化设计的目标。以换热器系统的总费用年值最小作为优化设计的目标。其中，其中，f1(X)是两级换热器的初始投资，是两级换热器的初始投资，f2(X)是两级换是两级换热器年维护费热器年维护费(包括除垢、保养、维修等包括除垢、保养、维修等)，f3(X)是
41、冷却是冷却水资源费以及管程压降能耗费，水资源费以及管程压降能耗费，f4(X)是壳程压降能耗费。是壳程压降能耗费。3.5.2 3.5.2 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院 2009年 第45页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w优化目标优化目标 经过分析，优化问题的独立变量共经过分析，优化问题的独立变量共12个，分别是一级换热
42、个，分别是一级换热器煤油出口温度器煤油出口温度t2、冷却水流量、冷却水流量G1、两个换热器的管内、两个换热器的管内径径d1，d2和管间距和管间距S1，S2、折流板间距、折流板间距B1，B2、折流板开、折流板开口角口角1，2、单管长度、单管长度L1，L2。3.5.2 3.5.2 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院 2009年 第46页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w应用模
43、拟退火算法解决优化设计应用模拟退火算法解决优化设计 状态表示状态表示12个变量的实数表示；个变量的实数表示；初始温度初始温度100；结束温度结束温度0.001；状态产生函数状态产生函数 ，为扰动幅度参数，为扰动幅度参数，为随机扰动变量，随机扰动可服从柯西、高斯、均匀分为随机扰动变量，随机扰动可服从柯西、高斯、均匀分布。布。降温因子降温因子0.98；马氏链长度马氏链长度1200。3.5.2 3.5.2 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用山东大学威海分校信息工程学院
44、 2009年 第47页，本讲稿共49页3.5 模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用模拟退火算法的实现与应用智能优化计算智能优化计算w优化结果优化结果 优化目标值优化目标值0.25565E06 独立变量取值独立变量取值 3.5.2 3.5.2 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用t2G1Kg/sd1mmS1mmB1m1弧度64.419415.9716615.5716334.097160.924361.93421L1md2mmS2mmB2m2弧度L2m5.9423416.7793527.740120.729532.199285.78314山东大学威海分校信息工程学院 2009年 第48页，本讲稿共49页第三章第三章 结束结束智能优化计算智能优化计算山东大学威海分校信息工程学院 2009年 第49页，本讲稿共49页