1、1遺傳算法(GA)的肇始“ 活的有機體是解決問題的專家。它們所表現出來的各種才能足以使最好的計算機程序自慚形穢。這種現象尤其令計算機科學家們感到痛楚。計算機科學家們為了某種算法可能花費數月乃至數年的腦力勞動，而有機體則能通過進化和自然選擇這樣一種顯然并非定向進行的機制獲得這種能力。” - John Holland2遺傳算法的思想 Darwin的進化論 - “自然選擇、適者生存” 特定環境的考驗 種群中個體的選擇選擇 種群中的交叉交叉繁殖 種群中個體的變異變異 上述操作反復執行，個體逐漸優化3 為更好地理解遺傳算法的運算過程，下面用手工計算來簡單地模擬遺傳算法的各為更好地理解遺傳算法的運算過程，

2、下面用手工計算來簡單地模擬遺傳算法的各 個主要執行步驟。個主要執行步驟。 例：求下述二元函數的最大值：例：求下述二元函數的最大值： max f(x1,x2)=x12+x22 s.t. x1 1,2,3,4,5,6,7 x2 1,2,3,4,5,6,7 遺傳算法的運算對象是表示個體的符號串，所以必須把變量遺傳算法的運算對象是表示個體的符號串，所以必須把變量 x1, x2 編碼為一種編碼為一種 符號串。符號串。本題中，用無符號二進制整數來表示。本題中，用無符號二進制整數來表示。 因因 x1, x2 為為 0 7之間的整數，所以分別用之間的整數，所以分別用3位無符號二進制整數來表示，將它位無符號二進

3、制整數來表示，將它 們連接在一起所組成的們連接在一起所組成的6位無符號二進制數就形成了個體的基因型，表示一個可位無符號二進制數就形成了個體的基因型，表示一個可 行解。行解。 例如，基因型例如，基因型 X101110 所對應的表現型是：所對應的表現型是：x 5，6 。 個體的表現型個體的表現型x和基因型和基因型X之間可通過編碼和解碼程序相互轉換。之間可通過編碼和解碼程序相互轉換。4 遺傳算法是對群體進行的進化操作，需要給其淮備一些表示起始搜索點的初始遺傳算法是對群體進行的進化操作，需要給其淮備一些表示起始搜索點的初始 群體數據。群體數據。 本例中，群體規模的大小取為本例中，群體規模的大小取為4，

4、即群體由，即群體由4個個體組成，每個個體可通過隨機個個體組成，每個個體可通過隨機 方法產生。方法產生。 如：如：011101，101011，011100，111001 遺傳算法中以個體適應度的大小來評定各個個體的優劣程度，從而決定其遺傳遺傳算法中以個體適應度的大小來評定各個個體的優劣程度，從而決定其遺傳 機會的大小。機會的大小。 本例中，目標函數總取非負值，并且是以求函數最大值為優化目標，故可直接本例中，目標函數總取非負值，并且是以求函數最大值為優化目標，故可直接 利用目標函數值作為個體的適應度。利用目標函數值作為個體的適應度。 選擇運算選擇運算(或稱為復制運算或稱為復制運算)把當前群體中適應

5、度較高的個體按某種規則或模型把當前群體中適應度較高的個體按某種規則或模型遺傳到下一代群體中。一般要求適應度較高的個體將有更多的機會遺傳到下一代遺傳到下一代群體中。一般要求適應度較高的個體將有更多的機會遺傳到下一代 群體中。群體中。 5 本例中，我們采用與適應度成正比的概率來確定各個個體復制到下一代群體中本例中，我們采用與適應度成正比的概率來確定各個個體復制到下一代群體中 的數量。其具體操作過程是：的數量。其具體操作過程是： 先計算出群體中所有個體的適應度的總和先計算出群體中所有個體的適應度的總和 fi ( i=1.2,M ); 其次計算出每個個體的相對適應度的大小其次計算出每個個體的相對適應度

