經(jīng)典算法研究系列：七、遺傳算法初探

            ---深入淺出、透析GA本質(zhì)

作者:July    二零一一年一月十二日。

本文參考：維基百科  華南理工大學(xué)電子講義  互聯(lián)網(wǎng)

-------------------------------------------------------------------------------

一、初探遺傳算法

Ok，先看維基百科對遺傳算法所給的解釋：

遺傳算法是計算數(shù)學(xué)中用于解決最優(yōu)化的搜索算法，是進(jìn)化算法的一種。進(jìn)化算法最初是借鑒了進(jìn)化生物學(xué)中的一些現(xiàn)象而發(fā)展起來的，這些現(xiàn)象包括遺傳、突變、自然選擇以及雜交等。

遺傳算法通常實現(xiàn)方式為一種計算機模擬。對于一個最優(yōu)化問題，一定數(shù)量的候選解（稱為個體）的抽象表示（稱為染色體）的種群向更好的解進(jìn)化。傳統(tǒng)上，解用二進(jìn)制表示（即0和1的串），但也可以用其他表示方法。進(jìn)化從完全隨機個體的種群開始，之后一代一代發(fā)生。在每一代中，整個種群的適應(yīng)度被評價，從當(dāng)前種群中隨機地選擇多個個體（基于它們的適應(yīng)度），通過自然選擇和突變產(chǎn)生新的生命種群，該種群在算法的下一次迭代中成為當(dāng)前種群。

光看定義，可能思路并不清晰，咱們來幾個清晰的圖解、步驟、公式：

基本遺傳算法的框圖：

所以，遺傳算法基本步驟是：

1）  初始化   t←0進(jìn)化代數(shù)計數(shù)器；T是最大進(jìn)化代數(shù)；隨機生成M個個體作為初始群體    P（t）；

2）  個體評價 計算P（t）中各個個體的適應(yīng)度值；

3）  選擇運算 將選擇算子作用于群體；

4）  交叉運算 將交叉算子作用于群體；

5）  變異運算 將變異算子作用于群體，并通過以上運算得到下一代群體P（t + 1）;

6）  終止條件判斷  t≦T：t← t+1 轉(zhuǎn)到步驟2；

               t>T：終止 輸出解。 

好的，看下遺傳算法的偽代碼實現(xiàn)：

▲Procedures  GA：   偽代碼

begin

       initialize P(0);

       t = 0;             //t是進(jìn)化的代數(shù)，一代、二代、三代...

       while(t <= T) do

              for i = 1 to M  do     //M是初始種群的個體數(shù)

                     Evaluate fitness of P(t);  //計算P（t）中各個個體的適應(yīng)度

              end for

              for i = 1 to M  do

                     Select operation to P(t);  //將選擇算子作用于群體

              end for

              for i = 1 to M/2  do

                     Crossover operation to P(t); //將交叉算子作用于群體

              end for

              for i = 1 to M  do

                     Mutation operation to P(t);  //將變異算子作用于群體

              end for

              for i = 1 to M  do

                     P(t+1) = P(t);      //得到下一代群體P（t + 1）

              end for

              t = t + 1;      //終止條件判斷  t≦T：t← t+1 轉(zhuǎn)到步驟2

       end while

end

二、深入遺傳算法

1、智能優(yōu)化算法概述

智能優(yōu)化算法又稱現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強且適合于并行處理的算法。

這種算法一般具有嚴(yán)密的理論依據(jù)，而不是單純憑借專家經(jīng)驗，理論上可以在一定的時間內(nèi)找到最優(yōu)解或近似最優(yōu)解。 

遺傳算法屬于智能優(yōu)化算法之一。 

常用的智能優(yōu)化算法有：

遺傳算法 、模擬退火算法、禁忌搜索算法、粒子群算法、蟻群算法。

（本經(jīng)典算法研究系列，日后將陸續(xù)闡述模擬退火算法、粒子群算法、蟻群算法。）

2、遺傳算法概述

遺傳算法是由美國的J. Holland教授于1975年在他的專著《自然界和人工系統(tǒng)的適應(yīng)性》中首先提出的。

借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。 

模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象。

在每次迭代中都保留一組候選解，并按某種指標(biāo)從解群中選取較優(yōu)的個體，利用遺傳算子(選擇、交叉和變異)對這些個

