自適應基因表達式程序設計研究及應用

賈麗媛，張弛

(湖南城市學院 信息科學與工程學院，湖南 益陽，413000)

基因表達式程序設計(Gene expression programming，GEP)是 Ferreira[1]提出的一種基于基因型(Genome)和表現型(Phenomena)的新型遺傳算法。GEP的個體是由多個長度固定不定的基因組成的線性串，然后，這些個體被表示成表達式樹(Expression trees,ET)。它綜合了 Genetic algorithm (GA)和 Genetic programming(GP)的優點，具有染色體簡單、線性和緊湊、易于進行遺傳操作等到優點。 它在符號回歸、分類和時間序列問題預測中得到廣泛應用[2-6]，成為一個非常有力的數據挖掘工具。染色體由若干個基因(Gene )通過連接運算符連接組成。Gene由頭部(hail)和尾部(tail)組成，hail包含了函數集(Op)和終結符集(Data)元素。設頭部長度為h，尾部長度為t，函數中的最大目數為n。

向量xi用于存貯函數集Op和終結符集Data向量的元素，其存貯形式為：

其中：Di∈data；i=1，2，…，m；Pi∈Op ，i=1，2，…，k；Data和Op集合的個數為m+k；數據集Data的個數為m；單基因染色體長度gene_len為h+1。

為方便差分操作向量xi中的m維Data向量，它們用二維數組D[NP][m]保存(其中：NP為種群個數)。

GEP進化過程與傳統的遺傳算法[2]很相似，每一代通過遺傳算子(選擇算子、變異算子、倒位算子、重組、變換算子)進化。文獻[3]描述了GEP算法的基本框架。

在GEP算法中，根據適應度函數選擇出的雙親基因非常接近，因而所產生的后代相對雙親也必然比較接近，所期待的改善程度就較小，這樣，基因模式的單一性不僅減慢進化歷程，而且可能導致進化停滯，過早收斂于局部最優點，導致算法搜索性能不高。

1 自適應基因表達式程序設計(AGEP)

1.1 基于差分突變的搜索技術

差分演化算法(Differential evolution，DE)是Strom和Price[7]共同提出的，是一種快速的演化算法。它采用實數編碼，并利用個體間的差分信息來引導搜索產生新個體。對于差分演化算法，為了區分其方法，使用符號“DE/a/b/c”。其中：DE為算法；a為突變的向量(可以是隨機或最佳向量)；b為差分向量的個數；c為指交叉方案(二項式或指數)。變異策略“DE/rand/1”是一個經典的戰略[7]，按下列方式產生中間向量vi：

在方程(2)中，r1，r2，r3∈{ 1，…，NP}；r1≠r2≠r3≠i；xr2-xr3為差分向量，在進化過程中，它能夠自適應地調整搜索方向和搜索步長；F為縮放因子。然而，若能夠更多地啟發式控制搜索方向，則差分進化性能可以明顯提高。為此，提出一個新的搜索技術。獲得di,j的方法如下：

其中：di,j為第i個目標向量的第j維搜索向量；sign(·)為向量的搜索控制符號函數，同時randint∈{1，0，1 }意味著di，j從{-1，0，1 }中隨機生成。di,j=1表明從正方向搜索，di,j=-1表明從負方向搜索，di,j=0表明仍停留在它的基向量第 j維方向；ui為目標向量的試驗向量(不同于 xi)。式(3)表明：當試驗向量優于其目標向量時，將獲得好的搜索方向；若試驗向量劣于其目標向量，則下一代搜索方向相反。結合di為目標向量的搜索向量，修改式(2)如下：

為了控制 GEP的搜索方向，對每個目標向量的Vi采用方程(4)方法進行。注意向量Vi中第j維的搜索向量di,j初始化值取集合{1，0，1}中元素。

1.2 混沌(Logistic映射)重組和變異算子

