第三章 經(jīng)典進(jìn)化計算-遺傳算法-2

3.2遺傳算法的應(yīng)用與特點一、遺傳算法應(yīng)用舉例二、遺傳算法的特點與優(yōu)勢一、遺傳算法應(yīng)用舉例

例1

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

y=x2

31

XY

分析

原問題可轉(zhuǎn)化為在區(qū)間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數(shù)值f(x)恰好就可以作為x的適應(yīng)度，區(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)=x2

(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)=132=169f(s2)=f(24)=242=576f(s3)=f(8)=82=64f(s4)=f(19)=192=361再計算種群S1中各個體的選擇概率。選擇概率的計算公式為

由此可求得

P(s1)=P(13)=0.14P(s2)=P(24)=0.49P(s3)=P(8)=0.06P(s4)=P(19)=0.31

賭輪選擇示意s40.31s20.49s10.14s30.06●賭輪選擇法

在算法中賭輪選擇法可用下面的子過程來模擬:①在［0,1］區(qū)間內(nèi)產(chǎn)生一個均勻分布的隨機(jī)數(shù)r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為選擇-復(fù)制

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

r1=0.450126,r2=0.110347r3=0.572496,r4=0.98503

染色體

適應(yīng)度選擇概率積累概率選中次數(shù)s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，經(jīng)復(fù)制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉

設(shè)交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設(shè)s1’與s2’配對，s3’與s4’配對。分別交換后兩位基因，得新染色體：

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中各染色體的情況

染色體

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

估計的選中次數(shù)s1=110016250.360.361s2=011001440.080.440s3=110117290.410.852s4=100002560.151.001

