模拟退火算法 第一节优秀PPT.ppt

《模拟退火算法 第一节优秀PPT.ppt》由会员分享，可在线阅读，更多相关《模拟退火算法 第一节优秀PPT.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、模拟退火算法 第一节你现在浏览的是第一页，共22页一固体退火过程一固体退火过程退火是一种物理过程，固体退火是先将固体加热至退火是一种物理过程，固体退火是先将固体加热至熔化，再熔化，再徐徐徐徐冷却使之凝固成规整晶体的热力学冷却使之凝固成规整晶体的热力学过程过程退火过程中，系统在每一温度下达到平衡态，退火过程中，系统在每一温度下达到平衡态，系统状态的分布满足一定的概率分布，即在温度系统状态的分布满足一定的概率分布，即在温度 T，系统达到平衡态后，分子停留在状态，系统达到平衡态后，分子停留在状态 r 满足波兹满足波兹曼曼(Boltzmann)概率分布概率分布2.1模拟退火算法及模型模拟退火算法及模型

2、你现在浏览的是第二页，共22页其中，其中，E(r)为为状态状态 r 的能量的能量，kB 0为为波兹曼常数波兹曼常数，为分子能量的一个为分子能量的一个随机变量随机变量，称为称为波兹曼因子波兹曼因子Z(T)为概率分布的为概率分布的标准化因子标准化因子，先研究由先研究由(2.1)确定的函数随确定的函数随 T 变化的趋势选变化的趋势选定两个能量定两个能量 E1 E2，在同一个温度，在同一个温度 T，有，有D 为为状态空间状态空间你现在浏览的是第三页，共22页在同一个温度，在同一个温度，(2.2)表示表示分子停留在能量小状态分子停留在能量小状态的概率比停留在能量大状态的概率要大的概率比停留在能量大状态的

3、概率要大当温度当温度相当高时，相当高时，(2.1)的概率分布使得每个状态的概率的概率分布使得每个状态的概率基本相同，接近平均值基本相同，接近平均值1 D，D为状态空间为状态空间 D中状态的个数此时，具有最低能量状态的波兹中状态的个数此时，具有最低能量状态的波兹曼概率曼概率接近并超出平均值接近并超出平均值1 D 你现在浏览的是第四页，共22页当当 rmin 是是 D中具有最低能量的状态时，得中具有最低能量的状态时，得由由你现在浏览的是第五页，共22页所以，所以，关于温度关于温度 T是单调下降的是单调下降的又有又有其中，其中，D0是具有最低能量的状态集合，是具有最低能量的状态集合，你现在浏览的是第

4、六页，共22页因此得到，当因此得到，当 T 趋向于趋向于 0 时，时，当温度趋向于当温度趋向于 0时，时，(2.1)决定的概率渐决定的概率渐近近由此可以得到，由此可以得到，在温度趋向于在温度趋向于 0时，分子停留在最低时，分子停留在最低能量状态的概率趋向能量状态的概率趋向1综合上面的讨论，分子在最综合上面的讨论，分子在最低能量状态的概率变化趋势由图低能量状态的概率变化趋势由图(a)表示表示你现在浏览的是第七页，共22页对于非能量最小的状态，由对于非能量最小的状态，由(2.2)和分子在能量最小状态的和分子在能量最小状态的概率是单调减小的事实，在温度较高时，分子在概率是单调减小的事实，在温度较高时

5、，分子在这些状态的概率在这些状态的概率在附近，依赖于状态的不同，附近，依赖于状态的不同，使使(2.1)决定的概率在决定的概率在(0,t)是单调升的；再由是单调升的；再由(2.4)可可知，当温度趋于知，当温度趋于 0时，时，(2.1)定义的概率趋于定义的概率趋于 0概率概率变化曲线见图变化曲线见图(b)可能超过可能超过由由(2.3)和和(2.4)可知存在一个温度可知存在一个温度t，你现在浏览的是第八页，共22页从上面的讨论得到，从上面的讨论得到，在温度很低时，能量越低的状态在温度很低时，能量越低的状态的概率值越高，在极限状况，只有能量最低的点概率不为的概率值越高，在极限状况，只有能量最低的点概率

6、不为即有即有1.系统在系统在 T 平衡时，系统状态的概率分布趋于平衡时，系统状态的概率分布趋于(2.1)式，式，你现在浏览的是第九页，共22页0.0020.0160.1170.865t=0.50.1810.2210.2690.325t=50.2320.2430.2560.269t=20例例2.1简化概率分布简化概率分布(2.1)为为其中其中q(t)为标准化因子设共有四个能量点为标准化因子设共有四个能量点x=1,2,3,4,在此在此观察观察 t=20,5,0.5,三个温度点概三个温度点概率分布变化率分布变化你现在浏览的是第十页，共22页二二 Metropolis准则准则固体在恒定温度下达到热平衡

