欢迎来到天天文库
浏览记录
ID:5336356
大小:703.83 KB
页数:35页
时间:2017-12-08
《模拟退火算法讲义(数学建模)》由会员上传分享,免费在线阅读,更多相关内容在应用文档-天天文库。
1、第二章模拟退火算法(SimulatedAnnealing)搜索问题描述3除当前高度外,对环境没有任何感知21)x0f(-1-2最优解位于海拔最低处-3050010001500200025003000x搜索问题描述¢LandscapewithvariousfeaturesObjectiveglobalmaxfunctionlocalmaxshoulderflatlocalmaxcurrentstateStatespace搜索算法¢盲目搜索还是启发式搜索?¢按照预定的控制策略实行搜索,在搜索过程中获取的中间信息不用来改进控制策
2、略,称为盲目搜索,反之,称为启发式搜索。¢关于“启发式”,可有两种看法:¢1)任何有助于找到问题的解,但不能保证找到解的方法均是启发式方法;¢2)有助于加速求解过程和找到较优解的方法是启发式方法。搜索算法¢盲目搜索¢深度优先、广度优先、代价优先、向前、向后、双向。。。¢启发式搜索¢爬山法、模拟退火算法、遗传算法、粒子群算法、蚁群算法。。。贪心算法1.随机选定一个初始解x0;2.Dowhile(中止条件不满足)1.在某个邻域函数所定义的邻域范围内,按照某个(随机)扰动Δ产生策略,得到一个新解x’;i2.对新解进行评估,得f(
3、xi’);3.如果f(xi’)>f(xi)(或者f(xi’)4、)>f(xi)且f(x’)>f(xj)(或者f(x’)f(xi)(或者f(xi)5、系)¢新解产生策略(随机,确定)¢接受策略(贪心)存在问题:¢对初始解(状态)敏感¢容易陷入局部最优模拟退火算法(起源)物理退火原理Realannealing:Sword¢Heheatsthemetal,thenslowlycoolsitashehammersthebladeintoshape.¢Ifhecoolsthebladetooquicklythemetalwillformpatchesofdifferentcomposition;¢Ifthemetaliscooledslowlywhileitisshaped,t6、heconstituentmetalswillformauniformalloy.模拟退火算法(起源)¢物理退火过程:¢加温过程¢等温过程¢冷却(退火)过程¢等温下热平衡过程可用MonteCarlo方法模拟,计算量大。¢1953年,Metropolis提出重要性采样法,即以概率接受新状态,称Metropolis准则,计算量相对MonteCarlo方法显著减少。¢1983年,Kirkpatrick等提出模拟退火算法,并将其应用于组合优化问题的求解。模拟退火算法(Metropolis准则)¢Metropolis准则假设在状态x7、时,系统受到某种扰动而使其状态old变为x。与此相对应,系统的能量也从E(x)变newold成E(x),系统由状态x变为状态x的接受概率newoldnewp:⎧1ifE(xnew)8、0best002)设置初始温度T(0)=To,迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解x按照某一邻域函数,产生一新的解x。计算新的目bestnew标函数值E(x),并计算目标函数值的增量ΔE=E(x)-E(x)。newnewbest3)如果ΔE<0,则x=
4、)>f(xi)且f(x’)>f(xj)(或者f(x’)f(xi)(或者f(xi)5、系)¢新解产生策略(随机,确定)¢接受策略(贪心)存在问题:¢对初始解(状态)敏感¢容易陷入局部最优模拟退火算法(起源)物理退火原理Realannealing:Sword¢Heheatsthemetal,thenslowlycoolsitashehammersthebladeintoshape.¢Ifhecoolsthebladetooquicklythemetalwillformpatchesofdifferentcomposition;¢Ifthemetaliscooledslowlywhileitisshaped,t6、heconstituentmetalswillformauniformalloy.模拟退火算法(起源)¢物理退火过程:¢加温过程¢等温过程¢冷却(退火)过程¢等温下热平衡过程可用MonteCarlo方法模拟,计算量大。¢1953年,Metropolis提出重要性采样法,即以概率接受新状态,称Metropolis准则,计算量相对MonteCarlo方法显著减少。¢1983年,Kirkpatrick等提出模拟退火算法,并将其应用于组合优化问题的求解。模拟退火算法(Metropolis准则)¢Metropolis准则假设在状态x7、时,系统受到某种扰动而使其状态old变为x。与此相对应,系统的能量也从E(x)变newold成E(x),系统由状态x变为状态x的接受概率newoldnewp:⎧1ifE(xnew)8、0best002)设置初始温度T(0)=To,迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解x按照某一邻域函数,产生一新的解x。计算新的目bestnew标函数值E(x),并计算目标函数值的增量ΔE=E(x)-E(x)。newnewbest3)如果ΔE<0,则x=
5、系)¢新解产生策略(随机,确定)¢接受策略(贪心)存在问题:¢对初始解(状态)敏感¢容易陷入局部最优模拟退火算法(起源)物理退火原理Realannealing:Sword¢Heheatsthemetal,thenslowlycoolsitashehammersthebladeintoshape.¢Ifhecoolsthebladetooquicklythemetalwillformpatchesofdifferentcomposition;¢Ifthemetaliscooledslowlywhileitisshaped,t
6、heconstituentmetalswillformauniformalloy.模拟退火算法(起源)¢物理退火过程:¢加温过程¢等温过程¢冷却(退火)过程¢等温下热平衡过程可用MonteCarlo方法模拟,计算量大。¢1953年,Metropolis提出重要性采样法,即以概率接受新状态,称Metropolis准则,计算量相对MonteCarlo方法显著减少。¢1983年,Kirkpatrick等提出模拟退火算法,并将其应用于组合优化问题的求解。模拟退火算法(Metropolis准则)¢Metropolis准则假设在状态x
7、时,系统受到某种扰动而使其状态old变为x。与此相对应,系统的能量也从E(x)变newold成E(x),系统由状态x变为状态x的接受概率newoldnewp:⎧1ifE(xnew)8、0best002)设置初始温度T(0)=To,迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解x按照某一邻域函数,产生一新的解x。计算新的目bestnew标函数值E(x),并计算目标函数值的增量ΔE=E(x)-E(x)。newnewbest3)如果ΔE<0,则x=
8、0best002)设置初始温度T(0)=To,迭代次数i=1;3)DowhileT(i)>Tmin1)forj=1~k2)对当前最优解x按照某一邻域函数,产生一新的解x。计算新的目bestnew标函数值E(x),并计算目标函数值的增量ΔE=E(x)-E(x)。newnewbest3)如果ΔE<0,则x=
此文档下载收益归作者所有