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

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

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

4、個(gè)體屬于模式H,記為即第t代時(shí),有m個(gè)個(gè)體屬于H模式.在再生階段(即種群個(gè)體的選擇階段),每個(gè)串根據(jù)它的適應(yīng)值進(jìn)行復(fù)制(選擇),一個(gè)串Ai被復(fù)制(選中)的概率為：'EA->1n表示種群中個(gè)體總數(shù)當(dāng)采用非重疊的n個(gè)串的種群替代種群A(t),可以得到下式:+1)=ifj>1其中：/()=表示在t時(shí)模式H的平均適應(yīng)度m_Z力假設(shè)用7二三一表示種群平均適應(yīng)度,那么前式可表示為：nmH+)=m(H,af上式說明：一個(gè)特定的模式根據(jù)其平均適應(yīng)度值與種群的平均適應(yīng)度值之間的比率生長(zhǎng),換句話說就是：那些適應(yīng)度值高于種群平均適應(yīng)度值的模式,在下一代中將會(huì)有更多的代表串處于A(t+1)中,由于

5、在/(H)77時(shí)有m(H,t+l)>m(H,t)假設(shè)從t=0開始,某一特定模式適應(yīng)度值保持在種群平均適應(yīng)度值以上.f,c為常數(shù)c>0,那么模式選擇生長(zhǎng)方程為：/?(/,r+1)=二年=(1+=(1+c)rm(H,O)f上式說明,在種群平均值以上(以下)的模式將按指數(shù)增長(zhǎng)(衰減)的方式被復(fù)制.下面討論交叉對(duì)模式H的影響：例：對(duì)串A分別在下面指定點(diǎn)上與Hi模式和H2模式進(jìn)行交叉A0111000Hj*1*0(被破壞概率：=-；生存率：1/6)/17-16H2*10*(被破壞概率：出2=L_=L生存率：5/6)/1716顯然A與Hi交叉后,Hi被破壞,而與H2交叉時(shí),此不被破壞.一般地有：

6、模式H被破壞的概率為也故交叉后模/1式H生存的概率為也J串長(zhǎng)；演H):模式H的定義階)/1考慮到交叉本身是以隨機(jī)方式進(jìn)行的,即以概率Pc進(jìn)行交叉,故對(duì)于模式H的生存概率Pc可用下式表示：同時(shí)考慮選擇交叉操作對(duì)模式的影響,選擇交叉互相獨(dú)立不影響那么子代模式的估計(jì)：,"%+1J.也2口一*2JIT上式說明模式增長(zhǎng)和衰減依賴于兩個(gè)因素：一是模式的適應(yīng)度值fH與平均適應(yīng)度值的相對(duì)大??；另一個(gè)是模式定義階6H的大小當(dāng)Pc一定,L一定時(shí).下面再考察變異操作對(duì)模式的影響：變異操作是以概率Pm隨機(jī)地改變一個(gè)位上的值,為了使得模式H可以生存下來,所有特定的位必須存活.由于單個(gè)等位基因存活的概率為1Pm

7、,并且由于每次變異都是統(tǒng)計(jì)獨(dú)立的,因此,當(dāng)模式H中OH個(gè)確定位都存活時(shí),這時(shí)模式H才能被保存下來,存活概率為：1一4°,.1.4化“/%«1為0.01以下上式說明OH個(gè)定位值沒有被變異的概率.由此我們可得到下式m(H,t+1)>J利/+l在t+1代種群中存在模式H的個(gè)體數(shù)目研在t代種群中存在模式H的個(gè)體數(shù)目fH在t代種群中包含模式H的個(gè)體平均適應(yīng)度7t代種群中所有個(gè)體的平均適應(yīng)度/個(gè)體長(zhǎng)度Pc交叉概率變異概率對(duì)于k點(diǎn)交叉時(shí),上式可表示為：+1利J絲.口_J一丁",-7%模式定理：在遺傳算子選擇、交叉和變異的作用下,具有低階、短定義距以及平均適應(yīng)度高于種群平均

