【正文】 這個(gè)最小值即使不是絕對(duì)最小，也相當(dāng)接近絕對(duì)最小了。當(dāng)N不斷增大時(shí)，運(yùn)行時(shí)間將迅速增加，進(jìn)而導(dǎo)致費(fèi)用高到令人難以接受的程度。這個(gè)間題屬于一類所謂“NP完全問題”。三、組合極小化：旅行推銷員問題下面是我們用“旅行推銷員問題”為具體實(shí)例說明模擬退火法的應(yīng)用。另一方面，某些當(dāng)前解要達(dá)到最優(yōu)解時(shí)必須經(jīng)過暫時(shí)惡化的“山脊”，因此，上述這些停止準(zhǔn)則無法保證最終解正好是整個(gè)搜索過程中曾經(jīng)達(dá)到的最優(yōu)解。在傳統(tǒng)的模擬退火過程中，算法終止于一個(gè)預(yù)先規(guī)定的停止準(zhǔn)則S，如：控制參數(shù)t的值小于某個(gè)充分小的正數(shù)；相繼的若干個(gè)Markov鏈中解未得到任何改善；兩個(gè)相繼Markov鏈所得解的差的絕對(duì)值小于某個(gè)充分小的正數(shù)等。但存在很多弊病，國內(nèi)外學(xué)者并對(duì)其作相應(yīng)的改進(jìn)，得到了改進(jìn)的模擬退火算法，包括：加溫退火法、有記憶的模擬退火算法、帶返回搜索的模擬退火算法、多次尋優(yōu)法、回火退火算法等。 溫度管理問題也是模擬退火算法難以處理的問題之一。實(shí)際應(yīng)用中，要針對(duì)具體問題的性質(zhì)和特征設(shè)置合理的退火平衡條件。 模擬退火算法的全局搜索性能也與退火速度密切相關(guān)。實(shí)際應(yīng)用過程中，初始溫度一般需要依據(jù)實(shí)驗(yàn)結(jié)果進(jìn)行若干次調(diào)整。 模擬退火算法的參數(shù)控制問題 模擬退火算法的應(yīng)用很廣泛，可以求解NP完全問題，但其參數(shù)難以控制，其主要問題有以下三點(diǎn)： (1) 溫度T的初始值設(shè)置問題。 　　　End。 　　　　　　End。 //f(S)為路徑總長 　　　　　　　　IF(Δt0) OR (EXP(Δt/T)Randomof[0,1]) 　　　　　　　　S=S′。 　　while termination=false 　　　begin 　　　　for i=1 to L do 　　　　　　begin 　　　　　　　　generate(S′form S)。 // T為初始溫度 　　S={1，……，n}。例如：隨機(jī)產(chǎn)生1和n之間的兩相異數(shù)k和m，不妨假設(shè)km，則將原路徑 變?yōu)樾侣窂剑荷鲜鲎儞Q方法就是將k和m之間對(duì)應(yīng)的多個(gè)城市在路徑序列顛倒位置, 可簡單說成是“逆轉(zhuǎn)中間或者逆轉(zhuǎn)兩端”。這種變換方法就是將k和m對(duì)應(yīng)的兩個(gè)城市在路徑序列中交換位置,稱為2opt映射。 　　我們要求的最優(yōu)路徑為目標(biāo)函數(shù)(代價(jià)函數(shù))為最小值時(shí)對(duì)應(yīng)的路徑。初始解可選為(1,……, n) 。城市i和城市j之間的距離為d(i，j) i, j=1,…,n．TSP問題是要找遍訪每個(gè)域市恰好一次的一條回路，且其路徑總長度為最短.。 模擬退火算法與初始值無關(guān)，算法求得的解與初始解狀態(tài)S(是算法迭代的起點(diǎn))無關(guān)；模擬退火算法具有漸近收斂性，已在理論上被證明是一種以概率1 收斂于全局最優(yōu)解的全局優(yōu)化算法；模擬退火算法具有并行性。可在此基礎(chǔ)上開始下一輪試驗(yàn)。 第四步，是當(dāng)新解被確定接受時(shí)，用新解代替當(dāng)前解，這只需將當(dāng)前解中對(duì)應(yīng)于產(chǎn)生新解時(shí)的變換部分予以實(shí)現(xiàn)，同時(shí)修正目標(biāo)函數(shù)值即可。事實(shí)表明，對(duì)大多數(shù)應(yīng)用而言，這是計(jì)算目標(biāo)函數(shù)差的最快方法。 第二步，是計(jì)算與新解所對(duì)應(yīng)的目標(biāo)函數(shù)差。 (7) T逐漸減少，且T0，然后轉(zhuǎn)第2步。 模擬退火的基本思想: (1) 初始化：初始溫度T(充分大)，初始解狀態(tài)S(是算法迭代的起點(diǎn))， 每個(gè)T值的迭代次數(shù)L (2) 對(duì)k=1，……，L做第(3)至第6步： (3) 產(chǎn)生新解S′ (4) 計(jì)算增量Δt′=C(S′)C(S)，其中C(S)為評(píng)價(jià)函數(shù) (5) 若Δt′0則接受S′作為新的當(dāng)前解，否則以概率exp(Δt′/T)接受S′作為新的當(dāng)前解. (6) 如果滿足終止條件則輸出當(dāng)前解作為最優(yōu)解，結(jié)束程序。應(yīng)說明的是，這里“高”和“低”的含義，還有進(jìn)程表的確定，都需要一定的物理知識(shí)和/或一些摸索的實(shí)驗(yàn)。3. 一個(gè)目標(biāo)函數(shù) (類似于能量)，求解的極小值，即為算法所要完成的工作。為了將米特波利斯算法應(yīng)用于熱力學(xué)以外的系統(tǒng)，必須提供以下幾項(xiàng)基本要素：1. 對(duì)可能的系統(tǒng)構(gòu)形的一種描述。這種格式總是采取下降過程，偶爾采取上升步驟。他們對(duì)一個(gè)模擬熱力學(xué)系統(tǒng)提供了一系列選擇項(xiàng)，并假設(shè)：系統(tǒng)構(gòu)形從能量變化到能量的概率為。換句話說，在有些情況下系統(tǒng)的能量可上升，也可下降，但是溫度越低，顯著上升的可能性就越小。并找到一個(gè)更好的、更接近于整體的極小點(diǎn)。即使在很低的溫度下，系統(tǒng)也有可能（雖然這種可能性很?。┨幱谝粋€(gè)較高的能量狀態(tài)。但是，正如前面常常提到的，這種方法往往只能求得局部極小點(diǎn)，卻求不到整體最小點(diǎn)。盡管我們的比喻并不算貼切，但是迄今為止本身所討論的所有極小化算法，確實(shí)與快速冷卻猝熄有某種關(guān)聯(lián)之處。因此，這一過程的本質(zhì)在于緩緩地致冷，以爭取充足的時(shí)間，讓大量原子在喪失可動(dòng)性之前進(jìn)行重新分布。對(duì)于這個(gè)系統(tǒng)來說，晶體狀態(tài)是能量最低狀態(tài)；而所有緩慢冷卻的系統(tǒng)都可以自然達(dá)到這個(gè)能量最低狀態(tài)，這可以說是一個(gè)令人驚奇的事實(shí)。如果該流體慢慢地冷卻下來，熱能可動(dòng)性便會(huì)消失。模擬退火的核心思想與熱力學(xué)的原理頗為相似，而且尤其類似于液體流動(dòng)和結(jié)晶以及金屬冷卻和退火方式。正如在下文中我們將看到的，模擬退火法的試探步驟是“隨機(jī)”的。后面我們還將介紹如何在其有連續(xù)控制參數(shù)的空間中利用模擬退火法。構(gòu)形空間中元素的數(shù)量相當(dāng)巨大，根本不可能窮舉，而且因?yàn)榧鲜请x散的，我們也不可能“沿合適的方向連續(xù)下降”。請(qǐng)注意，我們上面提到的兩個(gè)例子都屬于組合極小化問題。在實(shí)用上，它有效地“解決了”著名的旅行推梢員問題，即在必須依次訪問每一個(gè)城市(共有N個(gè)城市)的前提下，為旅行推銷員設(shè)計(jì)一條能夠返回起點(diǎn)的最短旅程。一、模擬退火法模擬退火法(參見[1,2])作為一種適合于求解大規(guī)模的優(yōu)化問題的技術(shù)，近來已引起極大的關(guān)注。特別是當(dāng)優(yōu)化問題有很多局部極值而全局極值又很難求出時(shí)，模擬退火法尤其有效。模擬退火方法還被成功地用于設(shè)計(jì)復(fù)雜的集成電路，也就是說如何最佳地安排幾十萬個(gè)電路元件，使它們?nèi)考稍谝粋€(gè)很小的硅片上，而相互連接的線路之間的纏繞能夠達(dá)到最小(參見[3,4]).盡管模擬退火法的功效非凡，但它的算法實(shí)現(xiàn)卻相對(duì)地簡單，這一點(diǎn)似乎有些不可思議?，F(xiàn)本類問題通常也有一個(gè)目標(biāo)函數(shù)，但是函數(shù)的定義域并不是簡單地由N個(gè)連續(xù)參變量組成的N維空間，而是一個(gè)離散的巨大空間，例如，由所有可能的城市旅行路線組成的集合，或者硅片電路元件的所有可能的分配方式的集合。因此在構(gòu)形空間中，“方向”概念就沒有什么意義了。這種應(yīng)用實(shí)際上要比組合問題復(fù)雜一些，因?yàn)槠渲杏忠霈F(xiàn)“狹長山谷”的情況。但在一個(gè)狹窄且漫長的等高線山谷中，幾乎所有的隨機(jī)步驟都呈向上的趨勢(shì)，因此，算法中需要增加一些技巧。在高溫下，一種液體的大最分子彼此之間進(jìn)行著相對(duì)自由的移動(dòng)。大量原子常常能夠自行排列成行，形成一個(gè)純凈的晶體，該晶體在各個(gè)方向上都被完全有序地排列在幾百萬倍于單個(gè)原子大小的距離之內(nèi)。實(shí)際上，如果某種液體金屬被迅速冷卻或被“猝熄”，那么它不會(huì)達(dá)到這一狀態(tài)，而只能達(dá)到一種具有較高能量的多晶狀態(tài)或非結(jié)晶狀態(tài)。這就是所謂退火在技術(shù)上的定義，同時(shí)也是確保達(dá)到低能量狀態(tài)所必需的條件。以往我們處理問題的方式都是:從初始點(diǎn)開始，立即沿下降方向前進(jìn)，走得越遠(yuǎn)越好，似乎這樣才能迅速求得問題的解。自然界本身的極小化算法則基于一種截然不同的方式，所謂的玻爾茲曼(Boltzmann)概率分布 （1）表達(dá)了這樣一種思想，即:一個(gè)處于熱平衡狀態(tài)且具有溫度T的系統(tǒng)，其能量按照概率，分布于所有不同能量狀態(tài)之中。因此，相應(yīng)地，系統(tǒng)也能夠獲得擺脫局部能量極小點(diǎn)的機(jī)會(huì)。式(1)中的參數(shù)k(稱為玻爾茲曼常數(shù))是一個(gè)自然常數(shù)，它的作用是將溫度與能量聯(lián)系起來。1953年，米特羅波利斯(Metropolis)及其合作者們首次將這種原理滲透到數(shù)值計(jì)算中。很顯然，如果，將大于1；在這類情況下，對(duì)構(gòu)形的能量變化任意指定一個(gè)概率值，也就是說，該系統(tǒng)總是取這個(gè)選擇項(xiàng)。目前已被公認(rèn)為米特羅波利斯算法。2. 一個(gè)有關(guān)構(gòu)形內(nèi)部隨機(jī)變化的生成函數(shù)，這些變化將作為“選擇項(xiàng)”提交給該系統(tǒng)。4. 一個(gè)控制參數(shù)T(類似于溫度)和一個(gè)退火進(jìn)程，該進(jìn)程用來說明系統(tǒng)是如何從高值向低值降低的，例如在溫度T時(shí)每次下降步驟中要經(jīng)過多少次隨機(jī)的構(gòu)形變化以及該步長是多大等等。模擬退火算法的模型模擬退火算法可以分解為解空間、目標(biāo)函數(shù)和初始解三部分。 終止條件通常取為連續(xù)若干個(gè)新解都沒有被接受時(shí)終止算法。 模擬退火算法新解的產(chǎn)生和接受可分為如下四個(gè)步驟： 第一步，是由一個(gè)產(chǎn)生函數(shù)從當(dāng)前解產(chǎn)生一個(gè)位于解空間的新解；為便于后續(xù)的計(jì)算和接受，減少算法耗時(shí)，通常選擇由當(dāng)前新解經(jīng)過簡單地變換即可產(chǎn)生新解的方法，如對(duì)構(gòu)成新解的全部或部分元素進(jìn)行置換、互換等，注意到產(chǎn)生新解的變換方法決定了當(dāng)前新解的鄰域結(jié)構(gòu)，因而對(duì)冷卻進(jìn)度表的選取有一定的影響。因?yàn)槟繕?biāo)函數(shù)差僅由變換部分產(chǎn)生，所以目標(biāo)函數(shù)差的計(jì)算最好按增量計(jì)算。 第三步，是判斷新解是否被接受,判斷的依據(jù)是一個(gè)接受準(zhǔn)則，最常用的接受準(zhǔn)則是Metropo1is準(zhǔn)則: 若Δt′0則接受S′作為新的當(dāng)前解S，否則以概率exp(Δt′/T)接受S′作為新的當(dāng)前解S。此時(shí)，當(dāng)前解實(shí)現(xiàn)了一次迭代。而當(dāng)新解被判定為舍棄時(shí)，則在原當(dāng)前解的基礎(chǔ)上繼續(xù)下一輪試驗(yàn)。 模擬退火算法的簡單應(yīng)用 　　作為模擬退火算法應(yīng)用，討論貨郎擔(dān)問題(Travelling Sal