基于多樣化進化策略的基因式gep算法

基于多樣化進化策略的基因式gep算法

基于多樣性策略的基因程式算法基因矩陣編程（gep：gene代理人）是2001年科迪納基于遺傳算法（ga：genticalgorithm）和遺傳編程（ep：gentic驅動程序）的新算法。GEP同傳統(tǒng)的遺傳算法和遺傳編程的主要步驟很相似,但在個體的編碼方法及結果的表現(xiàn)形式等方面又有明顯區(qū)別。Candida指出GEP比GA和GP快2～4個數(shù)量級。由于無須事先假定擬解決問題的任何先驗模型和其較高的演化效率及精度,GEP算法被廣泛應用于函數(shù)發(fā)現(xiàn)、關聯(lián)規(guī)則、分類、聚類和多模函數(shù)優(yōu)化等重要問題。GEP算法自身也存在不足,未成熟收斂是其中重要問題之一。部分局部最優(yōu)個體常會主導整個種群的進化,而其他有發(fā)展?jié)摿Φ膫€體(即有可能進化得到全局最優(yōu)解的個體)則較難進化到下一代,從而導致了整個進化停滯,使最終結果陷入局部最優(yōu)。因此,如何改善GEP算法的搜索能力,在提高算法的收斂速度的同時又保證了精度,使其更好地應用于實際工程領域,是各國研究者一直探索的主要課題。針對上述缺陷,文獻從修改GEP算法的控制參數(shù)方面對GEP算法進行改進,文獻使用自適應的參數(shù)設計方法改進GEP的進化效率,文獻將GEP算法和模擬退火相結合。但這些方法仍然存在問題,如進化控制參數(shù)定量方法并不具備普遍適用性,因此,目前GEP算法仍未能很好地解決全局搜索和局部搜索之間的矛盾。為此,筆者提出一種基于多樣化進化策略的基因表達式算法DS-GEP(GeneExpressionProgrammingbasedonDiversifieddevelopmentStrategy),通過基因空間均勻分布策略、自適應地交叉、變異算子以及淘汰算子等方法,對種群給予不同的進化策略,以保持個體間的多樣性,從而增強算法的尋優(yōu)能力。通過對函數(shù)發(fā)現(xiàn)的實驗證明,多樣化進化策略的各個部分均對改善挖掘效率發(fā)揮了作用,總體提高了DS-GEP函數(shù)挖掘算法的成功率,平均成功進化代數(shù)縮短了11%,成功進化時間縮短了8%,進化成功率提高了20%。1多樣性發(fā)展戰(zhàn)略1.1適用gsbs的多基因染色體種群初始化策略在傳統(tǒng)的GEP算法中,對初始種群采用隨機初始化策略,該方法簡單易行,占用資源少,但產(chǎn)生的種群多樣性有限,從而導致進化非常緩慢。實驗發(fā)現(xiàn),當初始種群中包含了更豐富的基因和基因片斷時,則在進化過程中,經(jīng)過交叉、變異等遺傳操作,將發(fā)生組合效應,能產(chǎn)生更多的模式,因此能提高搜索效率,更快地跳出局部最優(yōu)解。初始種群分布的均勻性能保證初始群體的多樣性和較豐富的模式,從而使算法能在全局范圍內(nèi)以較快的速度收斂,增加獲取全局最優(yōu)解的可能,從而提高算法的進化效率。為此,提出了基因空間均勻分布策略(GSBS:GeneSpaceBalanceStrategy),以提高初始種群基因的多樣性?？紤]到GEP特殊的染色體結構(染色體頭部可以出現(xiàn)函數(shù)符和終結符,尾部只能出現(xiàn)終結符),頭部可取到的基因符數(shù)大于尾部,故不能直接采用等概率的方式構造種群。為保證染色體的完備性和可靠性,通過構造一張基因符初始化概率均勻分布表指導種群的初始化工作。該表根據(jù)種群規(guī)模,按照均勻分布的原則,記錄每個基因位上不同基因符應出現(xiàn)的概率(或次數(shù))。為了方便描述,這里僅以單基因染色體群體的初始化為例,多基因染色體種群初始化的方法類似。例1設函數(shù)符集為F={+,-,*,/},終結符集為T={a,b},染色體頭長h=3,染色體尾長t=4,種群規(guī)模N=150,則各基因位出現(xiàn)相應基因符的概率如表1所示。根據(jù)表1和種群規(guī)模N得到各基因位出現(xiàn)相應基因符的次數(shù)如表2所示。在算法的開始,設置一個基因符在各基因位出現(xiàn)的計數(shù)矩陣M,初始化值全部為0。當每產(chǎn)生一個新個體時,就把該個體對應的基因位上的相應基因符的計數(shù)加1。如果增加的結果導致該基因符在該基因位的次數(shù)超過了基因符初始化出現(xiàn)次數(shù)均勻分布表中相應的數(shù)值,則把該基因符強變異為其他有效基因符,再檢查新變異得到的基因符是否符合上述規(guī)則,依此類推,直到得到恰當?shù)某跏紓€體。GSBS算法描述如下。算法1GSBS輸入:F,T,h,t,N,M。輸出:初始種群S。初始化基因符在各基因位出現(xiàn)的計數(shù)矩陣M;fori=1toN//N為種群規(guī)模{隨機產(chǎn)生一個個體;while(某基因符在某基因位的次數(shù)超過了基因符初始化出現(xiàn)次數(shù)均勻分布表中相應的數(shù)值)對該基因位上的基因符進行強變異;修正基因符在各基因位出現(xiàn)的計數(shù)矩陣M;}Return初始種群S。1.2個體間的顯著性海明距離和有效基因位在種群的進化過程中,保持種群的多樣性是GEP算法有效運行的前提。在種群規(guī)模一定的情況下,種群多樣性越大,種群越有可能產(chǎn)生出更優(yōu)子代,而一旦種群喪失多樣性,種群個體間越相互趨同,則過早收斂現(xiàn)象越容易發(fā)生。傳統(tǒng)的GEP算法雖然較遺傳算法效率提高了100～60000倍,但仍容易發(fā)生過早收斂。為了加快算法的收斂速度,必須使群體中的個體盡快向最優(yōu)解方向靠攏,而這樣做將不可避免地降低種群的多樣性,增加種群過早收斂的可能。因此,正確評價種群中個體分布的多樣性程度,以自適應地改變交叉和變異算子,對GEP算法性能的改進起著重要作用。在GEP中,一個個體就是一個染色體。為了評價種群中個體的差異,首先要定義個體的距離。為了簡化,這里只討論單基因染色體。考慮如下GEP環(huán)境。函數(shù)集F={+,-,*,/},終結符集T={a,b},頭長度h=4,設兩個GEP個體分別為+-abaabab(1)/-abbabba(2)+?abaabab(1)/?abbabba(2)在文獻中,提出了兩個GEP個體的海明距離,用來衡量個體間的差異度。定義1(GEP個體間的顯性海明距離)設GEP中個體的長度為l,GEP個體Ii和Ij之間的顯性海明距離為s(Ιi?Ιj)=l∑x=1(Ιxi⊕Ιxj)/l(3)s(Ii?Ij)=∑x=1l(Ixi⊕Ixj)/l(3)上述兩個個體的第1,5,8和9位置上的符號不同,因此個體1和個體2間的顯性海明距離s(I1,I2)=4/9。同樣考慮個體3和個體4a+abbabaa(4)/+abbabaa(5)a+abbabaa(4)/+abbabaa(5)它們分別對應的表達式樹如圖1所示。故得到個體3和個體4對應的表達式分別為a(6)(b+b)/a(7)a(6)(b+b)/a(7)雖然這兩個個體之間的顯性海明距離是1/9,然而它們對應的表達式卻相差很大,因此用個體間的顯性海明距離衡量個體間的差異度并不準確。因為染色體中某些基因位并沒有用于構建表達樹,即沒有被用于最終解碼。為此,引出定義2和觀察1。定義2(開放閱讀框)個體中用于最終解碼的有效基因位稱為開放閱讀框(ORF:OpenReadFrame)。觀察1個體間的顯性海明距離不能精確地反映個體間的差異,原因在于開放閱讀框ORF外的無效基因位加入了比較。個體4的ORF表示為a+abbabaa(8)a+abbabaa(8)個體5的ORF表示為/+abbabaa(9)/+abbabaa(9)ORF代表了個體的有效長度,個體3的有效長度為1,個體4的有效長度為5,因此,在定義兩個個體的相似性時,不應該比較ORF之外的基因位。定義3(基于ORF的個體海明距離)設個體Ii的ORF長度為li,個體Ij的ORF長度為lj,GEP個體Ii和Ij之間的基于ORF的海明距離sΟRF(Ιi?Ιj)=min(li?lj)∑x=1(Ιxi⊕Ιxj)/min(li?lj)(10)sORF(Ii?Ij)=∑x=1min(li?lj)(Ixi⊕Ixj)/min(li?lj)(10)基于ORF的個體海明距離的取值范圍介于[0,1]之間。0表示兩個個體完全一致,1表示兩個個體差異最大。通過這個定義可得個體3和個體4的基于ORF的海明距離sΟRF(Ι3?Ι4)=1(11)sORF(I3?I4)=1(11)顯然基于ORF的個體海明距離較顯性海明距離更有效地反映了個體之間的相似性。自適應遺傳算子的思想是:如果種群中個體間的海明距離總體偏低,說明種群中個體的相似度高,算法容易陷入局部最優(yōu)解,為了避免早熟而收斂到一個局部最優(yōu)解,應該增加種群的多樣性,提高交叉和變異的概率,以產(chǎn)生更多新的個體。然而,通過計算種群中所有個體兩兩之間的海明距離,獲得總體海明距離的方法計算量太大,效率較低。筆者采用在執(zhí)行交叉算子后進行計算方法,即在兩個個體進行交叉操作后,計算交叉后的兩個個體之間的海明距離,然后綜合考慮所有交叉后計算得到的海明距離,以判斷種群是否早熟。該方法利用個體交叉時一并計算兩個隨機個體的海明距離,以反映總體種群的早熟程度,避免了計算種群中所有個體兩兩間海明距離的過大計算量。同時,由于交叉算子的交叉概率一般在30%～70%,即種群中有60%和140%的個體(有重復個體)都計算了其之間的海明距離,因此能較好地反映種群總體的相似程度,以衡量種群的早熟程度。由此,定義了基于ORF的種群內(nèi)海明距離。定義4(基于ORF的種群內(nèi)海明距離)設由交叉產(chǎn)生的新個體的數(shù)目為N對,則經(jīng)過交叉抽樣得到的基于ORF的種群內(nèi)海明距離r=Ν∑k=1sΟRFk(Ιi?Ιj)Ν(12)其中Ii和Ij為每次交叉得到的兩個新個體。顯然,r∈[0,1],當種群中抽樣的所有個體都一樣時,r=0,當完全不一樣時,r=1,因此,r反映了GEP個體在種群中總的差異程度。利用評價種群過早收斂程度的指標基于ORF的種群內(nèi)海明距離r,提出自適應的交叉算子和變異算子ACMO(AdaptiveCrossoverandMutationOperators),使交叉概率Pc和變異概率Pm在進化過程中隨著r的增大而減小,表示為Ρc=exp(-k1r)2+0.5(13)Ρm=exp(-k2r)2(14)其中k1,k2>0,由于r始終大于或等于0,所以Pc取值范圍在[0.5,1]之間,Pm取值范圍在[0,0.5]之間,由式(13)、式(14)可見,在進化過程中,Pc和Pm根據(jù)r取值的不同進行動態(tài)地自適應調(diào)整:當種群個體趨于離散,即r變大時,Pc和Pm減小,種群的開發(fā)能力增強;當種群個體趨于收斂,即r變小時,Pc和Pm增大,種群的探測能力增強。自適應的交叉算子和變異算子ACMO算法描述如下。算法2自適應的交叉算子和變異算子ACMO輸入:當代種群S。輸出:自適應的交叉概率Pc和變異概率Pm。步驟:得到每次交叉操作后的兩個新個體Ii和Ij;根據(jù)式(10)計算兩個個體間的基于ORF的個體海明距離sORF(Ii,Ij);根據(jù)式(12)計算基于ORF的種群內(nèi)海明距離r;根據(jù)式(13)得到下代進化的自適應交叉概率Pc;根據(jù)式(14)得到下代進化的自適應變異概率Pm;返回Pc和Pm。1.3基于orf的個體海明距離,個體適應度最低為了增加種群多樣性,避免種群早熟收斂,在進化的過程中提出了淘汰算子(OBSO:ObsoleteOperator)。設d為基于ORF的個體海明距離的最小閾值,fmin為個體適應度最低的閾值。在1.2節(jié)中,每次交叉操作后,計算了兩個個體之間的基于ORF的海明距離。當兩個個體之間的海明距離小于閾值d,且適應度較低個體的適應度低于fmin時,將該個體加入淘汰池,因此淘汰池中的個體為種群中的重復且適應度較低的個體。相應的淘汰策略中,對前n個個體進行強變異,以替換淘汰池中的個體,也可直接產(chǎn)生新的個體替換淘汰池中的個體。其中,基于ORF的個體海明距離的最小閾值d和個體適應度最低的閾值fmin的設置應適中,如果閾值d和fmin太大,大量個體被淘汰,而需大量補充;反之,會保留大量雷同個體。1.4精英保留策略基于多樣化進化策略的基因表達式算法DS-GEP,通過綜合GSBS、ACMO以及OBSO等方法,對種群給予不同的進化策略,以保持個體間的多樣性,從而增強算法的尋優(yōu)能力。同時,Radolph證明了一般的遺傳算法不一定收斂,只有每代保存了最優(yōu)個體時才收斂,這同樣適用于GEP。為了保證算法的收斂性,加入了精英保留策略。DS-GEP算法具體表述如下。算法3DS-GEP輸入:樣本數(shù)據(jù)集Cases,算法初始參數(shù)。輸出:最優(yōu)解Best_Exp。步驟:使用算法1(GSBS)建立初始種群S;初始化最優(yōu)解Best_Exp;初始化遺傳操作代數(shù)m;While(m>0){執(zhí)行選擇算子;執(zhí)行精英保留策略Reserve(Best_Exp);執(zhí)行算法2自適應的的遺傳算子ACMO(S);執(zhí)行淘汰算子Obsolete(S);m=m-1;}ReturnBest_Exp。1.5復雜度mnk定理1設n為種群大小,m為總進化代數(shù),k為樣本集的長度。則DS-GEP算法的復雜度是O(m×n×k)。證明在DS-GEP算法中,計算個體對k個訓練樣本的復雜度為O(k),算法需計算種群中每個個體的適應度值,故種群適應度計算的復雜度為O(k×n),因算法需要進化m代,故算法的復雜度為O(m×n×k)。2數(shù)據(jù)集的挖掘實驗實驗平臺:CPU:IntelCore2Duo2.2GHz,內(nèi)存:2GByte,硬盤:320GByte,操作系統(tǒng):MSWindowsXP,編譯器:Eclipse。實驗模擬了3個函數(shù)的挖掘F1=πr2(15)F2=5x4+4x3+3x2+2x+1(16)F3=(1.0+x21+x22)2(√x21+x22+1.5)(17)上述3個函數(shù)分別代表了不同類型的函數(shù),常用于測試GEP算法挖掘性能,具有代表性和可比性。在實驗中,首先產(chǎn)生以上3個函數(shù)的訓練數(shù)據(jù)集,對每個函數(shù)的每個自變量分別隨機產(chǎn)生100個[0.00,20.00]之間的隨機數(shù)作為訓練的數(shù)據(jù)集的參數(shù)值,然后分別求出以上3個函數(shù)在各個參數(shù)值作為訓練數(shù)據(jù)集的目標值。對每個數(shù)據(jù)集重復100次挖掘實驗,最后取統(tǒng)計結果的平均值作為最后的實驗結果。算法中的基本原始參數(shù)設置如表3所示。對3個函數(shù)分別采用原始GEP算法,將GSBS、ACMO和OBSO單獨融于GEP算法和綜合所有策略的DS-GEP進行了挖掘實驗。5種方式中,進化到挖掘成功的平均代數(shù),挖掘成功的平均進化時間和挖掘成功率如圖2所示。圖2a表明,單獨采用GSBS、ACMO和OBSO策略雖然在個別函數(shù)上進化代數(shù)略微超過傳統(tǒng)的GEP算法,但總體上,減少了算法的進化到最優(yōu)個體的平均代數(shù)。當把3種策略綜合后,DS-GEP成功進化的代數(shù)明顯下降,成功進化的代數(shù)較傳統(tǒng)GEP算法