遺傳算法綜合

1、遺傳算法綜合遺傳算法綜合1 1 1 1 1 1 1 1 1 1 0 1 1 1 2 6 0 0 1 0 0 1 1 0個體（染色體）個體（染色體） 00100110 表現型表現型 2 6編碼解碼基因遺傳算法是一種基于種群的，迭代的元啟遺傳算法是一種基于種群的，迭代的元啟發(fā)式優(yōu)化算法發(fā)式優(yōu)化算法0001100000 0101111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）個體

2、染色體適值選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174個體染色體適值選擇概率累積概率1000110000082010111100153000000010

3、124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000在0-1之間產生隨機數：個體染色體適應度選擇概率累積概率10001100000820101111

4、00153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.

5、5078930.2911980.7163400.2709010.3714350.854641淘汰！淘汰！0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 00010100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100001011

6、010110111100001001110100000110011101001100000001101010100010100100110.7553610.3215460.5689220.9251400.1542320001010110 1111011011 1100000100 1001110100 10101010111110100000 1000010110 1001110001 1100000001 00010100100001010110 1111011011 1100000100 1001100100 10101010111110100000 1000010110 10010100

7、01 1100000001 01010100001122334410011002999997ffffffff選擇壓力小，差別選擇壓力小，差別小，選優(yōu)功能弱化小，選優(yōu)功能弱化0254444433422411ffffffffffff選擇壓力大，差別放選擇壓力大，差別放大，選優(yōu)功能強化了大，選優(yōu)功能強化了Fafb1a minbf minFff1a maxbfmaxFff kkFa fb1ka minkkkbf minkkFff1ka maxkkkbfmaxkkFff kkkkM0rkk1999. 0 , 9 . 0rkFflnFafbbfFaecwFaffwfminfwfminmaxminffrFf

8、frkkFa fbrffakminmax1minmaxminkfrbffr1iiNPiifPf1(1)iiPqq1111111iNPNPiqqqq 11jjqqpNPqqq11個體12345678910適應度2.01.81.61.41.21.00.80.60.40.2選擇概率0.180.160.150.130.110.090.070.060.030.02累計概率0.180.340.490.620.730.820.890.950.981.00個體12345678910適應度2.01.81.61.41.21.00.80.60.40.2選擇概率0.180.160.150.130.110.090.07

9、0.060.030.02累計概率0.180.340.490.620.730.820.890.950.981.00設定設定n為需要選擇的個體數為需要選擇的個體數目，等距離選擇個體，選擇目，等距離選擇個體，選擇指針的距離為指針的距離為1n。第一個。第一個指針的位置由指針的位置由0，ln區(qū)間區(qū)間的均勻隨機數決定。如圖所的均勻隨機數決定。如圖所示，需要選擇示，需要選擇6個個體，指個個體，指針間的距離為針間的距離為l60.167，第一個指針的隨機位置為第一個指針的隨機位置為0.1，按這種選擇方法被選中作為按這種選擇方法被選中作為交配集個體為：交配集個體為：1，2，3，4，6，8。 編號 價 格 飲 料

10、速 度二進制表示 1 高 可樂 快 011 2 高 酒 快 001 3 低 可樂 慢 110 4 高 可樂 慢 010表表1 1 飯店問題的表示方案（其中的飯店問題的表示方案（其中的4 4個）個）l初始種群初始種群群體規(guī)模群體規(guī)模N N4 4 第0代 i 串xi 適應值f（xi） 1 011 3 2 001 1 3 110 6 4 010 2 總和 12 最小值 1 平均值 3.00 最大值 6表表2 2 初始群體中經營決策的適應值初始群體中經營決策的適應值（2 2）適應度函數）適應度函數 第0代 交配池 i 串xi適應值f（xi） F(xi) / f(xi) 串 f（xi） 1 011 3

11、0.25 011 3 2 001 1 0.08 110 6 3 110 6 0.50 110 6 4 010 2 0.17 010 2 總和 12 17 最小值 1 2 平均值 3.00 4.25 最大值 6 6表3 使用復制算子后產生的交配池-選適應度高的選適應度高的（3-13-1）復制算子復制算子：采用賭盤選擇：采用賭盤選擇(3-2) (3-2) 雜交算子雜交算子：采用一點雜交：采用一點雜交l作用過程：作用過程：a a）產生一個在）產生一個在1 1到到l1 1之間的隨機數之間的隨機數i i b b）配對的兩個串相互對應的交換從）配對的兩個串相互對應的交換從i i1 1到到l l的位段的位段

