研一期末考模式識(shí)別四章

第四章

基于遺傳算法的隨機(jī)優(yōu)化搜索孔萬(wàn)增計(jì)算機(jī)應(yīng)用技術(shù)研究所計(jì)算機(jī)學(xué)院杭州電子科技大學(xué)目錄4.1基本概念4.2基本遺傳算法4.3遺傳算法應(yīng)用舉例4.4遺傳算法的特點(diǎn)與優(yōu)勢(shì)4.1基本概念

個(gè)體個(gè)體就是模擬生物個(gè)體，對(duì)問題中對(duì)象（一般就是問題的解）的一種稱呼。一個(gè)個(gè)體也就是搜索空間中的一個(gè)點(diǎn)。種群種群(population)就是模擬生物種群,由若干個(gè)體組成的群體.它一般是整個(gè)搜索空間的一個(gè)很小的子集.基本概念——適應(yīng)度與適應(yīng)度函數(shù)適應(yīng)度(fitness)借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度,對(duì)問題中的個(gè)體對(duì)象所設(shè)計(jì)的表征其優(yōu)劣的一種測(cè)度。適應(yīng)度函數(shù)(fitnessfunction)是問題中全體個(gè)體與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系。通常為實(shí)值函數(shù)。該函數(shù)就是遺傳算法中指導(dǎo)搜索的評(píng)價(jià)函數(shù)?；靖拍睢旧w與基因染色體（chromosome）與基因（gene）染色體是問題中個(gè)體的某種字符串形式的編碼表示。字符串中的字符稱為基因。例如：個(gè)體染色體

9----

1001（2，5，6）----010101110基本概念——遺傳操作遺傳操作亦稱遺傳算子(geneticoperator)關(guān)于染色體的運(yùn)算。遺傳算法中有三種遺傳操作:選擇-復(fù)制(selection-reproduction)交叉(crossover，亦稱交換、交配或雜交)變異(mutation，亦稱突變)選擇-復(fù)制對(duì)于一個(gè)規(guī)模為N的種群S,按每個(gè)染色體xi∈S的選擇概率P(xi)所決定的選中機(jī)會(huì),分N次從S中隨機(jī)選定N個(gè)染色體,并進(jìn)行復(fù)制。這里的選擇概率P(xi)的計(jì)算公式為:交叉交叉:互換兩個(gè)染色體某些位上的基因。例如,設(shè)染色體s1=01001011,s2=10010101,交換其后4位基因,即s1′=01000101,s2′=10011011可以看做是原染色體s1和s2的子代染色體。變異變異:就是改變?nèi)旧w某個(gè)(些)位上的基因。例如,設(shè)染色體s=11001101,將其第三位上的0變?yōu)?,即

s=11001101→11101101=s′。

s′也可以看做是原染色體s的子代染色體。遺傳算法基本流程框圖生成初始種群計(jì)算適應(yīng)度選擇-復(fù)制交叉變異生成新一代種群終止?結(jié)束遺傳算法中的一些控制參數(shù)種群規(guī)模最大換代數(shù)交叉率(crossoverrate)參與交叉運(yùn)算的染色體個(gè)數(shù)占全體染色體總數(shù)的比例，記為Pc,取值范圍一般為0.4~0.99。變異率(mutationrate)指發(fā)生變異的基因位數(shù)所占全體染色體的基因總位數(shù)的比例，記為Pm，取值范圍一般為0.0001~0.1?；具z傳算法步驟步1：在搜索空間U上定義一個(gè)適應(yīng)度函數(shù) f(x)，給定種群規(guī)模N，交叉率Pc和變異率 Pm，代數(shù)T；步2：隨機(jī)產(chǎn)生U中的N個(gè)個(gè)體s1,s2,…,sN，組 成初始種群S={s1,s2,…,sN}，置代數(shù)計(jì)數(shù) 器t=1；步3：計(jì)算S中每個(gè)個(gè)體的適應(yīng)度f(wàn)；步4：若終止條件滿足，則取S中適應(yīng)度最大的 個(gè)體作為所求結(jié)果，算法結(jié)束?；具z傳算法步驟2步5：按選擇概率P(xi)決定選中機(jī)率，每次從S中隨 機(jī)選定1個(gè)體并將其染色體復(fù)制，共做N次，然 后將復(fù)制所得的N個(gè)染色體組成群體S1；步6：按交叉率Pc決定參加交叉的染色體數(shù)c，從S1 中隨機(jī)確定c個(gè)染色體，對(duì)進(jìn)行交叉操作，并用 產(chǎn)生的新染色體代替原染色體，得群體S2；步7：按變異率Pm決定變異次數(shù)m，從S2中隨機(jī)確定 m個(gè)染色體，分別進(jìn)行變異操作，并用產(chǎn)生的新 染色體代替原染色體，得群體S3；步8：將群體S3作為新一代種群，即用S3代替S，t= t+1，轉(zhuǎn)步3；遺傳算法應(yīng)用舉例