傳統的基因重組和變異操作在算法整個搜索過程中都保持不變，這不利于算法性能的提高。為此，把混沌理論運用到基因重組和變異操作中，通過混沌序列動態地控制基因重組和變異操作，將提高基因重組和交叉操作的效率。在初始階段，適應度低于平均適應度，說明該個體性能不好，對它采用較大的基因重組概率pr和變異概率pm；在后期階段，適應度高于或接近平均適應度，說明該個體性能優良，對它采用較小的pr和pm。利用Logistic映射作為混沌信號發生器，產生一個迭代序列[8]，pr序列初始、中期和后期階段分別在[0.5，0.7]，[0.3，0.5]和[0.1，0.2]之間變化，pm序列初始、中期和后期階段分別在[0.06，0.07]，[0.03，0.06]和[0.02，0.03]之間變化。同時，也用混沌序列來控制基因重組點和變異點的選擇。

1.3 災變算子

GEP算法的局部搜索能力較強，但是，很容易陷入局部極值。災變的思想是[9]：在進化過程中，往往有前途的個體(全局是最優個體)適應度小于當前最佳適應度，容易被淘汰。所以，要跳出局部極值就必須殺死當前部分優秀個體，從而讓遠離當前極值的點有充分的進化余地。在種群適應度保持在穩定值一段時間后，發生災變，殺掉最優秀的個體，這樣才可能產生更優秀的物種。AGEP進行災變時用災變倒計數的概念，倒計數的長度取決于進化的速度，進化速度越慢，倒計數長度越長。當倒計數完畢還沒有新的最優值時，便認為局部搜索已經充分，就發生災變[10-15]。若若干次災變后產生的個體的適應度與沒災變前的一樣，則停止災變。

1.4 算法設計

算法如下：

PROCEDURE AGEP算法

Begin

隨機初始化種群P(0)，同時初始化dij；

計算P(0)中個體xi的適應度；

t:=0；

repeat；

按式(10)執行差分突變搜索產生中間個體vi，組成P(t)一部分；

執行混沌重組、變異操作來重組P(t)；

執行IS和RIS變換操作來重組P(t)；

計算P(t) 中個體的適應度；

根據選擇策略從 P(t) 中選擇生成下一代父體P(t+ 1)；

執行災變操作

t:= t+ 1；

until 滿足停止條件；

用P(t)中的最好個體進行系統預測；

End

2 實驗及結果

2.1 實驗參數設置

針對本文改進的 AGEP在函數優化中的應用數據，以VC++和Matlab為實驗平臺。輸入一組回歸數據，具有2個輸入變量x和y以及1個輸出變量z。算法通過已知的輸入輸出數據進行建模，再利用建立的模型算出預測值，計算真實值與預測值的相對誤差。分別對常規 GEP算法、改進 GEP算法[11]和本文的AGEP算法進行檢驗，比較和分析其結果。

設置進化算子：進化代數為 1 000，種群大小為50，基因數為5，頭部長度為6，IS和RIS變換率為0.1,單點重組、2點重組率pr和變異率pm采用混沌概率；函數集為{+，-，*，/，sqrt，ln，sin，cos，tan}；適應度函數：均方差,隨機數取值范圍為[-10, 10]。差分突變算子中的Fi和CRi采用文獻[8]中的參數。

2.2 實驗

由 AGEP 對表 1數據計算多次得到的較好模型為：

將AGEP算法運算后得到的預測值與GEP和文獻[11]中改進的GEP進行對比實驗，結果如表2所示。

表1 實驗參數Table 1 Experimental parameters

表2 AGEP和GEP、改進的GEP[11]實驗結果比較Table 2 Comparison of experimental results among GEP and improved GEP[11] and AGEP

圖1 AGEP算法的運算結果Fig.1 Operational results of AGEP

圖2 AGEP和GEP與改進的GEP[11]的時耗比較Fig.2 Comparison of time consumption among GEP and improved GEP[11] and AGEP

從表 2可見：GEP比 GEP和文獻[11]中改進的GEP算法性能要好，AGEP算法的平均誤差約為文獻[11]中改進的GEP算法的1/5，約為基本GEP算法的1/20。從圖2可見：在10次實驗中AGEP每次的收斂速度都比文獻[11]中的GEP和GEP的收斂速度快，說明AGEP算法具有更好的收斂性能、魯棒性和更高的運算精度。

3 結論

(1) 提出一種自適應基因表達式程序設計算法(AGEP)，設計了適合基因表達式特點的差分突變搜索、混沌重組、變異算子和災變算子。

(2) 此方法能提高算法的收斂速度、精度，有效克服算法陷入局部最優，以達到全局最優。

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