12、例如：從交配池中選擇編號為1和2的串進行配對，且雜交點選在2（用分隔符| |表示），雜交算子作用的結果為： 01 | 1 010 11 | 0 111對交配池中指定百分比的個體應用雜交算子，假設雜交概率pc50，交配池中余下的50個體僅進行復制運算，即復制概率pr50。 第 0 代 交 配 池 第 1 代 i串xi適應值f(xi)F(xi)/ f(xi) 串 f(xi)雜交點 xiF(xi) 1 011 3 0.25 011 3 2010 2 2 001 1 0.08 110 6 2111 7 3 110 6 0.50 110 6 110 6 4 010 2 0.17 010 2 010 2

13、總和 12 17 17最小值 1 2 2 平均值 3.00 4.25 4.25最大值 6 6 7表表4 4 使用使用復制和復制和雜交雜交算子算子的作用結果的作用結果 很小的概率pm隨機改變染色體串上的某些位 對二進制串，就是將相應位上的0變?yōu)?或將1變?yōu)?例如：選交配池中編號為4的串進行變異，且變異點在2，則 010 000l變異算子相對而言，是變異算子相對而言，是次要算子次要算子，但在恢，但在恢復群體中失去的多樣性方面具有潛在的作用。復群體中失去的多樣性方面具有潛在的作用。(3-3)(3-3)變異算子：采用一點變異變異算子：采用一點變異l 上述遺傳算法描述了從第上述遺傳算法描述了從第0 0代

14、產生第代產生第1 1代的代的過程，然后遺傳算法過程，然后遺傳算法迭代迭代地執(zhí)行這個過程，地執(zhí)行這個過程，直到滿足某個直到滿足某個停止準則停止準則。l 在每一代中，算法首先計算群體中每個個在每一代中，算法首先計算群體中每個個體地適應值，然后利用適應值信息，遺傳算體地適應值，然后利用適應值信息，遺傳算法分別法分別以概率以概率p pc c、p pr r 和和p pm m 執(zhí)行復制、雜交和執(zhí)行復制、雜交和變異操作變異操作，從而產生新的群體。，從而產生新的群體。 （4）控制算法運行的參數）控制算法運行的參數 例：求下述二元函數的最大值：例：求下述二元函數的最大值： max f(x1,x2) = x12+

15、x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 解題時不是直接找最大解題時不是直接找最大max f，而是尋找哪，而是尋找哪對對（ x1, x2 ）產生產生max f 。l 遺傳算法的運算對象是表示個體的符號串，遺傳算法的運算對象是表示個體的符號串，必須把變量必須把變量x1,x2x1,x2編碼為一種符號串編碼為一種符號串。l 用用3位位無符號二進制整數來表示無符號二進制整數來表示x，則，則x1, x2連接在連接在一起組成一起組成6位無符號二進制數，形成個體的基因型，位無符號二進制數，形成個體的基因型，表示一個可行解。表示一個可行解。 例例. 基因型基因型 X

16、101110 的表現型是的表現型是x 5,6 l 個體的表現型個體的表現型x和基因型和基因型X之間可通過之間可通過編碼和解碼編碼和解碼程序相互轉換。程序相互轉換。x1, x2 1,2,3,4,5,6,7 遺傳算法是對群體進行的進化操作，需要給遺傳算法是對群體進行的進化操作，需要給其淮備一些表示其淮備一些表示起始搜索點起始搜索點的初始群體數據的初始群體數據。 本例中，群體規(guī)模的大小取為本例中，群體規(guī)模的大小取為4，即群體由，即群體由4個個體組成，每個個體可通過個個體組成，每個個體可通過隨機隨機方法方法產生產生。 例如：例如：011101，101011，011100，111001v 怎么從這怎么從

