智能控制-遺傳算法

1、第四章第四章 遺傳算法遺傳算法 遺傳算法 遺傳算法（genetic algorithms）是在70年代初期由美國執(zhí)根（Michigan）大學的Holland教授發(fā)展起來的。1975年， Holland發(fā)表了第一本比較系統(tǒng)論述遺傳算法的專著Adptation in Natural and Artificial Systems.本章先介紹遺傳算法及一些基本性質(zhì)，然后討論遺傳算法實現(xiàn)的技術(shù)問題，最后通過在約束批量模型的應用了解算法實現(xiàn)過程。v4.1遺傳算法 遺傳算法的特征 遺傳算法 遺傳算法有待研究的主要因素 遺傳算法優(yōu)越性與不足v4.2模板理論 從模板理論的角度說明遺傳算法的收斂性 針對遺傳算法的

2、三個算子獨立考慮模板的變化給出三個引理 模板定理4.1遺傳算法v生物進化的基本過程群體變異子群競爭婚配種群淘汰的群體遺傳算法主要借鑒了生物的一些特征，其主要特征體現(xiàn)為：v進化發(fā)生在解的編碼上。這些編碼按生物學的術(shù)語稱為染色體。由于對解進行了編碼，優(yōu)化問題的一切性質(zhì)都通過編碼來研究。編碼和解碼是遺傳算法的一個主題。v自然選擇規(guī)律決定哪些染色體產(chǎn)生超過平均數(shù)的后代。遺傳算法中，通過優(yōu)化問題的目標而人為地構(gòu)造適應函數(shù)以達到好的染色體產(chǎn)生超過平均數(shù)的后代。v當染色體結(jié)合時，雙親的遺傳基因的結(jié)合使得子女保持父母的特征。v當染色體結(jié)合后，隨機的變異會造成子代同父代的不同。遺傳算法包含以下的主要處理步驟：v

3、對優(yōu)化問題的解進行編碼，此處，我們稱一個解的編碼為一個染色體，組成編碼的元素稱為基因。編碼的目的主要是用于優(yōu)化問題解的表現(xiàn)形式和利于之后遺傳算法中的計算。v適應函數(shù)的構(gòu)造和應用。適應函數(shù)基本上依據(jù)優(yōu)化問題的目標函數(shù)而定。當適應函數(shù)確定以后，自然選擇規(guī)律是以適應函數(shù)值的大小決定的概率分布來確定哪些染色體適應生存，哪些被淘汰。生存下來的染色體組成種群，形成一個可以繁衍下一代的群體。v染色體的結(jié)合。雙親的遺傳基因結(jié)合是通過編碼之間的交配達到下一代的產(chǎn)生。新一代的產(chǎn)生是一個生殖過程，它產(chǎn)生了一個新解。最后是變異。新解產(chǎn)生的過程中可能發(fā)生基因變異，變異使某些解的編碼發(fā)生變化，使解有更大的遍歷性。生物遺傳

4、概念在遺傳算法中的對應關(guān)系 生物遺傳概念 遺傳算法中的作用 適者生存 在算法停止時，最優(yōu)目標值的解有最大的可能被留住 個體（individual） 解 染色體(chromosome) 解的編碼（字符串，向量等） 基因(gene) 解中每一分量的特征（如各分量的值） 適應性(fitness) 適應函數(shù)值 群體(population) 選定的一組解（其中解的個數(shù)為群體的規(guī)模） 種群(reproduction) 根據(jù)適應函數(shù)值選取的一組解 交配(crossover) 通過交配原則產(chǎn)生一組新解的過程 變異（mutation） 編碼的某一個分量發(fā)生變化的過程 最優(yōu)化問題的求解過程是從眾多的解中選出最優(yōu)的

5、解，生物進化的適者生存的規(guī)律使得最具有生存能力的染色體以最大的可能生存。這樣的共同點使得遺傳算法可以在優(yōu)化問題中應用。例4.1 用遺傳算法求解 為整數(shù)的最大值。 xxxxf,310 ,)(2 一個簡單的表示解的編碼是二進制編碼，即0，1字符串。由于變量的最大值是31，因此可以采用5位數(shù)的二進制碼。如：10000 16 11111 31 01001 9 00010 2以上的5個字符串成為染色體，每一個分量稱為基因，每個基因有兩種狀態(tài)0或1。 模擬生物進化，首先要產(chǎn)生一個群體，可以隨機取4個染色體組成一個群體，)01000(, )01111(, )11001(, )00000(4321xxxx群體

6、有4個個體，適應函數(shù)可以依據(jù)目標函數(shù)而定，如適應函數(shù)2)()(xxfxfitness于是 2225)(xfitness0)(1xfitness2315)(xfitness248)(xfitness定義第i個個體入選種群的概率為jjiixfitnessxfitnessxp)()()(于是，適應函數(shù)值大的染色體個體的生存概率自然較大，若群體中4個個體成為種群則極有可能競爭上的是)01000(, )01111(, )11001(, )11001(4322xxxx若他們結(jié)合，采用如下的交配方式稱為簡單交配)000|01()001|11()111|01()001|11(4232xxxx)001|01()

