董素媛遺傳算法

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

2、體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指生物進(jìn)化循環(huán)圖遺傳算法概要：對于一個(gè)求函數(shù)最大值的優(yōu)化問題(求最小值也類同)，一般可描述為下述數(shù)學(xué)規(guī)劃模型:max f(X) (1-1)s.t.X 屬于 R (1-2)公屬于。(1-3)其中：X=x1,x2，,xnT為決策變量，f(X)為目標(biāo)函數(shù)，(1-2)、(1-3)為約束條件，U是基本空間，R是U的一個(gè)子集。滿足約束條件的解X稱為可行解；集合R表示由所有滿足約束條件的解所組成的一個(gè)集合，叫做可行解集合。對于上述最優(yōu)化問題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的 是連續(xù)的，有的是離散的；有的是單峰值的，有

3、的是多峰值的。隨著研究的深入，人們逐漸認(rèn) 識到在很多復(fù)雜情況下要想完全精確地求出其最優(yōu)解既不可能，也不現(xiàn)實(shí)，因而求出其近似最 優(yōu)解或滿意解是人們的主要著眼點(diǎn)之一。總的來說，求最優(yōu)解或近似最優(yōu)解的方法主要有三種：枚舉法、啟發(fā)式算法和搜索算法。隨著問題種類的不同，以及問題規(guī)模的擴(kuò)大，要尋求到一種能以有限的代價(jià)來解決上述最 優(yōu)化問題的通用方法仍是個(gè)難題。而遺傳算法卻為我們解決這類問題提供了一個(gè)有效的途徑和 通用框架，開創(chuàng)了一種新的全局優(yōu)化搜索算法。遺傳算法中：將n維決策向量X=%,x2，遇nT用個(gè)記號Xi(i=1,2,_,n)所組成的符號串乂來表示：X=XX2.xnX=x1，x2，.,xnT-把每一

4、個(gè)xi看作一個(gè)遺傳基因，這樣，X就可看做是由n個(gè)遺傳基因所組成的一個(gè)染色體。這里的等位基因可以是一組整數(shù)。也可以是某一范圍內(nèi)的實(shí)數(shù)值，或者是純粹的一個(gè)記號。最簡單的等位 基因是由0和1這兩個(gè)整數(shù)組成的，相應(yīng)的染色體就可表示為一個(gè)二進(jìn)制符號串。這種編碼所形成的排列形式X是個(gè)體的基因型，與它對應(yīng)的X值是個(gè)體的表現(xiàn)型。對于每一個(gè)個(gè)體X，要按照一定的規(guī)則確定出其適應(yīng)度，個(gè)體的適應(yīng)度與其對應(yīng)的個(gè)體表現(xiàn)型乂的目標(biāo)函數(shù) 值相關(guān)聯(lián)，乂越接近于目標(biāo)函數(shù)的最優(yōu)點(diǎn)，其適應(yīng)度越大；反之，適應(yīng)度越小。遺傳算法中，決策變量X組成了問題的解空間。對問題最優(yōu)解的搜索是通過對染色體X的搜索過程來進(jìn)行的。 從而所有的染色體X就組

5、成了問題的搜索空間。生物的進(jìn)化是以集團(tuán)為主體的。與此對應(yīng)，遺傳算法的運(yùn)算對象是由M個(gè)個(gè)體所組成的集合，稱為群體(或 稱種群)。與生物一代一代的自然進(jìn)化過程相類似，遺傳算法的運(yùn)算過程也是一個(gè)反復(fù)迭代過程：第俄群體記做P(t)，經(jīng)過一代遺傳和進(jìn)化后，得到t+1代群體，記做P(t+1),這個(gè)群體不斷地經(jīng)過遺傳和進(jìn)化操作，并且每次都按照優(yōu)勝劣汰的規(guī)則將適應(yīng)度較高的個(gè)體 更多地遺傳到下一代，這樣最終在群體中將會得到一個(gè)優(yōu)良的個(gè)體X，它所對應(yīng)的表現(xiàn)型乂將達(dá) 到或接近于問題的最優(yōu)解乂*。二、遺傳算法的基本流程：Stepl給出一個(gè)有N個(gè)染色體的初始群體pop(1),t=1；Step2若停止規(guī)則滿足，則算法停止

