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

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

例1

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

y=x2

31

XY

分析

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

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

由此可求得

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●賭輪選擇法

在算法中賭輪選擇法可用下面的子過(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稱(chēng)為染色體xi(i=1,2,…,n)的積累概率,其計(jì)算公式為選擇-復(fù)制

設(shè)從區(qū)間［0,1］中產(chǎn)生4個(gè)隨機(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中的全體染色體都參加交叉運(yùn)算。設(shè)s1’與s2’配對(duì)，s3’與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位，所以本輪遺傳操作不做變異。

于是，得到第二代種群S2：

s1=11001（25）,s2=01100（12）

s3=11011（27）,s4=10000（16）

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

染色體

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

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

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

染色體

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

估計(jì)的選中次數(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）

做交叉運(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。

YYy=x2

8131924

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

12162527

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

9192428

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

16242831

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

◆遺傳算法的主要特點(diǎn)

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

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

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

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

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

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

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

1.1問(wèn)題的引出

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

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

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

[結(jié)論]從這個(gè)例子可以看比，我們?cè)诜治鼍幋a字符串時(shí)，常常只關(guān)心某一位或某幾位字符，而對(duì)其他字符不關(guān)心。換句話(huà)講．我們只關(guān)心字符的某些特定形式，如1****，11***，0****。這種特定的形式就叫模式。

1.2模式、模式階及模式定義長(zhǎng)度

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

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

?

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

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

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

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

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

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

?一般地，有式子

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

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

(1)模式總數(shù)

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

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

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

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

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

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

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

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

[模式定理]

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

[舉例]

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

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

模式定理告訴我們：

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

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

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

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

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

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

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

?群體中有8個(gè)個(gè)體。

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