6、的大小 fi / fi ，它即為每個個體被遺傳，它即為每個個體被遺傳 到下一代群體中的概率，到下一代群體中的概率， 每個概率值組成一個區域，全部概率值之和為每個概率值組成一個區域，全部概率值之和為1； 最后再產生一個最后再產生一個0到到1之間的隨機數，依據該隨機數出現在上述哪一個概率區之間的隨機數，依據該隨機數出現在上述哪一個概率區 域內來確定各個個體被選中的次數。域內來確定各個個體被選中的次數。0124%24%17%35%1#2#3#4#個體編號個體編號初始群體初始群體p(0)適值適值占總數的百分比占總數的百分比總和總和123401110110101101110011100134342550

7、0.240.240.170.351431選擇次數選擇次數選擇結果選擇結果1102011101111001101011111001 x1 x2 3 5 5 3 3 4 7 16 交叉運算是遺傳算法中交叉運算是遺傳算法中產生新個體產生新個體的主要操作過程，它以某一概率相互交換某的主要操作過程，它以某一概率相互交換某 兩個個體之間的部分染色體。兩個個體之間的部分染色體。 本例采用單點交叉的方法，其具體操作過程是：本例采用單點交叉的方法，其具體操作過程是： 先對群體進行隨機配對；先對群體進行隨機配對； 其次隨機設置交叉點位置；其次隨機設置交叉點位置； 最后再相互交換配對染色體之間的部分基因。最后再相互

8、交換配對染色體之間的部分基因。選擇結果選擇結果01 110111 10011010 111110 01配對情況配對情況交叉點位置交叉點位置個體編號個體編號12341-23-41-2：23-4：4交叉結果交叉結果011001 111101101001111011 可以看出，其中新產生的個體可以看出，其中新產生的個體“111101”、“111011”的適應度較原來兩個個的適應度較原來兩個個體體 的適應度都要高。的適應度都要高。7 變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進變異運算是對個體的某一個或某一些基因座上的基因值按某一較小的概率進 行改變，它行改變，它也是產生新個體也

9、是產生新個體的一種操作方法。的一種操作方法。 本例中，我們采用基本位變異的方法來進行變異運算，其具體操作過程是：本例中，我們采用基本位變異的方法來進行變異運算，其具體操作過程是： 首先確定出各個個體的基因變異位置，下表所示為隨機產生的變異點位置，首先確定出各個個體的基因變異位置，下表所示為隨機產生的變異點位置， 其中的數字表示變異點設置在該基因座處；其中的數字表示變異點設置在該基因座處； 然后依照某一概率將變異點的原有基因值取反。然后依照某一概率將變異點的原有基因值取反。對群體對群體P(t)進行一輪選擇、交叉、變異運算之后可得到新一代的群體進行一輪選擇、交叉、變異運算之后可得到新一代的群體p(

10、t+1)。個體編號個體編號1234交叉結果交叉結果011001 111101101001111011變異結果變異結果變異點變異點4526011101 111111111001111010子代群體子代群體p(1)011101 1111111110011110108 從上表中可以看出，群體經過一代進化之后，其適應度的最大值、平均值都得從上表中可以看出，群體經過一代進化之后，其適應度的最大值、平均值都得 到了明顯的改進。事實上，這里已經找到了最佳個體到了明顯的改進。事實上，這里已經找到了最佳個體“111111”。 需要說明的是，表中有些欄的數據是隨機產生的。這里為了更好地說明問題，需要說明的是，表中

11、有些欄的數據是隨機產生的。這里為了更好地說明問題， 我們特意選擇了一些較好的數值以便能夠得到較好的結果，而在實際運算過程中我們特意選擇了一些較好的數值以便能夠得到較好的結果，而在實際運算過程中 有可能需要一定的循環次數才能達到這個最優結果。有可能需要一定的循環次數才能達到這個最優結果。個體編號個體編號子群體子群體p(1)適值適值占總數的百分比占總數的百分比總和總和1234011101 111111111001111010349850530.140.420.210.232351 x1 x2 3 5 7 7 7 1 7 29個體編號個體編號初始群體初始群體p(0) 適值適值fi(x1,x2)占總數