例4.1

利用遺傳算法求解區(qū)間[0,31]上的二次函數(shù)y=x2的最大值。y=x2

31

XY分析原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點(diǎn)a的問題。[0,31]中的每個(gè)點(diǎn)x就是個(gè)體。函數(shù)值f(x)恰好就可以作為x的適應(yīng)度。區(qū)間[0,31]就是一個(gè)(解)空間。問題：如何給出個(gè)體x的適當(dāng)染色體編碼？使得該問題可用遺傳算法來(lái)解決。求解步驟1：隨機(jī)選取初始種群(1)設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。假定將種群規(guī)模設(shè)定為4；采用5位二進(jìn)制數(shù)編碼染色體；隨機(jī)選取4個(gè)個(gè)體，組成初始種群S1:s1=13(01101)s2=24(11000)s3=8(01000)s4=19(10011)求解步驟2：定義適應(yīng)度函數(shù)（2）定義適應(yīng)度函數(shù)取適應(yīng)度函數(shù)：f(x)=x2適應(yīng)度函數(shù)選取是具體問題具體分析。求解步驟3：計(jì)算適應(yīng)度函數(shù)（3）計(jì)算當(dāng)前種群中的各個(gè)體的適應(yīng)度。以初始種群S1中各個(gè)體的適應(yīng)度f(wàn)(si)。s1=13(01101),s2=24(11000)

，s3=8(01000),s4=19(10011)有：

f(s1)=f(13)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361求解步驟4：計(jì)算選擇概率（4）計(jì)算當(dāng)前種群中各個(gè)體的選擇概率。選擇概率的計(jì)算公式為以初始種群S1為例：P(s1)=P(13)=169/1170=0.14P(s2)=P(24)=576/1170=0.49P(s3)=P(8)=64/1170=0.06P(s4)=P(19)=361/1170=0.31求解步驟5：選擇-復(fù)制選擇下一代種群的個(gè)體，選擇-復(fù)制：賭輪選擇法賭輪選擇法過程:①在[0,1]區(qū)間內(nèi)產(chǎn)生一個(gè)均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。 其中的qi稱為染色體xi

(i=1,2,…,n)的積累概率. 其計(jì)算公式為S4：0.31S2：0.49S1:0.14S3:0.06求解步驟5舉例：設(shè)從區(qū)間[0,1]中產(chǎn)生4個(gè)隨機(jī)數(shù)如下:r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=01101(13)1690.140.141(r2)s2=11000(24)5760.490.632(r1和r3)s3=01000(8)640.060.690s4=10011(19)3610.311.001(r4)求解步驟5舉例的結(jié)果：經(jīng)復(fù)制得下一代新種群的初始個(gè)體：s1′

=11000（24）,s2′

=01101（13）s3′

=11000（24）,s4′

