采用混合策略的改進基因表達式編程*

王超學，張婧菁，吳書玲

西安建筑科技大學 信息與控制工程學院，西安 710055

采用混合策略的改進基因表達式編程*

王超學，張婧菁+，吳書玲

西安建筑科技大學 信息與控制工程學院，西安 710055

WANG Chaoxue,ZHANG Jingjing,WU Shuling.Improved gene expression programming algorithm used by hybrid strategy.Journal of Frontiers of Computer Science and Technology,2017,11(1):163-170.

基因表達式編程（gene expression programming，GEP）是一種新型的進化算法，在函數發現領域具有很好的應用。針對傳統GEP存在的不足，提出了一種采用混合策略的改進基因表達式編程算法（improved gene expression programming algorithm used by hybrid strategy，HSI-GEP）。主要有兩點改進：（1）采用鏡像和重啟機制對種群中的較差個體進行替換，以提高種群的質量和多樣性；（2）在原有錦標賽選擇之前引入克隆選擇，以提高算法對優質解的開采能力。與權威文獻中改進的GEP算法關于函數發現問題的大量對比實驗表明，HSIGEP算法求解質量高，收斂速度快，具有明顯的競爭力。

基因表達式編程（GEP）；鏡像替換；重啟機制；克隆選擇

1 引言

基因表達式編程（gene expression programming，GEP）[1-2]由Ferreira在2001年提出，是進化算法的新成果。GEP繼承了遺傳算法（genetic algorithm，GA）與遺傳編程（genetic programming，GP）的優點，具有GA編碼、操作的簡潔性和GP求解復雜問題強有力的空間搜索能力，成為函數發現的有力工具，并且在機械工程、材料科學、醫學等領域取得了廣泛應用。如Kara[3]使用GEP建立了沒有箍筋的鋼纖維加強混凝土梁的切變強度的經驗模型，在預測鋼纖維加強混凝土梁的切變強度方面表現出了優勢。Traore等人[4]使用GEP建立了西非熱帶干旱地區的土壤水分蒸發蒸騰損失總量模型，與其他方法對比后發現GEP模型的精確度更高。

但是在實際應用中GEP依然存在著收斂速度慢，容易陷入局部最優的問題。目前，許多學者在函數發現領域對傳統的基因表達式編程算法進行不同程度的改進，主要有：林毅申等人[5]將小生境技術引入到GEP中，并將聚類分析與遺傳機制相結合來控制收斂的小生境數目，提高算法的全局尋優能力。姜玥等人[6]采用遠緣繁殖和動態適應度函數策略對種群的進化進行干預，增加了多樣性并且有利于選擇優質個體，提高了標準GEP的性能。莫海芳等人[7]采用GEP編碼的克隆選擇算法實現函數建模，提高解的質量的同時也提高了收斂速度。張永強等人[8]引入優質種群產生策略和變種群策略來提高算法的收斂速度和種群的多樣性。

為了進一步改善GEP的性能，本文提出了一種采用混合策略的改進基因表達式編程算法（improved gene expression programming algorithm used by hybrid strategy，HSI-GEP）。主要改進點如下：采用鏡像和重啟機制對較差個體進行替換，提高算法的全局搜索能力；在原有錦標賽選擇之前引入克隆選擇，提高算法對優質解的開采能力。為了驗證HSI-GEP算法的優越性，本文針對函數發現問題與權威文獻中改進的GEP算法進行了對比實驗。結果表明，HSIGEP算法在進化過程中能夠有效地克服停滯和早熟收斂現象，具有明顯的競爭力。

2 GEP簡介

GEP綜合了遺傳算法和遺傳編程的優點，具有更強的問題解決能力。GEP與二者的本質區別在于：在GA中個體由固定長度的線性串來表示，GP中個體由不同大小和形狀的非線性實體所表示，而GEP將個體先編碼為固定長度的線性串，再表示成大小和形狀都不同的非線性實體。

