基于混合選擇和動態(tài)變異的基因表達(dá)式編程

摘要:基因表達(dá)式編程(GEP)是一種基于基因型和表現(xiàn)型的新型遺傳算法，目前被廣泛應(yīng)用在函數(shù)發(fā)現(xiàn)、時間序列預(yù)測和分類等領(lǐng)域。傳統(tǒng)GEP算法采用輪盤賭方式來選擇種群個體，其擇優(yōu)強(qiáng)度過大，易導(dǎo)致個體多樣性減弱，產(chǎn)生“近親繁殖”;種群個體的變異概率固定，變異幅度不能動態(tài)地適應(yīng)每代的進(jìn)化結(jié)果，影響進(jìn)化效率。針對上述兩個缺陷，本文對傳統(tǒng)GEP做出兩點改進(jìn):作者采用混合選擇策略，以維持進(jìn)化過程中個體的多樣性，避免“近親繁殖”;引入動態(tài)變異思想，使種群在進(jìn)化過程中能根據(jù)自身適應(yīng)性的高低來動態(tài)調(diào)整個體的變異概率，以最大限度地保留高適應(yīng)度基因片段，消除低適應(yīng)度基因片段。通過實驗，本文驗證了兩項改進(jìn)的有效性。

關(guān)鍵詞:基因表達(dá)式編程;混合選擇;動態(tài)變異;函數(shù)發(fā)現(xiàn);時間序列預(yù)測

中圖分類號:TP311文獻(xiàn)標(biāo)識碼:A文章編號:1009-3044(2010)02-379-03

Gene Expression Programming Based on Mixed Selection and Dynamic Variation

DU Cui-fang1， YU Lei2， SU Jian1

(1.Yan'an Branch of Shaanxi BCTV Network Intermediary Co.，Ltd， Yan'an 716000， China; 2.College of Mechanical Engineering， Xi'an Jiaotong University， Xi'an， 710049， China)

Abstract: Gene expression programming (GEP)， which is a new type genetic algorithm based on genotype and phenotype， is now widely applied in function finding， time sequence prediction and classification. However， due to strong intensity in preferred roulette selection of individuals， traditional GEP often leads to reduction in the diversity of individuals and causes inbreeding; on the other hand， traditional GEP can not adapt to the evolution result of each generation by adjusting variation probability， so that the performance of GEP is affected. In order to overcome the drawbacks above， this paper makes two amendments to the traditional GEP: The author adopts the mixed selection strategy to maintain individual’s diversity and avoid the phenomenon of inbreeding. Dynamic variation is introduced to reserve the high-fitness gene segments and eliminate the low-fitness ones by adjusting variation probability of individuals according to the evaluation of individuals' performance. Through experiments， this paper verified the validity of two amendments.

Key words: gene expression programming; mixed selection; dynamic variation; function finding; time sequence prediction

基因表達(dá)式編程(Gene Expression Programming)是葡萄牙科學(xué)家Candida Ferreira在2001年提出來的一種新型仿生學(xué)算法[1]。其融合了遺傳算法和遺傳編程的優(yōu)點，采用基因型與表現(xiàn)型分離存在而相互轉(zhuǎn)化的算法結(jié)構(gòu)。GEP以其簡潔的算法結(jié)構(gòu)和優(yōu)良的求解性能，目前被廣泛應(yīng)用在函數(shù)發(fā)現(xiàn)、時間序列預(yù)測和問題分類等領(lǐng)域，并不斷得到改進(jìn)[4]。

傳統(tǒng)GEP一般采用輪盤賭方式選擇個體，但輪盤賭選擇是一種強(qiáng)性擇優(yōu)選擇，易導(dǎo)致個體多樣性降低，產(chǎn)生“近親繁殖”。函數(shù)發(fā)現(xiàn)實驗表明，加大變異概率的方法不能有效解決該問題。因而本文引入輪盤賭選擇與隨機(jī)選擇相結(jié)合的混合選擇，其既可將適應(yīng)性高的個體以較大概率復(fù)制到下一代，保證進(jìn)化的高效性，又可避免“近親繁殖”。

