遺傳算法的模式理論

導(dǎo)遺傳算法的基本理論，是J.H.Holland教授創(chuàng)立的模式理論。該理論揭示
??? 了遺傳算法的基本機理。
?3.1? 基本概念
?3.1.1? 問題的引出
???
?????? 例： 求?? max? f(x)=x2????? x ?{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****。這種特定的形式就叫模式。

?3.1.2? 模式、模式階及模式定義長度
????
???? 模式(Schema)——指編碼的字符串中具有類似特征的子集。
???????????????????????????????????? 以五位二進制字符串為例，
???????????????????????????????????? 模式? *111*?? 可代表4個個體： 01110，01111，11110，11111；
???????????????????????????????????? 模式? *0000? 則代表2個個體：10000，00000? 。

?? 個體是由二值字符集 V={0, 1} 中的元素所組成的一個編碼串;
?????? ?? 而模式卻是由三值字符集? V={0, 1,* } 中的元素所組成的一個編碼串，其中
?????????? “ * ” 表示通配符，它既可被當(dāng)作 “1” 也可被當(dāng)作 “0”。

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

???????? ?? 階次越低，模式的概括性越強，所代表的編碼串個體數(shù)也越多，反之亦然；
???????? ?? 當(dāng)模式階次為零時，它沒有明確含義的字符，其概括性最強。

模式的定義長度( Schema Defining? Length)
??????? ——指模式中第一個和最后一個具有明確含意的字符之間的距離，記作 ?(s)。
??????????????? 例如，模式( 011*l** ) 的第一個字符為0，最后一個字符為l，中間有3個字
??????????????????????????? 符，其定義長度為4，記作 ? ( 011*l** ) = 4 ；
??????????????????????????? 模式 ( 0****** ) 的長度是0，記作 ? ( 0****** ) = 0 ；
?? 一般地，有式子
????????????????????? ?(s)＝b – a
??????????? 式中???? b—模式s 中最后一個明確字符的位置;
???????????????????????? a—模式s 中最前一個明確字符的位置。
?
???? ?? 模式的長度代表該模式在今后遺傳操作(交叉、變異)中被破壞的可能性：
??????? 模式長度越短，被破壞的可能性越小，長度為0的模式最難被破壞。

3.1.3? 編碼字符串的模式數(shù)目
?
?? (1)? 模式總數(shù)
?????? ??? 二進制字符串
???????????? 假設(shè)字符的長度為l，字符串中每一個字符可取( 0, 1, * ) 三個符號中任意
???????? 一個，可能組成的模式數(shù)目最多為：
?????????????????????????? 3 ? 3 ? 3 ? … ? 3 = (2+1)l
?????? ? 一般情況下，
???????????? 假設(shè)字符串長度為l，字符的取值為 k 種，字符串組成的模式數(shù)目 n1 最多???
????????? 為：???????? n1=(k+1)l
(2)? 編碼字符串（一個個體編碼串）所含模式總數(shù)
???? ?? 二進制字符串
?????????? 對于長度為l的某二進制字符串，它含有的模式總數(shù)最多為：
?????????????????? 2 ? 2 ? 2 ? … ? 2 = 2l
?????????? [注意]
???????????????? 這個數(shù)目是指字符串已確定為0或1，每個字符只能在已定值 (0/1)或
????????????????? * 中選??；
????????????????? 前面所述的 n1 指字符串未確定，每個字符可在{0, 1, * }三者中選取。
???
???? ?? 一般情況下
?????????? 長度為l、取值有 k 種的某一字符串，它可能含有的模式數(shù)目最多為：
????????????????????????? n2 = kl

?(3)? 群體所含模式數(shù)
??????????? 在長度為l，規(guī)模為M的二進制編碼字符串群體中，一般包含有2l ~ M · 2l個
???????? 模式。
3.2? 模式定理??????

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

3.2.1? 復(fù)制時的模式數(shù)目
?????????? 這里以比例選擇算子為例研究。
???
??? [公式推導(dǎo)]
?????? (1) 假設(shè)在第t次迭代時, 群體P(t)中有M個個體, 其中m個個體屬于模式s, 記作m(s,t)。

?????? (2) 個體 ai 按其適應(yīng)度 fi 的大小進行復(fù)制。
??????????? 從統(tǒng)計意義講，個體ai被復(fù)制的概率pi是：
(3)? 因此復(fù)制后在下一代群體 P(t+1)中，群體內(nèi)屬于模式s（或稱與模式s匹配）
????? 的個體數(shù)目 m(s,t+1) 可用平均適應(yīng)度按下式近似計算：