1、精選優(yōu)質(zhì)文檔-傾情為你奉上第3章 遺傳算法的數(shù)學(xué)基礎(chǔ) 遺傳算法在機(jī)理方面具有搜索過(guò)程和優(yōu)化機(jī)制等屬性，數(shù)學(xué)方面的性質(zhì)可通過(guò)模式定理和構(gòu)造塊假設(shè)等分析加以討論，Markov鏈也是分析遺傳算法的一個(gè)有效工具。遺傳算法的選擇操作是在個(gè)體適應(yīng)度基礎(chǔ)上以概率方式進(jìn)行的，在概率選擇方式上與模擬退火法有些類(lèi)似。 本章將較全局地介紹遺傳算法的基礎(chǔ)數(shù)學(xué)理論和分析工具，包括驗(yàn)證基礎(chǔ)遺傳算法（SGA）的有效性的模式定理，分析遺傳算法過(guò)程的Walsh模式變換方法，遺傳算法的欺騙問(wèn)題以及遺傳算法的動(dòng)態(tài)分析工具M(jìn)arkov鏈分析。3.1 模式定理1. 模式我們將種群中的個(gè)體即基因串中的相似樣板稱(chēng)為“模式”，模式表示基因串

2、中某些特征位相同的結(jié)構(gòu)，因此模式也可能解釋為相同的構(gòu)形，是一個(gè)串的子集。在二進(jìn)制編碼中，模式是基于三個(gè)字符集0，1，*的字符串，符號(hào)* 代表0或1。例1 *1*表示四個(gè)元的子集010 011 110 111對(duì)于二進(jìn)制編碼串，當(dāng)串長(zhǎng)為L(zhǎng)時(shí)，共有3L個(gè)不同的模式。例2 串長(zhǎng)L=3，則其模式共有* *1* *0* *1 *0 1* 0* *10 *00 *01 1*1 1*0 0*1 0*0 11* 10* 01* 00* 111 110 101 011 001 010 100 000 共27個(gè)1+2*3+22*3+23=33遺傳算法中串的運(yùn)算實(shí)際上是模式的運(yùn)算。如果各個(gè)串的每一位按等概率生成0或1

3、，則模式為n的種群模式種類(lèi)總數(shù)的期望值為：種群最多可以同時(shí)處理個(gè)模式，見(jiàn)下例例 一個(gè)個(gè)體（種群中只有一個(gè)），父?jìng)€(gè)體011 要通過(guò)變異變?yōu)樽觽€(gè)體001，其可能影響的模式為：被處理的模式總數(shù)為8個(gè)，8=1*23如果獨(dú)立的考慮種群中的各個(gè)串，則僅能得到n條信息，然而當(dāng)把適應(yīng)值與各個(gè)串結(jié)合考慮，發(fā)掘串群體的相似點(diǎn)，就可得到大量的信息來(lái)幫助指導(dǎo)搜索，相似點(diǎn)的大量信息包含在規(guī)模不大的種群中。2. 模式階和定義距 定義1：模式階 模式H中確定位置的個(gè)數(shù)成為模式H的模式階，記作O(H) 例 O(011*1*0)=5定義2 定義階 模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，記作 例 3. 模式定理 假定

4、在給定時(shí)間步t(即第t代)，種群A(t)中有m個(gè)個(gè)體屬于模式H，記為m=m(H,t),即第t代時(shí)，有m個(gè)個(gè)體屬于H模式。在再生階段（即種群個(gè)體的選擇階段），每個(gè)串根據(jù)它的適應(yīng)值進(jìn)行復(fù)制（選擇），一個(gè)串Ai被復(fù)制（選中）的概率為：n表示種群中個(gè)體總數(shù)當(dāng)采用非重疊的n個(gè)串的種群替代種群A(t),可以得到下式：其中：，表示在t 時(shí)模式H的平均適應(yīng)度若用表示種群平均適應(yīng)度，則前式可表示為：上式表明：一個(gè)特定的模式按照其平均適應(yīng)度值與種群的平均適應(yīng)度值之間的比率生長(zhǎng)，換句話說(shuō)就是：那些適應(yīng)度值高于種群平均適應(yīng)度值的模式，在下一代中將會(huì)有更多的代表串處于A(t+1)中，因?yàn)樵跁r(shí)有m(H,t+1)>m

