模擬退火算法

第十章模擬退火算法在管理科學、計算機科學、分子物理學、生物學、超大規(guī)模集成電路設(shè)計、代碼設(shè)計、圖像處理和電子工程等領(lǐng)域中，存在著大量的組合優(yōu)化問題。例如，貨郎擔問題、最大截問題、0—1背包問題、圖著色問題、設(shè)備布局問題以及布線問題等，這些問題至今仍未找到多項式時間算法。這些問題已被證明是NP完全問題。根據(jù)NP完全性理論，除非P=NP，否那么所有的NP難問題都不存在多項式時間算法。但是，這并不意味著問題的終結(jié)。相反，由于這類問題廣泛應(yīng)用性，反而刺激人們以更大的熱情對NP完全問題進行研究。為解決這類問題，人們提出了許多近似算法，但這些算法或過于注意個別問題的特征而缺乏通用性，或因所得解強烈地依賴初始解的選擇而缺乏實用性。模擬退火算法是近年提出的一種適合解大規(guī)模組合優(yōu)化問題，特別是解NP完全問題的通用有效的近似算法，它與以往的近似算法相比，具有描述簡單、使用靈活、運用廣泛、運行效率高和較少受初始條件限制的優(yōu)點，而且特別適合并行計算，因此具有很大的使用價值。同時由于其討論涉及隨機分析、馬爾可夫鏈理論、漸進收斂性等學科，所以其研究還具有重要的理論意義。10.1模擬退火算法的根本思想10.1.1模擬退火算法的物理背景固體退火過程的物理圖像和統(tǒng)計性質(zhì)是模擬退火算法的物理背景。在熱力學與統(tǒng)計物理學的研究領(lǐng)域中，固體退火是其重要的研究對象。固體退火是指先將固體加熱至熔化，再徐徐冷卻使之凝固成規(guī)整晶體的熱力學過程。在高溫狀態(tài)下，液體的分子彼此之間可以自由的移動。如果液體徐徐冷卻，它的分子就會喪失由于溫度而引起的流動性。這時原子就會自己排列起來而形成一種純晶體，它們依次地朝各個方向幾十億倍于單個原子大小的距離，這個純晶體狀態(tài)就是該系統(tǒng)的最小能量狀態(tài)。有趣的是，對于一個徐徐冷卻的系統(tǒng)，當這些原子在逐漸失去活力的同時，它們自己就同時地排列而形成一個純晶體，使這個系統(tǒng)的能量到達其最小值。這里我們特別強調(diào)在這個物理系統(tǒng)的冷卻過程中，這些原子就“同時的”把它們自己排列成一個純晶體的。如果一種金屬熔液是被快速的冷卻，那么它不能到達純晶體狀態(tài)，而是變成一種多晶體或非晶體狀態(tài)，系統(tǒng)處在這種狀態(tài)時具有較高的能量。模擬退火算法就是模仿上述物理系統(tǒng)徐徐退火過程的一種通用隨機搜索技術(shù)，人們可用馬爾可夫鏈的遍歷理論來給它以數(shù)學上的描述。在搜索最優(yōu)解的過程中，模擬退火除了可以接受優(yōu)化解外，還用一個隨機接受準那么〔Metropolis準那么〕有限地接受惡化解，并使接受惡化解的概率慢慢地趨于零，這使得算法有可能從局部最優(yōu)解中跳出，盡可能找到全局最優(yōu)解，并保證了算法的收斂性。1982年Kirkpatrick等人首次把固體退火與組合極小化聯(lián)系在一起，他們分別用目標函數(shù)和組合極小化問題的解替代物理系統(tǒng)的能量和狀態(tài)，從而物理系統(tǒng)內(nèi)粒子的攝動等價于組合極小化問題中解的試探。極小化過程就是：首先在一個高溫〔溫度現(xiàn)在就成為一個參數(shù)控制〕狀態(tài)下有效的“溶化”解空間，然后慢慢地降低溫度直到系統(tǒng)“晶體”到一個穩(wěn)定解。通過以下例如，我們可以將組合優(yōu)化問題與固體退火進行類比：組合優(yōu)化問題固體退火解狀態(tài)最優(yōu)解能量最低狀態(tài)費用函數(shù)能量10.1.2模擬退火算法結(jié)構(gòu)模擬退火算法的求解過程如下：隨機產(chǎn)生初始解，給定初始溫度，令；隨機產(chǎn)生新解，并計算函數(shù)增量；假設(shè)，那么接受新解，=，轉(zhuǎn)(2)，否那么以概率決定是否接受新解。具體方法是：產(chǎn)生0和1之間的一個隨機數(shù)，假設(shè)，接受新解，否那么拒絕新解；重復第(2)、(3)步假設(shè)干次，使解接近當前溫度下的最優(yōu)解，這相當于用足夠慢的速度降溫，以保證在每個溫度時系統(tǒng)都能處于當前溫度下的能量最低狀態(tài)；按一定的方式降低溫度，例如=，其中(0,1)；假設(shè)滿足收斂條件，退火過程結(jié)束，否那么，轉(zhuǎn)(2)。通常，收斂條件為。理論已證明：只要初始溫度足夠高，退火過程足夠慢，模擬退火算法以概率1收斂到全局最優(yōu)解。10.2模擬退火算法的漸近收斂性馬爾可夫鏈理論定義10.1設(shè)為隨機變量序列，稱在時刻k處于狀態(tài)i，，S稱為狀態(tài)空間。當S中的狀態(tài)數(shù)有限時，稱為有限狀態(tài)空間。假設(shè)對任意的正整數(shù)n,滿足那么稱{X(k)}(k=1,2,…)為馬爾可夫鏈，簡稱馬氏鏈。馬氏鏈具有一種記憶功能，它只記憶前一時刻的狀態(tài)。上式可以簡單地記成稱為一步轉(zhuǎn)移概率。當狀態(tài)空間有限時，稱為有限馬氏鏈，一步轉(zhuǎn)移概率矩陣記為當成立時，即從狀態(tài)i移到狀態(tài)j的概率與時刻n無關(guān)，稱馬氏鏈為齊次馬氏鏈。反之，假設(shè)轉(zhuǎn)移矩陣與時刻有關(guān)，那么稱此馬氏鏈為非齊次馬氏鏈。切普曼—柯爾莫哥洛夫方程式：其中表示m步轉(zhuǎn)移概率，即在時刻n狀態(tài)為i的條件下，經(jīng)過m步轉(zhuǎn)移到達狀態(tài)j的概率。特別當馬爾可夫過程為齊次時切普曼—柯爾莫哥洛夫方程變成定義10.2如果對狀態(tài)i和j存在某個,使得，既由狀態(tài)i出發(fā)，經(jīng)過n次轉(zhuǎn)移以正的概率到達狀態(tài)j,那么稱自狀態(tài)i可到達狀態(tài)j,并記為。反之假設(shè)狀態(tài)i不能到達j，即對于一切,。定義10.3假設(shè)且，那么稱狀態(tài)i和j相通，記為定義10.4設(shè)C為狀態(tài)空間的一個子集，如果從C內(nèi)任一狀態(tài)i不能到達C外的任何狀態(tài)j，即對那么稱C是閉集。定義10.5稱轉(zhuǎn)移矩陣為P的馬爾可夫鏈為不可約的，假設(shè)，即除了整個狀態(tài)空間構(gòu)成一個閉集外沒有別的閉集，這時馬氏鏈中的所有狀態(tài)都是相通的。定義10.6稱轉(zhuǎn)移矩陣為p的馬爾可夫鏈為非周期的，假設(shè)對，集合的最大公約數(shù)為，其中由所有滿足式的整數(shù)n>0組成，且整數(shù)稱為解i的周期。故非周期即指出所有解的周期為1。定理10.1轉(zhuǎn)移矩陣為P的不可約馬氏鏈是非周期的一個充分條件是：證明:由不可約性可知，對滿足上式的j和有且故其中n=k+l，又由于因而n,n+1均屬于，故由于，故結(jié)論正確。在討論模擬退火算法收斂性的過程中用到的一個重要的分布是平穩(wěn)分布。定義10.7稱轉(zhuǎn)移矩陣為P的有限齊次馬爾可夫鏈的平穩(wěn)分布為向量q，其第i個分量為，其中且。假設(shè)這樣的平穩(wěn)分布q存在，那么該平穩(wěn)分布就是時解的概率分布。作者不加證明的給出以下重要定理：定理10.2：設(shè)P為有限齊次馬爾可夫鏈的相伴轉(zhuǎn)移矩陣，假設(shè)該馬氏鏈是不可約的和非周期的，那么其平穩(wěn)分布q存在且由下式唯一確定：(1)其中。根據(jù)模擬退火算法的特點，模擬退火算法的數(shù)學模型可以描述為：在給定鄰域結(jié)構(gòu)后，模擬退火過程是從一個狀態(tài)到另一個狀態(tài)不斷的隨機游動。我們可以用馬爾可夫鏈描述這一過程。當溫度t為一確定值時，兩個狀態(tài)的轉(zhuǎn)移概率定義為(2)其中，表示狀態(tài)集合(解集合)中狀態(tài)的個數(shù)。稱為從i到j(luò)的產(chǎn)生概率。表示在狀態(tài)i時，j狀態(tài)被選取的概率。比擬容易理解的是j是i的鄰域，如果在鄰域中等概率選取，那么j被選取的概率是(3)稱為接受概率，表示在狀態(tài)i時產(chǎn)生狀態(tài)j后，接受j的概率，如在模擬退火算法中接受概率是:(4),和分別稱為產(chǎn)生矩陣、接受矩陣和一步轉(zhuǎn)移概率矩陣。上述為模擬退火算法的主要模型。模擬退火算法主要分為兩類。第一類為齊次算法，在(1)中對每一個固定的t，計算對應(yīng)的馬爾可夫鏈變化，直到一個穩(wěn)定狀態(tài)，然后在使溫度下降。第二類是非齊次算法，由一個馬爾可夫鏈組成，要求在兩個相鄰的轉(zhuǎn)移中，溫度t是下降的。無論從實際和直觀，描述模擬退火過程的馬爾可夫鏈應(yīng)滿足以下條件:(1)可達性。無論起點如何，任何一個狀態(tài)都可以到達，這樣使我們有到達最優(yōu)解的可能。(2)漸進不依賴起點。由于起點的選擇有非常大的隨機性，我們的目標是到達全局最優(yōu)解，因此，應(yīng)漸進地不依賴起點。(3)分布穩(wěn)定性。包含兩個內(nèi)容：一是當溫度不大時，其馬爾可夫鏈的極限分布存在；二是當溫度漸進0時，其馬爾可夫鏈也存在極限分布。(4)收斂到最優(yōu)解。當溫度漸進0時，最優(yōu)狀態(tài)的極限分布和為1。下面將從理論上討論這些要求能否到達。模擬退火算法可以分為齊次和非齊次的，由以上馬氏鏈性質(zhì)的討論，收斂證明沿用下面的過程。齊次算法的收斂性(1)在每一個溫度t給出(2)的一步轉(zhuǎn)移概率的一些限定條件，使得轉(zhuǎn)移概率所對應(yīng)的馬氏鏈滿足不可約和非周期。根據(jù)定理4.2,此馬氏鏈在每一溫度t存在平穩(wěn)分布。(2)給出平穩(wěn)分布應(yīng)該滿足的條件，使得當溫度漸進到達零度時，平穩(wěn)分布的極限存在，即存在。(3)進一步要求平穩(wěn)分布的極限具有全局最優(yōu)解的其中表示最優(yōu)狀態(tài)集合。綜上所述，得到全局性收斂的表達式對非齊次算法，也需要下面的條件保證其全局收斂性。(1)因為非齊次算法的每一步溫度在變化，因此需要給出一步轉(zhuǎn)移概率的一些限定條件，即需要給出和的限定條件，使得非齊次馬氏鏈能收斂到一個分布。(2)溫度是漸進到零度的，即，給出保證到達全局最優(yōu)解的溫度變化關(guān)系。最終要求。由于組合優(yōu)化問題的狀態(tài)空間是有限的，齊次性是由算法保證的。要到達定理4.2的條件，需要討論模擬退火算法對應(yīng)的馬氏鏈的不可約性與非周期性，即可先證明模擬退火算法對應(yīng)的馬氏鏈是不可約和非周期判定定理。定理10.3假設(shè)對于使得(5)那么與模擬退火算法相伴的馬爾可夫鏈是不可約的。證：由〔5〕式可得使>0由不可約定義，知定理正確。定理10.4假設(shè)那么與模擬退火算法相伴的馬爾可夫鏈為非周期的。證：因為由上式可得引理得證。定理10.5設(shè)P為有限齊次不可約、非周期馬氏鏈的相伴矩陣，且其分量滿足(6)那么該馬氏鏈的平穩(wěn)分布是一給定分布q。證：由定理4.2可知，要證明該馬氏鏈的平穩(wěn)分布存在且由(1)式唯一確定。故只需證明q滿足(1)式即可。由(6)式，有即。證畢。由于在模擬退火算法中，P依賴于控制參數(shù)t，q也取決于t，故常表示成q=q(t)。由于組合優(yōu)化問題的狀態(tài)空間是有限的，齊次性是由算法保證的。要到達定理4.2的條件，需要討論模擬退火算法對應(yīng)的馬氏鏈的不可約性與非周期性即可，為了進一步確定平穩(wěn)分布的形式，還需驗證其是否滿足(6)式。(6)稱為細節(jié)平衡方程，而(1)稱為整體平衡方程。定理10.6設(shè)是組合優(yōu)化問題的某個實例，P(t)表示由(2)、(3)和(4)式定義的模擬退火算法相伴的轉(zhuǎn)移矩陣。又設(shè)產(chǎn)生矩陣G(t)滿足(5)式，那么與模擬退火算法相伴的馬氏鏈具有平穩(wěn)分布q(t)，其分量為其中并且(7)特別地，當成立時，有(8)證:為了證明本定理，只需證明馬氏鏈的不可約性與非周期性，并且滿足〔6〕式的細節(jié)平衡方程即可。先證不可約性。由定理10.3直接得證。再證非周期性。設(shè)由本定理滿足〔5〕的條件，只要，這樣的i,j，對一定存在。對這樣的i,j,對。于是由定理4.4，該馬氏鏈是非周期的。由定理4.2可知，該馬氏鏈存在唯一的平穩(wěn)分布且由(1)式確定。由定理4.5，我們只需再證q(t)為隨機的且滿足〔6〕式的細節(jié)平衡方程即可。q(t)顯然是隨機的，而因此q(t)為該馬氏鏈的平穩(wěn)分布。記為整體最優(yōu)解集，。那么特別地，當成立時，有證畢。此外，由〔7〕式和〔8〕式，可得因而這個結(jié)論反映了模擬退火算法的根本性質(zhì)，即漸進不依賴起點與全局收斂性。對于模擬退火算法中一般的產(chǎn)生概率和接受概率，只要滿足某些條件必能保證算法的漸進收斂性，根據(jù)以上的引理和定理，不難得出以下的結(jié)論。定理10.7:設(shè)(S,f)表示組合優(yōu)化問題的某個實例。并設(shè)與模擬退火算法相伴的轉(zhuǎn)移矩陣由式(2)定義，產(chǎn)生概率和接受概率滿足以下條件：那么模擬退火算法所對應(yīng)的馬氏鏈存在平穩(wěn)分布q(t)，其分量為且10.2.3非齊次算法的收斂性非齊次算法一步轉(zhuǎn)移概率的形式為：其中，。一步轉(zhuǎn)移概率矩陣為：多步轉(zhuǎn)移概率表示時刻m在狀態(tài)i，時刻k在狀態(tài)j的轉(zhuǎn)移概率。齊次算法實際執(zhí)行時是有限的，稍作修改，模擬退火算法執(zhí)行的全過程可定義為一個非齊次馬而可夫鏈，從而運用非齊次馬而可夫過程的遍歷理論導出更精確的收斂定理。設(shè)是第l個齊次馬而可夫鏈的控制參數(shù)，表示該馬氏鏈的長度，表示第k次試驗的控制參數(shù)，序列定義為即控制參數(shù)取分段常數(shù)。又序列滿足以下條件：于是，與試驗次數(shù)k相對的非齊次馬而可夫鏈由無限個長度有限的齊次馬氏鏈拼接而成。這些齊次馬氏鏈的長度可以取得不同，甚至與控制參數(shù)相關(guān)。此時，如何選取控制參數(shù)才能使該非齊次馬氏鏈具有平穩(wěn)分步呢？定義10.8假設(shè)非齊次馬氏鏈滿足以下條件，那么稱為弱遍歷。定義4.8說明，無論起點如何，當轉(zhuǎn)移步數(shù)增加時，到達同一狀態(tài)的概率漸進相同。即馬氏鏈的弱遍歷性意味著馬氏鏈的漸進收斂性與初始解無關(guān)。這是一種失去記憶的功能。定義10.9假設(shè)存在向量q，滿足且有那么稱非齊次馬氏鏈為強遍歷。定義10.9的意義是馬氏鏈的漸進穩(wěn)定性，即具有強遍歷性的馬氏鏈可以收斂到一個隨機分布。下面給出非齊次馬氏鏈為強遍歷的一個充分條件。定理10.8在溫度t時，一步轉(zhuǎn)移概率按(2)定義，G(t)為且存在,使得，其中，那么馬氏鏈為強遍歷，且該馬氏鏈收斂到的隨機分布為。其中。類似于定理10.6后半局部的證明，不難得出：非齊次的模擬退火算法在上述的條件下，以概率1收斂到全局最優(yōu)解。即另外，溫度下降的最快速度為10.3冷卻進度表10.3.1冷卻進度表的概念模擬退火算法的漸進收斂性意味著：對于多數(shù)組合優(yōu)問來說算法的執(zhí)行過程只有進行無限屢次變換后，才能返回一個整體最優(yōu)解。因而作為最優(yōu)化算法，模擬退火算法的執(zhí)行過程不能囿于多項式時間，而是一種指數(shù)時間算法，因而無法應(yīng)用于實際。冷卻進度表是一組控制算法進程的參數(shù)，用于逼近模擬退火算法的漸進性態(tài)，使算法在執(zhí)行多項式時間內(nèi)返回一個近似最優(yōu)解。冷卻進度表是影響模擬退火算法實驗性能的重要因素，其合理選取是算法應(yīng)用的關(guān)鍵。模擬退火算法漸進收斂性的有限時間通常采用下述方法來實現(xiàn)：用控制參數(shù)的一個遞減有限序列以及與之對應(yīng)鏈長的有限齊次馬爾可夫鏈序列去控制算法進程。為此必須確定一個確保算法收斂的參數(shù)集，這個參數(shù)集稱為冷卻進度表。組成冷卻進度表的參數(shù)集應(yīng)當包括：初始溫度、降溫策略、馬爾可夫鏈長度以及停止準那么四個方面。構(gòu)造冷卻進度表的核心概念是準平衡，設(shè)是第k個馬爾可夫鏈的長度，是相應(yīng)的第k個控制參數(shù)。稱模擬退火算法到達準平衡，假設(shè)在第k個馬爾可夫鏈的次抽樣后，解的概率分布充分逼近時的平穩(wěn)分布。亦即對某些確定的正數(shù)成立。10.3.2冷卻進度表的選擇原那么任一有效的冷卻進度表都必須妥善地解決兩個問題。首先是算法的收斂性問題。根據(jù)熱物理學平衡態(tài)統(tǒng)計理論與隨機過程馬爾可夫鏈理論，模擬退火算法在一定條件下是漸進收斂的。但這并不意味著任一冷卻進度表都能確保算法的收斂性，不合理的的冷卻進度表會使算法在某些解之間“振蕩”而不能收斂于最優(yōu)解。這個問題可以通過以及停止準那么的合理解決加以實現(xiàn)，算法的收斂性顯然取決于和的選擇。其次是模擬退火算法的實驗性能問題。算法的實驗性能一般用兩個指標——平均情況下最終解的質(zhì)量和CPU運行時間——來衡量。顯然，模擬退火算法最終解的質(zhì)量與運行時間成反向關(guān)系，很難兩全其美。這個結(jié)論的直觀解釋是：準平衡量化標準越高，算法進程搜索的解空間范圍越大，因而最終解的質(zhì)量也越高，其時間花費理所當然也越多。因此算法實驗性能問題的妥善解決只有一種方法：折中，即在合理的運算時間內(nèi)盡量提高解的質(zhì)量。這種選擇涉及冷卻進度表所有參數(shù)的合理選擇。冷卻進度表可以根據(jù)經(jīng)驗法那么〔基于上述的折中原那么〕或理論分析〔基于準平衡概念〕選取。經(jīng)驗法那么從合理的運行時間出發(fā)，探索提高最終解的質(zhì)量的途徑，簡單直觀而有賴豐富的實踐；理論分析由最終解的質(zhì)量入手，尋求縮減運行時間的方法，精細透徹卻難免繁瑣的推證。只有綜合兩者的優(yōu)勢才能構(gòu)造出較好的冷卻進度表。下面就這兩種方法作簡單的介紹。10.3.3經(jīng)驗法那么〔折中原那么〕①初始溫度的選取基于“值只要充分大，就會立即到達準平衡”的論證，為使算法進程一開始就到達準平衡，應(yīng)讓初始接受率由Metropolis準那么,可推知值很大。例如取，那么在時>949。經(jīng)驗法那么要求算法進程在合理時間里搜索盡可能大的解空間范圍，只有足夠大的值才能滿足這個要求:Kirkpatrick等在1982年提出確實定值的經(jīng)驗法那么是：選定一個大值作為的當前值并進行假設(shè)干次變換，假設(shè)接受率小于預(yù)定的初始接受率(Kirkpatrick等取)，那么當前值加倍。以新的當前值重復上述過程，直至得到使的值。這個經(jīng)驗法那么被許多研究者進一步深化。Johnson等建議通過計算假設(shè)干次隨機變換目標函數(shù)平均增量的方法來確定值提出由求解，其中表示上述平均增量。因此綜上所述，為使算法進程返回一個高質(zhì)量最終解，必須滿足選取“足夠大”的值，而過大的又可能導致較長的運行時間，同時使模擬退火算法喪失可行性。故要綜合考慮兩方面的因素。②降溫策略降溫策略主要解決溫度的下降速度問題。溫度下降既不能太快也不能太慢。太快會導致解的質(zhì)量下降，類似于固體降溫太快會出現(xiàn)的瑕疵，降溫太慢會導致太長的運行時間，尤其對于問題規(guī)模較大時。第一種方法是以ln(k)的速率下降，該方法優(yōu)點是有可能使算法收斂到全局最優(yōu)點，缺點是下降速率太慢而變的不實用。第二種方法是根據(jù)費用函數(shù)的分布來自動確定的下降速率。這種方法的優(yōu)點是冷卻進度僅由問題費用函數(shù)的統(tǒng)計量來確定，擔這種方法的缺點也是不容無視的，它假定了的分布是正態(tài)分布，這在實際應(yīng)用中也不一定成立。第三種是常系數(shù)法，即，其中在0.80和0.99之間，該方法形式簡單，而且對只要求尋找近似最優(yōu)解的問題也足夠有效，因而成為目前最常用的一種方法。③馬爾可夫鏈長度馬爾可夫鏈長度的選擇原那么是：在控制參數(shù)t的衰減函數(shù)已選定的前提下，應(yīng)選得在控制參數(shù)的每一取值上都能恢復準平衡。在控制參數(shù)的每一次取值的恢復準平衡需要進行的抽樣次數(shù)可通過恢復準平衡至少接受的抽樣次數(shù)來推算。擔由于抽樣的接受概率隨控制參數(shù)值的遞減而減少，接受固定數(shù)量的變化需進行的抽樣次數(shù)隨之增多，最終在時，。為此可用某些常量限定的值，以免在小值時產(chǎn)生過長的馬爾可夫鏈。表示算法進程在第k個馬爾可夫鏈中進行的抽樣次數(shù)，有限序列{}那么規(guī)定了算法進程搜索的接空間范圍。由于多數(shù)組合優(yōu)化問題的解空間規(guī)模隨問題規(guī)模n呈指數(shù)增長，為使模擬退火算法最終解的質(zhì)量有所保證，應(yīng)建立與n間的某種關(guān)系。指數(shù)型的關(guān)系是不切合實際的，因而通常取為問題規(guī)模n的一個多項式函數(shù)。這樣一個多項式函數(shù)可以依據(jù)組合優(yōu)化問題實例的性質(zhì)、規(guī)模以及處理這些問題的實踐經(jīng)驗加以確定，或直接指定為n的一個多項式函數(shù)例如，或由領(lǐng)域結(jié)構(gòu)間接確定例如(領(lǐng)域規(guī)模)上面已提及，的選取與控制參數(shù)的衰減量密切相關(guān)，通常選取的小衰減量而防止過長的馬爾可夫鏈。大量的模擬實驗也說明，過長的馬爾可夫鏈無助于最終解質(zhì)量的提高，而只會導致運行時間的無謂的增加，因此值只應(yīng)選的“適當大”。④停止準那么合理的停止準那么既要保證算法的收斂性，又要是最終解具有一定的質(zhì)量。從最終解的質(zhì)量考慮，假設(shè)能用最終解目標函數(shù)的相對誤差〔和分別是最終解和最優(yōu)解的目標函數(shù)值〕作為停止準那么判據(jù)最理想的。但組合優(yōu)化問題的最優(yōu)解往往未知或不可知的，這種理想往難以成真。因此，只有另辟蹊徑。模擬退火算法的漸進收斂性給人們以新的啟示：算法收斂于最優(yōu)解集是隨控制參數(shù)t值緩緩減漸進的進行的。只有在控制參數(shù)終值充分小”時，才有可能得出高質(zhì)量的最終解。故“充分小”在某種程度上可以替代“最終解質(zhì)量”判據(jù)，為停止準那么所用。一是讓控制參數(shù)的值小于某個充分小的正數(shù)，直接構(gòu)成停止準那么的判斷式；二是算法進程的接受率的控制參數(shù)遞減而減小的性態(tài)，確定一個終止參數(shù)，假設(shè)算法進程的當前接受率，就終止算法。從最終解質(zhì)量角度選取停止準那么的另一條途徑是：以算法進程所得到的某些近似解為衡量標準，判斷算法當前的質(zhì)量是否持續(xù)得到明顯的提高，從而確定是否終止算法。譬如，在假設(shè)干個相繼的馬爾可夫鏈中解無任何變化〔含優(yōu)化和惡化〕就終止。10.3.4理論分析法上面討論的冷卻進度表基于準平衡概念的直觀近似，稱之為簡單的冷卻進度表。對許多組合優(yōu)化問題來說，采用簡單的冷卻進度表的模擬退火算法根本可以返回一個符合要求的近似最優(yōu)解。只要冷卻進度表的選擇合理，模擬退火算法的實驗性能就會優(yōu)于某些近似算法。但是為了改良模擬退火算法對大規(guī)模組合優(yōu)化問題的實驗性能，他們提出了理論分析的方法，采用了一個更精細的冷卻進度表。所謂“精細”是指與準平衡量化聯(lián)系的緊密程度。準平衡概念的恰當量化是一項困難的任務(wù)，問題在于還沒有掌握準確確定解的概率分布的充分的統(tǒng)計資料。下面對精細的冷卻進度表作一簡介。①初始溫度Aarts等人也提出了另一種計算式，他們的做法是：假定對控制參數(shù)的某個確定值t產(chǎn)生一個m嘗試的序列，并設(shè)和分別是其中目標函數(shù)減小和增大的變換數(shù)，是次目標函數(shù)增大的平均增量。那么接受率可用下式近似：由上式可得:只要將設(shè)定為初始接受率，就能求出相應(yīng)的值。需要指出的是Aarts等人的冷卻進度表中的位置被初始接受率所取代。②降溫策略Aarts等人首先把準平衡條件用來替代.上式對某些正數(shù)成立，并假定準平衡在處到達且算法進程中始終保持。那么控制參數(shù)兩個相鄰值上的平穩(wěn)分布相互逼近，且可量化為上式對某些小正數(shù)成立〔與準平衡式中的相關(guān)〕。然后證明了上式成立的一個充分條件其中，再把上式改寫成最后經(jīng)化簡得的衰減函數(shù)。小的值導致控制參數(shù)t的小的衰減量，反之亦然。在Aarts等人的冷卻進度表中參數(shù)稱為距離參數(shù)。③馬爾可夫鏈長度Aarts等人猜測由于上述控制參數(shù)的衰減函數(shù)導致控制參數(shù)兩個相鄰值上的平穩(wěn)分布相互逼近，因此只要在值上到達準平衡，那么控制參數(shù)下一取值上的準平衡只須進行少量的抽樣就可迅速逼近。他們假設(shè)這個“少量抽樣”可以指定為，算法能以一個充分大的概率至少訪問給定解大局部領(lǐng)域所需進行抽樣的次數(shù)。然后，Aarts等人證明，對基數(shù)為的集合S進行N次重復抽樣，S中不同元素被選中的概率在N和為大值時，可近似為如果模擬退火算法對給定解i產(chǎn)生鏈長為L的馬爾可夫鏈，并假設(shè)在馬爾可夫鏈產(chǎn)生期間沒有接受任一變換，那么由上式可知，在馬爾可夫鏈產(chǎn)生過程中解i的不同領(lǐng)域近似解被訪問的概率是其中是領(lǐng)域規(guī)模〔〕。假設(shè)取，那么上述概率近似等于2/3。對于三個相繼的鏈長為的馬爾可夫鏈，這個概率近似等于1，說明解i的整個領(lǐng)域幾乎全被訪問到。于是，Aarts等人在其冷卻進度表中，把選定為領(lǐng)域規(guī)模，即④停止準那么在溫度t，定義平衡時目標函數(shù)的期望值為：Aarts等人對控制參數(shù)終值的選取基于期望目標函數(shù)在時的外推。設(shè)那么當小于處的期望目標函數(shù)值時，就終止算法。而對于充分大的值，有而。因此對t《1，可近似為于是能夠可靠地終止算法，假設(shè)對某些成立，其中是某些小正數(shù)。Aarts等人把上式稱為停止準那么。10.4模擬退火算法的應(yīng)用模擬退火算法具有廣泛的應(yīng)用性，可用于求解許多組合優(yōu)化問題。根據(jù)模擬退火算法的過程〔產(chǎn)生新解——計算目標函數(shù)差——判別是否接受新解——接受或舍棄新解〕，在算法的實際應(yīng)用中必須解決好三個問題：第一，問題的數(shù)學描述；第二，新解的產(chǎn)生和接受機制；第三，冷卻進度表的選取。其中第三個問題在上面已經(jīng)討論過了，此處不再贅述。此外，還必須有一個隨機數(shù)產(chǎn)生器。問題的描述主要包括解空間和目標函數(shù)兩局部。解空間為所有可行解〔有時也包含不可行解〕的集合它限定了初始解選取和新解產(chǎn)生的范圍。對于無約束優(yōu)化問題，任一可能解即為可行解；對于有約束優(yōu)化問題，解集中還可以包含一些不可行解，同時在目標函數(shù)中加上懲函數(shù)，以懲罰出現(xiàn)的不可行解。新解的產(chǎn)生和接受可分為四個步驟：第一，給出新解的變換方法，得到一個產(chǎn)生裝置，以從當前解產(chǎn)生一個新解；第二，計算新解和當前解的目標函數(shù)差，由于目標函數(shù)差僅由變換局部產(chǎn)生，因此，通常按增量計算目標函數(shù)差；第三，判斷新解是否被接受，判斷的依據(jù)是米特羅波利斯準那么，對于有約束優(yōu)化問題往往還伴隨有新解可行性的判斷；第四，接受或舍棄新解，假設(shè)接受，用新解代替當前解，同時修正目標函數(shù)值，否那么當前解與目標函數(shù)值保持不變。下面僅對幾個典型的組合優(yōu)化問題給出實現(xiàn)的算法描述，以揭示其建立數(shù)學模型和新解產(chǎn)生裝置的根本方法。10.4.1旅行商問題〔TSP〕設(shè)有n個城市和距離矩陣D=[]，其中表示城市i到城市j的距離，i,j=1,…，n，尋找遍訪每個城市恰好一次的一條回路，且其路徑長度為最短。求解的模擬退火算法描述如下：①解空間解空間S可表為{1,2，…，n}的所有循環(huán)排列的集合，即S={(,…,)|(,…,)為(1,2，…，n)的循環(huán)排列}，其中每一循環(huán)排列表示遍訪n個城市的一條回路，=j表示在第i個次序訪問城市j，并約定=。初始解可選為〔1,2，…，n〕。②目標函數(shù)此時的目標函數(shù)即為訪問所有城市的路徑長度或稱為代價函數(shù)，須求其最小值，選為f(,…,)=其中=。③新解的產(chǎn)生〔2變換法〕任選訪問的序號u和v,逆轉(zhuǎn)u和v及其之間的訪問順序，此時新路徑為〔設(shè)u<v〕……④代價函數(shù)差伴隨新解的代價函數(shù)差可由公式f=(+)-(++)計算。特別地，當問題為對稱的，即距離矩陣D=[]為對稱矩陣時，因為,上式可簡化為10.4.20-1背包問題〔ZKP〕給定一個可裝重量M的背包n件物品，物品i的重量和價值分別為和,i=1,,n。要選假設(shè)干件物品裝人背包，使其價值之和最大。求解的模擬退火算法描述如下：①解空間ZKP是一個有約束的優(yōu)化問題。為此，我們限定解空間為所有可行解的集合，即S={()|}其中表示物品i被選擇裝入背包。初始解選為(0,…,0)。②目標函數(shù)為一需求最大值的代價函數(shù)但必須滿足約束，i=1,…,n.③新解的產(chǎn)生隨機選取物品i。假設(shè)i不在背包中，那么將其直接裝入背包，或同時從背包中隨機取出另一件物品j。假設(shè)i已在背包中，那么將其取出，同時隨機裝入另一件物品j。即④背包價值差及重量差根據(jù)產(chǎn)生新解的三種可能，伴隨的背包代價差為為判定解的可行性，還需要求出對應(yīng)的背包重量差為其中為當前背包重量m的增重⑤接受準那么是擴充了可行性測定的馬爾可夫鏈準那么其中和分別由四中的兩式計算。10.4.3最大截問題〔MCP〕給定帶權(quán)圖G={V,E}，其中為頂點集合，E為邊集，權(quán)矩陣為。要將V劃分為子集和，使E中所有頂點分屬和的權(quán)之和最大。①解空間可表為V的所有劃分為兩子集和分劃的集合，即其中分劃表示頂點。初始解選為。②目標函數(shù)直接取為分劃所得得到的截量的相反數(shù)需求其最小值。即相應(yīng)截量的最大值。③新解的產(chǎn)生任選頂點，將其從目前所在的子集移到另一個子集中去，即:。④目標函數(shù)差根據(jù)目標函數(shù)和產(chǎn)生新解的方法可知，相應(yīng)于目標函數(shù)差為10.4.4獨立集問題〔ISP〕設(shè)有圖G=〔V，E〕，為頂點集。要找V的最大獨立集，即找最大的，滿足時必有。模擬退火算法的求解形式為：①解空間取V的冪集，即V的所有子集的集合注意到解空間S中可能含有不可行解，即可能存在V的子集,但并非獨立集，初始解為。如此構(gòu)造解空間可以使得產(chǎn)生新解的方法簡便，同時使算法可以從一個局部最優(yōu)的可行解變換為稍差的不可行解，以增大“逃離”局部最優(yōu)“陷阱”的概率。當然，這會使目標函數(shù)的構(gòu)造變的復雜一些。②目標函數(shù)為“懲罰”可能出現(xiàn)的不可行解，將目標函數(shù)選為其中表示點集的元素個數(shù)，表示邊集的元素個數(shù)。是一個大于1的懲罰因子，用于“懲罰”在中存在的邊。注意到時，恰好是獨立集的元素個數(shù)。③新解的產(chǎn)生通過任選頂點，當時將其移出，而時那么將其移入來產(chǎn)生，即其中為集特征函數(shù)，定義為：④目標函數(shù)差設(shè)表示圖G的鄰接矩陣，表示頂點與鄰接，即，且。那么伴隨新解的目標函數(shù)差為即10.4.5調(diào)度問題〔SCP〕有n個相互獨立的任務(wù)，所需時間分別為，均可由m臺機器中的一臺完成，且每臺機器一次僅可完成一項任務(wù)，要找一個最小調(diào)度，即找對n個任務(wù)的一個調(diào)度，使完成所有任務(wù)的時間最短。求解的模擬退火算法為①解空間一個調(diào)度可看成對正數(shù)集的一個分劃因此解空間可由所有可能的分劃組成，即初始解可選為。②目標函數(shù)SCP是要使分劃的誅子集中的各正數(shù)的和的最大值為最小，即需求的最小值，易證其最小值對應(yīng)于的最小值。所以劃分的目標函數(shù)可定義為但此時求出的最小值并非所得調(diào)度的實際需要時間。③新解的產(chǎn)生任選，將其移到任選的另一個子集中去，即它對應(yīng)于將所需時間為t的任務(wù)從機器調(diào)到機器上去完成。④目標函數(shù)差由目標函數(shù)可得，伴隨于新解的目標函數(shù)差為⑤停止準那么的擴充與前述問題不同，SCP的目標函數(shù)有一個確定且有時可以到達的下界它對應(yīng)于所有臺機器所需時間均為的情況，即的最小值。此時的調(diào)度必為一個最小調(diào)度。因此可在停止準那么中加一個形如iff=then停止算法運行的判斷。10.4.6圖著色問題〔GCP〕給定圖G=(G,V),為頂點集，E為邊集。要找G的一個最小著色，即找一個最小的正整數(shù)k和映射，使得，當時有。為了用模擬退火算法求解，首先注意到，假設(shè)圖G的頂點個數(shù)為n，那么圖G的最小著色的上界為n。此外，GCP也是一個有約束的優(yōu)化問題，我們同樣使用懲函數(shù)將其轉(zhuǎn)化為無約束問題。①解空間記將頂點集V劃分為n個子集的任一分劃為那么解空間的表為注意到可能存在，且有些分劃可能并非可行解。初始解就選為。②目標函數(shù)選為其中表示分劃中非空集合的個數(shù)。為懲函數(shù)因子。顯然的最小值即為最小著色的顏色數(shù)。③新解的產(chǎn)生任選頂點，將其從當前所在子集移到任選的另一個子集中去。即但限定時。④目標函數(shù)差仍設(shè)為G的鄰接矩陣，那么相應(yīng)于新解的目標函數(shù)差為其中sgn〔x〕定義為10.4.7關(guān)于模擬退火算法應(yīng)用的說明上面給出了6個典型的組合優(yōu)化問題的模擬退火算法描述。為了更好的應(yīng)用模擬退火算法,需要作以下幾點說明:(1)上面6個問題都是所謂的NP完全問題，根據(jù)的著名猜測，它們均不存在可行的精確算法。因此，對這類問題尋找高效可行的近似算法有著重要的實際意義和理論價值，模擬退火算法就是這樣的近似算法之一。(2)目前人們已發(fā)現(xiàn)千余個NP完全問題，這些NP完全問題中有許多可以用模擬退火算法求解，以上給出的僅僅是其中很小的一個子集。(3)上述算法只是說明模擬退火算法應(yīng)用的根本方法,如解空間的構(gòu)造、目標函數(shù)的定義、新解的產(chǎn)生方法、目標函數(shù)差的計算以及接受準那么的應(yīng)用等，其描述較為粗略，在實際應(yīng)用時還需作一些技術(shù)上的處理。(4)以上這些算法具有一定的典型性，有些可以推廣使用。如調(diào)度問題(SCP)的算法可以直接求解劃分問題(PAP)；0-1背包問題(ZKP)的算法可略加修改后用于解一般的整數(shù)背包問題、多約束的0-1背包問題、最小化的0-1規(guī)劃問題乃至于一般的整數(shù)規(guī)劃問題。再如鑒于圖的獨立集和覆蓋集的互補性，可根據(jù)解獨立集問題(ISP)的算法求出的最大獨立集直接得到最小覆蓋集。(5)模擬退火算法是一種隨機