基本遺傳算法PPT學習教案

1、會計學1基本遺傳算法基本遺傳算法 基本遺傳算法基本遺傳算法為正確計算這個概率，這里要求所有個體的適應為正確計算這個概率，這里要求所有個體的適應 度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預先確定好由目標函數(shù)度必須為正數(shù)或零。這樣，根據(jù)不同種類的問題，必須預先確定好由目標函數(shù) 值到個體適應度之間的轉換規(guī)則，特別是要預先確定好當目標函數(shù)值為負數(shù)時值到個體適應度之間的轉換規(guī)則，特別是要預先確定好當目標函數(shù)值為負數(shù)時 的處理方法。的處理方法。 基本遺傳算法使用下述三種遺傳算子：基本遺傳算法使用下述三種遺傳算子： 選擇運算：使用選擇運算：使用； 交叉運算：使用交叉運算：使用； 變異運算：使用變異運

2、算：使用。 基本遺傳算法有下述基本遺傳算法有下述4個運行參數(shù)需要提前設定：個運行參數(shù)需要提前設定： ：群體大小，即群體中所含個體的數(shù)量，一般取為：群體大小，即群體中所含個體的數(shù)量，一般取為20 100。 ：遺傳運算的終止進化代數(shù)，一般取為：遺傳運算的終止進化代數(shù)，一般取為100 500 ：交叉概率，一般取為：交叉概率，一般取為0. ： 第1頁/共56頁 這這4個運行參數(shù)對遺傳算法的求解結果和求解效率都有一定的影響，但目個運行參數(shù)對遺傳算法的求解結果和求解效率都有一定的影響，但目前前 尚無合理選擇它們的理論依據(jù)。在遺傳算法的實際應用中，往往需要經(jīng)過多次尚無合理選擇它們的理論依據(jù)。在遺傳算法的實際

3、應用中，往往需要經(jīng)過多次試試 算后才能確定出這些參數(shù)合理的取值大小或取值范圍。算后才能確定出這些參數(shù)合理的取值大小或取值范圍。 基本遺傳算法可定義為一個基本遺傳算法可定義為一個7元組：元組： M群體大??；群體大小； F個體適應度評價函數(shù)；個體適應度評價函數(shù)； s選擇操作算于；選擇操作算于； c交叉操作算子：交叉操作算子： m變異操作算于；變異操作算于； pc交叉概率；交叉概率； pm變異概率；變異概率；第2頁/共56頁Procedure GABegin initialize P(0); t=0; while (t=T) do for i=1 to M do Evaluate fitness o

4、f 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第3頁/共56頁 根據(jù)上面對基本遺傳算法構成要素的分析和算法描述，我們可以很方便地用根據(jù)上面對基本遺傳算法構成要素的分析和算法描述，我們可以

5、很方便地用計計 算機語言來實現(xiàn)這個基本遺傳算法。算機語言來實現(xiàn)這個基本遺傳算法。 現(xiàn)對具體實現(xiàn)過程中的問題作以下說明：現(xiàn)對具體實現(xiàn)過程中的問題作以下說明： 假設某一參數(shù)的取值范圍是假設某一參數(shù)的取值范圍是umin , umax，用長度為，用長度為l的二進制編碼符號串來的二進制編碼符號串來表示該參數(shù)，則它總共能夠產(chǎn)生表示該參數(shù)，則它總共能夠產(chǎn)生 2l種不同的編碼，參數(shù)編碼時的對應關系如下種不同的編碼，參數(shù)編碼時的對應關系如下： 00000000000000000 umin 00000000000000011 umin + 00000000000000102 umin + 2 1111111111

6、111111=2l1 umax 第4頁/共56頁 x = umin + ( bi 2i-1 ) 1 1i=lUmax umin2l 1 其中，其中， 為二進制編碼的編碼精度，其公式為：為二進制編碼的編碼精度，其公式為： = Umax umin2l 1 假設某一個體的編碼是：假設某一個體的編碼是： x： bl bl-1 bl-2b2b1 則對應的解碼公式為：則對應的解碼公式為：第5頁/共56頁 Umax umin2l =+ 11/1000012.1 + 3.0+ 1= 151001151001 即：即： 217 151001 00 if f(X)+Cmin 0F(X) =Cmax - f(X)