5、(H,t) 假設(shè)從t=0開(kāi)始，某一特定模式適應(yīng)度值保持在種群平均適應(yīng)度值以上，c為常數(shù)c>0, 則模式選擇生長(zhǎng)方程為：上式表明，在種群平均值以上（以下）的模式將按指數(shù)增長(zhǎng)（衰減）的方式被復(fù)制。下面討論交叉對(duì)模式H的影響：例：對(duì)串A分別在下面指定點(diǎn)上與H1模式和H2模式進(jìn)行交叉 A H1 *1*0 (被破壞概率：；生存率：1/6) H2 *10* (被破壞概率：；生存率：5/6)顯然A與H1交叉后， H1被破壞，而與H2交叉時(shí)， H2不被破壞。一般地有 ：模式H被破壞的概率為，故交叉后模式H生存的概率為（）考慮到交叉本身是以隨機(jī)方式進(jìn)行的，即以概率Pc進(jìn)行交叉，故對(duì)于模式H的生存概率Pc可

6、用下式表示：同時(shí)考慮選擇交叉操作對(duì)模式的影響，（選擇交叉互相獨(dú)立不影響）則子代模式的估計(jì)：上式表明模式增長(zhǎng)和衰減依賴(lài)于兩個(gè)因素：一是模式的適應(yīng)度值f(H)與平均適應(yīng)度值的相對(duì)大小；另一個(gè)是模式定義階的大小（當(dāng)Pc一定， L一定時(shí)）。下面再考察變異操作對(duì)模式的影響：變異操作是以概率Pm隨機(jī)地改變一個(gè)位上的值，為了使得模式H可以生存下來(lái)，所有特定的位必須存活。因?yàn)閱蝹€(gè)等位基因存活的概率為（1Pm）,并且由于每次變異都是統(tǒng)計(jì)獨(dú)立的，因此，當(dāng)模式H中O(H)個(gè)確定位都存活時(shí)，這時(shí)模式H才能被保留下來(lái)，存活概率為：（為0.01以下）上式表明O(H)個(gè)定位值沒(méi)有被變異的概率。由此我們可得到下式在t+1代種

7、群中存在模式H的個(gè)體數(shù)目在t代種群中存在模式H的個(gè)體數(shù)目在t代種群中包含模式H的個(gè)體平均適應(yīng)度t代種群中所有個(gè)體的平均適應(yīng)度個(gè)體長(zhǎng)度交叉概率變異概率對(duì)于k點(diǎn)交叉時(shí)，上式可表示為：模式定理：在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng)。4. 積木塊假設(shè)（building block hypochesis） 遺傳算法通過(guò)短定義距、低階以及高適應(yīng)度的模式（積木塊），在遺傳操作作用下相互結(jié)合，最終接近全局最優(yōu)解。滿足這個(gè)假設(shè)的條件有兩個(gè)：（1）表現(xiàn)型相近的個(gè)體基因型類(lèi)似（2）遺傳因子間相關(guān)性較低積木塊假設(shè)指出，遺傳算法具備尋找全局最優(yōu)解

8、的能力，即積木塊在遺傳算子作用下，能生成低階、短距、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。模式定理還存在以下缺點(diǎn)：（1） 模式定理只對(duì)二進(jìn)制編碼適用（2） 模式定理只是指出具備什么條件的木塊會(huì)在遺傳過(guò)程中按指數(shù)增長(zhǎng)或衰減，無(wú)法據(jù)此推斷算法的收斂性（3） 沒(méi)有解決算法設(shè)計(jì)中控制參數(shù)選取問(wèn)題3.2 Walsh模式變換1980年，密歇根大學(xué)的A.D.Bethke博士論文“作為函數(shù)優(yōu)化器的遺傳算法”，首次應(yīng)用Walsh函數(shù)進(jìn)行遺傳算法的模式處理，采用Walsh函數(shù)的離散形式有效地計(jì)算模式的平均適應(yīng)度，從而對(duì)遺傳算法的優(yōu)化過(guò)程的特征進(jìn)行分析。3.3 非均勻Walsh模式變換3.4 欺騙問(wèn)題在遺傳算法中

