1、遺傳算法原理與應用SN:SNO:主要內容遺傳算法基本原理2遺傳算法概述1 遺傳算法的應用及一些問題31、優化方法遺傳算法概述傳統的優化方法（局部優化） 共軛梯度法、擬牛頓法、單純形方法全局優化方法 GA、漫步法（Random Walk）、模擬退火法 2、遺傳算法優點 遺傳算法（GA）模擬自然選擇和自然遺傳過程中發生的繁殖、交叉和基因突變現象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進行組合，產生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。其遺傳進化操作過程簡單，容易理解。 遺傳算法基本原理1、基本思想 模擬自然界優

2、勝劣汰的進化現象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量染色體，向量的每個元素稱為基因。 通過不斷計算各染色體的適應值，選擇最好的染色體，獲得最優解。2、遺傳算法的基本運算 選擇運算 交換操作 變異選擇運算 從舊的種群中選擇適應度高的染色體，放入匹配集（緩沖區），為以后染色體交換、變異，產生新的染色體作準備。選擇方法適應度比例法（轉輪法）某染色體被選的概率：Pcxi 為種群中第i個染色體，f(xi )為第i個染色體的適應度值。具體步驟1）計算各染色體適應度值2）累計所有染色體適應度值，記錄中間累加值S - mid 和最后累加值 sum = f(xi)3）產生一個隨機數 N，0 N

3、sum4）選擇對應中間累加值S - mid 的第一個染色體進入交換集5） 重復（3）和（4），直到獲得足夠的染色體。舉例：具有6個染色體的二進制編碼、適應度值、Pc累計值。 染色體的適應度和所占的比例用轉輪方法進行選擇染色體被選的概率染色體編號 1 2 3 4 5 6 7 8 910適應度 8 217 7 212117 3 7被選概率0.10.020.220.090.020.160.140.090.030.09適應度累計 8 10 27 34 36485966 6976被選的染色體個數隨機數23497613 1 2757所選染色體號碼 3 710 3 1 3 7交換操作 方法:隨機選擇二個染色

4、體(雙親染色體),隨機指定一點或多點, 進行交換,可得二個新的染色體(子輩染色體).新的子輩染色體: A 11010001 B 01011110變異 模擬生物在自然界環境變化,引起基因的突變.在染色體二進制編碼中,1變成0;或0變成1.突變產生染色體的多樣性,避免進化中早期成熟,陷入局部極值點,突變的概率很低.GA流程簡單遺傳算法（GA）的基本參數種群規模 P: 參與進化的染色體總數.代溝G: 二代之間不相同的染色體數目,無重疊G = 1;有重疊 0 G 1選擇方法: 轉輪法,精英選擇法,競爭法.交換率: Pc 一般為60100%.變異率: Pm 一般為0.110%實例1、產生初始種群0001

5、100000 0101111001 0000000101 1001110100 1010101010（8） （5） （2） （10） （7） 1110010110 1001011011 1100000001 1001110100 000101001 （12） （5） （19） （10） （14）2、計算適應度3、選擇個體染色體適應度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111

6、488521071251910140.0869570.05434858521071251910140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521743、選擇個體染色體適應度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870

7、.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.0000003、選擇在01之間產生一個隨機數：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641個體染色體適應度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271

8、001011011581100000001199100111010010100001010011140.0869570.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰4、交叉 0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 100111

9、0100 1100000001 00010100110001100000 1110010110 1100000001 1001110100 00011110100000010110111100001011010110111100001001110100000110011101001100000001101010100010100100115、變異0001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 0001010011000111101000000101

10、10111100001011010110111100001001110100000110011101001100000001101010100010100100110001100000 1110010110 1100000001 1001110100 10101010101110010110 1001011011 1100000001 1001110100 000101001100011110100000010110111100001011010110111100001001010100000110011101001100000001101010100010100100116、至下一代，適應度計算選擇交叉變異，直至滿足終止條件。遺傳算法的應用及一些問題1、遺傳算法的應用領域（1）組合優化 （2）函數優化 （3）自動控制 （4）生產調度 （5）圖像處理 （6）機器學習 （7）人工生命 （8）數據