7、if f(X) Cmax0 if f(X) Cmax 第8頁/共56頁 從當前代群體中選擇出一些比較優(yōu)良的個體，并將其復制到下一代群體中。從當前代群體中選擇出一些比較優(yōu)良的個體，并將其復制到下一代群體中。 ： 比例選擇算子。比例選擇算子。 指個體被選中并遺傳到下一代群體中的概率與該個體的適應度大小成正比。指個體被選中并遺傳到下一代群體中的概率與該個體的適應度大小成正比。 輪盤法的基本精神是：個體被選中的概率取決于個體的相對適應度：輪盤法的基本精神是：個體被選中的概率取決于個體的相對適應度： pi = fi / fi ( i=1,2,M ) 式中式中 pi個體個體i被選中的概率；被選中的概率；

8、fi個體個體i的適應度；的適應度； fi群體的累加適應度。群體的累加適應度。 顯然，個體適應度愈高，被選中的概率愈大。但是，適應度小的個體也有可顯然，個體適應度愈高，被選中的概率愈大。但是，適應度小的個體也有可 能被選中，以便增加下一代群體的多樣性。能被選中，以便增加下一代群體的多樣性。第9頁/共56頁 圖中指針固定不動，外圈的圓環(huán)可圖中指針固定不動，外圈的圓環(huán)可以以 自由轉動，自由轉動， 圓環(huán)上的刻度代表各個個圓環(huán)上的刻度代表各個個 體的適應度。當圓環(huán)旋轉若干圈后停體的適應度。當圓環(huán)旋轉若干圈后停止，止， 指針指定的位置便是被選中的個體。指針指定的位置便是被選中的個體。 從統(tǒng)計意義講，適應度

9、大的個體，從統(tǒng)計意義講，適應度大的個體，其其 刻度長，被選中的可能性大；反之，刻度長，被選中的可能性大；反之，適適 應度小的個體被選中的可能性小，但應度小的個體被選中的可能性小，但有有 時也會被時也會被“破格破格”選中。選中。第10頁/共56頁 上述輪盤選擇過程，可描述如下：上述輪盤選擇過程，可描述如下： . 順序累計群體內(nèi)各個體的適應度，得相應的累計值順序累計群體內(nèi)各個體的適應度，得相應的累計值Si，最后一個累計值為，最后一個累計值為Sn； . 在在0, Sn區(qū)間內(nèi)產(chǎn)生均勻分布的隨機數(shù)區(qū)間內(nèi)產(chǎn)生均勻分布的隨機數(shù)r； . 依次用依次用Si與與r比較，第一個出現(xiàn)比較，第一個出現(xiàn)Si大于或等于大于

10、或等于r的個體的個體j被選為復制對象；被選為復制對象； . 重復重復 、 項，直至新群體的個體數(shù)目等于父代群體的規(guī)模。項，直至新群體的個體數(shù)目等于父代群體的規(guī)模。論盤選擇示例論盤選擇示例第11頁/共56頁 通過交叉，子代的基因值不同于父代。交換是遺傳算法產(chǎn)生新個體的主要手通過交叉，子代的基因值不同于父代。交換是遺傳算法產(chǎn)生新個體的主要手段。正是有了交換操作，群體的性態(tài)才多種多樣。段。正是有了交換操作，群體的性態(tài)才多種多樣。單點交叉算子。單點交叉算子。 . 對群體中的個體進行兩兩對群體中的個體進行兩兩隨機隨機配對。配對。 若群體大小為若群體大小為M，則共有，則共有 M/2 對相互對相互 配對的個

11、體組。配對的個體組。 . 每一對相互配對的個體，每一對相互配對的個體，隨機隨機設置某一基因座之后的位置為交叉點。設置某一基因座之后的位置為交叉點。 若染色體的長度為若染色體的長度為l ，則共有，則共有(l-1)個可能的交個可能的交叉點位置。叉點位置。 . 對每一對相互配對的個體，依設定的交叉概率對每一對相互配對的個體，依設定的交叉概率pc在其在其交交叉點處相互交換兩個叉點處相互交換兩個個個 體的部分染色體，從而產(chǎn)生出兩個新的個體。體的部分染色體，從而產(chǎn)生出兩個新的個體。 單點交叉運算的示單點交叉運算的示例例如下所示如下所示: 單點交叉單點交叉A；10110111 00 A：10110111 1

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

