最經(jīng)典的遺傳算法教程

最經(jīng)典的遺傳算法教程第1頁，共29頁，2023年，2月20日，星期五全局優(yōu)化方法1）不依賴于初始條件；2）不與求解空間有緊密關(guān)系，對解域，無可微或連續(xù)的要求。求解穩(wěn)健，但收斂速度慢。能獲得全局最優(yōu)。適合于求解空間不知的情況第2頁，共29頁，2023年，2月20日，星期五⑴選擇運算⑵交換操作⑶變異遺傳算法的基本運算遺傳算法基本原理模擬自然界優(yōu)勝劣汰的進化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量——染色體，向量的每個元素稱為基因。通過不斷計算各染色體的適應(yīng)值，選擇最好的染色體，獲得最優(yōu)解。第3頁，共29頁，2023年，2月20日，星期五●選擇運算——從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體作準備。選擇方法——適應(yīng)度比例法（轉(zhuǎn)輪法）按各染色體適應(yīng)度大小比例來決定其被選擇數(shù)目的多少。某染色體被選的概率：Pcxi為種群中第i個染色體，第4頁，共29頁，2023年，2月20日，星期五具體步驟1）計算各染色體適應(yīng)度值2）累計所有染色體適應(yīng)度值，記錄中間累加值S-mid和最后累加值sum=∑f(xi)3）產(chǎn)生一個隨機數(shù)N，0〈N〈sum4）選擇對應(yīng)中間累加值S-mid的第一個染色體進入交換集

5）重復(fù)（3）和（4），直到獲得足夠的染色體。舉例：⒈具有6個染色體的二進制編碼、適應(yīng)度值、Pc累計值。第5頁，共29頁，2023年，2月20日，星期五染色體的適應(yīng)度和所占的比例用轉(zhuǎn)輪方法進行選擇第6頁，共29頁，2023年，2月20日，星期五染色體編號

1

2

3

4

5

6

7

8

9

10適應(yīng)度

8

217

7

212117

3

7被選概率0.10.020.220.090.020.160.140.090.030.09適應(yīng)度累計

8

10

27

34

36

48

59

66

6976隨機數(shù)23497613

1

2757所選染色體號碼

3

710

3

1

3

7染色體被選的概率被選的染色體個數(shù)⒉10個染色體種群按比例的選擇過程第7頁，共29頁，2023年，2月20日，星期五●交換操作

方法:隨機選擇二個染色體(雙親染色體),隨機指定一點或多點,進行交換,可得二個新的染色體(子輩染色體).新的子輩染色體:A’11010001B’01011110模擬生物在自然界環(huán)境變化,引起基因的突變.在染色體二進制編碼中,1變成0;或0變成1.突變產(chǎn)生染色體的多樣性,避免進化中早期成熟,陷入局部極值點,突變的概率很低.●變異復(fù)制不能創(chuàng)新,交換解決染色體的創(chuàng)新第8頁，共29頁，2023年，2月20日，星期五GA的流程第9頁，共29頁，2023年，2月20日，星期五簡單遺傳算法（GA）的基本參數(shù)①種群規(guī)模P:參與進化的染色體總數(shù).②代溝G:二代之間不相同的染色體數(shù)目,無重疊G=1;

有重疊0<G<1③選擇方法:轉(zhuǎn)輪法,精英選擇法,競爭法.④交換率:Pc一般為60~100%.⑤變異率:Pm一般為0.1~10%舉例:變異概率取0.001第10頁，共29頁，2023年，2月20日，星期五初始種群和它的適應(yīng)度值染色體的交換操縱第11頁，共29頁，2023年，2月20日，星期五舉例：14第12頁，共29頁，2023年，2月20日，星期五步驟1）編碼：確定二進制的位數(shù)；組成個體（染色體）步驟2）選擇種群數(shù)P和初始個體，計算適應(yīng)度值，

