模拟退火算法ppt课件.ppt
《模拟退火算法ppt课件.ppt》由会员分享,可在线阅读,更多相关《模拟退火算法ppt课件.ppt(33页珍藏版)》请在三一办公上搜索。
1、,模拟退火算法,汇报人:许炯楼2014xxxxxx 李娜2014200909冒亚婷2014200922李园园2014200923,模拟退火算法及模型,1,1.1 模拟退火算法的来源及基本原理,算法的提出 模拟退火算法最早的思想由Metropolis等(1953)提出,1983年Kirkpatrick等将其应用于组合优化。算法的目的 解决NP复杂性问题;克服优化过程陷入局部极小;克服初值依赖性。,1.1 模拟退火算法的来源及基本原理,物理退火过程:退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。,加温过程增强粒子的热运动
2、,消除系统原先可能存在的非均匀态;等温过程对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是 朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;冷却过程使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的 晶体结构。,1.1 模拟退火算法的来源及基本原理,模仿自然界退火現象而得,利用了物理中固体物质的退火过程与一般优化问题的相似性;从某一初始温度开始,伴随温度的不断下降,结合概率突跳特性在解空间中随机寻找全局最优解。,1.1 模拟退火算法的来源及基本原理,数学表述 在温度T,分子停留在状态r满足Boltzmann概率分布,1.1 模拟退火算法的来源及基本思想,数学表述
3、 在同一个温度T,选定两个能量E1E2,有,模拟退火算法基本思想:在一定温度下,搜索从一个状态随机地变化到另一个状态;随着温度的不断下降直到最低温度,搜索过程以概率1停留在最优解,0,1,1.1 模拟退火算法的来源及基本思想,Boltzman概率分布告诉我们:(1)在同一个温度,分子停留在能量小状态的概率大于停留在能量大状态的概率(2)温度越高,不同能量状态对应的概率相差越小;温度足够高时,各状态对应概率基本相同。(3)随着温度的下降,能量最低状态对应概率越来越大;温度趋于0时,其状态趋于1,1.1 模拟退火算法的来源及基本原理,数学表述 若|D|为状态空间D中状态的个数,D0是具有最低能量的
4、状态集合:当温度很高时,每个状态概率基本相同,接近平均值1/|D|;状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值1/|D|;当温度趋于0时,分子停留在最低能量状态的概率趋于1。,能量最低状态 非能量最低状态,1.1 模拟退火算法的来源及基本原理,Metropolis准则(1953)以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。若在温度T,当前状态i 新状态j;若EjEi,则接受 j 为当前状态;否则,若概率 p=exp-(Ej-Ei)/kBT
5、 大于0,1)区间的随机数,则仍接受状态 j 为当前状态;若不成立则保留状态 i 为当前状态。p=exp-(Ej-Ei)/kBT 在高温下,可接受与当前状态能量差较大的新状态;在低温下,只接受与当前状态能量差较小的新状态。,1.1模拟退火算法的基本思想和步骤,给定初温t=t0,随机产生初始状态s=s0,令k=0;Repeat Repeat 产生新状态sj=Genete(s);if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足;退温tk+1=update(tk)并令k=k+1;Until 算法终止准则满足;输出算法搜索结果。,基本步
6、骤,1.1模拟退火算法的基本思想和步骤,给定初温t=t0,随机产生初始状态s=s0,令k=0;Repeat Repeat 产生新状态sj=Genete(s);if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;Until 抽样稳定准则满足;退温tk+1=update(tk)并令k=k+1;Until 算法终止准则满足;输出算法搜索结果。,影响优化结果的主要因素,三函数两准则初始温度,1.1模拟退火算法的基本思想和步骤,模拟退火算法的步骤,Step1 设定初始温度t=tmax,任选初始解r=r0Step2 内循环 Step2.1 从r的邻域中随机选一个解rt,计
7、算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 如不满足外循环停止条件,则转Step2;否则算法结束,1.达到终止温度2.达到迭代次数3.最优值连续若干步 保持不变,1.目标函数均值稳定2.连续若干步的目标值变化较小3.固定的抽样步数,模拟退火算法的马氏链描述,2,2.1马尔科夫链,定义,一步转移概率:,n步转移概率:,若解空间有限,称马尔可夫链为有限状态;
8、,若,称马尔可夫链为时齐的。,2.2 模拟退火算法与马尔科夫链,模拟退火算法对应了一个马尔可夫链 模拟退火算法:新状态接受概率仅依赖于新状态和当前状态,并由温度加以控制。若固定每一温度,算法均计算马氏链的变化直至平稳分布,然后下降温度,则称为时齐算法;若无需各温度下算法均达到平稳分布,但温度需按一定速率下降,则称为非时齐算法。分析收敛性,模拟退火算法关键参数和操作的设计,3,*,3 模拟退火算法关键参数和操作的设计,原则 产生的候选解应遍布全部解空间方法 在当前状态的邻域结构内以一定概率方式(均匀分布、正态分布、指数分布等)产生,状态产生函数,状态接受函数,原则(1)在固定温度下,接受使目标函
9、数下降的候选解的概率要大于使目标函数上升的候选解概率;(2)随温度的下降,接受使目标函数上升的解的概率要逐渐减小;(3)当温度趋于零时,只能接受目标函数下降的解。方法 具体形式对算法影响不大 一般采用min1,exp(-C/t),*,3 模拟退火算法关键参数和操作的设计,收敛性分析 通过理论分析可以得到初温的解析式,但解决实际问题时难以得到精确的参数;初温应充分大;实验表明 初温越大,获得高质量解的机率越大,但花费较多的计算时间;方法(1)均匀抽样一组状态,以各状态目标值得方差为初温;(2)随机产生一组状态,确定两两状态间的最大目标值差,根据差值,利用一定的函数确定初温;(3)利用经验公式。,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 ppt 课件
链接地址:https://www.31ppt.com/p-2066374.html