7、的过程可以进行固体在恒定温度下达到热平衡的过程可以进行模模拟拟1953年，年，Metropolis等提出重要性采样法他等提出重要性采样法他们用下述方法产生固体的状态序列：们用下述方法产生固体的状态序列：先给定以粒子相对位置表征的初始状态先给定以粒子相对位置表征的初始状态 i，作为固体，作为固体的当前状态，该状态的能量是的当前状态，该状态的能量是 Ei 然后用摄动装然后用摄动装置使随机选取的某个粒子的位移随机地产生一微小置使随机选取的某个粒子的位移随机地产生一微小变化，得到一个新状态变化，得到一个新状态 j，新状态的能量是，新状态的能量是Ej 如如Ej Ei，则，则考虑热运动的影响，该新状态是否

8、重要状态，要依据考虑热运动的影响，该新状态是否重要状态，要依据固体处于该状态的几率来固体处于该状态的几率来你现在浏览的是第十一页，共22页判断由判断由(2.1)知，固体处于知，固体处于 i 和和 j 的概率的比值等的概率的比值等于相应于相应Boltzmann因子的比值，即因子的比值，即r是一个小于是一个小于1的数用随机数发生器产生一个的数用随机数发生器产生一个0,1)区间的随机数区间的随机数，若，若r ，则新状态，则新状态 j 作为重要状态，作为重要状态，否则舍去若新状态否则舍去若新状态 j是重要状态，就以是重要状态，就以 j 取代取代 i 成为成为当前状态，否则仍以当前状态，否则仍以 i 为

9、当前状态，再重复以上新状态为当前状态，再重复以上新状态产生过程产生过程在大量固体状态的变换后，系统趋于能量在大量固体状态的变换后，系统趋于能量较低的平衡状态，固体状态的概率分布趋于较低的平衡状态，固体状态的概率分布趋于(2.1)式式的的Boltzmann概率分布概率分布你现在浏览的是第十二页，共22页由由()式可知，高温下可接受与当前状态能差式可知，高温下可接受与当前状态能差较大的新状态为重要状态而在低温下只能接受较大的新状态为重要状态而在低温下只能接受与当前状态能差较小的新状态为重要状态与当前状态能差较小的新状态为重要状态.这与这与不同温度下热运动的影响完全一致在温度趋与不同温度下热运动的影

10、响完全一致在温度趋与零时，就不能接受任一零时，就不能接受任一 Ej Ei 的新状态的新状态 j了了上述接受新状态的准则称为上述接受新状态的准则称为Metropolis准则，准则，相应的算法称为相应的算法称为Metropolis算法这种算法的计算法这种算法的计算量显著减少算量显著减少你现在浏览的是第十三页，共22页三模拟退火算法三模拟退火算法对固体退火过程的研究给人们以新的启示对固体退火过程的研究给人们以新的启示1982年，年，Kirkpatrick等首先意识到固体退火过程等首先意识到固体退火过程与组合优化问题之间存在的类似性，与组合优化问题之间存在的类似性，Metropolis等对固体在恒定温

11、度下达到热平衡的模拟也给他等对固体在恒定温度下达到热平衡的模拟也给他们以启迪：应该把们以启迪：应该把Metropolis准则引入到过程中来准则引入到过程中来最终他们得到一种对最终他们得到一种对Metropolis算法进行迭代的算法进行迭代的组合优化算法，这种算法组合优化算法，这种算法模拟固体退火过程，称之模拟固体退火过程，称之为模拟退火算法为模拟退火算法你现在浏览的是第十四页，共22页我们可以将我们可以将组合优化问题同金属物体退火进组合优化问题同金属物体退火进行类比行类比：组合优化问题组合优化问题金属物体金属物体假设算法用以解决如下组合优化问题：假设算法用以解决如下组合优化问题：解解费用费用(

12、目标目标)函数函数最优解最优解状态状态能量能量能量最低的状态能量最低的状态你现在浏览的是第十五页，共22页模拟退火算法模拟退火算法Step1任选一个初始解任选一个初始解 x0；xi:=x0；k:=0；Step2若在该温度达到内循环条件，则到若在该温度达到内循环条件，则到step3;Step3 tk+1:=d(tk)；k:=k+1；若满足停止条件，终；若满足停止条件，终t0:=tmax；(初始温度初始温度)；否则，从邻域否则，从邻域 N(xi)中中随机随机选一选一xj，计算，计算fij=f(xj)f(xi)；若；若fij 0，则，则 xi:=xj；否；否则若则若exp(fij/tk)random

13、(0,1)时，则时，则 xi:=xj；重复；重复step2；止计算；否则，回到止计算；否则，回到step2产生一个产生一个0与与1之间的一个随之间的一个随机数机数你现在浏览的是第十六页，共22页(1)随算法进程递减其值的随算法进程递减其值的控制参数控制参数 t 担当固体退火担当固体退火过程中的温度过程中的温度 T 的角色的角色(2)对对 t 的每一取值，算法持续进行的每一取值，算法持续进行“产生新解判断产生新解判断接受舍弃接受舍弃”的迭代过程就对应着固体在某一恒定温的迭代过程就对应着固体在某一恒定温度下度下趋于热平衡的过程趋于热平衡的过程也就是执行了一次也就是执行了一次Metropolis算法

