多表達(dá)式程序設(shè)計(jì)的新型評估方法*

鄭秋生，何 锫,2,3，李 驥

(1.長沙理工大學(xué)計(jì)算機(jī)與通信工程學(xué)院，湖南 長沙 410114;2.廣州大學(xué)計(jì)算機(jī)科學(xué)與教育軟件學(xué)院，廣東 廣州 510006;3.北京大學(xué)高可信軟件技術(shù)教育部重點(diǎn)實(shí)驗(yàn)室，北京 100871)

1 引言

遺傳程序設(shè)計(jì)GP(Genetic Programming)[1]是重要的自動程序設(shè)計(jì)方法，包括線性與非線性表示兩類。多表達(dá)式程序設(shè)計(jì)MEP(Multi Expression Programming)、基因表達(dá)式程序設(shè)計(jì)GEP(Gene Expression Programming)、文法演化GE(Grammatical Evolution)以及Hoare語義型遺傳程序設(shè)計(jì)等都是線性表達(dá)的遺傳程序設(shè)計(jì)方法[2～9]，它們在多目標(biāo)優(yōu)化、金融預(yù)測、海量數(shù)據(jù)分析、軟件工程、信息安全等領(lǐng)域都得到了廣泛的應(yīng)用[6, 10]。

與傳統(tǒng)GP相比較，MEP等線性表達(dá)的GP(某些文獻(xiàn)也將線性表達(dá)的GP簡稱為線性GP)既便于個體表示、遺傳操作，又易于描述復(fù)雜結(jié)構(gòu)和實(shí)現(xiàn)，因此自提出以來一直很受關(guān)注。然而一切GP都以遺傳算法[11]為基礎(chǔ)，因而轉(zhuǎn)換、評估工作十分繁復(fù)，除要將個體的樹型/線性表示方式轉(zhuǎn)換成相應(yīng)的表現(xiàn)型外，還要執(zhí)行、測試所得的近似解以確認(rèn)它的合適程度。如此一來，評估(某些語義計(jì)算甚至一個小小的步驟就得耗費(fèi)數(shù)十小時以上)等的計(jì)算耗費(fèi)了大量的時空資源，成為GP研究的挑戰(zhàn)性問題[12]。

本文擬就評估問題對MEP做深入探討。先系統(tǒng)化分析它的表示、評估過程中重復(fù)計(jì)算現(xiàn)象的根源所在，而后給出規(guī)避這些問題的理論依據(jù)、實(shí)際解決方案。因無須重復(fù)計(jì)算相同的語義工作，新方法在演化效率上有了顯著提高。

2 背景和相關(guān)工作

多表達(dá)式程序設(shè)計(jì)[3,6,9]作為線性表達(dá)的遺傳程序設(shè)計(jì)方法,主要通過將搜索目標(biāo)分為基因型與表現(xiàn)型兩個層面來規(guī)范求解過程。由于引入了雙層概念，MEP等線性表達(dá)方法的評估須先履行兩型間的轉(zhuǎn)換，而后執(zhí)行、測試表現(xiàn)型所刻畫的程序。

