模拟退火算法

第十章模拟退火算法在管理科学、计算机科学、分子物理学、生物学、超大规模集成电路设计、代码设计、图像处理和电子工程等领域中，存在着大量的组合优化问题。例如，货郎担问题、最大截问题、0—1背包问题、图着色问题、设备布局问题以及布线问题等，这些问题至今仍未找到多项式时间算法。这些问题已被证明是NP完全问题。根据NP完全性理论，除非P=NP，否则所有的NP难问题都不存在多项式时间算法。但是，这并不意味着问题的终结。相反，由于这类问题广泛应用性，反而刺激人们以更大的热情对NP完全问题进行研究。为解决这类问题，人们提出了许多近似算法，但这些算法或过于注意个别问题的特征而缺乏通用性，或因所得解强烈地依赖初始解的选择而缺乏实用性。模拟退火算法是近年提出的一种适合解大规模组合优化问题，特别是解NP完全问题的通用有效的近似算法，它与以往的近似算法相比，具有描述简单、使用灵活、运用广泛、运行效率高和较少受初始条件限制的优点，而且特别适合并行计算，因此具有很大的使用价值。同时由于其讨论涉及随机分析、马尔可夫链理论、渐进收敛性等学科，所以其研究还具有重要的理论意义。10.1模拟退火算法的基本思想10.1.1模拟退火算法的物理背景固体退火过程的物理图像和统计性质是模拟退火算法的物理背景。在热力学与统计物理学的研究领域中，固体退火是其重要的研究对象。固体退火是指先将固体加热至熔化，再徐徐冷却使之凝固成规整晶体的热力学过程。在高温状态下，液体的分子彼此之间可以自由的移动。如果液体徐徐冷却，它的分子就会丧失由于温度而引起的流动性。这时原子就会自己排列起来而形成一种纯晶体，它们依次地朝各个方向几十亿倍于单个原子大小的距离，这个纯晶体状态就是该系统的最小能量状态。有趣的是，对于一个徐徐冷却的系统，当这些原子在逐渐失去活力的同时，它们自己就同时地排列而形成一个纯晶体，使这个系统的能量达到其最小值。这里我们特别强调在这个物理系统的冷却过程中，这些原子就“同时的”把它们自己排列成一个纯晶体的。如果一种金属熔液是被快速的冷却，则它不能达到纯晶体状态，而是变成一种多晶体或非晶体状态，系统处在这种状态时具有较高的能量。模拟退火算法就是模仿上述物理系统徐徐退火过程的一种通用随机搜索技术，人们可用马尔可夫链的遍历理论来给它以数学上的描述。在搜索最优解的过程中，模拟退火除了可以接受优化解外，还用一个随机接受准则（Metropolis准则）有限地接受恶化解，并使接受恶化解的概率慢慢地趋于零，这使得算法有可能从局部最优解中跳出，尽可能找到全局最优解，并保证了算法的收敛性。1982年Kirkpatrick等人首次把固体退火与组合极小化联系在一起，他们分别用目标函数和组合极小化问题的解替代物理系统的能量和状态，从而物理系统内粒子的摄动等价于组合极小化问题中解的试探。极小化过程就是：首先在一个高温（温度现在就成为一个参数控制）状态下有效的“溶化”解空间，然后慢慢地降低温度直到系统“晶体”到一个稳定解。通过以下示例，我们可以将组合优化问题与固体退火进行类比：组合优化问题固体退火解状态最优解能量最低状态费用函数能量10.1.2模拟退火算法结构模拟退火算法的求解过程如下：随机产生初始解，给定初始温度，令；随机产生新解，并计算函数增量；若，则接受新解，=，转(2)，否则以概率决定是否接受新解。具体方法是：产生0和1之间的一个随机数，若，接受新解，否则拒绝新解；重复第(2)、(3)步若干次，使解接近当前温度下的最优解，这相当于用足够慢的速度降温，以保证在每个温度时系统都能处于当前温度下的能量最低状态；按一定的方式降低温度，例如=，其中(0,1)；若满足收敛条件，退火过程结束，否则，转(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）式可得使>0由不可约定义，知定理正确。定理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等人在其冷却进度表中，把选定为领域规模，即④停止准则在温度t，定义平衡时目标函数的期望值为：Aarts等人对控制参数终值的选取基于期望目标函数在时的外推。设则当小于处的期望目标函数值时，就终止算法。而对于充分大的值，有而。因此对t《1，可近似为于是能够可靠地终止算法，若对某些成立，其中是某些小正数。Aarts等人把上式称为停止准则。10.4模拟退火算法的应用模拟退火算法具有广泛的应用性，可用于求解许多组合优化问题。根据模拟退火算法的过程（产生新解——计算目标函数差——判别是否接受新解——接受或舍弃新解），在算法的实际应用中必须解决好三个问题：第一，问题的数学描述；第二，新解的产生和接受机制；第三，冷却进度表的选取。其中第三个问题在上面已经讨论过了，此处不再赘述。此外，还必须有一个随机数产生器。问题的描述主要包括解空间和目标函数两部分。解空间为所有可行解（有时也包含不可行解）的集合它限定了初始解选取和新解产生的范围。对于无约束优化问题，任一可能解即为可行解；对于有约束优化问题，解集中还可以包含一些不可行解，同时在目标函数中加上惩函数，以惩罚出现的不可行解。新解的产生和接受可分为四个步骤：第一，给出新解的变换方法，得到一个产生装置，以从当前解产生一个新解；第二，计算新解和当前解的目标函数差，由于目标函数差仅由变换部分产生，因此，通常按增量计算目标函数差；第三，判断新解是否被接受，判断的依据是米特罗波利斯准则，对于有约束优化问题往往还伴随有新解可行性的判断；第四，接受或舍弃新解，若接受，用新解代替当前解，同时修正目标函数值，否则当前解与目标函数值保持不变。下面仅对几个典型的组合优化问题给出实现的算法描述，以揭示其建立数学模型和新解产生装置的基本方法。10.4.1旅行商问题（TSP）设有n个城市和距离矩阵D=[]，其中表示城市i到城市j的距离，i,j=1,…，n，寻找遍访每个城市恰好一次的一条回路，且其路径长度为最短。求解的模拟退火算法描述如下：①解空间解空间S可表为{1,2，…，n}的所有循环排列的集合，即S={(,…,)|(,…,)为(1,2，…，n)的循环排列}，其中每一循环排列表示遍访n个城市的一条回路，=j表示在第i个次序访问城市j，并约定=。初始解可选为（1,2，…，n）。②目标函数此时的目标函数即为访问所有城市的路径长度或称为代价函数，须求其最小值，选为f(,…,)=其中=。③新解的产生（2变换法）任选访问的序号u和v,逆转u和v及其之间的访问顺序，此时新路径为（设u<v）……④代价函数差伴随新解的代价函数差可由公式f=(+)-(++)计算。特别地，当问题为对称的，即距离矩阵D=[]为对称矩阵时，因为,上式可简化为10.4.20-1背包问题（ZKP）给定一个可装重量M的背包n件物品，物品i的重量和价值分别为和,i=1,,n。要选若干件物品装人背包，使其价值之和最大。求解的模拟退火算法描述如下：①解空间ZKP是一个有约束的优化问题。为此，我们限定解空间为所有可行解的集合，即S={()|}其中表示物品i被选择装入背包。初始解选为(0,…,0)。②目标函数为一需求最大值的代价函数但必须满足约束，i=1,…,n.③新解的产生随机选取物品i。若i不在背包中，则将其直接装入背包，或同时从背包中随机取出另一件物品j。若i已在背包中，则将其取出，同时随机装入另一件物品j。即④背包价值差及重量差根据产生新解的三种可能，伴随的背包代价差为为判定解的可行性，还需要求出对应的背包重量差为其中为当前背包重量m的增重⑤接受准则是扩充了可行性测定的马尔可夫链准则其中和分别由四中的两式计算。10.4.3最大截问题（MCP）给定带权图G={V,E}，其中为顶点集合，E为边集，权矩阵为。要将V划分为子集和，使E中所有顶点分属和的权之和最大。①解空间可表为V的所有划分为两子集和分划的集合，即其中分划表示顶点。初始解选为。②目标函数直接取为分划所得得到的截量的相反数需求其最小值。即相应截量的最大值。③新解的产生任选顶点，将其从目前所在的子集移到另一个子集中去，即:。④目标函数差根据目标函数和产生新解的方法可知，相应于目标函数差为10.4.4独立集问题（ISP）设有图G=（V，E），为顶点集。要找V的最大独立集，即找最大的，满足时必有。模拟退火算法的求解形式为：①解空间取V的幂集，即V的所有子集的集合注意到解空间S中可能含有不可行解，即可能存在V的子集,但并非独立集，初始解为。如此构造解空间可以使得产生新解的方法简便，同时使算法可以从一个局部最优的可行解变换为稍差的不可行解，以增大“逃离”局部最优“陷阱”的概率。当然，这会使目标函数的构造变的复杂一些。②目标函数为“惩罚”可能出现的不可行解，将目标函数选为其中表示点集的元素个数，表示边集的元素个数。是一个大于1的惩罚因子，用于“惩罚”在中存在的边。注意到时，恰好是独立集的元素个数。③新解的产生通过任选顶点，当时将其移出，而时则将其移入来产生，即其中为集特征函数，定义为：④目标函数差设表示图G的邻接矩阵，表示顶点与邻接，即，且。则伴随新解的目标函数差为即10.4.5调度问题（SCP）有n个相互独立的任务，所需时间分别为，均可由m台机器中的一台完成，且每台机器一次仅可完成一项任务，要找一个最小调度，即找对n个任务的一个调度，使完成所有任务的时间最短。求解的模拟退火算法为①解空间一个调度可看成对正数集的一个分划因此解空间可由所有可能的分划组成，即初始解可选为。②目标函数SCP是要使分划的诛子集中的各正数的和的最大值为最小，即需求的最小值，易证其最小值对应于的最小值。所以划分的目标函数可定义为但此时求出的最小值并非所得调度的实际需要时间。③新解的产生任选，将其移到任选的另一个子集中去，即它对应于将所需时间为t的任务从机器调到机器上去完成。④目标函数差由目标函数可得，伴随于新解的目标函数差为⑤停止准则的扩充与前述问题不同，SCP的目标函数有一个确定且有时可以达到的下界它对应于所有台机器所需时间均为的情况，即的最小值。此时的调度必为一个最小调度。因此可在停止准则中加一个形如iff=then停止算法运行的判断。10.4.6图着色问题（GCP）给定图G=(G,V),为顶点集，E为边集。要找G的一个最小着色，即找一个最小的正整数k和映射，使得，当时有。为了用模拟退火算法求解，首先注意到，若图G的顶点个数为n，则图G的最小着色的上界为n。此外，GCP也是一个有约束的优化问题，我们同样使用惩函数将其转化为无约束问题。①解空间记将顶点集V划分为n个子集的任一分划为则解空间的表为注意到可能存在，且有些分划可能并非可行解。初始解就选为。②目标函数选为其中表示分划中非空集合的个数。为惩函数因子。显然的最小值即为最小着色的颜色数。③新解的产生任选顶点，将其从当前所在子集移到任选的另一个子集中去。即但限定时。④目标函数差仍设为G的邻接矩阵，则相应于新解的目标函数差为其中sgn（x）定义为10.4.7关于模拟退火算法应用的说明上面给出了6个典型的组合优化问题的模拟退火算法描述。为了更好的应用模拟退火算法,需要作以下几点说明:(1)上面6个问题都是所谓的NP完全问题，根据的著名猜测，它们均不存在可行的精确算法。因此，对这类问题寻找高效可行的近似算法有着重要的实际意义和理论价值，模拟退火算法就是这样的近似算法之一。(2)目前人们已发现千余个NP完全问题，这些NP完全问题中有许多可以用模拟退火算法求解，以上给出的仅仅是其中很小的一个子集。(3)上述算法只是说明模拟退火算法应用的基本方法,如解空间的构造、目标函数的定义、新解的产生方法、目标函数差的计算以及接受准则的应用等，其描述较为粗略，在实际应用时还需作一些技术上的处理。(4)以上这些算法具有一定的典型性，有些可以推广使用。如调度问题(SCP)的算法可以直接求解划分问题(PAP)；0-1背包问题(ZKP)的算法可略加修改后用于解一般的整数背包问题、多约束的0-1背包问题、最小化的0-1规划问题乃至于一般的整数规划问题。再如鉴于图的独立集和覆盖集的互补性，可根据解独立集问题(ISP)的算法求出的最大独立集直接得到最小覆