模拟退火算法详解课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《模拟退火算法详解课件.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 详解 课件
- 资源描述:
-
1、 1精选课件 2精选课件 3精选课件 w算法的提出算法的提出 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等(等(1953)提出,提出,1983年年Kirkpatrick等将其应用于组合优化。等将其应用于组合优化。w算法的目的算法的目的 解决解决NP复杂性复杂性问题;问题;克服优化过程陷入局部极小;克服优化过程陷入局部极小;克服初值依赖性。克服初值依赖性。4精选课件 w物理退火过程物理退火过程 什么是退火:什么是退火:退火是指将固体加热到足够高的温度,使分子呈随退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,最后分子以机排列状态,然后逐步降
2、温使之冷却,最后分子以低能状态排列,固体达到某种稳定状态。低能状态排列,固体达到某种稳定状态。5精选课件 w物理退火过程物理退火过程 加温过程加温过程增强粒子的热运动,消除系统原先可增强粒子的热运动,消除系统原先可能存在的非均匀态;能存在的非均匀态;等温过程等温过程对于与环境换热而温度不变的封闭系对于与环境换热而温度不变的封闭系统,系统状态的自发变化总是朝自由能减少的方向统,系统状态的自发变化总是朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态;进行,当自由能达到最小时,系统达到平衡态;冷却过程冷却过程使粒子热运动减弱并渐趋有序,系统使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而
3、得到低能的晶体结构。能量逐渐下降,从而得到低能的晶体结构。6精选课件w热力学中的退火现象指物体逐渐降温时发生的物理热力学中的退火现象指物体逐渐降温时发生的物理現象:現象:温度越低,物体的能量状态越低,到达足够的低点温度越低,物体的能量状态越低,到达足够的低点时,液体开始冷凝与结晶,在结晶状态时,系统的时,液体开始冷凝与结晶,在结晶状态时,系统的能量状态最低。缓慢降温(退火,能量状态最低。缓慢降温(退火,annealing)时,)时,可达到最低能量状态;但如果快速降温(淬火,可达到最低能量状态;但如果快速降温(淬火,quenching),会导致不是最低能态的非晶形。),会导致不是最低能态的非晶形
4、。w大自然知道大自然知道慢工出细活慢工出细活:缓缓降温,使得物体分子在每一温度时,能够有足缓缓降温,使得物体分子在每一温度时,能够有足够时间找到安顿位置,则逐渐地,到最后可得到最够时间找到安顿位置,则逐渐地,到最后可得到最低能态,系统最稳定。低能态,系统最稳定。7精选课件w模仿自然界退火現象而得,利用了物理中固体物质模仿自然界退火現象而得,利用了物理中固体物质的的退火过程退火过程与一般与一般优化优化问题的相似性问题的相似性 从某一初始从某一初始温度温度开始,伴随温度的不断下降,结合开始,伴随温度的不断下降,结合概率突跳概率突跳特性在解空间中特性在解空间中随机随机寻找寻找全局最优解全局最优解 8
5、精选课件 w数学表述数学表述 在温度在温度T,分子停留在状态,分子停留在状态r满足满足Boltzmann概率分概率分布布DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子:为概率分布的标准化因常数。为的能量,表示状态机变量,表示分子能量的一个随9精选课件 w数学表述数学表述 在在同一个温度同一个温度T,选定两个能量,选定两个能量E1E2,有,有TkEETkETZEEPEEPBB12121exp1exp)(10模拟退火算法基本思想模拟退火算法基本思想:在一定温度下,搜索从一个状态:在一定温度下,搜索从一个状态随机地变化到另一个
6、状态;随着温度的不断下降直到最低温度,随机地变化到另一个状态;随着温度的不断下降直到最低温度,搜索过程以概率搜索过程以概率1停留在最优解停留在最优解10精选课件 wBoltzmanBoltzman概率分布概率分布告诉我们:告诉我们:(1)在同一个温度,分子停留在能量小状态的概率)在同一个温度,分子停留在能量小状态的概率大于停留在能量大状态的概率大于停留在能量大状态的概率 (2)温度越高,不同能量状态对应的概率相差越小;)温度越高,不同能量状态对应的概率相差越小;温度足够高时,各状态对应概率基本相同。温度足够高时,各状态对应概率基本相同。(3)随着温度的下降,能量最低状态对应概率越来)随着温度的
7、下降,能量最低状态对应概率越来越大;温度趋于越大;温度趋于0时,其状态趋于时,其状态趋于111精选课件 w数学表述数学表述 若若|D|为状态空间为状态空间D中状态的个数,中状态的个数,D0是具有最低能是具有最低能量的状态集合:量的状态集合:当温度很高时,每个状态概率基本相同,接近平均当温度很高时,每个状态概率基本相同,接近平均值值1/|D|;状态空间存在超过两个不同能量时,具有最低能量状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值状态的概率超出平均值1/|D|;当温度趋于当温度趋于0时,分子停留在最低能量状态的概率时,分子停留在最低能量状态的概率趋于趋于1。能量最低状态能量最
8、低状态 非能量最低状态非能量最低状态12精选课件 wMetropolis准则(准则(1953)以概率接受新状态以概率接受新状态 固体在恒定温度下达到热平衡的过程可以用固体在恒定温度下达到热平衡的过程可以用Monte Carlo方法方法(计算机随机模拟方法)加以模拟,虽(计算机随机模拟方法)加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。的结果,计算量很大。13精选课件 wMetropolis准则(准则(1953)以概率接受新状态以概率接受新状态 若在温度若在温度T,当前状态,当前状态i 新状态新状态j 若若Ej=randr
9、om0,1 s=sj;Until 抽样稳定准则满足;抽样稳定准则满足;退温退温tk+1=update(tk)并令并令k=k+1;Until 算法终止准则满足;算法终止准则满足;输出算法搜索结果。输出算法搜索结果。17精选课件 w影响优化结果的主要因素影响优化结果的主要因素 给定初温给定初温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(t
10、k)并令并令k=k+1;Until 算法终止准则满足;算法终止准则满足;输出算法搜索结果。输出算法搜索结果。三函数两准则三函数两准则初始温度初始温度18精选课件 Step1 设定初始温度设定初始温度t=tmax,任选初始解任选初始解r=r0Step2 内循环内循环 Step2.1 从从r的邻域中随机选一个解的邻域中随机选一个解rt,计算计算r和和rt对应目标对应目标函函 数值数值,如如rt对应目标函数值较小,则令对应目标函数值较小,则令r=rt;否则若否则若 exp(-(E(rt)-E(r)/t)random(0,1),则令则令r=rt.Step2.2 不满足内循环停止条件时,重复不满足内循环
11、停止条件时,重复Step2.1Step3 外循环外循环 Step3.1 降温降温t=decrease(t)Step3.2 如不满足外循环停止条件,则转如不满足外循环停止条件,则转Step2;否则算;否则算法结束法结束1.达到终止温度达到终止温度2.达到迭代次数达到迭代次数3.最优值连续若干步最优值连续若干步保持不变保持不变1.目标函数均值稳定目标函数均值稳定2.连续若干步的目标连续若干步的目标值变化较小值变化较小3.固定的抽样步数固定的抽样步数w模拟退火算法的步骤模拟退火算法的步骤19精选课件 w定义定义 )1()(Pr)1(,)1(,)0()(Pr)()(,1021inXjnXinXiXiX
12、jnXZnkXkkXss,满足称为马尔可夫链,若随机序列时刻状态变量的取值。为间,为所有状态构成的解空令20精选课件 w定义定义 一步转移概率:一步转移概率:n步转移概率:步转移概率:若解空间有限,称马尔可夫链为若解空间有限,称马尔可夫链为有限状态有限状态;若若 ,称马尔可夫链为,称马尔可夫链为时齐的时齐的。)1()(Pr)1(,inXjnXnpji)1()(,npnpZnjiji)0()(Pr)(,iXjnXpnji21精选课件 w模拟退火算法对应了一个马尔可夫链模拟退火算法对应了一个马尔可夫链 模拟退火算法:新状态接受概率仅依赖于新状态和模拟退火算法:新状态接受概率仅依赖于新状态和当前状态
13、,并由温度加以控制。当前状态,并由温度加以控制。若固定每一温度,算法均计算马氏链的变化直至平若固定每一温度,算法均计算马氏链的变化直至平稳分布,然后下降温度,则称为稳分布,然后下降温度,则称为时齐算法时齐算法;若无需各温度下算法均达到平稳分布,但温度需按若无需各温度下算法均达到平稳分布,但温度需按一定速率下降,则称为一定速率下降,则称为非时齐算法非时齐算法。w分析收敛性分析收敛性22精选课件w原则原则 产生的候选解应遍布全部解空间产生的候选解应遍布全部解空间w方法方法 在当前状态的邻域结构内以一定概率方式(均匀分在当前状态的邻域结构内以一定概率方式(均匀分布、正态分布、指数分布等)产生布、正态
展开阅读全文