1、 指導遺傳算法的基本理論，是指導遺傳算法的基本理論，是J.H.Holland教授創立的教授創立的模式理論模式理論。該理論揭示。該理論揭示 了遺傳算法的基本機理。了遺傳算法的基本機理。 例：例： 求求 max f(x)=x2 x 0,31 分析分析 當編碼的最左邊字符為當編碼的最左邊字符為“1”時，其個體適應度較大，如時，其個體適應度較大，如2號個體和號個體和4號個體，號個體， 我們將其記為我們將其記為 “ 1* ”； 其中其中2號個體適應度最大，其編碼的左邊兩位都是號個體適應度最大，其編碼的左邊兩位都是1，我們記為，我們記為 “ 11* ”； 當編碼的最左邊字符為當編碼的最左邊字符為“0”時，

2、其個體適應度較小，如時，其個體適應度較小，如1號和號和3號個體，號個體， 我們記為我們記為 “ 0* ”。 結論結論 從這個例子可以看比，我們在分析編碼字符串時，常常只關心某一位或某幾位從這個例子可以看比，我們在分析編碼字符串時，常常只關心某一位或某幾位字符，而對其他字符不關心。換句話講我們只關心字符的某些特定形式，如字符，而對其他字符不關心。換句話講我們只關心字符的某些特定形式，如 1*，11*，0*。這種特定的形式就叫。這種特定的形式就叫模式模式。 指指編碼的字編碼的字符串中具符串中具有有類似特征的子集。類似特征的子集。 以五以五位位二進制字符二進制字符串串為例，為例， 模式模式 可代表可

3、代表4個個體：個個體： 01110，01111，11110，11111； 模式模式 則代表則代表2個個體：個個體：10000，00000 。 個體個體是由二值字符集是由二值字符集 V=0, 1 中的元素所組成的一個編碼串中的元素所組成的一個編碼串; 而而模式模式卻是由三值字符集卻是由三值字符集 V=0, 1,* 中的元素所組成的一個編碼串，其中中的元素所組成的一個編碼串，其中 “ ” 表示通配符，它既可被當作表示通配符，它既可被當作 “1” 也可被當作也可被當作 “0”。 指模式中已有明確含意指模式中已有明確含意(二進制字符時指二進制字符時指0或或1)的字符個數，的字符個數， 記做記做 o(s

4、)，式中，式中 s 代表模式。代表模式。 例如，模式例如，模式 ( 011*1* ) 含有含有4個明確含意的字符，其階次是個明確含意的字符，其階次是4， 記作記作 o( 011*1* ) =4; 模式模式 ( 0* ) 的階次是的階次是1，記作，記作 o( 0* ) =1。 當模式階次為零時，它沒有明確含義的字符，其概括性最強。當模式階次為零時，它沒有明確含義的字符，其概括性最強。 指模式中第一個和最后一個具有明確含意的字符之間的距離，記作指模式中第一個和最后一個具有明確含意的字符之間的距離，記作 (s)。 例如，模式例如，模式( 011*l* ) 的第一個字符為的第一個字符為0，最后一個字符

5、為，最后一個字符為l，中間有，中間有3個字個字 符，其定義長度為符，其定義長度為4，記作，記作 ( 011*l* ) = 4 ； 模式模式 ( 0* ) 的長度是的長度是0，記作，記作 ( 0* ) = 0 ； 一般地，有式子一般地，有式子 (s)b a 式中式中 b模式模式s 中最后一個明確字符的位置中最后一個明確字符的位置; a模式模式s 中最前一個明確字符的位置。中最前一個明確字符的位置。 二進制字符串二進制字符串 假設字符的長度為假設字符的長度為l，字符串中每一個字符可取，字符串中每一個字符可取( 0, 1, * ) 三個符號中任意三個符號中任意 一個，可能組成的模式數目最多為：一個，

6、可能組成的模式數目最多為： 3 3 3 3 = 一般情況下一般情況下， 假設字符串長度為假設字符串長度為l，字符的取值為，字符的取值為 k 種，字符串組成的模式數目種，字符串組成的模式數目 n1 最多最多 為：為： n1=(k+1)l 二進制字符串二進制字符串 對于長度為對于長度為l的某二進制字符串，它含有的模式總數最多為：的某二進制字符串，它含有的模式總數最多為： 2 2 2 2 = 注意注意 這個數目是指字符串已確定為這個數目是指字符串已確定為0或或1，每個字符只能在已定值，每個字符只能在已定值 (0/1)或或 * 中選?。恢羞x??； 前面所述的前面所述的 n1 指字符串未確定，每個字符可在

