遺傳算法概述

1、遺傳算法概述摘要：遺傳算法(geneticalgorithms,GA)是人工智能的重要新分支，是基于達(dá)爾文進(jìn)化論,在微型計(jì)算機(jī)上，模擬生命進(jìn)化機(jī)制而發(fā)展起來(lái)的一門學(xué)科。它根據(jù)適者生存、優(yōu)勝劣汰等自然進(jìn)化規(guī)則來(lái)進(jìn)行搜索計(jì)算機(jī)和問題求解。對(duì)許多用傳統(tǒng)數(shù)學(xué)難以解決或明顯失效的非常復(fù)雜的問題，特別是最優(yōu)化問題，GA提供了一個(gè)行之有效的新途徑。近年來(lái)，由于遺傳算法求解復(fù)雜優(yōu)化問題的巨大潛力及其在工業(yè)控制工程領(lǐng)域的成功應(yīng)用，這種算法受到了廣泛的關(guān)注。本文旨在闡述遺傳算法的基本原理、操作步驟和應(yīng)用中的一些基本問題，以及為了改善SGA的魯棒性而逐步發(fā)展形成的高級(jí)遺傳算法(refinegeneticalgori

2、thms,RGA)的實(shí)現(xiàn)方法。一、遺傳算法的基本原理和特點(diǎn)遺傳算法將生物進(jìn)化原理引入待優(yōu)化參數(shù)形成的編碼串群體中，按著一定的適值函數(shù)及一系列遺傳操作對(duì)各個(gè)體進(jìn)行篩選，從而使適值高的個(gè)體被保留下來(lái)，組成新的群體，新群體包含上一代的大量信息，并且引入了新一代的優(yōu)于上一代的個(gè)體。這樣周而復(fù)始，群體中各個(gè)體適值不斷提高，直至滿足一定的極限條件。此時(shí)，群體中適值最高的個(gè)體即為待優(yōu)化參數(shù)的最優(yōu)解。正是由于遺傳算法獨(dú)具特色的工作原理，使它能夠在復(fù)雜的空間進(jìn)行全局優(yōu)化搜索，并且具有較強(qiáng)的魯棒性；另外，遺傳算法對(duì)于搜索空間，基本上不需要什么限制性的假設(shè)(如連續(xù)性、可微及單峰等)。同常規(guī)優(yōu)化算法相比，遺傳算法有以

3、下特點(diǎn)。(1)遺傳算法是對(duì)參數(shù)編碼進(jìn)行操作，而非對(duì)參數(shù)本身。遺傳算法首先基于一個(gè)有限的字母表，把最優(yōu)化問題的自然參數(shù)集編碼為有線長(zhǎng)度的字符串。例如，一個(gè)最優(yōu)化問題：在整數(shù)區(qū)間【0,31】上求函數(shù)f(x)=x2的最大值。若采用傳統(tǒng)方法，需要不斷調(diào)節(jié)x參數(shù)的取值，直至得到最大的函數(shù)值為止。而采用遺傳算法，優(yōu)化過程的第一步的是把參數(shù)x編碼為有限長(zhǎng)度的字符串，常用二進(jìn)制字符串，設(shè)參數(shù)x的編碼長(zhǎng)度為5,“00000”代表0,“11111”代表31，在區(qū)間【0，31】上的數(shù)與二進(jìn)制編碼之間采用線性映射方法；隨機(jī)生成幾個(gè)這樣的字符串組成初始群體，對(duì)群體中的字符串進(jìn)行遺產(chǎn)操作，直至滿足一定的終止條件；求得最終

4、群體中適值最大的字符串對(duì)應(yīng)的十進(jìn)制數(shù)，其相應(yīng)的函數(shù)值則為所求解?？梢钥闯?，遺傳算法是對(duì)一個(gè)參數(shù)編碼群體進(jìn)行的操作，這樣提供的參數(shù)信息量大，優(yōu)化效果好。（2）遺傳算法是從許多點(diǎn)開始并行操作，并非局限于一點(diǎn)，從而可有效防止搜索過程收斂于局部最優(yōu)解。（3）遺傳算法通過目標(biāo)函數(shù)計(jì)算適值，并不需要其他推導(dǎo)和附加信息，因而對(duì)問題的依賴性較小。（4）遺傳算法的尋優(yōu)規(guī)則是由概率決定的，而非確定性的。（5）遺傳算法在解空間進(jìn)行高效啟發(fā)式搜索，而非盲目的窮舉或完全隨機(jī)搜索。（6）遺傳算法對(duì)求解的優(yōu)化問題沒有太多的數(shù)學(xué)要求。由于它的進(jìn)化特性，它在解的搜索中不需要了解問題的內(nèi)在性質(zhì)。遺傳算法可以處理任意形式的目標(biāo)函數(shù)

