董素媛遺傳算法

1、遺傳算法簡介Genetic Algorithm (GA)-An Brief Introduction-一、遺傳算法的概述 起源和特點：遺傳算法是模擬達(dá)爾文的遺傳選擇和自然淘汰、適者生存的生物進(jìn)化過程的計算模型，是由美國Michigan（密西根）大學(xué)的J.Holland教授于1975年首先提出的，是搜索最優(yōu)解的一種隨機(jī)化的方法。其主要特點是群體搜索策略和群體中個體之間的信息交換，是近十多年來備受關(guān)注的一種算法。搜索機(jī)制 ：遺傳算法模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體

2、進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 群體競爭種群婚配子群變異淘汰生物進(jìn)化循環(huán)圖 構(gòu)造初始種群計算個體（染色體）的適應(yīng)值選擇交叉變異遺傳算法基本流程遺傳算法概要： 對于一個求函數(shù)最大值的優(yōu)化問題（求最小值也類同），一般可描述為下述數(shù)學(xué)規(guī)劃模型： max f(X) (1-1) s.t. X屬于R (1-2) R屬于U (1-3) 其中：Xx1,x2,xnT為決策變量，f(X)為目標(biāo)函數(shù)， (1-2)、(1-3)為約束條件，U是基本空間，R是U的一個子集。滿足約束條件的解X稱為可行解； 集合R表示由所有滿足約束條件的解所組成的一個集合，叫做可行解集合。對于上述最優(yōu)

3、化問題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實，因而求出其近似最優(yōu)解或滿意解是人們的主要著眼點之一。 總的來說，求最優(yōu)解或近似最優(yōu)解的方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。 隨著問題種類的不同，以及問題規(guī)模的擴(kuò)大，要尋求到一種能以有限的代價來解決上述最優(yōu)化問題的通用方法仍是個難題。而遺傳算法卻為我們解決這類問題提供了一個有效的途徑和通用框架，開創(chuàng)了一種新的全局優(yōu)化搜索算法。遺傳算法中： 將n維決策向量Xxl,x2,xn

4、T用n個記號Xi(i=1,2,n)所組成的符號串X來表示： Xxlx2xn T Xx1，x2， ,xnT 把每一個xi看作一個遺傳基因，這樣，X就可看做是由n個遺傳基因所組成的一個染色體。 這里的等位基因可以是一組整數(shù)。也可以是某一范圍內(nèi)的實數(shù)值，或者是純粹的一個記號。最簡單的等位基因是由0和1這兩個整數(shù)組成的，相應(yīng)的染色體就可表示為一個二進(jìn)制符號串。 這種編碼所形成的排列形式X是個體的基因型，與它對應(yīng)的X值是個體的表現(xiàn)型。 對于每一個個體X，要按照一定的規(guī)則確定出其適應(yīng)度，個體的適應(yīng)度與其對應(yīng)的個體表現(xiàn)型X的目標(biāo)函數(shù)值相關(guān)聯(lián)，X越接近于目標(biāo)函數(shù)的最優(yōu)點，其適應(yīng)度越大；反之，適應(yīng)度越小。 遺傳

5、算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體X的搜索過程來進(jìn)行的。從而所有的染色體X就組成了問題的搜索空間。 生物的進(jìn)化是以集團(tuán)為主體的。與此對應(yīng)，遺傳算法的運(yùn)算對象是由M個個體所組成的集合，稱為群體（或稱種群）。與生物一代一代的自然進(jìn)化過程相類似，遺傳算法的運(yùn)算過程也是一個反復(fù)迭代過程： 第t代群體記做 P(t)， 經(jīng)過一代遺傳和進(jìn)化后，得到 t+1 代群體，記做 P(t+1), 這個群體不斷地經(jīng)過遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個體更多地遺傳到下一代，這樣最終在群體中將會得到一個優(yōu)良的個體X，它所對應(yīng)的表現(xiàn)型X將達(dá)到或接近于問題的最優(yōu)解X

