遺傳算法概述摘要：遺傳算法（geneticalgorithms,GA）是人工智能的重要新分支，是基于達爾文進化論，在微型計算機上，模擬生命進化機制而發展起來的一門學科。它根據適者生存、優勝劣汰等自然進化規則來進行搜索計算機和問題求解。對許多用傳統數學難以解決或明顯失效的非常復雜的問題，特別是最優化問題，GA提供了一種行之有效的新途徑。近年來，由于遺傳算法求解復雜優化問題的巨大潛力及其在工業控制工程領域的成功應用，這種算法受到了廣泛的關注。本文旨在敘述遺傳算法的基本原理、操作環節和應用中的某些基本問題，以及為了改善SGA的魯棒性而逐步發展形成的高級遺傳算法（refinegeneticalgorithms,RGA）的實現辦法。遺傳算法的基本原理和特點遺傳算法將生物進化原理引入待優化參數形成的編碼串群體中，按著一定的適值函數及一系列遺傳操作對各個體進行篩選，從而使適值高的個體被保存下來，構成新的群體，新群體包含上一代的大量信息，并且引入了新一代的優于上一代的個體。這樣周而復始，群體中各個體適值不停提高，直至滿足一定的極限條件。此時，群體中適值最高的個體即為待優化參數的最優解。正是由于遺傳算法獨具特色的工作原理，使它能夠在復雜的空間進行全局優化搜索，并且含有較強的魯棒性；另外，遺傳算法對于搜索空間，基本上不需要什么限制性的假設（如持續性、可微及單峰等）。同常規優化算法相比，遺傳算法有下列特點。遺傳算法是對參數編碼進行操作，而非對參數本身。遺傳算法首先基于一種有限的字母表，把最優化問題的自然參數集編碼為有線長度的字符串。例如，一種最優化問題：在整數區間【0，31】上求函數f(x)=x2的最大值。若采用傳統辦法，需要不停調節x參數的取值，直至得到最大的函數值為止。而采用遺傳算法，優化過程的第一步的是把參數x編碼為有限長度的字符串，慣用二進制字符串，設參數x的編碼長度為5，“00000”代表0，“11111”代表31，在區間【0，31】上的數與二進制編碼之間采用線性映射辦法；隨機生成幾個這樣的字符串構成初始群體，對群體中的字符串進行遺產操作，直至滿足一定的終止條件；求得最后群體中適值最大的字符串對應的十進制數，其對應的函數值則為所求解。能夠看出，遺傳算法是對一種參數編碼群體進行的操作，這樣提供的參數信息量大，優化效果好。遺傳算法是從許多點開始并行操作，并非局限于一點，從而可有效避免搜索過程收斂于局部最優解。遺傳算法通過目的函數計算適值，并不需要其它推導和附加信息，因而對問題的依賴性較小。遺傳算法的尋優規則是由概率決定的，而非擬定性的。遺傳算法在解空間進行高效啟發式搜索，而非盲目的窮舉或完全隨機搜索。遺傳算法對求解的優化問題沒有太多的數學規定。由于它的進化特性，它在解的搜索中不需要理解問題的內在性質。遺傳算法能夠解決任意形式的目的函數和約束，無論是線性的還是非線性的，離散的還是持續的，甚至是混合的搜索空間。遺傳算法含有并行計算的特點，因而可通過大規模并行計算來提高計算速度。遺傳算法的模式理論模式一種模式（schemata）就是一種描述種群在位串的某些擬定位置上含有相似性的一組符號串。為了描述一種模式，在用以表達位串的兩個字符｛0，1｝中加入一種通配符“*”，就構成了一種表達模式用的3個字符的符號表｛0，1，*｝。因此用三個元素符號表｛0，1，*｝能夠構造出任意一種模式。當一種模式與一種特定位串相匹配時，意味著該模式中的1與位串中的1相匹配，模式中的0與位串中的0相匹配，模式中的“*”與位串中的0或1相匹配。例如，模式00*00匹配了兩個位串，即｛00100，00000｝；模式*111*能夠和｛01110，01111，11110，11111｝中的任何一種相匹配；模式0*1**則匹配了長度為5，第一位為0、第三位為1的八個位串，即｛00100，00101，00110，00111，01100，01101，01110，01111｝。模式的思路提供了一種簡樸而有效的辦法，使能夠在有限符號表的基礎上討論有限長位串的嚴謹定義的相似性。應強調的是，“*”只是一種代表其它符號的一種元符號，它不能被遺傳算法直接解決，但能夠據此計算出全部可能的模式。普通地，假定符號表的基數是k，例如｛0，1｝的基數是2，則定義在該符號表上的長度為l的位串中，全部可能包含的最大模式數為（k+l）l,因素是在l個位置中的任何一種位置上即能夠取k個字符中的任何一種又能夠取通配符“*”，即共有k+l個不同的表達，則l個位置的全排列數為（k+l）l。例如，對長度l=5,k=2(對應0，1)，則會有3×3×3×3×3=35=243=（k+l）l種不同的符號串，而位串的數量僅為kl=25=32?？梢姡Ｊ降臄盗恳徊淮笥谖淮臄盗?。對于由0、1和*定義且長度為l的符號串所能構成的最大模式數為（2+l）l。對于任一長度為l的給定位串，當任一位置上只有兩種不同表達時，所含模式數為2l個，因此對于含有n個位串個體的種群可能包含的模式數在2l~n×2l之間。不難看出，遺產算法正是運用種群中位串之間的眾多的相似性以及適值之間的有關性，來引導遺傳算法進行有效地搜索。為了分辨不同類型的模式，對模式H定義兩個量：模式位數（order）和模式的定義長度（defininglength）分別表達為O(H)和(H)。O(H)是H中有定義的非“*”位的個數，模式定義長度(H)是指H中左右兩端有定義位置之間的距離。這兩個量為分析位串的相似性及分析遺傳操作對重要模式的影響提供了基本手段。2、復制對模式的影響設在給定時間（代）t，種群A（t）包含m個特定模式H，記為m=m(H，t)在復制過程中，A（t）中的任何一種位串Ai以概率Pi=fi/∑fi被選中并進行復制。如果選擇是有放回的抽樣，且兩代種群之間沒有交疊（即若A（t）的規模為n，則在產生A（t+1）時，必須從A（t）中選n個位串進匹配集），能夠盼望在復制完畢后，在t+1時刻，特定模式H的數量為：m(H,t+1)=m(H,t)nf(H)/∑fi其中，f(H)是在t時刻對應模式H的位串的平均適值，由于整個群的平均適值f=∑fi/n,則上式又可寫為m(H,t+1)=m(H,t)通過復制操作后，下一代中特定模式的數量H正比于所在位串的平均適值與種群平均適值的比值。若f(H)>,則H的數量將增加，若f(H)<，則H的數量將減少。即若包含H的個體位串的平均適值高于現在種群中全部個體位串的平均適值，則種群包含特模式的下一代中的數量將增加；反之，減少。操作中模式的增減在復制中是并行的，這恰恰體現了遺傳算法隱含的并行性。為了進一步分析高于平均適值的模式數量的增加，假設（c是一種不不大于零的常數），則上式可寫為：從原始種群開始（t=0），并假定是一種穩態的值，則有t可見，對于高于平均適值的模式數量將按指數規律增加（c>0）。從對復制的分析能夠看到，即使復制過程成功的以并行方式控制著模式數量以指數規模增減，但由于復制只是將某些高適值個體全盤復制，或者裁減某些低適值個體，而決不會產生新的模式構造，因而性能的改善是有限的。交叉對模式的影響交叉過程是位串之間有組織的隨機的信息交換。交叉操作對一種模式H的影響與模式的定義長度(H)有關，(H)越大，模式H被分裂的可能性越大，由于交叉操作要隨機選擇出進行匹配的一對位串上的某一隨機位置進行交叉。顯然(H)越大，H的跨度就越大，隨機交叉點落入其中的可能性就越大，從而H的存活率就減少。例如位串長度l=7，有以下包含兩個模式的位串A為A=01111000H1=*1****0,(H1)=5H2=***10**,(H2)=1隨機產生的交叉位置在3和4之間A=H1=,Pd=5/6H2=,Pd=1/6模式H1定義長(H1)=5，若交叉點始終是隨機地從l-1=7-1=6個可能的位置選用，則模式H1被破壞的概率為Pd=(H1)/(l-1)=5/6它的存活概率為Ps=1-Pd=1/6類似的，模式H2的定義長度(H2)=1，它被破壞的概率為Pd=1/6,它存活的概率為Ps=1-Pd=5/6.因此，模式H1比模式H2在交叉中更容易受到破壞。普通狀況下能夠計算出任何模式的交叉存活概率的下限為Ps在上面的討論中，均假設交叉的概率為1。若交叉的概率為Pc(即在選出進匹配集的一對位串上發生交叉操作的概率)，則存活率為Ps在復制交叉之后，模式的數量則為即因此，在復制和交叉的綜合作用之下，模式H的數量變化取決于其平均適值的高低和定義長度的長短，f(H)越大，(H)越小，則H的數量就越多。變異對模式的影響變異是對位串中的單個位置以概率Pm進行隨機替代，因而它可能破壞特定的模式。一種模式H要存活，意味著它全部的擬定位置都存活。因此，由于單個位置的基因值存活的概率為1-Pm，并且由于每個變異的發生是統計獨立的，因此，一種特定模式僅當它的O（H）個擬定位置都存活是才存活，從而得到經變異后，特定模式的存活率為（1-Pm）O(H),即（1-Pm）自乘O(H)次，由于普通狀況下Pm<<1,H的存活率可表達為（1-Pm）O(H)≈1-O(H)Pm綜合考慮復雜、交叉和變異操作的共同作用，則模式H在經歷復制、交叉、變異操作之后，在下一代中的數量可表達為也可近似表達為由上述分析能夠得出結論：定義長度短的、擬定位數少的、平均適值高的模式數量將隨著代數的增加呈指數增加。這個結論稱為模式理論或遺傳算法基本定理。根據模式理論，隨著遺傳算法一代一代地進行，那些定義長度短的，位數少的，高適值的模式將越來越多，因而可盼望最后得到的位串的性能越來越得到改善，并最后趨向全局最優點。遺傳算法中適值的調節為了使遺傳算法有效的工作，必須保持種群內位串的多樣性和位串之間的競爭機制?，F將遺傳算法的運行分為開始、中間和結束三個階段來考慮：在開始階段，若一種規模不太大的種群內有少數不凡的個體（適值很高的位串），按普通的選擇辦法，這些個體會被大量的復制，在種群中占有大的比重，這樣就會減少種群的多樣性，造成多早收斂，從而可能丟失某些故意義的搜索點或最優點，而進入局部最優；在結束階段，即使種群內保持了很大的多樣性，但若全部或大多數個體都有很高的適值，從而種群的平均適值和最大值相差無幾，則平均適值附近的個體和含有最高適值的個體被選中的機會相似，這樣選擇就成了一種近乎隨機的環節，適值的作用就會消失，從而使搜索性能得不到明顯的改善。因此，有必要對種群內各位串的適值進行有效的調節，既不能相差太大，又要拉開檔次，強化位串之間的競爭性。窗口法它是一種簡樸有效的適值調節辦法，調節后的個體適值為Fj=fj-(fmin-a)其中，fj為原來個體的適值；為每代種群中個體適值的最小值；a為一常數。在進化的后期窗口法增加了個體之間的差別。函數歸一法該法是將個體適值轉換到最大值與最小值之間成一定比例的范疇之內，這一范疇由選擇壓力ksp決定。具體環節以下：根據給定的選擇壓力ksp,求種群中適值調節后的適值最小值為其中fmin和fmax是調節前種群個體適值的最小值和最大值。適值調節后種群中適值最大值為Fmax=kspFmin計算線性適值轉換的斜率為△F=（3）計算每個個體的新適值為△其中，fj為調節前第j個個體適值。在進化的早期，函數歸一化法縮小了種群內個體之間的差別，而在進化的后期又適宜增大了性能相似個體之間的差別，加緊了收斂速度。線性調節法線性調節法是一種有效的調節辦法。設f是原個體適值，F是調節后個體的適值F=af+b，系數a、b可通過多個辦法選用。但是，在任何狀況下均規定Favg應與favg相等，即應滿足的條件為Favg=favg，fmax=CmultFavg，其中Cmult是最佳種群所規定的盼望副本數，是一種經驗值，對于一種不大的種群來說，可能在~2的范疇內取值。正常條件下的線性調節辦法以下圖正常條件下的線性調節正常條件下的線性調節法線性調節在遺傳算法的后期可能產生一種問題是，某些個體的適值遠遠不大于平均適值與最大值，而往往平均適值與最大適值又十分靠近，Cmult的這種選擇辦法將原始適值函數伸展成負值，以下圖，解決的辦法是，當無法找到一種適宜的Cmult時，保持Favg=favg，而將fmin映射到Fmin=0。線性映射辦法之一線性映射辦法之一高級遺傳算法的實現辦法局部搜索算法局部搜索算法是從爬山法改善而來的，構想要爬一座自己從未爬過的高山，目的是爬到山頂，那么如何設計一種方略使得人們能夠最快達成山頂呢在普通狀況下，如果沒有任何有關山頂的其它信息，沿著最陡的山坡向上爬，應當是一種不錯的選擇。這就是局部搜索算法中最基本的思想，即在搜索過程中，始終向著離目的最靠近的方向搜索。固然最優解能夠是求最大值，也能夠是求最小值，兩者思想是同樣的。在下面的討論中如果沒有特殊闡明，均假設最優解是最小值。局部搜索算法的普通過程是：隨機選擇一種初始的可能解x0∈D，xb=x0,P=N(xb)；D是問題的定義域，xb用于統計到目的位置得到的最優解，P為xb的領域。如果不滿足結束條件，則結束條件涉及達成了規定的循環次數、P為空等。Begin選擇P的一種子集P’,xn為p’中的最優解如果f(xn)<f(xb),則xb=xn,P=N(xb),轉②；f(x)為指標函數。否則P=P-P’,轉②。End輸出計算成果結束在算法第4步，選擇P的一種子集P’，能夠根據問題的特點，選擇適宜大小的子集。極端狀況下，能夠選擇P’為P本身，或者是P的一種元素。后者狀況下能夠采用隨機選擇的方式從P中得到一種元素。設五都市旅行商問題以下圖所示，用局部搜索辦法求解該問題。假設從都市a出發，我們用都市的序列表達該問題的一種可能解。設初始生成的可能解為：x0=（a,b,c,d,e）則根據各都市間的距離計算得到旅行商的旅行距離：f(xb)=f(x0)=38首先選擇兩個都市間的位置變換方式得到一種可能解的領域，并在算法的第④步選擇從p中隨機選擇一種元素的辦法。則算法的執行過程以下：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)}第一次循環：從P中隨機選擇一種元素，假設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)}。第二次循環：從P中隨機選擇一種元素，假設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)}。第三次循環：從P中隨機選擇一種元素，假設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)}。第四次循環：從P中隨機選擇一種元素，假設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)}。第五次循環：從P中隨機選擇一種元素，假設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)}。第六次循環：從P中隨機選擇一種元素，假設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)}。第七次循環：從P中隨機選擇一種元素，假設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)}。第八次循環：從P中隨機選擇一種元素，假設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)}。第九次循環：從P中隨機選擇一種元素，假設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)}。第十次循環：從P中隨機選擇一種元素，假設xn=(a，b，c，d，e)，f(xn)=41，f(xn)>f(xb)，P=P-{xn}={(a，b，e，c，d)}。第十一次循環：從P中隨機選擇一種元素，假設xn=(a，b，e，c，d)，f(xn)=41，f(xn)>f(xb)，P=P-{xn}={}。P等于空集，算法結束，得到成果為xb=(a，b，e，d，c)，f(xb)=34。在該問題中，由于初始值(abcde)的指標函數為38，已經是一種比較不錯的成果了，在11次循環的搜索過程中，指標函數只下降了一次，最后的成果指標函數為34，這剛好是該問題的最優解。從局部搜索的普通算法能夠看出，該辦法非常簡樸，但也存在某些問題。普通狀況下，并不能上上例那樣幸運得到問題的最優解。模擬退火算法模擬退火算法是局部搜索算法的一種擴展，該算法的思想最早由Metropolis在1953年提出，Kirkpatrick等人在1983年成功地將模擬退火算法用于求解組合優化問題。作為求解復雜組合優化問題的一種有效的辦法，模擬退火算法已經在許多工程和科學領域得到廣泛應用。模擬退火算法是根據復雜組合優化問題與固體的退火過程之間的相似之處，在它們之間建立聯系而提出來的。固體發熱退火過程是一種物理現象，屬于熱力學和統計物理學的研究范疇。當對一種固體進行加熱時，粒子的熱運動不停增加，隨著溫度的不停上升，粒子逐步脫離其平衡位置，變得越來越自由，直達成到固體的溶解溫度，粒子排列從原來的有序狀態變為完全的無序狀態。這就是固體的溶解過程。退火過程與溶解過程剛好相反。隨著溫度的下降，粒子的熱運動逐步削弱，粒子逐步停留在不同的狀態，其排列也從無序向著有序方向發展，直至到溫度很低時，粒子重新以一定的構造排列。粒子不同的排列構造，對應著不同的能量水平。如果退火過程是緩慢進行的，也就是說，溫度的下降如果非常緩慢的話，使得在每個溫度下，粒子的排列都達成一種平衡態，則當溫度趨于0時，系統的能量將趨于最小值。如果以粒子的排列或者對應的能量來體現固體所處的狀態，則溫度T下，固體所處的狀態含有一定的隨機性。首先，物理系統傾向于能量較低的狀態，另首先，熱運動又妨礙了系統精確落入低能狀態。根據這一物理現象，Metropolis給出了從狀態i轉換為狀態j的準則：如果E(j)≤E(i)，則狀態轉換被接受；如果E(j)＞E(i)，則狀態轉移被接受的概率為：，其中E(i)、E(j)分別表達在狀態i、j下的能量，T是溫度，K>0是波爾茲曼常數。Metropolis準則體現了這樣一種現象：在溫度T下，系統處在某種狀態，由于粒子的運動，系統的狀態發生微小的變化，并造成了系統能量的變化。如果這種變化使得系統的能量減少，則接受這種轉換；如果變換使得系統的能量增加，則以一定的概率接受這種轉換。在給定的溫度T下，當進行足夠多次的狀態轉換后，系統將達成熱平衡。此時系統處在某個狀態i的概率由Boltzmann分布給出：，其中為歸一化因子，S是全部可能狀態的集合。在給定的溫度T下，設有i、j兩個狀態，E(i)<E(j)，則有：由于，因此因此有：，即在任何溫度T下，系統處在能量低的狀態的概率不不大于能量高的狀態的概率。當溫度很高時有：，其中表達系統全部可能的狀態數。由上式能夠看出，當溫度很高時，系統處在各個狀態的概率基本相等，靠近于平均值，與所處狀態的能量幾乎無關。當溫度很低時則有：設Sm表達系統最小能量狀態的集合，Em是系統的最小能量。上式分子、分母乘以有：=由上式能夠看出，當溫度趨近于0時，系統以等概率趨近于幾個能量最小的狀態之一，而系統處在其它狀態的概率為0。由于：==其中：是溫度T下，各狀態能量的盼望值。由于Pi(T)、K、T均不不大于0，因此有：由此能夠看出，系統落入能量較低的狀態的概率是隨溫度T單調下降的，而系統落入高能量狀態的概率是隨溫度T單調上升的。也就是說，系統落入低能量狀態的概率隨著溫度的下降單調上升，而系統落入高能量狀態的概率隨著溫度的下降單調下降?？偨Y可得出以下結論：在高溫下，系統基本處在無序狀態，基本以等概率落入各個狀態。在給定的溫度下，系統落入低能量狀態的概率不不大于落入高能量狀態的概率。這樣在同一溫度下，如果系統交換得足夠充足，則系統會趨向于落入較低能量的狀態。隨著溫度的緩慢下降，系統落入低能量狀態的概率逐步增加，而落入高能量狀態的概率逐步減小，使得系統各狀態能量的盼望值隨溫度的下降單調下降，而只有那些能量不大于盼望值的狀態，其概率才隨溫度下降增加，其它狀態均隨溫度下降而下降。因此，隨著能量盼望值的逐步下降，能量低于盼望值的狀態逐步減少，當溫度趨于0時，只剩余那些含有最小能量的狀態，系統處在其它狀態的概率趨近于0。因此最后系統將以概率1處在含有最小能量的一種狀態。固體退火過程，最后達成最小能量的一種狀態，從理論上來說，必須滿足下列3個條件：初始溫度必須足夠高；在每個溫度下，狀態的交換必須足夠充足；溫度T的下降必須足夠緩慢。受固體退火過程的啟發，Kirkpatrick等人意識到組合優化問題與固體退火過程的類似性，將組合優化問題類比為固體的退火過程，提出了求解組合優化問題的模擬退貨算法。設一種定義在有限集S上的組合優化問題，i∈S是該問題的一種解，f(i)是解i的指標函數。由組合優化問題與退火過程的類比關系，i對應物理系統的一種狀態，f(i)對應當狀態的能量E(i)，一種用于控制算法的進程、其值隨算法進程遞減的控制參數t對應固體