遺傳算法的數(shù)學(xué)基礎(chǔ)

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

2、能解釋為相同的構(gòu)形，是一個(gè)串的子集。在二進(jìn)制編碼中，模式是基于三個(gè)字符集0，1，*的字符串，符號(hào)*代表0或1。例1*1*表示四個(gè)元的子集010011110111對(duì)于二進(jìn)制編碼串，當(dāng)串長為L時(shí)，共有3L個(gè)不同的模式。例2串長L=3，則其模式共有*1*0*1*01*0*10*00*011*00*10*0100000共27個(gè)1+2*3+22*3+23=33遺傳算法中串的運(yùn)算實(shí)際上是模式的運(yùn)算。如果各個(gè)串的每一位按等概率生成0或1,則模式為n的種群模式種類總數(shù)的期望值為：L'、Cii2i(1-(1-(1/2)i)n)i1種群最多可以同時(shí)處理ng2l個(gè)模式，見下例例一個(gè)個(gè)體(種群中只有一個(gè))，父

3、個(gè)體011要通過變異變?yōu)樽觽€(gè)體001,其可能影響的模式為：如果獨(dú)立的考慮種群中的各個(gè)串，則僅能得到n條信息，然而當(dāng)把適應(yīng)值與各個(gè)串結(jié)合考慮，發(fā)掘串群體的相似點(diǎn)，就可得到大量的信息來幫助指導(dǎo)搜索，相似點(diǎn)的大量信息包含在規(guī)模不大的種群中。2 .模式階和定義距定義1:模式階模式H中確定位置的個(gè)數(shù)成為模式H的模式階，記作0(H)例0(011*1*0)=5定義2定義階模式中第一個(gè)確定位置和最后一個(gè)確定位置之間的距離，記作(H)(011(001*1*0)*1*)53 .模式定理假定在給定時(shí)間步t(即第t代)，種群A(t)中有m個(gè)個(gè)體屬于模式H,記為m=m(H,t),即第t代時(shí)，有m個(gè)個(gè)體屬于H模式。在再生

4、階段(即種群個(gè)體的選擇階段)，每個(gè)串根據(jù)它的適應(yīng)值進(jìn)行復(fù)制(選擇)，一個(gè)串Ai被復(fù)制(選中)的概率為:n表示種群中個(gè)體總數(shù)當(dāng)采用非重疊的n個(gè)串的種群替代種群A(t),可以得到下式:m(H,t1)=m(H,t)gngf(Hfj%fi其中：f(H)=,表示在t時(shí)模式H的平均適應(yīng)度mn_fj一_i1,._、-,»若用f=一表示種群平均適應(yīng)度，則前式可表示為:nm(H,t1)=m(H,t)f(H)上式表明：一個(gè)特定的模式按照其平均適應(yīng)度值與種群的平均適應(yīng)度值之間的比率生長，換句話說就是：那些適應(yīng)度值高于種群平均適應(yīng)度值的模式，在下一代中將會(huì)有更多的代表串處于A(t+1)中，因?yàn)樵趂(H)f時(shí)

5、有m(H,t+1)>m(H,t)假設(shè)從t=0開始，某一特定模式適應(yīng)度值保持在種群平均適應(yīng)度值以上cf,c為常數(shù)c>0,則模式選擇生長方程為：fcftm(H,t1)=m(H,t)-=(1c)m(H,t)=(1c)tm(H,0)上式表明，在種群平均值以上(以下)的模式將按指數(shù)增長(衰減)的方式被復(fù)制。下面討論交叉對(duì)模式H的影響：例：對(duì)串A分別在下面指定點(diǎn)上與Hi模式和力模式進(jìn)行交叉A0111000Hi*1*0(被破壞概率：獨(dú)=勺；生存率：1/6)1-17-16H2*10*(被破壞概率：巴由=，=1；生存率：5/6)1-17-16顯然A與H1交叉后，H1被破壞，而與巳交叉時(shí)，也不被破壞。