5、和約束，無(wú)論是線性的還是非線性的，離散的還是連續(xù)的，甚至是混合的搜索空間。（7）遺傳算法具有并行計(jì)算的特點(diǎn)，因而可通過大規(guī)模并行計(jì)算來(lái)提高計(jì)算速度。二、遺傳算法的模式理論1、模式一個(gè)模式（schemata）就是一個(gè)描述種群在位串的某些確定位置上具有相似性的一組符號(hào)串。為了描述一個(gè)模式，在用以表示位串的兩個(gè)字符0,1中加入一個(gè)通配符“*”，就構(gòu)成了一個(gè)表示模式用的3個(gè)字符的符號(hào)表0,1,*o因此用三個(gè)元素符號(hào)表0,1,*可以構(gòu)造出任意一種模式。當(dāng)一個(gè)模式與一個(gè)特定位串相匹配時(shí)，意味著該模式中的1與位串中的1相匹配,模式中的0與位串中的0相匹配,模式中的“*”與位串中的0或1相匹配。例如,模式00

6、*00匹配了兩個(gè)位串,即00100,00000；模式*111*可以和01110,01111,11110,11111中的任何一個(gè)相匹配；模式0*1*則匹配了長(zhǎng)度為5,第一位為0、第三位為1的八個(gè)位串,即00100,00101,00110,00111,01100,01101,01110,01111。模式的思路提供了一種簡(jiǎn)單而有效的方法,使能夠在有限符號(hào)表的基礎(chǔ)上討論有限長(zhǎng)位串的嚴(yán)謹(jǐn)定義的相似性。應(yīng)強(qiáng)調(diào)的是,“*”只是一個(gè)代表其他符號(hào)的一個(gè)元符號(hào),它不能被遺傳算法直接處理,但可以據(jù)此計(jì)算出所有可能的模式。一般地，假定符號(hào)表的基數(shù)是k,例如0,1的基數(shù)是2,則定義在該符號(hào)表上的長(zhǎng)度為丨的位串中，所有可

7、能包含的最大模式數(shù)為(k+l)1,原因是在l個(gè)位置中的任何一個(gè)位置上即可以取k個(gè)字符中的任何一個(gè)又可以取通配符“*”，即共有k+1個(gè)不同的表示，則l個(gè)位置的全排列數(shù)為(k+1)。例如,對(duì)長(zhǎng)度l=5,k=2(對(duì)應(yīng)0,1),則會(huì)有3X3X3X3X3=35=243=(k+l)i種不同的符號(hào)串，而位串的數(shù)量?jī)H為ki=25=32。可見，模式的數(shù)量要大于位串的數(shù)量。對(duì)于由0、1和*定義且長(zhǎng)度為l的符號(hào)串所能組成的最大模式數(shù)為(2+l)l。對(duì)于任一長(zhǎng)度為l的給定位串，當(dāng)任一位置上只有兩種不同表示時(shí)，所含模式數(shù)為2l個(gè)，因此對(duì)于含有n個(gè)位串個(gè)體的種群可能包含的模式數(shù)在2lnX2l之間。不難看出，遺產(chǎn)算法正是利

8、用種群中位串之間的眾多的相似性以及適值之間的相關(guān)性，來(lái)引導(dǎo)遺傳算法進(jìn)行有效地搜索。為了區(qū)分不同類型的模式,對(duì)模式H定義兩個(gè)量:模式位數(shù)(order)和模式的定義長(zhǎng)度(defininglength)分別表示為O(H)和5(H)。O(H)是H中有定義的非“*”位的個(gè)數(shù)，模式定義長(zhǎng)度(H)是指H中左右兩端有定義位置之間的距離。這兩個(gè)量為分析位串的相似性及分析遺傳操作對(duì)重要模式的影響提供了基本手段。2、復(fù)制對(duì)模式的影響設(shè)在給定時(shí)間(代)t,種群A(t)包含m個(gè)特定模式H,記為m=m(H，t)在復(fù)制過程中，A(t)中的任何一個(gè)位串A.以概率P.=f./Ef.被選中并進(jìn)行復(fù)制。假如選擇是有放回的抽樣，且兩

