模拟退火算法 第三节

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,2.3,实现的技术问题,(,冷却进度表,),模拟退火算法的渐近收敛性意味着：对多数组合优化问题来说，算法的执行过程只有进行,无限多次变换,后，才能返回一个整体最优解因而作为最优化算法，,模拟退火算法的执行过程不能囿于多项式时间，它是一种指数时间算法，因而无法应用于实际,按理论要求，齐次算法要在每一个温度迭代无穷步以达到平稳分布，而非齐次算法要求温度下降的迭代次数是指数次从应用的角度来看，在可接受的时间里得到满意的解就可以了，因此,本节介绍的技术问题无法保证模拟退火算法得到全局最优解应用这些技术的模拟退火算法还是一种启发式算法,一冷却进度表的一般概念,定义：,一个冷却进度表应当规定下述参数：,控制参数,t,的初值,t,0,；即,初始温度的选取,控制参数,t,的衰减函数；即,温度下降的规则,马氏链的长度,L,k,；即,每一温度马氏链的迭代长度,控制参数,t,的终值,t,f,即停止准则,二冷却进度表的选取原则,任一有效的冷却进度表都必须妥善解决两个问题：,一是算法的收敛性问题,已经证明模拟退火算法在一定条件下的渐近收敛性但这并不意味着任一冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解这个问题,可以通过,t,k,，,L,k,以及停止准则的合理选取加以解决,二是模拟退火算法的实验性能问题,算法的实,验性能一般用两个指标平均情况下最终解的质,量和,CPU,时间来衡量模拟退火算法最终解的,质量与相应,CPU,时间呈反向关系，很难两全其美实验性能问题的妥善解决只有一种方法：,折衷,，即在合理的,CPU,时间里尽量提高最终解的质量这种抉择涉及冷却进度表所有参数的合理选取,冷却进度表可以根据,经验法则,（基于折衷原,则）或,理论分析,（基于准平衡概念）选取经验,法则从合理的,CPU,时间出发，探索提高最终解质,量的途径，简单直观而有赖丰富的实践；理论分,析由最终解的质量入手，寻求缩减,CPU,时间的方,法，精细透彻却难免繁琐的推证只有综合两者,的优势才能构造出高效的冷却进度表,1.,控制参数初值,t,0,的选取,（）起始温度,t,0,应保证平稳分布中每一状态的,概率相等应让,初始接受率,由,Metropolis,准则,可推知,t,0,值很大,例如取,0, 0.9,，则在,f,ij,100,时，,t,0, 949,下面给出数值计算估计,t,0,的方法数值计算估计方法的基本思想是给出一个值,0,(,0,接近,1,，如,0, 0.9 , 0.8,等,),，对给定的初始温度,t,0,用以下的算法：,初始温度数值计算算法,Step1,给定一个常量,T,;,初始温度,t,0,;,0,;,R,0,= 0;,k,:=1;,Step2,在该温度迭代,L,步,(,L,为一个给定的常 数,),，分,Step3,当,|,R,k,0,|,时，停止计算；否则，当,R,k,1,和,通过数值计算,可以估计出温度,t,0,.,别记录模拟退火算法中接受和被拒绝的个数，计算接受的状态数同迭代步数,L,的比率,R,k,；,R,k,0,时，则,k,:=,k,+1,，,t,0,:=,t,0,+,T,，返回,step2,；当,R,k,1,和,R,k,0,时，则,k,:=,k,+1,，,t,0,:=,t,0,T,，返回,step2;,当,R,k,1,0,且,R,k,0,时,则,k,:=,k,+1,t,0,:=,t,0,+,T,/2,T,:=,T,/2,返回,step2;,当,R,k,1,0,且,R,k,0,时,则,k,:=,k,+1,t,0,:=,t,0,T,/2 ,返回,step2.,（）由,可给出一个估计值为,t,0,=,K,，,K,充分大的数，其中，,实际计算中，可以选,K,=10,20,100,等实验值,对一些问题，有时可以简单地估计,，如对,TSP,的,估计,则可用,1,替代,但有的时候，会出现,比较难估计此时，通常采用统计的方法估计费用函数的上下限,假设,f,(,i,),i,D,是一个大样本空间,且服从正态分布,即,f,(,i,),i,D,的密度函数为,从状态空间,D,中随机选,n,个独立样本,X,i,i,1,n,样本均值统计量为,样本方差统计量为,则估计,的值为,（）,Aarts,等人也提出了一个计算,t,0,的方法他们的做法是：假定对控制参数的某个确定值,t,产生一个,m,次变换的序列，并设,m,1,和,m,2,分别是其中目,则接受率,可用下式近似：,只要将,设定为初始接受率,0,，就能求出相应的,t,0,值,是,m,2,次目标函数,标函数减小和增大的变换数，,增大变换的平均增量,2.,齐次算法的温度下降方法,为避免算法进程产生过长的马氏链，控制参数,t,k,的衰减量,以小为宜,我们可猜想在控制参数小,衰减量的情况下，两个相继值,t,k,和,t,k,1,上的平稳,分布是相互逼近的因此，如果在值,t,k,上已经达,到准平衡，则可以期望在,t,k,值衰减为,t,k,1,值后，可能只需进行少量的变换就足以恢复,t,k,1,值上的准平衡这样就可以选取较短长度的马氏链来缩减,CPU,时间,控制参数小衰减量还可能导致算法进程迭代次数的增加，因而可以期望算法进程接受更多的变换，访问更多的邻域，搜索更大范围的解空间，返回更高质的最终解，当然也花费更多的,CPU,时间实验结果表明，只要衰减函数选得恰当，就能在不影响,CPU,时间合理性的前提下，较大幅度地提高最终解的质量此外，如上所述，在控制参数小衰减量的情况中，可以选取短马氏链缩减,CPU,时间,齐次算法的理论要求温度下降到零，整个系统,以概率收敛到全局最优解无论直观理解还是,理论要求，温度总是下降的因此，一个非常直,观的下降方法是：,(1),t,k,1, ,t,k,，,k,0,1,2,其中,0, 0,是一个比较小的数，除当前局部最优解以外，其他状态的接受概率都小于,f,时，停止运算实现（）和（）时，记录当前局部最优解，给定一个固定的迭代次数，当在规定的次数里没有离开局部最优解或每一次计算的接受概率都小于,f,，则在这个温度停止计算,（）,邻域法,若采用产生概率,和接受概率,且设,f,0,和,f,1,分别为一个邻域内的局部最优和次最优值，当满足,时，其中,N,为邻域的大小，从局部最优到次优的接受概率满足,(,),，而从局部最优到其他费用更高,的状态的接受概率更小直观的想法是邻域中每,次至少有一个状态被接受，但当满足,(,),时，除局部最优解以外状态的接受概率都小于邻域总点平均数，此时可以认为从局部最优解转移到其他状态的可能性很小，因此停止通过,(,),可得终止温度,（）终止温度的精细估计（略）,理论上是用一个马尔可夫链描述模拟退火算法的变化过程，因此具有全局最优性实际应用中的模拟退火算法是一个启发式算法它有诸多的参数需要调整，如起始温度，温度下降的方案，固定温度时的迭代长度及终止规则等，这样需要人为地调整,人为的因素，如对问题的了解，参数和规则的搭配等，造成计算结果的差异,解决这个矛盾的方法主要通过大量的数值模拟计算，从中选择比较好的参数搭配,