8、適應(yīng)度的模式在子代中呈指數(shù)增長(zhǎng).4.積木塊假設(shè)buildingblockhypochesis遺傳算法通過短定義距、低階以及高適應(yīng)度的模式積木塊,在遺傳操作作用下相互結(jié)合,最終接近全局最優(yōu)解.滿足這個(gè)假設(shè)的條件有兩個(gè)：1表現(xiàn)型相近的個(gè)體基因型類似2遺傳因子間相關(guān)性較低積木塊假設(shè)指出,遺傳算法具備尋找全局最優(yōu)解的水平,即積木塊在遺傳算子作用下,能生成低階、短距、高平均適應(yīng)度的模式,最終生成全局最優(yōu)解.模式定理還存在以下缺點(diǎn)：1模式定理只對(duì)二進(jìn)制編碼適用2模式定理只是指出具備什么條件的木塊會(huì)在遺傳過程中按指數(shù)增長(zhǎng)或衰減,無法據(jù)此推斷算法的收斂性(3)沒有解決算法設(shè)計(jì)中限制參數(shù)選取問題3.2 Wals

9、h模式變換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è)體生成,從而影響遺傳算法正常工作的問題統(tǒng)稱為欺騙問題(deceptiveproblem),根據(jù)模式定理,如果低階、高適應(yīng)度模式中包含了最優(yōu)解的話,遺傳算法就可能找出它來,但是如果低階、高適應(yīng)度模式中未包含最優(yōu)串的具體取值,那么遺傳算法只能找出次優(yōu)解.定義競(jìng)爭(zhēng)模式假設(shè)模式H和H,中,*

10、位置是完全一致的,但任一確定位的編碼均不同,那么稱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)vf(H)那么f為m階欺騙.例對(duì)于一個(gè)三位二進(jìn)制編碼的模式,如果f(lll)為最大值,以下12個(gè)不等式中任意一個(gè)不等式成立,那么存在欺騙問題.模式階數(shù)為1時(shí)：f(*l)<f(*O),f(*1*)<f(*O*),f(l*)<f(O*)模式階數(shù)為2時(shí)：f(*ll)<f(*OO),f(l*l)<f(O*O),f(ll*)<f(00*)f(*

11、ll)<f(*O1),f(1*1)<f(0*)<f(01*)f(*ll)<f(*10),f(1*l)<f(l*O),f(ll*)<f(l0*)造成上述欺騙問題的主要原因有兩個(gè)：編碼不當(dāng)或適應(yīng)度函數(shù)選擇不當(dāng).如果它們均是單調(diào)關(guān)系,那么不會(huì)存在欺騙性問題,但是對(duì)于一個(gè)非線性問題,難于實(shí)現(xiàn)其單調(diào)性.1 .欺騙函數(shù)的類型Goldberg曾研究用適應(yīng)度函數(shù)的非單調(diào)性來研究欺騙性問題.考慮一個(gè)2位二進(jìn)制最大化問題,假定力1對(duì)應(yīng)最優(yōu)解,假設(shè)H(0*)>H(1*),那么欺騙性存在.該條件可化為:/(00)+/(01)>川0)+/(11)或八.0)+/(10)&g

12、t;/(01)+/(11)下而以前一種為例進(jìn)行討論,設(shè)r=/(ll)/(00),c=/(01)/(00),cf=/(10)/(00)那么有：r<l+c-c'c>l：稱為I類欺騙問題,見圖1,求最優(yōu)化時(shí)較難c二i：稱為n類欺騙問題,見圖2,此問題求最優(yōu)化更難圖2這兩類欺騙性問題應(yīng)該稱為非單調(diào)問題,在非單調(diào)問題中同時(shí)存在欺騙性和非欺騙性問題.過去,將適應(yīng)度函數(shù)的非單調(diào)問題與欺騙問題同等看待,認(rèn)為遺傳算法只有在單調(diào)問題里有效.但是,如果單調(diào)問題不使用遺傳算法或者不使用概率搜索,一般的搜索法可能是適用的,沒有遺傳算法存在的必要.即使是單調(diào)的,只有存在需要高機(jī)能交叉操作非單調(diào)且非欺騙