6、一般地有：模式H被破壞的概率為必，故交叉后模式H生1-1存的概率為1一皿(l:串長；"H):模式H的定義階)1-1考慮到交叉本身是以隨機(jī)方式進(jìn)行的，即以概率Pc進(jìn)行交叉,故對(duì)于模式H的生存概率Pc可用下式表示:Ps-1一Pc(h)1-1同時(shí)考慮選擇交叉操作對(duì)模式的影響,(選擇交叉互相獨(dú)立不影響)則子代模式的估計(jì):m(H,t1)-m(H,t)gf(H)1-Pc(H)l-1上式表明模式增長和衰減依賴于兩個(gè)因素：一是模式的適應(yīng)度值f(H)與平均適應(yīng)度值的相對(duì)大?。涣硪粋€(gè)是模式定義階6(H)的大小(當(dāng)Pc一定，L一定時(shí))。下面再考察變異操作對(duì)模式的影響：變異操作是以概率Pm隨機(jī)地改變一個(gè)位上

7、的值，為了使得模式H可以生存下來，所有特定的位必須存活。因?yàn)閱蝹€(gè)等位基因存活的概率為(1Pm)，并且由于每次變異都是統(tǒng)計(jì)獨(dú)立的，因此，當(dāng)模式H中0(H)個(gè)確定位都存活時(shí)，這時(shí)模式H才能被保留下來，存活概率為：(1-Pm)0(H)1-0(H)gPm(Pm)«1(為0.01以下)上式表明0(H)個(gè)定位值沒有被變異的概率。由此我們可得到下式m(H,t1)-m(H,t)gf-(fH1-Pcl-(-H-0(H)pmm(H,t+1)在t+1代種群中存在模式H的個(gè)體數(shù)目m(H,t)一在t代種群中存在模式H的個(gè)體數(shù)目f(H)在t代種群中包含模式H的個(gè)體平均適應(yīng)度ft代種群中所有個(gè)體的平均適應(yīng)度l個(gè)體

8、長度Pc交叉概率Pm變異概率對(duì)于k點(diǎn)交叉時(shí)，上式可表示為：ck-cK.m(H,t1)一m(H,t)gfH21一Hl一O(H)Pmfq模式定理：在遺傳算子選擇、交叉和變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。4 .積木塊假設(shè)(buildingblockhypochesis)遺傳算法通過短定義距、低階以及高適應(yīng)度的模式(積木塊)，在遺傳操作作用下相互結(jié)合，最終接近全局最優(yōu)解。滿足這個(gè)假設(shè)的條件有兩個(gè)：(1)表現(xiàn)型相近的個(gè)體基因型類似(2)遺傳因子間相關(guān)性較低積木塊假設(shè)指出，遺傳算法具備尋找全局最優(yōu)解的能力，即積木塊在遺傳算子作用下，能生成低階、短距、

9、高平均適應(yīng)度的模式，最終生成全局最優(yōu)解。模式定理還存在以下缺點(diǎn)：(1)模式定理只對(duì)二進(jìn)制編碼適用(2)模式定理只是指出具備什么條件的木塊會(huì)在遺傳過程中按指數(shù)增長或衰減，無法據(jù)此推斷算法的收斂性(3)沒有解決算法設(shè)計(jì)中控制參數(shù)選取問題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)化過程的特征進(jìn)行分析。3.3 非均勻Walsh模式變換3.4 欺騙問題在遺傳算法中，將所有妨礙評(píng)價(jià)值高的個(gè)體生成，從而影響遺傳算法正常工作的

10、問題統(tǒng)稱為欺騙問題(deceptiveproblem),根據(jù)模式定理，如果低階、高適應(yīng)度模式中包含了最優(yōu)解的話，遺傳算法就可能找出它來，但是如果低階、高適應(yīng)度模式中未包含最優(yōu)串的具體取值，則遺傳算法只能找出次優(yōu)解。定義競爭模式若模式H和H中，*位置是完全一致的，但任一確定位的編碼均不同，則稱H和H互為競爭模式。例10*與01*是競爭模式10*與11*不是競爭模式定義欺騙性假定f(x)的最大值對(duì)應(yīng)的x集合為x*，H為包含x*的m階模式，H的競爭模式為H，而且f(H)<f(H),則f為m階欺騙。例對(duì)于一個(gè)三位二進(jìn)制編碼的模式，如果f(111)為最大值，下列12個(gè)不等式中任意一個(gè)不等式成立，則

11、存在欺騙問題。模式階數(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*)造成上述欺騙問題的主要原因有兩個(gè)：編碼不當(dāng)或適應(yīng)度函數(shù)選擇不當(dāng)。如果它們均是單調(diào)關(guān)系，則不會(huì)存在欺騙性問題，但是對(duì)于一個(gè)非線性問題，難于實(shí)現(xiàn)其單調(diào)性。1 .欺騙函

12、數(shù)的類型Goldberg曾研究用適應(yīng)度函數(shù)的非單調(diào)性來研究欺騙性問題。考慮一個(gè)2位二進(jìn)制最大化問題，假定“11”對(duì)應(yīng)最優(yōu)解，若H(0*)>H(1*),則欺騙性存在。該條件可化為：f(00)+f(01)>f(10)+f(11)或f(00)+f(10)>f(01)+f(11)2222下面以前一種為例進(jìn)行討論，設(shè)r=f(11)/f(00),c=f(01)/f(00),c'=f(10)/f(00)則有：r<1+c-c'c>1：稱為I類欺騙問題，見圖1,求最優(yōu)化時(shí)較難c<=1：稱為II類欺騙問題，見圖2,此問題求最優(yōu)化更難OOv10.圖2這兩類欺騙性問

13、題應(yīng)該稱為非單調(diào)問題，在非單調(diào)問題中同時(shí)存在欺騙性和非欺騙性問題。過去，將適應(yīng)度函數(shù)的非單調(diào)問題與欺騙問題同等看待，認(rèn)為遺傳算法只有在單調(diào)問題里有效。但是，如果單調(diào)問題不使用遺傳算法或者不使用概率搜索，一般的搜索法可能是適用的，沒有遺傳算法存在的必要。即使是單調(diào)的，只有存在需要高機(jī)能交叉操作（非單調(diào)且非欺騙問題），才能使遺傳算法存在有意義，這不外乎使交叉操作成為遺傳算法本質(zhì)作用的一個(gè)證明。2 .欺騙性化解可以采用Grey編碼或糾正適應(yīng)度函數(shù)3 .遺傳算法的困難問題容易問題：采用基本的遺傳算法，易于得到最優(yōu)解的場合或問題困難問題;與上相反遺傳算法的欺騙性與遺傳算法的困難性不存在對(duì)等或等價(jià)關(guān)系，這

14、是由于遺傳算法的欺騙性是從靜態(tài)超平面分析給出的，并且假設(shè)個(gè)體數(shù)無偏差，而遺傳算法的困難性來源于不適當(dāng)?shù)膯栴}表示、交叉和變異的擾動(dòng)作用、有限的種群大小、復(fù)雜的多模型狀態(tài)圖等。3.5遺傳算法動(dòng)態(tài)分析從隨機(jī)過程和數(shù)理統(tǒng)計(jì)角度討論遺傳算法較為一般的規(guī)律，有助于較好地把握遺傳算法的特性，以提高求解效率和改善求解效果。鈴木（1995年）從Markov鏈的角度分析了基本遺傳算法（SGA）的統(tǒng)計(jì)規(guī)律，并得到了一些有意義的結(jié)論。SGA的當(dāng)前種群只與前一代種群有關(guān)，因此SGA可以用一個(gè)Markov鏈來描述。第四章遺傳算法的改進(jìn)自從1975年J.H.Holland系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來，總多學(xué)者一直

