基本遺傳算法課件

基本遺傳算法（GA）1基本遺傳算法描述遺傳算法在自然與社會(huì)現(xiàn)象模擬、工程計(jì)算等方面得到了廣泛應(yīng)用。在各個(gè)不同的應(yīng)用領(lǐng)域，為了取得更好的結(jié)果，人們對(duì)GA進(jìn)行了大量改進(jìn)，為了不至于混淆，我們把Holland提出的算法稱為基本遺傳算法，簡稱GA、SGA（SimpleGeneticAlgorithm)、CGA（CanonicalGeneticAlgorithm），將其它的“GA類”算法稱為GAs(GeneticAlgorithms）,可以把GA看作是GAs的一種特例。1.1基本遺傳算法的構(gòu)成要素

(1)染色體編碼方法

基本遺傳算法使用固定長度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位基因由二值符號(hào)集{0，1}組成。初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來生成。如：x；100111001000101101就可表示一個(gè)個(gè)體，該個(gè)體的染色體長度是l＝18。基本遺傳算法（GA）1(2)個(gè)體適應(yīng)度評(píng)價(jià)基本遺傳算法按與個(gè)體適應(yīng)度成正比的概率來決定當(dāng)前群體中每個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)多少。為正確計(jì)算這個(gè)概率，這里要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預(yù)先確定好由目標(biāo)函數(shù)值到個(gè)體適應(yīng)度之間的轉(zhuǎn)換規(guī)則，特別是要預(yù)先確定好當(dāng)目標(biāo)函數(shù)值為負(fù)數(shù)時(shí)的處理方法。(3)遺傳算子基本遺傳算法使用下述三種遺傳算子：

?選擇運(yùn)算：使用比例選擇算子；

?交叉運(yùn)算：使用單點(diǎn)交叉算子；?變異運(yùn)算：使用基本位變異算子。

(4)基本遺傳算法的運(yùn)行參數(shù)基本遺傳算法有下述4個(gè)運(yùn)行參數(shù)需要提前設(shè)定：

?

M：群體大小，即群體中所含個(gè)體的數(shù)量，一般取為20~100。

?T：遺傳運(yùn)算的終止進(jìn)化代數(shù)，一般取為100~500

?

pc：交叉概率，一般取為0.4~0.99

?

pm：變異概率，一般取為0.0001~0.1

(2)個(gè)體適應(yīng)度評(píng)價(jià)2[說明]這4個(gè)運(yùn)行參數(shù)對(duì)遺傳算法的求解結(jié)果和求解效率都有一定的影響，但目前尚無合理選擇它們的理論依據(jù)。在遺傳算法的實(shí)際應(yīng)用中，往往需要經(jīng)過多次試算后才能確定出這些參數(shù)合理的取值大小或取值范圍。1.2基本遺傳算法的形式化定義基本遺傳算法可定義為一個(gè)7元組：

GA＝(M,F,s,c,m,pc,pm)M——群體大??；F——個(gè)體適應(yīng)度評(píng)價(jià)函數(shù)；s——選擇操作算于；c——交叉操作算子：m——變異操作算于；pc——交叉概率；pm——變異概率；[說明]31.3基本遺傳算法描述ProcedureGABegininitializeP(0);t=0;while(t<=T)dofori=1toMdoEvaluatefitnessofP(t);endforfori=1toMdoSelectoperationtoP(t);endforfori=1toM/2doCrossoveroperationtoP(t);endforfori=1toMdoMutationoperationtoP(t);endforfori=1toMdoP(t+1)=P(t);endfort=t+1endwhileend1.3基本遺傳算法描述ProcedureGA42基本遺傳算法的實(shí)現(xiàn)根據(jù)上面對(duì)基本遺傳算法構(gòu)成要素的分析和算法描述，我們可以很方便地用計(jì)算機(jī)語言來實(shí)現(xiàn)這個(gè)基本遺傳算法?，F(xiàn)對(duì)具體實(shí)現(xiàn)過程中的問題作以下說明：2.1編碼與解碼

(1)編碼

假設(shè)某一參數(shù)的取值范圍是[umin,umax]，用長度為l的二進(jìn)制編碼符號(hào)串來表示該參數(shù)，則它總共能夠產(chǎn)生2l種不同的編碼，參數(shù)編碼時(shí)的對(duì)應(yīng)關(guān)系如下：00000000…00000000＝0umin

00000000…00000001＝1umin+00000000…00000010＝2umin+2……11111111…11111111=2l–1umax2基本遺傳算法的實(shí)現(xiàn)5x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1其中，為二進(jìn)制編碼的編碼精度，其公式為：=Umax