9、代種群之間沒有交疊(即若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)/Ef.其中，f(H)是在t時(shí)刻對(duì)應(yīng)模式H的位串的平均適值，因?yàn)檎麄€(gè)群的平均適值f=Efi/n,則上式又可寫為m(H,t+1)=m(H,t)f(H)經(jīng)過復(fù)制操作后，下一代中特定模式的數(shù)量H正比于所在位串的平均適值與種群平均適值的比值。若f(H)f，則H的數(shù)量將增加，若f(H)0)。從對(duì)復(fù)制的分析可以看到，雖然復(fù)制過程成功的以并行方式控制著模式數(shù)量以指數(shù)規(guī)模增減，但由于復(fù)制只是將某些高適值個(gè)體全盤

10、復(fù)制，或者淘汰某些低適值個(gè)體，而決不會(huì)產(chǎn)生新的模式結(jié)構(gòu)，因而性能的改進(jìn)是有限的。2、交叉對(duì)模式的影響交叉過程是位串之間有組織的隨機(jī)的信息交換。交叉操作對(duì)一個(gè)模式H的影響與模式的定義長(zhǎng)度S(H)有關(guān)，5(H)越大，模式H被分裂的可能性越大，因?yàn)榻徊娌僮饕S機(jī)選擇出進(jìn)行匹配的一對(duì)位串上的某一隨機(jī)位置進(jìn)行交叉。顯然5(H)越大，H的跨度就越大，隨機(jī)交叉點(diǎn)落入其中的可能性就越大，從而H的存活率就降低。例如位串長(zhǎng)度1=7,有如下包含兩個(gè)模式的位串A為A=01111000H1=*1*0,5(H1)=5H2=*10*,5(H2)=1隨機(jī)產(chǎn)生的交叉位置在3和4之間A=011M000H1=*1*M*0,Pd=5