P=20；第13頁，共29頁，2023年，2月20日，星期五步驟3）確定選擇方法；交換率PC；變異率Pm。選擇方法用競爭法；PC=0.7,Pm=0.05計算結(jié)果：①8代后，f(x,y)=0.998757,②41代后，f(x,y)=1.00000,x=3.000290,y=2.999924.③160次適應(yīng)度計算，達到最優(yōu)值。遺傳算法的基本數(shù)學(xué)問題一個重要的定理——圖式定理什么叫圖式？——描述種群中染色體相似性的字符串。（插入演示）演示12第14頁，共29頁，2023年，2月20日，星期五

（*為通配符）第15頁，共29頁，2023年，2月20日，星期五圖式的描述：⑴定義長度（H)——H左右二端有定義位置之間的距離；⑵圖式的階次(或固定長度)O(H）——H中非*位（有定義位）的個數(shù)。圖式定理的推導(dǎo)①圖式在選擇過程中的增加.第16頁，共29頁，2023年，2月20日，星期五經(jīng)過選擇,在t+1代,圖式H的數(shù)量m(H,t+1)為:

第17頁，共29頁，2023年，2月20日，星期五②圖式在交換中的破壞③圖式在變異中的破壞經(jīng)過選擇、交換、變異后在t+1中，圖式H的數(shù)量：圖式定理：在選擇、交換、變異的作用下，階次低、定義長度短、適應(yīng)度高的圖式（模塊）將按指數(shù)增長的規(guī)律，一代一代地增長。第18頁，共29頁，2023年，2月20日，星期五遺傳算法在應(yīng)用中的一些基本問題1）知識的編碼

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

a)適應(yīng)度函數(shù)值必須非負。根據(jù)情況做適當(dāng)?shù)奶幚矶M制和十進制的比較：二進制有更多圖式和更大的搜索范圍；十進制更接近于實際操作。第19頁，共29頁，2023年，2月20日，星期五第20頁，共29頁，2023年，2月20日，星期五3）全局最優(yōu)和收斂性。

根據(jù)圖式定理，對于具有“欺騙性”函數(shù)，GA有可能落入局部最優(yōu)點。b）為保持種群的多樣性，防止“超級”染色體“統(tǒng)治”種群。第21頁，共29頁，2023年，2月20日，星期五欺騙性函數(shù)

圖式劃分：指引相互之間競爭的定義位為同一集合的一組圖式。如#表示定義位，則H1=*1*0*，H2=*0*1*，H3=*1*1*，

H4=*0*0*同屬于劃分*#*#*。

總平均適應(yīng)度（OAF）：對一個給定圖式，OAF即為其成員的平均適應(yīng)度。欺騙性函數(shù)——包含全局最優(yōu)的圖式其OAF不如包含局部最優(yōu)的OAF，這種劃分稱為欺騙劃分，它會使GA陷入局部最優(yōu)。如最高階欺騙函數(shù)有k個定義位，則此函數(shù)稱k階欺騙。第22頁，共29頁，2023年，2月20日，星期五舉例：3位欺騙函數(shù)第23頁，共29頁，2023年，2月20日，星期五●高級GA算法1）操作的改進2）算法的改進選擇方法改進：精英法（競賽法）、置換式和非置換式隨機選擇法，排序法。交換方法的改進：多點交換；重組運算微種群遺傳算法（GA）雙種群遺傳算法（DPGA）重組運算：解決染色體分布過于集中問題。把適應(yīng)度函數(shù)做進一步處理。第24頁，共29頁，2023年，2月20日，星期五終止條件：1）達到預(yù)定指標；2）達到預(yù)定代數(shù)。GA算法第25頁，共29頁，2023年，2月20日，星期五雙種群算法（DPGA）基本思想：利用人類社會分工合作的機理。分成：全局種群——粗搜索，尋找可能存在的最優(yōu)區(qū)域；

局部種群

——精搜索在全局劃定的區(qū)域內(nèi)，尋找最優(yōu)點。第26頁，共29頁，2023年，2月20日，星期五測試函數(shù)：