15、致力于推動(dòng)遺傳算法的發(fā)展，對(duì)編碼方式、控制參數(shù)的確定、選擇方式和交叉機(jī)理等進(jìn)行了深入的探究，引入了動(dòng)態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能，提出了各種變形的遺傳算法（VariantsofCanonicalGeneticAlgorithm簡稱VCGA）.其基本途徑概括起來有以下幾個(gè)方面：（ 1） 改變遺傳算法的組成成分或使用技術(shù)，如選用優(yōu)化控制參數(shù)、適合問題特性的編碼技術(shù)等。（ 2） 采用混合遺傳算法（ 3） 采用動(dòng)態(tài)自適應(yīng)技術(shù)，在進(jìn)化過程中調(diào)整算法控制參數(shù)和編碼力度（ 4） 采用非標(biāo)準(zhǔn)的遺傳操作算子（ 5） 采用并行遺傳算法本章將介紹這些方面的典型思路和集中改進(jìn)的遺傳算法。4.1 分層遺傳算法

16、對(duì)于一個(gè)問題，首先隨機(jī)生成N*n各樣本(n>=2,N>=2)，然后將它們分成N個(gè)子種群，每個(gè)子種群包括n各樣本，對(duì)每個(gè)子種群獨(dú)立的運(yùn)行各自的遺傳算法，記它們?yōu)镚Ai(i=1,2.N)。這N個(gè)遺傳算法最好在設(shè)置特性上有較大差異，這樣就可以為將來的高層遺傳算法產(chǎn)生更多種類的優(yōu)良模式。在每個(gè)子種群的遺傳算法運(yùn)行到一定代數(shù)后，將N個(gè)遺傳算法的結(jié)果種群記錄到二維數(shù)組R；N,1-n中，則Ri,j(i=1-N,j=1-n)表示GAi的結(jié)果種群的第j個(gè)個(gè)體。同時(shí)將N各結(jié)果種群的平均適應(yīng)度值記錄到數(shù)組A1.N中，Ai表示GAi的結(jié)果種群平均適應(yīng)度。高層遺傳算法與普通遺傳算法的操作相類似，也可以分為以