umin2l

1

(2)解碼

假設(shè)某一個(gè)體的編碼是：

x：blbl-1bl-2……b2b1則對(duì)應(yīng)的解碼公式為：x=umin+(bi·2i-1)6[例]設(shè)-3.0≤x≤12.1,精度要求=1/10000，由公式：Umax

umin2l=+11/1000012.1+3.0+1==151001即：217

<151001<218

x需要18位{0/1}符號(hào)表示。如：010001001011010000解碼：x=umin+(

bi·2i-1)

·

1i=lUmax

umin2l

1=-0.3+70352(12.1+3)/(218-1)=1.052426=Umax

umin2l

1得：[例]設(shè)-3.0≤x≤12.1,精72.2個(gè)體適應(yīng)度評(píng)價(jià)如前所述，要求所有個(gè)體的適應(yīng)度必須為正數(shù)或零，不能是負(fù)數(shù)。

(1)當(dāng)優(yōu)化目標(biāo)是求函數(shù)最大值，并且目標(biāo)函數(shù)總?cè)≌禃r(shí)，可以直接設(shè)定個(gè)體的適應(yīng)度F(X)就等于相應(yīng)的目標(biāo)函數(shù)值f(X)，即：F(X)＝f(X)

(2)對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，理論上只需簡單地對(duì)其增加一個(gè)負(fù)號(hào)就可將其轉(zhuǎn)化為求目標(biāo)函數(shù)最大值的優(yōu)化問題，即：minf(X)＝max(-f(X))但實(shí)際優(yōu)化問題中的目標(biāo)函數(shù)值有正也有負(fù)，優(yōu)化目標(biāo)有求函數(shù)最大值，也有求函數(shù)最小值，顯然上面兩式保證不了所有情況下個(gè)體的適應(yīng)度都是非負(fù)數(shù)這個(gè)要求。

2.2個(gè)體適應(yīng)度評(píng)價(jià)8

基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值f(x)變換為個(gè)體的適應(yīng)度F(x)：

方法一：對(duì)于求目標(biāo)函數(shù)最大值的優(yōu)化問題，變換方法為：

其中，Cmin為一個(gè)適當(dāng)?shù)叵鄬?duì)比較小的數(shù)，它可用下面方法之一來選?。?/p>

?預(yù)先指定的一個(gè)較小的數(shù)。

?進(jìn)化到當(dāng)前代為止的最小目標(biāo)函數(shù)值。

?當(dāng)前代或最近幾代群體中的最小目標(biāo)函數(shù)值。

方法二：對(duì)于求目標(biāo)函數(shù)最小值的優(yōu)化問題，變換方法為：其中，Cmax是一個(gè)適當(dāng)?shù)叵鄬?duì)比較大的數(shù)，它可用下面幾種方法求得：?預(yù)先指定的一個(gè)較大的數(shù)。

?進(jìn)化到當(dāng)前代為止的最大目標(biāo)函數(shù)值。

?當(dāng)前代或最近幾代群體中的最大目標(biāo)函數(shù)值。F(X)=f(X)+Cminiff(X)+Cmin>00

iff(X)+Cmin≤0F(X)=Cmax-f(X)

iff(X)Cmax0

iff(X)

Cmax基本遺傳算法一般采用下面兩種方法之一將目標(biāo)函數(shù)值f(x)92.3比例選擇算子

(1)選擇算子或復(fù)制算子的作用：從當(dāng)前代群體中選擇出一些比較優(yōu)良的個(gè)體，并將其復(fù)制到下一代群體中。

(2)

最常用和最基本的選擇算子：比例選擇算子。

(3)比例選擇算子：指個(gè)體被選中并遺傳到下一代群體中的概率與該個(gè)體的適應(yīng)度大小成正比。

(4)執(zhí)行比例選擇的手段是輪盤選擇。輪盤法的基本精神是：個(gè)體被選中的概率取決于個(gè)體的相對(duì)適應(yīng)度：pi=fi/fi(i=1,2,…,M)

式中pi——個(gè)體i被選中的概率；fi——個(gè)體i的適應(yīng)度；