13、定的另一個個體交叉，交叉叉 點隨機確定。點隨機確定。個體編號個體編號個體個體隨機數(shù)隨機數(shù)交叉操作交叉操作新個體新個體1110110000.728110110002101010110.589101010 11101010 013001011000.678001011004100011010.801100011 01100011 11第13頁/共56頁 對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操對于基本遺傳算法中用二進制編碼符號串所表示的個體，若需要進行變異操作作 的某一基因座上的原有基因值為的某一基因座上的原有基因值為0，則變異操作將該基因值變?yōu)?，則變異操作將該基因值變?yōu)?/p>

14、1，反之，若原，反之，若原有有 基因值為基因值為1，則變異操作將其變?yōu)?，則變異操作將其變?yōu)?。 . 對個體的每一個基因座，依變異概率對個體的每一個基因座，依變異概率pm指定其為變異點。指定其為變異點。 . 對每一個指定的變異點，對其基因值做取反運算或用其它等位基因值來代替對每一個指定的變異點，對其基因值做取反運算或用其它等位基因值來代替， 從而產(chǎn)生出一個新的個體。從而產(chǎn)生出一個新的個體。 基本位變異運算的示例如下所示：基本位變異運算的示例如下所示： A：1010 1 01010 A：1010 0 01010 變異點變異點基本位變異基本位變異第14頁/共56頁 變異是針對個體的某一個或某一些基因

15、座上的基因值執(zhí)行的，因此變異概率變異是針對個體的某一個或某一些基因座上的基因值執(zhí)行的，因此變異概率pm 也是針對基因而言，即：也是針對基因而言，即：式中式中 B每代中變異的基因數(shù)目；每代中變異的基因數(shù)目； M每代中群體擁有的個體數(shù)目每代中群體擁有的個體數(shù)目 l個體中基因串長度。個體中基因串長度。Pm = B M l 第15頁/共56頁變異操作示例變異操作示例 變異字符的位置是隨機確定的，如下表所示。某群體有變異字符的位置是隨機確定的，如下表所示。某群體有3個個體，每個體含個個體，每個體含4 個基因。針對每個個體的每個基因產(chǎn)生一個個基因。針對每個個體的每個基因產(chǎn)生一個0, 1 區(qū)間具有區(qū)間具有3

16、位有效數(shù)字的均位有效數(shù)字的均 勻隨機數(shù)。假設變異概率勻隨機數(shù)。假設變異概率 pm = 0.01，則隨機數(shù)小于，則隨機數(shù)小于0.01的對應基因值產(chǎn)生的對應基因值產(chǎn)生變變，該基因產(chǎn)生變異，該基因產(chǎn)生變異， 使使3號個體由號個體由 0010 變?yōu)樽優(yōu)?0011 。其余基因的隨機數(shù)均大于。其余基因的隨機數(shù)均大于0.01，不產(chǎn)生變異，不產(chǎn)生變異。第16頁/共56頁開開始始Gen=0編碼編碼隨機產(chǎn)生隨機產(chǎn)生M個初始個體個初始個體滿足終止條件滿足終止條件?計算群體中各個體適應度計算群體中各個體適應度從左至右依次執(zhí)行遺傳算子從左至右依次執(zhí)行遺傳算子j = 0j = 0j = 0根據(jù)適應度選擇復制個體根據(jù)適應度

17、選擇復制個體選擇兩個交叉?zhèn)€體選擇兩個交叉?zhèn)€體選擇個體變異點選擇個體變異點執(zhí)行變異執(zhí)行變異執(zhí)行交叉執(zhí)行交叉執(zhí)行復制執(zhí)行復制將復制的個體添入將復制的個體添入新群體中新群體中將交叉后的兩個新個體將交叉后的兩個新個體添入新群體中添入新群體中將變異后的個體添入將變異后的個體添入新群體中新群體中j = j+1j = j+2j = j+1 j = M? j = pcM? j = pmLM?Gen=Gen+1輸出結果輸出結果終終止止YNYYYNNNpcpm第17頁/共56頁。 例例 Rosenbrock函數(shù)的全局最大值計算。函數(shù)的全局最大值計算。 max f(x1,x2) = 100 (x12-x22)2 +

