1、第三章模式理論指導(dǎo)遺傳算法的基本理論，是J.H.Holland教授創(chuàng)立的模式理論。該理論揭示了遺傳算法的基本機(jī)理。3.1 基本概念3.1.1 問(wèn)題的引出例：求max f(x)=x2x ?0,311第三章模式理論指導(dǎo)遺傳算法的基本理論，是J.H.Hollan分析? 當(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ì)

2、其他字符不關(guān)心。換句話講我們只關(guān)心字符的某些特定形式，如1*，11*，0*。這種特定的形式就叫模式。3.1.2 模式、模式階及模式定義長(zhǎng)度模式(Schema)指編碼的字符串中具有類似特征的子集。以五位二進(jìn)制字符串為例，模式*111*可代表4個(gè)個(gè)體：01110，01111，11110，11111；模式*0000則代表2個(gè)個(gè)體：10000，00000 。2分析? 當(dāng)編碼的最左邊字符為“1”時(shí)，其個(gè)體適應(yīng)度較大? 個(gè)體是由二值字符集V=0, 1 中的元素所組成的一個(gè)編碼串;? 而模式卻是由三值字符集V=0, 1,* 中的元素所組成的一個(gè)編碼串，其中“*”表示通配符，它既可被當(dāng)作“1” 也可被當(dāng)作“0

3、”。模式階(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)度( SchemaDefining Length)指模式中第一個(gè)和最后一個(gè)具有明確含意的字符之間的距離，記作?(s)。例如，模式( 011*l* ) 的第一個(gè)字符為0，最后一個(gè)字

4、符為l，中間有3個(gè)字符，其定義長(zhǎng)度為4，記作?( 011*l* ) = 4 ；模式( 0* ) 的長(zhǎng)度是0，記作?( 0* ) = 0 ；3? 個(gè)體是由二值字符集V=0, 1 中的元素所組成的一個(gè)? 一般地，有式子?(s)b a式中b模式s 中最后一個(gè)明確字符的位置;a模式s 中最前一個(gè)明確字符的位置。? 模式的長(zhǎng)度代表該模式在今后遺傳操作(交叉、變異)中被破壞的可能性：模式長(zhǎng)度越短，被破壞的可能性越小，長(zhǎng)度為0的模式最難被破壞。3.1.3 編碼字符串的模式數(shù)目(1) 模式總數(shù)?二進(jìn)制字符串假設(shè)字符的長(zhǎng)度為l，字符串中每一個(gè)字符可取( 0, 1, * ) 三個(gè)符號(hào)中任意一個(gè)，可能組成的模式數(shù)目

5、最多為：3 ?3 ?3 ? ?3 = (2+1)l? 一般情況下，假設(shè)字符串長(zhǎng)度為l，字符的取值為k 種，字符串組成的模式數(shù)目n1最多為：n1=(k+1)l4? 一般地，有式子?(s)b a式中b模式s 中最后(2) 編碼字符串（一個(gè)個(gè)體編碼串）所含模式總數(shù)? 二進(jìn)制字符串對(duì)于長(zhǎng)度為l的某二進(jìn)制字符串，它含有的模式總數(shù)最多為：2 ?2 ?2 ? ?2 = 2l注意 這個(gè)數(shù)目是指字符串已確定為0或1，每個(gè)字符只能在已定值(0/1)或* 中選取；前面所述的n1指字符串未確定，每個(gè)字符可在0, 1, * 三者中選取。? 一般情況下長(zhǎng)度為l、取值有k 種的某一字符串，它可能含有的模式數(shù)目最多為：n2

6、= kl(3) 群體所含模式數(shù)在長(zhǎng)度為l，規(guī)模為M的二進(jìn)制編碼字符串群體中，一般包含有2l M 2l個(gè)模式。5(2) 編碼字符串（一個(gè)個(gè)體編碼串）所含模式總數(shù)? 二進(jìn)3.2 模式定理由前面的敘述我們可以知道，在引入模式的概念之后，遺傳算法的實(shí)質(zhì)可看作是對(duì)模式的一種運(yùn)算。對(duì)基本遺傳算法(GA)而言，也就是某一模式s 的各個(gè)樣本經(jīng)過(guò)選擇運(yùn)算、交義運(yùn)算、變異運(yùn)算之后，得到一些新的樣本和新的模式。3.2.1 復(fù)制時(shí)的模式數(shù)目這里以比例選擇算子為例研究。公式推導(dǎo)(1) 假設(shè)在第t次迭代時(shí), 群體P(t)中有M個(gè)個(gè)體, 其中m個(gè)個(gè)體屬于模式s, 記作m(s,t)。(2) 個(gè)體ai 按其適應(yīng)度f(wàn)i 的大小進(jìn)

7、行復(fù)制。從統(tǒng)計(jì)意義講，個(gè)體ai被復(fù)制的概率pi是：pi?fi?Mf(j)j?1(3) 因此復(fù)制后在下一代群體P(t+1)中，群體內(nèi)屬于模式s（或稱與模式s匹配）的個(gè)體數(shù)目m(s,t+1) 可用平均適應(yīng)度按下式近似計(jì)算：f(s)式中f(s)第t代屬于模式s 的所有m(s,t?1)?m(s,t)?M?f(j)j?1M個(gè)體之平均適應(yīng)度；M群體中擁有的個(gè)體數(shù)目。63.2 模式定理由前面的敘述我們可以知道，在引入模式的概念(4) 設(shè)第t代所有個(gè)體(不論它屬于何種模式)的平均適應(yīng)度是f, 有等式:?f?Mf(j)Mj?1(5) 綜合上述兩式，復(fù)制后模式s所擁有的個(gè)體數(shù)目可按下式近似計(jì)算：m(s,t?1)?