MEP的個體可以表示為線性序列c1,c2,…,cn，其中ci(1≤i≤n)或取自由常量、變量組成的終端集，或取自函數(shù)集F，當(dāng)然此時須依函數(shù)的數(shù)目以及此前獲得的cj(1≤j

Table 1 MEP individual representation

表1中基因1對應(yīng)的表現(xiàn)型或表達(dá)式為a；基因2對應(yīng)的表達(dá)式為b；基因3的表達(dá)式為a+b；基因4的表達(dá)式為a；基因5的表達(dá)式為b×(a+b)；基因6的表達(dá)式為(b×(a+b))+a。由此可見，語義的重復(fù)計(jì)算現(xiàn)象會充斥評估過程，這在MEP里尤為明顯。

有關(guān)MEP的算法流程如下所示(讀者也可以參見文獻(xiàn)[3,6,9])：

(1)隨機(jī)產(chǎn)生一個個體種群；

(2)評估種群中的個體，若滿足評估標(biāo)準(zhǔn)、精度或算法終止條件，則停止，最佳個體所表征的解即為所求目標(biāo)；

(3)若不滿足終止條件，則在當(dāng)前種群上實(shí)施雜交、變異等遺傳操作以期獲得新的種群；

(4)轉(zhuǎn)第(2)步，反復(fù)迭代。

MEP的應(yīng)用[6,9,13～20]概括地講涵蓋數(shù)字電路設(shè)計(jì)、天線設(shè)計(jì)、符號回歸、金融預(yù)測與建模、分類、數(shù)據(jù)分析、入侵檢測、決策支持系統(tǒng)、算法設(shè)計(jì)以及TSP求解等領(lǐng)域。圖像配準(zhǔn)是利用圖像序列實(shí)施3D重建的關(guān)鍵任務(wù)。文獻(xiàn)[17]將這一難題歸結(jié)為面向特征點(diǎn)的公式發(fā)現(xiàn)問題，嘗試采用MEP求解。 文獻(xiàn)[13]等則探討了MEP等諸多線性表達(dá)的GP在基本入侵檢測方面的應(yīng)用。Alavi A H團(tuán)隊(duì)[18～20]解決實(shí)際工程應(yīng)用問題多次采用了MEP。如他們在文獻(xiàn)[18]中借助MEP對瀝青混合材料的永久變形進(jìn)行分析；在文獻(xiàn)[19]中對土壤液化的評估實(shí)施MEP建模。MEP在國內(nèi)也得到了關(guān)注。文獻(xiàn)[14，15]等充分考慮GEP、MEP的優(yōu)勢，在個體表示、解讀方面做了努力，提高了性能。

綜上所述，MEP應(yīng)用面很廣，是解決數(shù)據(jù)分析、實(shí)際工程應(yīng)用問題的有力工具。然而，MEP與其他GP家族成員一樣，也有計(jì)算量大、評估耗時的不足。鑒于目前直接改進(jìn)其評估工作的研究尚不多見，以下擬系統(tǒng)深入地分析個體表示，嘗試規(guī)避評估過程凸顯的重復(fù)計(jì)值現(xiàn)象，從而提高算法性能。

3 MEP中的重復(fù)評估問題

MEP實(shí)質(zhì)是以一定法則不斷改變、演化產(chǎn)生新的個體集(也叫種群)的方式來獲取問題的解的。從第2節(jié)的表1易見，個體的評估會出現(xiàn)大量重復(fù)計(jì)值現(xiàn)象。本節(jié)將深入分析MEP算法模型上的這一問題，指出重復(fù)計(jì)值現(xiàn)象產(chǎn)生的充分條件和理論計(jì)算依據(jù)。

定理1設(shè)MEP的函數(shù)集和終端集分別是F、T，T中終端符的個數(shù)為|T|，則染色體中基因個數(shù)多于|T|時，必有重復(fù)運(yùn)算。

定義1(等型基因) 設(shè)I是MEP系統(tǒng)中長度為d的個體(染色體)，I中第d1、d2(1≤d1,d2≤d)兩號基因等型，如果它們所表征的表現(xiàn)型或抽象語法樹一致。

定理2設(shè)MEP的函數(shù)集和終端集分別是F、T，那么評估個體I的長為d的前綴片段(個體前d個基因構(gòu)成的基因片段)所需的運(yùn)算量總數(shù)，記為N(T,F,I,d)，可由式(1)獲得。

(1)

其中,di是基因在個體I中的下標(biāo)。

證明施歸納于個體前綴基因片段的長度d如下：

(1)歸納基始：d=0或1時，結(jié)論顯見成立。

(2)歸納論證步驟分兩步進(jìn)行。

①當(dāng)?shù)赿個基因?yàn)榻K端符時： 評估d個前綴基因的總運(yùn)算量N(T,F,I,d)實(shí)質(zhì)是在前d-1個基因評估運(yùn)算量基礎(chǔ)上增加了一次常量提取運(yùn)算，因而結(jié)論成立，符合公式描述。

