遺傳算法概述摘要：遺傳算法（geneticalgorithms,GA）是人工智能的重要新分支，是基于達(dá)爾文進(jìn)化論，在微型計(jì)算機(jī)上，模擬生命進(jìn)化機(jī)制而發(fā)展起來的一門學(xué)科。它根據(jù)適者生存、優(yōu)勝劣汰等自然進(jìn)化規(guī)則來進(jìn)行搜索計(jì)算機(jī)和問題求解。對許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的非常復(fù)雜的問題，特別是最優(yōu)化問題，GA提供了一個(gè)行之有效的新途徑。近年來，由于遺傳算法求解復(fù)雜優(yōu)化問題的巨大潛力及其在工業(yè)控制工程領(lǐng)域的成功應(yīng)用，這種算法受到了廣泛的關(guān)注。本文旨在闡述遺傳算法的基本原理、操作步驟和應(yīng)用中的一些基本問題，以及為了改善SGA的魯棒性而逐步發(fā)展形成的高級遺傳算法（refinegeneticalgorithms,RGA）的實(shí)現(xiàn)方法。一、遺傳算法的基本原理和特點(diǎn)遺傳算法將生物進(jìn)化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按著一定的適值函數(shù)及一系列遺傳操作對各個(gè)體進(jìn)行篩選，從而使適值高的個(gè)體被保留下來，組成新的群體，新群體包含上一代的大量信息，并且引入了新一代的優(yōu)于上一代的個(gè)體。這樣周而復(fù)始，群體中各個(gè)體適值不斷提高，直至滿足一定的極限條件。此時(shí)，群體中適值最高的個(gè)體即為待優(yōu)化參數(shù)的最優(yōu)解。正是由于遺傳算法獨(dú)具特色的工作原理，使它能夠在復(fù)雜的空間進(jìn)行全局優(yōu)化搜索，并且具有較強(qiáng)的魯棒性；另外，遺傳算法對于搜索空間，基本上不需要什么限制性的假設(shè)（如連續(xù)性、可微及單峰等）。同常規(guī)優(yōu)化算法相比，遺傳算法有以下特點(diǎn)。（1）遺傳算法是對參數(shù)編碼進(jìn)行操作，而非對參數(shù)本身。遺傳算法首先基于一個(gè)有限的字母表，把最優(yōu)化問題的自然參數(shù)集編碼為有線長度的字符串。例如，一個(gè)最優(yōu)化問題：在整數(shù)區(qū)間【0，31】上求函數(shù)f（x）=x2的最大值。若采用傳統(tǒng)方法，需要不斷調(diào)節(jié)x參數(shù)的取值，直至得到最大的函數(shù)值為止。而采用遺傳算法，優(yōu)化過程的第一步的是把參數(shù)x編碼為有限長度的字符串，常用二進(jìn)制字符串，設(shè)參數(shù)x的編碼長度為5,“00000”代表0，“11111”代表31，在區(qū)間【0，31】上的數(shù)與二進(jìn)制編碼之間采用線性映射方法；隨機(jī)生成幾個(gè)這樣的字符串組成初始群體，對群體中的字符串進(jìn)行遺產(chǎn)操作，直至滿足一定的終止條件；求得最終群體中適值最大的字符串對應(yīng)的十進(jìn)制數(shù)，其相應(yīng)的函數(shù)值則為所求解。可以看出，遺傳算法是對一個(gè)參數(shù)編碼群體進(jìn)行的操作，這樣提供的參數(shù)信息量大，優(yōu)化效果好。（2）遺傳算法是從許多點(diǎn)開始并行操作，并非局限于一點(diǎn)，從而可有效防止搜索過程收斂于局部最優(yōu)解。（3）遺傳算法通過目標(biāo)函數(shù)計(jì)算適值，并不需要其他推導(dǎo)和附加信息，因而對問題的依賴性較小。（4）遺傳算法的尋優(yōu)規(guī)則是由概率決定的，而非確定性的。（5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目的窮舉或完全隨機(jī)搜索。（6）遺傳算法對求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求。由于它的進(jìn)化特性，它在解的搜索中不需要了解問題的內(nèi)在性質(zhì)。遺傳算法可以處理任意形式的目標(biāo)函數(shù)和約束，無論是線性的還是非線性的，離散的還是連續(xù)的，甚至是混合的搜索空間。（7）遺傳算法具有并行計(jì)算的特點(diǎn)，因而可通過大規(guī)模并行計(jì)算來提高計(jì)算速度。二、遺傳算法的模式理論1、模式一個(gè)模式（schemata）就是一個(gè)描述種群在位串的某些確定位置上具有相似性的一組符號串。為了描述一個(gè)模式，在用以表示位串的兩個(gè)字符｛0，1｝中加入一個(gè)通配符“*”，就構(gòu)成了一個(gè)表示模式用的3個(gè)字符的符號表｛0,1,*｝。因此用三個(gè)元素符號表｛0,1,*｝可以構(gòu)造出任意一種模式。當(dāng)一個(gè)模式與一個(gè)特定位串相匹配時(shí)，意味著該模式中的1與位串中的1相匹配，模式中的0與位串中的0相匹配，模式中的“*”與位串中的0或1相匹配。例如，模式00*00匹配了兩個(gè)位串，即｛00100,00000｝；模式*111*可以和｛01110,01111,11110,11111｝中的任何一個(gè)相匹配；模式0*1**則匹配了長度為5,第一位為0、第三位為1的八個(gè)位串，即｛00100,00101,00110,00111,01100,01101,01110,01111｝。模式的思路提供了一種簡單而有效的方法，使能夠在有限符號表的基礎(chǔ)上討論有限長位串的嚴(yán)謹(jǐn)定義的相似性。應(yīng)強(qiáng)調(diào)的是，“*”只是一個(gè)代表其他符號的一個(gè)元符號，它不能被遺傳算法直接處理，但可以據(jù)此計(jì)算出所有可能的模式。一般地，假定符號表的基數(shù)是k,例如｛0,1｝的基數(shù)是2,則定義在該符號表上的長度為l的位串中，所有可能包含的最大模式數(shù)為(k+l)i,原因是在l個(gè)位置中的任何一個(gè)位置上即可以取k個(gè)字符中的任何一個(gè)又可以取通配符“*”，即共有k+l個(gè)不同的表示，則l個(gè)位置的全排列數(shù)為(k+l)l。例如，對長度l=5,k=2(對應(yīng)0,1),則會有3X3X3X3X3=35=243=(k+l)l種不同的符號串，而位串的數(shù)量僅為kl=25=32?？梢?，模式的數(shù)量要大于位串的數(shù)量。對于由0、1和*定義且長度為l的符號串所能組成的最大模式數(shù)為(2+l)l。對于任一長度為l的給定位串，當(dāng)任一位置上只有兩種不同表示時(shí)，所含模式數(shù)為2l個(gè)，因此對于含有n個(gè)位串個(gè)體的種群可能包含的模式數(shù)在2l?nX2i之間。不難看出，遺產(chǎn)算法正是利用種群中位串之間的眾多的相似性以及適值之間的相關(guān)性，來引導(dǎo)遺傳算法進(jìn)行有效地搜索。為了區(qū)分不同類型的模式，對模式H定義兩個(gè)量：模式位數(shù)(order)和模式的定義長度(defininglength)分別表示為O(H)和5(H)。O(H)是H中有定義的非“*”位的個(gè)數(shù)，模式定義長度5(H)是指H中左右兩端有定義位置之間的距離。這兩個(gè)量為分析位串的相似性及分析遺傳操作對重要模式的影響提供了基本手段。2、復(fù)制對模式的影響設(shè)在給定時(shí)間(代)t，種群A(t)包含m個(gè)特定模式H,記為m=m(H,t)在復(fù)制過程中，A(t)中的任何一個(gè)位串Ai以概率Pi=fi/Ef.被選中并進(jìn)行復(fù)制。假如選擇是有放回的抽樣，且兩代種群之間沒有交疊(即若A(t)的規(guī)模為n,則在產(chǎn)生A(t+1)時(shí)，必須從A(t)中選n個(gè)位串進(jìn)匹配集)，可以期望在復(fù)制完成后，在t+1時(shí)刻，特定模式H的數(shù)量為：m(H,t+1)=m(H,t)nf(H)/Efi其中,f(H)是在t時(shí)刻對應(yīng)模式H的位串的平均適值，因?yàn)檎麄€(gè)群的平均適值f=Efi/n,則上式又可寫為f(H)m(H,t+1)=m(H,t)—f—經(jīng)過復(fù)制操作后，下一代中特定模式的數(shù)量H正比于所在位串的平均適值與種群平均適值的比值。若f(H)>f，則H的數(shù)量將增加，若f(H)<f，則H的數(shù)量將減少。即若包含H的個(gè)體位串的平均適值高于當(dāng)前種群中所有個(gè)體位串的平均適值，則種群包含特模式的下一代中的數(shù)量將增加；反之，減少。操作中模式的增減在復(fù)制中是并行的，這恰恰表現(xiàn)了遺傳算法隱含的并行性。為了進(jìn)一步分析高于平均適值的模式數(shù)量的增長，假設(shè)f(H)-f=3(c是一個(gè)大于零的常數(shù))，則上式可寫為:,一、，、f+cm(H,t+1)=m(H,t)=(1+c)m(H,t)f從原始種群開始(t=0)，并假定是一個(gè)穩(wěn)態(tài)的值，則有m(H,t+1)=m(H,0)(1+c)t可見，對于高于平均適值的模式數(shù)量將按指數(shù)規(guī)律增長(c>0)。從對復(fù)制的分析可以看到，雖然復(fù)制過程成功的以并行方式控制著模式數(shù)量以指數(shù)規(guī)模增減，但由于復(fù)制只是將某些高適值個(gè)體全盤復(fù)制，或者淘汰某些低適值個(gè)體，而決不會產(chǎn)生新的模式結(jié)構(gòu)，因而性能的改進(jìn)是有限的。2、交叉對模式的影響交叉過程是位串之間有組織的隨機(jī)的信息交換。交叉操作對一個(gè)模式H的影響與模式的定義長度§(H)有關(guān)，5(H)越大，模式H被分裂的可能性越大，因?yàn)榻徊娌僮饕S機(jī)選擇出進(jìn)行匹配的一對位串上的某一隨機(jī)位置進(jìn)行交叉。顯然5(H)越大，H的跨度就越大，隨機(jī)交叉點(diǎn)落入其中的可能性就越大，從而H的存活率就降低。例如位串長度l=7,有如下包含兩個(gè)模式的位串A為A=01111000H1=*1****0,5(H1)=5H2=***10**,5(H2)=1隨機(jī)產(chǎn)生的交叉位置在3和4之間A=01151000H1=*1*:***0,Pd=5/6H2=***：10**,Pd=1/6模式H1定義長5(H1)=5，若交叉點(diǎn)始終是隨機(jī)地從l-1=7-1=6個(gè)可能的位置選取，則模式H1被破壞的概率為Pd=5(H1)/(l-1)=5/6它的存活概率為Ps=1-Pd=1/6類似的，模式H2的定義長度5(H2)=1，它被破壞的概率為Pd=1/6，它存活的概率為Ps=1-Pd=5/6.因此，模式H1比模式H2在交叉中更容易受到破壞。一般情況下可以計(jì)算出任何模式的交叉存活概率的下限為15(H)Ps>1l-1在上面的討論中，均假設(shè)交叉的概率為1。若交叉的概率為Pc(即在選出進(jìn)匹配集的一對位串上發(fā)生交叉操作的概率)，則存活率為Ps>1-PC虹l-1在復(fù)制交叉之后，模式的數(shù)量則為m(H,t+1)=m(H,t)f^H^Ps即m(H,t+1)>m(H,t)f^H-ff因此，在復(fù)制和交叉的綜合作用之下，模式H的數(shù)量變化取決于其平均適值的高低和定義長度的長短，f(H)越大，5(H)越小，則H的數(shù)量就越多。3、變異對模式的影響變異是對位串中的單個(gè)位置以概率Pm進(jìn)行隨機(jī)替換，因而它可能破壞特定的模式。一個(gè)模式H要存活，意味著它所有的確定位置都存活。因此，由于單個(gè)位置的基因值存活的概率為1-Pm，而且由于每個(gè)變異的發(fā)生是統(tǒng)計(jì)獨(dú)立的，因此，一個(gè)特定模式僅當(dāng)它的O(H)個(gè)確定位置都存活是才存活，從而得到經(jīng)變異后，特定模式的存活率為(1-Pm)o(h)，即(1-Pm)自乘O(H)次，由于一般情況下Pm<<1,H的存活率可表示為(1-Pm)o(HF-O(H)Pm綜合考慮復(fù)雜、交叉和變異操作的共同作用，則模式H在經(jīng)歷復(fù)制、交叉、變異操作之后，在下一代中的數(shù)量可表示為m(H,t+1)>m(H,t)^(^1-Pc1-O(H)Pm]fLi-1也可近似表示為m(H,t+1)>m(H,t)^^1-Pc-O(H)PmfLi-1由上述分析可以得出結(jié)論：定義長度短的、確定位數(shù)少的、平均適值高的模式數(shù)量將隨著代數(shù)的增加呈指數(shù)增長。這個(gè)結(jié)論稱為模式理論或遺傳算法基本定理。根據(jù)模式理論，隨著遺傳算法一代一代地進(jìn)行，那些定義長度短的，位數(shù)少的，高適值的模式將越來越多，因而可期望最后得到的位串的性能越來越得到改善，并最終趨向全局最優(yōu)點(diǎn)。三、遺傳算法中適值的調(diào)整為了使遺傳算法有效的工作，必須保持種群內(nèi)位串的多樣性和位串之間的競爭機(jī)制?，F(xiàn)將遺傳算法的運(yùn)行分為開始、中間和結(jié)束三個(gè)階段來考慮：在開始階段，若一個(gè)規(guī)模不太大的種群內(nèi)有少數(shù)非凡的個(gè)體(適值很高的位串)，按通常的選擇方法，這些個(gè)體會被大量的復(fù)制，在種群中占有大的比重，這樣就會減少種群的多樣性，導(dǎo)致多早收斂，從而可能丟失一些有意義的搜索點(diǎn)或最優(yōu)點(diǎn)，而進(jìn)入局部最優(yōu)；在結(jié)束階段，即使種群內(nèi)保持了很大的多樣性，但若所有或大多數(shù)個(gè)體都有很高的適值，從而種群的平均適值和最大值相差無幾，則平均適值附近的個(gè)體和具有最高適值的個(gè)體被選中的機(jī)會相同，這樣選擇就成了一個(gè)近乎隨機(jī)的步驟，適值的作用就會消失，從而使搜索性能得不到明顯的改進(jìn)。因此，有必要對種群內(nèi)各位串的適值進(jìn)行有效的調(diào)整，既不能相差太大，又要拉開檔次，強(qiáng)化位串之間的競爭性。1、窗口法它是一種簡單有效的適值調(diào)整方法，調(diào)整后的個(gè)體適值為Fj=f「(fmm-a)其中，fj為原來個(gè)體的適值；為每代種群中個(gè)體適值的最小值；a為一常數(shù)。在進(jìn)化的后期窗口法增加了個(gè)體之間的差異。2、函數(shù)歸一法該法是將個(gè)體適值轉(zhuǎn)換到最大值與最小值之間成一定比例的范圍之內(nèi)，這一范圍由選擇壓力ksp決定。具體步驟如下：根據(jù)給定的選擇壓力ksp,求種群中適值調(diào)整后的適值最小值為fmin+fmaxFmin=—1+ksp其中fmin和fmax是調(diào)整前種群個(gè)體適值的最小值和最大值。適值調(diào)整后種群中適值最大值為Fmax=kspFmin計(jì)算線性適值轉(zhuǎn)換的斜率為Fmax-Fmin△F=—fmax-fmin計(jì)算每個(gè)個(gè)體的新適值為Fj=Fmin+△F(fj-fmin)其中，fj為調(diào)整前第j個(gè)個(gè)體適值。在進(jìn)化的早期，函數(shù)歸一化法縮小了種群內(nèi)個(gè)體之間的差異，而在進(jìn)化的后期又適當(dāng)增大了性能相似個(gè)體之間的差異，加快了收斂速度。3、線性調(diào)整法線性調(diào)整法是一個(gè)有效的調(diào)整方法。設(shè)f是原個(gè)體適值，F(xiàn)是調(diào)整后個(gè)體的適值F=af+b，系數(shù)a、b可通過多種方法選取。不過，在任何情況下均要求Favg應(yīng)與favg相等，即應(yīng)滿足的條件為Favg=favg，fmax=CmultFavg，其中Cmult是最佳種群所要求的期望副本數(shù)，是一個(gè)經(jīng)驗(yàn)值，對于一個(gè)不大的種群來說，可能在1.2?2的范圍內(nèi)取值。正常條件下的線性調(diào)整方法如下圖正常條件下的線性調(diào)整法線性調(diào)整在遺傳算法的后期可能產(chǎn)生一個(gè)問題是，一些個(gè)體的適值遠(yuǎn)遠(yuǎn)小于平均適值與最大值，而往往平均適值與最大適值又十分接近，Cmult的這種選擇方法將原始適值函數(shù)伸展成負(fù)值，如下圖，解決的方法是，當(dāng)無法找到一個(gè)合適的Cmult時(shí)，保持Favg=favg，而將fmin映射到Fmin=0。四、高級遺傳算法的實(shí)現(xiàn)方法1、局部搜索算法局部搜索算法是從爬山法改進(jìn)而來的，設(shè)想要爬一座自己從未爬過的高山，目標(biāo)是爬到山頂，那么如何設(shè)計(jì)一種策略使得人們可以最快到達(dá)山頂呢？在一般情況下，如果沒有任何有關(guān)山頂?shù)钠渌畔?，沿著最陡的山坡向上爬，?yīng)該是一種不錯的選擇。這就是局部搜索算法中最基本的思想，即在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。當(dāng)然最優(yōu)解可以是求最大值，也可以是求最小值，二者思想是一樣的。在下面的討論中如果沒有特殊說明，均假設(shè)最優(yōu)解是最小值。局部搜索算法的一般過程是：隨機(jī)選擇一個(gè)初始的可能解x0ED，xb=x0,P=N(xb)；D是問題的定義域，xb用于記錄到目標(biāo)位置得到的最優(yōu)解，P為xb的領(lǐng)域。如果不滿足結(jié)束條件，則結(jié)束條件包括達(dá)到了規(guī)定的循環(huán)次數(shù)、P為空等。Begin選擇P的一個(gè)子集P’，xn為p’中的最優(yōu)解如果f(xn)<f(xb),則xb=xn,P=N(xb)，轉(zhuǎn)②；f(x)為指標(biāo)函數(shù)。否則P=P-P’，轉(zhuǎn)②。End輸出計(jì)算結(jié)果結(jié)束在算法第4步，選擇P的一個(gè)子集P’，可以根據(jù)問題的特點(diǎn)，選擇適當(dāng)大小的子集。極端情況下，可以選擇P’為P本身，或者是P的一個(gè)元素。后者情況下可以采用隨機(jī)選擇的方式從P中得到一個(gè)元素。設(shè)五城市旅行商問題如下圖所示，用局部搜索方法求解該問題。假設(shè)從城市a出發(fā)，我們用城市的序列表示該問題的一個(gè)可能解。設(shè)初始生成的可能解為：x0=（a,b,c,d,e）則根據(jù)各城市間的距離計(jì)算得到旅行商的旅行距離：f（xb）=f（x0）=38首先選擇兩個(gè)城市間的位置變換方式得到一個(gè)可能解的領(lǐng)域，并在算法的第④步選擇從p中隨機(jī)選擇一個(gè)元素的方法。則算法的執(zhí)行過程如下：P=｛（a,c,d,b,e）,（a,d,c,b,e）（a,e,c,d,b）,（a,b,d,c,e）,（a,b,e,d,c）,（a,b,c,e,d）｝第一次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，c，b，d，e），f（xn）=42,f（xn）＞f（xb），P=P-｛xn｝=｛（a，d，c，b，e），（a，e，c，d，b），（a，b，d，c，e），（a，b，e，d，c），（a，b，c，e，d）｝。第二次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，d，c，b，e），f（xn）=45,f（xn）＞f（xb），P=P-｛xn｝=｛（a，e，c，d，b），（a，b，c，d，e），（a，b，e，d，c），（a，b，c，e，d）｝。第三次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，e，c，d，b），f（xn）=44,f（xn）＞f（xb），P=P-｛xn｝=｛（a，b，d，c，e），（a，b，e，d，c），（a，b，c，e，d）｝。第四次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，b，d，c，e），f（xn）=44,f（xn）＞f（xb），P=P-｛xn｝=｛（a，b，e，d，c），（a，b，c，e，d）｝。第五次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，b，e，d，c），f（xn）=34，f（xn）＜f（xb），xb=（a，b，e，d，c），P=｛（a，e，b，d，c），（a，d，e，b，c），（a，c，e，d，b），（a，b，d，e，c），（a，b，c，d，e），（a，b，e，c，d）｝。第六次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，e，b，d，c），f（xn）=44,f（xn）＞f（xb），P=P-｛xn｝=｛（a，d，e，b，c），（a，c，e，d，b），（a，b，d，e，c），（a，b，c，d，e），（a，b，e，c，d）｝。第七次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，d，e，b，c），f（xn）=39,f（xn）＞f（xb），P=P-｛xn｝=｛（a，c，e，d，b），（a，b，d，e，c），（a，b，c，d，e），（a，b，e，c，d）｝。第八次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，c，e，d，b），f（xn）=38,f（xn）＞f（xb），P=P-｛xn｝=｛（a，b，d，e，c），（a，b，c，d，e），（a，b，e，c，d）｝。第九次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，b，d，e，c），f（xn）=38,f（xn）＞f（xb），P=P-｛xn｝=｛（a，b，c，d，e），（a，b，e，c，d）｝。第十次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，b，c，d，e），f（xn）=41，f（xn）＞f（xb），P=P-｛xn｝=｛（a，b，e，c，d）｝。第十一次循環(huán)：從P中隨機(jī)選擇一個(gè)元素，假設(shè)xn=（a，b，e，c，d），f（xn）=41，f（xn）＞f（xb），P=P-｛xn｝=｛｝。P等于空集，算法結(jié)束，得到結(jié)果為xb=（a，b，e，d，c），f（xb）=34。在該問題中，由于初始值（abcde）的指標(biāo)函數(shù)為38，已經(jīng)是一個(gè)比較不錯的結(jié)果了，在11次循環(huán)的搜索過程中，指標(biāo)函數(shù)只下降了一次，最終的結(jié)果指標(biāo)函數(shù)為34,這剛好是該問題的最優(yōu)解。從局部搜索的一般算法可以看出，該方法非常簡單，但也存在一些問題。一般情況下，并不能上上例那樣幸運(yùn)得到問題的最優(yōu)解。

