經(jīng)典遺傳算法教程演示文稿

經(jīng)典遺傳算法教程演示文稿目前一頁\總數(shù)二十七頁\編于十八點（優(yōu)選）經(jīng)典遺傳算法教程目前二頁\總數(shù)二十七頁\編于十八點⑴選擇運算⑵交換操作⑶變異遺傳算法的基本運算遺傳算法基本原理

模擬自然界優(yōu)勝劣汰的進(jìn)化現(xiàn)象，把搜索空間映射為遺傳空間，把可能的解編碼成一個向量——染色體，向量的每個元素稱為基因。通過不斷計算各染色體的適應(yīng)值，選擇最好的染色體，獲得最優(yōu)解。目前三頁\總數(shù)二十七頁\編于十八點●選擇運算——從舊的種群中選擇適應(yīng)度高的染色體，放入匹配集（緩沖區(qū)），為以后染色體交換、變異，產(chǎn)生新的染色體作準(zhǔn)備。選擇方法——適應(yīng)度比例法（轉(zhuǎn)輪法）按各染色體適應(yīng)度大小比例來決定其被選擇數(shù)目的多少。某染色體被選的概率：Pcxi為種群中第i個染色體，目前四頁\總數(shù)二十七頁\編于十八點具體步驟1）計算各染色體適應(yīng)度值2）累計所有染色體適應(yīng)度值，記錄中間累加值S-mid和最后累加值sum=∑f(xi)3）產(chǎn)生一個隨機數(shù)N，0〈N〈sum4）選擇對應(yīng)中間累加值S-mid的第一個染色體進(jìn)入交換集

5）重復(fù)（3）和（4），直到獲得足夠的染色體。舉例：⒈具有6個染色體的二進(jìn)制編碼、適應(yīng)度值、Pc累計值。目前五頁\總數(shù)二十七頁\編于十八點染色體的適應(yīng)度和所占的比例用轉(zhuǎn)輪方法進(jìn)行選擇目前六頁\總數(shù)二十七頁\編于十八點染色體編號12345678910適應(yīng)度8217721211737被選概率0.10.020.220.090.020.160.140.090.030.09適應(yīng)度累計8

10

273436

48

59

666976隨機數(shù)2349761312757所選染色體號碼37103137染色體被選的概率被選的染色體個數(shù)⒉10個染色體種群按比例的選擇過程目前七頁\總數(shù)二十七頁\編于十八點●交換操作

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

有重疊0<G<1③選擇方法:轉(zhuǎn)輪法,精英選擇法,競爭法.④交換率:Pc一般為60~100%.⑤變異率:Pm一般為0.1~10%舉例:變異概率取0.001目前十頁\總數(shù)二十七頁\編于十八點初始種群和它的適應(yīng)度值染色體的交換操縱目前十一頁\總數(shù)二十七頁\編于十八點舉例：14目前十二頁\總數(shù)二十七頁\編于十八點步驟1）編碼：確定二進(jìn)制的位數(shù)；組成個體（染色體）步驟2）選擇種群數(shù)P和初始個體，計算適應(yīng)度值，

P=20；目前十三頁\總數(shù)二十七頁\編于十八點步驟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)度計算，達(dá)到最優(yōu)值。遺傳算法的基本數(shù)學(xué)問題一個重要的定理——圖式定理什么叫圖式？——描述種群中染色體相似性的字符串。（插入演示）演示12目前十四頁\總數(shù)二十七頁\編于十八點

（*為通配符）目前十五頁\總數(shù)二十七頁\編于十八點圖式的描述：⑴定義長度（H)——H左右二端有定義位置之間的距離；⑵圖式的階次(或固定長度)O(H）——H中非*位（有定義位）的個數(shù)。圖式定理的推導(dǎo)①圖式在選擇過程中的增加.目前十六頁\總數(shù)二十七頁\編于十八點經(jīng)過選擇,在t+1代,圖式H的數(shù)量m(H,t+1)為:

目前十七頁\總數(shù)二十七頁\編于十八點②圖式在交換中的破壞③圖式在變異中的破壞經(jīng)過選擇、交換、變異后在t+1中，圖式H的數(shù)量：圖式定理：在選擇、交換、變異的作用下，階次低、定義長度短、適應(yīng)度高的圖式（模塊）將按指數(shù)增長的規(guī)律，一代一代地增長。目前十八頁\總數(shù)二十七頁\編于十八點遺傳算法在應(yīng)用中的一些基本問題1）知識的編碼

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

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

二進(jìn)制和十進(jìn)制的比較：二進(jìn)制有更多圖式和更大的搜索范圍；十進(jìn)制更接近于實際操作。目前十九頁\總數(shù)二十七頁\編于十八點目前二十頁\總數(shù)二十七頁\編于十八點3）全局最優(yōu)和收斂性。

根據(jù)圖式定理，對于具有“欺騙性”函數(shù)，GA有可能落入局部最優(yōu)點。b）為保持種群的多樣性，防止“超級”染色體“統(tǒng)治”種群。目前二十一頁\總數(shù)二十七頁\編于十八點欺騙性函數(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階欺騙。目前二十二頁\總數(shù)二十七頁\編于十八點舉例：3位欺騙函數(shù)目前二十三頁\總數(shù)二十七頁\編于十八點●高級GA算法1）操作的改進(jìn)2）算法的改進(jìn)選擇方法改進(jìn)：精英法（競賽法）、置換式和非置換式隨機選擇法，排序法。交換方法的改進(jìn)：多點交換；重組運算微種群遺傳算法（GA）雙種群遺傳算法（DPGA）重組運算：解決染色體分布過于集中問題。把適應(yīng)度函數(shù)做進(jìn)一步處理。目前二十四頁\總數(shù)二十七頁\編于十八點終止條件：1）達(dá)到預(yù)定指標(biāo)；2）達(dá)到預(yù)定代數(shù)。GA算法目