模拟退火算法讲义.pdf

《模拟退火算法讲义.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章模拟退火算法（SimulatedAnnealing）搜索问题描述3除当前高度外，对环境没有任何感知21)x0f(-1-2最优解位于海拔最低处-3050010001500200025003000x搜索问题描述¢LandscapewithvariousfeaturesObjectiveglobalmaxfunctionlocalmaxshoulderflatlocalmaxcurrentstateStatespace搜索算法¢盲目搜索还是启发式搜索？¢按照预定的控制策略实行搜索，在搜索过程中获取的中间信息不用来改进控制策略，称为盲目搜索，反之，称为启发式搜索。¢关于“启发式”，

2、可有两种看法：¢1)任何有助于找到问题的解，但不能保证找到解的方法均是启发式方法；¢2)有助于加速求解过程和找到较优解的方法是启发式方法。搜索算法¢盲目搜索¢深度优先、广度优先、代价优先、向前、向后、双向。。。¢启发式搜索¢爬山法、模拟退火算法、遗传算法、粒子群算法、蚁群算法。。。贪心算法1.随机选定一个初始解x0；2.Dowhile（中止条件不满足）1.在某个邻域函数所定义的邻域范围内，按照某个（随机）扰动Δ产生策略，得到一个新解x’；i2.对新解进行评估，得f(xi’)；3.如果f(xi’)>f(xi)（或者f(xi’)

3、.否则，xi＋1＝xi。3.EndDo爬山法1.随机选定一个初始解x0；2.Dowhile（中止条件不满足）1.在某个邻域函数所定义的邻域范围内，按照某个（随机）扰动Δ产生策略，得到多个新解X={x1,x,…,xk}；newii2i12k2.对这组新解进行评估，得{f(xi),f(xi),…,f(xi)}；j3.xi＋1＝xi’,xi’∈Xnew,∀xi,(i=1,2,…,n;j=1,2,…,k),f(xi’)>f(xi)且f(x’)>f(xj)（或者f(x’)

4、,(i=1,2,…,n;j=1,2,…,k),f(xi)>f(xi)（或者f(xi)

5、sitashehammersthebladeintoshape.¢Ifhecoolsthebladetooquicklythemetalwillformpatchesofdifferentcomposition;¢Ifthemetaliscooledslowlywhileitisshaped,theconstituentmetalswillformauniformalloy.模拟退火算法（起源）¢物理退火过程：¢加温过程¢等温过程¢冷却（退火）过程¢等温下热平衡过程可用MonteCarlo方法模拟，计算量大。¢1953年，Metropolis提出重要性采样法，即以概率接受新状态，

6、称Metropolis准则，计算量相对MonteCarlo方法显著减少。¢1983年，Kirkpatrick等提出模拟退火算法，并将其应用于组合优化问题的求解。模拟退火算法（Metropolis准则）¢Metropolis准则假设在状态x时，系统受到某种扰动而使其状态old变为x。与此相对应，系统的能量也从E(x)变newold成E(x)，系统由状态x变为状态x的接受概率newoldnewp：⎧1ifE(xnew)

7、最优解能量最低态设定初温熔解过程Metropolis采样过程等温过程控制参数的下降冷却目标函数能量模拟退火算法（流程）1)随机产生一个初始解x，令x＝x，并计算目标函数值E(x);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=