6、*。二、遺傳算法的基本流程：Step1 給出一個有N個染色體的初始群體pop(1),t=1；Step2 若停止規(guī)則滿足，則算法停止；否則，對群體pop(t)中每一個染色體popi(t)計算其適應(yīng)值；Step3 從群體pop(t)中隨機(jī)選一些染色體構(gòu)成一個種群newpop(t+1)=popj(t)|j=1,2,N;Step4 通過交叉，交叉概率為Pc,得到有N個染色體的crosspop(t+1)Step5 對每個新個體依變異概率Pm進(jìn)行變異，形成mutpop(t+1);t=t+1,新的群體pop(t)=mutpop(t);返回Step2注意：1）newpop(t+1)集中可能重復(fù)選pop(t)中

7、的某個元素2）最好的染色體不一定出現(xiàn)在最后一代，所以在進(jìn)化開始，必須把最好的染色體保留下來，記為V0，如果在新的種群中又發(fā)現(xiàn)了更好的染色體，則用它代替原來的染色體V0,在進(jìn)化完成之后，這個染色體就可以看作是最優(yōu)問題的解。三、遺傳算法實現(xiàn)的技術(shù)問題：解的編碼；初始群體的設(shè)定；適應(yīng)值函數(shù)的設(shè)計；遺傳算子(選擇規(guī)則；交叉規(guī)則；變異規(guī)則；)約束條件的處理；結(jié)束準(zhǔn)則；運(yùn)行參數(shù)的選擇；GA的流程框圖編碼的主要方法：常規(guī)碼（二進(jìn)制編碼）(1)每個實數(shù)都可以用二進(jìn)制數(shù)表示例（連續(xù)變量的編碼）：對于給定的區(qū)間a,b,設(shè)采用二進(jìn)制編碼長為n,則任一變量 x=a+a1(b-a)/2+ a2(b-a)/22+ an(

8、b-a)/2n 對應(yīng)二進(jìn)制編碼a1 a2 an，二進(jìn)制碼與實際變量的最大誤差為(b-a)/2 n (2)有些問題的解可以用0，1變量來表示例（01背包問題）：設(shè)有一個容積為b的背包，n個體積分別為ai（i=1,2,n）的價值分別為ci （i=1,2,n）的物品，如何以最大的價值裝包？在這個問題中可以定義xi為決策變量，其中xi1表示第i個物品裝包， xi0表示第i個物品不裝包，于是可以按(x1,x2,xn)的取值形成一個自然編碼。浮點碼：每一個染色體由一個向量表示，如用向量 x=(x1,x2,xn)表示最優(yōu)化問題的解，相應(yīng)的染色體也是V= (x1,x2,xn)（常用于一些多維，高精度要求的連續(xù)

9、函數(shù)優(yōu)化問題 ）非常規(guī)碼：非常規(guī)的編碼與問題聯(lián)系緊密（基因值取決一個無數(shù)值意義，而只有代碼意義的符號集） 例（TSP旅行商問題）：一個商人欲到n個城市推銷商品，每兩個城市i和j之間的距離為dij,如何選擇一條道路使得商人每個城市走一遍后回到起點且所走路徑最短。?群體的設(shè)定:遺傳算法的兩個主要特點之一就是基于群體搜索的策略，群體的設(shè)定，尤其是群體規(guī)模的設(shè)定，對遺傳算法性能有著重要的影響。這中間包括兩個問題：1）初始群體如何設(shè)定；2）進(jìn)化過程中各代的規(guī)模如何維持？初始群體的設(shè)定：遺傳算法中初始群體中的個體是按一定的分布隨機(jī)產(chǎn)生的，一般來講，初始群體的設(shè)定可以采用如下的策略：（1）根據(jù)問題固有知識，

