人工智能導(dǎo)論課件第4章 基于遺傳算法的隨機(jī)優(yōu)化搜索

第4章基于遺傳算法的隨機(jī)優(yōu)化搜索

4.1基本概念

4.2基本遺傳算法

4.3遺傳算法應(yīng)用舉例

4.4遺傳算法的特點(diǎn)與優(yōu)勢(shì)

4.1基本概念

1．染色體及其編碼遺傳算法以生物細(xì)胞中的染色體(chromosome)代表問(wèn)題中個(gè)體對(duì)象（即可能解）。一般用字符串表示，而基因也就是字符串中的一個(gè)個(gè)字符。例如，假設(shè)數(shù)字9是某問(wèn)題中的個(gè)體對(duì)象，則我們就可以用它的二進(jìn)制數(shù)串1001作為它的染色體編碼。2.適應(yīng)度與適應(yīng)度函數(shù)適應(yīng)度(fitness)就是借鑒生物個(gè)體對(duì)環(huán)境的適應(yīng)程度，而對(duì)所求解問(wèn)題中的對(duì)象（即染色體）設(shè)計(jì)的一種表征優(yōu)劣的測(cè)度。適應(yīng)度函數(shù)(fitnessfunction)就是問(wèn)題中的全體對(duì)象與其適應(yīng)度之間的一個(gè)對(duì)應(yīng)關(guān)系，即對(duì)象集合到適應(yīng)度集合的一個(gè)映射。3.種群種群（population）就是模擬生物種群而由若干個(gè)染色體組成的群體，它一般是整個(gè)論域空間的一個(gè)很小的子集。遺傳算法就是通過(guò)在種群上實(shí)施所稱的遺傳操作，使其不斷更新?lián)Q代而實(shí)現(xiàn)對(duì)整個(gè)論域空間的搜索。4.遺傳操作

遺傳算法中有三種關(guān)于染色體的運(yùn)算：選擇-復(fù)制*、交叉和變異，稱為遺傳操作或遺傳算子（geneticoperator）。

選擇-復(fù)制

選擇概率P(xi)的計(jì)算公式為其中，f為適應(yīng)度函數(shù)，f(xi)為xi的適應(yīng)度。

按概率選擇的方法可用一種稱為賭輪的原理來(lái)實(shí)現(xiàn)。算法中賭輪選擇法可用下面的子過(guò)程來(lái)模擬：①在[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ì)算公式為

交叉

交叉(crossover)亦稱交換、交配或雜交，就是互換兩個(gè)染色體某些位上的基因。例如，設(shè)染色體s1=01001011，s2=10010101，交換其后4位基因，即則得新串s1’=01000101，s2’=10011011。s1’和s2’可以看作是原染色體s1和s2的子代染色體。

變異

變異(Mutation)亦稱突變，就是改變?nèi)旧w某個(gè)（些）位上的基因。

例如，把染色體s=11001101的第三位上的0變?yōu)?，則得到新染色體s’=11101101。4.2

基本

遺傳

算法4.3遺傳算法應(yīng)用舉例

例4-1利用遺傳算法求區(qū)間[0,31]上的二次函數(shù)y=x2的最大值。解(1)定義適應(yīng)度函數(shù)，編碼染色體。

將函數(shù)f(x)=x2就可作為空間U上的適應(yīng)度函數(shù)。(2)設(shè)定種群規(guī)模，產(chǎn)生初始種群。將種群規(guī)模設(shè)定為4，取染色體s1=01101（13）,s2=11000（24）

s3=01000（8）,s4=10011（19）組成初始種群S1。(3)計(jì)算各代種群中的各染色體的適應(yīng)度，并進(jìn)行遺傳操作，直到適應(yīng)度最高的染色體（該問(wèn)題中顯然為“11111”=31）出現(xiàn)為止。計(jì)算S1中各染色體的適應(yīng)度、選擇概率、積累概率等并列表于表4-1中。選擇-復(fù)制設(shè)從區(qū)間[0,1]中產(chǎn)生4個(gè)隨機(jī)數(shù)如下：