11、/6H2=*M0*,Pd=1/6模式H1定義長(zhǎng)5(H1)=5，若交叉點(diǎn)始終是隨機(jī)地從1-1=7-1=6個(gè)可能的位置選取，則模式H1被破壞的概率為Pd=5(H1)/(l-1)=5/6它的存活概率為Ps=1-Pd=1/6類似的，模式H2的定義長(zhǎng)度5(H2)=1，它被破壞的概率為Pd=1/6，它存活的概率為Ps=1-Pd=5/6.因此，模式H1比模式H2在交叉中更容易受到破壞。一般情況下可以計(jì)算出任何模式的交叉存活概率的下限為在上面的討論中，均假設(shè)交叉的概率為1。若交叉的概率為Pc(即在選出進(jìn)匹配集的一對(duì)位串上發(fā)生交叉操作的概率)，則存活率為Ps1-Pcl1在復(fù)制交叉之后，模式的數(shù)量則為1m(H,t

12、+1)二m(H,tpf(H)Ps即m(H,t+1)m(H,tpf(H)因此，在復(fù)制和交叉的綜合作用之下，模式H的數(shù)量變化取決于其平均適值的高低和定義長(zhǎng)度的長(zhǎng)短，f(H)越大，5(H)越小，則H的數(shù)量就越多。3、變異對(duì)模式的影響變異是對(duì)位串中的單個(gè)位置以概率Pm進(jìn)行隨機(jī)替換，因而它可能破壞特定的模式。一個(gè)模式H要存活，意味著它所有的確定位置都存活。因此，由于單個(gè)位置的基因值存活的概率為1-Pm，而且由于每個(gè)變異的發(fā)生是統(tǒng)計(jì)獨(dú)立的，因此，一個(gè)特定模式僅當(dāng)它的0(H)個(gè)確定位置都存活是才存活，從而得到經(jīng)變異后，特定模式的存活率為(1-Pm)0(H),即(1-Pm)自乘0(H)次，由于一般情況下Pm1

13、,H的存活率可表示為(1-Pm)o(H)1-O(H)Pm綜合考慮復(fù)雜、交叉和變異操作的共同作用，則模式H在經(jīng)歷復(fù)制、交叉、變異操作之后，在下一代中的數(shù)量可表示為m(H,t+1)m(H,tpf1-Pc1-O(H)PmfLl-i也可近似表示為m(H,t+1)m(H,t1-Pc-0(H)PmfL1-1由上述分析可以得出結(jié)論：定義長(zhǎng)度短的、確定位數(shù)少的、平均適值高的模式數(shù)量將隨著代數(shù)的增加呈指數(shù)增長(zhǎng)。這個(gè)結(jié)論稱為模式理論或遺傳算法基本定理。根據(jù)模式理論，隨著遺傳算法一代一代地進(jìn)行，那些定義長(zhǎng)度短的，位數(shù)少的，高適值的模式將越來(lái)越多，因而可期望最后得到的位串的性能越來(lái)越得到改善，并最終趨向全局最優(yōu)點(diǎn)。三

14、、遺傳算法中適值的調(diào)整為了使遺傳算法有效的工作，必須保持種群內(nèi)位串的多樣性和位串之間的競(jìng)爭(zhēng)機(jī)制。現(xiàn)將遺傳算法的運(yùn)行分為開始、中間和結(jié)束三個(gè)階段來(lái)考慮：在開始階段，若一個(gè)規(guī)模不太大的種群內(nèi)有少數(shù)非凡的個(gè)體(適值很高的位串)，按通常的選擇方法，這些個(gè)體會(huì)被大量的復(fù)制，在種群中占有大的比重，這樣就會(huì)減少種群的多樣性，導(dǎo)致多早收斂，從而可能丟失一些有意義的搜索點(diǎn)或最優(yōu)點(diǎn)，而進(jìn)入局部最優(yōu)；在結(jié)束階段，即使種群內(nèi)保持了很大的多樣性但若所有或大多數(shù)個(gè)體都有很高的適值，從而種群的平均適值和最大值相差無(wú)幾，則平均適值附近的個(gè)體和具有最高適值的個(gè)體被選中的機(jī)會(huì)相同，這樣選擇就成了一個(gè)近乎隨機(jī)的步驟，適值的作用就會(huì)

15、消失，從而使搜索性能得不到明顯的改進(jìn)。因此，有必要對(duì)種群內(nèi)各位串的適值進(jìn)行有效的調(diào)整，既不能相差太大，又要拉開檔次，強(qiáng)化位串之間的競(jìng)爭(zhēng)性。1、窗口法它是一種簡(jiǎn)單有效的適值調(diào)整方法，調(diào)整后的個(gè)體適值為Fj=fj-(fmin-a)其中，fj為原來(lái)個(gè)體的適值；為每代種群中個(gè)體適值的最小值；a為一常數(shù)。在進(jìn)化的后期窗口法增加了個(gè)體之間的差異。2、函數(shù)歸一法該法是將個(gè)體適值轉(zhuǎn)換到最大值與最小值之間成一定比例的范圍之內(nèi)，這一范圍由選擇壓力ksp決定。具體步驟如下：（1）根據(jù)給定的選擇壓力ksp,求種群中適值調(diào)整后的適值最小值為fmin+fmaxFmm=1+ksp其中fmin和fmax是調(diào)整前種群個(gè)體適值的

16、最小值和最大值。適值調(diào)整后種群中適值最大值為Fmax=kspFmin（2）計(jì)算線性適值轉(zhuǎn)換的斜率為Fmax-Fminf=fmax-fmin（3）計(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,

17、其中Cmult是最佳種群所要求的期望副本數(shù)，是一個(gè)經(jīng)驗(yàn)值，對(duì)于一個(gè)不大的種群來(lái)說，可能在2的范圍內(nèi)取值。正常條件下的線性調(diào)整方法如下圖正常條件下的線性調(diào)整法線性調(diào)整在遺傳算法的后期可能產(chǎn)生一個(gè)問題是，一些個(gè)體的適值遠(yuǎn)遠(yuǎn)小于平均適值與最大值，而往往平均適值與最大適值又十分接近，Cmult的這種選擇方法將原始適值函數(shù)伸展成負(fù)值，如下圖，解決的方法是，當(dāng)無(wú)法找到一個(gè)合適的Cmult時(shí)，保持Favg=favg,而將fmin映射到Fmin=0。四、高級(jí)遺傳算法的實(shí)現(xiàn)方法1、局部搜索算法局部搜索算法是從爬山法改進(jìn)而來(lái)的，設(shè)想要爬一座自己從未爬過的高山，目標(biāo)是爬到山頂，那么如何設(shè)計(jì)一種策略使得人們可以最快到

18、達(dá)山頂呢在一般情況下，如果沒有任何有關(guān)山頂?shù)钠渌畔ⅲ刂疃傅纳狡孪蛏吓?，?yīng)該是一種不錯(cuò)的選擇。這就是局部搜索算法中最基本的思想，即在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。當(dāng)然最優(yōu)解可以是求最大值，也可以是求最小值，二者思想是一樣的。在下面的討論中如果沒有特殊說明，均假設(shè)最優(yōu)解是最小值。局部搜索算法的一般過程是：隨機(jī)選擇一個(gè)初始的可能解xOWD,xb=xO,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),P=P

19、-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,

20、d,c,e),f(xn)=44,f(xn)f(xb),P=P-xn=(a,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),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,e,d,b),(a,b,d,e,c),(a,b,c,d,e),(a,b,e,c,d)。第八次循環(huán)：從P中隨機(jī)選擇一