10、設(shè)法把握最優(yōu)解所占空間在整個問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。（2）先隨機(jī)生成一定數(shù)目的個體，然后從中挑出最好的個體加入到初始群體中。這一過程不斷重復(fù)，直到初始群體中個體數(shù)達(dá)到了預(yù)定的規(guī)模。群體規(guī)模的設(shè)定：若群體規(guī)模太大，群體中個體的多樣性越高，算法陷入局部最優(yōu)解的危險就越小。另外，群體規(guī)模太小，會使遺傳算法的搜索空間分布范圍有限，因而搜索有可能停止在未成熟階段，引起未成熟收斂（premature convergence）現(xiàn)象。實際應(yīng)用中群體規(guī)模一般取幾十幾百。適應(yīng)值函數(shù)的設(shè)計：在傳統(tǒng)的優(yōu)化方法中，判斷一個解集的好壞是根據(jù)目標(biāo)函數(shù)值的大小，而在遺傳算法中，則是根據(jù)適應(yīng)值的

11、大小。因此存在目標(biāo)函數(shù)到適應(yīng)值函數(shù)的對應(yīng)問題。一般來講，適應(yīng)值函數(shù)應(yīng)該滿足：（1）非負(fù)性；（2）目標(biāo)函數(shù)的優(yōu)化方向?qū)?yīng)適應(yīng)值增大方向。如果目標(biāo)函數(shù)本身已經(jīng)滿足上述兩個條件，可以直接用目標(biāo)函數(shù)代替適應(yīng)值函數(shù)。否則就要設(shè)計適當(dāng)?shù)倪m應(yīng)值函數(shù)，下面介紹幾種使用比較方便的適應(yīng)值函數(shù)的設(shè)計方法。簡單適應(yīng)函數(shù)（目標(biāo)函數(shù)的簡單變形）max f(x),且在可行域內(nèi)不是非負(fù)函數(shù)可適當(dāng)取適應(yīng)值函數(shù)fitness(x)=f(x)+M,其中M為常數(shù)，且保證fitness(x)0min f(x)可適當(dāng)取適應(yīng)值函數(shù)fitness(x)=M-f(x),其中M為常數(shù)，且保證fitness(x)0排序適應(yīng)函數(shù)（計算同一代群體中N

12、個染色體的目標(biāo)函數(shù)值）使染色體由好到壞進(jìn)行排序，即一個染色體越好其序號越小。設(shè)參數(shù)（0，1）給定，定義基于序的適應(yīng)函數(shù)為p（Vi）= (1- )i-1 (i=1,2,N)將染色體由壞到好進(jìn)行排序，即一個染色體越好其序號越大。定義基于序的 適應(yīng)函數(shù)為 p（Vi）=(i=1,2,N)遺傳算子：遺傳操作是模擬生物基因遺傳的操作。包括三個基本遺傳算子（genetic operator）：選擇，交叉和變異。這三個遺傳算子具有一些特點：（1）這三個算子的操作都是在隨機(jī)擾動情況下進(jìn)行的。換句話說，遺傳操作是隨機(jī)化操作，因此，群體中個體向最優(yōu)解遷移的規(guī)則是隨機(jī)的。需要強(qiáng)調(diào)的是，這種隨機(jī)化操作和傳統(tǒng)的隨機(jī)搜索方

13、法是有區(qū)別的。遺傳操作進(jìn)行的是高效有向的搜索，而不是如一般隨機(jī)搜索方法所進(jìn)行的無向搜索。（2）遺傳操作的效果和所取的操作概率、編碼方法、群體大小，以及適應(yīng)度函數(shù)的設(shè)定密切相關(guān)。（3）三個基本算子的操作方法和操作策略隨具體求解問題的不同而異。或者說，是和個體的編碼方式直接相關(guān)。選擇規(guī)則:從群體中選擇優(yōu)勝個體，淘汰劣質(zhì)個體的操作叫選擇。根據(jù)各個個體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇出一些優(yōu)良的個體遺傳到下一代群體P(t+1)中；適應(yīng)度比例選擇：最基本的選擇方法，其中每個個體被選擇的期望數(shù)量與其適應(yīng)度值和群體平均適應(yīng)度值的比例有關(guān)，通常采用輪盤賭（roulette wheel

