遺傳算法原理與應(yīng)用SN:SNO:經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第1頁!主要內(nèi)容遺傳算法基本原理2遺傳算法概述1遺傳算法的應(yīng)用及一些問題3經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第2頁!1、優(yōu)化方法遺傳算法概述傳統(tǒng)的優(yōu)化方法（局部優(yōu)化）共軛梯度法、擬牛頓法、單純形方法全局優(yōu)化方法

GA、漫步法（RandomWalk）、模擬退火法

經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第3頁!2、遺傳算法優(yōu)點

遺傳算法（GA）模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。其遺傳進(jìn)化操作過程簡單，容易理解。

經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第4頁!選擇運算

從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體作準(zhǔn)備。選擇方法——適應(yīng)度比例法（轉(zhuǎn)輪法）某染色體被選的概率：Pcxi為種群中第i個染色體，f(xi)為第i個染色體的適應(yīng)度值。經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第5頁!舉例：

⒈具有6個染色體的二進(jìn)制編碼、適應(yīng)度值、Pc累計值。

染色體的適應(yīng)度和所占的比例用轉(zhuǎn)輪方法進(jìn)行選擇經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第6頁!交換操作

方法:隨機(jī)選擇二個染色體(雙親染色體),隨機(jī)指定一點或多點,進(jìn)行交換,可得二個新的染色體(子輩染色體).新的子輩染色體:A’11010001

B’01011110經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第7頁!GA流程經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第8頁!實例1、產(chǎn)生初始種群00011000000101111001000000010110011101001010101010（8）（5）（2）（10）（7）

1110010110100101101111000000011001110100000101001（12）（5）（19）（10）（14）2、計算適應(yīng)度經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第9頁!3、選擇個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0543480.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.0869570.1413040.1630430.2717390.3478260.4782610.5326090.7391300.8478261.000000經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第10頁!4、交叉000110000011100101101100000001100111010010101010101110010110100101101110011101001100000001000101001100011000001110010110110000000110011101000001111010000001011011110000101101011011110000100111010000011001110100110000000110101010001010010011經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第11頁!6、至下一代，適應(yīng)度計算→選擇→交叉→變異，直至滿足終止條件。經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第12頁!

2）適應(yīng)度函數(shù)

適應(yīng)度函數(shù)值必須非負(fù)，根據(jù)情況做適當(dāng)?shù)奶幚怼?/p>

經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第13頁!3）全局最優(yōu)和收斂性。

根據(jù)圖式定理，對于具有“欺騙性”函數(shù)，GA有可能落入局部最優(yōu)點。舉例：3位欺騙函數(shù)經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第14頁!遺傳算法基本原理1、基本思想

模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量——染色體，向量的每個元素稱為基因。通過不斷計算各染色體的適應(yīng)值，選擇最好的染色體，獲得最優(yōu)解。2、遺傳算法的基本運算⑴選擇運算⑵交換操作⑶變異經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第15頁!具體步驟1）計算各染色體適應(yīng)度值2）累計所有染色體適應(yīng)度值，記錄中間累加值S-mid和最后累加值sum=∑f(xi)3）產(chǎn)生一個隨機(jī)數(shù)N，0〈N〈sum4）選擇對應(yīng)中間累加值S-mid的個染色體進(jìn)入交換集5）重復(fù)（3）和（4），直到獲得足夠的染色體。經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第16頁!染色體被選的概率染色體編號12345678910適應(yīng)度8217721211737被選概率0.10.020.220.090.020.160.140.090.030.09適應(yīng)度累計8

10

2734364859666976被選的染色體個數(shù)隨機(jī)數(shù)2349761312757所選染色體號碼37103137經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第17頁!變異模擬生物在自然界環(huán)境變化,引起基因的突變.在染色體二進(jìn)制編碼中,1變成0;或0變成1.突變產(chǎn)生染色體的多樣性,避免進(jìn)化中早期成熟,陷入局部極值點,突變的概率很低.經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第18頁!簡單遺傳算法（GA）的基本參數(shù)①種群規(guī)模P:參與進(jìn)化的染色體總數(shù).②代溝G:二代之間不相同的染色體數(shù)目,無重疊G=1;有重疊0<G<1③選擇方法:轉(zhuǎn)輪法,精英選擇法,競爭法.④交換率:Pc一般為60~100%.⑤變異率:Pm一般為0.1~10%經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第19頁!3、選擇個體染色體適應(yīng)度選擇概率累積概率10001100000820101111001530000000101241001110100105101010101076111001011012710010110115811000000011991001110100101000010100111488＋5＋2＋10＋7＋12＋5＋19＋10＋140.0869570.05434858＋5＋2＋10＋7＋12＋5＋19＋10＋140.0217390.1086960.0760870.1304350.0543480.2065220.1086960.152174經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第20頁!3、選擇在0～1之間產(chǎn)生一個隨機(jī)數(shù)：0.5459290.7845670.4469300.5078930.2911980.7163400.2709010.3714350.854641個體染色體適應(yīng)度選擇概率累積概率1000110000082010111100153000000010124100111010010510101010107611100101101271001011011581100000001199100111010010100001010011140.0869570.0869570.0543480.1413040.0217390.1086960.0760870.1304350.0543480.2065220.1086960.1521740.2717390.3478260.4782610.5326090.7391300.8478261.0000000.163043淘淘汰經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第21頁!5、變異0001100000111001011011000000011001110100101010101011100101101001011011110000000110011101000001010011000111101000000101101111000010110101101111000010011101000001100111010011000000011010101000101001001100011000001110010110110000000110011101001010101010111001011010010110111100000001100111010000010100110001111010000001011011110000101101011011110000100101010000011001110100110000000110101010001010010011經(jīng)典遺傳算法原理與應(yīng)用共25頁，您現(xiàn)在瀏覽的是第22頁!遺傳算法的應(yīng)用及一些問題1、遺傳算法的應(yīng)用領(lǐng)域（1）組合優(yōu)化（2）函數(shù)優(yōu)化