17、下三個(gè)步驟：1 .選擇(種群之內(nèi)選擇)基于數(shù)組A1小,即N個(gè)遺傳算法的平均適應(yīng)度值，對(duì)數(shù)組R代表結(jié)果種群進(jìn)行選擇操作，一些結(jié)果種群由于它們的平均適應(yīng)度值高而被復(fù)制，甚至復(fù)制多次；另一些結(jié)果種群由于它們的種群平均適應(yīng)度值低而被淘汰。2 .交叉(種群之間交叉)如果Ri,1-in和Rj,1.川被隨機(jī)地匹配到一起，而且從位置x進(jìn)行交叉(14，jMn;1MxMn-1)則Ri,x+1.n和Rj,x+1.n相互交換相應(yīng)的部分。這一步驟相當(dāng)于交換GAi和GAj中結(jié)果種群的n-x個(gè)個(gè)體。3 .變異以很小的概率將少量隨機(jī)生成的新個(gè)體替換R1-N,1-n中隨機(jī)抽取的個(gè)體。至此，高層遺傳算法的第一輪運(yùn)行結(jié)束，N各遺傳

18、算法GAi(i=1N)可以從相應(yīng)于新的R1.N,1n種群繼續(xù)各自的操作。分層遺傳算法的流程圖如下:4.2 CHC算法CHC算法是Eshelman于1991年提出的遺傳算法的縮寫，第一個(gè)C代表(Crossgenerationalelitistselection)策略，H代表異物種重組(Heterogeneousrecombination)，第二個(gè)C代表大變異(Cataclysmicmutation)。CHC算法與基本遺傳算法SGA不同點(diǎn)在于：SGA的遺傳操作比較單純，簡單地實(shí)行并行處理；而CHC算法犧牲這種單純性，換取遺傳操作的較好效果，并強(qiáng)調(diào)優(yōu)良個(gè)體的保留。下面分別介紹其遺傳操作的改進(jìn)之處。1

19、. 選擇通常遺傳算法是依據(jù)個(gè)體的適應(yīng)度復(fù)制個(gè)體完成選擇操作的，而在CHC算法中，上世代種群于通過新的交叉方法產(chǎn)生的個(gè)體種群混合起來，從中按一定概率選擇較優(yōu)的個(gè)體。這一策略成為跨世代精英選擇。其明顯特征表現(xiàn)在：( 1) 健壯性由于這一選擇策略，即使當(dāng)交叉操作產(chǎn)生較劣個(gè)體偏多時(shí)，由于原種群多數(shù)個(gè)體殘留，不會(huì)引起個(gè)體的評(píng)價(jià)值降低。( 2) 遺傳多樣性保持由于大個(gè)體群操作，可以更好的保持遺傳過程中的遺傳多樣性。( 3) 排序方法克服了比例適應(yīng)度計(jì)算的尺度計(jì)算2 .交叉CHC算法使用的重組操作是對(duì)均勻交叉的一種改進(jìn)。均勻交叉對(duì)父個(gè)體位值的各位位置以相同概率實(shí)行交叉操作，這里改進(jìn)之處是：當(dāng)兩個(gè)父個(gè)體的位置

20、相異的位數(shù)為m時(shí)，從中隨機(jī)選取m/2個(gè)位置，實(shí)行父個(gè)體位置的互換。顯然，這樣的操作對(duì)模式具有很強(qiáng)的破壞性，因此，確定一閾值，當(dāng)個(gè)體間的海明距離低于該閾值時(shí)，不進(jìn)行交叉操作。并且，與種群進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。3 .變異CHC算法在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定的收斂時(shí)期，從優(yōu)秀個(gè)體中選擇一部分個(gè)體進(jìn)行初始化。初始化的方法是選擇一定比例的基因座，隨機(jī)的決定它們的位置。這個(gè)比例值稱為擴(kuò)散率，一般取0.35。4 .3messyGA根據(jù)積木塊假設(shè)，SGA中，定義距長的模式容易受到破壞，只有從小積木塊的模式中才能最終構(gòu)成最優(yōu)解，這對(duì)進(jìn)化模擬而言是十分不利的。為克服這一缺點(diǎn)，Goldb

