賈麗媛，張弛

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

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

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

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

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

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

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

1 自適應(yīng)基因表達(dá)式程序設(shè)計(jì)(AGEP)

1.1 基于差分突變的搜索技術(shù)

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

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

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

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

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

傳統(tǒng)的基因重組和變異操作在算法整個(gè)搜索過程中都保持不變，這不利于算法性能的提高。為此，把混沌理論運(yùn)用到基因重組和變異操作中，通過混沌序列動(dòng)態(tài)地控制基因重組和變異操作，將提高基因重組和交叉操作的效率。在初始階段，適應(yīng)度低于平均適應(yīng)度，說明該個(gè)體性能不好，對(duì)它采用較大的基因重組概率pr和變異概率pm；在后期階段，適應(yīng)度高于或接近平均適應(yīng)度，說明該個(gè)體性能優(yōu)良，對(duì)它采用較小的pr和pm。利用Logistic映射作為混沌信號(hào)發(fā)生器，產(chǎn)生一個(gè)迭代序列[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]之間變化。同時(shí)，也用混沌序列來控制基因重組點(diǎn)和變異點(diǎn)的選擇。

1.3 災(zāi)變算子

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

1.4 算法設(shè)計(jì)

算法如下：

PROCEDURE AGEP算法

Begin

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

計(jì)算P(0)中個(gè)體xi的適應(yīng)度；

t:=0；

repeat；

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

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

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

計(jì)算P(t) 中個(gè)體的適應(yīng)度；

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

執(zhí)行災(zāi)變操作

t:= t+ 1；

until 滿足停止條件；

用P(t)中的最好個(gè)體進(jìn)行系統(tǒng)預(yù)測；

End

2 實(shí)驗(yàn)及結(jié)果

2.1 實(shí)驗(yàn)參數(shù)設(shè)置

針對(duì)本文改進(jìn)的 AGEP在函數(shù)優(yōu)化中的應(yīng)用數(shù)據(jù)，以VC++和Matlab為實(shí)驗(yàn)平臺(tái)。輸入一組回歸數(shù)據(jù)，具有2個(gè)輸入變量x和y以及1個(gè)輸出變量z。算法通過已知的輸入輸出數(shù)據(jù)進(jìn)行建模，再利用建立的模型算出預(yù)測值，計(jì)算真實(shí)值與預(yù)測值的相對(duì)誤差。分別對(duì)常規(guī) GEP算法、改進(jìn) GEP算法[11]和本文的AGEP算法進(jìn)行檢驗(yàn)，比較和分析其結(jié)果。

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

2.2 實(shí)驗(yàn)

由 AGEP 對(duì)表 1數(shù)據(jù)計(jì)算多次得到的較好模型為：

將AGEP算法運(yùn)算后得到的預(yù)測值與GEP和文獻(xiàn)[11]中改進(jìn)的GEP進(jìn)行對(duì)比實(shí)驗(yàn)，結(jié)果如表2所示。

表1 實(shí)驗(yàn)參數(shù)Table 1 Experimental parameters

表2 AGEP和GEP、改進(jìn)的GEP[11]實(shí)驗(yàn)結(jié)果比較Table 2 Comparison of experimental results among GEP and improved GEP[11] and AGEP

圖1 AGEP算法的運(yùn)算結(jié)果Fig.1 Operational results of AGEP

圖2 AGEP和GEP與改進(jìn)的GEP[11]的時(shí)耗比較Fig.2 Comparison of time consumption among GEP and improved GEP[11] and AGEP

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

3 結(jié)論

(1) 提出一種自適應(yīng)基因表達(dá)式程序設(shè)計(jì)算法(AGEP)，設(shè)計(jì)了適合基因表達(dá)式特點(diǎn)的差分突變搜索、混沌重組、變異算子和災(zāi)變算子。

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

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

[2] 周明, 孫樹棟. 遺傳算法原理及應(yīng)用[M]. 北京: 國防工業(yè)出版社, 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] 龔文引, 蔡之華. 基因表達(dá)式程序設(shè)計(jì)在復(fù)雜函數(shù)自動(dòng)建模中的應(yīng)用[J]. 系統(tǒng)仿真學(xué)報(bào), 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的多層物流網(wǎng)絡(luò)Prufer編碼優(yōu)化算法[J]. 系統(tǒng)仿真學(xué)報(bào), 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算法的邊坡穩(wěn)定性預(yù)測[J]. 巖土力學(xué), 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] 王衛(wèi)紅, 阮薇, 李曲. 基于差分演化的 GEP決策樹算法[J].計(jì)算機(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. 人工智能現(xiàn)代方法[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] 張春潛, 王洪亮, 武江偉. 一種改進(jìn)的 GEP算法在函數(shù)優(yōu)化中的運(yùn)用[J]. 兵工自動(dòng)化, 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] 朱紅求, 陽春華, 桂衛(wèi)華. 一種帶混沌變異的粒子群優(yōu)化算法[J]. 計(jì)算機(jī)科學(xué), 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] 毛潤宇, 王小平, 薛小平. 一種自適應(yīng)差分演化算法[J]. 計(jì)算機(jī)應(yīng)用與軟件, 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] 郭俊, 桂衛(wèi)華, 陽春華. 改進(jìn)差分進(jìn)化算法在鋁電解多目標(biāo)優(yōu)化中的應(yīng)用[J]. 中南大學(xué)學(xué)報(bào): 自然科學(xué)版, 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.