13、問題,才能使遺傳算法存在有意義,這不外乎使交叉操作成為遺傳算法本質(zhì)作用的一個(gè)證實(shí).2 .欺騙性化解可以采用Grey編碼或糾正適應(yīng)度函數(shù)3 .遺傳算法的困難問題容易問題：采用根本的遺傳算法,易于得到最優(yōu)解的場(chǎng)合或問題困難問題;與上相反遺傳算法的欺騙性與遺傳算法的困難性不存在對(duì)等或等價(jià)關(guān)系,這是由于遺傳算法的欺騙性是從靜態(tài)超平而分析給出的,并且假設(shè)個(gè)體數(shù)無偏差,而遺傳算法的困難性來源于不適當(dāng)?shù)膯栴}表示、交叉和變異的擾動(dòng)作用、有限的種群大小、復(fù)雜的多模型狀態(tài)圖等O3.5遺傳算法動(dòng)態(tài)分析從隨機(jī)過程和數(shù)理統(tǒng)計(jì)角度討論遺傳算法較為一般的規(guī)律,有助于較好地把握遺傳算法的特性,以提升求解效率和改善求解效果o鈴

14、木(1995年)從Markov鏈的角度分析了根本遺傳算法(SGA)的統(tǒng)計(jì)規(guī)律,并得到了一些有意義的結(jié)論.SGA的當(dāng)前種群只與前一代種群有關(guān),因此SGA可以用一個(gè)Markov鏈來描述.第四章遺傳算法的改良自從1975年J.H.Holkmd系統(tǒng)地提出遺傳算法的完整結(jié)構(gòu)和理論以來,總多學(xué)者一直致力于推動(dòng)遺傳算法的開展,對(duì)編碼方式、控制參數(shù)確實(shí)定、選擇方式和交叉機(jī)理等進(jìn)行了深入的探究,引入了動(dòng)態(tài)策略和自適應(yīng)策略以改善遺傳算法的性能,提出了各種變形的遺傳算法VariantsofCanonicalGeneticAlgorithm,簡(jiǎn)稱VCGA.其根本途徑概括起來有以下幾個(gè)方面：（1） 改變遺傳算法的組成成

15、分或使用技術(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） 采用并行遺傳算法本章將介紹這些方面的典型思路和集中改良的遺傳算法.4.1分層遺傳算法對(duì)于一個(gè)問題,首先隨機(jī)生成N*n各樣本n>=2,N>=2,然后將它們分成N個(gè)子種群,每個(gè)子種群包括n各樣本,對(duì)每個(gè)子種群獨(dú)立的運(yùn)行各自的遺傳算法,記它們?yōu)镚Ai=l,2,.N.這N個(gè)遺傳算法最好在設(shè)置特性上有較大差異,這樣就可以為將來的高層遺傳算法產(chǎn)生更多種類的優(yōu)良模式.在每個(gè)子種群的遺傳算法運(yùn)行到一定代數(shù)后,將

16、N個(gè)遺傳算法的結(jié)果種群記錄到二維數(shù)組R1中,那么RiJi=l.N,j=l.n表示GA的結(jié)果種群的第j個(gè)個(gè)體.同時(shí)將N各結(jié)果種群的平均適應(yīng)度值記錄到數(shù)組中,Ai表示GA的結(jié)果種群平均適應(yīng)度.高層遺傳算法與普通遺傳算法的操作相類似,也可以分為以下三個(gè)步驟：1 .選擇(種群之內(nèi)選擇)基于數(shù)組即N個(gè)遺傳算法的平均適應(yīng)度值,對(duì)數(shù)組R代表結(jié)果種群進(jìn)行選擇操作,一些結(jié)果種群由于它們的平均適應(yīng)度值高而被復(fù)制,甚至復(fù)制屢次；另一些結(jié)果種群由于它們的種群平均適應(yīng)度值低而被淘汰.2 .交叉(種群之間交叉)如果和Rjn被隨機(jī)地匹配到一起,而且從位置x進(jìn)行交叉(l<i9j<n;<x<n-l)那么