21、個(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=Pxn=(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=Pxn=(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=

22、Pxn=。P等于空集,算法結(jié)束,得到結(jié)果為xb=(a,b,e,d,c),f(xb)=34。在該問題中，由于初始值(abcde)的指標(biāo)函數(shù)為38，已經(jīng)是一個(gè)比較不錯(cuò)的結(jié)果了，在11次循環(huán)的搜索過程中,指標(biāo)函數(shù)只下降了一次,最終的結(jié)果指標(biāo)函數(shù)為34,這剛好是該問題的最優(yōu)解。從局部搜索的一般算法可以看出,該方法非常簡(jiǎn)單,但也存在一些問題。一般情況下,并不能上上例那樣幸運(yùn)得到問題的最優(yōu)解。2、模擬退火算法模擬退火算法是局部搜索算法的一種擴(kuò)展，該算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。作為求解復(fù)雜組合優(yōu)化問題的

23、一種有效的方法,模擬退火算法已經(jīng)在許多工程和科學(xué)領(lǐng)域得到廣泛應(yīng)用。模擬退火算法是根據(jù)復(fù)雜組合優(yōu)化問題與固體的退火過程之間的相似之處,在它們之間建立聯(lián)系而提出來(lái)的。固體發(fā)熱退火過程是一種物理現(xiàn)象,屬于熱力學(xué)和統(tǒng)計(jì)物理學(xué)的研究范疇。當(dāng)對(duì)一個(gè)固體進(jìn)行加熱時(shí),粒子的熱運(yùn)動(dòng)不斷增加,隨著溫度的不斷上升,粒子逐漸脫離其平衡位置,變得越來(lái)越自由,直到達(dá)到固體的溶解溫度,粒子排列從原來(lái)的有序狀態(tài)變?yōu)橥耆臒o(wú)序狀態(tài)。這就是固體的溶解過程。退火過程與溶解過程剛好相反。隨著溫度的下降,粒子的熱運(yùn)動(dòng)逐漸減弱,粒子逐漸停留在不同的狀態(tài),其排列也從無(wú)序向著有序方向發(fā)展,直至到溫度很低時(shí),粒子重新以一定的結(jié)構(gòu)排列。粒子不同

24、的排列結(jié)構(gòu),對(duì)應(yīng)著不同的能量水平。如果退火過程是緩慢進(jìn)行的,也就是說,溫度的下降如果非常緩慢的話,使得在每個(gè)溫度下,粒子的排列都達(dá)到一種平衡態(tài),則當(dāng)溫度趨于0時(shí),系統(tǒng)的能量將趨于最小值。如果以粒子的排列或者相應(yīng)的能量來(lái)表達(dá)固體所處的狀態(tài)，則溫度T下，固體所處的狀態(tài)具有一定的隨機(jī)性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運(yùn)動(dòng)又妨礙了系統(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

25、是溫度，K0是波爾茲曼常數(shù)。Metropolis準(zhǔn)則表達(dá)了這樣一種現(xiàn)象：在溫度T下，系統(tǒng)處于某種狀態(tài)，由于粒子的運(yùn)動(dòng)，系統(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分布給出：F(i)ekt寸F(丿)Pi(T)=，其中Ze-kt為歸一化因子，S是所有可能狀態(tài)的集合。ZTTjes在給定的溫度T下，設(shè)有i、j兩個(gè)狀態(tài)，E(i)E(j)，則有：ektekt1-F(i)ekt1(F(j)

26、F(i)Pi(T)-Pj(T)二二e-kt(1-)二e-kt1-e-ktZZZ3ZI丿TTTeKTT-F(j)-F(i)由于E(i)E(j)，所以ekt0，即在任何溫度T下，系統(tǒng)處于能量低的狀態(tài)的概率大于能量高的狀態(tài)的概率。當(dāng)溫度很高時(shí)有：=，其中|S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。Islim(Pi(T)=limTsTfgeKTy一3eKTjes由上式可以看出，當(dāng)溫度很高時(shí)，系統(tǒng)處于各個(gè)狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無(wú)關(guān)。_E(DeKT當(dāng)溫度很低時(shí)則有：lim(Pi(T)=limTtoTto|V_EjeKTjwS-Em設(shè)Sm表示系統(tǒng)最小能量狀態(tài)的集合，Em是系統(tǒng)的最小能量。

27、上式分子、分母乘以e弄有:lim(Pi(T)=limTtOTtOE(i)EmeKTVeKT=limTtOE(i)EmeKTVEmeKTE(i)EeKT/VE(/)E八mektjeSm丿=limTtOjeSmjeSmE(j_EmKT丿J，如果ieSmS0,如果i電Sm由上式可以看出，當(dāng)溫度趨近于0時(shí)，系統(tǒng)以等概率趨近于幾個(gè)能量最小的狀態(tài)之一，而系統(tǒng)處于其他狀態(tài)的概率為0。由于：E(i)E(i)1中QZE(i)D、Pi(T)QZeKTT二Pl(l)TKT2ZZ2QTKT2ZQTTTTE(j)也(E(i)VE(j)亠)KT2ZjeSTQPi(T)QE(i)=()QTQTZT型Pi(T)P(T)KT2

28、ZKT2TjeSPT(E(i)VE(j)Pj(T)二PT(E(i)可)KT2KT2TjeS其中：E=VE(j)Pj(T)是溫度T下，各狀態(tài)能量的期望值。由于Pi(T)、K、T均大于0，TjeSQPi(T)J0.如果E(i)E:QT0,如果E(i)ET由此可以看出，系統(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)基本處于無(wú)序狀態(tài)，基本以等概率落入各個(gè)狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于落入高能

29、量狀態(tài)的概率。這樣在同一溫度下，如果系統(tǒng)交換得足夠充分，則系統(tǒng)會(huì)趨向于落入較低能量的狀態(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)，從理論上來(lái)說，必須滿足以下3個(gè)條件：初始溫度必須足夠高；在每

30、個(gè)溫度下，狀態(tài)的交換必須足夠充分；溫度T的下降必須足夠緩慢。受固體退火過程的啟發(fā)，Kirkpatrick等人意識(shí)到組合優(yōu)化問題與固體退火過程的類似性，將組合優(yōu)化問題類比為固體的退火過程，提出了求解組合優(yōu)化問題的模擬退貨算法。設(shè)一個(gè)定義在有限集S上的組合優(yōu)化問題，iS是該問題的一個(gè)解，f(i)是解i的指標(biāo)函數(shù)。由組合優(yōu)化問題與退火過程的類比關(guān)系，i對(duì)應(yīng)物理系統(tǒng)的一個(gè)狀態(tài)，f(i)對(duì)應(yīng)該狀態(tài)的能量E(i),個(gè)用于控制算法的進(jìn)程、其值隨算法進(jìn)程遞減的控制參數(shù)t對(duì)應(yīng)固體退火中的溫度T，粒子的熱運(yùn)動(dòng)則用解在領(lǐng)域中的交換來(lái)代替。這樣就將一個(gè)組合優(yōu)化問題與固體退火過程建立了聯(lián)系。在求解組合優(yōu)化問題時(shí)，首先給定一個(gè)比