3.2遺傳算法的應用與特點一、遺傳算法應用舉例二、遺傳算法的特點與優勢一、遺傳算法應用舉例

例1

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

y=x2

31

XY

分析

原問題可轉化為在區間［0,31］中搜索能使y取最大值的點a的問題。那么，［0,31］中的點x就是個體,函數值f(x)恰好就可以作為x的適應度，區間［0,31］就是一個(解)空間。這樣,只要能給出個體x的適當染色體編碼,該問題就可以用遺傳算法來解決。

解

(1)

設定種群規模,編碼染色體，產生初始種群。將種群規模設定為4；用5位二進制數編碼染色體；取下列個體組成初始種群S1:s1=13(01101),s2=24(11000)s3=8(01000),s4=19(10011)

(2)定義適應度函數,

取適應度函數：f(x)=x2

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

首先計算種群S1中各個體

s1=13(01101),s2=24(11000)

s3=8(01000),s4=19(10011)的適應度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］區間內產生一個均勻分布的隨機數r。②若r≤q1,則染色體x1被選中。③若qk-1<r≤qk(2≤k≤N),則染色體xk被選中。其中的qi稱為染色體xi(i=1,2,…,n)的積累概率,其計算公式為選擇-復制

設從區間［0,1］中產生4個隨機數如下:

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

染色體

適應度選擇概率積累概率選中次數s1=011011690.140.141s2=110005760.490.632s3=01000640.060.690s4=100113610.311.001于是，經復制得群體：s1’

=11000（24）,s2’

=01101（13）s3’

=11000（24）,s4’

=10011（19）交叉

設交叉率pc=100%，即S1中的全體染色體都參加交叉運算。設s1’與s2’配對，s3’與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中各染色體的情況

染色體

適應度選擇概率積累概率

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

假設這一輪選擇-復制操作中，種群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中各染色體的情況

染色體

適應度選擇概率積累概率

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

設這一輪的選擇-復制結果為：

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。

YYy=x2

8131924

X第一代種群及其適應度y=x2

12162527

XY第二代種群及其適應度y=x2

9192428

XY第三代種群及其適應度y=x2

16242831

X第四代種群及其適應度二、遺傳算法的特點與優勢

◆遺傳算法的主要特點

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

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

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

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

——遺傳算法的適應性強,除需知適應度函數外,幾乎不需要其他的先驗知識。

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

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

1.1問題的引出

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

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

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

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

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

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

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

?

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

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

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

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

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

?當模式階次為零時，它沒有明確含義的字符，其概括性最強。模式的定義長度(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編碼字符串的模式數目

(1)模式總數

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

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

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

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

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

(3)群體所含模式數

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

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

[模式定理]

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

[舉例]

以maxf(x)=x2x{0,31}為例，圖中：橫坐標表示x，縱坐標代表適應度f(x)=x2，用千分數表示，弧線表示適應度曲線，網點區代表所有符合此模式的個體集合。模式1：1****模式2：10***模式3：**1*1[結論]

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

模式定理告訴我們：

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

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

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

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

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

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

?問題的最優用三個建筑塊BB1,BB2,BB3表示；

?群體中有8個個體。

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