GEP算法可以定義為九元組：GEP={C,E,P0,M,φ,Γ,Φ,Π,Τ}。式中C為個體的編碼方式；E為個體適應度評價函數；P0為初始種群；M為群體規模；φ為選擇算子；Γ為重組算子；Φ為變異算子；∏為插串算子；T為遺傳運算終止條件。

標準GEP算法的操作流程如下[9]：（1）輸入相關參數，創建初始化群體；（2）計算每個個體的適應度函數，若不滿足終止條件，繼續下一步，否則結束；（3）保留最優個體；（4）選擇操作；（5）變異；（6）插串操作（倒串、IS插串、RIS插串、基因變化）；（7）重組操作（單點重組、兩點重組、基因重組）；（8）轉到（2）。

3 采用混合策略的改進基因表達式編程

本文提出的采用混合策略的改進基因表達式編程算法（HSI-GEP）流程圖如圖1所示。

3.1 適應度函數

統計學中，用于評價兩組數據符合程度的方法

更多是采用復相關系數法。本文的適應度函數為：

即統計學中的復相關系數的平方[10]。

其中，yj表示觀測數據；表示利用公式從觀測數據計算得到的yj的預測值；為變量y的平均值；SSE為殘差平方和；SST為總離差平方和。

Fig.1 Flowchart of HSI-GEP圖1 HSI-GEP算法流程圖

3.2 終止條件

在進化操作中，終止條件有多種判斷標準。例如適應度值達到最大值1，或者種群的迭代次數達到預先設定值。本文算法的終止條件采用的是最大迭代次數。

3.3 種群信息熵

種群多樣性代表種群中個體間的差異程度。多樣性是影響進化算法性能的關鍵因素。目前，評價種群多樣性的方法主要有適應度方差[11]、信息熵[12]、帶權的多樣性測度[13]等。信息熵是一種表示狀態多樣性和豐富程度的定量計量標尺。與其他方法相比，采用信息熵來評價種群的多樣性，能夠較容易地與種群中的個體相對應，更能夠客觀地反映其多樣性的含義，易于理解。

本文采用信息熵的方式來判斷種群多樣性的優劣。由信息熵的計算公式可知，當種群中的所有個體在同一基因位置上的等位基因各不相同時，種群的信息熵最大，個體間的差異度最大，此時種群的多樣性最好。衡量種群多樣性的信息熵的具體計算方式如下：

（1）統計出第i個函數符或終止符在種群的同一基因位置j上出現的次數Cij。

（2）求出第i個函數符或終止符在該種群的同一基因位置j上出現的概率Pij：

（3）計算種群的信息熵：

其中，L為每個個體的基因位置的總數，即每個個體的總長度；S為函數符和終止符的總數。

3.4 鏡像和重啟機制

在進化過程的初期，種群的多樣性比較高，但隨著迭代次數的增大，種群中的多樣性就會降低。依據這個思想，本文把種群多樣性的判斷分為3個階段，并且設定不同的閾值。當種群的多樣性低于預先設定的閾值時，就采用鏡像和重啟機制替換掉部分較差的個體，提高種群多樣性，增強空間搜索能力。具體操作步驟如下所示：

（1）分別計算理想種群和當前種群的多樣性熵值，記為Hl和Hp。

（2）根據種群的最大迭代次數MaxGene，設置3個多樣性判斷階段，分別為1～MaxGene/3、MaxGene/3～2×MaxGene/3、2×MaxGene/3～MaxGene，對應的種群閾值h可以分別設定為0.5、0.4、0.3。如果Hp＜h×Hl，則對當前種群進行鏡像和重啟操作。

（3）依據適應度把種群中的個體進行排序，然后選出適應度最差的m個個體和次差的n個個體。

（4）采用重啟機制，即隨機產生m個個體替換掉適應度最差的m個個體；采用鏡像機制，即對適應度次差的n個個體進行鏡像處理。鏡像處理實際上是對于每一個個體中的函數符用其相對應的鏡像函數符來替換。例如，functionSet={+，-，*，/，Sin，Cos，ln，exp}，則該函數符集合的鏡像函數符集合為mirrorfunctionSet={-，+，/，*，Cos，Sin，exp，ln}。