fi——群體的累加適應(yīng)度。顯然，個(gè)體適應(yīng)度愈高，被選中的概率愈大。但是，適應(yīng)度小的個(gè)體也有可能被選中，以便增加下一代群體的多樣性。2.3比例選擇算子10輪盤選擇的原理：圖中指針固定不動(dòng)，外圈的圓環(huán)可以自由轉(zhuǎn)動(dòng)，圓環(huán)上的刻度代表各個(gè)個(gè)體的適應(yīng)度。當(dāng)圓環(huán)旋轉(zhuǎn)若干圈后停止，指針指定的位置便是被選中的個(gè)體。從統(tǒng)計(jì)意義講，適應(yīng)度大的個(gè)體，其刻度長，被選中的可能性大；反之，適應(yīng)度小的個(gè)體被選中的可能性小，但有時(shí)也會(huì)被“破格”選中。輪盤選擇的原理：11上述輪盤選擇過程，可描述如下：

Ⅰ.順序累計(jì)群體內(nèi)各個(gè)體的適應(yīng)度，得相應(yīng)的累計(jì)值Si，最后一個(gè)累計(jì)值為Sn；

Ⅱ.在[0,Sn]區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)r；

Ⅲ.依次用Si與r比較，第一個(gè)出現(xiàn)Si大于或等于r的個(gè)體j被選為復(fù)制對(duì)象；

Ⅳ.重復(fù)Ⅲ、Ⅳ項(xiàng)，直至新群體的個(gè)體數(shù)目等于父代群體的規(guī)模。[論盤選擇示例]上述輪盤選擇過程，可描述如下：[論盤選擇示例]122.4單點(diǎn)交叉算子(1)交叉算子作用

通過交叉，子代的基因值不同于父代。交換是遺傳算法產(chǎn)生新個(gè)體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。(2)最常用和最基本——單點(diǎn)交叉算子。(3)單點(diǎn)交叉算子的具體計(jì)算過程如下：

Ⅰ.對(duì)群體中的個(gè)體進(jìn)行兩兩隨機(jī)配對(duì)。若群體大小為M，則共有[M/2]對(duì)相互配對(duì)的個(gè)體組。Ⅱ.每一對(duì)相互配對(duì)的個(gè)體，隨機(jī)設(shè)置某一基因座之后的位置為交叉點(diǎn)。若染色體的長度為l，則共有(l-1)個(gè)可能的交叉點(diǎn)位置。Ⅲ.對(duì)每一對(duì)相互配對(duì)的個(gè)體，依設(shè)定的交叉概率pc在其交叉點(diǎn)處相互交換兩個(gè)個(gè)體的部分染色體，從而產(chǎn)生出兩個(gè)新的個(gè)體。

單點(diǎn)交叉運(yùn)算的示例如下所示:

單點(diǎn)交叉A；1011011100A’：1011011111B：0001110011B’：00011100002.4單點(diǎn)交叉算子單點(diǎn)交叉A；101101110013

交叉概率pc=McM式中M——群體中個(gè)體的數(shù)目；Mc——群體中被交換個(gè)體的數(shù)目。[交叉操作示例]交叉的個(gè)體是隨機(jī)確定的，如下表所示。某群體有n個(gè)個(gè)體，每個(gè)個(gè)體含8個(gè)等位基因。針對(duì)每個(gè)個(gè)體產(chǎn)生一個(gè)[0,1]區(qū)間的均勻隨機(jī)數(shù)。假設(shè)交叉概率pc=0.6，則隨機(jī)數(shù)小于0.6的對(duì)應(yīng)個(gè)體與其隨機(jī)確定的另一個(gè)個(gè)體交叉，交叉點(diǎn)隨機(jī)確定。個(gè)體編號(hào)個(gè)體隨機(jī)數(shù)交叉操作新個(gè)體1110110000.728110110002101010110.58910101011101010013001011000.678001011004100011010.8011000110110001111……………交叉概率pc=McM式中M——群體中142.5基本位變異算子

基本位變異算子是最簡單和最基本的變異操作算子。對(duì)于基本遺傳算法中用二進(jìn)制編碼符號(hào)串所表示的個(gè)體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?，反之，若原有基因值為1，則變異操作將其變?yōu)?。

基本位變異因子的具體執(zhí)行過程是：

Ⅰ.對(duì)個(gè)體的每一個(gè)基因座，依變異概率pm指定其為變異點(diǎn)。

Ⅱ.對(duì)每一個(gè)指定的變異點(diǎn)，對(duì)其基因值做取反運(yùn)算或用其它等位基因值來代替，從而產(chǎn)生出一個(gè)新的個(gè)體。

基本位變異運(yùn)算的示例如下所示：

A：1010101010A’：1010001010

變異點(diǎn)基本位變異2.5基本位變異算子變異點(diǎn)基本位變異15變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，因此變異概率pm

