模拟退火算法 第一节.ppt

文档介绍：模拟退火(simulated annealing);采用Metropolis接受准则;并用一组称为冷却进度表的参数控制算法进程,使算法在多项式时间里给出一个近似最优解.
模拟退火算法最早的思想由Metropolis在1953年提出,Kirkpatrick在1983年成功地应用在组合最优化问题中.
第2章模拟退火算法
一固体退火过程
退火是一种物理过程,固体退火是先将固体加热至熔化,再徐徐冷却使之凝固成规整晶体的热力学过程.
退火过程中,系统在每一温度下达到平衡态,系统状态的分布满足一定的概率分布,即在温度 T,系统达到平衡态后,分子停留在状态 r 满足波兹曼(Boltzmann)概率分布
模拟退火算法及模型
其中,E(r)为状态 r 的能量,kB 0为波兹曼常数,
为分子能量的一个随机变量,
(T)为概率分布的标准化因子,
先研究由()确定的函数随 T E1< E2,在同一个温度 T ,有
D 为状态空间.
在同一个温度,(),()的概率分布使得每个状态的概率基本相同,接***均值1D,D为状态空间 D
,具有最低能量状态的波兹曼概率接近并超出平均值1D.
当 rmin 是 D中具有最低能量的状态时,得
由
所以,
关于温度
其中,D0是具有最低能量的状态集合,
因此得到,当 T 趋向于 0 时,
当温度趋向于 0时,()决定的概率渐近
由此可以得到,在温度趋向于 0时,,分子在最低能量状态的概率变化趋势由图(a)表示.
对于非能量最小的状态,由()和分子在能量最小状态的概率是单调减小的事实,在温度较高时,分子在
这些状态的概率在
附近,依赖于状态的不同,
使()决定的概率在(0 ,t)是单调升的;再由()可知,当温度趋于 0时,()定义的概率趋于 (b).
可能超过
由()和()可知存在一个温度t,
从上面的讨论得到,在温度很低时,能量越低的状态的概率值越高,在极限状况,
1. 系统在 T 平衡时,系统状态的概率分布趋于()式,




t=




t=5




t=20
简化概率分布()为
其中q(t)=1, 2, 3, 4,
在此
观察 t = 20, 5, , 三个温度点概
率分布变化.