18、 (1-x1)2 s.t. -2.048 xi 2.048 (xi=1,2)如圖所示：如圖所示：該函數(shù)有兩個局部極大點該函數(shù)有兩個局部極大點，分別是分別是: 和和 其中后者為全局最大點。其中后者為全局最大點。第18頁/共56頁：確定決策變量及其約束條件。：確定決策變量及其約束條件。 s.t. -2.048 xi 2.048 (xi=1,2)建立優(yōu)化模型。建立優(yōu)化模型。 max f(x1,x2) = 100 (x12-x22)2 + (1-x1)2確定編碼方法。確定編碼方法。 用長度為用長度為l0l0位的二進制編碼串來分別表示二個決策變量位的二進制編碼串來分別表示二個決策變量x x1 1,x,x

19、2 2。 lOlO位二進制編碼串可以表示從位二進制編碼串可以表示從0 0到到10231023之間的之間的10241024個不同的數(shù)，故將個不同的數(shù)，故將x x1 1,x,x2 2的定義域離散化為的定義域離散化為10231023個均等的區(qū)域，包括兩個端點在內(nèi)共有個均等的區(qū)域，包括兩個端點在內(nèi)共有10241024個不同的個不同的離散點。從離散點離散點。從離散點-2.048-2.048到離散點到離散點2.0482.048，依次讓它們分別，依次讓它們分別對應于從對應于從0000000000(0)到到1111111111(1023)之間的二進制編碼。再將分別表示之間的二進制編碼。再將分別表示x x1 1

20、和和x x2 2的二個的二個10位長的二進制編碼串連接在一起，組成一個位長的二進制編碼串連接在一起，組成一個20位長的二進制編碼串位長的二進制編碼串，它就構成了這個函數(shù)優(yōu)化問題的染色體編碼方法。例如，它就構成了這個函數(shù)優(yōu)化問題的染色體編碼方法。例如 X：0000110111 11011 10001 就表示一個個體的基因型。就表示一個個體的基因型。第19頁/共56頁確定解碼方法。確定解碼方法。 解碼時先將解碼時先將20位長的二進制編碼串切斷為二個位長的二進制編碼串切斷為二個10位長的二進制編碼串，然位長的二進制編碼串，然后分別將它們轉換為對應的十進制整數(shù)代碼，分別記為后分別將它們轉換為對應的十進

21、制整數(shù)代碼，分別記為y1和和y2。 依據(jù)前述個體編碼方法相對定義域的離散化方法可知，將代碼依據(jù)前述個體編碼方法相對定義域的離散化方法可知，將代碼yi轉換為變轉換為變量量xi的解碼公式為：的解碼公式為：例如，對前述個體例如，對前述個體 X： 0000110111 11011 10001 它由這樣的兩個代碼所組成：它由這樣的兩個代碼所組成： y1= 55 y2 = 881 經(jīng)上式的解碼處理后，得到：經(jīng)上式的解碼處理后，得到： x1 x2= 1.476 xi = 4.096 yi 1023 2.048 ( i = 1,2)第20頁/共56頁 確定個體評價方法。確定個體評價方法。 由式由式 f(x1,

22、x2) = 100 (x12-x22)2 + (1-x1)2 可知，可知， Rosenbrock函數(shù)的值域函數(shù)的值域總是非負的，并且優(yōu)化目標是求函數(shù)的最大值，故這里可將個體的適應度直接總是非負的，并且優(yōu)化目標是求函數(shù)的最大值，故這里可將個體的適應度直接取為對應的目標函數(shù)值，并且不再對它作其他變換處理，即有：取為對應的目標函數(shù)值，并且不再對它作其他變換處理，即有： F(x) = f(x1,x2)設計遺傳算子。設計遺傳算子。 選擇運算使用比例選擇算子；選擇運算使用比例選擇算子； 交叉運算使用單點交叉算子；交叉運算使用單點交叉算子； 變異運算使用基本位變異算子。變異運算使用基本位變異算子。確定遺傳算法的運行參數(shù)。確定遺傳算法的運行參數(shù)。 對于本例，設定基本遺傳算法的運行參數(shù)如下：對于本例，設定基本遺傳算法的運行參數(shù)如下： 群體大小群體大小: M80 終止代數(shù)終止代數(shù): T200 交叉概率：交叉概率：pc 變異概率：變異概率：pm第21頁/共56頁 下圖為其進化過程示例及運行結果。下圖為其進化過程示例及運行結果。 圖中兩條曲線分別為各代群體中個體適應度的最大值和平均值圖中兩條曲線分別為各代群體中個體適應度的最大值和平均值。第22頁/共56頁(a)下圖所示分別為初始群體