也是針對(duì)基因而言，即：式中B——每代中變異的基因數(shù)目；M——每代中群體擁有的個(gè)體數(shù)目

l——個(gè)體中基因串長度。Pm=BM·l

變異概率變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因16[變異操作示例]變異字符的位置是隨機(jī)確定的，如下表所示。某群體有3個(gè)個(gè)體，每個(gè)體含4個(gè)基因。針對(duì)每個(gè)個(gè)體的每個(gè)基因產(chǎn)生一個(gè)[0,1]區(qū)間具有3位有效數(shù)字的均勻隨機(jī)數(shù)。假設(shè)變異概率pm=0.01，則隨機(jī)數(shù)小于0.01的對(duì)應(yīng)基因值產(chǎn)生變異。表中3號(hào)個(gè)體的第4位的隨機(jī)數(shù)為0.001，小于0.01，該基因產(chǎn)生變異，使3號(hào)個(gè)體由0010變?yōu)?011。其余基因的隨機(jī)數(shù)均大于0.01，不產(chǎn)生變異。[變異操作示例]17開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體中各個(gè)體適應(yīng)度從左至右依次執(zhí)行遺傳算子j=0j=0j=0根據(jù)適應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)執(zhí)行變異執(zhí)行交叉執(zhí)行復(fù)制將復(fù)制的個(gè)體添入新群體中將交叉后的兩個(gè)新個(gè)體添入新群體中將變異后的個(gè)體添入新群體中j=j+1j=j+2j=j+1

j=M?

j=pc·M?

j=pm·L·M?Gen=Gen+1輸出結(jié)果終止YNYYYNNNpcpm2.6算法流程圖開始Gen=0編碼隨機(jī)產(chǎn)生M個(gè)初始個(gè)體滿足終止條件?計(jì)算群體183基本遺傳算法應(yīng)用舉例——基本遺傳算法在函數(shù)優(yōu)化中的應(yīng)用。

[例]Rosenbrock函數(shù)的全局最大值計(jì)算。

maxf(x1,x2)=100(x12-x22)2+(1-x1)2s.t.-2.048≤xi≤2.048(xi=1,2)如圖所示：該函數(shù)有兩個(gè)局部極大點(diǎn)，分別是:f(2.048,-2048)=3897.7342和f(-2.048,-2.0048)=3905.9262其中后者為全局最大點(diǎn)。3基本遺傳算法應(yīng)用舉例——基本遺傳算法在函數(shù)優(yōu)化中的應(yīng)19下面介紹求解該問題的遺傳算法的構(gòu)造過程：第一步：確定決策變量及其約束條件。

s.t.-2.048≤xi≤2.048(xi=1,2)第二步：建立優(yōu)化模型。maxf(x1,x2)=100(x12-x22)2+(1-x1)2第三步；確定編碼方法。用長度為l0位的二進(jìn)制編碼串來分別表示二個(gè)決策變量x1,x2。lO位二進(jìn)制編碼串可以表示從0到1023之間的1024個(gè)不同的數(shù)，故將x1,x2的定義域離散化為1023個(gè)均等的區(qū)域，包括兩個(gè)端點(diǎn)在內(nèi)共有1024個(gè)不同的離散點(diǎn)。從離散點(diǎn)-2.048到離散點(diǎn)2.048，依次讓它們分別對(duì)應(yīng)于從0000000000(0)到1111111111(1023)之間的二進(jìn)制編碼。再將分別表示x1和x2的二個(gè)10位長的二進(jìn)制編碼串連接在一起，組成一個(gè)20位長的二進(jìn)制編碼串，它就構(gòu)成了這個(gè)函數(shù)優(yōu)化問題的染色體編碼方法。例如X：00001101111101110001就表示一個(gè)個(gè)體的基因型。下面介紹求解該問題的遺傳算法的構(gòu)造過程：20第四步：確定解碼方法。

解碼時(shí)先將20位長的二進(jìn)制編碼串切斷為二個(gè)10位長的二進(jìn)制編碼串，然后分別將它們轉(zhuǎn)換為對(duì)應(yīng)的十進(jìn)制整數(shù)代碼，分別記為y1和y2。依據(jù)前述個(gè)體編碼方法相對(duì)定義域的離散化方法可知，將代碼yi轉(zhuǎn)換為變量xi的解碼公式為：例如，對(duì)前述個(gè)體X：00001101111101110001它由這樣的兩個(gè)代碼所組成：y1=55y2=881經(jīng)上式的解碼處理后，得到：x1=-1.828x2=1.476xi=4.096yi

10