3.5 選擇算子

克隆選擇算法的實質是先通過克隆繁殖優良個體，進而通過變異對其鄰近區域進行搜索，從而選擇出更優的個體。因此克隆選擇具有收斂速度快，搜索精度高的特點。而錦標賽選擇在一定程度上，也能避免過早收斂和停滯現象的發生。精英個體是種群進化到當前為止算法搜索到的適應度值最高的個體，它具有最好的基因結構和優良特性。精英策略就是算法在進化過程中，保證迄今出現的最優個體不會被選擇、交叉和變異操作所丟失和破壞。本文在原有錦標賽選擇之前引入了克隆選擇，提出帶有精英策略的混合選擇操作。具體如下：

（1）根據個體的適應度從父本種群中選擇最優的a%的個體。

（2）把選擇的a%的個體均克隆b次，并對這些克隆后的個體進行變異操作。

（3）計算被選擇的父本和變異后子代的適應度。如果某一個子代個體的適應度大于其父本和兄弟的適應度，則該子代個體將被選入下一代種群中；反之，則不選入?？寺∵x擇后，被選擇進入到下一代的克隆個體數量c最多等于被克隆的a%的個體數量[14]。

（4）采用競賽規模為s的錦標賽選擇算子從父本種群中選擇剩余的N-c個個體，以滿足種群規模N。

（5）找出該代中適應度最好的個體pbest，與目前為止保存的適應度最好的個體pmax進行比較，如果適應度pbest＞pmax，則用pbest對pmax進行更新；反之，則用pmax替換掉該代中適應度最差的個體。這樣做的目的是保證最好的個體能夠進入種群，參與各種遺傳操作。

3.6 HSI-GEP算法機理分析

本文首先采用鏡像和重啟機制替換種群中的部分較差個體，向種群中引入一些新的個體和鏡像個體，提高了種群的質量和多樣性，進而提高了算法的全局搜索能力。其次引入了帶有精英策略的混合選擇操作，兼顧了算法的全局搜索和局部搜索，使得算法可以在優質解的區域展開更精細的局部搜索，縮短了尋優時間，提高了算法的收斂速度和對優質解的開采能力。

選擇算子是進化算法中重要的算子，體現了自然界中優勝劣汰的基本規律，直接影響進化算法的性能。算法的收斂性是由選擇算子來保證的?？寺∵x擇算法是人工免疫算法的一種，文獻[15]已經證明了該算法的收斂性。錦標賽選擇是進化算法中常見的選擇算子，可以在一定程度上保證算法的收斂性。文獻[16]也已經證明了帶有精英策略的GEP算法在函數發現中的全局收斂性。本文把克隆選擇算法的思想與錦標賽選擇結合起來，組成混合選擇算子，在提高算法收斂速度的同時，并沒有影響原來算法的收斂性。同時，帶有精英策略的混合選擇操作進一步保證算法在理論上以概率1收斂到全局最優解。

4 實驗和結果

本文設計了兩個實驗來驗證HSI-GEP算法在函數發現領域的有效性和競爭力，實驗的運行參數設置見表1。實驗程序使用Matlab 2009a實現，實驗環境為Windows 7操作系統，Intel Core i7 3.40 GHz處理器，4 GB內存。

4.1 HSI-GEP算法的有效性實驗

Ferreira在文獻[1]中采用的F函數具有自變量個數少，維度高的特點，多次出現在各個權威文獻中，具有一定的對比價值。為了評價HSI-GEP算法各因子的影響效果，本文采用F函數來驗證HSI-GEP算法的有效性，具體公式如式（5）所示。

其中，an是由非負整數組成的，an=0,1,2,…。實驗中，首先根據F函數隨機產生10組訓練樣本數據集，然后利用HSI-GEP算法對樣本數據集進行挖掘，得到反映其規律的函數表達式，再利用訓練樣本數據的自變量，根據挖掘出的函數表達式求出其目標值。對數據集重復50次挖掘實驗，最后將實驗結果與標準GEP算法和文獻[17]中的DS-GEP算法進行對比。實驗1的測試結果如表2所示。

