模拟退火算法第三节

模拟退火算法第三节第一页，共二十四页，编辑于2023年，星期六一．冷却进度表的一般概念定义：一个冷却进度表应当规定下述参数：１．控制参数t的初值t0

；即初始温度的选取．２．控制参数t

的衰减函数；即温度下降的规则．３．马氏链的长度Lk

；即每一温度马氏链的迭代长度．４．控制参数t的终值tf

．即停止准则．第二页，共二十四页，编辑于2023年，星期六二．冷却进度表的选取原则任一有效的冷却进度表都必须妥善解决两个问题：一是算法的收敛性问题．已经证明模拟退火算法在一定条件下的渐近收敛性．但这并不意味着任一冷却进度表都能确保算法收敛，不合理的冷却进度表会使算法在某些解间“振荡”而不能收敛于某一近似解．这个问题可以通过tk，Lk

以及停止准则的合理选取加以解决．

二是模拟退火算法的实验性能问题．算法的实验性能一般用两个指标－平均情况下最终解的质量和CPU时间－来衡量．模拟退火算法最终解的第三页，共二十四页，编辑于2023年，星期六质量与相应CPU时间呈反向关系，很难两全其美．实验性能问题的妥善解决只有一种方法：折衷，即在合理的CPU时间里尽量提高最终解的质量．这种抉择涉及冷却进度表所有参数的合理选取．冷却进度表可以根据经验法则（基于折衷原则）或理论分析（基于准平衡概念）选取．经验法则从合理的CPU时间出发，探索提高最终解质量的途径，简单直观而有赖丰富的实践；理论分析由最终解的质量入手，寻求缩减CPU时间的方法，精细透彻却难免繁琐的推证．只有综合两者的优势才能构造出高效的冷却进度表．第四页，共二十四页，编辑于2023年，星期六1.控制参数初值t0的选取．（１）起始温度t0应保证平稳分布中每一状态的概率相等．应让初始接受率由Metropolis准则可推知t0值很大．例如取00.9，则在fij100时，t0>949．下面给出数值计算估计t0的方法．数值计算估计方法的基本思想是给出一个值0

(0接近1，如0

0.9,0.8等)，对给定的初始温度t0用以下的算法：第五页，共二十四页，编辑于2023年，星期六初始温度数值计算算法Step1给定一个常量T;初始温度

t0;0;R0=0;k:=1;Step2在该温度迭代L步(L为一个给定的常数)，分

Step3当|Rk0|<ε时，停止计算；否则，当Rk1和通过数值计算,可以估计出温度t0.别记录模拟退火算法中接受和被拒绝的个数，计算接受的状态数同迭代步数

L的比率

Rk

；

Rk<0时，则k:=k+1，t0:=t0+T，返回step2；当Rk1和Rk0

时，则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.第六页，共二十四页，编辑于2023年，星期六（２）由可给出一个估计值为t0=Kδ，K充分大的数，其中，实际计算中，可以选K=10,20,100…等实验值．对一些问题，有时可以简单地估计，如对TSP的

估计．则可用1替代．第七页，共二十四页，编辑于2023年，星期六但有的时候，会出现

比较难估计．此时，通常采用统计的方法估计费用函数的上下限．假设f(i)iD是一个大样本空间,且服从正态分布,即f(i)iD的密度函数为从状态空间D中随机选n个独立样本Xii1,,n样本均值统计量为样本方差统计量为则估计的值为第八页，共二十四页，编辑于2023年，星期六（３）Aarts等人也提出了一个计算t0的方法．他们的做法是：假定对控制参数的某个确定值t产生一个m次变换的序列，并设m1和m2分别是其中目则接受率

可用下式近似：只要将

设定为初始接受率0，就能求出相应的t0值．是m2次目标函数标函数减小和增大的变换数，增大变换的平均增量．第九页，共二十四页，编辑于2023年，星期六2.齐次算法的温度下降方法为避免算法进程产生过长的马氏链，控制参数tk的衰减量以小为宜．我们可猜想在控制参数小衰减量的情况下，两个相继值tk和tk1

上的平稳分布是相互逼近的．因此，如果在值tk上已经达到准平衡，则可以期望在tk

值衰减为tk1

值后，可能只需进行少量的变换就足以恢复tk1

值上的准平衡．这样就可以选取较短长度的马氏链来缩减CPU时间．第十页，共二十四页，编辑于2023年，星期六控制参数小衰减量还可能导致算法进程迭代次数的增加，因而可以期望算法进程接受更多的变换，访问更多的邻域，搜索更大范围的解空间，返回更高质的最终解，当然也花费更多的CPU时间．实验结果表明，只要衰减函数选得恰当，就能在不影响CPU时间合理性的前提下，较大幅度地提高最终解的质量．此外，如上所述，在控制参数小衰减量的情况中，可以选取短马氏链缩减CPU时间．第十一页，共二十四页，编辑于2023年，星期六齐次算法的理论要求温度下降到零，整个系统以概率１收敛到全局最优解．无论直观理解还是理论要求，温度总是下降的．因此，一个非常直观的下降方法是：(1)tk1tk，k

