智能控制系統(tǒng)三13.遺傳算法的理論基礎

指導遺傳算法的基本理論，是J.H.Holland教授創(chuàng)立的模式理論。該理論揭示了遺傳算法的基本機理。3.1基本概念問題的引出

例：求maxf(x)=x2x∈{0,31}23.遺傳算法的理論基礎

[分析]?當編碼的最左邊字符為“1”時，其個體適配值較大，如2號個體和4號個體，我們將其記為“1****”；其中2號個體適配值最大，其編碼的左邊兩位都是1，我們記為“11***”；?當編碼的最左邊字符為“0”時，其個體適配值較小，如1號和3號個體，我們記為“0****”。33.遺傳算法的理論基礎

[結(jié)論]

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

這種特定的組合形式就叫模式。43.遺傳算法的理論基礎模式、模式位數(shù)及模式定義長度

模式(Schemata)——指編碼的字符串在某些確定位置上具有相似性的位串子集的相似性模板。使用三元素字母表{0，1，*}可以構(gòu)造出任意模式。其中“*”稱為通配符，表示這一位可以是{0，1}中任意一種。使用大寫字母H代表模式，例如H=1100*53.遺傳算法的理論基礎匹配的定義模式中的“0”和位串中的“0”匹配，模式中的“1”和位串中的“1”匹配，模式中的“*”和位串中的“0”或“1”匹配.以五位二進制字符串為例。模式*111*

可匹配4個個體：01110，01111，11110，11111模式*0000

則匹配2個個體：10000，0000063.遺傳算法的理論基礎模式位數(shù)(Order)——指模式中有定義的非“*”位個數(shù)，記為O(H)例如，若H=00*1*0，則O(H)=4模式的定義長度（DefiningLength）——指模式中最兩端的有定義位置之間的距離，記為(H)

例如，若H=00*1*0，則(H)=6-1=5若H=**11**，則(H)=4-3=1若H=******，則(H)=073.遺傳算法的理論基礎模式長度越短，被破壞的可能性越小，長度為0的模式最難被破壞。編碼位串的模式數(shù)目模式總數(shù)二進制位串假設字符串的長度為l，字符串中每一個字符可取(0,1,*)三個符號中任意一個，可能組成的模式數(shù)目最多為：3×3×3×3×3…×3=3l83.遺傳算法的理論基礎一般情況假設字符的長度為l，字符串中有k種具體字符可取，可能組成的模式數(shù)目最多為：(k+1)×(k+1)×(k+1)×(k+1)×…×(k+1)=(k+1)l某一特定編碼串包含的模式數(shù)二進制位串對于長度為l的某二進制字符串，它含有的模式總數(shù)最多為：

2×2×2×…×2=2l

93.遺傳算法的理論基礎

[注]這個數(shù)目是指字符串已確定為0或1，每個字符只能在已定值(0/1)或*中選取。某一特定群體所含模式數(shù)在長度為l

，規(guī)模為n的二進制編碼字符串群體中，一般包含有2l~n·2l個模式。103.遺傳算法的理論基礎3.2模式定理引入模式的概念之后，遺傳算法的實質(zhì)可看作是對模式的一種運算。對基本遺傳算法(GA)而言，也就是某一模式H

的各個樣本經(jīng)過選擇運算、交義運算、變異運算之后，得到一些新的樣本和新的模式。復制時的模式數(shù)目

[公式推導]假設在第t次迭代時,群體A(t)中有n個個體,其中有m個符合特定模式Ｈ,記作m(Ｈ,t)。

113.遺傳算法的理論基礎個體Ａi

按其適配值fi

的大小進行復制。從統(tǒng)計意義講，個體Ａi被復制的概率pi是：

因此復制后在下一代群體Ａ(t+1)中，群體內(nèi)屬于模式Ｈ（或稱與模式Ｈ匹配）的個體數(shù)目m(Ｈ,t+1)

可用平均適配值按下式近似計算(ｆ(Ｈ)是屬于模式H的個體的平均適配值）：123.遺傳算法的理論基礎設第t代所有個體(不論它屬于何種模式)的平均適配值是,有等式:綜合上述兩式，復制后模式H所擁有的個體數(shù)目可按下式近似計算：

133.遺傳算法的理論基礎[結(jié)論]

?上式說明復制后下一代群體中屬于模式H的個體數(shù)目，取決于該模式的平均適配值與群體的平均適配值之比;?只有當模式H的平均值大于群缽的平均值時，H模式的個體數(shù)目才能增長。否則，H模式的數(shù)目要減小。

?模式的這種增減規(guī)律，正好符合復制操作的“優(yōu)勝劣汰”原則，這也說明模式的確能描述編碼字符串的內(nèi)部特征。

143.遺傳算法的理論基礎[進一步推導]假設某一模式H在復制過程中其平均適應度f(H)比群體的平均適配值高出一個定值，其中c為常數(shù)，則上式改寫為：從第一代開始，若模式H以常數(shù)c繁殖到第t+1代，其個體數(shù)目為：[結(jié)論]說明模式H所擁有的個體數(shù)目在復制過程中以指數(shù)形式增加或減小。153.遺傳算法的理論基礎交叉時的模式數(shù)目這里以單點交叉算子為例研究。[舉例]有兩個模式H1:“*1****0”

H2:“***10**”

它們有一個共同的可匹配的個體（可與模式匹配的個體稱為模式的表示）

A:“0111000”

選擇個體A進行交叉,隨機選擇交叉點。

163.遺傳算法的理論基礎

H1:“*1****0”交叉點選在第2~6之間都可能破壞模式H1;

H2:“***10**”交叉點在第4~5之間才破壞H2

。[公式推導]交換發(fā)生在模式H的定義長度(H)范圍內(nèi)，即模式被破壞的概率是：例：H1被破壞的概率為：5/6

H2被破壞的概率為：1/6

173.遺傳算法的理論基礎模式不被破壞，存活下來的概率為：若交叉概率為pc，則模式存活下來的概率為：經(jīng)復制、交叉操作后，模式H在下一代群體中所擁有的個體數(shù)目為：

183.遺傳算法的理論基礎

[結(jié)論]

模式的定義長度對模式的存亡影響很大，模式的長度越大，越容易被破壞。變異時的模式數(shù)目這里以基本位變異算子為例研究。[公式推導]

變異時個體的每一位發(fā)生變化的概率是變異概率pm，也就是說，每一位存活的概率是(1-pm)。根據(jù)模式位數(shù)o(H)，可知模式中有明確含意的字符有o(H)個，于是模式H存活的概率是：193.遺傳算法的理論基礎通常pm<<1，上式用泰勒級數(shù)展開取一次項，可近似表達為：

[結(jié)論]上式說明，模式的階次o(H)越低，模式H

存活的可能性越大，反之亦然。模式定理綜合上述分析可以得出遺傳算法經(jīng)復制、交叉、變異操作后，模式H在下一代群體中所擁有的個體數(shù)目：

203.遺傳算法的理論基礎

[模式定理]適應度高于群體平均適應度的，長度較短，低階的模式在遺傳算法的迭代過程中將按指數(shù)規(guī)律增長。

模式定理深刻地闡明了遺傳算法中發(fā)生“優(yōu)勝劣汰