模擬退火算法

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