数学建模模拟退火算法.ppt
- 文档编号:18749348
- 上传时间:2023-10-28
- 格式:PPT
- 页数:49
- 大小:629.50KB
数学建模模拟退火算法.ppt
《数学建模模拟退火算法.ppt》由会员分享,可在线阅读,更多相关《数学建模模拟退火算法.ppt(49页珍藏版)》请在冰点文库上搜索。
第三章模拟退火算法,智能优化计算,浙江大学,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.130城市TSP问题(d*=423.741byDBFogel)3.5.2模拟退火算法在管壳式换热器优化设计中的应用,智能优化计算,浙江大学,3.1模拟退火算法及模型,智能优化计算,浙江大学,算法的提出模拟退火算法最早的思想由Metropolis等(1953)提出,1983年Kirkpatrick等将其应用于组合优化。
算法的目的解决NP复杂性问题;克服优化过程陷入局部极小;克服初值依赖性。
3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,物理退火过程什么是退火:
退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。
3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,物理退火过程加温过程增强粒子的热运动,消除系统原先可能存在的非均匀态;等温过程对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;冷却过程使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。
3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,数学表述在温度T,分子停留在状态r满足Boltzmann概率分布,3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,数学表述在同一个温度T,选定两个能量E1E2,有在同一个温度,分子停留在能量小的状态的概率比停留在能量大的状态的概率要大。
3.1.1物理退火过程,1,0,3.1模拟退火算法及模型,智能优化计算,浙江大学,数学表述若|D|为状态空间D中状态的个数,D0是具有最低能量的状态集合:
当温度很高时,每个状态概率基本相同,接近平均值1/|D|;状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值1/|D|;当温度趋于0时,分子停留在最低能量状态的概率趋于1。
3.1.1物理退火过程,能量最低状态非能量最低状态,3.1模拟退火算法及模型,智能优化计算,浙江大学,Metropolis准则(1953)以概率接受新状态固体在恒定温度下达到热平衡的过程可以用MonteCarlo方法(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。
3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,Metropolis准则(1953)以概率接受新状态若在温度T,当前状态i新状态j若EjEi,则接受j为当前状态;否则,若概率p=exp-(Ej-Ei)/kBT大于0,1)区间的随机数,则仍接受状态j为当前状态;若不成立则保留状态i为当前状态。
3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,Metropolis准则(1953)以概率接受新状态p=exp-(Ej-Ei)/kBT在高温下,可接受与当前状态能量差较大的新状态;在低温下,只接受与当前状态能量差较小的新状态。
3.1.1物理退火过程,3.1模拟退火算法及模型,智能优化计算,浙江大学,相似性比较,3.1.2组合优化与物理退火的相似性,3.1模拟退火算法及模型,智能优化计算,浙江大学,基本步骤给定初温t=t0,随机产生初始状态s=s0,令k=0;RepeatRepeat产生新状态sj=Genete(s);ifmin1,exp-(C(sj)-C(s)/tk=randrom0,1s=sj;Until抽样稳定准则满足;退温tk+1=update(tk)并令k=k+1;Until算法终止准则满足;输出算法搜索结果。
3.1.3模拟退火算法的基本思想和步骤,3.1模拟退火算法及模型,智能优化计算,浙江大学,影响优化结果的主要因素给定初温t=t0,随机产生初始状态s=s0,令k=0;RepeatRepeat产生新状态sj=Genete(s);ifmin1,exp-(C(sj)-C(s)/tk=randrom0,1s=sj;Until抽样稳定准则满足;退温tk+1=update(tk)并令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),其中t0为起始温度,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)增加记忆功能(记忆“Bestsofar”状态);(3)增加补充搜索过程(以最优结果为初始解);(4)对每一当前状态,采用多次搜索策略,以概率接受区域内的最优状态;(5)结合其它搜索机制的算法;(6)上述各方法的综合。
3.4.2改进内容,3.4模拟退火算法的改进,智能优化计算,浙江大学,改进的思路
(1)记录“Bestsofar”状态,并即时更新;
(2)设置双阈值,使得在尽量保持最优性的前提下减少计算量,即在各温度下当前状态连续m1步保持不变则认为Metropolis抽样稳定,若连续m2次退温过程中所得最优解不变则认为算法收敛。
3.4.3一种改进的模拟退火算法,3.4模拟退火算法的改进,智能优化计算,浙江大学,改进的退火过程
(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*)m2?
若是,则转第(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)若CC(s)?
若是,则令s*=s,q=0;否则,令q=q+1。
若C0,则以概率exp(-C/t)接受s作为下一当前状态;(4)令k=k+1,判断qm1?
若是,则转第(5)步;否则,返回第
(2)步;(5)将当前最优解s*和当前状态s(k)返回改进退火过程。
3.4.3一种改进的模拟退火算法,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模拟退火算法的实现与应用,智能优化计算,浙江大学,初始温度的计算fori=1:
100route=randperm(CityNum);fval0(i)=CalDist(dislist,route);endt0=-(max(fval0)-min(fval0)/log(0.9);,3.5.130城市TSP问题(d*=423.741byDBFogel),3.5模拟退火算法的实现与应用,智能优化计算,浙江大学,状态产生函数的设计
(1)互换操作,随机交换两个城市的顺序;
(2)逆序操作,两个随机位置间的城市逆序;(3)插入操作,随机选择某点插入某随机位置。
3.5.130城市TSP问题(d*=423.741byDBFogel),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,3.5模拟退火算法的实现与应用,智能优化计算,浙江大学,参数设定截止温度tf=0.01;退温系数alpha=0.90;内循环次数L=200*CityNum;,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.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模拟退火算法的实现与应用,智能优化计算,浙江大学,优化目标经过分析,优化问题的独立变量共12个,分别是一级换热器煤油出口温度t2、冷却水流量G1、两个换热器的管内径d1,d2和管间距S1,S2、折流板间距B1,B2、折流板开口角1,2、单管长度L1,L2。
3.5.2模拟退火算法在管壳式换热器优化设计中的应用,3.5模拟退火算法的实现与应用,智能优化计算,浙江大学,应用模拟退火算法解决优化设计状态表示12个变量的实数表示;初始温度100;结束温度0.001;状态产生函数,为扰动幅度参数,为随机扰动变量,随机扰动可服从柯西、高斯、均匀分布。
降温因子0.98;马氏链长度1200。
3.5.2模拟退火算法在管壳式换热器优化设计中的应用,3.5模拟退火算法的实现与应用,智能优化计算,浙江大学,优化结果优化目标值0.25565E06独立变量取值,3.5.2模拟退火算法在管壳式换热器优化设计中的应用,第三章结束,智能优化计算,浙江大学,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数学 建模 模拟 退火 算法