17、Ri,x+1.n和Rj,x+1n相互交換相應(yīng)的局部.這一步驟相當(dāng)于交換GA和GAj中結(jié)果種群的n-x個(gè)個(gè)體.3 .變異以很小的概率將少量隨機(jī)生成的新個(gè)體替換n中隨機(jī)抽取的個(gè)體.至此,高層遺傳算法的第一輪運(yùn)行結(jié)束,N各遺傳算法GA(i=lN)可以從相應(yīng)于新的R1.N,L.n種群繼續(xù)各自的操作0分層遺傳算法的流程圖如下：4.2 CHC算法CHC算法是Eshelman于1991年提出的遺傳算法的縮寫,第一個(gè)C代表(Crossgenerationalelitistselection)策略,H代表異物種重組(Heterogeneousrecombination),第二個(gè)C代表大變異(Cataclysmi

18、cmutation)oCHC算法與根本遺傳算法SGA不同點(diǎn)在于：SGA的遺傳操作比擬單純,簡(jiǎn)單地實(shí)行并行處理；而CHC算法犧牲這種單純性,換取遺傳操作的較好效果,并強(qiáng)調(diào)優(yōu)良個(gè)體的保存.下面分別介紹其遺傳操作的改良之處.1 .選擇通常遺傳算法是依據(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è)體群操作,可以更好的保持遺傳過程中的遺

19、傳多樣性O(shè)3排序方法克服了比例適應(yīng)度計(jì)算的尺度計(jì)算2交叉CHC算法使用的重組操作是對(duì)均勻交叉的一種改良.均勻交叉對(duì)父?jìng)€(gè)體位值的各位位置以相同概率實(shí)行交叉操作,這里改良之處是：當(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)行交叉操作.并且,與種群進(jìn)化收斂的同時(shí),逐漸地減小該閾值.3.變異CHC算法在進(jìn)化前期不采取變異操作,當(dāng)種群進(jìn)化到一定的收斂時(shí)期,從優(yōu)秀個(gè)體中選擇一局部個(gè)體進(jìn)行初始化.初始化的方法是選擇一定比例的基因座,隨機(jī)的決定它們的位置.這個(gè)比例值稱為擴(kuò)散率,

20、一般取0.35.4.3 messyGA根據(jù)積木塊假設(shè),SGA中,定義距長(zhǎng)的模式容易受到破壞,只有從小積木塊的模式中才能最終構(gòu)成最優(yōu)解,這對(duì)進(jìn)化模擬而言是十分不利的.為克服這一缺點(diǎn),Goldberg等在1989年提出了一種變長(zhǎng)度染色體遺傳算法,該算法在不影響模式定義距的情況下,是優(yōu)良的模式得以增殖.在生物進(jìn)化過程中,其染色體長(zhǎng)度比不是固定不變的,而是隨著進(jìn)化過程也在慢慢的變化.另一方面,在遺傳算法的實(shí)際應(yīng)用中,有時(shí)為了簡(jiǎ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)度可以描述為

21、變化的.用染色體算法對(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ù)位用左邊的值表示).例.X(1,0)(2,1)(3,1)(4,0)(5,1)X2(1,1)(2,1)(3,0)X、(1,0)(2,1)(3,1)(4,0)(2,1)(3,0)X2(1,1)(5,1)X、染色體為0110X、染色體為100.1(位碼己變)Xi染色體為01101X2染色體為110其交叉