=10011（19）結(jié)束了嗎？求解步驟6：交叉根據(jù)交叉率從新種群選取參與交叉運(yùn)算的個(gè)體。若交叉率pc=100%，則全體染色體都參加交叉運(yùn)算。隨機(jī)選擇兩對(duì)染色體參與交叉。隨機(jī)選擇交叉運(yùn)算時(shí)的交換位數(shù)。舉例：設(shè)在選擇-復(fù)制獲得新種群后，隨機(jī)選擇s1’與s2’配對(duì)交叉，s3’與s4’配對(duì)交叉。求解步驟6舉例s1′

=11000（24）,s2′

=01101（13）隨機(jī)確定最后兩位交叉，分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）同樣：s3′=11000（24）,s4′=10011（19）最后兩位交叉，得新染色體：s3’’=11011（27）,s4’’=10000（16）求解步驟6舉例的結(jié)果新種群中各個(gè)體的染色體：s1’’=11001（25）,s2’’=01100（12）s3’’=11011（27）,s4’’=10000（16）求解步驟7：變異根據(jù)變異率pm，對(duì)新種群中個(gè)體的染色體基因進(jìn)行變異。新種群中各個(gè)體染色體的各個(gè)基因，產(chǎn)生隨機(jī)數(shù)，若小于pm

，則變異（反轉(zhuǎn)）。舉例：設(shè)變異率pm=0.001從總體看，共有5×4×0.001=0.02位基因發(fā)生變異。0.02位顯然不足1位，所以不會(huì)有變異。求解步驟8：下一代種群的產(chǎn)生第二代種群S2：s1=11001（25）,s2=01100（12）s3=11011（27）,s4=10000（16）計(jì)算新種群中最大的適應(yīng)度值s3=11011 f(s3)=729大于前一代種群中的最大適應(yīng)度值新種群“適者生存”，新種群作為當(dāng)前種群。為第二代種群S2。

返回步驟3，迭代迭代求解步驟3、4當(dāng)前種群中染色體S2適應(yīng)度選擇概率積累概率估計(jì)的選中次數(shù)s1=11001(25)6250.360.361s2=01100(12)1440.080.441s3=11011(27)7290.410.851s4=10000(16)2560.151.001迭代求解步驟5選擇-復(fù)制這一輪假設(shè)選擇-復(fù)制操作中，經(jīng)隨機(jī)選擇，將種群S2中的4個(gè)染色體都選中，則得到新群體：s1’=11001（25）,s2’=01100（12）s3’=11011（27）,s4’=10000（16）迭代求解步驟6、7交叉運(yùn)算，經(jīng)隨機(jī)確定，讓s1’與s2’，s3’與s4’

分別交換后三位基因，得：s1’’=11100（28）,s2’’=01001（9）s3’’=11000（24）,s4’’=10011（19）變異運(yùn)算隨機(jī)確定，沒有變異發(fā)生。新種群產(chǎn)生得到新一代種群：

s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）計(jì)算新種群中最大的適應(yīng)度值s1=11100 f(s1)=784大于前一代種群中的最大適應(yīng)度值新種群“適者生存”，新種群作為當(dāng)前種群，為第三代種群S3

。第三代種群S3中各染色體情況

染色體適應(yīng)度選擇概率積累概率

估計(jì)的選中次數(shù)s1=11100(28)7840.440.442s2=01001(9)810.040.480s3=11000(24)5760.320.801s4=10011(19)3610.201.001第三代的遺傳運(yùn)算設(shè)這一輪的選擇-復(fù)制結(jié)果為：s1’=11100（28）,s2’=11100（28）s3’=11000（24）,s4’=10011（19）做交叉運(yùn)算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1’’=11111（31）,s2’’=11100（28）s3’’=11000（24）,s4’’=10000（16）這一輪仍然不會(huì)發(fā)生變異。獲得第四代種群S4第四代種群S4：