Table 1 Parameter setting of experiments表1 實驗中算法的運行參數

Table 2 Test results of experiment 1表2 實驗1測試結果

從表2中可以看出，HSI-GEP算法的尋優率和平均收斂代數明顯優于DS-GEP和GEP算法。為了驗證選擇算子的有效性，在滿足其他條件都相同的情況下，本文做了兩個對比實驗：一個實驗采用普通的錦標賽選擇算子；另一個采用本文的選擇算子。圖2和圖3分別為二者的進化曲線圖，圖中紅色實線代表最優適應度值，藍色虛線代表平均適應度值。

Fig.2 Evolution curve of experiment with tournament selection圖2 帶錦標賽選擇的進化曲線圖

Fig.3 Evolution curve of experiment with selection operator in this paper圖3 本文選擇算子的進化曲線圖

從圖2和圖3中可以明顯看出，由于該函數比較簡單，二者都可以達到全局最優。但是在錦標賽選擇之前加入克隆選擇后，算法取得最優解的收斂代數明顯減小。圖3在不到20代時就已經達到最優，說明了引入克隆選擇后能明顯提高種群的收斂速度。

信息熵是衡量種群多樣性的標志，信息熵與種群多樣性成正比。從圖4加鏡像和重啟機制前后信息熵對比曲線圖可以看出，隨著進化代數的不斷加大，種群的信息熵逐漸減小，加入鏡像和重啟機制后，種群的信息熵明顯提高。這說明引入鏡像和重啟機制能夠明顯提高種群的多樣性，這也是HSI-GEP算法能夠達到全局最優的原因。

Fig.4 Comparison of information entropy before and after using mirror and reset mechanism圖4 加鏡像和重啟機制前后信息熵對比圖

4.2 HSI-GEP算法的先進性實驗

為了測試HSI-GEP算法的先進性，本文選取最新文獻DS-GEP[17]、S-GEP[18]、MDC-GEP[19]、DG-GEP[20]中的算法進行對比測試。測試函數與文獻[18-19]相同。具體函數表達式如式（6）～（15）所示。運行時參數設置見表1。實驗測試結果見表3。

Table 3 Test results of experiment 2表3 實驗2結果統計表

從表3中可以看出，與DS-GEP、MDC-GEP、SGEP、DG-GEP算法相比，HSI-GEP算法對于大多數函數，最大適應度、最小適應度和平均適應度都有明顯的提高，說明了HSI-GEP算法的先進性和競爭力。對于較為簡單的函數F2和F6，HSI-GEP算法能夠達到最大適應度值1，但是F3、F5、F10函數的部分值卻小于（非常接近）MDC-GEP算法。這是因為GEP算法本身是一種隨機算法，且算法的運行代數、性能參數等都對實驗有很大的影響，每個函數取得最優值所依賴的運行代數和性能參數都會不同，所以在算法的性能參數相同的條件下，少數函數取不到更優解的情況是存在的。

5 結束語

本文對標準GEP算法進行改進，提出了一種采用混合策略的改進基因表達式編程算法，并通過函數發現問題來驗證該算法的有效性和競爭力。文中提出了兩個改進點：首先，針對自然進化過程中由于種群多樣性缺失導致的早熟收斂現象，通過鏡像和重啟機制替換掉部分較差個體，以增加種群的質量和多樣性，提高算法的全局搜索能力。其次，在錦標賽選擇之前引入了克隆選擇，進一步在優質解的搜索區域中展開更精細的局部搜索，提高了對優質解的開采能力。通過與權威文獻中改進的GEP算法關于函數發現問題的大量對比實驗表明，改進后的HSI-GEP算法具有明顯的競爭優勢。

雖然HSI-GEP算法在本文的兩次實驗中均表現了優越的性能，但還是存在一定的問題，例如少數函數取不到更優解，算法參數的合理性選擇，測試問題領域比較局限等。因此，優化算法的性能參數和擴大測試問題領域將是未來研究的重點。

