經(jīng)典遺傳算法原理與應(yīng)用PPT.ppt

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

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

3、sum,4）選擇對應(yīng)中間累加值S - mid 的第一個染色體進入交換集,5） 重復(fù)（3）和（4），直到獲得足夠的染色體。,舉例：具有6個染色體的二進制編碼、適應(yīng)度值、Pc累計值。,染色體的適應(yīng)度和所占的比例,用轉(zhuǎn)輪方法進行選擇,染色體被選的概率,被選的染色體個數(shù),交換操作,方法:隨機選擇二個染色體(雙親染色體),隨機指定一點或多點, 進行交換,可得二個新的染色體(子輩染色體).,新的子輩染色體: A 11010001 B 01011110,變異,模擬生物在自然界環(huán)境變化,引起基因的突變.在染色體二進制編碼中,1變成0;或0變成1.突變產(chǎn)生染色體的多樣性,避免進化中早期成熟,陷入局部極值點,突變

4、的概率很低.,GA流程,簡單遺傳算法（GA）的基本參數(shù),種群規(guī)模 P: 參與進化的染色體總數(shù). 代溝G: 二代之間不相同的染色體數(shù)目,無重疊G = 1;有重疊 0 G 1 選擇方法: 轉(zhuǎn)輪法,精英選擇法,競爭法. 交換率: Pc 一般為60100%. 變異率: Pm 一般為0.110%,實例,1、產(chǎn)生初始種群,0001100000 0101111001 0000000101 1001110100 1010101010 （8） （5） （2） （10） （7） 1110010110 1001011011 1100000001 1001110100 000101001 （12） （5） （19）

5、（10） （14）,2、計算適應(yīng)度,3、選擇,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,3、選擇,0.086957,0.054348,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.086957,0.141304,0.163043,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,3、

6、選擇,在01之間產(chǎn)生一個 隨機數(shù)：,0.545929,0.784567,0.446930,0.507893,0.291198,0.716340,0.270901,0.371435,0.854641,0.086957,0.086957,0.054348,0.141304,0.021739 0.108696 0.076087 0.130435 0.054348 0.206522 0.108696 0.152174,0.271739 0.347826 0.478261 0.532609 0.739130 0.847826 1.000000,0.163043,4、交叉,0001100000 11100

7、10110 1100000001 1001110100 1010101010 1110010110 1001011011 1001110100 1100000001 0001010011,0001100000 1110010110 1100000001 1001110100,0001,1110,100000,010110,111,100,0010110,1011011,110000,100111,0100,0001,1001110100,1100000001,1010101,0001010,010,011,5、變異,6、至下一代，適應(yīng)度計算選擇交叉變異，直至滿足終止條件。,遺傳算法的應(yīng)用及一些問題,1、遺傳算法的應(yīng)用領(lǐng)域,（1）組合優(yōu)化 （2）函數(shù)優(yōu)化 （3）自動控制 （4）生產(chǎn)調(diào)度 （5）圖像處理 （6）機器學(xué)習(xí) （7）人工生命 （8）數(shù)據(jù)挖掘,2、遺傳算法在應(yīng)用中的一些問題,1）知識的編碼,二進制和十進制的比較：二進制有更多圖式和更大的搜