多個體參與交叉的遺傳算法

多個體參與交叉的遺傳算法

近年來，這種概率搜索法（ga）對科學產生了廣泛的興趣，并取得了優(yōu)異的成績。該概率搜索法用于模擬自然界的生物進化過程，調查各種潛在解，淘汰缺陷解，促進優(yōu)質解的發(fā)展，逐步提高解的質量（接近）。這種解釋功能是建立在模擬的基礎上的，模擬是與自然界形成的過程有關的。盡管模擬具有解釋功能，但也有一些不利的方面。這個問題既模糊又難。沿著模擬道路走，這將阻礙不符合模型認可的方法的發(fā)展。對于應用，遺傳計算的基本前提是，解的功能（適應值）與結構（代碼）之間的相關性應該包括在內。好解之所以好，是因為它有一個好基因（模式），好基因的這種可能性很大。在確定了這些前提后，我們回顧了之前的遺傳計算方法的運算方法，通過證明相應的模型理論體析了對解群多樣性的影響，初步解釋了計算效率最高的原因。并給出了一個例子來驗證這一點。1解群的群體迭代由于遺傳算法發(fā)展很迅速,分支很多,這里只描述基本遺傳算法.遺傳算法執(zhí)行的主要步驟如下:(1)隨機產生初始解群.(2)群體迭代:①計算每個個體的適應值;②選擇解群中較優(yōu)的一部分;③應用復制、交叉和變異算子產生新解群.3步循環(huán)執(zhí)行,直到滿足停止準則.(3)取任一代中最好的個體作為執(zhí)行結果.圖1為基本遺傳算法的框圖,其中交叉操作部分用橢圓圍起.關于基本遺傳算法有許多種描述形式,它們之間有較小的差異,本文給出的算法框圖是其中一種.2多個人參與跨多個階段的遺傳計算方法2.1多個體參與交叉的遺傳算法本文只描述與基本遺傳算法相對應的多個體參與交叉的遺傳算法.但幾乎所有的遺傳算法都可以轉化為對應的多個體參與交叉的遺傳算法形式.應用此遺傳算法求解問題的準備工作與基本遺傳算法大致相同,只是控制參數中還應加上參與交叉的父代個體數目a和交叉后產生的子代個體數目b兩個參數.這兩個參數對遺傳算法的性能有重要影響.圖2是與基本遺傳算法相對應的多個體參與交叉的遺傳算法框圖.它與圖1不同之處是用橢圓圍起的那一部分,即交叉操作部分.由圖可見,當提出了有多父代個體參與交叉的遺傳算法概念之后,基本遺傳算法便可理解為多個體參與交叉的遺傳算法中參與交叉的個體數目a=2的特例.交叉方式可以有多種多樣,本文提供一種方式.隨機產生a-1個數值在1與串長L之間的整數,這樣參與交叉的a個父代個體都被分為a段,相應子代個體的a段來自父代個體,但不一定分別來自a個父代個體,可能來自大于等于2個父代個體小于等于a個父代個體.這樣可能產生新的個體數為aa-a個,可取子代個體數目1≤b≤aa-a.例如選擇了3個個體參與交叉,隨機選取2個交叉斷點,則可產生33-3=24個新個體,子代個體數目可取1～24.由此可見,采用新的遺傳算法可明顯增加解的多樣性,從而提高計算效率.2.2模式h的數目模式定理具有短的定義長度、低階并且適應值在群體平均適應值以上的模式,在遺傳算法迭代過程中將按指數增長率被采樣.模式定理是遺傳算法的基本定理,它解釋了遺傳算法的有效性.若能證明多個體參與交叉的遺傳算法的模式定理,將會給這類遺傳算法一個堅實的根基.定理1模式定理對多個體參與交叉的遺傳算法仍然成立,而且通過調整參與交叉的個體數目對模式的短小性可有不同要求,有利于快速求得(近)最優(yōu)解.證明假設在給定的時間步t,一個特定的模式H有m個代表串包含在群體A(t)中,記為m=m(H,t),用f(H)表示在時間步t含模式H串的平均適應值,則交配池中含H的串的數目為m(Η,t)nf(Η)/n∑j=1fjm(H,t)nf(H)/∑j=1nfj定義δ(H)為模式H的長度,即從第一個確定位到最后一個確定位的數目,l表示染色體串長,則易知在一點交叉中,模式H被破壞的可能性為pd=δ(H)/(l-1),那么生存概率為ps=1-pd.a表示參與交叉的父代個體數目,而多父代參與交叉的生存概率為p(n)s=(p(2)s)a,因此在采用兩個體一點交叉的遺傳算法的下一代中,模式H的數目為m(Η,t+1)=m(Η,t)nf(Η)[1-δ(Η)l-1]/n∑j=1fjm(H,t+1)=m(H,t)nf(H)[1?δ(H)l?1]/∑j=1nfj而在多個體參與交叉的遺傳算法的下一代中,模式H的數目為m(Η,t+1)=m(Η,t)nf(Η)[1-δ(Η)l-1]a/n∑j=1fjm(H,t+1)=m(H,t)nf(H)[1?δ(H)l?1]a/∑j=1nfj3解群方差和熵從兩個方面來理解解群的多樣性,一種是解群的空間分布,顯然從這個意義上來看,解群的空間分布越大,解群的多樣性越強.因此,本文用方差來描述解群的空間分布情況.定義1若第t代解群中的個體xit由L個基因構成,即xit=[xi(1)t,xi(2)t,…,xi(L)t],i∈{1,2,…,N},定義第t代解群的平均個體為ˉx=[ˉx(1)t?ˉx(2)t???ˉx(L)t]xˉ=[xˉ(1)t?xˉ(2)t???xˉ(L)t]其中,ˉx(l)t=Ν∑i=1xi(l)t/Νxˉ(l)t=∑i=1Nxi(l)t/N.由此定義第t代的解群方差為Dt=[D(1)t?D(2)t???D(L)t]Dt=[D(1)t?D(2)t???D(L)t]其中,D(l)t=Ν∑i=1(xi(l)t-ˉx(l)t)2/Ν,而l∈{1,2,…,L}.從定義1可以看出方差Dt是L維的行向量,每一個分量表示出了解群在該維坐標上的空間分布.顯然D(l)t越大,則解群在第l維坐標上的空間分布就越大.方差僅反映出了解群的空間偏離程度,還不能完全刻畫解群的多樣性.例如,解群{1,2,3,4,5}由5個個體組成,顯然D=2;而解群{1,1,1,1,5},方差D=2.56.顯然后者比前者的方差大,但前者比后者有更大的進化能力,為此,本文引入描述解群多樣性的第二個量——熵.定義2若第t代解群有Q個子集:St1,St2,…,StQ各個子集所包含的個體數目記為|St1|,|St2|,…,|StQ|,且對任意p,q∈{1?2???Q}?Stp∩Stq=??Q∪q=1Stq=At?At為第t代解群的集合.則定義第t代解群的熵Et=-Q∑j=1pjlogpj.其中,pj=|Stj|/N,N為解群中個體數目.定義2表明:①當解群中所有個體都相同時,即Q=1,這時熵取最小值E=0;②當Q=N時,熵取最大值E=logN.解群中的個體類型越多,分配得越平均,熵就越大.對于十進制編碼,熵的最大值為EDmax=logN;對于二進制編碼熵的最大值為EBmax=log[min(N,2L)].如果解群的方差和熵都很大,解群的情況如圖3(a)所示,一般初始解群就是這個樣子.當解群的方差很大、熵很小時,如圖3(b)所示,解群集中在幾個點上;當解群的方差很小、熵很大時,解群集中在一個很小的區(qū)域中,如圖3(c)所示;當解群的方差和熵都很小時,解群收斂,如圖3(d)所示;當經過多代進化后,解群處于這種狀態(tài).4遺傳算法4個個體參與交叉多個體參與交叉的遺傳算法的交叉操作可以描述為隨機地從解群x′1t,x′2t,…,x′Nt中選出a個個體,依交換概率pc進行基因重組運算,產生解群x″1t,x″2t,…,x″Nt.文獻中證明了當解群數目無窮,交叉操作保證每個坐標的邊緣概率密度函數不變,即gx?(l)t(x(l))=gx′(l)t(x(l))(1)式中l(wèi)∈{1,2,…,L}.定理2無論交叉操作是兩個個體參與交叉,還是多個個體參與交叉,都不改變解群的方差,Dt=D0.D0為初始解群方差.證明由式(1),定理2顯然成立.定理3若解群中每個個體有L個基因位,且初始解群中有Q個子集:St1,St2,…,StQ.對任意p,q∈{1,2,…,Q},有Stp∩Stq=??Q∪q=1Stq=At?At為第t代解群的集合,若取兩個個體參與交叉,則對任意m,n∈{1,2,…,Q},xit∈Sm,xjt∈Sn,被分為兩段滿足xit≠xjt(2)則經過交叉操作后會產生兩個不同類型的個體.證明由式(2),定理3顯然成立.定理4若解群中每個個體有L個基因位,且初始解群中有Q個子集:St1,St2,…,StQ,對任意p,q∈{1,2,…,Q},有Stp∩Stq=??Q∪q=1Stq=At?At為第t代解群的集合,若取a個個體參與交叉,則對任意C1,C2,…,Ca∈{1,2,…,Q},x1t∈SC1,x2t∈SC2,…,xat∈SCa,被分為a段滿足x1t≠x2t≠?≠xatx1(1)t≠x2(1)t≠?≠xa(1)tx1(2)t≠x2(2)t≠?≠xa(2)t?x1(a)t≠x2(a)t≠?≠xa(a)t}(3)則經過交叉操作后會產生aa-a個不同類型的個體.證明由于增加了式(3)的約束,則交叉后可產生aa個個體,減去原有的a得證.由定理3、4可知,采用多個體參與交叉的遺傳算法可明顯增加解的多樣性,而且這種增加是指數增長的.例如,取3個個體參與交叉,則可產生33-3=24個新個體;取4個個體參與交叉,則可產生44-4=252個新個體.由定理2可知,交叉操作不改變解群的方差,交叉操作增加解的多樣性事實上是增加了解群的熵.而采用多個個體參與交叉的遺傳算法能呈指數快速性增加解群的熵.定理5若解群中每個個體有L個基因位,且初始解群中有Q個子集:St1,St2,…,StQ,對任意p,q∈{1,2,…,Q},有Stp∩Stq=??Q∪q=1Stq=At?At為第t代解群的集合,若取兩個個體參與交叉,則對任意m,n∈{1,2,…,Q}和l∈{1,2,…,Q},xit∈Sm,xjt∈Sn,滿足xit≠xjt(4)xi(l)t≠xj(l)t(5)則經過交叉操作,t→∞時解群中有Q′個不同類型的個體,即Q′=2(L-1)C2Q+Q(6)若子集Sk中個體的L位基因是由l1,l2,…,lL∈{1,2,…,Q}子集中的相應基因元素構成的,則子集Sk所對應的pk=|Sk|/N,由下式可得pk=pl1,pl2???plL(7)當t→∞時,解群的熵E滿足limt→∞E=-Q′∑k=1pklogpk(8)證明Q個子集中任兩個子集中各取一個個體,交換的位置有L-1個,由定理5的條件式(4)和(5)可知,一定產生兩個新個體x′,x″,且x′,x″?Sq,q∈{1,2,…,Q}.所以交叉可產生2(L-1)C2Q個新型個體,再加上原有的Q個類型,得出式(6).由定理2得知,交叉操作不改變每維坐標的基因元素,顯然式(7)成立.由熵的定義容易得出式(8).定理6當t→∞時,多個體參與交叉的遺傳算法的熵與兩個體參與交叉的熵相同.證明任意數目個體參與交叉后產生的不同類型個體都可以通過兩個體多次交叉后產生.易得定理6.由定理5、6可看出,交叉操作不能保證解群的熵在t→∞時達到最大,熵的變化與初始解群的分布有關,當初始解群的所有個體都相同時,交換操作不改變解群的熵.用二進制編碼時,式(3)、(5)不易滿足,在基因數目L相同的情況下,二進制編碼產生的新個體類型數目比十進制少.但并不意味交叉操作對二進制編碼解群熵的提高能力小.因為對于十進制數,往往采用多位二進制表示,所以對同一問題,二進制編碼的基因位總是高于十進制的基因位.5基本遺傳算法與多個體參與交叉考慮下面測試函數的極小值:f(x)=30∑i=1x2i?-5.12≤xi≤5.12此函數是簡單的平方求和函數,只有一個極小值,但由于變量個數較多,解空間龐大,因此應用基本遺傳算法求解的效率不高.本文只用此函數比較基本遺傳算法與多個體參與交叉的遺傳算法的性能.為公平起見,一些基本特征及控制參數設置如下:①二進制編碼;②賭盤選擇;③初始解群相同;④解群規(guī)模N=50;⑤交叉概率pc=0.8;⑥變異概率pm=0.001;⑦a=2,5,10,相應b=2,5,10.之所以設置⑦,是因為隨機選取多個個體參與交叉增加子計算量,相應增加子代個體數目會平衡這種計算量的增加,使得任一遺傳算法計算一代的時間大致相同.圖4所示為每代最優(yōu)解適應值的變化,圖5為每代平均適應值的變化.從圖中可知,多個體參與交叉的遺傳算法的確比基本遺傳算法性能有較大提高.6遺傳算例的初步分析提出了多個體參與交叉的遺傳算法,它的思路來