模拟退火算法详解优秀PPT.ppt
《模拟退火算法详解优秀PPT.ppt》由会员分享,可在线阅读,更多相关《模拟退火算法详解优秀PPT.ppt(51页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、模拟退火算法详解你现在浏览的是第一页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 3.1.1 3.1.1 物理退火过程物理退火过程物理退火过程物理退火过程 3.1.2 3.1.2 组合优化与物理退火的相似性组合优化与物理退火的相似性组合优化与物理退火的相似性组合优化与物理退火的相似性 3.1.3 3.1.3 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤 3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述 3.2.1 3.2.1 马尔可夫链马尔可夫链马尔可夫链马尔可夫链 3.2.2 3.2.2 模拟退火算法与马尔
2、可夫链模拟退火算法与马尔可夫链模拟退火算法与马尔可夫链模拟退火算法与马尔可夫链 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.5 3.3.5 内循环终止准则内循环终止准则内循环终止准则内循环终止准则 3.3.6 3.3.6 外循环终止准则外循环终止准则外循环终止准则外循环终止准则 现代优化计算现
3、代优化计算你现在浏览的是第二页,共51页3.4 模拟退火算法的改进模拟退火算法的改进 3.4.1 3.4.1 模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点模拟退火算法的优缺点 3.4.2 3.4.2 改进内容改进内容改进内容改进内容 3.4.3 3.4.3 一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法一种改进的模拟退火算法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
4、.2 3.5.2 模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用模拟退火算法在管壳式换热器优化设计中的应用现代优化计算现代优化计算你现在浏览的是第三页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算w算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等(等(1953)提)提出,出,1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。w算法的目的算法的目的 解决解决NP复杂性复杂性问题;问题;克服优化过程陷入局部极小;克
5、服优化过程陷入局部极小;克服初值依赖性。克服初值依赖性。3.1.1 物理退火过程物理退火过程你现在浏览的是第四页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算w物理退火过程物理退火过程 什么是退火:什么是退火:退火是指将固体加热到足够高的温度,使分子呈随机退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,最后分子以低能排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。状态排列,固体达到某种稳定状态。3.1.1 物理退火过程物理退火过程你现在浏览的是第五页,共51页3.1 模拟退火算法及模型模拟退火算法及模
6、型 现代优化计算现代优化计算w物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动,消除系统原先可能增强粒子的热运动,消除系统原先可能存在的非均匀态;存在的非均匀态;等温过程等温过程对于与环境换热而温度不变的封闭系统,对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;自由能达到最小时,系统达到平衡态;冷却过程冷却过程使粒子热运动减弱并渐趋有序,系统能使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。量逐渐下降,从而得到低能的晶体结构。3.1.1 物理退火
7、过程物理退火过程你现在浏览的是第六页,共51页w热力学中的退火现象指物体逐渐降温时发生的物理热力学中的退火现象指物体逐渐降温时发生的物理現象:現象:温度越低,物体的能量状态越低,到达足够的低点时,温度越低,物体的能量状态越低,到达足够的低点时,液体开始冷凝与结晶,在结晶状态时,系统的能量状液体开始冷凝与结晶,在结晶状态时,系统的能量状态最低。缓慢降温(退火,态最低。缓慢降温(退火,annealing)时,可达到最)时,可达到最低能量状态;但如果快速降温(淬火,低能量状态;但如果快速降温(淬火,quenching),),会导致不是最低能态的非晶形。会导致不是最低能态的非晶形。w大自然知道大自然知
8、道慢工出细活慢工出细活:缓缓降温,使得物体分子在每一温度时,能够有足够缓缓降温,使得物体分子在每一温度时,能够有足够时间找到安顿位置,则逐渐地,到最后可得到最低能时间找到安顿位置,则逐渐地,到最后可得到最低能态,系统最稳定。态,系统最稳定。3.1 模拟退火算法及模型模拟退火算法及模型 3.1.1 物理退火过程物理退火过程现代优化计算现代优化计算你现在浏览的是第七页,共51页w模仿自然界退火現象而得,利用了物理中固体物质的模仿自然界退火現象而得,利用了物理中固体物质的退火过程退火过程与一般与一般优化优化问题的相似性问题的相似性 从某一初始从某一初始温度温度开始,伴随温度的不断下降,结合开始,伴随
9、温度的不断下降,结合概概率突跳率突跳特性在解空间中特性在解空间中随机随机寻找寻找全局最优解全局最优解3.1 模拟退火算法及模型模拟退火算法及模型 3.1.1 物理退火过程物理退火过程现代优化计算现代优化计算你现在浏览的是第八页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算w数学表述数学表述 在温度在温度T,分子停留在状态,分子停留在状态r满足满足Boltzmann概率分布概率分布 3.1.1 物理退火过程物理退火过程你现在浏览的是第九页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算w数学表述数学表述 在在同一个温度同一个温度T
10、,选定两个能量,选定两个能量E1E2,有,有 3.1.1 物理退火过程物理退火过程0模拟退火算法基本思想模拟退火算法基本思想:在一定温度下,搜索从一个状态随机地:在一定温度下,搜索从一个状态随机地变化到另一个状态;随着温度的不断下降直到最低温度,搜索过程以概变化到另一个状态;随着温度的不断下降直到最低温度,搜索过程以概率率1停留在最优解停留在最优解你现在浏览的是第十页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 3.1.1 物理退火过程物理退火过程现代优化计算现代优化计算wBoltzmanBoltzman概率分布概率分布告诉我们:告诉我们:(1)在同一个温度,分子停留在能量小状态的概
11、率)在同一个温度,分子停留在能量小状态的概率大于停留在能量大状态的概率大于停留在能量大状态的概率 (2)温度越高,不同能量状态对应的概率相差越小;温度)温度越高,不同能量状态对应的概率相差越小;温度足够高时,各状态对应概率基本相同。足够高时,各状态对应概率基本相同。(3)随着温度的下降,能量最低状态对应概率越来越大;)随着温度的下降,能量最低状态对应概率越来越大;温度趋于温度趋于0时,其状态趋于时,其状态趋于1你现在浏览的是第十一页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算w数学表述数学表述 若若|D|为状态空间为状态空间D中状态的个数,中状态的个数,D0
12、是具有最低能量是具有最低能量的状态集合:的状态集合:当温度很高时,每个状态概率基本相同,接近平均值当温度很高时,每个状态概率基本相同,接近平均值1/|D|;状态空间存在超过两个不同能量时,具有最低能量状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值状态的概率超出平均值1/|D|;当温度趋于当温度趋于0时,分子停留在最低能量状态的概率趋于时,分子停留在最低能量状态的概率趋于1。3.1.1 物理退火过程物理退火过程能量最低状态能量最低状态 非能量最低状态非能量最低状态你现在浏览的是第十二页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算wMetrop
13、olis准则(准则(1953)以概率接受新状态以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法方法(计算机随机模拟方法)加以模拟,虽然(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。果,计算量很大。3.1.1 物理退火过程物理退火过程你现在浏览的是第十三页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算wMetropolis准则(准则(1953)以概率接受新状态以概率接受新状态 若在温度若在温度T
14、,当前状态,当前状态i 新状态新状态j 若若Ej=randrom0,1 s=sj;Until 抽样稳定准则满足;抽样稳定准则满足;退温退温tk+1=update(tk)并令并令k=k+1;Until 算法终止准则满足;算法终止准则满足;输出算法搜索结果。输出算法搜索结果。3.1.3 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤你现在浏览的是第十七页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算w影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温t=t0,随机产生初始状态,随机产生初始状态s=s0,令,令k=0;Repeat Repeat
15、 产生新状态产生新状态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 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和步骤三函数两准则三函数两准则初始温度初始温度你现在浏览的是第十八页,共51页3.1 模拟退火算法及模型模拟退火算法及模型 现代优化计算现代优化计算 3.1.3 模拟退火算法的基本思想和步骤模拟退火算法的基本思想和
16、步骤Step1 设定初始温度设定初始温度t=tmax,任选初始解任选初始解r=r0Step2 内循环内循环 Step2.1 从从r的邻域中随机选一个解的邻域中随机选一个解rt,计算计算r和和rt对应目标对应目标函函 数值数值,如如rt对应目标函数值较小,则令对应目标函数值较小,则令r=rt;否则若否则若 exp(-(E(rt)-E(r)/t)random(0,1),则令则令r=rt.Step2.2 不满足内循环停止条件时,重复不满足内循环停止条件时,重复Step2.1Step3 外循环外循环 Step3.1 降温降温t=decrease(t)Step3.2 如不满足外循环停止条件,则转如不满足
17、外循环停止条件,则转Step2;否则算法结束;否则算法结束1.达到终止温度达到终止温度2.达到迭代次数达到迭代次数3.最优值连续若干步最优值连续若干步保持不变保持不变1.目标函数均值稳定目标函数均值稳定2.连续若干步的目标值变化连续若干步的目标值变化较小较小3.固定的抽样步数固定的抽样步数w模拟退火算法的步骤模拟退火算法的步骤你现在浏览的是第十九页,共51页3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述 现代优化计算现代优化计算w定义定义 3.2.1 马尔科夫链马尔科夫链你现在浏览的是第二十页,共51页3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述 现代优化计算现代优化计算
18、w定义定义 一步转移概率:一步转移概率:n步转移概率:步转移概率:若解空间有限,称马尔可夫链为若解空间有限,称马尔可夫链为有限状态有限状态;若若 ,称马尔可夫链为,称马尔可夫链为时齐的时齐的。3.2.1 马尔科夫链马尔科夫链你现在浏览的是第二十一页,共51页3.2 模拟退火算法的马氏链描述模拟退火算法的马氏链描述 现代优化计算现代优化计算w模拟退火算法对应了一个马尔可夫链模拟退火算法对应了一个马尔可夫链 模拟退火算法:新状态接受概率仅依赖于新状态和当前模拟退火算法:新状态接受概率仅依赖于新状态和当前状态,并由温度加以控制。状态,并由温度加以控制。若固定每一温度,算法均计算马氏链的变化直至平稳若
19、固定每一温度,算法均计算马氏链的变化直至平稳分布,然后下降温度,则称为分布,然后下降温度,则称为时齐算法时齐算法;若无需各温度下算法均达到平稳分布,但温度需按一若无需各温度下算法均达到平稳分布,但温度需按一定速率下降,则称为定速率下降,则称为非时齐算法非时齐算法。w分析收敛性分析收敛性 3.2.2 模拟退火算法与马尔科夫链模拟退火算法与马尔科夫链你现在浏览的是第二十二页,共51页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计现代优化计算现代优化计算w原则原则 产生的候选解应遍布全部解空间产生的候选解应遍布全部解空间w方法方法 在当前状态的邻域结构内以一定概率方式(均匀
20、分布、在当前状态的邻域结构内以一定概率方式(均匀分布、正态分布、指数分布等)产生正态分布、指数分布等)产生 3.3.1 3.3.1 状态产生函数状态产生函数状态产生函数状态产生函数你现在浏览的是第二十三页,共51页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计现代优化计算现代优化计算w原则原则 (1)在固定温度下,接受使目标函数下降的候选解的概在固定温度下,接受使目标函数下降的候选解的概率要大于使目标函数上升的候选解概率;率要大于使目标函数上升的候选解概率;(2)随温度的下降,接受使目标函数上升的解的概率要逐随温度的下降,接受使目标函数上升的解的概率要逐渐减小;渐减小
21、;(3)当温度趋于零时,只能接受目标函数下降的解。当温度趋于零时,只能接受目标函数下降的解。w方法方法 具体形式对算法影响不大具体形式对算法影响不大 一般采用一般采用min1,exp(-C/t)3.3.2 状态接受函数状态接受函数你现在浏览的是第二十四页,共51页3.3 模拟退火算法关键参数和操作的设计模拟退火算法关键参数和操作的设计现代优化计算现代优化计算w收敛性分析收敛性分析 通过理论分析可以得到初温的解析式,但解决实际问题通过理论分析可以得到初温的解析式,但解决实际问题时难以得到精确的参数;时难以得到精确的参数;初温应充分大;初温应充分大;w实验表明实验表明 初温越大,获得高质量解的机率
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 详解 优秀 PPT
限制150内