②當(dāng)?shù)赿個基因?yàn)楹瘮?shù)運(yùn)算f(d1,d2,…,dm)時：d個前綴基因的總評估運(yùn)算量N(T,F,I,d)應(yīng)包括前d-1個基因的評估運(yùn)算量與f(d1,d2,…,dm)本身的運(yùn)算量兩部分。據(jù)歸納假設(shè)，前者是N(T,F,I,d-1)，后者宜為第d1,d2,…,dm個基因的評估運(yùn)算量加上一次m元運(yùn)算f(d1,d2,…,dm)。又對任意i(1≤i≤m)，第di個基因本身的評估運(yùn)算量可借助歸納假設(shè)和總運(yùn)算量概念表達(dá)為：N(T,F,I,d)-N(T,F,I,di-1)。故此結(jié)論成立。

□

為方便理解，表1同時給出了染色體前綴運(yùn)算總量的計(jì)值示例。由定義1易見，基因間的等型關(guān)系是一種等價關(guān)系。下面的定理3將著力回答評估中的重復(fù)運(yùn)算問題。

證明需注意三點(diǎn)：

(1)等型基因類中的元素僅需實(shí)際計(jì)算一個(比如該類中被第一個分析和發(fā)現(xiàn)的元素)。

(2)實(shí)際計(jì)算等型基因類中的一個元素時，涉及F∪T上符號所表征的計(jì)值運(yùn)算僅有一次。因?yàn)閰⑴c復(fù)合運(yùn)算的子樹是低深度的子樹，其計(jì)值早在低深度基因類分析過程中已完成，可以直接引用(不涉及F∪T中元素所明確表示的運(yùn)算)。

(3)關(guān)于深度為1的等型類的計(jì)值問題，這里按計(jì)值一次的方式處理(涉及到T中符號，有可能存在某些轉(zhuǎn)換)，其它重復(fù)現(xiàn)象可以通過引用獲得(不必做有關(guān)轉(zhuǎn)換)。

至此，我們分析了MEP的重復(fù)計(jì)值問題。它們包括個體內(nèi)與種群中個體間的重復(fù)計(jì)值現(xiàn)象，其中后者較為隱蔽。下節(jié)將據(jù)定理3等結(jié)論給出去除重復(fù)計(jì)算現(xiàn)象的具體技術(shù)方案。實(shí)際應(yīng)用過程中，定理3可以施用于演化過程產(chǎn)生的所有種群和個體，這只需將定理中的d視為演化過程中所有個體首尾銜接形成的大個體即可。

4 新型MEP算法及評估

依據(jù)以上定理，本節(jié)介紹具有去除重復(fù)運(yùn)算功能的評估方案：處理單個基因的算法NMEP及嵌入NMEP的MEP演化算法。

算法NMEP基本思想：通過不斷構(gòu)建等型基因有向圖Q(V，E)來識別重復(fù)的基因，從而避免重復(fù)計(jì)算。V是頂點(diǎn)集，E是有向邊集，V中每個頂點(diǎn)有編號且對應(yīng)一個基因，并存儲該基因的信息。

算法NMEP

輸入：基因g。

輸出：基因g在V中的相關(guān)頂點(diǎn)編號及g的其他信息。

步驟1本步驟只在MEP初始化種群之前執(zhí)行一次。初始化等型基因有向圖Q(V，E)：終端符集T={z1,…,zk}中每個終端符代表的基因g1,…,gk均屬不同等型基因類，故在V中創(chuàng)建它們對應(yīng)的頂點(diǎn)v1,…,vk(下標(biāo)1,2,…,k是頂點(diǎn)在V中的編號，下同)，并對所有頂點(diǎn)從1開始依序編號。將基因g1,…,gk所涵蓋的語義動作及其基因信息分別寫入v1,…,vk頂點(diǎn)中。num_gene等于V中頂點(diǎn)數(shù)。

步驟2演化過程中，如果基因g取自T中終端符，由于步驟1已對T中所有終端符進(jìn)行處理，則直接找到V中與基因g同屬一個等型基因類的基因g′對應(yīng)的頂點(diǎn)v′，輸出v′的編號及其基因信息。