GEP經(jīng)常用來求解缺乏先驗知識的問題。傳統(tǒng)GEP根據(jù)經(jīng)驗值來設(shè)置變異概率，包括突變率、移位率和重組率。經(jīng)驗值設(shè)定后，在進(jìn)化過程中不再變動，因而具有盲目性和非動態(tài)適應(yīng)性。動態(tài)變異根據(jù)當(dāng)代最優(yōu)個體適應(yīng)度與上一代最優(yōu)個體適應(yīng)度的比較結(jié)果，動態(tài)調(diào)整變異概率。若當(dāng)代最優(yōu)個體適應(yīng)度比上一代高時，適度降低變異概率，讓優(yōu)良基因片段較為完整地保留到下一代;反之，提高變異概率，消除不良基因片段，產(chǎn)生新的優(yōu)良基因片段。

1 GEP原理

1.1 GEP基礎(chǔ)概念

GEP中最重要的概念是基因型(染色體)和表現(xiàn)型(表達(dá)式樹)。染色體是承載遺傳信息的實體，直接參與遺傳操作;表達(dá)式樹作為染色體中遺傳信息的表達(dá)形式，可簡潔地將遺傳信息表示為具有數(shù)學(xué)意義的圖形。

傳統(tǒng)GEP中，染色體由若干個基因通過連接運(yùn)算符(如‘+’、‘*’等)相接組成。這種人為設(shè)定的連接運(yùn)算符會限制染色體結(jié)構(gòu)，不利于遺傳。因此，本文采用單基因結(jié)構(gòu)染色體，以較長的基因長度來彌補(bǔ)單基因攜帶遺傳信息量少的缺陷。基因由頭部和尾部組成。頭部含有終結(jié)符和函數(shù)符，尾部只含有終結(jié)符。終結(jié)符是數(shù)值變量，函數(shù)符是運(yùn)算符號。尾部長度t=h*(n-1)+1，這里h是頭部長度，n是運(yùn)算符最大運(yùn)算目數(shù)。文獻(xiàn)[7]證明了在此公式約束下，GEP遺傳操作總能產(chǎn)生有效基因。表達(dá)式樹是由終結(jié)符和函數(shù)符組成的樹形結(jié)構(gòu)。表達(dá)式樹與染色體通過編碼和解碼規(guī)則相互進(jìn)行無歧異的轉(zhuǎn)化，使遺傳操作簡單、進(jìn)化結(jié)果直觀。

Candida提出了兩種適應(yīng)度評價函數(shù)[1]:一種是基于絕對誤差的適應(yīng)度評價函數(shù)(如1式)，另一種是基于相對誤差的適應(yīng)度評價函數(shù)(如2式)。

(1)

這里fi表示第i號個體的適應(yīng)度;常數(shù)M表示選擇帶寬;Cij表示將第j號測試樣本代入第i號個體所得函數(shù)值;Tj表示第j號測試樣本的目標(biāo)值;Ct表示測試樣本總數(shù)。

1.2 GEP編解碼規(guī)則

GEP編解碼規(guī)則是GEP精髓所在。編碼規(guī)則描述為:將數(shù)學(xué)表達(dá)式根據(jù)其語義構(gòu)造成一棵表達(dá)式樹，然后從根結(jié)點開始，對樹進(jìn)行層次遍歷，所得到的結(jié)點就是基因編碼的有效部分(K-表達(dá)式[1])。基因長度固定，所以基因由K-表達(dá)式和尾部填充的冗余字符組成。看似冗余的字符串為基因變異提供了空間結(jié)構(gòu)。解碼規(guī)則描述為:根據(jù)基因中字符的語義，由左往右將字符串表示為一棵表達(dá)式樹。

1.3 GEP算法流程