6、；否則，對群體pop(t)中每一個(gè)染色體popi(t)計(jì)算其適應(yīng)值； Step3從群體pop(t)中隨機(jī)選一些染色體構(gòu)成一個(gè)種群newpop(t+1)=popj(t)lj=1,2，,N;Step4通過交叉，交叉概率為Pc,得到有N個(gè)染色體的crosspop(t+1)Step5對每個(gè)新個(gè)體依變異概率Pm進(jìn)行變異，形成mutpop(t+1);t=t+1,新的群體pop(t)=mutpop(t);返回Step2注意：1)newpop(t+1)集中可能重復(fù)選pop(t)中的某個(gè)元素2)最好的染色體不一定出現(xiàn)在最后一代，所以在進(jìn)化開始，必須把最好的染色體保留下來，記為V0， 如果在新的種群中又發(fā)現(xiàn)了更好

7、的染色體，則用它代替原來的染色體V0,在進(jìn)化完成之后，這個(gè)染色體就可以 看作是最優(yōu)問題的解。三、遺傳算法實(shí)現(xiàn)的技術(shù)問題：解的編碼；初始群體的設(shè)定；適應(yīng)值函數(shù)的設(shè)計(jì)；遺傳算子(選擇規(guī)則；交叉規(guī)則；變異規(guī)則；) 約束條件的處理；結(jié)束準(zhǔn)則；運(yùn)行參數(shù)的選擇；GA的流程框圖編碼的主要方法：常規(guī)碼(二進(jìn)制編碼)每個(gè)實(shí)數(shù)都可以用二進(jìn)制數(shù)表示例(連續(xù)變量的編碼)：對于給定的區(qū)間a,b,設(shè)采用二進(jìn)制編碼長為n,則任一變量x=a+ai(b-a)/2+ a (b-a)/22+H a (b-a)/2n對應(yīng)二進(jìn)制編碼a a - a，二進(jìn)制碼與實(shí)際變量的最大誤差為(b-a)/2 n(2)有些問題的解可以用0，1變量來表示

8、例(01背包問題)：設(shè)有一個(gè)容積為b的背包，n個(gè)體積分別為ai (i=1,2, -,n)的價(jià)值分別為ci (i=1,2,-,n)的物品，如何以最大的價(jià)值裝包？在這個(gè)問題中可以定義xi為決策變量，其中xi = 1表示第i個(gè)物品裝包，xi = 0表示第i個(gè)物品不裝包，于是可以按(x1,x2, ,xn)的取值形成一個(gè)自然編碼。浮點(diǎn)碼：每一個(gè)染色體由一個(gè)向量表示，如用向量x=(x1,x2,xn)表示最優(yōu)化問題的解，相 應(yīng)的染色體也是V= (x1,x2, ,xn)(常用于一些多維，高精度要求的連續(xù)函數(shù)優(yōu)化問題) 非常規(guī)碼：非常規(guī)的編碼與問題聯(lián)系緊密(基因值取決一個(gè)無數(shù)值意義，而只有代碼意義的符號集)例(

9、TSP旅行商問題)：一個(gè)商人欲到n個(gè)城市推銷商品，每兩個(gè)城市i和j之間的距離為dij,如何選擇一 條道路使得商人每個(gè)城市走一遍后回到起點(diǎn)且所走路徑最短。？群體的設(shè)定：遺傳算法的兩個(gè)主要特點(diǎn)之一就是基于群體搜索的策略，群體的設(shè)定，尤其是群體規(guī)模的設(shè)定，對遺傳算 法性能有著重要的影響。這中間包括兩個(gè)問題：1)初始群體如何設(shè)定；2)進(jìn)化過程中各代的規(guī)模如何維持？ 初始群體的設(shè)定：遺傳算法中初始群體中的個(gè)體是按一定的分布隨機(jī)產(chǎn)生的，一般來講，初始 群體的設(shè)定可以采用如下的策略：根據(jù)問題固有知識，設(shè)法把握最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定 初始群體。先隨機(jī)生成一定數(shù)目的個(gè)

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