14、模拟退火算法从某个初始解出发，经算法模拟退火算法从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值时组合优过大量解的变换后，可以求得给定控制参数值时组合优化问题的化问题的相对最优解相对最优解然后然后减小减小t 的值，的值，重复执行重复执行Metropolis算法，就可以算法，就可以在在 t 趋于零时，最终求得整趋于零时，最终求得整体最优解体最优解(3)由于退火必须由于退火必须“徐徐徐徐”降温，降温，t 也必须也必须缓慢衰减缓慢衰减，才能确保模拟退火算法最终趋于组合优化问题的整体才能确保模拟退火算法最终趋于组合优化问题的整体最优解集最优解集你现在浏览的是第十七页，共22页(4)模拟退火

15、算法依据模拟退火算法依据Metropolis准则接受新解，准则接受新解，因此因此除接受优化解外，还在一个限定范围内接受恶除接受优化解外，还在一个限定范围内接受恶化解化解，这正是，这正是模拟退火算法与局部搜索算法的本模拟退火算法与局部搜索算法的本质区别所在质区别所在开始时开始时 t 值大，可能接受较差的恶值大，可能接受较差的恶化解；随着化解；随着 t 的减小，只能接受较好的恶化解；最后的减小，只能接受较好的恶化解；最后在在 t 值趋于零时，就不再接受任何恶化解了这值趋于零时，就不再接受任何恶化解了这就使算法就使算法既可以从局部最优的陷阱中跳出，更既可以从局部最优的陷阱中跳出，更有可能求得组合优化

16、问题的整体最优解有可能求得组合优化问题的整体最优解；又不；又不失简单性和通用性因此对大多数组合优化问失简单性和通用性因此对大多数组合优化问题而言，模拟退火算法要题而言，模拟退火算法要优于优于局部搜索算法局部搜索算法你现在浏览的是第十八页，共22页模拟退火算法的数学模型可以描述为：模拟退火算法的数学模型可以描述为：在给定邻在给定邻域结构后，模拟退火过程是从一个状态到另一个状态不域结构后，模拟退火过程是从一个状态到另一个状态不断地随机游动断地随机游动我们可用我们可用马尔可夫链马尔可夫链描述这一过程描述这一过程当温度当温度 t 为一确定值时，两个状态的为一确定值时，两个状态的转移概率转移概率定义定义

17、为：为：Gij(t)称为从称为从 i 到到 j 的的产生概率产生概率，Gij(t)表示在状态表示在状态i时，时，j 状态被选取的概率比较容易理解的是状态被选取的概率比较容易理解的是 j是是 i 的的邻居，如果在邻域中等概率选取，则邻居，如果在邻域中等概率选取，则 j 被被你现在浏览的是第十九页，共22页选中的概率为选中的概率为Aij(t)称为称为接受概率接受概率，Aij(t)表示在状态表示在状态 i 产生产生 j 后，接后，接受受 j 的概率，如在模拟退火算法中接受的概率是的概率，如在模拟退火算法中接受的概率是你现在浏览的是第二十页，共22页(2.5),(2.6),(2.7)为模拟退火算法的主

18、要模型模为模拟退火算法的主要模型模拟退火算法主要可以分为两类第一类为拟退火算法主要可以分为两类第一类为齐次算法齐次算法，在在(2.5)中对每一个固定的中对每一个固定的 t，计算对应的马尔可，计算对应的马尔可夫链变化，直至达到一个稳定状态，然后再使温夫链变化，直至达到一个稳定状态，然后再使温度下降第二类是度下降第二类是非齐次算法非齐次算法，由一个马尔可夫链，由一个马尔可夫链组成，要求在两个相邻的转移中，温度组成，要求在两个相邻的转移中，温度 t 是下降的是下降的你现在浏览的是第二十一页，共22页描述模拟退火算法过程的马尔可夫链应满足下列描述模拟退火算法过程的马尔可夫链应满足下列条件：条件：(1)可达性可达性无论起点如何，任何一个状态都可无论起点如何，任何一个状态都可以到达以到达(2)渐进不依赖起点渐进不依赖起点(3)分布稳定性分布稳定性包含两个内容：一是当温度不变包含两个内容：一是当温度不变时，其马尔可夫链的极限分布存在；二是当温度渐时，其马尔可夫链的极限分布存在；二是当温度渐近近 0时，其马尔可夫链也有极限分布时，其马尔可夫链也有极限分布(4)收敛到最优解收敛到最优解当温度渐近当温度渐近 0时，最优状态时，最优状态的极限分布和为的极限分布和为1你现在浏览的是第二十二页，共22页