s1=11111（31）,s2=11100（28）s3=11000（24）,s4=10000（16）在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。之后遺傳進(jìn)化所得的各代種群，最大個(gè)體適應(yīng)度值均小于等于s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。遺傳算法數(shù)值結(jié)果染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2

中得原問題的解，即函數(shù)y=x2的最大值為961。遺傳算法迭代圖示Yy=x2

8131924

X第一代種群及其適應(yīng)度y=x2

12162527

XY第二代種群及其適應(yīng)度y=x2

9192428

XY第三代種群及其適應(yīng)度Yy=x2

16242831

X第四代種群及其適應(yīng)度例4.2用遺傳算法求解TSP分析如何構(gòu)建染色體？任一可能解：一個(gè)合法的城市序列，即n個(gè)城市的一個(gè)排列。因此，可直接在解空間（所有合法的城市序列）中搜索最佳解。這正適合用遺傳算法求解。一個(gè)合法的城市序列s=（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個(gè)個(gè)體。步驟1：定義適應(yīng)度函數(shù)城市序列中相鄰兩城之間的距離之和的倒數(shù)可作為相應(yīng)個(gè)體s的適應(yīng)度。即適應(yīng)度函數(shù)就是：為什么這么定義？如何編碼和交叉雖然選定一個(gè)合法的城市序列（c1,c2,…,cn,cn+1）(cn+1就是c1)作為一個(gè)個(gè)體。還需對(duì)個(gè)體進(jìn)行編碼。如果編碼不當(dāng)，就會(huì)在實(shí)施交叉或變異操作時(shí)出現(xiàn)非法城市序列即無(wú)效解。例如，對(duì)于5個(gè)城市的TSP，用符號(hào)A、B、C、D、E代表相應(yīng)的城市，用這5個(gè)符號(hào)的序列表示可能解即染色體。出現(xiàn)的問題？設(shè)s1=(A,C,B,E,D,A)，s2=(A,E,D,C,B,A)進(jìn)行遺傳操作:實(shí)施常規(guī)的交叉操作，如交換后三位，得s1’=（A,C,B,C,B,A），s2’=（A,E,D,E,D,A）實(shí)施常規(guī)的變異操作，將染色體s1第二位的C變?yōu)镋，得s1’’=（A,E,B,E,D,A）可以看出，上面得到的s1’，

s2’和s1’’都是非法的城市序列。求解方法對(duì)TSP必須設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算。針對(duì)TSP已提出了許多編碼方法和相應(yīng)的特殊化的交叉、變異操作，以巧妙地用遺傳算法解決TSP。如順序編碼或整數(shù)編碼、隨機(jī)鍵編碼.如部分映射交叉、順序交叉、循環(huán)交叉、位置交叉。如反轉(zhuǎn)變異、移位變異、互換變異等等。編碼方式二進(jìn)制編碼對(duì)TSP而言沒有意義，因?yàn)槌鞘刑?hào)就是基本單元。路徑表示最常用的編碼方式有許多特殊的遺傳操作算子Matrixrepresentation(6

3

541

2)(2314)交叉方式——部分映射交叉部分映射交叉PMX(Partial-MappedCrossover)(12345678)2parents(37516824)1.隨機(jī)取兩點(diǎn),例如4、62.兩點(diǎn)內(nèi)部分先行交換3.其余依次填入,

但重復(fù)者必須替換

置換規(guī)則交叉方式——循環(huán)交叉循環(huán)交叉CycleCrossover(12345678)(24687531)1.從第一個(gè)位置開始填起,２選１,下例為選到左邊parent的情形2.填好第一個(gè)位置之後后,看另一個(gè)parent同樣number(此處為１)的位置何在(位置8)3.再將原parent同位置的number填入offspring,其餘依此類推4.左邊parent沒有number可供填入,則找右邊的parent,從offspring最前面的空位填起2parents產(chǎn)生一個(gè)offspring部分研究實(shí)驗(yàn)顯示cyclecrossover較PMX效果佳(12345678)