9、，將所有妨礙評(píng)價(jià)值高的個(gè)體生成，從而影響遺傳算法正常工作的問(wèn)題統(tǒng)稱(chēng)為欺騙問(wèn)題（deceptive problem）,根據(jù)模式定理，如果低階、高適應(yīng)度模式中包含了最優(yōu)解的話，遺傳算法就可能找出它來(lái)，但是如果低階、高適應(yīng)度模式中未包含最優(yōu)串的具體取值，則遺傳算法只能找出次優(yōu)解。定義 競(jìng)爭(zhēng)模式 若模式H和H中，*位置是完全一致的，但任一確定位的編碼均不同，則稱(chēng)H和H互為競(jìng)爭(zhēng)模式。例 10*與01*是競(jìng)爭(zhēng)模式 10*與11*不是競(jìng)爭(zhēng)模式定義 欺騙性 假定f(x)的最大值對(duì)應(yīng)的x集合為x*，H為包含x*的m階模式， H的競(jìng)爭(zhēng)模式為H，而且f(H)<f(H),則f為m階欺騙。例 對(duì)于一個(gè)三位二進(jìn)制編

10、碼的模式，如果f(111)為最大值，下列12個(gè)不等式中任意一個(gè)不等式成立，則存在欺騙問(wèn)題。 模式階數(shù)為1時(shí)：f(*1)<f(*0),f(*1*)<f(*0*),f(1*)<f(0*) 模式階數(shù)為2時(shí)：f(*11)<f(*00),f(1*1)<f(0*0),f(11*)<f(00*) f(*11)<f(*01),f(1*1)<f(0*1),f(11*)<f(01*) f(*11)<f(*10),f(1*1)<f(1*0),f(11*)<f(10*)造成上述欺騙問(wèn)題的主要原因有兩個(gè)：編碼不當(dāng)或適應(yīng)度函數(shù)選擇不當(dāng)。如果它們均是單

11、調(diào)關(guān)系，則不會(huì)存在欺騙性問(wèn)題，但是對(duì)于一個(gè)非線性問(wèn)題，難于實(shí)現(xiàn)其單調(diào)性。1. 欺騙函數(shù)的類(lèi)型Goldberg曾研究用適應(yīng)度函數(shù)的非單調(diào)性來(lái)研究欺騙性問(wèn)題。考慮一個(gè)2位二進(jìn)制最大化問(wèn)題，假定“11”對(duì)應(yīng)最優(yōu)解，若H(0*)>H(1*)，則欺騙性存在。該條件可化為：下面以前一種為例進(jìn)行討論，設(shè)則有：r<1+c-cc>1：稱(chēng)為類(lèi)欺騙問(wèn)題，見(jiàn)圖1，求最優(yōu)化時(shí)較難c<=1:稱(chēng)為類(lèi)欺騙問(wèn)題，見(jiàn)圖2，此問(wèn)題求最優(yōu)化更難圖1圖2這兩類(lèi)欺騙性問(wèn)題應(yīng)該稱(chēng)為非單調(diào)問(wèn)題，在非單調(diào)問(wèn)題中同時(shí)存在欺騙性和非欺騙性問(wèn)題。過(guò)去，將適應(yīng)度函數(shù)的非單調(diào)問(wèn)題與欺騙問(wèn)題同等看待，認(rèn)為遺傳算法只有在單調(diào)問(wèn)題里有

12、效。但是，如果單調(diào)問(wèn)題不使用遺傳算法或者不使用概率搜索，一般的搜索法可能是適用的，沒(méi)有遺傳算法存在的必要。即使是單調(diào)的，只有存在需要高機(jī)能交叉操作（非單調(diào)且非欺騙問(wèn)題），才能使遺傳算法存在有意義，這不外乎使交叉操作成為遺傳算法本質(zhì)作用的一個(gè)證明。2. 欺騙性化解可以采用Grey 編碼或糾正適應(yīng)度函數(shù)3. 遺傳算法的困難問(wèn)題容易問(wèn)題：采用基本的遺傳算法，易于得到最優(yōu)解的場(chǎng)合或問(wèn)題困難問(wèn)題;與上相反遺傳算法的欺騙性與遺傳算法的困難性不存在對(duì)等或等價(jià)關(guān)系，這是由于遺傳算法的欺騙性是從靜態(tài)超平面分析給出的，并且假設(shè)個(gè)體數(shù)無(wú)偏差，而遺傳算法的困難性來(lái)源于不適當(dāng)?shù)膯?wèn)題表示、交叉和變異的擾動(dòng)作用、有限的種群