假設(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中各染色體的情況

染色體

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

估計的選中次數(shù)s1=111007840.440.442s2=01001810.040.480s3=110005760.320.801s4=100113610.201.001

設(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）,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。

YYy=x2

8131924

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

12162527

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

9192428

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

16242831

X第四代種群及其適應(yīng)度二、遺傳算法的特點與優(yōu)勢

◆遺傳算法的主要特點

——遺傳算法一般是直接在解空間搜索,而不像圖搜索那樣一般是在問題空間搜索,最后才找到解。

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

——遺傳算法總是在尋找優(yōu)解,而不像圖搜索那樣并非總是要求優(yōu)解,而一般是設(shè)法盡快找到解,所以遺傳算法又是一種優(yōu)化搜索算法。

——遺傳算法的搜索過程是從空間的一個點集(種群)到另一個點集(種群)的搜索,而不像圖搜索那樣一般是從空間的一個點到另一個點地搜索。因而它實際是一種并行搜索,適合大規(guī)模并行計算,而且這種種群到種群的搜索有能力跳出局部最優(yōu)解。

——遺傳算法的適應(yīng)性強(qiáng),除需知適應(yīng)度函數(shù)外,幾乎不需要其他的先驗知識。

——遺傳算法長于全局搜索,它不受搜索空間的限制性假設(shè)的約束,不要求連續(xù)性,能以很大的概率從離散的、多極值的、含有噪聲的高維問題中找到全局最優(yōu)解?！暨z傳算法的應(yīng)用函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域;組合優(yōu)化實踐證明，遺傳算法對于組合優(yōu)化中的NP完全問題非常有效;自動控制如基于遺傳算法的模糊控制器優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等;機(jī)器人智能控制遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運動軌跡規(guī)劃、機(jī)器人逆運動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行動協(xié)調(diào)等;組合圖像處理和模式識別目前已在圖像恢復(fù)、圖像邊緣持征提取、幾何形狀識別等方面得到了應(yīng)用;人工生命基于遺傳算法的進(jìn)化模型是研究人工生命現(xiàn)象的重要理論基礎(chǔ)，遺傳算法已在其進(jìn)化模型、學(xué)習(xí)模型、行為模型等方面顯示了初步的應(yīng)用能力；遺傳程序設(shè)計Koza發(fā)展了遺傳程序設(shè)計的慨念，他使用了以LISP語言所表示的編碼方法，基于對一種樹型結(jié)構(gòu)所進(jìn)行的遺傳操作自動生成計算機(jī)程序;

指導(dǎo)遺傳算法的基本理論，是J.H.Holland教授創(chuàng)立的模式理論。該理論揭示遺傳算法的基本機(jī)理。一、基本概念二、模式定理三、建筑塊假說四、隱含并行性3.3—遺傳算法的模式理論一、基本概念

1.1問題的引出

例：求maxf(x)=x2x{0,31}[分析]

?當(dāng)編碼的最左邊字符為“1”時，其個體適應(yīng)度較大，如2號個體和4號個體，我們將其記為“1****”；

其中2號個體適應(yīng)度最大，其編碼的左邊兩位都是1，我們記為“11***”；?當(dāng)編碼的最左邊字符為“0”時，其個體適應(yīng)度較小，如1號和3號個體，我們記為“0****”。

[結(jié)論]從這個例子可以看比，我們在分析編碼字符串時，常常只關(guān)心某一位或某幾位字符，而對其他字符不關(guān)心。換句話講．我們只關(guān)心字符的某些特定形式，如1****，11***，0****。這種特定的形式就叫模式。

1.2模式、模式階及模式定義長度

模式(Schema)——指編碼的字符串中具有類似特征的子集。以五位二進(jìn)制字符串為例，模式

*111*可代表4個個體：01110，01111，11110，11111；模式*0000則代表2個個體：10000，00000。

?

個體是由二值字符集V={0,1}中的元素所組成的一個編碼串;

?而模式卻是由三值字符集V={0,1,*}中的元素所組成的一個編碼串，其中“*

”表示通配符，它既可被當(dāng)作“1”也可被當(dāng)作“0”。模式階(SchemaOrder)

——指模式中已有明確含意(二進(jìn)制字符時指0或1)的字符個數(shù)，記做o(s)，式中s代表模式。例如，模式(011*1**)含有4個明確含意的字符，其階次是4，記作o(011*1**)=4;模式(0******)的階次是1，記作o(0******)=1。

?階次越低，模式的概括性越強(qiáng)，所代表的編碼串個體數(shù)也越多，反之亦然；

?當(dāng)模式階次為零時，它沒有明確含義的字符，其概括性最強(qiáng)。模式的定義長度(SchemaDefiningLength)——指模式中第一個和最后一個具有明確含意的字符之間的距離，記作(s)。例如，模式(011*l**)的第一個字符為0，最后一個字符為l，中間有3個字符，其定義長度為4，記作(011*l**)=4；模式(0******)的長度是0，記作(0******)=0；

?一般地，有式子

(s)＝b–a式中b—模式s中最后一個明確字符的位置;a—模式s中最前一個明確字符的位置。

?模式的長度代表該模式在今后遺傳操作(交叉、變異)中被破壞的可能性：模式長度越短，被破壞的可能性越小，長度為0的模式最難被破壞。1.3編碼字符串的模式數(shù)目

(1)模式總數(shù)

?二進(jìn)制字符串假設(shè)字符的長度為l，字符串中每一個字符可取(0,1,*)三個符號中任意一個，可能組成的模式數(shù)目最多為：333…3=(2+1)l

?一般情況下，假設(shè)字符串長度為l，字符的取值為k種，字符串組成的模式數(shù)目n1最多為：n1=(k+1)l(2)編碼字符串（一個個體編碼串）所含模式總數(shù)

?二進(jìn)制字符串對于長度為l的某二進(jìn)制字符串，它含有的模式總數(shù)最多為：222…2=2l

[注意]這個數(shù)目是指字符串已確定為0或1，每個字符只能在已定值(0/1)或*中選??；前面所述的n1指字符串未確定，每個字符可在{0,1,*}三者中選取。

?一般情況下長度為l、取值有k種的某一字符串，它可能含有的模式數(shù)目最多為：n2=kl

(3)群體所含模式數(shù)

在長度為l，規(guī)模為M的二進(jìn)制編碼字符串群體中，一般包含有2l~M·2l個模式。二、模式定理

由前面的敘述我們可以知道，在引入模式的概念之后，遺傳算法的實質(zhì)可看作是對模式的一種運算。對基本遺傳算法(GA)而言，也就是某一模式s的各個樣本經(jīng)過選擇運算、交義運算、變異運算之后，得到一些新的樣本和新的模式。

[模式定理]

適應(yīng)度高于群體平均適應(yīng)度的，長度較短，低階的模式在遺傳算法的迭代過程中將按指數(shù)規(guī)律增長。模式定理深刻地闡明了遺傳算法中發(fā)生“優(yōu)勝劣汰”的原因。在遺傳過程中能存活的模式都是定義長度短、階次低、平均適應(yīng)度高于群體平均適應(yīng)度的優(yōu)良模式。遺傳算法正是利用這些優(yōu)良模式逐步進(jìn)化到最優(yōu)解。2.5模式定理示例例：求maxf(x)=x2x{0,31}個體變化叉叉S1S2S3叉三、建筑塊假說3.1模式對搜索空間的劃分

[舉例]

以maxf(x)=x2x{0,31}為例，圖中：橫坐標(biāo)表示x，縱坐標(biāo)代表適應(yīng)度f(x)=x2，用千分?jǐn)?shù)表示，弧線表示適應(yīng)度曲線，網(wǎng)點區(qū)代表所有符合此模式的個體集合。模式1：1****模式2：10***模式3：**1*1[結(jié)論]

