文档介绍：历点文延大
Southwest Jiaotong University
模拟退火算法
汇报人:许炯楼2014XX
李娜2014200909
冒亚婷2014200922
李园园2014200923
模拟退火算法及模型
模拟退火算法的来源及基本原理
算法的提出
模拟退火算法最早的思想由 Metropolis等(1953)提出,1983年
Kirkpatrick等将其应用于组合优化。
算法的目的
解决NP复杂性问题
克服优化过程陷入局部极小;
克服初值依赖性。
模拟退火算法的来源及基本原理
物理退火过程:
退火是指将回体加热到足够高的温度,使分子呈随机排列状态,
然后逐步降温使之冷却,最后分孑以低能状态排列,固体达到某
种稳定状态。
加温过程—增强粒子的热运动,消除系统原先可能存在的非均匀态
等温过程—对于与坏境换热而温度不变的封闭系统,系统状态的自发变化总是
朝自由能减少的方向进行,当自由能达到最小时,系统达到平衡态
冷却过程—使粒子热运动减弜并渐趋有序,系统能量逐渐下降,从而得到低能的
晶体结构
模拟退火算法的来源及基本原理
模仿自然界退火現象而得,利用了物理中固体物质的退火过
程与一般优化问题的相似性;
从某一初始温度开始,伴随温度的不断下降,结合概率突跳
特性在解空间中随机寻找全局最优解。
11模退火算法的来源及基本原理
数学表述
在温度T,分孑子停留在状态r满足 Boltzmann概率分布
PE=B()}=
E表示分子能量的松量()表示状舶能量
k2>0为 Boltzman数Z()为概率分布的标准化
E(C
()
ex
k
模拟退火算法的来源及基本思想
数学表述
在同一个温度T,选定两个能量E1<E2,有
>0
模拟退火算法基本思想:在一定温度下,搜索从一个状态随机地变化
到另一个状态;随着温度的不断下降直到最低温度,搜索过程以概率]
停留在最优解
11模找退火算法的来源及基本思想
√ Boltzmann概率分布告诉我们
(1)在同一个温度,分子停留在能量小状态的概率大于停留在能量大状态
的概率
(2)温度越高,不同能量状态对应的概率相差越小;温度足够高时,各状
态对应概率基本相同。
(3)随着温度的下降,能量最低状态对应概率越来越大;温度趋于0时
其状态趋于1
模拟退火算法的来源及基本原理
数学表述
若D为状态空间D中状态的个数,D是具有最低能量的状态集合
当温度很高时,每个状态概率基本相同,接***均值D
状态空间存在超过两个不同能量时,具有最低能量状态的概率超出平均值D
当温度趋于0时,分子停留在最低能量状态的概率趋于1。
能量最低状态
非能量最低状态
11模找退火算法的来源及基本原理
Metropolis准则(1953)—以概率接受新状态
固体在恒定温度下达到热平衡的过程可以用 Monte carlo方法〔计算机随机模拟
方法)加以模拟,虽然该方法简单,但必须大量釆样才能得到比较精确的结果
计算量很大。
若在温度T,当前状态i→新状态;
若E<E,则接受j为当前状态;否则,若概率p= expl-(ErE)n门大于1)区间的
随机数,则仍接受状态j为当前状态;若不成立则保留状态i为当前状态
p=exp[-E EikgT]
在高温下,可接受与当前状态能量差较大的新状态
在低温下,只接受与当前状态能量差较小的新状态。