遺傳算法概述

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

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

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

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

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

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

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

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

9、代種群之間沒有交疊(即若A(t)的規(guī)模為n,則在產(chǎn)生A(t+1)時，必須從A(t)中選n個位串進匹配集)，可以期望在復(fù)制完成后，在t+1時刻，特定模式H的數(shù)量為：m(H,t+1)=m(H,t)nf(H)/Ef.其中，f(H)是在t時刻對應(yīng)模式H的位串的平均適值，因為整個群的平均適值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)。從對復(fù)制的分析可以看到，雖然復(fù)制過程成功的以并行方式控制著模式數(shù)量以指數(shù)規(guī)模增減，但由于復(fù)制只是將某些高適值個體全盤

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

11、/6H2=*M0*,Pd=1/6模式H1定義長5(H1)=5，若交叉點始終是隨機地從1-1=7-1=6個可能的位置選取，則模式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在交叉中更容易受到破壞。一般情況下可以計算出任何模式的交叉存活概率的下限為在上面的討論中，均假設(shè)交叉的概率為1。若交叉的概率為Pc(即在選出進匹配集的一對位串上發(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ù)量變化取決于其平均適值的高低和定義長度的長短，f(H)越大，5(H)越小，則H的數(shù)量就越多。3、變異對模式的影響變異是對位串中的單個位置以概率Pm進行隨機替換，因而它可能破壞特定的模式。一個模式H要存活，意味著它所有的確定位置都存活。因此，由于單個位置的基因值存活的概率為1-Pm，而且由于每個變異的發(fā)生是統(tǒng)計獨立的，因此，一個特定模式僅當(dāng)它的0(H)個確定位置都存活是才存活，從而得到經(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é)論：定義長度短的、確定位數(shù)少的、平均適值高的模式數(shù)量將隨著代數(shù)的增加呈指數(shù)增長。這個結(jié)論稱為模式理論或遺傳算法基本定理。根據(jù)模式理論，隨著遺傳算法一代一代地進行，那些定義長度短的，位數(shù)少的，高適值的模式將越來越多，因而可期望最后得到的位串的性能越來越得到改善，并最終趨向全局最優(yōu)點。三

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

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

16、最小值和最大值。適值調(diào)整后種群中適值最大值為Fmax=kspFmin（2）計算線性適值轉(zhuǎn)換的斜率為Fmax-Fminf=fmax-fmin（3）計算每個個體的新適值為Fj=Fmin+F（fj-fmin）其中，fj為調(diào)整前第j個個體適值。在進化的早期，函數(shù)歸一化法縮小了種群內(nèi)個體之間的差異，而在進化的后期又適當(dāng)增大了性能相似個體之間的差異，加快了收斂速度。3、線性調(diào)整法線性調(diào)整法是一個有效的調(diào)整方法。設(shè)f是原個體適值，F(xiàn)是調(diào)整后個體的適值F=af+b，系數(shù)a、b可通過多種方法選取。不過，在任何情況下均要求Favg應(yīng)與favg相等，即應(yīng)滿足的條件為Favg=favg,fmax=CmultFavg,

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

18、達(dá)山頂呢在一般情況下，如果沒有任何有關(guān)山頂?shù)钠渌畔?，沿著最陡的山坡向上爬，?yīng)該是一種不錯的選擇。這就是局部搜索算法中最基本的思想，即在搜索過程中，始終向著離目標(biāo)最接近的方向搜索。當(dāng)然最優(yōu)解可以是求最大值，也可以是求最小值，二者思想是一樣的。在下面的討論中如果沒有特殊說明，均假設(shè)最優(yōu)解是最小值。局部搜索算法的一般過程是：隨機選擇一個初始的可能解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的一個子集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中隨機選擇一個元素，假設(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中隨機選擇一個元素，假設(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中隨機選擇一個元素，假設(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中隨機選擇一個元素，假設(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中隨機選擇一個元素，假設(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中隨機選擇一

21、個元素，假設(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中隨機選擇一個元素，假設(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中隨機選擇一個元素，假設(shè)xn=(a,b,c,d,e),f(xn)=41,f(xn)f(xb),P=Pxn=(a,b,e,c,d)。第十一次循環(huán)：從P中隨機選擇一個元素，假設(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)是一個比較不錯的結(jié)果了，在11次循環(huán)的搜索過程中,指標(biāo)函數(shù)只下降了一次,最終的結(jié)果指標(biāo)函數(shù)為34,這剛好是該問題的最優(yōu)解。從局部搜索的一般算法可以看出,該方法非常簡單,但也存在一些問題。一般情況下,并不能上上例那樣幸運得到問題的最優(yōu)解。2、模擬退火算法模擬退火算法是局部搜索算法的一種擴展，該算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優(yōu)化問題。作為求解復(fù)雜組合優(yōu)化問題的

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

24、的排列結(jié)構(gòu),對應(yīng)著不同的能量水平。如果退火過程是緩慢進行的,也就是說,溫度的下降如果非常緩慢的話,使得在每個溫度下,粒子的排列都達(dá)到一種平衡態(tài),則當(dāng)溫度趨于0時,系統(tǒng)的能量將趨于最小值。如果以粒子的排列或者相應(yīng)的能量來表達(dá)固體所處的狀態(tài)，則溫度T下，固體所處的狀態(tài)具有一定的隨機性。一方面，物理系統(tǒng)傾向于能量較低的狀態(tài)，另一方面，熱運動又妨礙了系統(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)，由于粒子的運動，系統(tǒng)的狀態(tài)發(fā)生微小的變化，并導(dǎo)致了系統(tǒng)能量的變化。如果這種變化使得系統(tǒng)的能量減少，則接受這種轉(zhuǎn)換；如果變換使得系統(tǒng)的能量增加，則以一定的概率接受這種轉(zhuǎn)換。在給定的溫度T下，當(dāng)進行足夠多次的狀態(tài)轉(zhuǎn)換后，系統(tǒng)將達(dá)到熱平衡。此時系統(tǒng)處于某個狀態(tài)i的概率由Boltzmann分布給出：F(i)ekt寸F(丿)Pi(T)=，其中Ze-kt為歸一化因子，S是所有可能狀態(tài)的集合。ZTTjes在給定的溫度T下，設(shè)有i、j兩個狀態(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)溫度很高時有：=，其中|S|表示系統(tǒng)所有可能的狀態(tài)數(shù)。Islim(Pi(T)=limTsTfgeKTy一3eKTjes由上式可以看出，當(dāng)溫度很高時，系統(tǒng)處于各個狀態(tài)的概率基本相等，接近于平均值，與所處狀態(tài)的能量幾乎無關(guān)。_E(DeKT當(dāng)溫度很低時則有：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時，系統(tǒng)以等概率趨近于幾個能量最小的狀態(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)基本處于無序狀態(tài)，基本以等概率落入各個狀態(tài)。在給定的溫度下，系統(tǒng)落入低能量狀態(tài)的概率大于落入高能

29、量狀態(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時，只剩下那些具有最小能量的狀態(tài)，系統(tǒng)處于其他狀態(tài)的概率趨近于0。因此最終系統(tǒng)將以概率1處于具有最小能量的一個狀態(tài)。固體退火過程，最終達(dá)到最小能量的一個狀態(tài)，從理論上來說，必須滿足以下3個條件：初始溫度必須足夠高；在每

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