14、）方式實現(xiàn)。這種方式首先計算每個個體的適應(yīng)度值，然后計算出此適應(yīng)度值在群體適應(yīng)度值總和中所占的比例，表示該個體在選擇過程中被選中的概率。選擇過程體現(xiàn)了生物進(jìn)化過程中“適者生存，優(yōu)勝劣汰”的思想。對于給定的規(guī)模為n的群體，個體的適應(yīng)度值為，其選擇概率為：步驟1 對每個染色體Vi，計算累積概率qi步驟2 從區(qū)間0, qN中產(chǎn)生一個隨機(jī)數(shù)r;步驟3 若qi-1 r qi ，選擇第i個染色體Vi (1i N) ；步驟4 重復(fù)步驟2和步驟3共N次，這樣可以得到N個染色體(可能會有重復(fù))交叉規(guī)則：群體P(t)內(nèi)的各個個體隨機(jī)搭配成對，對每一對個體，以某個概率 (稱為交叉概率）交換它們之間的部分染色體.交叉

15、操作一般分為以下幾個步驟：（1）從配對池中隨機(jī)取出要交配的一對個體；（2）根據(jù)位串長度L，對要交叉的一對個體，隨機(jī)選取1, L-1中一個或多個整數(shù)k作為交叉位置；（3）根據(jù)交叉概率實施交叉操作，配對個體在交叉位置處，相互交換各自的部分內(nèi)容，形成新的一對個體。注意：任何交叉算子需滿足交叉算子的評估準(zhǔn)則，即交叉算子需保證前一代中優(yōu)秀個體的性狀能在下一代的新個體中盡可能得到遺傳何繼承。此外，交叉算子設(shè)計和編碼設(shè)計需協(xié)調(diào)操作常規(guī)碼的交叉規(guī)則：交叉概率連續(xù)改變?nèi)旧w多個基因位上的遺傳信息息交叉位Pccross父代個體子代個體1212非常規(guī)碼的常規(guī)交叉法 隨機(jī)選一個交叉位，兩個后代交叉位之前的基因分別繼承

16、雙親的交叉位之前的基因，交叉位之后的基因分別按異方基因順序選取不重基因。如父A 1 2 3 | 4 5 6 7 8 9 10 子A 1 2 3 | 4 7 8 5 9 6 10父B 4 7 8 | 3 2 5 9 1 6 10 子B 4 7 8 | 1 2 3 5 6 9 10浮點碼的交叉操作 從開區(qū)間（0，1）中產(chǎn)生一個隨機(jī)數(shù)c，然后，按以下形式在Vi和Vj之間進(jìn)行交叉操作，并產(chǎn)生兩個后代X和Y： 如果可行集是凸的，這種凸組合交叉運(yùn)算在兩個父代可行的情況下，能夠保證兩個后代也是可行的但是，在許多情況下，可行集不一定是凸的，或很難驗證其凸性，此時必須檢驗每一后代的可行性如果兩個后代均可行，則用

17、它們代替其父代，否則，保留其中可行的（如果存在的話），然后，產(chǎn)生新的隨機(jī)數(shù)c，重新進(jìn)行交叉操作，直到得到兩個可行的后代或循環(huán)給定次數(shù)為止無論如何，僅用可行的后代取代其父代 變異規(guī)則：變異操作模擬自然界生物體進(jìn)化中染色體上某位基因發(fā)生的突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀。在遺傳算法中，對群體P(t)中的每一個個體，變異算子通過按變異概率pm隨機(jī)反轉(zhuǎn)某位等位基因的二進(jìn)制字符值來實現(xiàn)。注意：變異操作作用于個體位串的等位基因上，由于變異概率比較小，在實施過程中一些個體可能根本不發(fā)生一次變異，造成大量計算資源的浪費。給定一個較小的變異概率Pm（0.0010.01）, i=1到N重復(fù)下列過程：從區(qū)間

