基本遺傳算法ppt課件

1、種特例。種特例。1.1 根本遺傳算法的構(gòu)成要素根本遺傳算法的構(gòu)成要素 (1) 染色體編碼方法染色體編碼方法根本遺傳算法運(yùn)用固定長(zhǎng)度的二進(jìn)根本遺傳算法運(yùn)用固定長(zhǎng)度的二進(jìn)制符號(hào)串來表示群體中的個(gè)體，其等位制符號(hào)串來表示群體中的個(gè)體，其等位基基來由二值符號(hào)集來由二值符號(hào)集0，1組成。組成。初始群體中各個(gè)個(gè)體的基因值用均初始群體中各個(gè)個(gè)體的基因值用均勻分布的隨機(jī)數(shù)來生成。如：勻分布的隨機(jī)數(shù)來生成。如： x；100111001000101101就可表示一個(gè)個(gè)體，該個(gè)體的染色體就可表示一個(gè)個(gè)體，該個(gè)體的染色體長(zhǎng)度是長(zhǎng)度是 l18。Procedure GABegin initialize P(0); t=0

2、; while (t=T) do for i=1 to M do Evaluate fitness of P(t); end for for i=1 to M do Select operation to P(t); end for for i=1 to M/2 do Crossover operation to P(t); end for for i=1 to M do Mutation operation to P(t); end for for i=1 to M do P(t+1) = P(t); end for t=t+1 end whileend x = umin + ( bi 2i

3、-1 ) 1 1i=lUmax umin2l 1 其中，其中， 為二進(jìn)制編碼的編碼精度，其公式為：為二進(jìn)制編碼的編碼精度，其公式為： = Umax umin2l 1 (2) 解碼解碼 假設(shè)某一個(gè)體的編碼是：假設(shè)某一個(gè)體的編碼是： x： bl bl-1 bl-2b2b1 那么對(duì)應(yīng)的解碼公式為：那么對(duì)應(yīng)的解碼公式為：例例 設(shè)設(shè) -3.0 x 12.1 , 精度要求精度要求 =1/10000，由公式：，由公式： Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001 即：即： 217 151001 00 if f(X)+Cmin 0F(X) =Cmax - f(X)

4、 if f(X) Cmax0 if f(X) Cmax 上述輪盤選擇過程，可描畫如下：上述輪盤選擇過程，可描畫如下： . 順序累計(jì)群體內(nèi)各個(gè)體的順應(yīng)度，得相應(yīng)的累計(jì)值順序累計(jì)群體內(nèi)各個(gè)體的順應(yīng)度，得相應(yīng)的累計(jì)值Si，最后一個(gè)累計(jì)值為，最后一個(gè)累計(jì)值為Sn； . 在在0, Sn區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)區(qū)間內(nèi)產(chǎn)生均勻分布的隨機(jī)數(shù)r； . 依次用依次用Si與與r比較，第一個(gè)出現(xiàn)比較，第一個(gè)出現(xiàn)Si大于或等于大于或等于r的個(gè)體的個(gè)體j被選為復(fù)制對(duì)象；被選為復(fù)制對(duì)象； . 反復(fù)反復(fù) 、 項(xiàng)，直至新群體的個(gè)體數(shù)目等于父代群體的規(guī)模。項(xiàng)，直至新群體的個(gè)體數(shù)目等于父代群體的規(guī)模。論盤選擇例如論盤選擇例如單點(diǎn)

5、交叉單點(diǎn)交叉A；10110111 00 A：10110111 11B：00011100 11 B：00011100 00 交叉概率交叉概率 pc = McM 式中式中 M群體中個(gè)體的數(shù)目；群體中個(gè)體的數(shù)目； Mc群體中被交換個(gè)體的數(shù)目。群體中被交換個(gè)體的數(shù)目。交叉操作例如交叉操作例如 交叉的個(gè)體是隨機(jī)確定的，如下表所示。某群體有交叉的個(gè)體是隨機(jī)確定的，如下表所示。某群體有n個(gè)個(gè)體，每個(gè)個(gè)體含個(gè)個(gè)體，每個(gè)個(gè)體含8 個(gè)等位基因。針對(duì)每個(gè)個(gè)體產(chǎn)生一個(gè)個(gè)等位基因。針對(duì)每個(gè)個(gè)體產(chǎn)生一個(gè)0, 1 區(qū)間的均勻隨機(jī)數(shù)。假設(shè)交叉概率區(qū)間的均勻隨機(jī)數(shù)。假設(shè)交叉概率 pc = 0.6，那么隨機(jī)數(shù)小于，那么隨機(jī)數(shù)小于

