基本遺傳算法ppt課件

1、種特例。種特例。1.1 根本遺傳算法的構(gòu)成要素根本遺傳算法的構(gòu)成要素 (1) 染色體編碼方法染色體編碼方法根本遺傳算法運用固定長度的二進根本遺傳算法運用固定長度的二進制符號串來表示群體中的個體，其等位制符號串來表示群體中的個體，其等位基基來由二值符號集來由二值符號集0，1組成。組成。初始群體中各個個體的基因值用均初始群體中各個個體的基因值用均勻分布的隨機數(shù)來生成。如：勻分布的隨機數(shù)來生成。如： x；100111001000101101就可表示一個個體，該個體的染色體就可表示一個個體，該個體的染色體長度是長度是 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 其中，其中， 為二進制編碼的編碼精度，其公式為：為二進制編碼的編碼精度，其公式為： = Umax umin2l 1 (2) 解碼解碼 假設(shè)某一個體的編碼是：假設(shè)某一個體的編碼是： x： bl bl-1 bl-2b2b1 那么對應(yīng)的解碼公式為：那么對應(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 上述輪盤選擇過程，可描畫如下：上述輪盤選擇過程，可描畫如下： . 順序累計群體內(nèi)各個體的順應(yīng)度，得相應(yīng)的累計值順序累計群體內(nèi)各個體的順應(yīng)度，得相應(yīng)的累計值Si，最后一個累計值為，最后一個累計值為Sn； . 在在0, Sn區(qū)間內(nèi)產(chǎn)生均勻分布的隨機數(shù)區(qū)間內(nèi)產(chǎn)生均勻分布的隨機數(shù)r； . 依次用依次用Si與與r比較，第一個出現(xiàn)比較，第一個出現(xiàn)Si大于或等于大于或等于r的個體的個體j被選為復(fù)制對象；被選為復(fù)制對象； . 反復(fù)反復(fù) 、 項，直至新群體的個體數(shù)目等于父代群體的規(guī)模。項，直至新群體的個體數(shù)目等于父代群體的規(guī)模。論盤選擇例如論盤選擇例如單點

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

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

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

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

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

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

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

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