體進(jìn)行組合，產(chǎn)生新一代的候選解群，重復(fù)此過程，直到滿足某種收斂指標(biāo)為止。 

基本遺傳算法（Simple Genetic Algorithms，GA)又稱簡單遺傳算法或標(biāo)準(zhǔn)遺傳算法），是由Goldberg總結(jié)出的一種最基本的遺傳算法，其遺傳進(jìn)化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。

3、基本遺傳算法的組成

（1）編碼（產(chǎn)生初始種群）

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

（3）遺傳算子（選擇、交叉、變異）

（4）運行參數(shù)

接下來，咱們分門別類，分別闡述著基本遺傳算法的五個組成部分：

1、編碼

遺傳算法（GA）通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。

正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。

基本遺傳算法（SGA）使用二進(jìn)制串進(jìn)行編碼。 

初始種群：基本遺傳算法（SGA）采用隨機方法生成若干個個體的集合，該集合稱為初始種群。

初始種群中個體的數(shù)量稱為種群規(guī)模。

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

遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。

適應(yīng)度函數(shù)是遺傳算法進(jìn)化過程的驅(qū)動力，也是進(jìn)行自然選擇的唯一標(biāo)準(zhǔn)，

它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。 

3.1、選擇算子

遺傳算法使用選擇運算對個體進(jìn)行優(yōu)勝劣汰操作。

適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。

選擇操作的任務(wù)就是從父代群體中選取一些個體，遺傳到下一代群體。

基本遺傳算法（SGA）中選擇算子采用輪盤賭選擇方法。

Ok，下面就來看下這個輪盤賭的例子，這個例子通俗易懂，對理解選擇算子幫助很大。

輪盤賭選擇方法
輪盤賭選擇又稱比例選擇算子，其基本思想是：
各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。

設(shè)群體大小為N，個體xi 的適應(yīng)度為 f(xi)，則個體xi的選擇概率為：

輪盤賭選擇法可用如下過程模擬來實現(xiàn)：
(1)在［0, 1］內(nèi)產(chǎn)生一個均勻分布的隨機數(shù)r。
(2)若r≤q1,則染色體x1被選中。
(3)若qk-1<r≤qk(2≤k≤N), 則染色體xk被選中。
其中的qi稱為染色體xi (i=1, 2, …, n)的積累概率, 其計算公式為：

積累概率實例： 

輪盤賭選擇方法的實現(xiàn)步驟:
（1）計算群體中所有個體的適應(yīng)度值；
（2）計算每個個體的選擇概率；
（3）計算積累概率；
（4）采用模擬賭盤操作（即生成0到1之間的隨機數(shù)與每個個體遺傳到下一代群體的概率進(jìn)行匹配）
來確定各個個體是否遺傳到下一代群體中。

例如，有染色體
s1= 13 (01101)
s2= 24 (11000)
s3= 8   (01000)
s4= 19 (10011)

假定適應(yīng)度為f(s)=s^2 ，則
f (s1) = f(13) = 13^2 = 169
f (s2) = f(24) = 24^2 = 576
f (s3) = f(8) = 8^2 = 64
f (s4) = f(19) = 19^2 = 361

染色體的選擇概率為：

染色體的累計概率為：

根據(jù)上面的式子，可得到：

例如設(shè)從區(qū)間［0, 1］中產(chǎn)生4個隨機數(shù): 

   r1 = 0.450126,    r2 = 0.110347 

   r3 = 0.572496,    r4 = 0.98503 

3.2、交叉算子

交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率 Pc 按某種方式相互交換其部分基因，
從而形成兩個新的個體。

交叉運算是遺傳算法區(qū)別于其他進(jìn)化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，
是產(chǎn)生新個體的主要方法。
基本遺傳算法（SGA）中交叉算子采用單點交叉算子。

單點交叉運算

3.3、變異算子 

變異運算，是指改變個體編碼串中的某些基因值，從而形成新的個體。
變異運算是產(chǎn)生新個體的輔助方法，決定遺傳算法的局部搜索能力，保持種群多樣性。

交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。
基本遺傳算法（SGA）中變異算子采用基本位變異算子。

基本位變異算子是指對個體編碼串隨機指定的某一位或某幾位基因作變異運算。
對于二進(jìn)制編碼符號串所表示的個體，若需要進(jìn)行變異操作的某一基因座上的原有基因值為0，
則將其變?yōu)?；反之，若原有基因值為1，則將其變?yōu)? 。