0,1,2,其中0<<1，是一个接近1的常数．越接近1温度下降得越慢．这个衰减函数被许多研究者采用，他们选用的值是0.5－0.99．这种方法简单易行，很受应用人员的欢迎．它的每一步以相同的比率下降．第十二页，共二十四页，编辑于2023年，星期六其中t0为初始温度，L为算法温度下降的总次数．这一下降方法的优点是易于操作，而且可以简单的控制温度下降的总步数．它的每一步下降长度相等．只适用于以迭代次数为停止准则的冷却进度表．第十三页，共二十四页，编辑于2023年，星期六3.齐次算法每一温度的迭代长度规则．即马氏链长度Lk的选取．

Lk值给定算法进程在第k个马氏链中进行的变换数，有限序列Lk则规定了算法进程搜索的解范围．由于多数组合优化问题的解空间规模随问题规模n呈指数型增大，为使算法最终解的质量有所保证，理应建立Lk与n间的某种关系．指数型的关系显然是不切合实际的，因而Lk通常取为问题规模n

的一个多项式函数．

（１）固定长度在每一温度，迭代相同的步数，步数的选取同第十四页，共二十四页，编辑于2023年，星期六问题的大小有关，通常采用与邻域大小直接相关的规则．如TSP中的2-opt，邻域大小是(n是城市数)，在同一温度，可取（２）由接受和拒绝的比率来控制迭代步数．当温度很高时，每一个状态被接受的频率基本相同，而且几乎所有的状态都被接受．此时，在同一温度应使迭代的步数尽量小．当温度渐渐变低时，越来越多的状态被拒绝．如果在此温度的第十五页，共二十四页，编辑于2023年，星期六迭代太少，则可能造成过早地陷入局部最优状态，比较直观和有效的方法是随着温度的下降，将同一温度的迭代步长增加．实现的一种方法是给定一个充分大的步长上限U和一个接受次数指标R，当接受次数等于R时，在此温度不再迭代而使温度下降，否则，一直迭代到上限步数．实现的第二种方法是给定一个接受比率指标R，迭代步长上限U和下限L，每一温度至少迭代L步且记录同一温度迭代的总次数和被接受的次数，当迭代超过L步时，若接受次数同总次数的比率不小于R时，在这一温度不再迭代而开始温度下降，否则，一直迭代到上限步数．第十六页，共二十四页，编辑于2023年，星期六同样可以用拒绝次数为指标类似上面的讨论得到一些控制迭代步数的规则．（３）概率控制法．（略）第十七页，共二十四页，编辑于2023年，星期六4.

算法的终止原则．即控制参数终值tf

的选取．中已经提及，即总的温度下模拟退火算法从初始温度开始，通过在每一温度的迭代和温度的下降，最后达到终止原则而停止.尽管有些原则有一定理论的指导，终止原则大多是直观的．下面分类讨论．（１）零度法（即tf

充分小）．模拟退火算法的最终温度为零．因而最为简单的原则是：给定一个比较小的正数ε

，当温度tk

ε时，算法停止．表示已经达到最低温度．（２）循环总数控制法．这一简单原则在齐次算法的温度下降方法（２）第十八页，共二十四页，编辑于2023年，星期六降次数为一定值L，当温度迭代次数达到L时，停止运算．这一原则可分为两类，一类是整个算法的总迭代步数为一固定数．它表示各温度时马氏链迭代数（内循环）的总和为一个给定的数．这样很容易计算算法的复杂性，但需要合理分配内循环的长度和温度下降的次数．另一类是内循环的次数由迭代长度规则的（２）和（３）决定，温度下降次数（外循环）为一个定值．这样的控制法对估计算法的复杂性有一定的困难．第十九页，共二十四页，编辑于2023年，星期六（３）基于不改进规则的控制法．以算法进程所得到的某些近似解为衡量标准，判断算法当前解的质量是否持续得到明显提高，从而确定是否终止算法．Kirkpatrick等人选取的停止准则是，在若干个（取s个如s=1,s=2等）相继的马氏链中解无任何变化（含优化或恶化）就终止算法．

或在一个温度和给定的迭代次数内没有改进当前的局部最优解，则停止算法．模拟退火的一个基本思想是跳出局部最优解．直观的结论是在较高的温度没能跳出局部最优解，则在低的温度跳第二十页，共二十四页，编辑于2023年，星期六出局部最优解的可能也比较小．由此产生上面的停止原则．（４）接受概率控制法．给定一个指标f

>0是一个比较小的数，除当前局部最优解以外，其他状态的接受概率都小于f时，停止运算．实现（３）和（４）时，记录当前局部最优解，给定一个固定的迭代次数，当在规定的次数里没有离开局部最优解或每一次计算的接受概率都小于f，则在这个温度停止计算．第二十一页，共二十四页，编辑于2023年，星期六（５）邻域法若采用产生概率和接受概率且设f0和f1分别为一个邻域内的局部最优和次最优值，当满足时，其中N为邻域的大小，从局部最优到次优的接受概率满足()，而从局部最优到其他费用更高第二十二页，共二十四页，编辑于2023年，星期六的状态的接受概率更小．直观的想法是邻域中每次至少有一个状态被接受，但当满足()时，除局部最优解以外状态的接受概率都小于邻域总点平均数，此时可以认为从局部最优解转移到其他状态的可能性很小，因此停止