經(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)點(diǎn),遺傳算法（GA）模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個(gè)體，利用遺傳算子(選擇、交叉和變異)對(duì)這些個(gè)體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。其遺傳進(jìn)化操作過程簡單，容易理解。,遺傳算法基本原理,1、基本思想 模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索

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

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

4、的概率很低.,GA流程,簡單遺傳算法（GA）的基本參數(shù),種群規(guī)模 P: 參與進(jìn)化的染色體總數(shù). 代溝G: 二代之間不相同的染色體數(shù)目,無重疊G = 1;有重疊 0 G 1 選擇方法: 轉(zhuǎn)輪法,精英選擇法,競爭法. 交換率: Pc 一般為60100%. 變異率: Pm 一般為0.110%,實(shí)例,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、計(jì)算適應(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)生一個(gè) 隨機(jī)數(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)度計(jì)算選擇交叉變異，直至滿足終止條件。,遺傳算法的應(yīng)用及一些問題,1、遺傳算法的應(yīng)用領(lǐng)域,（1）組合優(yōu)化 （2）函數(shù)優(yōu)化 （3）自動(dòng)控制 （4）生產(chǎn)調(diào)度 （5）圖像處理 （6）機(jī)器學(xué)習(xí) （7）人工生命 （8）數(shù)據(jù)挖掘,2、遺傳算法在應(yīng)用中的一些問題,1）知識(shí)的編碼,二進(jìn)制和十進(jìn)制的比較：二進(jìn)制有更多圖式和更大的搜