模拟退火算法第三节.ppt

《模拟退火算法第三节.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2.3实现的技术问题(冷却进度表)模拟退火算法的渐近收敛性意味着：对多数组合优化问题来说，算法的执行过程只有进行无限多次变换后，才能返回一个整体最优解．因而作为最优化算法，模拟退火算法的执行过程不能囿于多项式时间，它是一种指数时间算法，因而无法应用于实际．按理论要求，齐次算法要在每一个温度迭代无穷步以达到平稳分布，而非齐次算法要求温度下降的迭代次数是指数次．从应用的角度来看，在可接受的时间里得到满意的解就可以了，因此本节介绍的技术问题无法保证模拟退火算法得到全局最优解．应用这些技术的模拟退火算法还是一种启发式算法．一．冷却进度表的一般概念定义：一个冷却进

2、度表应当规定下述参数：１．控制参数t的初值t0；即初始温度的选取．２．控制参数t的衰减函数；即温度下降的规则．３．马氏链的长度Lk；即每一温度马氏链的迭代长度．４．控制参数t的终值tf．即停止准则．二．冷却进度表的选取原则任一有效的冷却进度表都必须妥善解决两个问题：一是算法的收敛性问题．已经证明模拟退火算法在一定条件下的渐近收敛性．但这并不意味着任一冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解．这个问题可以通过tk，Lk以及停止准则的合理选取加以解决．二是模拟退火算法的实验性能问题．算法的实验性能一般用两

3、个指标－平均情况下最终解的质量和CPU时间－来衡量．模拟退火算法最终解的质量与相应CPU时间呈反向关系，很难两全其美．实验性能问题的妥善解决只有一种方法：折衷，即在合理的CPU时间里尽量提高最终解的质量．这种抉择涉及冷却进度表所有参数的合理选取．冷却进度表可以根据经验法则（基于折衷原则）或理论分析（基于准平衡概念）选取．经验法则从合理的CPU时间出发，探索提高最终解质量的途径，简单直观而有赖丰富的实践；理论分析由最终解的质量入手，寻求缩减CPU时间的方法，精细透彻却难免繁琐的推证．只有综合两者的优势才能构造出高效的冷却进度表．1.控制参数初值t0的选取．

4、（１）起始温度t0应保证平稳分布中每一状态的概率相等．应让初始接受率由Metropolis准则可推知t0值很大．例如取00.9，则在fij100时，t0>949．下面给出数值计算估计t0的方法．数值计算估计方法的基本思想是给出一个值0(0接近1，如00.9,0.8等)，对给定的初始温度t0用以下的算法：初始温度数值计算算法Step1给定一个常量T;初始温度t0;0;R0=0;k:=1;Step2在该温度迭代L步(L为一个给定的常数)，分Step3当

5、Rk0

6、<ε时，停止计算；否则，当Rk1和通过数值计算,可以估计出温度t0.别记录

7、模拟退火算法中接受和被拒绝的个数，计算接受的状态数同迭代步数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.（２）由可给出一个估计值为t0=Kδ，K充分大的数，其中，实际计算中，可以选K=10,20,100…等实验值．对一些问题，有时可以简单地估计，如对TSP的估

8、计．则可用1替代．但有的时候，会出现比较难估计．此时，通常采用统计的方法估计费用函数的上下限．假设f(i)iD是一个大样本空间,且服从正态分布,即f(i)iD的密度函数为从状态空间D中随机选n个独立样本Xii1,,n样本均值统计量为样本方差统计量为则估计的值为（３）Aarts等人也提出了一个计算t0的方法．他们的做法是：假定对控制参数的某个确定值t产生一个m次变换的序列，并设m1和m2分别是其中目则接受率可用下式近似：只要将设定为初始接受率0，就能求出相应的t0值．是m2次目标函数标函数减小和增大的变换数，增大变换

9、的平均增量．2.齐次算法的温度下降方法为避免算法进程产生过长的马氏链，控制参数tk的衰减量以小为宜．我们可猜想在控制参数小衰减量的情况下，两个相继值tk和tk1上的平稳分布是相互逼近的．因此，如果在值tk上已经达到准平衡，则可以期望在tk值衰减为tk1值后，可能只需进行少量的变换就足以恢复tk1值上的准平衡．这样就可以选取较短长度的马氏链来缩减CPU时间．控制参数小衰减量还可能导致算法进程迭代次数的增加，因而可以期望算法进程接受更多的变换，访问更多的邻域，搜索更大范围的解空间，返回更高质的最终解，当然也花费更多的CPU时间．实验结果表明，只要衰减函

10、数选得恰当，就能在不影响CPU时间合理性的前提下，较大幅度地提高最终解的质量．此