6、0.6的對(duì)應(yīng)個(gè)體與其隨機(jī)確定的另一個(gè)個(gè)體交叉，的對(duì)應(yīng)個(gè)體與其隨機(jī)確定的另一個(gè)個(gè)體交叉，交叉交叉 點(diǎn)隨機(jī)確定。點(diǎn)隨機(jī)確定。個(gè)體編號(hào)個(gè)體編號(hào)個(gè)體個(gè)體隨機(jī)數(shù)隨機(jī)數(shù)交叉操作交叉操作新個(gè)體新個(gè)體1110110000.728110110002101010110.589101010 11101010 013001011000.678001011004100011010.801100011 01100011 11變異點(diǎn)變異點(diǎn)根本位變異根本位變異 變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，因此變異概率變異是針對(duì)個(gè)體的某一個(gè)或某一些基因座上的基因值執(zhí)行的，因此變異概率pm 也是針對(duì)基因此言，即：也是針

7、對(duì)基因此言，即：式中式中 B每代中變異的基因數(shù)目；每代中變異的基因數(shù)目； M每代中群體擁有的個(gè)體數(shù)目每代中群體擁有的個(gè)體數(shù)目 l個(gè)體中基因串長(zhǎng)度。個(gè)體中基因串長(zhǎng)度。Pm = B M l 變異操作例如變異操作例如 變異字符的位置是隨機(jī)確定的，如下表所示。某群體有變異字符的位置是隨機(jī)確定的，如下表所示。某群體有3個(gè)個(gè)體，每個(gè)體含個(gè)個(gè)體，每個(gè)體含4 個(gè)基因。針對(duì)每個(gè)個(gè)體的每個(gè)基因產(chǎn)生一個(gè)個(gè)基因。針對(duì)每個(gè)個(gè)體的每個(gè)基因產(chǎn)生一個(gè)0, 1 區(qū)間具有區(qū)間具有3位有效數(shù)字的均位有效數(shù)字的均 勻隨機(jī)數(shù)。假設(shè)變異概率勻隨機(jī)數(shù)。假設(shè)變異概率 pm = 0.01，那么隨機(jī)數(shù)小于，那么隨機(jī)數(shù)小于0.01的對(duì)應(yīng)基因值產(chǎn)生

8、的對(duì)應(yīng)基因值產(chǎn)生變變 異。表中異。表中3號(hào)個(gè)體的第號(hào)個(gè)體的第4位的隨機(jī)數(shù)為位的隨機(jī)數(shù)為0.001，小于，小于0.01，該基因產(chǎn)生變異，該基因產(chǎn)生變異， 使使3號(hào)個(gè)體由號(hào)個(gè)體由 0010 變?yōu)樽優(yōu)?0011 。其他基因的隨機(jī)數(shù)均大于。其他基因的隨機(jī)數(shù)均大于0.01，不產(chǎn)生變異。，不產(chǎn)生變異。開開場(chǎng)場(chǎng)Gen=0編碼編碼隨機(jī)產(chǎn)生隨機(jī)產(chǎn)生M個(gè)初始個(gè)體個(gè)初始個(gè)體滿足終止條件滿足終止條件?計(jì)算群體中各個(gè)體順應(yīng)度計(jì)算群體中各個(gè)體順應(yīng)度從左至右依次執(zhí)行遺傳算子從左至右依次執(zhí)行遺傳算子j = 0j = 0j = 0根據(jù)順應(yīng)度選擇復(fù)制個(gè)體根據(jù)順應(yīng)度選擇復(fù)制個(gè)體選擇兩個(gè)交叉?zhèn)€體選擇兩個(gè)交叉?zhèn)€體選擇個(gè)體變異點(diǎn)選擇個(gè)體

9、變異點(diǎn)執(zhí)行變異執(zhí)行變異執(zhí)行交叉執(zhí)行交叉執(zhí)行復(fù)制執(zhí)行復(fù)制將復(fù)制的個(gè)體添入將復(fù)制的個(gè)體添入新群體中新群體中將交叉后的兩個(gè)新個(gè)體將交叉后的兩個(gè)新個(gè)體添入新群體中添入新群體中將變異后的個(gè)體添入將變異后的個(gè)體添入新群體中新群體中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1輸出結(jié)果輸出結(jié)果終終止止YNYYYNNNpcpm如下圖：如下圖：該函數(shù)有兩個(gè)部分極大點(diǎn)，該函數(shù)有兩個(gè)部分極大點(diǎn)，分別是分別是: f(2.048, -2048)=3897.7342 和和 f(-2.048,-2.0048)=3905.9262其中后者為全局最大點(diǎn)。其中后者

