模拟退火法.ppt

模拟退火法
模拟退火法
模拟退火算法起源于物理退火。
􀂄物理退火过程:
(1)       加温过程
(2)       等温过程
(3)       冷却过程
模拟退火法
发展
􀂄1953年,Metropolis提出重要性采样法,即以概率接受新状态,称Metropolis准则,计算量相对Monte Carlo方法显著减少。
􀂄 1983年,Kirkpatrick等提出模拟退火算法,并将其应用于组合优化问题的求解。
模拟退火法
1)  Metropolis准则提出
    固体在恒定温度下达到热平衡的过程可以用MorteCarol算法方法加以模拟,虽然该方法简单,但必须大量采样才能得到比较精确的结果,因而计算量很大。
鉴于物理系统倾向于能量较低的状态,而热运动又妨碍它准确落到最低态。采样时着重选取那些有重要贡献的状态则可较快达到较好的结果。因此,Metropolis等在1953年提出了重要的采样法,即以概率接受新状态。
模拟退火法
Metropolis准则
     假设在状态xold时,系统受到某种扰动而使其状态变为xnew。与此相对应,系统的能量也从E(xold)变成E(xnew),系统由状态xold变为状态xnew的接受概率p:
模拟退火法
算法流程图
模拟退火法
模拟退火算法-------步骤
1) 随机产生一个初始解x0,令xbest= x0 ,并计算目标函数值E(x0);
2) 设置初始温度T(0)=To,迭代次数i = 1;
3) Do while T(i) > Tmin
1) for j = 1~k
2) 对当前最优解xbest按照某一邻域函数,产生一新的解xnew。计算新的目标函数值E(xnew) ,并计算目标函数值的增量ΔE = E(xnew) - E(xbest) 。
3) 如果ΔE <0,则xbest = xnew;
4) 如果ΔE >0,则p = exp(- ΔE /T(i));
1) 如果c = random[0,1] < p, xbest = xnew; 否则xbest = xbest。
5) End for
4) i = i + 1;
5) End Do
6) 输出当前最优点,计算结束
模拟退火法
模拟退火算法------参数的选择
   􀂄冷却进度表——称调整模拟退火法的一系列重要参数为冷却进度表。它控制参数T的初值及其衰减函数,对应的MARKOV链长度和停止条件,非常重要。
冷却进度表规定的参数:
;;。(即每一次随机游走过程,要迭代多少次,才能趋于一个准平衡分布,即一个局部收敛解位置)
模拟退火法
有效的冷却进度表判据:
:主要取决于衰减函数和马可夫链的长度及停止准则的选择
:最终解的质量和CPU的时间
模拟退火法
参数的选取:一)控制参数初值T0的选取一般要求初始值t0的值要充分大,即一开始即处于高温状态,且Metropolis的接收率约为1。
(1) 均匀抽样一组状态,以各状态目标值的方差为初温。
(2) 随机产生一组状态,确定两两状态间的最大目标值差|Δmax|,然后依据差值,利用一定的函数确定初温。比如,
t0=-Δmax/pr ,其中pr为初始接受概率。