一種新型的ＧＥＰ算法及應用研究

摘 要：提出一種適合于GEP表達式樹構造的新方法，以及相應的新解碼方法(GPED)。通過實驗對比，GPED可大大縮短演化時間。提出一種新的算法GPEP，將GPEP應用于碎石樁復合地基承載力預測，結果表明GPEP算法在預測精度和演化效率上均超過遺傳神經網絡、GP等算法。

關鍵詞：基因表達式編程; 遺傳程序設計; 解碼; 預測

中圖分類號：TP18文獻標志碼：A

文章編號：1001-3695(2007)06-0098-03

0 引言

在進化計算家族中，遺傳算法(GA)［1］用固定長度的線性串表示個體。由于遺傳操作簡單，目前已廣泛應用于各行各業的優化組合、圖像處理、機器人等問題中；但卻喪失了功能的復雜性［2］。在遺傳規劃(GP)［3，4］中，個體是長度和形狀不同的非線性實體（分裂樹），所以能夠表示復雜問題而被應用于復雜函數建模、時間序列預測等領域；但遺傳操作復雜、演化時間長。基因表達式編程(GEP)［2，5，6］則將個體編碼成固定長度的線性串（基因組或染色體），然后將其轉換為不同長度和形狀的非線性實體（表達式樹），從而實現了用簡單編碼表示復雜問題，同時易于遺傳操作，并且通過遺傳操作所產生的新個體在語法上都是有效的，不需要對新個體進行有效性判斷和處理，在速度上比GP提高了2－4個數量級。但GEP在將染色體串表示成表達式樹，再遍歷表達式樹（通常是求后綴表達式，也稱逆波蘭式）來計算適應度值過程中，由于樹的構造和遍歷操作非常耗時，大大影響了算法的效率。對此，本文提出了一種新的染色體解碼方法（Gene Postfix Expression Decoding，GPED）。該方法只需對染色體作簡單處理，即可直接得到染色體相對應的后綴表達式，不需要構造和遍歷表達式樹，可進一步提高演化效率。文中給出了GPED的有關性質證明，以及與其相對應的表達式樹的另一種構造方法。在GPED基礎上，提出了一種新的GEP算法GPEP(Gene Postfix Expression Programming)。

1 GEP中染色體基因和表達式樹的互相轉換 

GEP的基因由頭部和尾部構成。頭部可以含有函數符號和終端符號，而尾部只包含終端符號。在具體問題中，頭部長度h是根據求解問題的復雜度而選定的；而尾部長度t則由式（1）計算得到。其中n是帶有最多參數的函數的參數個數。

從左到右逐個讀取該基因中的字符。根據其語義，按層次順序構成表達式樹(ET)［2］，如圖1所示。對于給定的表達式樹，按從上到下、從左到右的順序層次遍歷ET中的節點，得到的符號序列即為基因編碼的有效部分，如遍歷圖1中的表達式樹可得到序列CS*a/eb。

2 一種新的GEP解碼方法和對應表達式樹構造方法及其優點