8、m(s,t)?結(jié)論f(s)f? 上式說(shuō)明復(fù)制后下一代群體中屬于模式s 的個(gè)體數(shù)目，取決于該模式的平均適應(yīng)度f(wàn)(s)與群體的平均適應(yīng)度f(wàn)之比;? 只有當(dāng)模式s 的平均值f(s)大于群缽的平均值f時(shí)，s模式的個(gè)體數(shù)目才能增長(zhǎng)。否則，s模式的數(shù)目要減小。? 模式s 的這種增減規(guī)律，正好符合復(fù)制操作的“優(yōu)勝劣汰”原則，這也說(shuō)明模式的確能描述編碼字符串的內(nèi)部特征。7(4) 設(shè)第t代所有個(gè)體(不論它屬于何種模式)的平均適應(yīng)度進(jìn)一步推導(dǎo)(1) 假設(shè)某一模式s 在復(fù)制過(guò)程中其平均適應(yīng)度f(wàn)(s)比群體的平均適應(yīng)度f(wàn)高出一個(gè)定值c f，其中c 為常數(shù)，則上式改寫為：+c ffm(s,t?1)?m(s,t)?f=

9、m( s, t ) (1+c )(2) 從第一代開始，若模式s 以常數(shù)c 繁殖到第t+1代，其個(gè)體數(shù)目為：m( s, t+1 ) = m( s, 1 ) (1+c )t結(jié)論從數(shù)學(xué)上講，上式是一個(gè)指數(shù)方程，它說(shuō)明模式s 所擁有的個(gè)體數(shù)目在復(fù)制過(guò)程中以指數(shù)形式增加或減小。8進(jìn)一步推導(dǎo)(1) 假設(shè)某一模式s 在復(fù)制過(guò)程中其平均適3.2.2 交叉時(shí)的模式數(shù)目這里以單點(diǎn)交叉算子為例研究。舉例 (1) 有兩個(gè)模式s1: “ * 1 * * * * 0 ”s2: “ * * * 1 0 * * ”它們有一個(gè)共同的可匹配的個(gè)體（可與模式匹配的個(gè)體稱為模式的表示）a: “ 0 1 1 1 0 0 0 ”(2)

10、選擇個(gè)體a 進(jìn)行交叉(3) 隨機(jī)選擇交叉點(diǎn)s1: “ * 1 * * * * 0 ” 交叉點(diǎn)選在第2 6 之間都可能破壞模式s1;s2: “ * * * 1 0 * * ” 交叉點(diǎn)在第4 5之間才破壞s2。公式推導(dǎo)(1) 交換發(fā)生在模式s 的定義長(zhǎng)度?(s)范圍內(nèi)，即模式被破壞的概率是：?(s)pd? l?1例：s1被破壞的概率為：5/6 s2被破壞的概率為：1/6 93.2.2 交叉時(shí)的模式數(shù)目這里以單點(diǎn)交叉算子為例研究。(2) 模式不被破壞，存活下來(lái)的概率為：ps?1?pd?1?(s)l-1(3) 若交叉概率為pc，則模式存活下來(lái)的概率為：ps?1?pc?(s)l-1(4) 經(jīng)復(fù)制、交叉操

11、作后，模式s在下一代群體中所擁有的個(gè)體數(shù)目為：m(s,t?1)?m(s,t)?f(s)f?(s)?1?pc?l-1?結(jié)論模式的定義長(zhǎng)度對(duì)模式的存亡影響很大，模式的長(zhǎng)度越大，越容易被破壞。10(2) 模式不被破壞，存活下來(lái)的概率為：ps?1?pd?13.2.3 變異時(shí)的模式數(shù)目這里以基本位變異算子為例研究。公式推導(dǎo)(1) 變異時(shí)個(gè)體的每一位發(fā)生變化的概率是變異概率pm，也就是說(shuō)，每一位存活的概率是(1-pm)。根據(jù)模式的階o(s)，可知模式中有明確含意的字符有o(s)個(gè)，于是模式s 存活的概率是：o(s)p?(1?p)sm(2) 通常pm1，上式用泰勒級(jí)數(shù)展開取一次項(xiàng)，可近似表達(dá)為：ps ?1

12、pm o(s)結(jié)論 上式說(shuō)明，模式的階次o(s)越低，模式s 存活的可能性越大，反之亦然。113.2.3 變異時(shí)的模式數(shù)目這里以基本位變異算子為例研究。3.2.4 模式定理綜合式、可以得出遺傳算法經(jīng)復(fù)制、交叉、變異操作后，模式s在下一代群體中所擁有的個(gè)體數(shù)目，如下式所示：m(s,t?1)?m(s,t)?f(s)f?(s)?1?p?p?o(s)c?m?l-1?模式定理適應(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)解。123.2.4 模式定理綜合式、可以得出遺傳算法經(jīng)復(fù)制、3.2.5 模式定理示例例：求max f(x)=x2x ?0,31個(gè)體變化叉叉133.2.5 模式定理示例例：求max f(x)=x2x 叉S1