18、0,1中產(chǎn)生隨機(jī)數(shù)r，如果r< Pm ，則選擇染色體Vi作為變異的父代常規(guī)碼：如果某一位被選中進(jìn)行變異，則0變?yōu)?，1變?yōu)?即可非常規(guī)碼：非常規(guī)碼變異時，變異位一般成對選擇，變異規(guī)則是將兩個變異位上的數(shù)據(jù)互換，如1 2 3 4的變異位是1，3位，則變異后成為3 2 1 4當(dāng)交叉操作產(chǎn)生的后代個體的適應(yīng)值不再比它們的前輩更好，但又未達(dá)到全局最優(yōu)解時，就會發(fā)生成熟前收斂或早熟收斂（Premature convergence）。這時引入變異算子往往能產(chǎn)生很好的效果。一方面，變異算子可以使群體進(jìn)化過程中丟失的等位基因信息得以恢復(fù)，以保持群體中的個體差異性，防止發(fā)生成熟前收斂；另一方面，當(dāng)種群規(guī)模

19、較大時，在交叉操作基礎(chǔ)上引人適度的變異，也能夠提高遺傳算法的局部搜索效率。在群體進(jìn)化的整個過程中，交叉操作是主要的基因重組和群體更迭的手段，變異操作的作用是第二位的，變異算子僅僅充當(dāng)背景性的角色（background role）。約束條件的處理：為了保證染色體是可行的，必須對遺傳操作過程中得到的每一個染色體進(jìn)行檢查對每個最優(yōu)化問題，最好設(shè)計一個程序，其輸出值1表示染色體是可行的，0表示不可行 例如，對約束條件gj (x) 0,j=1,2,p，可以作如下的一個子函數(shù)： 從j1開始循環(huán) 若gj (x) >0 ，返回0 直到j(luò)p結(jié)束 返回 1結(jié)束準(zhǔn)則：（1）最簡單的結(jié)束準(zhǔn)則是給定一個最大的遺傳

20、代數(shù)MAXGEN,算法迭代代數(shù)達(dá)到MAXGEN時停止（2）給定問題一個下界LB，當(dāng)進(jìn)化中達(dá)到要求的偏差度時，算法終止，即當(dāng)|V*(t)-LB|< 時停止( V*(t)為第t代所得的最優(yōu)目標(biāo)值，即 )（3）自適應(yīng)規(guī)則： 用V*(t)進(jìn)行監(jiān)控，如果監(jiān)控到算法已經(jīng)K代沒有進(jìn)化到一個更好的解，則算法停止。運(yùn)行參數(shù)的選擇：在遺傳算法的運(yùn)行過程中，存在著對其性能產(chǎn)生重大影響的一組參數(shù)。這組參數(shù)在初始階段或群體進(jìn)化過程中需要合理的選擇和控制，以使 GA以最佳的搜索軌跡達(dá)到最優(yōu)解。主要參數(shù)包括染色體位串長度L，群體規(guī)模n，終止進(jìn)化代數(shù)maxGen，交叉概率Pc以及變異概率Pm。許多學(xué)者進(jìn)行了大量實驗研究

21、，給出了最優(yōu)參數(shù)建議。位串長度L：位串長度L的選擇取決于特定問題解的精度。要求的精度越高，位串越長，但要更多的計算時間。群體規(guī)模popSize（N）：一般建議為20100終止進(jìn)化代數(shù)maxGen：1001000交叉概率pc：0.40.99變異概率pm：0.0010.01實際上，上述參數(shù)與問題的類型有著直接的關(guān)系。問題的目標(biāo)函數(shù)越復(fù)雜，參數(shù)選擇就越困難。從理論上來講，不存在一組適用于所有問題的最佳參數(shù)值，隨著問題特征的變化，有效參數(shù)的差異往往非常顯著。如何設(shè)定遺傳算法的控制參數(shù)以使遺傳算法的性能得到改善，還需要結(jié)合實際問題深人研究，以及有賴于遺傳算法理論研究的新進(jìn)展。GA的流程框圖 ：實際問題參