[2] 周明, 孫樹棟. 遺傳算法原理及應用[M]. 北京: 國防工業出版社, 1999: 123-166.ZHOU Ming, SUN Shu-dong. The principle and application of genetic algorithm[M]. Beijing: National Defense Industrial Press,1999: 123-166.

[3] 龔文引, 蔡之華. 基因表達式程序設計在復雜函數自動建模中的應用[J]. 系統仿真學報, 2006, 18(6): 1450-1454.GONG Wen-yin, CAI Zhi-hua. Automatic modeling of complex functions based on gene expression programming[J]. Journal of system simulation, 2006, 18(6): 1450-1454.

[4] 李康順, 黃浩華, 張文生. 一種基于 GEP的多層物流網絡Prufer編碼優化算法[J]. 系統仿真學報, 2012, 24(3): 594-602.LI Kang-shun, HUANG Hao-hua, ZHANG Wen-sheng. Prufer code optimization algorithm for muti-layer logistic networks based on gene expression programming[J]. Journal of system simulation, 2012, 24(3): 594-602.

[5] 谷瓊, 蔡之華, 朱莉. 基于PCA-GEP算法的邊坡穩定性預測[J]. 巖土力學, 2009, 30(3): 758-761.GU Qiong, CAI Zhi-hua, ZHU Li. Slope stability prediction based on PCA-GEP algorithm[J]. Rock and Soil Mechanics,2009, 30(3): 758-761.

[6] 王衛紅, 阮薇, 李曲. 基于差分演化的 GEP決策樹算法[J].計算機工程, 2011, 37(1): 182-183.WANG Wei-hong, RUAN Wei, LI Qu. Decision tree algorithm by gene expression programming based on differential evolution[J]. Computer Engineering, 2011, 37(1): 182-183.

[7] Storn R, Price K. Differential evolution—A simple and eff i cient heuristic for global optimization over continuous spaces[J]. J of Global Optim, 1997, 11(4): 341-359.

[8] Bezdek J C. What is computational intelligence computational intelligence imitationg life[M]. New York: IEEE Press, 1994:202-205.

[9] Russell S, Norvig P. 人工智能現代方法[M]. 姜哲, 等譯. 北京: 人民郵電出版社, 2004: 105-106.Russell S, Norvig P. A artificial intelligence modern approach[M]. JIANG Zhe, et al, trans. Beijing: The People Post and Telecommunications Press, 2004: 105-106.

[10] Cai Z. Disciplinary frame and general features for intelligence science[C]// Proc 1st China-Korea Joint Workshop on Intelligent Systems. Korea, 2002: 214-219.

[11] 張春潛, 王洪亮, 武江偉. 一種改進的 GEP算法在函數優化中的運用[J]. 兵工自動化, 2010, 29(4): 90-94.ZHANG Chu-qian, WANG Hong-liang, WU Jiang-wei.Application of an improved GEP algorithm on function optimization[J]. Ordnance Industry Automation, 2010, 29(4):90-94.

[12] Brest J, Greiner S, Boskovic B, et al. Adapting control parameters in differential evolution: A comparative study on numerical benchmark problems[J]. IEEE Trans on Evol Comput,2006, 10(6): 646-657.

[13] 朱紅求, 陽春華, 桂衛華. 一種帶混沌變異的粒子群優化算法[J]. 計算機科學, 2010, 37(3): 216-218.ZHU Hong-qiu, YANG Chun-hua, GUI Wei-hua. Particle swarm optimization with chaotic mutation[J]. Computer Science, 2010,37(3): 216-218.

[14] 毛潤宇, 王小平, 薛小平. 一種自適應差分演化算法[J]. 計算機應用與軟件, 2008, 25(12): 7-26.MAO Run-yu, WANG Xiao-ping, XUE Xiao-ping. An adaptive differential evolution algorithm[J]. Computer Applications and Software, 2008, 25(12): 7-26.

[15] 郭俊, 桂衛華, 陽春華. 改進差分進化算法在鋁電解多目標優化中的應用[J]. 中南大學學報: 自然科學版, 2012, 33(1):45-48.GUO Jun, GUI Wei-hua, YANG Chun-hua. An improved hybrid differential evolution algorithm used for multi-objective optimization of aluminum[J]. Journal of Central South University: Science and Technology, 2012, 33(1): 45-48.