13、大小、復(fù)雜的多模型狀態(tài)圖等。3.5 遺傳算法動(dòng)態(tài)分析從隨機(jī)過(guò)程和數(shù)理統(tǒng)計(jì)角度討論遺傳算法較為一般的規(guī)律，有助于較好地把握遺傳算法的特性，以提高求解效率和改善求解效果。鈴木（1995年）從Markov鏈的角度分析了基本遺傳算法（SGA）的統(tǒng)計(jì)規(guī)律，并得到了一些有意義的結(jié)論。SGA的當(dāng)前種群只與前一代種群有關(guān)，因此SGA可以用一個(gè)Markov鏈來(lái)描述。第四章 遺傳算法的改進(jìn)自從1975年J.H.Holland系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來(lái)，總多學(xué)者一直致力于推動(dòng)遺傳算法的發(fā)展，對(duì)編碼方式、控制參數(shù)的確定、選擇方式和交叉機(jī)理等進(jìn)行了深入的探究，引入了動(dòng)態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能，

14、提出了各種變形的遺傳算法（Variants of Canonical Genetic Algorithm,簡(jiǎn)稱(chēng)VCGA）.其基本途徑概括起來(lái)有以下幾個(gè)方面：（1） 改變遺傳算法的組成成分或使用技術(shù)，如選用優(yōu)化控制參數(shù)、適合問(wèn)題特性的編碼技術(shù)等。（2） 采用混合遺傳算法（3） 采用動(dòng)態(tài)自適應(yīng)技術(shù)，在進(jìn)化過(guò)程中調(diào)整算法控制參數(shù)和編碼力度（4） 采用非標(biāo)準(zhǔn)的遺傳操作算子（5） 采用并行遺傳算法本章將介紹這些方面的典型思路和集中改進(jìn)的遺傳算法。4.1 分層遺傳算法對(duì)于一個(gè)問(wèn)題，首先隨機(jī)生成N*n各樣本(n>=2,N>=2),然后將它們分成N個(gè)子種群，每個(gè)子種群包括n各樣本，對(duì)每個(gè)子種群獨(dú)立

15、的運(yùn)行各自的遺傳算法，記它們?yōu)镚Ai(i=1,2,.N)。這N個(gè)遺傳算法最好在設(shè)置特性上有較大差異，這樣就可以為將來(lái)的高層遺傳算法產(chǎn)生更多種類(lèi)的優(yōu)良模式。在每個(gè)子種群的遺傳算法運(yùn)行到一定代數(shù)后，將N個(gè)遺傳算法的結(jié)果種群記錄到二維數(shù)組R1.N,1n中，則Ri,j（i=1N,j=1n）表示GAi的結(jié)果種群的第j個(gè)個(gè)體。同時(shí)將N各結(jié)果種群的平均適應(yīng)度值記錄到數(shù)組A1.N中，Ai表示GAi的結(jié)果種群平均適應(yīng)度。高層遺傳算法與普通遺傳算法的操作相類(lèi)似，也可以分為以下三個(gè)步驟：1.選擇（種群之內(nèi)選擇）基于數(shù)組A1.N，即N個(gè)遺傳算法的平均適應(yīng)度值，對(duì)數(shù)組R代表結(jié)果種群進(jìn)行選擇操作，一些結(jié)果種群由于它們的平

16、均適應(yīng)度值高而被復(fù)制，甚至復(fù)制多次；另一些結(jié)果種群由于它們的種群平均適應(yīng)度值低而被淘汰。2. 交叉（種群之間交叉）如果Ri,1.n和Rj,1.n被隨機(jī)地匹配到一起，而且從位置x進(jìn)行交叉（）則Ri,x+1.n和Rj,x+1.n相互交換相應(yīng)的部分。這一步驟相當(dāng)于交換GAi和GAj中結(jié)果種群的n-x個(gè)個(gè)體。3.變異以很小的概率將少量隨機(jī)生成的新個(gè)體替換R1N,1n中隨機(jī)抽取的個(gè)體。至此，高層遺傳算法的第一輪運(yùn)行結(jié)束，N各遺傳算法GAi(i=1N)可以從相應(yīng)于新的R1.N,1n種群繼續(xù)各自的操作。分層遺傳算法的流程圖如下：4.2 CHC算法CHC算法是shelman于1991年提出的遺傳算法的縮寫(xiě)，第