7、000|11()001|01()111|11(4321yyyy即交換第二個位置以后的基因，得到 和 。若 的第一個基因發(fā)生變異，則變成 。321,yyy4y4y)11001(4ySTEP1 選擇問題的一個編碼；給出一個有N個染色體的初始群體pop(1),t:=1STEP3 若停止規(guī)則滿足，則算法停止；否則，計算概率并以此概率分布從pop（t）中隨機選一些染色體構(gòu)成一個種群 newpop(t+1)=popj(t)|j=1,2, N ；【注】 newpop(t+1)集中可能重復pop（t）中的一個元素，如例4.1中的 就選取兩次。STEP4 通過交配，交配概率為Pc，得到一個有N個染色體的cors

8、spop(t+1);STEP5 以一個較小的概率p，使得一個染色體的一個基因發(fā)生變異，形成 mutpop(t+1);t:=t+1,一個新的群體pop(t)= mutpop(t);返回STEP2。STEP2 對群體pop(t)中的每一個染色體popi(t)計算它的適應函數(shù) )(tpopfitnessfii遺傳算法NiffpNjiii,2,1,1(4.1)例4.2 用遺傳算法求. 1 , 0,1)(max2xxxf 由于對連續(xù)變量求解，要解決的一個問題是如何編碼。假設對解的誤差要求是1/16，則可以采用4位二進制編碼。對應關(guān)系為16842)(dcbaabcd表4.2 遺傳算法中的一步計算X值 舊群

9、體 適應函 概率 new 交配位 cross 是否 mut x值 pop(t) 數(shù)值f 分布p pop pop 變異 pop1/16 0001 0.996 0.318 0001 00|01 0000 N 0000 0 1/4 0100 0.938 0.299 0100 01|00 0101 Y 1101 13/163/16 0011 0.965 0.308 0001 000|1 0001 N 0001 1/16 7/8 1110 0.234 0.075 0011 001|1 0011 N 0011 3/16 平均值=0.7833，交配概率p=1，變異概率pm=0.02簡單遺傳算法可以理解為：v

10、求解的問題是極大目標函數(shù)的優(yōu)化問題；v采用01二進制編碼；vpop（t）中的染色體個數(shù)是一個常數(shù)；v初始群體隨機選取v適應函數(shù)為目標函數(shù)；v按輪盤賭方法選取染色體個數(shù)同pop（t）相同的種群；v常規(guī)交配方法：一對染色體按隨機位交換后的基因；v染色體中的每一個基因都以相同的概率變異。有待研究的主要因素有待研究的主要因素v解的編碼和解碼。v初始群體的選取和計算中群體的大小。v適應函數(shù)的確定。v三個算子。遺傳算法的三個算子是：種群選取、交配和變異或稱突變。遺傳算法的優(yōu)越性可以簡單地歸結(jié)為遺傳算法的優(yōu)越性可以簡單地歸結(jié)為v遺傳算法適合數(shù)值求解那些多參數(shù)、多變量、多目標和在多區(qū)域但連通性較差的NPhar

11、d優(yōu)化問題。v遺傳算法在求解很多組合優(yōu)化問題時，不需要有很強的技巧和對問題有非常深入的了解。v遺傳算法同求解問題的其他啟發(fā)式算法有較好的兼容性。遺傳算法的不足遺傳算法的不足（1）編碼不規(guī)范及編碼存在表示的不準確性。（2）單一的遺傳算法編碼不能全面地將優(yōu)化問題的約束表示出來。（3）是否能保證收斂到最優(yōu)解4.2模板理論簡單遺傳算法的主要特征有：v群體和種群的維數(shù)相等，且不隨代數(shù)的變化而變化；v適應函數(shù)直接選用目標函數(shù)；v種群中的個體通過輪盤賭的方式選??；v種群中的一對個體采用隨機交配位的方式產(chǎn)生一對子代；v每一個基因有相同的變異概率。v染色體稱為向量v一個給定的向量結(jié)構(gòu)，包括關(guān)心的分量位置和值，稱

12、為該向量的一個模板。 如1010001和1111010 110表示基因不同或我們不關(guān)心這個位置的取值， 稱H= 110為一個模板v0，1的位置稱為模板位置，位置稱為非模板位置。v模板長度：從第一個模板位置到最后一個模板位置的所有分量個數(shù)減1。 如H= 110的長度為4，記為 。)(Hv模板的階數(shù)：模板位置對應的確定分量個數(shù)。如H= 110的階數(shù)為3，記為 。)(H若染色體Y在H的模板位置上對應的分量相同，則稱Y具有H模板。記G（t）是第t代群體，即第t代染色體集合)2 . 4(, | )()(,(HYtGYtGHT具有模板其中t稱為遺傳的第t代。T（H,G（t）為模板H所包含的G（t）中的所有

13、染色體集合。 引理4.1 在生殖過程中，若每一個個體被選入種群newpop(t+1)的概率為（4.1），且種群的規(guī)模與群體相同，則模板H所包含的染色體在t+1時刻的期望數(shù)為)3 . 4(, ),(),() 1,(1tHNtHftHE其中N(H,t)為t時刻T(H,pop(t)所包含的染色體數(shù)，)4.4()()()(,()(),()(:)(,(:tpopYYtpopHTYYtpopYfitnesstpopHTYfitnesstHf證明證明 H模板的每一個染色體被選中的平均概率為)(,(:)(,()(tpopHTYYtpopHTYfitness而群體中每一個個體被選的平均概率為)(:)()(tpo

14、pYYtpopYfitness所以，（4.3）成立。 引理4.2 若在t時刻，模板H的長度為 ，采用簡單交配方法，即隨機選一個交配位，交換位后基因，交配的概率是 ，則在t+1時刻模板H保留下來的概率為)(Hcp)5 . 4(),(1 (1)(1) 1,(tHpnHptHpci其中，p（H，t）表示t時刻模板H出現(xiàn)的概率。證明證明 模板H發(fā)生變化的可能是由交配產(chǎn)生的。由于采用交配位后的基因交換，因此選擇第一個模板位到最后一個模板位中的任何一個位置為交配位都可能產(chǎn)生模板變化，所以，模板發(fā)生改變的最大概率是 。假設交配的雙方有相同的模板，則交配后模板不變。一方不具有同H相同的概率為 。于是使模板H改

15、變的最大概率為1)(nHpc),(1tHp,),(1(1)(tHpnHpc在交配的過程中，會出現(xiàn)交配的雙方不具有H模板，但交配后卻具有H模板，故有.),(1(1)(1)1,(1tHpnHptHpc 引理4.3 假設模板H在t時刻存在的概率為p(H,t)，經(jīng)過簡單變異，則有)6.4(,)(1)1,(2HptHpm其中， 為每個基因變異概率， 為H的階 mp)(H 定理4.1 （模板定理）假設群體在t時刻有相同模板H的染色體個數(shù)為N(H,t),經(jīng)過滿足引理4.1的種群選取、滿足引理4.2的以概率 的交配和滿足引理4.3以概率 的變異，則在t+1時刻，群體中具有H模板的染色體數(shù)的期望值為cpmp)7

16、 . 4(),(),()(),(1 (1)(1) 1,(tHNtHfHptHpnHptHEmc如果)8 . 4(,)(),(1 (1)(1),(1HptHpnHptHfmc則從概率意義來說，每代中具有H模板的染色體個數(shù)將隨代數(shù)t的增加而增加。 證明證明 遺傳算法每一代的遺傳由種群選取、交配和變異三個算子組成。三個事件的綜合效果，使新一代群體中具有模板H的染色體數(shù)的期望值由引理4.1、引理4.2和引理4.3得到112(,1)(,1)(,1)(,1)()1(1(, )11() (, )(, )()1(1(, )1() (, )(, ).cmcmE H tE H tp H tp H tpHp H t

17、npHf H t N H tpHp H tnpHf H t N H t例4.4 用遺傳算法求解 。觀察模板 ， 和 的變化情況。2310max xzxx為整數(shù)11H 102H013H表4.3 遺傳算法第一步數(shù)值結(jié)果No. 群體 x 適應函數(shù)f(x) 概率分布 隨機模擬 選取出現(xiàn)次數(shù)414)()(iifif 1 01101 13 169 0.14 0.58 1 2 11000 24 576 0.49 1.97 2 3 01000 8 64 0.06 0.22 0 4 10011 19 361 0.31 1.23 1合計 1170 1.00 4.00 4.0 平均 293 0.25 1.00 1.

18、0最大 576 0.49 1.97 2.020. 32293469),(),() 1,(1111tHNtHftHE種群中具有H1模板的染色體期望值為97. 1) 1,(,18. 2) 1,(3121tHEtHE模板特性（生殖前）模板 群體 具有同模 板染色體H1 1 2，4 469 1.6H2 1 0 2，3 320 1.09H3 1 0 2 576 1.97),(),()(tHTitHTif)(),()()(),()(tpopitHTitpopiftHTif表4.4（a） 遺傳算法第二步數(shù)值結(jié)果 種群體 匹配（隨機選） 交配位（隨機選） 新群體 x值 f(x) 0110|1 2 4 01100 12 144 1100|0 1 4 11001 25 625 11|000 4 2 11011 27 729 10|011 3 2 10000 16 256 合計 1754 平均 439 最大 729表4.4（b） 模板特性（種群）模板 理論期望數(shù)