21、erg等在1989年提出了一種變長度染色體遺傳算法，該算法在不影響模式定義距的情況下，是優(yōu)良的模式得以增殖。在生物進(jìn)化過程中，其染色體長度比不是固定不變的，而是隨著進(jìn)化過程也在慢慢的變化。另一方面，在遺傳算法的實(shí)際應(yīng)用中，有時(shí)為了簡化描述問題的解，也需要使用不同長度的編碼串。例如，用遺傳算法對(duì)模糊控制器規(guī)則庫進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，事先一般不知道規(guī)則數(shù)目，這樣一個(gè)規(guī)則庫對(duì)應(yīng)一個(gè)個(gè)體，個(gè)體的染色體長度可以描述為變化的。用染色體算法對(duì)人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行優(yōu)化設(shè)計(jì)時(shí)，如果各層的節(jié)點(diǎn)數(shù)是未知的，同樣，個(gè)體染色體長度也可以描述為變化的。變長染色體的編碼采用二元編制，同時(shí)用一個(gè)二元數(shù)組表示，二元數(shù)組的第一位為固定

22、座序號(hào)，第二位是基因座上的數(shù)值。變長度染色體中可能在交叉操作中出現(xiàn)缺失位(缺失位上的值用0表示)和重復(fù)位(重復(fù)位用左邊的值表示)。例.X1(1,0)(2,1)(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染色體為0110X2染色體為10001(位碼已變)X1染色體為01101X2染色體為110其交叉操作是切斷和拼接兩部分完成的。4.4 自適應(yīng)遺傳算法遺傳算法的參數(shù)中交配概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在，直接影響算法的收斂性，Pc越大，新個(gè)體產(chǎn)生速率就越快。

23、然而，Pc過大時(shí)遺傳模式被破壞的可能也越大，使得具有高適應(yīng)度的個(gè)體結(jié)構(gòu)很快就會(huì)被破壞，但是如果Pc過小，就不易產(chǎn)生新的個(gè)體結(jié)構(gòu)；若Pm取值過大，那么遺傳算法就變成了純粹的隨機(jī)搜索算法，Pc和Pm的確定在實(shí)際應(yīng)用中是個(gè)繁瑣和困難的事情。Srinvivas等提出的自適應(yīng)遺傳算法(AdaptiveGA),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í)保證遺傳算法的收斂性。

24、Pc,Pm可按如下簡單公式計(jì)算：（多有=k2,k3=k4）f'-favg3（，-f'）f'favgPc=fmaxfavgk2f-favgk3（fmax-f'）ffavgPm=fmax-favgKK:是要選定的上式雖然簡單但存在問題，當(dāng)f'或f趨于fmax時(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。(Pci-Pc2)(f'-favg)axp

25、m1(Pmi一Pm2)(fmax一f)avgmaxavgpmiPci=0.9,Pc2=0.6,Pmi=01Pm2=0.0014.5 基于小生境技術(shù)的遺傳算法生物學(xué)上，小生境（niche）是指特定環(huán)境中的一種組織功能。在自然界中，往往特征、性狀相似的物種相聚在一起，并在同類中交配繁殖后代。在SGA中，交配完全是隨機(jī)的，雖然這種隨機(jī)化的交配形式在尋優(yōu)的初級(jí)階段保持了解的多樣性，但在進(jìn)化的后期，大量個(gè)體集中于某一極值點(diǎn)上，它們的后代造成近親繁殖。在用遺傳算法求解多峰值函數(shù)的優(yōu)化計(jì)算時(shí)，經(jīng)常是只能找到個(gè)別的幾個(gè)最優(yōu)解，甚至往往的得到的是局部最優(yōu)解。我們希望優(yōu)化算法能夠找出全部最優(yōu)解，引進(jìn)小生境的概念，

26、有助于實(shí)現(xiàn)這樣的目的。小生境技術(shù)就是將每一類個(gè)體劃分為若干類，每個(gè)類中選出若干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群，再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個(gè)體群。小生境技術(shù)特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問題。小生境的模擬方法主要建立在常規(guī)選擇操作的改進(jìn)基礎(chǔ)上。1.1970年，Cavichio：當(dāng)新產(chǎn)生的子代個(gè)體的適應(yīng)度越過其父代個(gè)體的適應(yīng)度時(shí)，所產(chǎn)生的子代個(gè)體才能替代父代個(gè)體而遺傳到下一代個(gè)體中，否則父代個(gè)體仍保留在下一代種群中。預(yù)選擇機(jī)制的選擇策略。2 .1975年，DoJong:排列機(jī)制的選擇策略一個(gè)有限的生存空間中，各種不同的生物為了能夠延續(xù)生存，它們之間必須相互競