11、適應(yīng)值增大方向。如果目標(biāo)函數(shù)本身已經(jīng)滿足上述兩個(gè)條件，可以直接用目標(biāo)函數(shù)代替適應(yīng)值函數(shù)。否則就要設(shè)計(jì)適當(dāng)?shù)倪m應(yīng)值 函數(shù)，下面介紹幾種使用比較方便的適應(yīng)值函數(shù)的設(shè)計(jì)方法。簡單適應(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) 30min f(x)可適當(dāng)取適應(yīng)值函數(shù)fitness(x)=M-f(x),其中M為常數(shù)，且保證fitness(x) 30排序適應(yīng)函數(shù)(計(jì)算同一代群體中N個(gè)染色體的目標(biāo)函數(shù)值)使染色體由好到壞進(jìn)行排序，即一個(gè)染色體越好其序號越小。設(shè)參數(shù)a仁(0，1)給定， 定義

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

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

14、適應(yīng)度值總和中所占的比例，表示該個(gè)體在選 擇過程中被選中的概率。選擇過程體現(xiàn)了生物進(jìn)化過程中“適者生存，優(yōu)勝劣汰”的思想。對于給定的規(guī)模為n的群體P = ai,a2,一，叩，個(gè)體aj G P的適應(yīng)度值為f(aj其選擇概率 n ，/、f (a )ps為：步驟1(a ) =j,j = ，2, . . ., nj 切 f (a )ii =1對每個(gè)染色體V.，計(jì)算累積概率q.iiq0= 0,5jq =Z p(七)，i = 1,2, , Nj=l步驟2從區(qū)間0, q中產(chǎn)生一個(gè)隨機(jī)數(shù)r;步驟3若q. 1 Wr W q.,選擇第i個(gè)染色體V. (1i WN)；步驟4重復(fù)步驟2和步驟3共N次，這樣可以得到N個(gè)

15、染色體.(可能會有重復(fù))交叉規(guī)則：群體P(t)內(nèi)的各個(gè)個(gè)體隨機(jī)搭配成對，對每一對個(gè)體，以某個(gè)概率(稱為交叉概率) 交換它們之間的部分染色體.交叉操作一般分為以下幾個(gè)步驟：從配對池中隨機(jī)取出要交配的一對個(gè)體；根據(jù)位串長度L,對要交叉的一對個(gè)體，隨機(jī)選取1, L-1中一個(gè)或多個(gè)整數(shù)k作為交叉位置；根據(jù)交叉概率實(shí)施交叉操作，配對個(gè)體在交叉位置處，相互交換各自的部分內(nèi)容，形成新的一對個(gè)體。 注意：任何交叉算子需滿足交叉算子的評估準(zhǔn)則，即交叉算子需保證前一代中優(yōu)秀個(gè)體的性狀 能在下一代的新個(gè)體中盡可能得到遺傳何繼承。此外，交叉算子設(shè)計(jì)和編碼設(shè)計(jì)需協(xié)調(diào)操作常規(guī)碼的交叉規(guī)則:父代個(gè)體子代個(gè)體非常規(guī)碼的常規(guī)交

16、叉法隨機(jī)選一個(gè)交叉位，兩個(gè)后代交叉位之前的基因分別繼承雙親的交叉位之前的基因，交叉 位之后的基因分別按異方基因順序選取不重基因。如父 A1 2 3|4 5 6 78 910子 A1 2 3 | 478 59610父 B4 7 8|3 2 5 91 610子 B4 7 8 | 123 56910浮點(diǎn)碼的交叉操作從開區(qū)間(0，1)中產(chǎn)生一個(gè)隨機(jī)數(shù)c，然后，按以下形式在Vi和Vj之間進(jìn)行交叉操作， 并產(chǎn)生兩個(gè)后代X和Y：Y = (1 - c).V + cV.如果可行集是凸的，這種凸組合交叉運(yùn)算在兩個(gè)父代可行的情況下，能夠保證兩個(gè)后代也是可行的.但是， 在許多情況下，可行集不一定是凸的，或很難驗(yàn)證其凸

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