步驟3如果基因g是函數(shù)形式(pg，s1,…,sn)，其中pg是操作符，s1,…,sn是它的參數(shù)，s1,…,sn所對應(yīng)的基因gs1,…,gsn必然已被處理，找到基因gs1,…,gsn在V中對應(yīng)的頂點(diǎn)編號a1,…,an。對算法中的操作符需要考慮交換率時，執(zhí)行步驟3.1、步驟3.3和步驟3.4；不需要時，執(zhí)行步驟3.2、步驟3.3和步驟3.4。

步驟3.1當(dāng)算法適用交換率時，如果pg滿足交換率，則需要將a1,…,an按一定順序排列成標(biāo)準(zhǔn)序列(本算法以a1,…,an的升序排列結(jié)果作為標(biāo)準(zhǔn)序列t1,…,tn)，如此便于在步驟3.4的操作中查找滿足與基因g重復(fù)條件的基因；否則，如果pg不滿足交換率，把a(bǔ)1,…,an賦值給t1,…tn；最后，找到頂點(diǎn)vt1。

步驟3.2當(dāng)算法不適用交換率時，把a(bǔ)1,…,an賦值給t1,…,tn；最后，找到頂點(diǎn)vt1。

為此，嵌入NMEP進(jìn)行評估去重的算法可重新表述如下：

Begin:

初始化種群；

for(i=1；i≤演化代數(shù)；i++)

{for(j=1;j≤種群大小;j++)

{依次處理種群的每個個體q：用算法NMEP處理個體中的每個基因；}

如果(i<演化代數(shù))

{交叉；變異；}

}

輸出最佳個體；

End

5 實(shí)驗(yàn)分析

由以上敘述可知，NMEP僅在評估時對MEP的基因進(jìn)行了等價去重處理，并沒有對演化規(guī)則、過程進(jìn)行任何變動，因而嵌入NMEP的MEP與傳統(tǒng)MEP應(yīng)有一樣的精度，自然無需就精度進(jìn)行實(shí)驗(yàn)比較。

新方法采用MEP的適應(yīng)值計(jì)算方法，即計(jì)算單染色體中所有基因的適應(yīng)值，然后以最佳值來表征個體適應(yīng)值，詳見式(2)。

(2)

本節(jié)針對符號回歸問題做了三個實(shí)驗(yàn)，其中目標(biāo)函數(shù)如式(3)～式(5)所示，x,y∈[-100，100]，涉及的參數(shù)見表2，S和E分別表示sin和exp運(yùn)算，比較的對象是運(yùn)行時間。

z=x4+x3+x2+x

(3)

z=sin(exp(sin(exp(sin(x)))))

(4)

z=x3+x2y-y

(5)

為更好地體現(xiàn)新方法的時間優(yōu)勢(主要得益于消除基因的重復(fù)引用，即語義的重復(fù)計(jì)算現(xiàn)象)，還增加了演化過程的語義復(fù)雜度，如為每個基因的處理/運(yùn)行額外添加了語義延時程序extra()。它的一次執(zhí)行將達(dá)萬次“a++”之眾。

Table 2 Parameters of experiment 1～experiment 3

圖2～圖4為通過實(shí)驗(yàn)1～實(shí)驗(yàn)3對比嵌入NMEP的MEP與傳統(tǒng)MEP的時間開銷，圖中橫坐標(biāo)表示運(yùn)行次數(shù)，縱坐標(biāo)表示時間，單位是s。每個實(shí)驗(yàn)都有兩條曲線，位于下方的曲線(時間少)均是嵌入NMEP的MEP的演化時間；位于上方的曲線(時間多)均是傳統(tǒng)MEP的演化時間。由圖2～圖4可知，傳統(tǒng)MEP在時間性能上明顯落后于嵌入NMEP的MEP，也即新評估方法擁有較大的時間優(yōu)勢。