17、一個(gè)C代表（Cross generational elitist selection）策略，H 代表異物種重組（Heterogeneous recombination），第二個(gè)C代表大變異（Cataclysmic mutation）。CHC算法與基本遺傳算法SGA不同點(diǎn)在于：SGA的遺傳操作比較單純，簡(jiǎn)單地實(shí)行并行處理；而CHC算法犧牲這種單純性，換取遺傳操作的較好效果，并強(qiáng)調(diào)優(yōu)良個(gè)體的保留。下面分別介紹其遺傳操作的改進(jìn)之處。1. 選擇通常遺傳算法是依據(jù)個(gè)體的適應(yīng)度復(fù)制個(gè)體完成選擇操作的，而在CHC算法中，上世代種群于通過(guò)新的交叉方法產(chǎn)生的個(gè)體種群混合起來(lái)，從中按一定概率選擇較優(yōu)的個(gè)體。 這一

18、策略成為跨世代精英選擇。其明顯特征表現(xiàn)在：（1） 健壯性 由于這一選擇策略，即使當(dāng)交叉操作產(chǎn)生較劣個(gè)體偏多時(shí)，由于原種群多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低。（2） 遺傳多樣性保持由于大個(gè)體群操作，可以更好的保持遺傳過(guò)程中的遺傳多樣性。（3） 排序方法克服了比例適應(yīng)度計(jì)算的尺度計(jì)算2.交叉 CHC算法使用的重組操作是對(duì)均勻交叉的一種改進(jìn)。均勻交叉對(duì)父?jìng)€(gè)體位值的各位位置以相同概率實(shí)行交叉操作，這里改進(jìn)之處是：當(dāng)兩個(gè)父?jìng)€(gè)體的位置相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父?jìng)€(gè)體位置的互換。顯然，這樣的操作對(duì)模式具有很強(qiáng)的破壞性，因此，確定一閾值，當(dāng)個(gè)體間的海明距離低于該閾值時(shí)，不進(jìn)行交叉操作

19、。并且，與種群進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。3.變異CHC算法在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定的收斂時(shí)期，從優(yōu)秀個(gè)體中選擇一部分個(gè)體進(jìn)行初始化。初始化的方法是選擇一定比例的基因座，隨機(jī)的決定它們的位置。這個(gè)比例值稱(chēng)為擴(kuò)散率，一般取0.35。4.3 messy GA根據(jù)積木塊假設(shè)，SGA中，定義距長(zhǎng)的模式容易受到破壞，只有從小積木塊的模式中才能最終構(gòu)成最優(yōu)解，這對(duì)進(jìn)化模擬而言是十分不利的。為克服這一缺點(diǎn)，Goldberg等在1989年提出了一種變長(zhǎng)度染色體遺傳算法，該算法在不影響模式定義距的情況下，是優(yōu)良的模式得以增殖。在生物進(jìn)化過(guò)程中，其染色體長(zhǎng)度比不是固定不變的，而是隨著進(jìn)化過(guò)

20、程也在慢慢的變化。另一方面，在遺傳算法的實(shí)際應(yīng)用中，有時(shí)為了簡(jiǎn)化描述問(wèn)題的解， 也需要使用不同長(zhǎng)度的編碼串。例如，用遺傳算法對(duì)模糊控制器規(guī)則庫(kù)進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，事先一般不知道規(guī)則數(shù)目，這樣一個(gè)規(guī)則庫(kù)對(duì)應(yīng)一個(gè)個(gè)體，個(gè)體的染色體長(zhǎng)度可以描述為變化的。用染色體算法對(duì)人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，如果各層的節(jié)點(diǎn)數(shù)是未知的，同樣，個(gè)體染色體長(zhǎng)度也可以描述為變化的。變長(zhǎng)染色體的編碼采用二元編制，同時(shí)用一個(gè)二元數(shù)組表示，二元數(shù)組的第一位為固定座序號(hào)，第二位是基因座上的數(shù)值。變長(zhǎng)度染色體中可能在交叉操作中出現(xiàn)缺失位（缺失位上的值用0表示）和重復(fù)位（重復(fù)位用左邊的值表示）。例. X1 (1,0) (2,1) (

21、3,1) (4,0) (5,1)X2 (1,1) (2,1) (3,0)X1 (1,0) (2,1) (3,1) (4,0) (2,1) (3,0)X2 (1,1) (5,1)X1染色體為 0 1 1 0 X2染色體為 1 0 0 0 1（位碼已變）X1染色體為 0 1 1 0 1 X2染色體為 1 1 0 其交叉操作是切斷和拼接兩部分完成的。4.4自適應(yīng)遺傳算法遺傳算法的參數(shù)中交配概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性，Pc越大，新個(gè)體產(chǎn)生速率就越快。然而，Pc過(guò)大時(shí)遺傳模式被破壞的可能也越大，使得具有高適應(yīng)度的個(gè)體結(jié)構(gòu)很快就會(huì)被破壞，但是如果P