先初始化一個種群，對種群中的個體進(jìn)行適應(yīng)度評價，適應(yīng)度高的個體有較大機(jī)率被復(fù)制到下一代種群，反之亦然;在進(jìn)化過程中，對每一代種群的個體進(jìn)行變異操作，再進(jìn)行適應(yīng)度評價，如此重復(fù)，直到出現(xiàn)預(yù)期適應(yīng)度個體或達(dá)到預(yù)定進(jìn)化代數(shù)為止。算法流程如圖1所示。

2 混合選擇

輪盤賭選擇以個體適應(yīng)度占總適應(yīng)度之和的比例作為個體被選擇的概率，即 。個體適應(yīng)度越高，被選留到下一代的機(jī)會就越大。隨機(jī)選擇是完全隨機(jī)性的選擇方式。如何將兩種選擇方式搭配使用是混合選擇的關(guān)鍵。本文采用輪盤賭主隨機(jī)輔混合選擇:進(jìn)化過程中，若當(dāng)代最優(yōu)個體適應(yīng)度高于或等于上一代，采用輪盤賭選擇，否則采用隨機(jī)選擇，即:

if (fittest [generation] >= fittest[generation-1])

then RouletteSlect;

elsethen RandomSelect;

3 動態(tài)變異

3.1 動態(tài)變異的基本思想

變異包括突變、移位和重組三種形式。動態(tài)變異根據(jù)每一代進(jìn)化效果來動態(tài)地調(diào)整變異概率。動態(tài)變異描述為:進(jìn)化過程中，變異率(突變率、移位率和重組率)等于初始變異率乘以上代最優(yōu)個體適應(yīng)度與當(dāng)代最優(yōu)個體適應(yīng)度的商，即P=PInit*(best[g-1]/best[g])。這樣，若當(dāng)代最優(yōu)個體適應(yīng)度比上代最優(yōu)個體適應(yīng)度高時，變異率會降低，有利于保存適應(yīng)度高的基因片段;若當(dāng)代最優(yōu)個體適應(yīng)度比上代低時，變異率會提高，有利于消除低適應(yīng)度的基因片段，產(chǎn)生新的高適應(yīng)度基因片段。

3.2 突變、移位和重組

突變是一種較為簡單的變異。本文采用的點突變可直接對基因中任何位置的字符進(jìn)行替換。動態(tài)突變應(yīng)用了動態(tài)變異的思想，突變概率會實時調(diào)整;移位是對基因中的片段先進(jìn)行復(fù)制，再插入基因頭部其他位置的操作;重組是對兩個不同基因的同位置片段進(jìn)行調(diào)換，從而得到兩個新基因的操作。動態(tài)移位、動態(tài)重組的思想與動態(tài)突變相似。

4 實驗驗證與分析

4.1 實驗概況

實驗是在進(jìn)化相同代的條件下，比較最優(yōu)個體適應(yīng)度的平均值。為方便比較，將各改進(jìn)的GEP簡稱規(guī)定如下:GEP(傳統(tǒng)GEP)、Mixed-GEP(混合選擇GEP)、Dyn-GEP(動態(tài)變異GEP)和Mixed-Dyn-GEP(動態(tài)變異混合選擇GEP)。實驗平臺為: Pentium 4 2.8G， 512M，Java開發(fā)。設(shè)計的三組實驗如下。前兩組實驗的運(yùn)行參數(shù)如表1所示。

1) 簡單函數(shù)a3+a2+a的發(fā)現(xiàn);2) Schaffer函數(shù)的發(fā)現(xiàn);3) 太陽黑子預(yù)測。

4.2 簡單函數(shù)a3+a2+a發(fā)現(xiàn)

四種GEP算法各運(yùn)行20次，統(tǒng)計出各種GEP進(jìn)化得到最優(yōu)個體適應(yīng)度的平均值，如圖2所示。從圖中可看出:改進(jìn)后GEP的性能均比傳統(tǒng)GEP有一定程度的提高。Mixed-GEP提高了7%，Dyn-GEP提高了3.6%，Mixed-Dyn-GEP提高了28%。可見，將混合選擇與動態(tài)變異兩項改進(jìn)相融合的Mixed-Dyn-GEP表現(xiàn)最好。

4.3 Schaffer F6函數(shù)發(fā)現(xiàn)