基本位變異算子的執(zhí)行過程：

4、運行參數(shù)

（1）M  ：種群規(guī)模
（2）T  ： 遺傳運算的終止進(jìn)化代數(shù)
（3）Pc  ：交叉概率
（4）Pm ：變異概率

三、淺出遺傳算法

遺傳算法的本質(zhì)

遺傳算法本質(zhì)上是對染色體模式所進(jìn)行的一系列運算，即通過選擇算子將當(dāng)前種群中的優(yōu)良模式遺傳
到下一代種群中，利用交叉算子進(jìn)行模式重組，利用變異算子進(jìn)行模式突變。
通過這些遺傳操作，模式逐步向較好的方向進(jìn)化，最終得到問題的最優(yōu)解。

遺傳算法的主要有以下八方面的應(yīng)用：
（1）組合優(yōu)化      （2）函數(shù)優(yōu)化 （3）自動控制      （4）生產(chǎn)調(diào)度
（5）圖像處理      （6）機器學(xué)習(xí) （7）人工生命      （8）數(shù)據(jù)挖掘

四、遺傳算法的應(yīng)用

遺傳算法的應(yīng)用舉例、透析本質(zhì)（這個例子簡明、但很重要）

已知x為整數(shù)，利用遺傳算法求解區(qū)間［0, 31］上的二次函數(shù)y=x2的最大值。

[分析]

原問題可轉(zhuǎn)化為在區(qū)間［0, 31］中搜索能使 y 取最大值的點 a 的問題。
個體：［0, 31］ 中的任意點x
適應(yīng)度：函數(shù)值f(x)=x2
解空間：區(qū)間［0, 31］

這樣, 只要能給出個體x的適當(dāng)染色體編碼, 該問題就可以用遺傳算法來解決。

[解]

(1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。
將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個體組成初始種群S1

s1= 13 (01101),  s2= 24 (11000)
s3= 8 (01000),    s4= 19 (10011） 

(2) 定義適應(yīng)度函數(shù), 取適應(yīng)度函數(shù)
f (x)=x^2

(3) 計算各代種群中的各個體的適應(yīng)度, 并對其染色體進(jìn)行遺傳操作,
直到適應(yīng)度最高的個體，即31（11111）出現(xiàn)為止。

首先計算種群S1中各個體：
s1= 13(01101),    s2= 24(11000)
s3= 8(01000),      s4= 19(10011)
的適應(yīng)度f (si), 容易求得：
f (s1) = f(13) = 13^2 = 169
f (s2) = f(24) = 24^2 = 576
f (s3) = f(8) = 8^2 = 64
f (s4) = f(19) = 19^2 = 361

再計算種群S1中各個體的選擇概率：

由此可求得
P(s1) = P(13) = 0.14
P(s2) = P(24) = 0.49
P(s3) = P(8) = 0.06
P(s4) = P(19) = 0.31

再計算種群S1中各個體的積累概率：

選擇-復(fù)制 

設(shè)從區(qū)間［0, 1］中產(chǎn)生4個隨機數(shù)如下:
r1 = 0.450126,     r2 = 0.110347
r3 = 0.572496,     r4 = 0.98503

于是，經(jīng)復(fù)制得群體：
s1’ =11000（24）,  s2’ =01101（13）
s3’ =11000（24）（24被選中倆次）,  s4’ =10011（19）

交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運算。
設(shè)s1’與s2’配對，s3’與s4’配對。
s1’ =11000（24）,  s2’ =01101（13）
s3’ =11000（24）,  s4’ =10011（19）
分別交換后兩位基因，得新染色體：
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位，所以本輪遺傳操作不做變異。

于是，得到第二代種群S2：
s1=11001（25）,   s2=01100（12）
s3=11011（27）,   s4=10000（16）

第二代種群S2中各染色體的情況：

假設(shè)這一輪選擇-復(fù)制操作中，種群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）

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

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

設(shè)這一輪的選擇-復(fù)制結(jié)果為：

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）

這一輪仍然不會發(fā)生變異。

于是，得第四代種群S4： 

s1=11111（31）(出現(xiàn)最優(yōu)解),  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中，即得原問題的解，即函數(shù)y=x2的最大值為961。 

所以，綜合以上各代群的情況，如下：