22、數(shù)集編碼群體t計算適值運(yùn)算：復(fù)制交叉變異群體t+1滿足要求？解碼改善或解決實際問題群體t+1Þ群體tYN四、遺傳算法的手工模擬計算示例 為更好地理解遺傳算法的運(yùn)算過程，下面用手工計算來簡單地模擬遺傳算法的各個主要執(zhí)行步驟。例：求下述二元函數(shù)的最大值： max f(x1,x2)=x12+x22 s.t. x1 Î 1,2,3,4,5,6,7 x2 Î 1,2,3,4,5,6,7(1) 個體編碼：遺傳算法的運(yùn)算對象是表示個體的符號串，所以必須把變量 x1, x2 編碼為一種符號串。本題中，用無符號二進(jìn)制整數(shù)來表示。因 x1, x2 為 0 7之間的整數(shù)，所以分別用3位

23、無符號二進(jìn)制整數(shù)來表示，將它們連接在一起所組成的6位無符號二進(jìn)制數(shù)就形成了個體的基因型，表示一個可行解。 例如，基因型 X101110 所對應(yīng)的表現(xiàn)型是：x 5，6 。 個體的表現(xiàn)型x和基因型X之間可通過編碼和解碼程序相互轉(zhuǎn)換。(2) 初始群體的產(chǎn)生：遺傳算法是對群體進(jìn)行的進(jìn)化操作，需要淮備一些表示起始搜索點的初始群體數(shù)據(jù)。 本例中，群體規(guī)模的大小取為4，即群體由4個個體組成，每個個體可通過隨機(jī)方法產(chǎn)生。 如：011101，101011，011100，111001(3) 適應(yīng)度汁算：遺傳算法中以個體適應(yīng)度的大小來評定各個個體的優(yōu)劣程度，從而決定其遺傳機(jī)會的大小。 本例中，目標(biāo)函數(shù)總?cè)》秦?fù)值，并

24、且是以求函數(shù)最大值為優(yōu)化目標(biāo)，故可直接利用目標(biāo)函數(shù)值作為個體的適應(yīng)度。(4) 選擇運(yùn)算：選擇運(yùn)算(或稱為復(fù)制運(yùn)算)把當(dāng)前群體中適應(yīng)度較高的個體按某種規(guī)則或模型遺傳到下一代群體中。一般要求適應(yīng)度較高的個體將有更多的機(jī)會遺傳到下一代群體中。 本例中，我們采用與適應(yīng)度成正比的概率來確定各個個體復(fù)制到下一代群體中的數(shù)量。其具體操作過程是： 先計算出群體中所有個體的適應(yīng)度的總和 Sfi ( i=1.2,M ); 再計算出每個個體相對適應(yīng)度的大小 fi / Sfi ，即每個個體被遺傳到下一代群體中的概率， 每個概率值組成一個區(qū)域，全部概率值之和為1； 最后產(chǎn)生一個0到1之間的隨機(jī)數(shù)，依據(jù)該隨機(jī)數(shù)出現(xiàn)在上述哪一個概率區(qū)域內(nèi)來確定各個個體被選中的次數(shù)。個體編號初始群體p(0)適值占總數(shù)的百分比總和1234011101101011011100111001343425500.240.240.170.351431選擇次數(shù)選擇結(jié)果1102011101111001101011111001x1 x2 3 5 5 3 3 4 7 10124%24%17%35%1#2#3#4#(5) 交叉運(yùn)算：交叉運(yùn)算是遺傳算法中產(chǎn)生新個體的主要操