《模拟退火算法第三节.ppt》由会员分享，可在线阅读，更多相关《模拟退火算法第三节.ppt（24页珍藏版）》请在三一文库上搜索。
1、2.3实现的技术问题(冷却进度表),模拟退火算法的渐近收敛性意味着：对多数组合优化问题来说，算法的执行过程只有进行无限多次变换后，才能返回一个整体最优解因而作为最优化算法，模拟退火算法的执行过程不能囿于多项式时间，它是一种指数时间算法，因而无法应用于实际,按理论要求，齐次算法要在每一个温度迭代无穷步以达到平稳分布，而非齐次算法要求温度下降的迭代次数是指数次从应用的角度来看，在可接受的时间里得到满意的解就可以了，因此本节介绍的技术问题无法保证模拟退火算法得到全局最优解应用这些技术的模拟退火算法还是一种启发式算法,一冷却进度表的一般概念,定义：一个冷却进度表应当规定下述参数： 控制参数t 的初值
2、t0 ；即初始温度的选取 控制参数t 的衰减函数；即温度下降的规则 马氏链的长度 Lk ；即每一温度马氏链的迭代长度 控制参数t 的终值tf 即停止准则,二冷却进度表的选取原则,任一有效的冷却进度表都必须妥善解决两个问题：一是算法的收敛性问题已经证明模拟退火算法在一定条件下的渐近收敛性但这并不意味着任一冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解这个问题可以通过 tk，Lk 以及停止准则的合理选取加以解决,二是模拟退火算法的实验性能问题算法的实 验性能一般用两个指标平均情况下最终解的质 量和CPU时间来衡量模拟退火算法最终解的,质量与相应CPU
3、时间呈反向关系，很难两全其美实验性能问题的妥善解决只有一种方法：折衷，即在合理的CPU时间里尽量提高最终解的质量这种抉择涉及冷却进度表所有参数的合理选取,冷却进度表可以根据经验法则（基于折衷原 则）或理论分析（基于准平衡概念）选取经验 法则从合理的CPU时间出发，探索提高最终解质 量的途径，简单直观而有赖丰富的实践；理论分 析由最终解的质量入手，寻求缩减CPU时间的方 法，精细透彻却难免繁琐的推证只有综合两者 的优势才能构造出高效的冷却进度表,1.控制参数初值 t0 的选取,（）起始温度 t0 应保证平稳分布中每一状态的 概率相等应让初始接受率,由Metropolis准则,可推知 t0 值很大
4、例如取 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当|Rk 0|时，停止计算；否则，当Rk1和,通过数值计算, 可以估计出温度t0 .,别记录模拟退火算法中接受和被拒绝的个数，计算接受的状态数同迭代步数 L的比率 Rk ；,Rk 0时，则k:=k+1，t
5、0:= t0+T，返回step2；当Rk 1和Rk 0 时，则k:=k+1，t0:= t0 T，返回step2; 当Rk1 0且Rk 0时, 则k:=k+1, t0:= t0 +T/2, T:= T/2, 返回step2; 当Rk1 0且Rk 0时, 则k:=k+1, t0:= t0 T/2 , 返回step2.,K充分大的数，其中，,实际计算中，可以选 K=10,20,100等实验值,对一些问题，有时可以简单地估计，如对TSP的 估计,则可用1替代,但有的时候，会出现 比较难估计此时，通常采用统计的方法估计费用函数的上下限,假设f(i)iD是一个大样本空间, 且服从正态分布,即f(i)iD的
6、密度函数为,从状态空间D中随机选 n个独立样本Xi i 1,n,样本均值统计量为,样本方差统计量为,则估计的值为,（）Aarts等人也提出了一个计算 t0的方法他们的做法是：假定对控制参数的某个确定值 t 产生一个m 次变换的序列，并设m1和m2分别是其中目,则接受率 可用下式近似：,只要将 设定为初始接受率 0，就能求出相应的 t0值,增大变换的平均增量,2.齐次算法的温度下降方法,为避免算法进程产生过长的马氏链，控制参数 tk 的衰减量以小为宜我们可猜想在控制参数小 衰减量的情况下，两个相继值 tk 和tk1 上的平稳 分布是相互逼近的因此，如果在值tk 上已经达 到准平衡，则可以期望在t
7、k 值衰减为tk1 值后，可能只需进行少量的变换就足以恢复tk1 值上的准平衡这样就可以选取较短长度的马氏链来缩减CPU时间,控制参数小衰减量还可能导致算法进程迭代次数的增加，因而可以期望算法进程接受更多的变换，访问更多的邻域，搜索更大范围的解空间，返回更高质的最终解，当然也花费更多的CPU时间实验结果表明，只要衰减函数选得恰当，就能在不影响CPU时间合理性的前提下，较大幅度地提高最终解的质量此外，如上所述，在控制参数小衰减量的情况中，可以选取短马氏链缩减CPU时间,齐次算法的理论要求温度下降到零，整个系统 以概率收敛到全局最优解无论直观理解还是 理论要求，温度总是下降的因此，一个非常直 观的
8、下降方法是：,(1) tk1 tk，k 0,1,2, 其中 0 1，是一个接近1的常数 越接近1温度下降得越慢这个衰减函数被许多研究者采用，他们选用的值是0.50.99这种方法简单易行，很受应用人员的欢迎它的每一步以相同的比率下降,其中t0为初始温度，L为算法温度下降的总次数这一下降方法的优点是易于操作，而且可以简单的控制温度下降的总步数它的每一步下降长度相等只适用于以迭代次数为停止准则的冷却进度表,3.齐次算法每一温度的迭代长度规则即马氏 链长度 Lk 的选取,Lk值给定算法进程在第k个马氏链中进行的变 换数，有限序列Lk则规定了算法进程搜索的解 范围由于多数组合优化问题的解空间规模随问 题
9、规模n呈指数型增大，为使算法最终解的质量 有所保证，理应建立 Lk与n间的某种关系指数 型的关系显然是不切合实际的，因而Lk通常取为 问题规模n 的一个多项式函数,（）固定长度,在每一温度，迭代相同的步数，步数的选取同,问题的大小有关，通常采用与邻域大小直接相关,的规则如TSP中的2-opt，邻域大小是,(n是城市数)，在同一温度，可取,（）由接受和拒绝的比率来控制迭代步数,当温度很高时，每一个状态被接受的频率基本 相同，而且几乎所有的状态都被接受此时，在 同一温度应使迭代的步数尽量小当温度渐渐变 低时，越来越多的状态被拒绝如果在此温度的,迭代太少，则可能造成过早地陷入局部最优状态，比较直观和
10、有效的方法是随着温度的下降，将同一温度的迭代步长增加实现的一种方法是给定一个充分大的步长上限U和一个接受次数指标R，当接受次数等于R时，在此温度不再迭代而使温度下降，否则，一直迭代到上限步数实现的第二种方法是给定一个接受比率指标R，迭代步长上限U和下限 L，每一温度至少迭代 L步且记录同一温度迭代的总次数和被接受的次数，当迭代超过 L步时，若接受次数同总次数的比率不小于R时，在这一温度不再迭代而开始温度下降，否则，一直迭代到上限步数,同样可以用拒绝次数为指标类似上面的讨论得到一些控制迭代步数的规则,（）概率控制法（略）,4.算法的终止原则即控制参数终值tf 的选取,中已经提及，即总的温度下,模
11、拟退火算法从初始温度开始，通过在每一温度的迭代和温度的下降，最后达到终止原则而停止. 尽管有些原则有一定理论的指导，终止原则大多是直观的下面分类讨论,（）零度法（即tf 充分小）,模拟退火算法的最终温度为零因而最为简单的原则是：给定一个比较小的正数 ，当温度tk 时，算法停止表示已经达到最低温度,（）循环总数控制法,这一简单原则在齐次算法的温度下降方法（）,降次数为一定值L，当温度迭代次数达到L时，停止运算这一原则可分为两类，一类是整个算法的总迭代步数为一固定数它表示各温度时马氏链迭代数（内循环）的总和为一个给定的数这样很容易计算算法的复杂性，但需要合理分配内循环的长度和温度下降的次数另一类是
12、内循环的次数由迭代长度规则的（）和（）决定，温度下降次数（外循环）为一个定值这样的控制法对估计算法的复杂性有一定的困难,（）基于不改进规则的控制法,以算法进程所得到的某些近似解为衡量标准， 判断算法当前解的质量是否持续得到明显提高， 从而确定是否终止算法Kirkpatrick等人选取 的停止准则是，在若干个（取s个如s=1,s=2等） 相继的马氏链中解无任何变化（含优化或恶化） 就终止算法,或在一个温度和给定的迭代次数内没有改进当前的局部最优解，则停止算法模拟退火的一个基本思想是跳出局部最优解直观的结论是在较高的温度没能跳出局部最优解，则在低的温度跳,出局部最优解的可能也比较小由此产生上面的停
13、止原则,（）接受概率控制法,给定一个指标 f 0是一个比较小的数，除当前局部最优解以外，其他状态的接受概率都小于f 时，停止运算实现（）和（）时，记录当前局部最优解，给定一个固定的迭代次数，当在规定的次数里没有离开局部最优解或每一次计算的接受概率都小于f ，则在这个温度停止计算,（）邻域法,若采用产生概率,和接受概率,且设 f0 和 f1 分别为一个邻域内的局部最优和次最优值，当满足,时，其中N为邻域的大小，从局部最优到次优的接受概率满足()，而从局部最优到其他费用更高,的状态的接受概率更小直观的想法是邻域中每 次至少有一个状态被接受，但当满足()时，除局部最优解以外状态的接受概率都小于邻域总点平均数，此时可以认为从局部最优解转移到其他状态的可能性很小，因此停止通过()可得终止温度,（）终止温度的精细估计（略）,理论上是用一个马尔可夫链描述模拟退火算法的变化过程，因此具有全局最优性实际应用中的模拟退火算法是一个启发式算法它有诸多的参数需要调整，如起始温度，温度下降的方案，固定温度时的迭代长度及终止规则等，这样需要人为地调整人为的因素，如对问题的了解，参数和规则的搭配等，造成计算结果的差异解决这个矛盾的方法主要通过大量的数值模拟计算，从中选择比较好的参数搭配,