7、指字符串未確定，每個字符可在0, 1, * 三者中選取。三者中選取。 一般情況下一般情況下 長度為長度為l、取值有、取值有 k 種的某一字符串，它可能含有的模式數目最多為：種的某一字符串，它可能含有的模式數目最多為： n2 = kl 在長度為在長度為l，規模為規模為M的二進制編碼字符串群體中，一般包含有的二進制編碼字符串群體中，一般包含有2l M 2l個個 模式。模式。 由前面的敘述我們可以知道，在引入模式的概念之后，遺傳算法的實質可看由前面的敘述我們可以知道，在引入模式的概念之后，遺傳算法的實質可看 作是對模式的一種運算。對基本遺傳算法作是對模式的一種運算。對基本遺傳算法(GA)而言，也就是

8、某一模式而言，也就是某一模式s 的各個的各個 樣本經過選擇運算、交義運算、變異運算之后，得到一些新的樣本和新的模式。樣本經過選擇運算、交義運算、變異運算之后，得到一些新的樣本和新的模式。 這里以比例選擇算子為例研究。這里以比例選擇算子為例研究。 (1) 假設在第假設在第t次迭代時次迭代時, 群體群體P(t)中有中有M個個體個個體, 其中其中m個個體屬于模式個個體屬于模式s, 記作記作m(s,t)。 (2) 個體個體 ai 按其適應度按其適應度 fi 的大小進行復制。的大小進行復制。 從統計意義講，個體從統計意義講，個體ai被復制的概率被復制的概率pi是：是： M1jii) j ( ffp(3)

9、 因此復制后在下一代群體因此復制后在下一代群體 P(t+1)中，群體內屬于模式中，群體內屬于模式s（或稱與模式（或稱與模式s匹配）匹配） 的個體數目的個體數目 m(s,t+1) 可用平均適應度按下式近似計算：可用平均適應度按下式近似計算： M1j) j (fM) t , s (m)1t , s (mf(s)式中式中 第第t代屬于模式代屬于模式 s 的所有的所有 個體之平均適應度；個體之平均適應度； M群體中擁有的個體數目。群體中擁有的個體數目。f(s) (4) 設第設第t代所有個體代所有個體(不論它屬于何種模式不論它屬于何種模式)的平均適應度是的平均適應度是 , 有等式有等式:f(5) 綜合上

10、述兩式，復制后模式綜合上述兩式，復制后模式s所擁有的個體數目可按下式近似計算：所擁有的個體數目可按下式近似計算：M) j(fM1j f ) t , s (m)1t , s (mff(s) 模式模式s 的這種增減規律，正好符合復制操作的的這種增減規律，正好符合復制操作的“優勝劣汰優勝劣汰”原則，這也說明原則，這也說明模模 式的確能描述編碼字符串的內部特征。式的確能描述編碼字符串的內部特征。f(s)ff(s)f (1) 假設某一模式假設某一模式s 在復制過程中其平均適應度在復制過程中其平均適應度 比群體的平均適應度比群體的平均適應度 高高 出一個定值出一個定值 ，其中，其中c 為常數，則上式改寫為

11、：為常數，則上式改寫為：ff(s) c f ) t , s (m)1t , s (mf c ff += m( s, t ) (1+c ) (2) 從第一代開始，若模式從第一代開始，若模式s 以常數以常數c 繁殖到第繁殖到第 t+1代，其個體數目為：代，其個體數目為： m( s, t+1 ) = m( s, 1 ) (1+c )t 這里以單點交叉算子為例研究。這里以單點交叉算子為例研究。 (1) 有兩個模式有兩個模式 s1: “ * 1 * * * * 0 ” s2: “ * * * 1 0 * * ” 它們有一個共同的可匹配的個體（可與模式匹配的個體稱為模式的表示）它們有一個共同的可匹配的個體

12、（可與模式匹配的個體稱為模式的表示） a: “ 0 1 1 1 0 0 0 ” (2) 選擇個體選擇個體a 進行交叉進行交叉 (3) 隨機選擇交叉點隨機選擇交叉點 s1: “ * 1 * * * * 0 ” 交叉點選在第交叉點選在第 2 6 之間都可能破壞模式之間都可能破壞模式s1; s2: “ * * * 1 0 * * ” 交叉點在交叉點在 第第 4 5之間才破壞之間才破壞s2。 (1) 交換發生在模式交換發生在模式s 的定義長度的定義長度 (s)范圍內，即模式被破壞的概率是：范圍內，即模式被破壞的概率是：例：例： s1 被破壞的概率為：被破壞的概率為：5/6 s2 被破壞的概率為：被破壞

13、的概率為：1/6 1 ) s (pd l (2) 模式不被破壞，存活下來的概率為：模式不被破壞，存活下來的概率為： (3) 若交叉概率為若交叉概率為pc，則模式存活下來的概率為：，則模式存活下來的概率為： (4) 經復制、交叉操作后，模式經復制、交叉操作后，模式s在下一在下一 代群體中所擁有的個體數目為：代群體中所擁有的個體數目為：) s (1p1pds l-1 1) s (p1pcs l-1 1 ),()1,(tsmtsmff(s) ) s (p1cl-1 1 這里以基本位變異算子為例研究。這里以基本位變異算子為例研究。 (1) 變異時個體的每一位發生變化的概率是變異概率變異時個體的每一位發

14、生變化的概率是變異概率pm，也就是說，每一位存，也就是說，每一位存 活的概率是活的概率是(1- pm)。根據模式的階。根據模式的階o(s)，可知模式中有明確含意的字符有，可知模式中有明確含意的字符有o(s) 個，于是模式個，于是模式s 存活的概率是：存活的概率是： )s (oms)p1(p (2) 通常通常 pm1，上式用泰勒級數展開取一次項，可近似表達為：，上式用泰勒級數展開取一次項，可近似表達為： ps 1 pm o(s) 綜合式綜合式、 可以得出遺傳算法經復制、交叉、變異操作后，模式可以得出遺傳算法經復制、交叉、變異操作后，模式s在在 下一代群體中所擁有的個體數目，如下式所示：下一代群體

15、中所擁有的個體數目，如下式所示： 模式定理深刻地闡明了遺傳算法中發生模式定理深刻地闡明了遺傳算法中發生“優勝劣汰優勝劣汰”的原因。在遺傳過程的原因。在遺傳過程中中 能存活的模式都是定義長度短、階次低、平均適應度高于群體平均適應度的能存活的模式都是定義長度短、階次低、平均適應度高于群體平均適應度的 優良模式。遺傳算法正是利用這些優良模式逐步進化到最優解。優良模式。遺傳算法正是利用這些優良模式逐步進化到最優解。 ) t , s (m)1t , s (mff(s) ) s (op) s (p1mcl-1 1 例：例： 求求 max f(x)=x2 x 0,31個個 體體 變變 化化叉叉叉叉S1S2S

16、3叉叉 以以 max f(x)=x2 x 0,31 為例，為例， 圖中：橫坐標表示圖中：橫坐標表示x， 縱坐標代表適應度縱坐標代表適應度f(x)=x2，用千分數表示，用千分數表示， 弧線表示適應度曲線，弧線表示適應度曲線， 網點區代表所有符合此模式的個體集合。網點區代表所有符合此模式的個體集合。 模式模式1：1*模式模式2：10*模式模式3：*1*1 模式定理告訴我們：模式定理告訴我們： 前面我們已經介紹了前面我們已經介紹了GA如何劃分搜索空間和在各個子空間中分配搜索次數，如何劃分搜索空間和在各個子空間中分配搜索次數， 那么那么GA如何利用搜索過程中的積累信息加快搜索速度呢？如何利用搜索過程中

17、的積累信息加快搜索速度呢？ Holland 和和 Goldberg在模式定理的基礎上提出了在模式定理的基礎上提出了“建筑塊假說建筑塊假說”。 短定義長度、低階、高適應度的模式。短定義長度、低階、高適應度的模式。 之所以稱之為建筑塊（積木塊），是由于遺傳算法的求解過程并不是在搜之所以稱之為建筑塊（積木塊），是由于遺傳算法的求解過程并不是在搜 索空間中逐一地測試各個基因的枚舉組合，而是通過一些較好的模式，像索空間中逐一地測試各個基因的枚舉組合，而是通過一些較好的模式，像 搭積木一樣、將它們拼接在一起，從而逐漸地構造出適應度越來越高的個搭積木一樣、將它們拼接在一起，從而逐漸地構造出適應度越來越高的個

18、 體編碼串。體編碼串。 GA在搜索過程中將不同的在搜索過程中將不同的“建筑塊建筑塊”通過遺傳算子（如交叉算子）的通過遺傳算子（如交叉算子）的作作 用結合在一起，形成適應度更高的新模式。這樣將大大縮小用結合在一起，形成適應度更高的新模式。這樣將大大縮小GA的搜索范的搜索范 圍。圍。 建筑塊通過遺傳算子的作用集合在一起的過程稱為建筑塊通過遺傳算子的作用集合在一起的過程稱為“建筑塊混合建筑塊混合”。 當那些構成最優點（或近似最優點）的當那些構成最優點（或近似最優點）的“建筑塊建筑塊”結合在一起時，就得到了最優結合在一起時，就得到了最優點。點。 問題的最優用三個建筑塊問題的最優用三個建筑塊 BB1,

19、BB2, BB3 表示；表示； 群體中有群體中有8個個體。個個體。 初始群體中個體初始群體中個體1，個體，個體2包含建筑塊包含建筑塊BB1 ，個體，個體3包含包含BB3 ,個體個體5包含包含BB2 。P1P2P3P4P5P6P7P8BB1BB2BB1BB3P1P2P3P4P5P6P7P8BB2BB3BB1BB3BB1BB2BB1BB1BB2BB3P1P2P3P4P5P6P7P8BB2BB3BB1BB3BB1BB2BB1BB1BB2BB3BB2BB3初始群體初始群體第二代群體第二代群體第三代群體第三代群體說明：說明：第三代群體中第三代群體中出現了一個包出現了一個包含三個含三個“建筑塊建筑塊”的個

20、體的個體3。個體個體3就代表這就代表這個問題的最優解。個問題的最優解。 隱含并行性（隱含并行性（Implicit Parallelism）是模式理論的另一個重要內容。）是模式理論的另一個重要內容。 這一機理說明，在遺傳算法中盡管每一代只處理這一機理說明，在遺傳算法中盡管每一代只處理M個個體，但實際上卻是處理個個體，但實際上卻是處理 了了M3以上的模式。以上的模式。 設設 ( 0, 1 ) 是一個很小的數，是一個很小的數，模式存活的最小長度模式存活的最小長度 , 群體規模為群體規模為 , 則則GA在一次迭代中所處理的在一次迭代中所處理的“存活率存活率”大于大于 (1- ) 的模的模式式 數約為數

21、約為O(M3) 。其中。其中 表示上取值。表示上取值。 1) 1( lls2/2slM 以二進制編碼為例。在長度為以二進制編碼為例。在長度為l，規模為，規模為M的群體中，包含了的群體中，包含了 2l M2l 個不個不 同的模式，隨著進化過程的進行，這些模式中一些定義長度較長的模式被破同的模式，隨著進化過程的進行，這些模式中一些定義長度較長的模式被破 壞掉，而另一些定義長度較短的模式卻能夠生存下來。壞掉，而另一些定義長度較短的模式卻能夠生存下來。 從模式定理中可以看出，模式在交叉和變異時可能遭破壞。從模式定理中可以看出，模式在交叉和變異時可能遭破壞。 由于變異概率很小，在此只考慮交叉的破壞（此式

22、也可兼顧變異的破壞因素由于變異概率很小，在此只考慮交叉的破壞（此式也可兼顧變異的破壞因素)。 模式被破壞的概率為：模式被破壞的概率為：1 )s(pd l 為保證模式的存活率為保證模式的存活率 , 令令pd ，即：，即： 1)(ls)1()( lssl 根據模式定義長度的定義，模式不被破壞的最小長度根據模式定義長度的定義，模式不被破壞的最小長度 是：是：sl1)( sls 帶入上式得：帶入上式得：1)1( lls 示例示例 假設下述個體編碼字符串的長度假設下述個體編碼字符串的長度 l10， 1 0 1 1 1 0 0 0 1 0 設模式設模式s 的存活長度的存活長度 5。 . 將它放置在個體字符

23、串的最左側，則有：將它放置在個體字符串的最左側，則有： 1 0 1 1 1 0 0 0 1 0 寫成模式的形式，上述字符串變為：寫成模式的形式，上述字符串變為： % % % % 1 % % % % 1 * * * * * * * * * * 方框中方框中% %可在可在 0, 1, * 三者中任取一個。也就是說，可為固定值三者中任取一個。也就是說，可為固定值 ( 0/1 ) 或不固定值或不固定值(*)兩種情況。兩種情況。 方框內的方框內的1表示有一個確定的模式，也可以選方框內的其他固定值表示。表示有一個確定的模式，也可以選方框內的其他固定值表示。 這時，可以組成的模式個數是：這時，可以組成的模式個數是： 2 2 2 = . 將上述方框右移一位將上述方框右移一位 其模式表達為：其模式表達為： 1 0 1 1 1 0 0 0 1 0 * % % % % 0 % % % % 0 * * *