模拟退火算法Word文档下载推荐.doc
《模拟退火算法Word文档下载推荐.doc》由会员分享，可在线阅读，更多相关《模拟退火算法Word文档下载推荐.doc（26页珍藏版）》请在冰点文库上搜索。
（1）随机产生初始解，给定初始温度，令；
（2）随机产生新解，并计算函数增量；
（3）若，则接受新解，=，转
（2），否则以概率决定是否接受新解。
具体方法是：
产生0和1之间的一个随机数，若，接受新解，否则拒绝新解；
（4）重复第
（2）、（3）步若干次，使解接近当前温度下的最优解，这相当于用足够慢的速度降温，以保证在每个温度时系统都能处于当前温度下的能量最低状态；
（5）按一定的方式降低温度，例如=，其中（0,1）；
（6）若满足收敛条件，退火过程结束，否则，转
（2）。
通常，收敛条件为。
理论已证明：
只要初始温度足够高，退火过程足够慢，模拟退火算法以概率1收敛到全局最优解。
10.2模拟退火算法的渐近收敛性
10.2.1马尔可夫链理论
定义10.1设为随机变量序列，称在时刻k处于状态i，，S称为状态空间。
当S中的状态数有限时，称为有限状态空间。
若对任意的正整数n,满足
则称{X（k）}（k=1,2,…）为马尔可夫链，简称马氏链。
马氏链具有一种记忆功能，它只记忆前一时刻的状态。
上式可以简单地记成
称为一步转移概率。
当状态空间有限时，称为有限马氏链，一步转移概率矩阵记为
当成立时，即从状态i移到状态j的概率与时刻n无关，称马氏链为齐次马氏链。
反之，若转移矩阵与时刻有关，则称此马氏链为非齐次马氏链。
切普曼—柯尔莫哥洛夫方程式：
其中表示m步转移概率，即在时刻n状态为i的条件下，经过m步转移到达状态j的概率。
特别当马尔可夫过程为齐次时切普曼—柯尔莫哥洛夫方程变成
定义10.2如果对状态i和j存在某个,使得，既由状态i出发，经过n次转移以正的概率到达状态j,则称自状态i可达到状态j,并记为。
反之若状态i不能达到j，即对于一切,。
定义10.3若且，则称状态i和j相通，记为
定义10.4设C为状态空间的一个子集，如果从C内任一状态i不能到达C外的任何状态j，即对则称C是闭集。
定义10.5称转移矩阵为P的马尔可夫链为不可约的，若，即除了整个状态空间构成一个闭集外没有别的闭集，这时马氏链中的所有状态都是相通的。
定义10.6称转移矩阵为p的马尔可夫链为非周期的，若对，集合的最大公约数为，其中由所有满足式的整数n>
0组成，且整数称为解i的周期。
故非周期即指出所有解的周期为1。
定理10.1转移矩阵为P的不可约马氏链是非周期的一个充分条件是：
证明:
由不可约性可知，对满足上式的j和有
且
故
其中n=k+l，又由于
因而n,n+1均属于，故
由于，故结论正确。
在讨论模拟退火算法收敛性的过程中用到的一个重要的分布是平稳分布。
定义10.7称转移矩阵为P的有限齐次马尔可夫链的平稳分布为向量q，其第i个分量为，其中且。
若这样的平稳分布q存在，则该平稳分布就是时解的概率分布。
作者不加证明的给出以下重要定理：
定理10.2：
设P为有限齐次马尔可夫链的相伴转移矩阵，若该马氏链是不可约的和非周期的，则其平稳分布q存在且由下式唯一确定：
（1）
其中。
根据模拟退火算法的特点，模拟退火算法的数学模型可以描述为：
在给定邻域结构后，模拟退火过程是从一个状态到另一个状态不断的随机游动。
我们可以用马尔可夫链描述这一过程。
当温度t为一确定值时，两个状态的转移概率定义为
（2）
其中，表示状态集合（解集合）中状态的个数。
称为从i到j的产生概率。
表示在状态i时，j状态被选取的概率。
比较容易理解的是j是i的邻域，如果在邻域中等概率选取，则j被选取的概率是
（3）
称为接受概率，表示在状态i时产生状态j后，接受j的概率，如在模拟退火算法中接受概率是:
（4）
和分别称为产生矩阵、接受矩阵和一步转移概率矩阵。
上述为模拟退火算法的主要模型。
模拟退火算法主要分为两类。
第一类为齐次算法，在
（1）中对每一个固定的t，计算对应的马尔可夫链变化，直到一个稳定状态，然后在使温度下降。
第二类是非齐次算法，由一个马尔可夫链组成，要求在两个相邻的转移中，温度t是下降的。
无论从实际和直观，描述模拟退火过程的马尔可夫链应满足下列条件:
（1）可达性。
无论起点如何，任何一个状态都可以到达，这样使我们有达到最优解的可能。
（2）渐进不依赖起点。
由于起点的选择有非常大的随机性，我们的目标是达到全局最优解，因此，应渐进地不依赖起点。
（3）分布稳定性。
包含两个内容：
一是当温度不大时，其马尔可夫链的极限分布存在；
二是当温度渐进0时，其马尔可夫链也存在极限分布。
（4）收敛到最优解。
当温度渐进0时，最优状态的极限分布和为1。
下面将从理论上讨论这些要求能否达到。
模拟退火算法可以分为齐次和非齐次的，由以上马氏链性质的讨论，收敛证明沿用下面的过程。
10.2.2齐次算法的收敛性
（1）在每一个温度t给出
（2）的一步转移概率的一些限定条件，使得转移概率所对应的马氏链满足不可约和非周期。
根据定理4.2,此马氏链在每一温度t存在平稳分布。
（2）给出平稳分布应该满足的条件，使得当温度渐进达到零度时，平稳分布的极限存在，即存在。
（3）进一步要求平稳分布的极限具有全局最优解的
其中表示最优状态集合。
综上所述，得到全局性收敛的表达式
对非齐次算法，也需要下面的条件保证其全局收敛性。
（1）因为非齐次算法的每一步温度在变化，因此需要给出一步转移概率的一些限定条件，即需要给出和的限定条件，使得非齐次马氏链能收敛到一个分布。
（2）温度是渐进到零度的，即，给出保证达到全局最优解的温度变化关系。
最终要求。
由于组合优化问题的状态空间是有限的，齐次性是由算法保证的。
要达到定理4.2的条件，需要讨论模拟退火算法对应的马氏链的不可约性与非周期性，即可先证明模拟退火算法对应的马氏链是不可约和非周期判定定理。
定理10.3若对于
使得
（5）
则与模拟退火算法相伴的马尔可夫链是不可约的。
证：
由（5）式可得
使
>
由不可约定义，知定理正确。
定理10.4若
则与模拟退火算法相伴的马尔可夫链为非周期的。
因为
由上式可得
引理得证。
定理10.5设P为有限齐次不可约、非周期马氏链的相伴矩阵，且其分量满足
（6）
则该马氏链的平稳分布是一给定分布q。
由定理4.2可知，要证明该马氏链的平稳分布存在且由
（1）式唯一确定。
故只需证明q满足
（1）式即可。
由（6）式，有
即
。
证毕。
由于在模拟退火算法中，P依赖于控制参数t，q也取决于t，故常表示成q=q（t）。
要达到定理4.2的条件，需要讨论模拟退火算法对应的马氏链的不可约性与非周期性即可，为了进一步确定平稳分布的形式，还需验证其是否满足（6）式。
（6）称为细节平衡方程，而
（1）称为整体平衡方程。
定理10.6设是组合优化问题的某个实例，P（t）表示由
（2）、（3）和（4）式定义的模拟退火算法相伴的转移矩阵。
又设产生矩阵G（t）满足（5）式，则与模拟退火算法相伴的马氏链具有平稳分布q（t），其分量为
其中
并且
（7）
特别地，当
成立时，有
（8）
证:
为了证明本定理，只需证明马氏链的不可约性与非周期性，并且满足（6）式的细节平衡方程即可。
先证不可约性。
由定理10.3直接得证。
再证非周期性。
设
由本定理满足（5）的条件，只要，这样的i,j，对一定存在。
对这样的i,j,对。
于是由定理4.4，该马氏链是非周期的。
由定理4.2可知，该马氏链存在唯一的平稳分布且由
（1）式确定。
由定理4.5，我们只需再证q（t）为随机的且满足（6）式的细节平衡方程即可。
q（t）显然是随机的，而
因此q（t）为该马氏链的平稳分布。
记为整体最优解集，。
则
此外，由（7）式和（8）式，可得
因而
这个结论反映了模拟退火算法的基本性质，即渐进不依赖起点与全局收敛性。
对于模拟退火算法中一般的产生概率和接受概率，只要满足某些条件必能保证算法的渐进收敛性，根据以上的引理和定理，不难得出下列的结论。
定理10.7:
设（S,f）表示组合优化问题的某个实例。
并设与模拟退火算法相伴的转移矩阵由式
（2）定义，产生概率和接受概率满足以下条件：
则模拟退火算法所对应的马氏链存在平稳分布q（t），其分量为
且
10.2.3非齐次算法的收敛性
非齐次算法一步转移概率的形式为：
其中，。
一步转移概率矩阵为：
多步转移概率表示时刻m在状态i，时刻k在状态j的转移概率。
齐次算法实际执行时是有限的，稍作修改，模拟退火算法执行的全过程可定义为一个非齐次马而可夫链，从而运用非齐次马而可夫过程的遍历理论导出更精确的收敛定理。
设是第l个齐次马而可夫链的控制参数，表示该马氏链的长度，表示第k次试验的控制参数，序列定义为
即控制参数取分段常数。
又序列满足以下条件：
于是，与试验次数k相对的非齐次马而可夫链由无限个长度有限的齐次马氏链拼接而成。
这些齐次马氏链的长度可以取得不同，甚至与控制参数相关。
此时，如何选取控制参数才能使该非齐次马氏链具有平稳分步呢？
定义10.8若非齐次马氏链满足下列条件，则称为弱遍历。
定义4.8说明，无论起点如何，当转移步数增加时，到达同一状态的概率渐进相同。
即马氏链的弱遍历性意味着马氏链的渐进收敛性与初始解无关。
这是一种失去记忆的功能。
定义10.9若存在向量q，满足
且有
则称非齐次马氏链为强遍历。
定义10.9的意义是马氏链的渐进稳定性，即具有强遍历性的马氏链可以收敛到一个随机分布。
下面给出非齐次马氏链为强遍历的一个充分条件。
定理10.8在温度t时，一步转移概率按
（2）定义，G（t）为
且存在,使得，其中，
则马氏链为强遍历，且该马氏链收敛到的随机分布为。
类似于定理10.6后半部分的证明，不难得出：
非齐次的模拟退火算法在上述的条件下，以概率1收敛到全局最优解。
另外，温度下降的最快速度为
10.3冷却进度表
10.3.1冷却进度表的概念
模拟退火算法的渐进收敛性意味着：
对于多数组合优问来说算法的执行过程只有进行无限多次变换后，才能返回一个整体最优解。
因而作为最优化算法，模拟退火算法的执行过程不能囿于多项式时间，而是一种指数时间算法，因而无法应用于实际。
冷却进度表是一组控制算法进程的参数，用于逼近模拟退火算法的渐进性态，使算法在执行多项式时间内返回一个近似最优解。
冷却进度表是影响模拟退火算法实验性能的重要因素，其合理选取是算法应用的关键。
模拟退火算法渐进收敛性的有限时间通常采用下述方法来实现：
用控制参数的一个递减有限序列以及与之对应链长的有限齐次马尔可夫链序列去控制算法进程。
为此必须确定一个确保算法收敛的参数集，这个参数集称为冷却进度表。
组成冷却进度表的参数集应当包括：
初始温度、降温策略、马尔可夫链长度以及停止准则四个方面。
构造冷却进度表的核心概念是准平衡，设是第k个马尔可夫链的长度，是相应的第k个控制参数。
称模拟退火算法达到准平衡，若在第k个马尔可夫链的次抽样后，解的概率分布充分逼近时的平稳分布。
亦即对某些确定的正数成立。
10.3.2冷却进度表的选择原则
任一有效的冷却进度表都必须妥善地解决两个问题。
首先是算法的收敛性问题。
根据热物理学平衡态统计理论与随机过程马尔可夫链理论，模拟退火算法在一定条件下是渐进收敛的。
但这并不意味着任一冷却进度表都能确保算法的收敛性，不合理的的冷却进度表会使算法在某些解之间“振荡”而不能收敛于最优解。
这个问题可以通过以及停止准则的合理解决加以实现，算法的收敛性显然取决于和的选择。
其次是模拟退火算法的实验性能问题。
算法的实验性能一般用两个指标——平均情况下最终解的质量和CPU运行时间——来衡量。
显然，模拟退火算法最终解的质量与运行时间成反向关系，很难两全其美。
这个结论的直观解释是：
准平衡量化标准越高，算法进程搜索的解空间范围越大，因而最终解的质量也越高，其时间花费理所当然也越多。
因此算法实验性能问题的妥善解决只有一种办法：
折中，即在合理的运算时间内尽量提高解的质量。
这种选择涉及冷却进度表所有参数的合理选择。
冷却进度表可以根据经验法则（基于上述的折中原则）或理论分析（基于准平衡概念）选取。
经验法则从合理的运行时间出发，探索提高最终解的质量的途径，简单直观而有赖丰富的实践；
理论分析由最终解的质量入手，寻求缩减运行时间的方法，精细透彻却难免繁琐的推证。
只有综合两者的优势才能构造出较好的冷却进度表。
下面就这两种方法作简单的介绍。
10.3.3经验法则（折中原则）
①初始温度的选取
基于“值只要充分大，就会立即达到准平衡”的论证，为使算法进程一开始就达到准平衡，应让初始接受率
由Metropolis准则,可推知值很大。
例如取，则在时>
949。
经验法则要求算法进程在合理时间里搜索尽可能大的解空间范围，只有足够大的值才能满足这个要求:
Kirkpatrick等在1982年提出的确定值的经验法则是：
选定一个大值作为的当前值并进行若干次变换，若接受率小于预定的初始接受率（Kirkpatrick等取），则当前值加倍。
以新的当前值重复上述过程，直至得到使的值。
这个经验法则被许多研究者进一步深化。
Johnson等建议通过计算若干次随机变换目标函数平均增量的方法来确定值提出由
求解，其中表示上述平均增量。
因此
综上所述，为使算法进程返回一个高质量最终解，必须满足选取“足够大”的值，而过大的又可能导致较长的运行时间，同时使模拟退火算法丧失可行性。
故要综合考虑两方面的因素。
②降温策略
降温策略主要解决温度的下降速度问题。
温度下降既不能太快也不能太慢。
太快会导致解的质量下降，类似于固体降温太快会出现的瑕疵，降温太慢会导致太长的运行时间，尤其对于问题规模较大时。
第一种方法是以ln（k）的速率下降，该方法优点是有可能使算法收敛到全局最优点，缺点是下降速率太慢而变的不实用。
第二种方法是根据费用函数的分布来自动确定的下降速率。
这种方法的优点是冷却进度仅由问题费用函数的统计量来确定，担这种方法的缺点也是不容忽视的，它假定了的分布是正态分布，这在实际应用中也不一定成立。
第三种是常系数法，即，其中在0.80和0.99之间，该方法形式简单，而且对只要求寻找近似最优解的问题也足够有效，因而成为目前最常用的一种方法。
③马尔可夫链长度
马尔可夫链长度的选择原则是：
在控制参数t的衰减函数已选定的前提下，应选得在控制参数的每一取值上都能恢复准平衡。
在控制参数的每一次取值的恢复准平衡需要进行的抽样次数可通过恢复准平衡至少接受的抽样次数来推算。
担由于抽样的接受概率随控制参数值的递减而减少，接受固定数量的变化需进行的抽样次数随之增多，最终在时，。
为此可用某些常量限定的值，以免在小值时产生过长的马尔可夫链。
表示算法进程在第k个马尔可夫链中进行的抽样次数，有限序列{}则规定了算法进程搜索的接空间范围。
由于多数组合优化问题的解空间规模随问题规模n呈指数增长，为使模拟退火算法最终解的质量有所保证，应建立与n间的某种关系。
指数型的关系是不切合实际的，因而通常取为问题规模n的一个多项式函数。
这样一个多项式函数可以依据组合优化问题实例的性质、规模以及处理这些问题的实践经验加以确定，或直接指定为n的一个多项式函数例如，或由领域结构间接确定例如（领域规模）
上面已提及，的选取与控制参数的衰减量密切相关，通常选取的小衰减量而避免过长的马尔可夫链。
大量的模拟实验也表明，过长的马尔可夫链无助于最终解质量的提高，而只会导致运行时间的无谓的增加，因此值只应选的“适当大”。
④停止准则
合理的停止准则既要保证算法的收敛性，又要是最终解具有一定的质量。
从最终解的质量考虑，若能用最终解目标函数的相对误差
（和分别是最终解和最优解的目标函数值）作为停止准则判据最理想的。
但组合优化问题的最优解往往未知或不可知的，这种理想往难以成真。
因此，只有另辟蹊径。
模拟退火算法的渐进收敛性给人们以新的启示：
算法收敛于最优解集是随控制参数t值缓缓减渐进的进行的。
只有在控制参数终值充分小”时，才有可能得出高质量的最终解。
故“充分小”在某种程度上可以替代“最终解质量”判据，为停止准则所用。
一是让控制参数的值小于某个充分小的正数，直接构成停止准则的判断式；
二是算法进程的接受率的控制参数递减而减小的性态，确定一个终止参数，若算法进程的当前接受率，就终止算法。
从最终解质量角度选取停止准则的另一条途径是：
以算法进程所得到的某些近似解为衡量标准，判断算法当前的质量是否持续得到明显的提高，从而确定是否终止算法。
譬如，在若干个相继的马尔可夫链中解无任何变化（含优化和恶化）就终止。
10.3.4理论分析法
上面讨论的冷却进度表基于准平衡概念的直观近似，称之为简单的冷却进度表。
对许多组合优化问题来说，采用简单的冷却进度表的模拟退火算法基本可以返回一个符合要求的近似最优解。
只要冷却进度表的选择合理，模拟退火算法的实验性能就会优于某些近似算法。
但是为了改进模拟退火算法对大规模组合优化问题的实验性能，他们提出了理论分析的方法，采用了一个更精细的冷却进度表。
所谓“精细”是指与准平衡量化联系的紧密程度。
准平衡概念的恰当量化是一项困难的任务，问题在于还没有掌握准确确定解的概率分布的充分的统计资料。
下面对精细的冷却进度表作一简介。
①初始温度
Aarts等人也提出了另一种计算式，他们的做法是：
假定对控制参数的某个确定值t产生一个m尝试的序列，并设和分别是其中目标函数减小和增大的变换数，是次目标函数增大的平均增量。
则接受率可用下式近似：
由上式可得:
只要将设定为初始接受率，就能求出相应的值。
需要指出的是Aarts等人的冷却进度表中的位置被初始接受率所取代。
②降温策略
Aarts等人首先把准平衡条件用
来替代.上式对某些正数成立，并假定准平衡在处达到且算法进程中始终保持。
则控制参数两个相邻值上的平稳分布相互逼近，且可量化为
上式对某些小正数成立（与准平衡式中的相关）。
然后证明了上式成立的一个充分条件
其中，再把上式改写成
最后经化简得
的衰减函数。
小的值导致控制参数t的小的衰减量，反之亦然。
在Aarts等人的冷却进度表中参数称为距离参数。
Aarts等人猜想由于上述控制参数的衰减函数导致控制参数两个相邻值上的平稳分布相互逼近，因此只要在值上达到准平衡，那么控制参数下一取值上的准平衡只须进行少量的抽样就可迅速逼近。
他们假设这个“少量抽样”可以指定为，算法能以一个充分大的概率至少访问给定解大部分领域所需进行抽样的次数。
然后，Aarts等人证明，对基数为的集合S进行N次重复抽样，S中不同元素被选中的概率在N和为大值时，可近似为
如果模拟退火算法对给定解i产生链长为L的马尔可夫链，并假设在马尔可夫链产生期间没有接受任一变换，则由上式可知，在马尔可夫链产生过程中解i的不同领域近似解被访问的概率是
其中是领域规模（）。
若取，则上述概率近似等于2/3。
对于三个相继的链长为的马尔可夫链，这个概率近似等于1，表明解i的整个领域几乎全被访问到。
于是，Aarts等人在其冷却进度表中，把选定为领域规模，即
④停止准
升级会员 