《现代优化技术-靳志宏》算法收敛性.ppt

现代优化技术第13讲:算法收敛性浅析1ppt课件一、模拟退火算法的基本思想启发注意到一个自然规则:物质总是趋于最低的能态。水总是向低处流。电子总是向最低能级的轨道排布。最低能态是最稳定的状态。物质会”自动”地趋向的最低能态。2ppt课件模拟退火算法(起源)物理退火原理3ppt课件模拟退火算法与物理退火过程的相似关系模拟退火物理退火解粒子状态最优解能量最低态设定初温熔解过程Metropolis采样过程等温过程控制参数的下降冷却目标函数能量4ppt课件模拟退火算法(Metropolis准则)Metropolis准则 假设在状态xold时,系统受到某种扰动而使其状态变为xnew。与此相对应,系统的能量也从E(xold)变成E(xnew),系统由状态xold变为状态xnew的接受概率p:5ppt课件模拟退火算法(流程)随机产生一个初始解x0,令xbest=x0,并计算目标函数值E(x0);设置初始温度T(0)=To;DowhileT>Tmin//降温过程forj=1~k //等温过程对当前最优解xbest按照某一邻域函数,产生一新的解xnew。计算新的目标函数值E(xnew),并计算目标函数值的增量E=E(xnew)-E(xbest)。如果E<0,则xbest=xnew;如果E>0,则p=exp(-E/T(i));如果c=random[0,1]<p,xbest=xnew;否则xbest=xbest。Endfor按照温度控制策略更新T;EndDo输出当前最优点,计算结束。6ppt课件模拟退火算法(要素)1、状态空间与状态产生函数(邻域函数)搜索空间也称为状态空间,它由经过编码的可行解的集合所组成。状态产生函数(邻域函数)应尽可能保证产生的候选解能遍布全部解空间。通常由两部分组成,即产生候选解的方式和候选解产生的概率分布。候选解一般按照某一概率分布对解空间进行随机采样来获得。概率分布可以是均匀分布、正态分布、指数分布等等。7ppt课件模拟退火算法(要素)2、状态转移概率(接受概率)p状态转移概率是指从一个状态xold(一个可行解)向另一个状态xnew(另一个可行解)的转移概率;通俗的理解是接受一个新解为当前解的概率;它与当前的温度参数T有关,随温度下降而减小。一般采用Metropolis准则8ppt课件模拟退火算法(要素)3、冷却进度表T(t) 冷却进度表是指从某一高温状态To向低温状态冷却时的降温管理表。 假设时刻t的温度用T(t)来表示,则经典模拟退火算法的降温方式为: 而快速模拟退火算法的降温方式为: 这两种方式都能够使得模拟退火算法收敛于全局最小点。9ppt课件10ppt课件