17、這4個個體產生出許多新個體個個體產生出許多新個體 遺傳算法以個體適應度的大小來評定其優(yōu)劣遺傳算法以個體適應度的大小來評定其優(yōu)劣程度，從而決定其遺傳機會的大小。程度，從而決定其遺傳機會的大小。本例是求目標函數本例是求目標函數(=0)最大值為優(yōu)化目標，最大值為優(yōu)化目標，故直接利用故直接利用目標函數值目標函數值作為個體的適應度。作為個體的適應度。 （運算）運算）選擇運算把當前群體中選擇運算把當前群體中適應度較高的個體適應度較高的個體按按某種規(guī)則或模型某種規(guī)則或模型遺傳到下一代遺傳到下一代群體中。群體中。一般要求一般要求適應度較高適應度較高的個體將有的個體將有更多的機會更多的機會遺傳到下一代群體中。遺

18、傳到下一代群體中。 本例采用本例采用及適應度成正比的概率及適應度成正比的概率來確定各來確定各個個體復制到下一代群體中的數量。具體：個個體復制到下一代群體中的數量。具體： 計算出群體中所有個體的計算出群體中所有個體的適應度的總和適應度的總和 fi ( i=1.2,M ); 計算每個計算每個個體的相對適應度的大小個體的相對適應度的大小 fi / fi ，即每個個體被即每個個體被遺傳遺傳到下一代群體中的到下一代群體中的概率概率，每個概率值組成一個區(qū)域，全部概率值之和每個概率值組成一個區(qū)域，全部概率值之和為為1； 最后再產生一個最后再產生一個0到到1之間的之間的隨機數隨機數，依據該，依據該隨機數出現在

19、上述隨機數出現在上述哪一個概率區(qū)域哪一個概率區(qū)域內來確定內來確定各個個體被選中的次數。各個個體被選中的次數。0124%24%17%35%1#2#3#4#個體編個體編號號初始群體初始群體p(0)適值適值占總數的占總數的百分比百分比總和1234011101101011011100111001343425500.240.240.170.351431 選擇選擇次數次數選擇選擇結果結果1102011101111001101011111001(不對應不對應) x1 x23 55 33 47 1f(x1,x2)=x12+x22落入 交叉運算是遺傳算法中交叉運算是遺傳算法中產生新個體產生新個體的主要的主要操作

20、過程，它以某一操作過程，它以某一概率相互交換概率相互交換某兩個個某兩個個體之間體之間的部分的部分染色體。染色體。 本例采用單點交叉的方法，具體操作過程：本例采用單點交叉的方法，具體操作過程： 先對群體進行隨機配對；先對群體進行隨機配對； 其次隨機設置交叉點位置；其次隨機設置交叉點位置； 最后再相互交換配對染色體之間的部分基因。最后再相互交換配對染色體之間的部分基因。選擇結果選擇結果01 110111 10011010 111110 01配對情況配對情況 交叉點位置交叉點位置個體編號個體編號12341-23-41-2：23-4：4交叉結果交叉結果011001 111101101001111011

21、可以看出，新個體可以看出，新個體“111101”、“111011”的的適應度較原來兩個個體的適應度都要高：適應度較原來兩個個體的適應度都要高：f2=49+25, f4=49+9f(x1,x2)=x12+x22 變異運算是對個體的變異運算是對個體的某一個或某一些某一個或某一些基因座基因座上的基因值按某一上的基因值按某一較小的概率較小的概率進行改變，它進行改變，它也是產生新個體也是產生新個體的一種操作方法。的一種操作方法。 本例采用基本位變異的方法來進行變異運算：本例采用基本位變異的方法來進行變異運算： 確定出各個個體的基因確定出各個個體的基因變異位置變異位置，下表所示，下表所示為為隨機隨機產生的變異點位置，其中的數字表示產生的變異點位置，其中的數字表示變異點設置在該基因座處；變異點設置在該基因座處； 依照某一依照某一概率概率將變異點的原有將變異點的原有基因值取反基因值取反。l對群體對群體P(t)進行一輪進行一輪選擇、交叉、變異選擇、交叉、變異運運算之后可得到新一代的群體算之后可得到新一代的群體p(t+1)。個體編號個體編號1234交叉結果交叉結果011001 111101101001111011變異結果變異結果變異點變異