r1=0.450126,r2=0.110347,r3=0.572496,r4=0.98503按賭輪選擇法，染色體s1,s2,s3,s4的被選中次數(shù)依次為：1,2,0,1。經(jīng)復(fù)制得群體：s1’=11000（24）,s2’=01101（13）

s3’=11000（24）,s4’=10011（19）交叉設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運(yùn)算。將s1’與s2’配對(duì)，s2’與s4’配對(duì)，分別交換后兩位基因，得新染色體：s1’’=11001（25）,s2’’=01100（12）

s3’’=11011（27）,s4’’=10000（16）變異設(shè)變異率pm=0.001。這樣，群體S1中共有5

4

0.001=0.02位基因可以變異。0.02位顯然不足1位，所以本輪遺傳操作不做變異?，F(xiàn)在，得到了第二代種群S2：s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）計(jì)算S2中各染色體的適應(yīng)度、選擇概率、積累概率等并列表于表4-2中。

假設(shè)這一輪選擇-復(fù)制操作中，種群S2中的4個(gè)染色體都被選中，則得到群體：s1’=11001（25）,s2’=01100（12）

s3’=11011（27）,s4’=10000（16）然后，做交叉運(yùn)算，讓s1’與s2’，s3’與s4’

分別配對(duì)并交換后三位基因，得s1’’=11100（28）,s2’’=01001（9）

s3’’=11000（24）,s4’’=10011（19）這一輪仍然不會(huì)發(fā)生變異。于是，得第三代種群S3：s1=11100（28）,s2=01001（9）

s3=11000（24）,s4=10011（19）計(jì)算S3中各染色體的適應(yīng)度、選擇概率、積累概率等并列表于表4-3中。

設(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：s1=11111（31）,s2=11100（28）

s3=11000（24）,s4=10000（16）

顯然，在這一代種群中已經(jīng)出現(xiàn)了適應(yīng)度最高的染色體s1=11111。于是，遺傳操作終止，將染色體“11111”作為最終結(jié)果輸出。然后，將染色體“11111”解碼為表現(xiàn)型，即得所求的最優(yōu)解：31。將31代入函數(shù)y=x2中，即得原問(wèn)題的解，即函數(shù)y=x2的最大值為961。

例4-2用遺傳算法求解TSP。

解將一個(gè)合法的城市序列s=(c1,c2,…,cn,cn+1)(cn+1就是c1)作為一個(gè)個(gè)體。這個(gè)序列中相鄰兩城之間的距離之和的倒數(shù)就可作為相應(yīng)個(gè)體s的適應(yīng)度，從而適應(yīng)度函數(shù)就是用符號(hào)A、B、C、D、E代表相應(yīng)的城市，用這5個(gè)符號(hào)的序列表示可能解即染色體。然后設(shè)計(jì)合適的染色體和相應(yīng)的遺傳運(yùn)算，使得這些遺傳運(yùn)算對(duì)染色體集合封閉。為此，人們針對(duì)TSP提出了許多編碼方法和相應(yīng)的特殊化了的交叉、變異操作，如順序編碼或整數(shù)編碼、隨機(jī)鍵編碼、部分映射交叉、順序交叉、循環(huán)交叉、位置交叉、反轉(zhuǎn)變異、移位變異、互換變異等等。從而巧妙地用遺傳算法解決了TSP。同時(shí)，也發(fā)展和完善了遺傳算法，進(jìn)一步擴(kuò)展了它的應(yīng)用。4.4遺傳算法的特點(diǎn)與優(yōu)勢(shì)

遺傳算法一般是直接在解空間搜索，而不像圖搜索那樣一般是在問(wèn)題空間搜索，最后才找到解（如果搜索成功的話）。

遺傳算法的搜索隨機(jī)地始于搜索空間的一個(gè)點(diǎn)集，而不像圖搜索那樣固定地始于搜索空間的初始節(jié)點(diǎn)或終止節(jié)點(diǎn)。所以，遺傳算法是一種隨機(jī)搜索算法。

遺傳算法總是在尋找優(yōu)解（最優(yōu)解或次優(yōu)解），而不像圖搜索那樣并非總是要求優(yōu)解，而一般是設(shè)法盡快找到解（當(dāng)然包括優(yōu)解）。