在GEP中，要計算個體適應度值，就必須將個體染色體或基因組轉換為表達式樹；然后遍歷表達式樹得到相應的函數式；最后根據適應度函數計算適應度值。通常的做法就是后序遍歷表達式樹得到后綴表達式，如圖1中表達式樹的后綴表達式為aeb/*SC。這樣就可以由后綴表達式計算表達式值。由于要進行大量的構造樹和遍歷樹操作，成為影響GEP算法效率的瓶頸。本文提出一種新的針對GEP基因的解碼方法。

定義1(基因后綴表達式解碼) 下述過程稱為基因后綴表達式解碼。首先，設置一個計數量nCount并初始化為1。從左到右逐個讀取基因中的字符，按下列規則改變nCount的值，直到nCount為0。

性質1 對任意一個有效的GEP，即GEP的頭部和尾部滿足式(1)，基因后綴表達式解碼掃描完基因串之前，計數量nCount必定已等于0。

性質1保證了絕不會出現當基因后綴表達式解碼掃描完基因串后，nCount 的值還不為0的情況。

下面介紹一種新的表達式樹構造方法。過程如下：基因的首字符對應樹的根節點；從左到右逐個讀取基因串的字符，并按照從右到左、深度優先的順序構造表達式樹，直到樹中所有葉節點都是終端字符。與GEP一樣，每個函數節點連接的子分支數目為該節點的參數個數，而終端字符節點只作為葉節點。以式(2)為例，用新方法構造的表達式樹如圖2所示。按照從右到左、深度優先的順序遍歷該表達式樹，即可得到基因的有效編碼部分，如按這種方法遍歷圖2中的表達式樹得到CS*a/eb。它正是式(2)的基因有效編碼部分。為了與GEP中的表達式樹區別，將這種新方法構造的樹稱為后綴表達式樹 (Postfix Expression Tree，PET)。

性質2 任意一個有效的GEP基因通過基因后綴表達式解碼得到的都是一個在語義上合法的后綴表達式。

證明 由PET的構造過程可知，若函數的參數個數為n，則該函數節點有n個分支，即該節點的出度為n。當節點不為根節點時，函數節點和終端節點入度均為1；當為根節點時，入度均為0。為了統一，不妨設一個虛節點指向PET的根節點，這樣每個節點不管其是不是根節點，其入度均為1。構造PET時設置一個計數變量nCount，每增加一個新節點時，nCount加上新節點的出度數并減去新節點的入度數。因為虛節點出度為1，所以令nCount初始值為1。如果新節點為函數節點，則出度為n，入度為1，所以nCount要加上n-1；如果新節點為終端節點，則出度為0，入度為1，所以nCount應減去1。而樹中所有節點的出度之和等于入度之和，所以當nCount為0時，PET樹將構造完畢。一個PET的構造步驟與GPED步驟是一一對應的。根據PET的構造過程可知，PET的后序遍歷結果即PET的后綴表達式，剛好是基因有效編碼部分的逆序。而PET在語義上代表一個合法的數學或邏輯表達式，因此得到的后綴表達式也必定是一個合法的表達式。證畢。

從上面可以看到，基因后綴表達式解碼也同樣能將一個基因表達成一種新的表達式樹。作為基因的表現性，并且任何一個GEP表達式樹，均可以通過變換得到一個語義相同（對符號回歸問題即同一函數）而形狀不同的PET 樹，因此基因表示問題的能力和算法性能不會改變。但是，通過GPED可以由基因串直接得到PET樹的后綴表達式，而無須構造和遍歷表達式樹。將新解碼方法應用于GEP算法，可望比原解碼方法具有更高的效率。這正是GPED的優越性所在。下面將通過實驗驗證。

3 基于GPED的GEP算法及與基本GEP算法比較

本文將基因后綴表達式解碼與基本GEP算法［2］相結合，提出一種新的算法GPEP。為了驗證GPED的效率，GPEP采用與基本GEP一樣的算法流程、參數設置，具體參見文獻[2，5]。GPEP與GEP不同的是基因解碼方法（表達式樹的構造方法），以及個體的表現型。用文獻[2]中SI問題來驗證。SI問題是一個符號回歸問題，文獻[2]用N=5n4+4n3+3n2+2n+1來產生10個樣本［2］，然后在這些樣本上通過GEP演化發現一個好的函數來擬合。由于這些樣本不含噪聲，可以通過演化得到精確解(即每次獨立運行找到的最優解剛好是上式)，用成功率作為衡量算法性能的精確尺度。表2給出了GPEP與GEP的比較。對于參數的不同設置，用GPEP和GEP各獨立運行20次（本文所有實驗均在P4 2.4GHz的PC機上運行）。

可見GPEP表示問題的能力和搜索效率，與GEP相比并不會降低；然而由于GPEP算法采用了GPED方法，無須頻繁構造和遍歷樹操作，在同樣條件下演化時間大大降低。當問題越復雜，群體規模、演化代數、基因頭長、基因個數等參數越大時， GPEP的演化效率就越明顯。

為了進一步增強GPEP算法在實際問題中的求解精度和演化效率，對其作如下改進：遺傳操作只選用多點重組、IS變換、倒置和變異四種算子。多點重組指當染色體由多個基因組成時，對每個基因均進行單點重組。這樣m個基因的染色體就進行m點重組。為降低選擇壓力，保持種群多樣性，新算法中采用每個個體只與其兒子競爭的選擇機制。當一個個體通過遺傳操作產生一個新個體時，如果新個體的適應度大于父個體，則替換父個體。另外，算法采用鄰域變異搜索來提高局部搜索能力。為了提高初始解的質量，先生成五倍于群體規模N的個體，按適應度選取較大的前N個個體作為初始群體演化。這樣可以加快收斂速度，提高演化效率。對于實際應用中的復雜問題，為了克服最優解停滯（演化很多代都沒找到更好解），本算法采用突變算子［7］對群體中部分適應度低的個體進行再生。但過多使用這種突變算子，不僅增加了計算開銷，也破壞了進化的穩定性，即優良的或有潛力的個體可能被破壞掉，所以本文設定一閾值MAXNO。當最優個體沒有更新的代數超過MAXNO時，對群體進行排序，選擇適應度小于10%的個體進行突變。實驗證明，這種改進是有效的。GPEP算法描述如下：

4 基于GPED的GPEP在碎石樁復合地基承載力預測中的應用

碎石樁復合地基是目前處理軟弱地基常用的方法之一。由于地基土的物理、力學性能比較復雜，碎石樁復合地基承載力的計算公式還無法確定。用改進遺傳神經網絡［8］和GP方法［9］雖然提供了預測碎石樁復合地基承載力較為有效的途徑，但精度仍不盡如人意。本文利用上面的新算法GPEP對文獻[8，9]中的數據進行演化建模，并與GAANN和GP的結果進行比較。GPEP函數集取{+，-， *， /， Ln， Exp， Sqrt， Pow10， Sin， Cos，Tan}，變量集合(表3)取{a，b，c，d，e，f，g，x，y，z}。參數設置：群體大小為200，演化代數為5 000，基因頭長為15，基因個數為7，表達式樹用+連接，IS變換概率為0.5，倒置概率為0.5，變異概率為0.01。以15個樣本中前13個作為訓練數據（表3前13行），后2個作為檢驗樣本（表3最后2行）。

從表3中可以看出，無論是訓練樣本還是檢驗樣本，GPEP得到的模型計算的相對誤差都要遠小于GP模型得到的相對誤差。表4進一步將GPEP預測結果與GA_ANN［8］、GP［7］以及錢鴻縉計算方法［8］的預測結果作了比較。結果顯示GPEP的預測精度均高于這些方法。

用GPEP得到的模型為

5 結束語

本文分析了GEP中染色體由基因串到表達式樹解碼過程的不足，提出了表達式樹的另一種構造方法，以及與之對應的新解碼方法GPED，并對有關定義和性質作了詳細探討。新解碼方法的優點在于：它在評價個體適應度時不必構造和遍歷表達式樹，大大節約了演化時間。本文通過實驗證明了在同樣參數條件下這種新方法的速度比GEP快一倍左右。最后，將該方法應用于GEP中，并從初始群體生成、選擇策略、遺傳算子等方面作了新的改進，提出了一種新的算法GPEP。通過在碎石樁復合地基承載力預測中的應用，GPEP算法的演化精度要大大高于遺傳神經網絡、GP等算法。由于GPEP算法事先不需要專業領域的知識和影響基因變量各要素之間的關系，演化精度較高且簡單有效，適合于復雜問題的預測，值得進一步研究和應用。

本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。