12、的百分比占總數的百分比fi / f1234011101101011011100111001343425500.240.240.170.35 x1 x2 3 5 5 3 3 4 7 1 fi=143fmax=50f=35.75選擇結果選擇結果011101111001101011111001配對情況配對情況交叉點位置交叉點位置1-23-41-2：23-4：4交叉結果交叉結果011001 111101101001111011選擇次數選擇次數1102變異結果變異結果變異點變異點4526011101 111111111001111010子代群體子代群體p(1) 適值適值fi(x1,x2)占總數的百分比占

13、總數的百分比fi / f011101 111111111001111010349850530.140.420.210.23 x1 x2 3 5 7 7 7 1 7 2 fi=253fmax=98f=58.7510遺傳算法的一個實例 求解方程：將方程求解問題轉化為生存問題：解一定在0,10之間，將區間0,10劃分成若干個小區間，設想每個小區間為一個生物個體，使下列表達式最小的個體有 最好的生存能力，該個體即為解。10010 xex)0( x|100|10 xex11遺傳算法的一個實例 如何找到這個最優個體？ 可通過 Darwin 的進化論由初始個體經過代代演化，逐漸進化出來。 如何將生物進化的操

14、作轉化為計算機可以執行的操作？ 通過編碼表征生物個體，則生物之間的演化轉化為編碼的變化。12步驟一：初始化 個體編碼：(假定要求小數點后兩位) 將0,10劃分為1024個小區間 個體 1 0000000000 個體 2 0000000001 個體 3 0000000010 個體 1024 1111111111 種群初始化： 隨機生成m個10位二進制串102421001013 定義適應度函數： 選擇（適應度較大的個體） 步驟二：選擇|100|110 xexf為何取倒數？0.10.30.20.40.10.10.30.40.20.60.41.0ABCD隨機產生0,1之間的數 RN，選擇個體 RN個體

15、ABCD1 . 00 RN4 . 01 . 0 RN6 . 04 . 0 RN16 . 0 RN14 選中的優勢個體進行交叉 - 由父個體生成子個體步驟三：交叉相同的兩個父個體生成相同的兩個子個體15 變異操作 在個體中隨機選擇一位，改變該位的值步驟四：變異交叉和變異操作均以一定概率進行16 反復執行步驟二、三、四并記錄最優個體（適應度最大的個體） 程序結束時，最優個體即為所求解 程序結束的判定 根據循環次數 根據最大適應度 根據種群中相同個體數與總個體數的比值步驟五17遺傳算法各步驟的評價 選擇 - 優勝劣汰 選擇操作為種群提供了演進的方向 交叉 - 優優組合 交叉操作的作用在于匯集散布于不

16、同 個體間的局部優勢模式 變異 - 尋找新模式 變異操作是種群向外擴展的觸角(隨機) 好的變異將保留，壞的淘汰18遺傳算法的總體評價 優點 解決問題的方法具有普適性 全局收斂性（依概率收斂） 能解決的問題范圍很廣 不足 求得的解為近似的數值解 對于經典數學可以解決的問題，效率較低19遺傳算法的適應度函數求函數的全局極小值取 的初始區間，例如：-10,10將此區間分為1024個小區間，然后編碼若求全局極大值(且為正)，可直接取函數值為其適應度值，據此作概率選擇；若求全局極小值(且為正)，可取函數值的倒數為其適應度值，據此作概率選擇。若不全為負，可統一加上一個正數，使為正。)(41)(10sin(

17、)80sin(sin()sin(70sin()60sin()50exp(sin(22yxyxyxexyyx,20TSP問題的遺傳算法求解 步驟一：個體編碼及種群初始化 步驟二：適應度選擇 步驟三：交叉操作 步驟四：變異操作 步驟五：重復二、三、四步，直至結束 令城市(點)數目為 N21 個體編碼 取長度為N的數字串，串中數字互不重復，取值范圍為1,N之間的整數。則每一個數字串代表一個個體，個體中數字出現的位置表征路徑中城市出現的順序。 初始種群 令種群中有 M 個個體，可隨機產生 M 個數字 串構成初始種群。例如： 將數字串 1234N 上的數字進行隨機的交換步驟一：初始化22 適應度的計算步

18、驟二：適應度選擇123451l2l3l4l5lNiijlf11對于個體 ，適應度為：j被選中作為父個體的概率：Mjjjjffp11jp選擇選擇 M 次次重新生成種群重新生成種群23 TSP中交叉算子的特點 要保證生成的解為有效解 從一個父個體中隨機選取一段子串A，在另一個父個體中將A中出現的數字去掉形成串B，AB為一個子串步驟三：交叉操作此外還有多種交叉算子24 常用的變異操作： 隨機選取兩個相鄰位置的數字，交換其順序。 51243(5) 51234(5)步驟四：變異操作1234512345交換3,4此外還有多種變異算子25 反復執行步驟二、三、四 結束判定 循環執行 G 次 (例如 G=50

19、0) 后 當最優個體的總路徑長度小于預期時步驟五：26中國各省會城市的運行結果2712345 缺陷：相同父個體生成不同的子個體 以下是相同個體： 12345(1) 54321(5) 反射操作 12345(1) 34512(3) 旋轉操作交叉算子的進一步研究用群論描述 所有路徑的集合形成一個二面體群 A 等價解構成一個正規子群 B A 中陪集的數目為 2N2812345(1) 32154(3) 相同父個體交叉34215(3) 15234(1) 不同子個體，且和父個體不同12345123451234529 簡單實例簡單實例產生初始種群產生初始種群1.計算適應度計算適應度 0001100000 01

20、01111001 0000000101 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011（8） （5） （2） （10） （7）（12） （5） （19） （10） （14）30 簡單實例簡單實例選擇選擇 個體個體染色體染色體適應度適應度選擇概率選擇概率累積概率累積概率100011000008201011110015300000001012410011101001051010101010761110010110127100101101158110000000119910011101001010

21、00010100111488521071251910140.08695758521071251910140.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.15217431 簡單實例簡單實例選擇選擇 個體個體染色體染色體適應度適應度選擇概率選擇概率累積概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.

22、0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.00000032 簡單實例簡單實例選擇選擇在在01之間產生一個之間產生一個3.隨機數：隨機數： 個體個體染色體染色體適應度適應度選擇概率選擇概率累積概率累積概率10001100000820101111001530000000101241001110100105101010101076111001

23、01101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000000.0702210.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641淘汰

24、！淘汰！淘汰！淘汰！330001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011 簡單實例簡單實例4.交叉交叉 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1001110100 1100000001 000101001100011110100000010110111100001011010110111100001001110100

25、0001100111010011000000011010101000101001001134 簡單實例簡單實例5.變異變異 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100110001100000 1110010110 11000000

26、01 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001135 問題的提出問題的提出 一元函數求最大值：一元函數求最大值： 2 , 1 0 . 2)10sin()(xxxxf36 問題的提出問題的提出 用微分法求取用微分法求取f(x)的最大值：的最大值： 解有無窮多個：解有無窮多個： xxxxxxf1

27、0)10tan( 0)10cos(10)10sin()( 即的實數遞減序列。一接近于是及，0), 2, 1, 2 , 1( , 2, 1 ,2012 0 , 2 , 1 ,20120iiiixxiixiiiii37 問題的提出問題的提出 當當i為奇數時為奇數時xi對應局部極大值點，對應局部極大值點，i為偶數時為偶數時xi對應對應局部極小值。局部極小值。x19即為區間即為區間-1,2內的最大值點：內的最大值點： 此時，函數最大值此時，函數最大值f(x19)比比f(1.85)=3.85稍大。稍大。 19191985. 12037x38 編碼編碼 表現型：表現型：x 基因型：二進制編碼（串長取決于求解精度）基因型：二進制編碼（串長取決于求解精度） 串長與精度之間的關系串長與精度之間的關系： 若要求求解精度到若要求求解精度到6位小數，區間長度為位小數，區間長度為2-(-1)3，即需將區間分為即需將區間分為3/0.000001=3106等份。等份。 所以編碼的二進制串長應為所以編碼的二進制串長應為22位。位。 41943042300000022097152222139 產生初始種群產生初始種群 產生的方式：隨機產生的方式：隨機 產生的結果：長度為產生的結果：長度為22的二進制串的二進制串