Figure 2 Time comparison between NMEP-based MEP and traditional MEP in experiment 1圖2 實(shí)驗(yàn)1中嵌入NMEP的MEP與傳統(tǒng)MEP時間比較

Figure 3 Time comparison between NMEP-based MEP and traditional MEP in experiment 2圖3 實(shí)驗(yàn)2中嵌入NMEP的MEP與傳統(tǒng)MEP時間比較

Figure 4 Time comparison between NMEP-based MEP and traditional MEP in experiment 3圖5 實(shí)驗(yàn)3中嵌入NMEP的MEP與傳統(tǒng)MEP時間比較

圖5～圖7刻畫三個實(shí)驗(yàn)中NMEP查出傳統(tǒng)MEP演化過程包含的基因的重復(fù)次數(shù)。圖中橫坐標(biāo)表示演化代數(shù)，縱坐標(biāo)表示傳統(tǒng)MEP的基因的重復(fù)引用次數(shù)。從圖5～圖7的基因的重復(fù)引用總量看來，重復(fù)量是不可小覷的。試想如果被重復(fù)計(jì)算的語義動作的時間復(fù)雜度很高，那么大量重復(fù)將耗費(fèi)龐大的運(yùn)算時間和其他資源。

Figure 5 Repeat number NMEP finds out in experiment 1圖5 實(shí)驗(yàn)1中算法NMEP查找出的重復(fù)次數(shù)

Figure 6 Repeat number NMEP finds out in experiment 2圖6 實(shí)驗(yàn)2中算法NMEP查找出的重復(fù)次數(shù)

Figure 7 Repeat number NMEP finds out in experiment 3圖7 實(shí)驗(yàn)3中算法NMEP查找出的重復(fù)次數(shù)

綜觀圖2～圖7，當(dāng)傳統(tǒng)MEP的種群在演化過程中涉及的基因重復(fù)引用量、語義動作的運(yùn)算量越大，嵌入NMEP的MEP所節(jié)省的時間就越多。由上可知，嵌入NMEP的MEP在不改變傳統(tǒng)MEP演化規(guī)則和精度的基礎(chǔ)上，能夠準(zhǔn)確有效地識別被重復(fù)使用的基因，避免重復(fù)計(jì)算帶來的大量的資源消耗，使得MEP在性能上得到較大的提高。這表明，針對MEP的去重運(yùn)算研究不僅具有充分的理論依據(jù)，而且在具體實(shí)現(xiàn)環(huán)節(jié)也是可行的，是擁有重要前景的一個研究領(lǐng)域。

6 結(jié)束語

本文首先深入分析了MEP的基因在染色體中的表示特點(diǎn)及采用的評估方法，發(fā)現(xiàn)每個染色體中的任何基因都有可能多次被當(dāng)前或其它后續(xù)種群中的其他基因引用，造成重復(fù)計(jì)算的現(xiàn)象，繼而給出了現(xiàn)象出現(xiàn)的充分條件，以及處理的理論依據(jù)和具體算法。算法NMEP在保證與傳統(tǒng)MEP精度相同的基礎(chǔ)上，能有效識別會被重復(fù)引用的基因，避免大量重復(fù)計(jì)算，節(jié)省了寶貴的時空資源。最后的實(shí)驗(yàn)結(jié)論表明，去重計(jì)值后，嵌入NMEP的MEP在性能上有顯著提高?？梢姡ブ匮芯繉τ贛EP的整體研究具有重要的意義。我們下一步將用類似方法分析GEP的評估問題，相信在深度優(yōu)先解碼方式下會有相似效果。

[1] Koza J R.Genetic programming:On the programming of computers by means of natural selection[M]. Cambridge:MIT Press, 1992.

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

[3] Oltean M, Grosan C. A comparison of several linear genetic programming techniques[J]. Complex Systems, 2003, 14(4):285-313.

[4] McKay R I, Hoal N X, Whigham P A,et al. Grammar-based genetic programming:A survey[J]. Genetic Programming and Evolvable Machines, 2010, 11(3-4):365-396.

