【正文】 為： 模式的適應(yīng)值與群體平均適應(yīng)值的比例為： 這就意味著如果模式保持在平均之上，那么它將在下一代中保持串?dāng)?shù)的幾何增長(zhǎng)。特別地，在時(shí)刻，預(yù)計(jì)可以得到3*= （可能有4個(gè)或5個(gè)）被模式匹配；在時(shí)刻，有3*= ，即可能有6個(gè)串，等等。根據(jù)直覺(jué)，的模式定義了搜索空間中極有希望的一部分，并且它以幾何增長(zhǎng)的方式被復(fù)制?？梢杂靡郧暗膶?shí)例檢驗(yàn)對(duì)的預(yù)測(cè)。在時(shí)刻，新的群體見(jiàn)P5下方的?？梢?jiàn)，模式在時(shí)刻匹配5個(gè)串：、和。 然而，選擇本身不能產(chǎn)生新的潛在解，只能從中間群體中復(fù)制一些串。所以在進(jìn)化周期的第二步（重組）中向群體中引入了新個(gè)體。這是通過(guò)雜交和變異兩個(gè)算子完成的。以下依次討論兩個(gè)算子作用于群體中模式的效果。2． 雜交：考慮下面的例子：如在前面討論的，群體中一個(gè)單獨(dú)個(gè)體的串，設(shè)為：被233種模式匹配；該串同時(shí)被下面兩個(gè)模式匹配： 進(jìn)一步假定上述串被選擇用來(lái)雜交。根據(jù)上一節(jié)的例子（個(gè)體和被選擇進(jìn)行雜交），假定雜交位置為。很明顯，模式生存下來(lái)，即有一個(gè)后代仍然匹配。因?yàn)殡s交在一個(gè)后代串上保存了第5，6，7位上的序列“111”。雜交前 雜交后 另一方面，模式遭破壞：子代不與它匹配。因?yàn)樵谀０彘_(kāi)始的固定位“111”和結(jié)尾的固定位“10”分布在不同的子代上。 很明顯，模式的定義長(zhǎng)度對(duì)其生存和損壞的概率起著很重要的作用。注意模式的定義長(zhǎng)度為，而模式的定義長(zhǎng)度為。 通常，雜交位是在中可能的位置上被唯一地選擇的。這就意味著模式的最大消亡概率為 因此，該模式的最小存活概率為實(shí)際上，我們的例子中的模式和的存活概率和消亡概率分別為：， ， 所以結(jié)果是可以預(yù)測(cè)的。注意實(shí)際上只有一些染色體經(jīng)歷雜交，并且雜交的選擇性概率為。這說(shuō)明一個(gè)模式的最小存活概率實(shí)際上為：再一次參考前面例子中的模式()： 注意，盡管雜交位置是在一個(gè)模式的固定位置之間選擇的，該模式仍然有機(jī)會(huì)存活。例如，如果串和都是以“111”開(kāi)始，“10”結(jié)尾，模式將雜交存活，當(dāng)然，這種可能性非常小。因此，模式的存活概率為 所以，選擇和雜交的結(jié)合給出了一個(gè)新的形式的復(fù)制模式生長(zhǎng)公式： (2)公式(2)告訴我們?cè)谙乱淮衅ヅ淠Ｊ降念A(yù)測(cè)串?dāng)?shù)是實(shí)際匹配模式串?dāng)?shù)、模式的相對(duì)適應(yīng)值及模式的定義長(zhǎng)度的函數(shù)。顯然，在平均之上，短的定義長(zhǎng)度的模式將按照幾何增長(zhǎng)的速率被復(fù)制。對(duì)模式：這說(shuō)明短的、平均值之上的模式將在下一代中出現(xiàn)幾何增長(zhǎng)的串?dāng)?shù)：在時(shí)刻，預(yù)測(cè)有3*= ；在時(shí)刻，將有3*= 。3． 變異：變異算子以概率隨機(jī)地改變一個(gè)染色體中的某一位。其變化為從0到1或者相反。很明顯，如果模式經(jīng)過(guò)變異還存活，該模式上的所有固定位應(yīng)保持不變。再一次考慮群體中的一個(gè)串，設(shè)為： ()和模式。進(jìn)一步假定串經(jīng)歷變異，即至少有一位發(fā)生變異。根據(jù)前一節(jié)的結(jié)果，在第9位變異，其子代為仍然被模式匹配。如果被選擇變異的位置是從1到4，或者8到33，那么所生成的子代仍然被模式匹配。這里只有3位（第5，6和7位，即模式的固定位）是很重要的：變異其中之一將破壞模式。很明顯，這些重要位的數(shù)目等于模式的階，即固定位的數(shù)目。 因?yàn)閱蝹€(gè)位變異的概率為，所以單個(gè)位存活的概率為。單個(gè)變異是和其它變異相互獨(dú)立的，所以模式經(jīng)過(guò)單點(diǎn)變異后的存活概率為由于，所以此概率可以被近似為再一次參考例子中的模式(): 選擇、雜交和變異的組合給出了復(fù)制生長(zhǎng)公式的新形式： (3) 正如簡(jiǎn)單公式(1)和(2)，公式(3)告訴我們?cè)谙乱淮?，預(yù)測(cè)匹配模式的串?dāng)?shù)是匹配模式的實(shí)際串?dāng)?shù)、模式的相對(duì)適應(yīng)值和定義長(zhǎng)度以及階的函數(shù)。很明顯，在平均值之上的、短的定義長(zhǎng)度和低階的模式將按照幾何增長(zhǎng)的速率被復(fù)制。 對(duì)模式：這就意味著短的、低階、平均之上的模式將在下一代中產(chǎn)生幾何增長(zhǎng)的串?dāng)?shù)：在時(shí)刻預(yù)計(jì)有3*=（——只考慮選擇的結(jié)果，——值考慮選擇和雜交的結(jié)果），在時(shí)刻，有3*=（）。 注意，公式()是基于適應(yīng)值函數(shù)返回正值的假定：當(dāng)用遺傳算法優(yōu)化可能返回負(fù)值的優(yōu)化函數(shù)時(shí)，需要附加一些適應(yīng)值函數(shù)和優(yōu)化函數(shù)之間的映射。 概括起來(lái)，生長(zhǎng)公式(1)顯示：選擇增加了平均之上的模式的復(fù)制率，并且這種變化是指數(shù)型的。復(fù)制本身并不能增加新的模式（初始時(shí)刻的復(fù)制除外）。這就是為什么要引入雜交算子的原因——能以結(jié)構(gòu)化的方式隨機(jī)地交換信息。另外，變異算子向群體引入了較大的變化性。如果一個(gè)模式是短的且低階的，這些算子作用在該模式上的組合分裂效果是不大的。生長(zhǎng)公式(3)的最終結(jié)果可以用下面的定理和假設(shè)表示：定理1 模式定理(Schema Theorem)： 短的、低階、平均之上的模式在遺傳算子的后續(xù)代中將按幾何級(jí)數(shù)增長(zhǎng)。這一定理的直接結(jié)果是：遺傳算法通過(guò)短的、低階模式的雜交信息交換過(guò)程探求了搜索空間。假設(shè)1 基因塊假設(shè)(Building Block Hypothesis)： 遺傳算法是通過(guò)并列短的、低階、高效模式（稱之為基因塊）來(lái)尋求接近最優(yōu)的執(zhí)行效果。雖然已有一些研究來(lái)證明此假設(shè)，但是多數(shù)重要的應(yīng)用還是依賴于實(shí)驗(yàn)結(jié)果。遺傳算法在眾多問(wèn)題領(lǐng)域中的應(yīng)用支持基因塊假設(shè)。毫無(wú)疑問(wèn)，基因塊假設(shè)說(shuō)明遺傳算法的編碼問(wèn)題對(duì)其執(zhí)行效果來(lái)說(shuō)是至關(guān)重要的，并且這種編碼應(yīng)該符合短基因塊的思想。四、遺傳算法實(shí)現(xiàn)中的若干問(wèn)題和討論：前面已給出了遺傳算法運(yùn)行步驟的一般描述，通過(guò)一個(gè)實(shí)例具體地考察了它的運(yùn)行步驟，并給出了遺傳算法的理論基礎(chǔ)。在具體實(shí)現(xiàn)過(guò)程中，仍有一些問(wèn)題值得重視：1． 選擇策略：選擇策略是指復(fù)制算子按照什么方式進(jìn)行操作?？偟脑瓌t是讓適者生存，即適應(yīng)值大的串生存概率要大。常用的選擇方法有以下幾種：(1). 確定性選擇方法：對(duì)群體中每個(gè)串計(jì)算生存概率（其中為總適應(yīng)值），從而得到的期望拷貝數(shù)。按的整數(shù)部分值，分配給該串一個(gè)拷貝數(shù)。顯然，總的拷貝數(shù)小于。剩余部分的填充方法是：把每個(gè)串對(duì)應(yīng)的的小數(shù)部分進(jìn)行排隊(duì)，按從大到小的順序選擇對(duì)應(yīng)的串，直到填滿。(2). 賭盤(pán)選擇方法：即前面采用的方法，此處不在贅述。由于賭盤(pán)選擇不能保證把最好的個(gè)體保留下來(lái)，因此又提出最優(yōu)選擇：設(shè)是直到第代最好的個(gè)體，按賭盤(pán)產(chǎn)生后，若不在中，則把加入中，并隨機(jī)舍棄一個(gè)個(gè)體。(3). 有退還和無(wú)退還剩余隨機(jī)選擇：首先計(jì)算期望拷貝數(shù)，整數(shù)部分決定拷貝數(shù)。對(duì)余下的小數(shù)部分：a. 有退還剩余隨機(jī)選擇：把的小數(shù)部分作為賭盤(pán)選擇的權(quán)，利用賭盤(pán)選擇決定取舍；b. 無(wú)退還剩余隨機(jī)選擇：把的小數(shù)部分視為概率，一個(gè)一個(gè)地進(jìn)行貝努利試驗(yàn)，其中小數(shù)部分作為成功概率。2． 控制參數(shù)的選擇：在使用遺傳算法時(shí)，首先要給定一組控制參數(shù)，如群體規(guī)模，雜交率和變異率等，控制參數(shù)的不同選擇會(huì)對(duì)遺傳算法的性能產(chǎn)生很大的影響，要想發(fā)掘執(zhí)行的最優(yōu)性能，必須確定最優(yōu)的參數(shù)設(shè)置。事實(shí)上，參數(shù)設(shè)置本身也是個(gè)優(yōu)化問(wèn)題。這里僅討論一些原則。遺傳算法的參數(shù)空間包括：群體規(guī)模、雜交率、變異率、代間隙、選擇策略和適應(yīng)值變換等?！?群體規(guī)模：它影響到遺傳算法的最終性能和效率。規(guī)模太小，群體中所含的模式太少，對(duì)基因塊采樣增長(zhǎng)速率小，且代表性差，最終解的質(zhì)量不高；規(guī)模大的群體包含大量有廣泛代表性的基因塊，可以阻止算法過(guò)早地收斂到局部最優(yōu)解。然而群體規(guī)模越大，每一代所需要的計(jì)算量就越大，這會(huì)導(dǎo)致收斂過(guò)程太慢；● 雜交率：雜交率控制雜交算子的應(yīng)用頻率。雜交率越高，群體中的串的更新就越快，算法對(duì)解空間的搜索能力越強(qiáng)。若雜交率過(guò)高，高性能的串被破壞的速度也加快了；若雜交率過(guò)低，算法搜索解空間的能力下降，有蛻變成局部隨機(jī)搜索算法的危險(xiǎn)。● 變異率：變異是增加群體多樣性的搜索算法。一個(gè)低水平的變異率足以防止整個(gè)群體中任一給定位保持永遠(yuǎn)收斂于單一的值；高水平的變異率產(chǎn)生的實(shí)際上是隨機(jī)搜索。● 代間隙：它被引入算法中是允許出現(xiàn)群體重疊的情形，定義在0到1之間，控制每一代群體被替換的百分率。時(shí)，表示全部替換；時(shí)，表示部分替換。中有個(gè)個(gè)體被隨機(jī)地保留到下一代中?！?選擇策略：前面已經(jīng)討論過(guò)，用的較多的是賭盤(pán)選擇?！?適應(yīng)值變換：目的時(shí)提高算法對(duì)適應(yīng)值變化的敏感度。因?yàn)檫m應(yīng)值是算法唯一利用的信息，對(duì)適應(yīng)值變化是否敏感是很重要的。3． 適應(yīng)值變換：注意到賭盤(pán)選擇要求適應(yīng)值是正的，而目標(biāo)函數(shù)不一定為正，因此需要對(duì)目標(biāo)函數(shù)做變換，即：其中選取一個(gè)適當(dāng)大的數(shù)。 進(jìn)行適應(yīng)值比例變換的目的是調(diào)節(jié)遺傳算法執(zhí)行過(guò)程中串的復(fù)制數(shù)目，以提高算法的性能。通俗地講就是希望放大串的適應(yīng)值的間隔，不因適應(yīng)值非常接近而無(wú)法選擇適應(yīng)值更好的串。另外，還可壓制某些適應(yīng)值非常大的串控制選擇過(guò)程。(1) 線性變換設(shè)原適應(yīng)函數(shù)為，比例適應(yīng)函數(shù)為，則 稱為線性比例變換。系數(shù)和的選擇必須滿足以下兩個(gè)條件：1. 平均比例適應(yīng)值等于原平均適應(yīng)值；2. 最大的比例適應(yīng)值是平均適應(yīng)值的指定倍數(shù)，即，一般取2，這兩個(gè)條件保證平均群體個(gè)體最好的個(gè)體的期望復(fù)制數(shù)分別為1和。(2) 冪比例變換冪比例變換是比例適應(yīng)值取為原適應(yīng)值的某個(gè)指定冪： ，值一般是依賴于具體問(wèn)題的，在算法執(zhí)行中需要變化以滿足要求的伸縮范圍，即是代的函數(shù)。(3) 指數(shù)比例變換指數(shù)比例滿足關(guān)系式：。指數(shù)比例既可讓非常好的串保持較多的復(fù)制機(jī)會(huì)，同時(shí)又限制了其復(fù)制數(shù)目，以免很快控制整個(gè)群體。同時(shí)對(duì)于適應(yīng)值相近的串也提高了競(jìng)爭(zhēng)性。參數(shù)的值決定了選擇的側(cè)重，越小，選擇強(qiáng)制越趨向于那些具有最高適應(yīng)值的串，值隨著代的演化而增大。4． 遺傳算法的困難：(1). “編碼困難”：“表達(dá)是遺傳算法的主要問(wèn)題。因?yàn)楸磉_(dá)方案嚴(yán)重地限制了系統(tǒng)觀察世界的窗口?！?Koza, 1990)“在我看來(lái)有時(shí)確實(shí)如此，我們不能用二進(jìn)制表達(dá)和只由二進(jìn)制雜交和二進(jìn)制變異組成的算子集來(lái)處理多數(shù)真實(shí)世界的問(wèn)題?！?Davis, 1989)遺傳算法傳統(tǒng)上使用的二進(jìn)制編碼當(dāng)用于多維、高精度數(shù)值問(wèn)題時(shí)會(huì)有一些障礙。例如，對(duì)于一個(gè)有100個(gè)變量、域區(qū)間[500, 500]、精度要求精確到小數(shù)點(diǎn)后第6位的問(wèn)題，二進(jìn)制解向量的長(zhǎng)度是3000。這本身會(huì)產(chǎn)生一個(gè)大約是101000的搜索空間。對(duì)這樣的問(wèn)題，遺傳算法執(zhí)行得很不好。編碼應(yīng)該具有這樣的性質(zhì)：在表達(dá)空間里相互靠近的兩個(gè)點(diǎn)也必須在問(wèn)題空間里靠近，反之亦然。而二進(jìn)制方法并不總是這樣。一個(gè)可能的解決途徑是采用浮點(diǎn)編碼，目的是使遺傳算法更接近問(wèn)題空間。通過(guò)利用真實(shí)空間的一些特征，這樣的移近強(qiáng)制算子更與問(wèn)題的特殊性有關(guān)。(2). “有限困難”：遺傳算法理論解釋了為什么對(duì)一個(gè)給定的問(wèn)題表達(dá)，能收斂到欲求的最優(yōu)點(diǎn)。但不幸的是，實(shí)際的應(yīng)用并不總遵循這一理論。主要的原因除了上面的“編碼困難”之外，還有“有限困難”，即：理論假定迭代次數(shù)是無(wú)限的，而實(shí)際上有限制；理論上也假定群體規(guī)模是無(wú)限的，實(shí)際上也有限制。這說(shuō)明遺傳算法在某種條件下不能找到最優(yōu)解：這種失敗是由于過(guò)早地收斂到局部最優(yōu)造成的。過(guò)早收斂問(wèn)題是所有優(yōu)化算法共同的問(wèn)題。如果收斂發(fā)生的太快，包含在群體中的有價(jià)值的信息常常會(huì)失去。而遺傳算法的執(zhí)行趨向于在找到最優(yōu)解之前過(guò)早地收斂。有一些避免過(guò)早收斂的策略，比如：(1) 配對(duì)策略(mating strategy)，又稱為近親預(yù)防(incest prevention)； (2) 使用均勻雜交(uniform crossover)；(3). 檢測(cè)群體中的重復(fù)串。參考文獻(xiàn)：Michalewicz, Z. (2000). 演化程序——遺傳算法和數(shù)據(jù)編碼的結(jié)合 (中譯本). 科學(xué)出版社.楊文采 (1997). 地球物理反演的理論與方法. 地質(zhì)出版社.１７０