模拟退火算法(完整版)ppt资料课件.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《模拟退火算法(完整版)ppt资料课件.ppt》由用户(三亚风情)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模拟 退火 算法 完整版 ppt 资料 课件
- 资源描述:
-
1、模拟退火算法模拟退火算法是什么?是怎样提出来的?模拟退火算法是什么?是怎样提出来的?模拟退火算法模拟退火算法Simulated Annealing,SA是一种模拟物理退火的过程而设计的优化算法。是一种模拟物理退火的过程而设计的优化算法。它的根本思想最早在它的根本思想最早在1953年就被年就被Metropolis提出,提出,但直到但直到1983年年Kirkpatrick等人才设计出真正等人才设计出真正意义上的模拟退火算法并进行应用。意义上的模拟退火算法并进行应用。 模拟退火算法的根本思想是怎样的?模拟退火算法的根本思想是怎样的?模拟退火算法采用类似于物理退火的过程,模拟退火算法采用类似于物理退火
2、的过程,先在一个高温状态下相当于算法随机搜索,然后逐渐退火,先在一个高温状态下相当于算法随机搜索,然后逐渐退火,在每个温度下相当于算法的每一次状态转移徐徐冷却在每个温度下相当于算法的每一次状态转移徐徐冷却相当于算法局部搜索,最终到达物理基态相当于算法局部搜索,最终到达物理基态相当于算法找到最优解。相当于算法找到最优解。 简介简介l模拟退火算法的来源是根据复杂组合优化问题模拟退火算法的来源是根据复杂组合优化问题与固体的退火过程之间的相似之处。与固体的退火过程之间的相似之处。l该算法在系统向着能量减小的趋势变化过程中,该算法在系统向着能量减小的趋势变化过程中,偶尔允许系统跳到能量较高的状态,以避开
3、局偶尔允许系统跳到能量较高的状态,以避开局部最小,最终稳定在全局最小。部最小,最终稳定在全局最小。简介简介lSAA属于随机模拟算法属于随机模拟算法l模拟统计物理学中物体加热后冷却这一退模拟统计物理学中物体加热后冷却这一退火过程而建立的随机优化算法,意图是防火过程而建立的随机优化算法,意图是防止陷入局部极小解,早期用于组合优化,止陷入局部极小解,早期用于组合优化,后来开展成一种通用的优化算法。后来开展成一种通用的优化算法。根本思想根本思想lSAA是是基于基于Mente Carlo迭代求解策略的一种迭代求解策略的一种随机寻优算法,其随机寻优算法,其出发点出发点是基于物理中固体物是基于物理中固体物质
4、的退火过程与一般组合优化问题之间的相似质的退火过程与一般组合优化问题之间的相似性。另一方面,性。另一方面,结合爬山法和随机行走。结合爬山法和随机行走。lSAA在某一初温下,伴随温度参数的不断下降,在某一初温下,伴随温度参数的不断下降,结合概率突跳特性在解空间中随机寻找目标函结合概率突跳特性在解空间中随机寻找目标函数的全局最优解,即在局部优解能概率性地跳数的全局最优解,即在局部优解能概率性地跳出并最终趋于全局最优。出并最终趋于全局最优。 模拟退火算法是一种通用的优化算法,目模拟退火算法是一种通用的优化算法,目前已在工程中得到了广泛应用。前已在工程中得到了广泛应用。 根本思路根本思路l首先在高温下
5、进行搜索,此时各状态出现概率首先在高温下进行搜索,此时各状态出现概率相差不大,可以很快进入相差不大,可以很快进入“热平衡状态,这热平衡状态,这时进行的是一种时进行的是一种“粗搜索,也就是大致找到粗搜索,也就是大致找到系统的低能区域;系统的低能区域;l随着温度的逐渐降低,各状态出现概率的差距随着温度的逐渐降低,各状态出现概率的差距逐渐被扩大,搜索精度不断提高。这就可以越逐渐被扩大,搜索精度不断提高。这就可以越来越准确的找到网络能量函数的全局最小点。来越准确的找到网络能量函数的全局最小点。一、模拟退火算法概述一、模拟退火算法概述二、模拟退火算法的马氏链描述及收敛性二、模拟退火算法的马氏链描述及收敛
6、性三、模拟退火算法关键参数和操作设计三、模拟退火算法关键参数和操作设计四、模拟退火算法的改进及其并行性四、模拟退火算法的改进及其并行性五、模拟退火算法的实现及应用五、模拟退火算法的实现及应用固体退火过程固体退火过程Metropolis准那么准那么组合优化与物理退火的相似性组合优化与物理退火的相似性模拟退火算法的步骤模拟退火算法的步骤第一节第一节 模拟退火算法概述模拟退火算法概述 l算法的提出算法的提出l 模拟退火算法最早的思想由模拟退火算法最早的思想由Metropolis等等1953提出,提出,1983年年Kirkpatrick等将其应用于等将其应用于组合优化。组合优化。l Optimizat
7、ion by simulated annealing, IBM Research Reportl算法的目的算法的目的l 解决解决NP复杂性问题提供有效近似算法;复杂性问题提供有效近似算法;l 克服优化过程陷入局部极小;克服优化过程陷入局部极小;l 克服初值依赖性。克服初值依赖性。1、源于对固体退火过程的模拟;、源于对固体退火过程的模拟;2、采用、采用Metropolis接受准那么;接受准那么;3、用冷却进度表控制算法进程,使算法在多、用冷却进度表控制算法进程,使算法在多项式时间里给出一个近似解。项式时间里给出一个近似解。 固体退火过程的物理图像和统计性质是固体退火过程的物理图像和统计性质是SA
8、A的的物理背景;物理背景;Metropolis接受准那么使算法跳离局部接受准那么使算法跳离局部最优最优 “险井;而冷却进度表的合理选择是算法应险井;而冷却进度表的合理选择是算法应用的前提。用的前提。 l算法的根底算法的根底 l固体退火过程固体退火过程l 什么是退火:什么是退火:l 退火是指将固体加热到足够高的温度,使分退火是指将固体加热到足够高的温度,使分子呈随机排列状态,然后逐步降温使之冷却,子呈随机排列状态,然后逐步降温使之冷却,最后分子以低能状态排列,固体到达某种稳定最后分子以低能状态排列,固体到达某种稳定状态。状态。 固体退火是将固体加热至融化,再徐固体退火是将固体加热至融化,再徐徐冷
9、却使之凝固成规整晶体的热力学过程,徐冷却使之凝固成规整晶体的热力学过程,属于热力学与统计物理研究的范畴。属于热力学与统计物理研究的范畴。由以下三局部组成:由以下三局部组成:加温过程加温过程等温过程等温过程冷却过程冷却过程固体在恒定温度下到固体在恒定温度下到达热平衡的过程!达热平衡的过程! l固体退火过程固体退火过程l 加温过程加温过程增强粒子的热运动,使其偏离增强粒子的热运动,使其偏离平衡位置,目的是消除系统原先可能存在的非平衡位置,目的是消除系统原先可能存在的非均匀态;均匀态;l 等温过程等温过程退火过程中要让温度慢慢降低,退火过程中要让温度慢慢降低,在每一个温度下要到达热平衡状态,对于与环
10、在每一个温度下要到达热平衡状态,对于与环境换热而温度不变的封闭系统满足自由能较少境换热而温度不变的封闭系统满足自由能较少定律,系统状态的自发变化总是朝自由能减少定律,系统状态的自发变化总是朝自由能减少的方向进行,当自由能到达最小时,系统到达的方向进行,当自由能到达最小时,系统到达平衡态;平衡态;l 冷却过程冷却过程使粒子热运动减弱并渐趋有序,使粒子热运动减弱并渐趋有序,系统能量逐渐下降,从而得到低能的晶体结构。系统能量逐渐下降,从而得到低能的晶体结构。当液体凝固为固体的晶态时退火过程完成。当液体凝固为固体的晶态时退火过程完成。 l数学表述数学表述 在温度在温度T,分子停留在状态,分子停留在状态
11、r满足满足Boltzmann概率分布概率分布 温度低时能量低的微观状态概率大,温度趋于零时,温度低时能量低的微观状态概率大,温度趋于零时,固体几乎处于概率最大能量最小的基态。固体几乎处于概率最大能量最小的基态。DsBBBTksETZTZkrrEETkrETZrEEP)(exp)()(Boltzmann0)()(exp)(1)(子:为概率分布的标准化因常数。为的能量,表示状态机变量,表示分子能量的一个随 l数学表述数学表述 在在同一个温度同一个温度T,选定两个能量,选定两个能量E1E2,有,有 在同一个温度,分子停留在能量小的状态的概在同一个温度,分子停留在能量小的状态的概率比停留在能量大的状态
12、的概率要大。率比停留在能量大的状态的概率要大。TkEETkETZEEPEEPBB12121exp1exp)(10l数学表述数学表述l 假设假设|D|为状态空间为状态空间D中状态中状态的个数,的个数,D0是具有最低能量的是具有最低能量的状态集合:状态集合:l (1) 当温度很高时,每个状态当温度很高时,每个状态概率根本相同,接近平均值概率根本相同,接近平均值1/|D|;l (2) 状态空间存在超过两个不状态空间存在超过两个不同能量时,具有最低能量状态的同能量时,具有最低能量状态的概率超出平均值概率超出平均值1/|D| ;l (3) 当温度趋于当温度趋于0时,分子停时,分子停留在最低能量状态的概率
13、趋于留在最低能量状态的概率趋于1。能量最低状态能量最低状态非能量最低状态非能量最低状态 lMetropolis准那么准那么1953以概率接受新状以概率接受新状态态l 固体在恒定温度下到达热平衡的过程可以用固体在恒定温度下到达热平衡的过程可以用Monte Carlo方法计算机随机模拟方法加以方法计算机随机模拟方法加以模拟,虽然该方法简单,但必须大量采样才能模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,计算量很大。得到比较精确的结果,计算量很大。lMonte Carlo模拟退火过程模拟退火过程l蒙特卡罗蒙特卡罗(Monte Carlo)方法,或称计算机方法,或称计算机随机模拟方法,是
14、一种基于随机模拟方法,是一种基于“随机数的计随机数的计算方法。这一方法源于美国在第一次世界算方法。这一方法源于美国在第一次世界大战中研制原子弹的大战中研制原子弹的“曼哈顿方案。该方曼哈顿方案。该方案的主持人之一、数学家冯案的主持人之一、数学家冯诺伊曼用著名诺伊曼用著名世界的赌城世界的赌城摩纳哥的摩纳哥的Monte Carlo来命来命名这种方法,为它蒙上了一层神秘色彩。名这种方法,为它蒙上了一层神秘色彩。lMonte Carlo方法方法lMonte Carlo方法的根本思想很早以前就被方法的根本思想很早以前就被人们所发现和利用。人们所发现和利用。l早在早在17世纪,人们就知道用事件发生的世纪,人
15、们就知道用事件发生的“频频率来决定事件的率来决定事件的“概率。概率。lBuffon试验:试验:19世纪人们用投针试验的方世纪人们用投针试验的方法来求解圆周率法来求解圆周率。l本世纪本世纪40年代电子计算机的出现,特别是年代电子计算机的出现,特别是近年来高速电子计算机的出现,使得用数近年来高速电子计算机的出现,使得用数学方法在计算机上大量、快速地模拟这样学方法在计算机上大量、快速地模拟这样的试验成为可能。的试验成为可能。lMonte Carlo方法方法l用民意测验来作一个不严格的比喻。民意用民意测验来作一个不严格的比喻。民意测验的人不是征询每一个登记选民的意见,测验的人不是征询每一个登记选民的意
16、见,而是通过对选民进行小规模的抽样调查来而是通过对选民进行小规模的抽样调查来确定可能的优胜者。其根本思想是一样的。确定可能的优胜者。其根本思想是一样的。l它需要一个良好的随机数源。这种方法往它需要一个良好的随机数源。这种方法往往包含一些误差,但是随着随机抽取样本往包含一些误差,但是随着随机抽取样本数量的增加,结果也会越来越精确。数量的增加,结果也会越来越精确。 lMetropolis准那么准那么1953以概率接受新状以概率接受新状态态l 假设在温度假设在温度T,当前状态,当前状态i 新状态新状态jl 假设假设Ej=randrom0,1 s=sj;l Until 抽样稳定准那么满足;抽样稳定准那
17、么满足;l 退温退温tk+1=update(tk)并令并令k=k+1;l Until 算法终止准那么满足;算法终止准那么满足; l 输出算法搜索结果。输出算法搜索结果。 l影响优化结果的主要因素影响优化结果的主要因素l 给定初温给定初温t=t0,随机产生初始状态,随机产生初始状态s=s0,令,令k=0;l Repeatl Repeatl 产生新状态产生新状态sj=Genete(s);l if min1,exp-(C(sj)-C(s)/tk=randrom0,1 s=sj;l Until 抽样稳定准那么满足;抽样稳定准那么满足;l 退温退温tk+1=update(tk)并令并令k=k+1;l U
18、ntil 算法终止准那么满足;算法终止准那么满足; l 输出算法搜索结果。输出算法搜索结果。三函数两准那么三函数两准那么初始温度初始温度三函数两准那三函数两准那么么状态产生函数状态产生函数状态接受函数状态接受函数退温函数退温函数抽样稳定准那抽样稳定准那么么退火结束准那退火结束准那么么SAA流程流程确定确定初温初温随机给定随机给定初始解初始解收敛准收敛准则则满足满足否?否?输出结果输出结果Y抽样稳定准则抽样稳定准则满足否?满足否?由当前由当前状态产生状态产生新状态新状态接受函数接受函数成立否?成立否?替换当前状态替换当前状态YYNNN退温退温保持当前状态不变保持当前状态不变 关键环节关键环节1
19、1 初温、初始解初温、初始解2 2 状态产生函数状态产生函数3 3 状态接受函数状态接受函数4 4 退温函数退温函数5 5 抽样稳定准那么抽样稳定准那么6 6 收敛准那么收敛准那么SAA特点特点l可以保证全局最优可以保证全局最优l特别适合组合优化问题特别适合组合优化问题l可以随机选择初始解可以随机选择初始解l对问题本身没有特别要求,不会因为问题对问题本身没有特别要求,不会因为问题实例的改变影响性能实例的改变影响性能l简单易行,通用性好简单易行,通用性好马氏链描述马氏链描述收敛性收敛性时齐算法收敛性时齐算法收敛性非时齐算法收敛性非时齐算法收敛性渐近性态渐近性态第二节第二节 SAA的马氏链描述及收
20、敛性的马氏链描述及收敛性 模拟退火算法模拟退火算法(SAA)是将物理退火过程与是将物理退火过程与组合优化相结合的一种随机迭代寻优算法。组合优化相结合的一种随机迭代寻优算法。数学模型描述为数学模型描述为 由某一较高初始温度开始,在给定的由某一较高初始温度开始,在给定的邻域结构中,模拟退火过程,利用概率特邻域结构中,模拟退火过程,利用概率特性与抽样策略在解空间中随机搜索,随着性与抽样策略在解空间中随机搜索,随着温度不断下降重复抽样,用来优化问题的温度不断下降重复抽样,用来优化问题的解。解。引言引言设设 为所有状态构成的解空间,为所有状态构成的解空间,,21ss)(kX为为k时刻状态变量的取值。时刻
21、状态变量的取值。随机序列随机序列 称为称为马氏链马氏链,若若,)(21kkXZn满足满足)(|)()(inXjnXPnpij11简简记记记忆遗忘功能记忆遗忘功能)1(|)()1(,)1(,)0(|)(10inXjnXPinXiXiXjnXP 一步转移概率一步转移概率)(|)()(inXjnXPnpij11n步转移概率步转移概率)(|)()(iXjnXPpnij0有限状态马氏链有限状态马氏链假设解空间有限。假设解空间有限。时齐马氏链时齐马氏链)()(,1npnpZnijij模拟退火算法模拟退火算法(SAA)的搜索进程:的搜索进程: 算法从某一个初始状态开始后,每一步算法从某一个初始状态开始后,每
22、一步状态转移均是在当前状态的邻域中随机产生状态转移均是在当前状态的邻域中随机产生新状态,然后以一定概率进行接受的。新状态,然后以一定概率进行接受的。 接受概率仅依赖于新状态和当前状态,接受概率仅依赖于新状态和当前状态,并由温度加以控制。因此,并由温度加以控制。因此,SAA对应一个马对应一个马氏链。氏链。假设固定每一温度,算法均假设固定每一温度,算法均计算马氏链的变化直至平稳计算马氏链的变化直至平稳分布,然后下降温度。分布,然后下降温度。时齐算法时齐算法非时齐算法非时齐算法假设无需各温度下算法均到假设无需各温度下算法均到达平稳分布,但温度需按照达平稳分布,但温度需按照一定的速率下降。或称非平一定
23、的速率下降。或称非平稳马氏链算法。稳马氏链算法。SAA根底理论根底理论 iNkkiiijijijiijtpijandNjijandNjtagtpji)(10)()(,/ )(exp, 1min,tCCaijji 通通常常令令马氏链模型马氏链模型 iNjiijijigigNjNjigjigg),()(, 0),(/ ),(,SAA要实现全局收敛必须满足以下条件:要实现全局收敛必须满足以下条件:状态可达性状态可达性初值鲁棒性初值鲁棒性极限分布存在性极限分布存在性收敛到最优解收敛到最优解温度不变,温度不变,M链极限分布存链极限分布存在在温度渐近温度渐近0,M链极限分布存在链极限分布存在对应马氏链的状
24、态图是强连通的对应马氏链的状态图是强连通的对算法的最终结果不依赖于初值对算法的最终结果不依赖于初值定义定义1状态状态i可达状态可达状态j:00)(|)()(iXjnXPpnijji 定义定义2平稳分布平稳分布:称称 为马氏链的平稳分布为马氏链的平稳分布,若一步转移概率满足等式若一步转移概率满足等式,Zjvj01iijijpvv时齐算法的收敛性时齐算法的收敛性 时齐模拟退火算法的收敛性时齐模拟退火算法的收敛性结论结论:结论结论1 时齐模拟退火算法对应的有限状态马时齐模拟退火算法对应的有限状态马氏链存在平稳分布。氏链存在平稳分布。结论结论2 当温度趋于当温度趋于0时,马氏链以概率时,马氏链以概率1
25、收敛收敛到最优状态集,而收敛到非最优状态的概率到最优状态集,而收敛到非最优状态的概率为为0。实现途径:实现途径:通过各温度下各状态序列无限长通过各温度下各状态序列无限长得以实现!得以实现!非时齐算法的收敛性非时齐算法的收敛性收敛定理收敛定理 对退温函数加以严格控制,可使得对退温函数加以严格控制,可使得SA算法以概率算法以概率1收敛到全局最优解。收敛到全局最优解。 可设计退温函数为可设计退温函数为, 1, 0,)ln( kmktk m2其中其中 ,则当,则当 时,时,SA算法算法以概率以概率1收敛到全局最优解。收敛到全局最优解。rL 算法渐近性能的逼近算法渐近性能的逼近 收敛可以保证,但是时间性
展开阅读全文