[1]Ferreira C.Gene expression programming:a new adaptive algorithm for solving problems[J].Complex Systems,2001, 13(2):87-129.

[2]Ferreira C.Function finding and the creation of numerical constants in gene expression programming[M]//Advances in Soft Computing.London:Springer,2003:257-266.

[3]Kara I F.Empirical modeling of shear strength of steel fiber reinforced concrete beams by gene expression programming[J]. Neural Computing&Applications,2013,23(3/4):823-834.

[4]Traore S,Guven A.New algebraic formulations of evapo transpiration extracted from gene-expression programming in the tropical seasonally dry regions of west africa[J].Irrigation Science,2011,31(1):1-10.

[5]Lin Yishen,Peng Hong,Wei Jia.Function finding in niching gene expression programming[J].Journal of Chinese Computer Systems,2008,29(11):2111-2114.

[6]Jiang Yue,Tang Changjie,Zheng Xiuming,et al.Outbreeding strategy with dynamic fitness in gene expression programming[J].Journal of Sichuan University:Engineering Science Edition,2007,39(2):121-126.

[7]Mo Haifang,Kang Shun.Clonal selection algorithm with GEP code for function modeling[J].Pattern Recognition andArtificial Intelligence,2013,26(9):878-884.

[8]Zhang Yongqiang,Xiao Jing.Anew strategy for gene expression programming and its applications in function mining [J].Universal Journal of Computer Science&Engineering Technology,2010,1(2):122-126.

[9]Yuan Chang'an,Peng Yuzhong,Qin Xiao,et al.The principle and application of gene expression programming algorithm[M].Beijing:Science Press,2010:30-33.

[10]Zuo Jie.Gene expression programming core technology research[D].Chengdu:Sichuan University,2004.

[11]Shan Bing,Ni Shihong,Zha Xiang.GEP based on population diversity measure by variance of individuals’fitness[J]. Computer Engineering and Design,2013,34(9):3094-3098.

[12]Shen Huihui,Han Shenglian.A method to calculate the immune algorithm diversity and affinity[J].Journal of Chongqing Vocational&Technical Institute,2004,13(4):125-126.

[13]Li Taiyong,Tang Changjie,Wu Jiang,et al.Adaptive population diversity tuning algorithm for gene expression programming[J].Journal of University of Electronic Science and Technology of China,2010,39(2):279-283.

[14]Liu Y C,Hsieh J C.A hybrid selection algorithm for time series modeling[J].Soft Computing,2014,19:1-11.

[15]Yu Ying,Hou Chaozhen.Convergence analysis of clonal selection algorithm[J].Computer Application Research,2006, 23(6):96-98.

[16]Yuan Chang'an,Tang Changjie,Zuo Jie.Function mining based on gene expression programming—convergency analysis and remnant-guided evolution algorithm[J].Journal of Sichuan University:Engineering Science Edition,2004,36 (6):100-105.

[17]Wang Chaoxue,Zhang Kai,Dong Hui,et al.Double systemgene expression programming and its application in function finding[C]//Proceedings of the 2014 International Conference on Mechatronics,Control and Electronic Engineering,Shenyang,Aug 29-31,2014:357-361.

[18]Peng Yuzhong,Yuan Chang'an,Qin X,et al.An improved gene expression programming approach for symbolic regression problems[J].Neurocomputing,2014,137(15):293-301.

[19]Xuan Shibin,Liu Yiguang.GEP evolution algorithm based on control of mixed diversity degree[J].Pattern Recognition andArtificial Intelligence,2012,25(2):187-194.

[20]Liu Qihong,Tang Changjie,Hu Jian.Gene expression programming based on diversity-guided grading evolution[J]. Journal of Sichuan University:Engineering Science Edition,2006,38(6):108-113.

附中文參考文獻：

[5]林毅申,彭宏,韋佳.小生境基因表達式編程在函數發現的研究[J].小型微型計算機系統,2008,29(11):2111-2114.

[6]姜玥,唐常杰,鄭明秀,等.基因表達式編程中動態適應的遠緣繁殖策略[J].四川大學學報:工程科學版,2007,39 (2):121-126.

