董素媛遺傳算法

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è)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體

2、進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 群體競爭種群婚配子群變異淘汰生物進(jìn)化循環(huán)圖 構(gòu)造初始種群計(jì)算個(gè)體（染色體）的適應(yīng)值選擇交叉變異遺傳算法基本流程遺傳算法概要： 對(duì)于一個(gè)求函數(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的一個(gè)子集。滿足約束條件的解X稱為可行解； 集合R表示由所有滿足約束條件的解所組成的一個(gè)集合，叫做可行解集合。對(duì)于上述最優(yōu)

3、化問題，目標(biāo)函數(shù)和約束條件種類繁多，有的是線性的，有的是非線性的；有的是連續(xù)的，有的是離散的；有的是單峰值的，有的是多峰值的。隨著研究的深入，人們逐漸認(rèn)識(shí)到在很多復(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維決策向量Xxl,x2,xn

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

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

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

7、的某個(gè)元素2）最好的染色體不一定出現(xiàn)在最后一代，所以在進(jìn)化開始，必須把最好的染色體保留下來，記為V0，如果在新的種群中又發(fā)現(xiàn)了更好的染色體，則用它代替原來的染色體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)制編碼）(1)每個(gè)實(shí)數(shù)都可以用二進(jìn)制數(shù)表示例（連續(xù)變量的編碼）：對(duì)于給定的區(qū)間a,b,設(shè)采用二進(jìn)制編碼長為n,則任一變量 x=a+a1(b-a)/2+ a2(b-a)/22+ an(

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

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

10、設(shè)法把握最優(yōu)解所占空間在整個(gè)問題空間中的分布范圍，然后，在此分布范圍內(nèi)設(shè)定初始群體。（2）先隨機(jī)生成一定數(shù)目的個(gè)體，然后從中挑出最好的個(gè)體加入到初始群體中。這一過程不斷重復(fù)，直到初始群體中個(gè)體數(shù)達(dá)到了預(yù)定的規(guī)模。群體規(guī)模的設(shè)定：若群體規(guī)模太大，群體中個(gè)體的多樣性越高，算法陷入局部最優(yōu)解的危險(xiǎn)就越小。另外，群體規(guī)模太小，會(huì)使遺傳算法的搜索空間分布范圍有限，因而搜索有可能停止在未成熟階段，引起未成熟收斂（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)值的

11、大小。因此存在目標(biāo)函數(shù)到適應(yīng)值函數(shù)的對(duì)應(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)滿足上述兩個(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)0min f(x)可適當(dāng)取適應(yīng)值函數(shù)fitness(x)=M-f(x),其中M為常數(shù)，且保證fitness(x)0排序適應(yīng)函數(shù)（計(jì)算同一代群體中N

12、個(gè)染色體的目標(biāo)函數(shù)值）使染色體由好到壞進(jìn)行排序，即一個(gè)染色體越好其序號(hào)越小。設(shè)參數(shù)（0，1）給定，定義基于序的適應(yīng)函數(shù)為p（Vi）= (1- )i-1 (i=1,2,N)將染色體由壞到好進(jìn)行排序，即一個(gè)染色體越好其序號(hào)越大。定義基于序的 適應(yīng)函數(shù)為 p（Vi）=(i=1,2,N)遺傳算子：遺傳操作是模擬生物基因遺傳的操作。包括三個(gè)基本遺傳算子（genetic operator）：選擇，交叉和變異。這三個(gè)遺傳算子具有一些特點(diǎn)：（1）這三個(gè)算子的操作都是在隨機(jī)擾動(dòng)情況下進(jìn)行的。換句話說，遺傳操作是隨機(jī)化操作，因此，群體中個(gè)體向最優(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）三個(gè)基本算子的操作方法和操作策略隨具體求解問題的不同而異?；蛘哒f，是和個(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

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

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

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浮點(diǎn)碼的交叉操作 從開區(qū)間（0，1）中產(chǎn)生一個(gè)隨機(jī)數(shù)c，然后，按以下形式在Vi和Vj之間進(jìn)行交叉操作，并產(chǎn)生兩個(gè)后代X和Y： 如果可行集是凸的，這種凸組合交叉運(yùn)算在兩個(gè)父代可行的情況下，能夠保證兩個(gè)后代也是可行的但是，在許多情況下，可行集不一定是凸的，或很難驗(yàn)證其凸性，此時(shí)必須檢驗(yàn)每一后代的可行性如果兩個(gè)后代均可行，則用

17、它們代替其父代，否則，保留其中可行的（如果存在的話），然后，產(chǎn)生新的隨機(jī)數(shù)c，重新進(jìn)行交叉操作，直到得到兩個(gè)可行的后代或循環(huán)給定次數(shù)為止無論如何，僅用可行的后代取代其父代 變異規(guī)則：變異操作模擬自然界生物體進(jìn)化中染色體上某位基因發(fā)生的突變現(xiàn)象，從而改變?nèi)旧w的結(jié)構(gòu)和物理性狀。在遺傳算法中，對(duì)群體P(t)中的每一個(gè)個(gè)體，變異算子通過按變異概率pm隨機(jī)反轉(zhuǎn)某位等位基因的二進(jìn)制字符值來實(shí)現(xiàn)。注意：變異操作作用于個(gè)體位串的等位基因上，由于變異概率比較小，在實(shí)施過程中一些個(gè)體可能根本不發(fā)生一次變異，造成大量計(jì)算資源的浪費(fèi)。給定一個(gè)較小的變異概率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ī)碼變異時(shí)，變異位一般成對(duì)選擇，變異規(guī)則是將兩個(gè)變異位上的數(shù)據(jù)互換，如1 2 3 4的變異位是1，3位，則變異后成為3 2 1 4當(dāng)交叉操作產(chǎn)生的后代個(gè)體的適應(yīng)值不再比它們的前輩更好，但又未達(dá)到全局最優(yōu)解時(shí)，就會(huì)發(fā)生成熟前收斂或早熟收斂（Premature convergence）。這時(shí)引入變異算子往往能產(chǎn)生很好的效果。一方面，變異算子可以使群體進(jìn)化過程中丟失的等位基因信息得以恢復(fù)，以保持群體中的個(gè)體差異性，防止發(fā)生成熟前收斂；另一方面，當(dāng)種群規(guī)模

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

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

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

22、數(shù)集編碼群體t計(jì)算適值運(yùn)算：復(fù)制交叉變異群體t+1滿足要求？解碼改善或解決實(shí)際問題群體t+1Þ群體tYN四、遺傳算法的手工模擬計(jì)算示例 為更好地理解遺傳算法的運(yùn)算過程，下面用手工計(jì)算來簡單地模擬遺傳算法的各個(gè)主要執(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) 個(gè)體編碼：遺傳算法的運(yùn)算對(duì)象是表示個(gè)體的符號(hào)串，所以必須把變量 x1, x2 編碼為一種符號(hào)串。本題中，用無符號(hào)二進(jìn)制整數(shù)來表示。因 x1, x2 為 0 7之間的整數(shù)，所以分別用3位

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

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