模拟退火算法第三节.ppt

文档介绍：模拟退火算法第三节
第一页，共24页
一．冷却进度表的一般概念
定义：一个冷却进度表应当规定下述参数：
１．控制参数t 的初值 t0 ；即初始温度的选取．
２．控制参数t 的衰减函数；即温度下降的规则．
３．马氏链的长度 Lk ；即每一温度马氏链的迭代长度．
４．控制参数t 的终值tf ．即停止准则．
第二页，共24页
二．冷却进度表的选取原则
任一有效的冷却进度表都必须妥善解决两个问题：一是算法的收敛性问题．已经证明模拟退火算法在一定条件下的渐近收敛性．但这并不意味着任一冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解．这个问题可以通过 tk，Lk 以及停止准则的合理选取加以解决．
二是模拟退火算法的实验性能问题．算法的实
验性能一般用两个指标－平均情况下最终解的质
量和CPU时间－来衡量．模拟退火算法最终解的
第三页，共24页
质量与相应CPU时间呈反向关系，很难两全其美．实验性能问题的妥善解决只有一种方法：折衷，即在合理的CPU时间里尽量提高最终解的质量．这种抉择涉及冷却进度表所有参数的合理选取．
冷却进度表可以根据经验法则（基于折衷原
则）或理论分析（基于准平衡概念）选取．经验
法则从合理的CPU时间出发，探索提高最终解质
量的途径，简单直观而有赖丰富的实践；理论分
析由最终解的质量入手，寻求缩减CPU时间的方
法，精细透彻却难免繁琐的推证．只有综合两者
的优势才能构造出高效的冷却进度表．
第四页，共24页
1.　控制参数初值 t0 的选取．
（１）起始温度 t0 应保证平稳分布中每一状态的
概率相等．应让初始接受率
由Metropolis准则
可推知 t0 值很大．例如取 0  ，则在 fij 100时， t0 > 949．
下面给出数值计算估计 t0 的方法．数值计算估计方法的基本思想是给出一个值 0 ( 0接近1，如 0  , 等)，对给定的初始温度 t0 用以下的算法：
第五页，共24页
初始温度数值计算算法
Step1　给定一个常量T; 初始温度 t0; 0; R0= 0; k:=1;
Step2　在该温度迭代 L步( L为一个给定的常 数)，分
Step3　当|Rk 0|<ε时，停止计算；否则，当Rk1和
通过数值计算, 可以估计出温度t0 .
别记录模拟退火算法中接受和被拒绝的个数，计算接受的状态数同迭代步数 L的比率 Rk ；
Rk< 0时，则k:=k+1，t0:= t0+T，返回step2；当Rk 1和Rk 0 时，则k:=k+1，t0:= t0 T，返回step2; 当Rk1  0且Rk  0时, 则k:=k+1, t0:= t0 +T/2, T:= T/2, 返回step2; 当Rk1  0且Rk  0时, 则k:=k+1, t0:= t0 T/2 , 返回step2.
第六页，共24页
（２）由
可给出一个估计值为t0 =Kδ，
K充分大的数，其中，
实际计算中，可以选 K=10,20,100…等实验值．
对一些问题，有时可以简单地估计，如对TSP的 估计．
则可用1替代．
第七页，共24页
但有的时候，会出现 比较难估计．此时，通常采用统计的方法估计费用函数的上下限．
假设f(i)iD是一个大样本空间, 且服从正态分布,
即f(i)iD的密度函数为
从状态空间D中随机选 n个独立样本Xi  i 1,,n
样本均值统计量为
样本方差统计量为
则估计的值为
第八页，共24页
（３）Aarts等人也提出了一个计算 t0的方法．他们的做法是：假定对控制参数的某个确定值 t 产生一个m 次变换的序列，并设m1和m2分别是其中目
则接受率  可用下式近似：
只要将  设定为初始接受率 0，就能求出相应的
t0值．
是m2次目标函数
标函数减小和增大的变换数，
增大变换的平均增量．
第九页，共24页
2.　齐次算法的温度下降方法
为避免算法进程产生过长的马氏链，控制参数
tk 的衰减量以小为宜．我们可猜想在控制参数小
衰减量的情况下，两个相继值 tk 和tk1 上的平稳
分布是相互逼近的．因此，如果在值tk 上已经达
到准平衡，则可以期望在tk 值衰减为tk1 值后，可能只需进行少量的变换就足以恢复tk1 值上的准平衡．这样就可以选取较短长度的马氏链来缩减CPU时间．
第十页，共24页