[7]莫海芳,康順.采用GEP編碼的克隆選擇算法實現函數建模[J].模式識別與人工智能,2013,26(9):878-884.

[9]元昌安,彭昱忠,覃孝,等.基因表達式編程算法原理與應用[M].北京:科學出版社,2010:30-33.

[10]左劼.基因表達式編程核心技術研究[D].成都:四川大學, 2004.

[11]單兵,倪世宏,查翔.基于適應度方差度量種群多樣性的GEP算法[J].計算機工程與設計,2013,34(9):3094-3098.

[12]沈慧慧,韓生廉.免疫算法多樣性及親和性的一種計算方法[J].重慶職業技術學院學報,2004,13(4):125-126.

[13]李太勇,唐常杰,吳江,等.基因表達式編程種群多樣性自適應調控算法[J].電子科技大學學報,2010,39(2):279-283.

[15]于瀛,侯朝楨.一種克隆選擇算法的收斂性分析[J].計算機應用研究,2006,23(6):96-98.

[16]元昌安,唐常杰,左劼.基于基因表達式編程的函數挖掘——收斂性分析與殘差制導進化算法[J].四川大學學報:工程科學版,2004,36(6):100-105.

[19]宣士斌,劉怡光.基于混合差異度控制的基因表達式編程[J].模式識別與人工智能,2012,25(2):187-194.

[20]劉齊宏,唐常杰,胡建.多樣性制導分段進化的基因表達式編程[J].四川大學學報:工程科學版,2006,38(6):108-113.

WANG Chaoxue was born in 1967.He received the Ph.D.degree in computer science from Xi'an University of Technology.Now he is a professor at Xi’an University of Architecture and Technology,and the member of CCF.His research interests include artificial intelligence and data mining.

王超學（1967—），男，陜西西安人，西安理工大學計算機科學專業博士，現為西安建筑科技大學教授，CCF會員，主要研究領域為人工智能，數據挖掘。

ZHANG Jingjing was born in 1990.She is an M.S.candidate at Xi’an University of Architecture and Technology. Her research interest is intelligent software development.

張婧菁（1990—），女，山西運城人，西安建筑科技大學信息與控制工程學院碩士研究生，主要研究領域為智能軟件開發。

WU Shuling was born in 1991.She is an M.S.candidate at Xi’an University of Architecture and Technology.Her research interest is intelligent modeling and forecasting.

吳書玲（1991—），女，河南駐馬店人，西安建筑科技大學信息與控制工程學院碩士研究生，主要研究領域為智能建模及預測。

Improved Gene Expression ProgrammingAlgorithm Used by Hybrid Strategy*

WANG Chaoxue,ZHANG Jingjing+,WU Shuling
School of Information and Control Engineering,Xi’an University ofArchitecture and Technology,Xi'an 710055,China
+Corresponding author:E-mail:494945856@qq.com

Gene expression programming(GEP)is a new evolutionary algorithm,which has the very good applications in the field of function finding.In view of the insufficiency of traditional GEP,this paper puts forward an improved gene expression programming algorithm used by hybrid strategy(HSI-GEP).This paper has two improvements:(1)Using mirror and reset mechanism to replace the worst individuals of population,to improve the quality and diversity of population;(2)Introducing the clonal selection before tournament selection operator in order to improve the mining ability of algorithm about high qualities.A large number of experiments have been carried on the function finding problems,and the results show that the algorithm is of high quality,has fast convergence rate and obvious competitiveness compared with the improved GEP in authoritative literature.

gene expression programming(GEP);mirror replace;reset mechanism;clonal selection

A

：TP311

10.3778/j.issn.1673-9418.1509046

*The National Natural Science Foundation of China under Grant No.31170393(國家自然科學基金);the Natural Science Foundation of Shaanxi Province under Grant No.2012JM8023(陜西省自然科學基金).

Received 2015-09,Accepted 2016-02.

CNKI網絡優先出版:2016-02-03,http://www.cnki.net/kcms/detail/11.5602.TP.20160203.1126.002.html