[5] O′Neill M, Ryan C. Grammatical evolution[M]. Dordrecht:Kluwer Academic Publishers, 2013.

[6] Oltean M, Grosan C, Diosan L,et al. Genetic programming with linear representation:A survey[J]. International Journal on Artificial Intelligence Tools, 2009, 19(2):197-239.

[7] He Pei,Kang Li-shan,Johnson C G,et al.Hoare logic-based genetic programming[J]. Science China(Information Sciences), 2011, 54(3):623-637.

[8] He Pei, Johnson C G, Wang Hou-feng. Modeling grammatical evolution by automation[J]. Science China Information Sciences, 2011, 54(12):2544-2553.

[9] Oltean M. Improving the search by encoding multiple solutions in a chromosome[M]∥Evolutionary Machine Design:Methodology and Applications,2005:88-110.

[10] Harman M. Software engineering meets evolutionary computation[J]. IEEE Computer, 2011, 44(10):31-39.

[11] Mitchell M. An introduction to genetic algorithms[J].Cambridge:MIT Press, 1996.

[12] O’Neill M, Vanneschi L, Gustafson S,et al. Open issues in genetic programming[J].Genetic Programming and Evolvable Machine, 2010, 11(3):339-363.

[13] Wu Shelly Xiaonan, Banzhaf W. The use of computational intelligence in intrusion detection systems:A review[J].Applied Soft Computing, 2010(10):1-35.

[14] Dai Mu-cheng,Tang Chang-jie,Zhu Ming-fang,et al.Automatic complex function discovery based on multi expression gene programming[J]. Journal of Sichuan University(Engineering Science Edition),2008,40(6):121-126.(in Chinese)

[15] Deng Wei,He Pei,Qian Jun-yan.Multi-gene expression programming with depth-first decoding principle[J].Pattern Recognition and Artificial Intelligence,2013,26(9):819-828.(in Chinese)

[16] Zhang Jia-wei,Wu Zhi-jian,Huang Zhang-can,et al.Classification based on multi expression programming[J]. Journal of Chinese Computer Systems,2010,31(7):1371-1374.(in Chinese)

[17] Zhao Xiu-yang, Zhang Cai-ming, Wang Ya-nan,et al. A hybrid approach based on MEP and CSP for contour registration[J].Applied Soft Computing, 2011(11):5391-5399.

[18] Mirzahosseini M R, Aghaeifar A, Alavi A H, et al. Permanent deformation analysis of asphalt mixtures using soft computing techniques[J]. Expert Systems with Applications, 2011, 38:6081-6100.

[19] Alavi A H, Gandomi A H. Energy-based numerical models for assessment of soil liquefaction[J].Geoscience Frontiers, 2012, 3(4):541-555.

[20] Alavi A H, Aminian P, Gandomi A H,et al. Genetic-based modeling of uplift capacity of suction caissons[J].Expert Systems with Applications, 2011, 38:12608-12618.

[21] Jiang Da-zhi,Peng Chen-feng,Liu Liang. Forecasting soil slope stability with MEP algorithm[J]. Journal of Shantou University(Natural Science Edition),2011,26(4):66-72.(in Chinese)

附中文參考文獻(xiàn)：

[14] 代術(shù)成，唐常杰，朱明放,等.基于多表達(dá)式基因編程的復(fù)雜函數(shù)挖掘算法[J].四川大學(xué)學(xué)報(工程科學(xué)版)，2008，40(6)：121-126.

[15] 鄧薇, 何锫, 錢俊彥. 深度優(yōu)先的多基因表達(dá)式程序設(shè)計(jì)[J].模式識別與人工智能，2013,26(9):819-828.

[16] 張建偉，吳志健，黃樟燦,等.基于多表達(dá)式編程的分類算法研究[J].小型微型計(jì)算機(jī)系統(tǒng)，2010，31(7)：1371-1374.

[21] 姜大志，彭晨楓，劉亮. 邊坡穩(wěn)定性的預(yù)報MEP分類預(yù)測算法[J].汕頭大學(xué)學(xué)報(自然科學(xué)版),2011，26(4)：66-72.