各GEP運(yùn)行10次所得到最優(yōu)適應(yīng)度的平均值如圖3所示。各改進(jìn)的GEP均比傳統(tǒng)GEP的性能有所提高。Mixed-GEP提高了2.7%，Dyn-GEP提高了2.4%，Mixed-Dyn-GEP提高了6%。

4.4 太陽黑子預(yù)測

太陽黑子是時間序列預(yù)測的經(jīng)典測試數(shù)據(jù)。本實驗采用文獻(xiàn)[6]的太陽黑子數(shù)據(jù)集和實驗參數(shù)，選擇1756年到1859年的數(shù)據(jù)作訓(xùn)練集，1860年到1864年的數(shù)據(jù)做預(yù)測，適應(yīng)度評價函數(shù)采用式(1)。實驗選用10維相關(guān)度，即當(dāng)年太陽黑子數(shù)據(jù)與其前10年的數(shù)據(jù)有關(guān)。用各GEP進(jìn)化出最優(yōu)預(yù)測模型，見表2所示(X0-X9表示當(dāng)年的前10年太陽黑子數(shù)據(jù))。然后根據(jù)模型來預(yù)測1860年到1864年的數(shù)據(jù)值，并與實際值比較，見圖4所示。

通過用式(3)計算各模型預(yù)測值與實際值間的累計絕對誤差。可看出，混合選擇或動態(tài)變異單獨作用時效果不好，但兩項改進(jìn)融合時可起到明顯的改善作用。GEP模型的預(yù)測誤差是43.15，而Mixed-Dyn-GEP模型的預(yù)測誤差是37.93，誤差減小了12.18%。

py表示預(yù)測值，ty表示實際值式(3)。

5 結(jié)論與展望

通過實驗，本文驗證了兩項改進(jìn)的有效性，并總結(jié)了改進(jìn)的GEP所適用的求解問題類型:兩項改進(jìn)獨立作用時，均能明顯改善函數(shù)發(fā)現(xiàn)的結(jié)果，但不適合模型預(yù)測;當(dāng)兩項改進(jìn)融合作用時，對兩類實驗均有較好的改進(jìn)效果。

本文仍有不足之處，作者會繼續(xù)探究以下方面工作:考慮更合理的混合選擇策略，更精確地調(diào)整動態(tài)變異率，建立更完善的太陽黑子模型。

參考文獻(xiàn):

[1] Ferreira C. Gene Expression Programming: A New Adaptive Algorithm for Solving Problems. Complex Systems， 2001，13(2): 87-129.

[2] FERREIRA C.Gene Expression Programming in Problem Solving[A].6th Online World Conference on Soft Computing in Industrial Applications[C].2001.

[3] 張文修，梁怡.遺傳算法的數(shù)學(xué)基礎(chǔ)[M].西安:西安交通大學(xué)出版社，2000:13-26.

[4] 唐常杰，彭京，張歡，等.基于基因表達(dá)式編程的知識發(fā)現(xiàn)的三項新技術(shù)——轉(zhuǎn)基因，重疊基因表達(dá)和回溯進(jìn)化[J].計算機(jī)應(yīng)用，2005(09).

[5] 陳宇.基于基因表達(dá)式編程函數(shù)挖掘和時間序列分析關(guān)鍵技術(shù)研究[D].四川大學(xué)，2006.

[6] 陳宇，唐常杰，鐘義嘯，等.一個基于基因表達(dá)式編程的時間序列預(yù)測新方法[J].計算機(jī)科學(xué)，2005(增刊B):269-271，2005.

[7] ZUO J， TANG C J， LI C， et al. Time Series Prediction based on Gene Expression Programming[A].International Conference for Web Information Age 2004[C] .Lecture Notes in Computer Science， 2004.

[8] Ferreira C，F(xiàn)unction Finding and the Creation of Numerical Constants in Gene Expression Programming[A]. the 7th Online World Conference on Soft Computing in Industrial Applications[C]. England:September 23-October 4，2002.

[9] http://www.gene-expression-programming.com.