22、操作是切斷和拼接兩局部完成的.4.4 自適應(yīng)遺傳算法遺傳算法的參數(shù)中交配概率Pc和變異概率Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵所在,直接影響算法的收斂性,Pc越大,新個(gè)體產(chǎn)生速率就越快.然而,Pc過大時(shí)遺傳模式被破壞的可能也越大,使得具有高適應(yīng)度的個(gè)體結(jié)構(gòu)很快就會(huì)被破壞,但是如果Pc過小,就不易產(chǎn)生新的個(gè)體結(jié)構(gòu)；假設(shè)Pm取值過大,那么遺傳算法就變成了純粹的隨機(jī)搜索算法,Pc和Pm確實(shí)定在實(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增大,反之減小.

23、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：是要選定的f之fa、*f<Lvg上式雖然簡(jiǎn)單但存在問題,當(dāng)尸或f趨于fmx時(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ì)前式假設(shè)作如下修改便使f'或f趨于fmax時(shí),Pc,Pm不會(huì)為0.Pc=&

24、#39;(PlP,2)(/%)/Pel-J-JavgJmaxJavgf'<faVgPm(P"一P,2)(/max-/)maxf之力喀PmiPd=0-9,pc2=0.6,=0.1,Pro2=0.001生物學(xué)上,小生境niche是指特定環(huán)境中的一種組織功能o在自然界中,往往特征、性狀相似的物種相聚在一起,并在同類中交配繁殖后代.在SGA中,交配完全是隨機(jī)的,雖然這種隨機(jī)化的交配形式在尋優(yōu)的初級(jí)階段保持了解的多樣性,但在進(jìn)化的后期,大量個(gè)體集中于某一極值點(diǎn)上,它們的后代造成近親繁殖.在用遺傳算法求解多峰值函數(shù)的優(yōu)化計(jì)算時(shí),經(jīng)常是只能找到個(gè)別的幾個(gè)最優(yōu)解,甚至往往的得到的是局部

25、最優(yōu)解.我們希望優(yōu)化算法能夠找出全部最優(yōu)解,引進(jìn)小生境的概念,有助于實(shí)現(xiàn)這樣的目的.小生境技術(shù)就是將每一類個(gè)體劃分為假設(shè)干類,每個(gè)類中選出假設(shè)干適應(yīng)度較大的個(gè)體作為一個(gè)類的優(yōu)秀代表組成一個(gè)種群,再在種群中以及不同種群之間通過雜交、變異產(chǎn)生新一代個(gè)體群.小生境技術(shù)特別適合于復(fù)雜多峰函數(shù)的優(yōu)化問題.小生境的模擬方法主要建立在常規(guī)選擇操作的改良根底上.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è)

26、有限的生存空間中,各種不同的生物為了能夠延續(xù)生存,它們之間必須相互競(jìng)爭(zhēng)有限的資源設(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è)新的混合遺傳算法(hybr

27、idgeneticalgorithm),是提升遺傳算法運(yùn)行效率和求解質(zhì)量的一個(gè)有效手段.目前,混合遺傳算法表達(dá)在兩個(gè)方面：一是引入局部搜索過程,二是增加編碼變換操作過程.在構(gòu)成混合遺傳算法時(shí),DeJong提出下面三個(gè)根本原那么；1 .盡量采用原有算法的編碼(這個(gè)原有指遺傳原有)2 .利用原有算法全局搜索的優(yōu)點(diǎn)3 .改良遺傳算子第五章進(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ì)算理論

28、的根本框架進(jìn)化計(jì)算是指以進(jìn)化原理為仿真依據(jù),在計(jì)算機(jī)上實(shí)現(xiàn)的具有進(jìn)化機(jī)制的算法和程序.目前進(jìn)化計(jì)算側(cè)重于算法的研究,因此有時(shí)稱為進(jìn)化算法(EvolutionaryAlgorithm)假設(shè)有性質(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) 偏向

29、以程式表現(xiàn)人工智能行為的遺傳程序設(shè)計(jì)(geneticprogramming)(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ì)測(cè)度理論,動(dòng)力學(xué)機(jī)制也是必須加以研究的動(dòng)態(tài)屬性.適應(yīng)度狀態(tài)圖描述了適應(yīng)度和基因型間的關(guān)系,自適應(yīng)狀態(tài)圖那么