第4章基于遺傳算法的隨機優化搜索

4.1基本概念

4.2基本遺傳算法

4.3遺傳算法應用舉例

4.4遺傳算法的特點與優勢

4.1基本概念

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

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

選擇-復制

選擇概率P(xi)的計算公式為其中，f為適應度函數，f(xi)為xi的適應度。

按概率選擇的方法可用一種稱為賭輪的原理來實現。算法中賭輪選擇法可用下面的子過程來模擬：①在[0,1]區間內產生一個均勻分布的偽隨機數r；②若r≤q1，則染色體x1被選中；③若qk-1<r≤qk(2≤k≤N)，則染色體xk被選中。其中的qi稱為染色體xi（i=1,2,…,n）的積累概率，其計算公式為

交叉

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

變異

變異(Mutation)亦稱突變，就是改變染色體某個（些）位上的基因。

例如，把染色體s=11001101的第三位上的0變為1，則得到新染色體s’=11101101。4.2

基本

遺傳

算法4.3遺傳算法應用舉例

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

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

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

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

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

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

4

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

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

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

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

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

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

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

設這一輪的選擇-復制結果為：s1’=11100（28）,s2’=11100（28）

s3’=11000（24）,s4’=10011（19）然后，做交叉運算，讓s1’與s4’，s2’與s3’

分別交換后兩位基因，得s1’’=11111（31）,s2’’=11100（28）

s3’’=11000（24）,s4’’=10000（16）這一輪仍然不會發生變異。于是，得第四代種群S4：s1=11111（31）,s2=11100（28）

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

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

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

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

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

遺傳算法的搜索隨機地始于搜索空間的一個點集，而不像圖搜索那樣固定地始于搜索空間的初始節點或終止節點。所以，遺傳算法是一種隨機搜索算法。

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