10、為全局最大點(diǎn)。例如，對(duì)前述個(gè)體例如，對(duì)前述個(gè)體 X： 0000110111 11011 10001 它由這樣的兩個(gè)代碼所組成：它由這樣的兩個(gè)代碼所組成： y1= 55 y2 = 881 經(jīng)上式的解碼處置后，得到：經(jīng)上式的解碼處置后，得到： x1= -1.828 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2) 第五步：確定個(gè)體評(píng)價(jià)方法。第五步：確定個(gè)體評(píng)價(jià)方法。 由式由式 f(x1,x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函數(shù)的值域函數(shù)的值域總是非負(fù)的，并且優(yōu)化目的是求函數(shù)的最大值，故這里可將個(gè)體

11、的順應(yīng)度直接總是非負(fù)的，并且優(yōu)化目的是求函數(shù)的最大值，故這里可將個(gè)體的順應(yīng)度直接取為對(duì)應(yīng)的目的函數(shù)值，并且不再對(duì)它作其他變換處置，即有：取為對(duì)應(yīng)的目的函數(shù)值，并且不再對(duì)它作其他變換處置，即有： F(x) = f(x1,x2)第六步：設(shè)計(jì)遺傳算子。第六步：設(shè)計(jì)遺傳算子。 選擇運(yùn)算運(yùn)用比例選擇算子；選擇運(yùn)算運(yùn)用比例選擇算子； 交叉運(yùn)算運(yùn)用單點(diǎn)交叉算子；交叉運(yùn)算運(yùn)用單點(diǎn)交叉算子； 變異運(yùn)算運(yùn)用根本位變異算子。變異運(yùn)算運(yùn)用根本位變異算子。第七步：確定遺傳算法的運(yùn)轉(zhuǎn)參數(shù)。第七步：確定遺傳算法的運(yùn)轉(zhuǎn)參數(shù)。 對(duì)于本例，設(shè)定根本遺傳算法的運(yùn)轉(zhuǎn)參數(shù)如下：對(duì)于本例，設(shè)定根本遺傳算法的運(yùn)轉(zhuǎn)參數(shù)如下： 群體大小群體大

12、小: M80 終止代數(shù)終止代數(shù): T200 交叉概率：交叉概率：pc0.6 變異概率：變異概率：pm0.001 以下圖為其進(jìn)化過程例如及運(yùn)轉(zhuǎn)結(jié)果。以下圖為其進(jìn)化過程例如及運(yùn)轉(zhuǎn)結(jié)果。 圖中兩條曲線分別為各代群體中個(gè)體順應(yīng)度的最大值和平均值。圖中兩條曲線分別為各代群體中個(gè)體順應(yīng)度的最大值和平均值。(a)以下圖所示分別為初始群體、第以下圖所示分別為初始群體、第5代群體、第代群體、第10代群體和第代群體和第100代群體中個(gè)體的分布情況。代群體中個(gè)體的分布情況。 在圖在圖(a)中各個(gè)個(gè)體分布得比較均勻。中各個(gè)個(gè)體分布得比較均勻。 在圖在圖(b)中大量的個(gè)體分布在最優(yōu)點(diǎn)和次最優(yōu)點(diǎn)附近。中大量的個(gè)體分布在最優(yōu)點(diǎn)和次最優(yōu)點(diǎn)附近。(b)從圖從圖(c) 中可以看出，次最優(yōu)點(diǎn)也被淘汰。中可以看出，次最優(yōu)點(diǎn)也被淘汰。(c)從圖從圖(d)中可以看出，個(gè)體更加集中在最優(yōu)點(diǎn)附近。中可以看出，個(gè)體更加集中在最優(yōu)點(diǎn)附近。(d) 由該組圖我們可以看出，隨著進(jìn)化過程的進(jìn)展，群體中順應(yīng)度較低的一些個(gè)體由該組圖我們可以看出，隨著進(jìn)化過程的進(jìn)展，群體中順應(yīng)度較低的一些個(gè)體被逐漸淘汰掉，而順應(yīng)度較高的一些個(gè)領(lǐng)會(huì)越來越多并且它們都集中在所求