經(jīng)典算法研究系列：七、深入淺出遺傳算法，透析GA本質(zhì)

2011.02.03

關(guān)注

深入淺出遺傳算法，透析GA本質(zhì)收藏

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

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

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

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

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

一、初探遺傳算法

Ok，先看維基百科對(duì)遺傳算法所給的解釋?zhuān)?/span>

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

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

光看定義，可能思路并不清晰，咱們來(lái)幾個(gè)清晰的圖解、步驟、公式：

基本遺傳算法的框圖：

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

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

2）個(gè)體評(píng)價(jià) 計(jì)算P（t）中各個(gè)個(gè)體的適應(yīng)度值；

3）選擇運(yùn)算將選擇算子作用于群體；

4）交叉運(yùn)算將交叉算子作用于群體；

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

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

t>T：終止輸出解。

好的，看下遺傳算法的偽代碼實(shí)現(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是初始種群的個(gè)體數(shù)

Evaluate fitness of P(t); //計(jì)算P（t）中各個(gè)個(gè)體的適應(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)化算法又稱(chēng)現(xiàn)代啟發(fā)式算法，是一種具有全局優(yōu)化性能、通用性強(qiáng)且適合于并行處理的算法。

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

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

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

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

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

2、遺傳算法概述

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

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

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

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

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

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

3、基本遺傳算法的組成

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

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

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

（4）運(yùn)行參數(shù)

接下來(lái)，咱們分門(mén)別類(lèi)，分別闡述著基本遺傳算法的五個(gè)組成部分：

1、編碼

遺傳算法（GA）通過(guò)某種編碼機(jī)制把對(duì)象抽象為由特定符號(hào)按一定順序排成的串。

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

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

初始種群：基本遺傳算法（SGA）采用隨機(jī)方法生成若干個(gè)個(gè)體的集合，該集合稱(chēng)為初始種群。

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

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

遺傳算法對(duì)一個(gè)個(gè)體（解）的好壞用適應(yīng)度函數(shù)值來(lái)評(píng)價(jià)，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。

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

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

3.1、選擇算子

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

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

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

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

Ok，下面就來(lái)看下這個(gè)輪盤(pán)賭的例子，這個(gè)例子通俗易懂，對(duì)理解選擇算子幫助很大。

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

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

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

積累概率實(shí)例：

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

例如，有染色體
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ì)概率為：

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

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

r1 = 0.450126, r2 = 0.110347

r3 = 0.572496, r4 = 0.98503

3.2、交叉算子

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

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

單點(diǎn)交叉運(yùn)算

3.3、變異算子

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

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

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

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

4、運(yùn)行參數(shù)

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

三、淺出遺傳算法

遺傳算法的本質(zhì)

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

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

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

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

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

[分析]

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

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

[解]

(1) 設(shè)定種群規(guī)模,編碼染色體，產(chǎn)生初始種群。
將種群規(guī)模設(shè)定為4；用5位二進(jìn)制數(shù)編碼染色體；取下列個(gè)體組成初始種群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) 計(jì)算各代種群中的各個(gè)體的適應(yīng)度, 并對(duì)其染色體進(jìn)行遺傳操作,
直到適應(yīng)度最高的個(gè)體，即31（11111）出現(xiàn)為止。

首先計(jì)算種群S1中各個(gè)體：
s1= 13(01101), s2= 24(11000)
s3= 8(01000), s4= 19(10011)
的適應(yīng)度f(wàn) (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

再計(jì)算種群S1中各個(gè)體的選擇概率：

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

再計(jì)算種群S1中各個(gè)體的積累概率：

選擇-復(fù)制

設(shè)從區(qū)間［0, 1］中產(chǎn)生4個(gè)隨機(jī)數(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中的全體染色體都參加交叉運(yùn)算。
設(shè)s1’與s2’配對(duì)，s3’與s4’配對(duì)。
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個(gè)染色體都被選中，則得到群體：
s1’=11001（25）, s2’= 01100（12）
s3’=11011（27）, s4’= 10000（16）

做交叉運(yùn)算，讓s1’與s2’，s3’與s4’ 分別交換后三位基因，得
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）

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

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

s1’=11100（28）, s2’=11100（28）

s3’=11000（24）, s4’=10011（19）

做交叉運(yùn)算，讓s1’與s4’，s2’與s3’ 分別交換后兩位基因，得