模式能夠劃分搜索空間，而且模式的階越高，對搜索空間的劃分越細(xì)致。3.2分配搜索次數(shù)

模式定理告訴我們：

GA根據(jù)模式的適應(yīng)度、長度和階次為模式分配搜索次數(shù)。為那些適應(yīng)度較高，長度較短，階次較低的模式分配的搜索次數(shù)按指數(shù)率增長；為那些適應(yīng)度較低，長度較長，階次較高的模式分配的搜索次數(shù)按指數(shù)率衰減。3.3建筑塊假說

前面我們已經(jīng)介紹了GA如何劃分搜索空間和在各個子空間中分配搜索次數(shù)，

那么GA如何利用搜索過程中的積累信息加快搜索速度呢？Holland和Goldberg在模式定理的基礎(chǔ)上提出了“建筑塊假說”。

[建筑塊（或稱積木塊）(BulidingBlock)]——短定義長度、低階、高適應(yīng)度的模式。

之所以稱之為建筑塊（積木塊），是由于遺傳算法的求解過程并不是在搜索空間中逐一地測試各個基因的枚舉組合，而是通過一些較好的模式，像搭積木一樣、將它們拼接在一起，從而逐漸地構(gòu)造出適應(yīng)度越來越高的個體編碼串。

[建筑塊假說]GA在搜索過程中將不同的“建筑塊”通過遺傳算子（如交叉算子）的作用結(jié)合在一起，形成適應(yīng)度更高的新模式。這樣將大大縮小GA的搜索范圍。[建筑塊混合]——建筑塊通過遺傳算子的作用集合在一起的過程稱為“建筑塊混合”。當(dāng)那些構(gòu)成最優(yōu)點（或近似最優(yōu)點）的“建筑塊”結(jié)合在一起時，就得到了最優(yōu)點。[建筑塊混合的例子]

?問題的最優(yōu)用三個建筑塊BB1,BB2,BB3表示；

?群體中有8個個體。

?初始群體中個體1，個體2包含建筑塊BB1，個體3包含BB3,個體5包含BB2。P1P2P3P4P5P6P7P8BB