2、模擬退火算法模擬退火算法是局部搜索算法的一種擴(kuò)展，該算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。作為求解復(fù)雜組合優(yōu)化問題的一種有效的方法，模擬退火算法已經(jīng)在許多工程和科學(xué)領(lǐng)域得到廣泛應(yīng)用。模擬退火算法是根據(jù)復(fù)雜組合優(yōu)化問題與固體的退火過程之間的相似之處，在它們之間建立聯(lián)系而提出來的。固體發(fā)熱退火過程是一種物理現(xiàn)象，屬于熱力學(xué)和統(tǒng)計(jì)物理學(xué)的研究范疇。當(dāng)對一個(gè)固體進(jìn)行加熱時(shí)，粒子的熱運(yùn)動不斷增加，隨著溫度的不斷上升，粒子逐漸脫離其平衡位置，變得越來越自由，直到達(dá)到固體的溶解溫度，粒子排列從原來的有序狀態(tài)變?yōu)橥耆臒o序狀態(tài)。這就是固體的溶解過程。退火過程與溶解過程剛好相反。隨著溫度的下降，粒子的熱運(yùn)動逐漸減弱，粒子逐漸停留在不同的狀態(tài)，其排列也從無序向著有序方向發(fā)展，直至到溫度很低時(shí)，粒子重新以一定的結(jié)構(gòu)排列。粒子不同的排列結(jié)構(gòu)，對應(yīng)著不同的能量水平。如果退火過程是緩慢進(jìn)行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個(gè)溫度下，粒子的排列都達(dá)到一種平衡態(tài)，則當(dāng)溫度趨于0時(shí)，系統(tǒng)的能量將趨于最小值。如果以粒子的排列或者相應(yīng)的能量來表達(dá)固體所處的狀態(tài)，則溫度T下，固體所處的狀態(tài)具有一定的隨機(jī)性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運(yùn)動又妨礙了系統(tǒng)準(zhǔn)確落入低能狀態(tài)。根據(jù)這一物理現(xiàn)象，Metropolis給出了從狀態(tài)i轉(zhuǎn)換為狀態(tài)j的準(zhǔn)則：如果E(j)WE(i)，則狀態(tài)轉(zhuǎn)換被接受；E。)-F.(j)如果E(j)>E(i)，則狀態(tài)轉(zhuǎn)移被接受的概率為：ekt，其中E(i)、E(j)分別表示在狀態(tài)i、j下的能量，T是溫度，K>0是波爾茲曼常數(shù)。Metropolis準(zhǔn)則表達(dá)了這樣一種現(xiàn)象：在溫度T下，系統(tǒng)處于某種狀態(tài)，由于粒子的運(yùn)動，系統(tǒng)的狀態(tài)發(fā)生微小的變化，并導(dǎo)致了系統(tǒng)能量的變化。如果這種變化使得系統(tǒng)的能量減少，則接受這種轉(zhuǎn)換；如果變換使得系統(tǒng)的能量增加，則以一定的概率接受這種轉(zhuǎn)換。在給定的溫度T下，當(dāng)進(jìn)行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達(dá)到熱平衡。此時(shí)系統(tǒng)處于某個(gè)狀態(tài)i的概率由Boltzmann分布給出：E(i)Pi(T)==，其中Z=Ze-K)為歸一化因子，S是所有可能狀態(tài)的集合。ZTIs在給定的溫度T下，設(shè)有i、j兩個(gè)狀態(tài)，E(i)<E(j)，則有：Pi(T)-Pi(T)-Pj(T)=Ei)Ej-—-—ektektZZTT_Ej上e-切(1—M)=ZEi)—Tekt1_W)(_E(j)—E(i)—ekt1—ektZT\JE(j)—E(i)由于E(i)vE(j)，所以e-kt<1所以有：所以有：Pi(T)—Pj(T)>0，即在任何溫度T下，

系統(tǒng)處于能量低的狀態(tài)的概率大于能量高的狀態(tài)的概率。當(dāng)溫度很高時(shí)有:_—ektE(i)_—eKTlim(Pi(T))=limTt0Tt0E(i)—E

m

e_—ektE(i)_—eKTlim(Pi(T))=limTt0Tt0E(i)—E

m

eKTy_四胃eKT'jeSm=limTT0E(i)-EmKTE(j^EmKT=limTT0^^EmektV_E(j)-EmyektjJm1「，如果ieSmSm0,如果i史Sm由上式可以看出，當(dāng)溫度趨近于0時(shí)，統(tǒng)處于其他狀態(tài)的概率為0。由于：系統(tǒng)以等概率趨近于幾個(gè)能量最小的狀態(tài)之一，而系E(i)E(i)dPi(T)5,e-kt、E(i)e-kt\o"CurrentDocument"=()\o"CurrentDocument"5T5TZTKT2ZZ2TT1v._Ej—乙E(j)ektElPi(T)-PTKT2ZKT2TjeSKT)(e①-ye(j)j))=PT)(e①-可)jeSe-ET奚=如Pi(T)-PT土5TKT2Z^5TE(j)

=m(e(i)-ye(j)w)

KT2ZjeST5T_|ye一#IlSl'jes/由上式可以看出，當(dāng)溫度很高時(shí)，系統(tǒng)處于各個(gè)狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關(guān)。當(dāng)溫度很低時(shí)則有：lim(Pi(T))=limlTt0T項(xiàng)|須-^^eKTj^sEm,.設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。上式分子、分母乘以e*有:其中：Et=ZE(j)Pj(T)是溫度T下，各狀態(tài)能量的期望值。由于Pi(T)、K、T均大于0，jeS5Pi(T)1>0.如果E(i)>E:5T|<0,如果E(i)<EkT由此可以看出，系統(tǒng)落入能量較低的狀態(tài)的概率是隨溫度T單調(diào)下降的，而系統(tǒng)落入高能量狀態(tài)的概率是隨溫度T單調(diào)上升的。也就是說，系統(tǒng)落入低能量狀態(tài)的概率隨著溫度的

下降單調(diào)上升，而系統(tǒng)落入高能量狀態(tài)的概率隨著溫度的下降單調(diào)下降?？偨Y(jié)可得出如下結(jié)論：在高溫下，系統(tǒng)基本處于無序狀態(tài)，基本以等概率落入各個(gè)狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于落入高能量狀態(tài)的概率。這樣在同一溫度下，如果系統(tǒng)交換得足夠充分，則系統(tǒng)會趨向于落入較低能量的狀態(tài)。隨著溫度的緩慢下降，系統(tǒng)落入低能量狀態(tài)的概率逐步增加，而落入高能量狀態(tài)的概率逐步減小，使得系統(tǒng)各狀態(tài)能量的期望值隨溫度的下降單調(diào)下降，而只有那些能量小于期望值的狀態(tài)，其概率才隨溫度下降增加，其他狀態(tài)均隨溫度下降而下降。因此，隨著能量期望值的逐步下降，能量低于期望值的狀態(tài)逐步減少，當(dāng)溫度趨于0時(shí)，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于0。因此最終系統(tǒng)將以概率1處于具有最小能量的一個(gè)狀態(tài)。固體退火過程，最終達(dá)到最小能量的一個(gè)狀態(tài)，從理論上來說，必須滿足以下3個(gè)條件:初始溫度必須足夠高；在每個(gè)溫度下，狀態(tài)的交換必須足夠充分;溫度T的下降必須足夠緩慢。受固體退火過程的啟發(fā)，Kirkpatrick等人意識到組合優(yōu)化問題與固體退火過程的類似性，將組合優(yōu)化問題類比為固體的退火過程，提出了求解組合優(yōu)化問題的模擬退貨算法。設(shè)一個(gè)定義在有限集S上的組合優(yōu)化問題，iES是該問題的一個(gè)解