27、爭有限的資源一一設(shè)計(jì)一個(gè)排擠因子CF（一般取2或3）,由種群中隨機(jī)選擇的1/CF個(gè)個(gè)體組成排擠成員，然后依據(jù)新產(chǎn)生的個(gè)體與排擠成員的相似性來排擠一些與排擠成員相類似的個(gè)體，個(gè)體之間的類似性是由海明距離來度量。隨著排擠過程的進(jìn)行，群體中的個(gè)體逐漸被分類，從而形成一個(gè)個(gè)小的生成環(huán)境，并維持群體的多樣性。3 共享法的選擇策略（暫略，較難）4.6混合遺傳算法眾所周知，梯度法、模擬退火法等一些優(yōu)化算法具有很強(qiáng)的局部搜索能力，而另一些含有問題相關(guān)的啟發(fā)知識(shí)的啟發(fā)式算法的運(yùn)行效率也比較高。如果融合這些優(yōu)化方法的思想，構(gòu)成一個(gè)新的混合遺傳算法（hybridgeneticalgorithm）,是提高遺傳算法運(yùn)行

28、效率和求解質(zhì)量的一個(gè)有效手段。目前，混合遺傳算法體現(xiàn)在兩個(gè)方面：一是引入局部搜索過程，二是增加編碼變換操作過程。在構(gòu)成混合遺傳算法時(shí)，DeJong提出下面三個(gè)基本原則；1. 盡量采用原有算法的編碼（這個(gè)原有指遺傳原有）2. 利用原有算法全局搜索的優(yōu)點(diǎn)3. 改進(jìn)遺傳算子第五章進(jìn)化計(jì)算初步進(jìn)化計(jì)算有三個(gè)分支：（1）遺傳算法（GA）（2）進(jìn)化規(guī)劃EvolutionaryPrograming)(3)進(jìn)化策略(EvolutionaryStrategy)本章將討論進(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)的具

29、有進(jìn)化機(jī)制的算法和程序。目前進(jìn)化計(jì)算側(cè)重于算法的研究，因此有時(shí)稱為進(jìn)化算法（EvolutionaryAlgorithm）若有性質(zhì)來區(qū)分，現(xiàn)有的進(jìn)化算法可細(xì)分為：（ 1） 具有代表性的、最基本的遺傳算法（geneticalgorithm）（第二章）（ 2） 側(cè)重于數(shù)值分析的進(jìn)化策略（evolutionarystrategy）（5.2節(jié)）（ 3） 介于數(shù)值分析和人工智能間的進(jìn)化規(guī)劃（evolutionarystrategy）（5.3節(jié)）（ 4） 偏向進(jìn)化自組織和系統(tǒng)動(dòng)力學(xué)特性的進(jìn)化動(dòng)力學(xué)（evolutionarydynamics）（ 5） 偏向以程式表現(xiàn)人工智能行為的遺傳程序設(shè)計(jì)（geneticp

30、rogramming）（5.4節(jié)）（ 6） 適應(yīng)動(dòng)態(tài)環(huán)境學(xué)習(xí)的分類系統(tǒng)（classifiersystem）（第8章）（ 7） 用以觀察復(fù)雜系統(tǒng)交互的各種生態(tài)模擬系統(tǒng)（echosystemandetc)（ 8） 研究人工生命(artificallife)的元胞自動(dòng)機(jī)(cellualarautomata)（ 9） 模擬螞蟻群體行為的蟻元系統(tǒng)(antsystem)(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)致類似的行為。這樣在研究基因型表現(xiàn)型相互關(guān)系及其在進(jìn)化過程中的規(guī)律時(shí)就必須充分利用非線性系統(tǒng)工具和隨機(jī)過程的統(tǒng)計(jì)測度理論，動(dòng)力學(xué)機(jī)制也是必須加以研究的動(dòng)態(tài)屬性。適應(yīng)度狀態(tài)圖描述了適應(yīng)度和基因型間的關(guān)系，自適應(yīng)狀態(tài)圖則勾畫了適應(yīng)度與