22、c過(guò)小，就不易產(chǎn)生新的個(gè)體結(jié)構(gòu)；若Pm取值過(guò)大，那么遺傳算法就變成了純粹的隨機(jī)搜索算法，Pc和Pm的確定在實(shí)際應(yīng)用中是個(gè)繁瑣和困難的事情。Srinvivas等提出的自適應(yīng)遺傳算法（Adaptive GA）,Pc和Pm能夠隨適應(yīng)度自動(dòng)改變：1. 當(dāng)種群個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使Pc,Pm增大，反之減小。2. 對(duì)于適應(yīng)度高于種群平均適應(yīng)度的個(gè)體，使Pc，Pm減小，反之增大。即好的個(gè)體盡量保持，差的個(gè)體盡量被替代而淘汰當(dāng)Pc，Pm恰當(dāng)時(shí)，AGA算法能夠在保持群體多樣性的同時(shí)保證遺傳算法的收斂性。Pc，Pm可按如下簡(jiǎn)單公式計(jì)算：（多有） K：是要選定的上式雖然簡(jiǎn)單但存在問(wèn)題，當(dāng)f或f趨于f

23、max時(shí)，Pc，Pm趨于0，f越小則Pc,Pm大。這種調(diào)整方法對(duì)于種群處于進(jìn)化后期比較合適，但在進(jìn)化初期是不當(dāng)?shù)?，這會(huì)使初期較優(yōu)的個(gè)體處于幾乎不變的狀態(tài)，從而以使進(jìn)化走向局部最優(yōu)解。為此對(duì)前式假如作如下修改便使f或f趨于fmax時(shí)，Pc，Pm不會(huì)為0。4.5 基于小生境技術(shù)的遺傳算法生物學(xué)上，小生境（niche）是指特定環(huán)境中的一種組織功能。在自然界中，往往特征、性狀相似的物種相聚在一起，并在同類(lèi)中交配繁殖后代。在SGA中，交配完全是隨機(jī)的，雖然這種隨機(jī)化的交配形式在尋優(yōu)的初級(jí)階段保持了解的多樣性，但在進(jìn)化的后期，大量個(gè)體集中于某一極值點(diǎn)上，它們的后代造成近親繁殖。在用遺傳算法求解多峰值函數(shù)的

24、優(yōu)化計(jì)算時(shí)，經(jīng)常是只能找到個(gè)別的幾個(gè)最優(yōu)解，甚至往往的得到的是局部最優(yōu)解。我們希望優(yōu)化算法能夠找出全部最優(yōu)解，引進(jìn)小生境的概念，有助于實(shí)現(xiàn)這樣的目的。小生境技術(shù)就是將每一類(lèi)個(gè)體劃分為若干類(lèi)，每個(gè)類(lèi)中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類(lèi)的優(yōu)秀代表組成一個(gè)種群，再在種群中以及不同種群之間通過(guò)雜交、變異產(chǎn)生新一代個(gè)體群。小生境技術(shù)特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問(wèn)題。小生境的模擬方法主要建立在常規(guī)選擇操作的改進(jìn)基礎(chǔ)上。1.1970年，Cavichio：當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度越過(guò)其父代個(gè)體的適應(yīng)度時(shí)，所產(chǎn)生的子代個(gè)體才能替代父代個(gè)體而遺傳到下一代個(gè)體中，否則父代個(gè)體仍保留在下一代種群中。預(yù)選擇機(jī)制的選擇

25、策略。2. 1975年，Do Jong :排列機(jī)制的選擇策略一個(gè)有限的生存空間中，各種不同的生物為了能夠延續(xù)生存，它們之間必須相互競(jìng)爭(zhēng)有限的資源設(shè)計(jì)一個(gè)排擠因子CF(一般取2或3)，由種群中隨機(jī)選擇的1/CF個(gè)個(gè)體組成排擠成員，然后依據(jù)新產(chǎn)生的個(gè)體與排擠成員的相似性來(lái)排擠一些與排擠成員相類(lèi)似的個(gè)體，個(gè)體之間的類(lèi)似性是由海明距離來(lái)度量。隨著排擠過(guò)程的進(jìn)行，群體中的個(gè)體逐漸被分類(lèi)，從而形成一個(gè)個(gè)小的生成環(huán)境，并維持群體的多樣性。3共享法的選擇策略（暫略，較難）4.6 混合遺傳算法眾所周知，梯度法、模擬退火法等一些優(yōu)化算法具有很強(qiáng)的局部搜索能力，而另一些含有問(wèn)題相關(guān)的啟發(fā)知識(shí)的啟發(fā)式算法的運(yùn)行效率也

26、比較高。如果融合這些優(yōu)化方法的思想，構(gòu)成一個(gè)新的混合遺傳算法（hybrid genetic algorithm）,是提高遺傳算法運(yùn)行效率和求解質(zhì)量的一個(gè)有效手段。目前，混合遺傳算法體現(xiàn)在兩個(gè)方面：一是引入局部搜索過(guò)程，二是增加編碼變換操作過(guò)程。在構(gòu)成混合遺傳算法時(shí)，De Jong提出下面三個(gè)基本原則；1. 盡量采用原有算法的編碼（這個(gè)原有指遺傳原有）2. 利用原有算法全局搜索的優(yōu)點(diǎn)3. 改進(jìn)遺傳算子第五章 進(jìn)化計(jì)算初步進(jìn)化計(jì)算有三個(gè)分支：（1）遺傳算法（GA）（2）進(jìn)化規(guī)劃（Evolutionary Programing ）(3)進(jìn)化策略（Evolutionary Strategy）本章將討論

27、進(jìn)化計(jì)算的理論框架及分支的構(gòu)成技術(shù)，主要介紹遺傳程序設(shè)計(jì)技術(shù)。5.1 進(jìn)化計(jì)算理論的基本框架進(jìn)化計(jì)算是指以進(jìn)化原理為仿真依據(jù)，在計(jì)算機(jī)上實(shí)現(xiàn)的具有進(jìn)化機(jī)制的算法和程序。目前進(jìn)化計(jì)算側(cè)重于算法的研究，因此有時(shí)稱(chēng)為進(jìn)化算法（Evolutionary Algorithm）若有性質(zhì)來(lái)區(qū)分， 現(xiàn)有的進(jìn)化算法可細(xì)分為：（1） 具有代表性的、最基本的遺傳算法（genetic algorithm）(第二章)（2） 側(cè)重于數(shù)值分析的進(jìn)化策略（evolutionary strategy）(5.2節(jié))（3） 介于數(shù)值分析和人工智能間的進(jìn)化規(guī)劃（evolutionary strategy）（5.3節(jié)）（4） 偏向進(jìn)化

28、自組織和系統(tǒng)動(dòng)力學(xué)特性的進(jìn)化動(dòng)力學(xué)（evolutionary dynamics）（5） 偏向以程式表現(xiàn)人工智能行為的遺傳程序設(shè)計(jì)（genetic programming）(5.4節(jié))（6） 適應(yīng)動(dòng)態(tài)環(huán)境學(xué)習(xí)的分類(lèi)系統(tǒng)（classifier system）(第8章)（7） 用以觀察復(fù)雜系統(tǒng)交互的各種生態(tài)模擬系統(tǒng)（echo system and etc）（8） 研究人工生命（artifical life）的元胞自動(dòng)機(jī)（cellualar automata）（9） 模擬螞蟻群體行為的蟻元系統(tǒng)（ant system）(10.3節(jié))基因型與表現(xiàn)型之間的關(guān)系是進(jìn)化計(jì)算中的一個(gè)基本關(guān)系，在其復(fù)雜的非線性關(guān)系中“一因多果”和“一果多因”是突出的兩個(gè)特點(diǎn)。 表現(xiàn)型的變化是對(duì)對(duì)象遺傳結(jié)構(gòu)和當(dāng)時(shí)環(huán)境條件交互作用所致的結(jié)果，非線性效果很明顯，甚至相差很大的遺傳結(jié)構(gòu)可能會(huì)導(dǎo)致類(lèi)似的行為。這樣在研究基因型表現(xiàn)型相互關(guān)系及其在進(jìn)化過(guò)程中的規(guī)律時(shí)就必須充分利用非線性系統(tǒng)工具和隨機(jī)過(guò)程的統(tǒng)計(jì)測(cè)度理論，