基因表達(dá)式程序設(shè)計(jì)在宏觀經(jīng)濟(jì)預(yù)測(cè)中的應(yīng)用

鄢靖豐

(許昌學(xué)院 信息工程學(xué)院，河南 許昌461000)

Gene Expression Programming，簡(jiǎn)稱GEP[1]是葡萄牙科學(xué)家C. Ferreira 在2001年提出的一種新的自適應(yīng)演化算法，它模擬生物界的自然選擇和進(jìn)化機(jī)制，具有自組織、自學(xué)習(xí)等特征，同時(shí)還具有優(yōu)勝劣汰的自然選擇、簡(jiǎn)單的遺傳操作、結(jié)構(gòu)與功能的復(fù)雜性等特點(diǎn).它運(yùn)用遺傳算法[2](Genetic Algorithm, GA)和遺傳程序設(shè)計(jì)[3](Genetic Programming, GP)的基本思想，通過生成計(jì)算機(jī)程序來解決問題，既吸收了GA和GP的優(yōu)點(diǎn)：GA個(gè)體的固定長(zhǎng)度線性串編碼，容易進(jìn)行遺傳操作；GP個(gè)體的非線性樹型表示，可以用來解決復(fù)雜的問題.同時(shí)又克服了GA和GP的缺點(diǎn)：GA只能解決一些簡(jiǎn)單問題；而GP過于復(fù)雜，不利于進(jìn)行遺傳操作.在GEP中，個(gè)體首先被表示成具有固定長(zhǎng)度的線性串K-表達(dá)式，在計(jì)算的時(shí)候把K-表達(dá)式轉(zhuǎn)換成表達(dá)式樹.由于GEP利用樹來表示計(jì)算機(jī)程序，因此，可以通過自動(dòng)生成計(jì)算機(jī)程序來解決許多問題，如預(yù)測(cè)、分類、符號(hào)回歸和圖像處理等.

1 GEP算法思路框架與實(shí)現(xiàn)過程

圖1 算法流程圖

GEP求解函數(shù)優(yōu)化與建模問題主要包括GEP個(gè)體編碼及表示、適應(yīng)度函數(shù)設(shè)計(jì)、常數(shù)創(chuàng)建以及GEP的遺傳操作等，算法求解一般問題的思路框架如圖1所示.

1.1 算法編碼方案

在GEP中，個(gè)體是由一個(gè)或多個(gè)基因組成.基因是由頭部和尾部組成，其中頭部符號(hào)可以從函數(shù)集和終止符集中隨機(jī)選取(其中第一個(gè)符號(hào)只從函數(shù)集中選取)；尾部符號(hào)只能從終止符集中選取.如果基因的頭部長(zhǎng)度為h，則尾部長(zhǎng)度t可由公式(1)計(jì)算得到，

t=h*(n-1)+1 ，

(1)

圖2 基因表達(dá)樹

其中，n表示在函數(shù)集中變量數(shù)最多函數(shù)參數(shù)個(gè)數(shù).由于尾部與頭部所具有的特殊關(guān)系，必須保證，基因在遺傳演化過程中，都不能產(chǎn)生無(wú)效個(gè)體，即GEP中良性染色體集合在遺傳操作下是封閉的[4].將基因內(nèi)的元素進(jìn)行編碼設(shè)計(jì)成為K-express，將K-express按照一定規(guī)則進(jìn)行解碼構(gòu)成一個(gè)表達(dá)樹，所以GEP算法的編碼具有2種特性，即表現(xiàn)型與基因型，這與傳統(tǒng)的GP編程有所不同，這正是GEP的優(yōu)勢(shì)之所在，基因表達(dá)樹的構(gòu)建樹過程如圖2所示，構(gòu)造方法按照中序遍歷算法訪問，對(duì)應(yīng)基因序列表達(dá)式為(a+b)*(c-d).

1.2 適應(yīng)度函數(shù)的設(shè)計(jì)

在自然界中，個(gè)體適應(yīng)度值就是代表它的繁殖能力，將直接關(guān)系到后代的質(zhì)量與數(shù)量.在演化計(jì)算中，適應(yīng)度值是用來區(qū)分群體中個(gè)體好壞的標(biāo)準(zhǔn)，是算法演化過程的驅(qū)動(dòng)力，是算法進(jìn)行自然選擇的唯一依據(jù)[4，5].計(jì)算個(gè)體適應(yīng)度值通常會(huì)占用較大的計(jì)算資源，為此，正確地選擇適應(yīng)度函數(shù)對(duì)于演化計(jì)算順利進(jìn)行很關(guān)鍵.

在GEP中，為解決符號(hào)回歸問題，C. Ferreira提出了兩種適應(yīng)度函數(shù)[6,7]：公式(2)是基于絕對(duì)誤差的公式(3)則是基于相對(duì)誤差.

(2)

(3)

其中，M是一個(gè)常數(shù)，表示種群的選擇范圍，在這個(gè)范圍內(nèi)種群開始初始化；C(i,j)表示第i個(gè)染色體利用函數(shù)關(guān)系式在第j個(gè)樣本中的變量數(shù)據(jù)所求得的函數(shù)值；Tj表示第j個(gè)樣本包含的實(shí)際測(cè)量值(比如：有函數(shù)表達(dá)式z=f(x,y)，通過測(cè)量得到一個(gè)樣本(x1,y1,z1)，則C(i,j)=f(x1,y1)，Tj=z1；Ct表示樣本的數(shù)目.顯然，當(dāng)C(i,j)=Tj時(shí)，適應(yīng)度函數(shù)取得最大值fi=fmax=Ct*M.在實(shí)際應(yīng)用中，當(dāng)|C(i,j)-Tj|的精度小于或等于0.01時(shí)，可以認(rèn)為它等于0.

1.3 遺傳算子的設(shè)計(jì)

GEP中有多種遺傳算子，如復(fù)制策略，重組算子，變異算子，插串操作，不同的算子具有不同的功能與作用，利用這些遺傳算子進(jìn)行相關(guān)操作，更新種群，維護(hù)種群中個(gè)體的多樣性.下面分別簡(jiǎn)單介紹.

1.3.1 選擇復(fù)制算子(replication)

使用某種選擇策略對(duì)各個(gè)體分配選擇概率，選擇概率及繁殖概率pr，使用轉(zhuǎn)盤來選擇個(gè)體繁殖，為保證算法的收斂性，我們還采用擇優(yōu)的選擇策略[8]，即將上代最后的個(gè)體保留在當(dāng)前新的群體中.

1.3.2 變異算子(mutation)

變異是從父體中選擇一個(gè)染色體(染色體是由一個(gè)基因或多個(gè)基因組成)，再?gòu)娜旧w中選擇變異的節(jié)點(diǎn)，若選擇的節(jié)點(diǎn)為頭部?jī)?nèi)的節(jié)點(diǎn)，則只能變異為運(yùn)算符集里面的其它元素；若選擇的節(jié)點(diǎn)為身部?jī)?nèi)的節(jié)點(diǎn)，則可變異為運(yùn)算符集和終端集里面的元素；若選擇的節(jié)點(diǎn)為尾部的節(jié)點(diǎn)，則只能變異為終端集里面的元素.對(duì)頭部和身部的節(jié)點(diǎn)變異為其它的節(jié)點(diǎn)可以采取類似于轉(zhuǎn)盤賭選擇策略的辦法[9]來生成變異后的元素，即變異成適應(yīng)值大的運(yùn)算符的概率選擇應(yīng)該較大.

1.3.3 移植算子(transposition)

移植是在一個(gè)染色體內(nèi)部操作，在GEP中有三種不同的移植算子[10]，IS, RIS ,Gene transposition 在這里我們選擇Gene transposition即從染色體中選擇一個(gè)完整的基因，整體移植到這個(gè)染色體另外的一個(gè)基因的位置，其它位置的基因依次的向后移動(dòng)，下面討論的染色體都是由3 個(gè)基因組成的.

012345678012345678012345678*-/aabaab/-q+baaabq+/ababab

把第2 個(gè)基因通過Gene transposition 操作到第1 個(gè)基因的位置上，其結(jié)果

012345678012345678012345678/-q+baaab *-/aabaabq+/ababab

1.3.4 重組算子(recombination)

重組是在不同的染色體間的操作，在GEP中有三種重組算子，單點(diǎn)重組(one-point recombination)，兩點(diǎn)重組(two-point recombination)，基因重組(gene recombination).本算法選擇單點(diǎn)重組(one-point recombination)，隨機(jī)選擇2 個(gè)染色體，然后再隨機(jī)選擇一個(gè)重組點(diǎn)，交換以重組點(diǎn)分界地后面地基因片斷.

2 算法的改進(jìn)

由于GEP線性串和表達(dá)式樹之間的映射關(guān)系，使得它可以在問題求解空間無(wú)約束的搜索，并且產(chǎn)生有效的程序結(jié)構(gòu)，但是在確定程序的結(jié)構(gòu)后，如果參數(shù)選取不當(dāng)也會(huì)導(dǎo)致所建立的系統(tǒng)不穩(wěn)定.因此， 較好的常數(shù)創(chuàng)建對(duì)算法的效率與穩(wěn)定性非常重要.

本文采用由算法本身來創(chuàng)建隨機(jī)常數(shù)，并在程序執(zhí)行過程中根據(jù)適應(yīng)度函數(shù)不斷自適應(yīng)地調(diào)整，本文與文獻(xiàn)[1]中的常數(shù)創(chuàng)建方法不同的是：本文不在基因中引入附加常數(shù)域，而是在基因的終結(jié)點(diǎn)集中引入符號(hào)“?”用來代表臨時(shí)隨機(jī)常數(shù)，并用一個(gè)數(shù)組保存隨機(jī)常數(shù)，在譯碼時(shí)，按順序用數(shù)組中的元素依次替換基因中的“?”.對(duì)常數(shù)的遺傳操作只要對(duì)數(shù)組中的元素進(jìn)行即可.這樣在演化過程中既不會(huì)破壞模型的結(jié)構(gòu)又可節(jié)約內(nèi)存資源和簡(jiǎn)化基因結(jié)構(gòu)，同時(shí)也方便進(jìn)行各種遺傳操作.例如有如下一個(gè)基因：* ? * * ? + ? a a ? ? a ? a ?，保存隨機(jī)常數(shù)的數(shù)組X[10]={0.43, 0.05, 0.576, 0.001, -2.33, 1.178, -0.25, 2.93, 1.33, 0.98}則相應(yīng)的表達(dá)式樹和譯碼后用隨機(jī)常數(shù)替換“?”的表達(dá)式樹* 0.43 * * 0.05 + 0.576 a a 0.01 -2.33 a 1.178 a -0.25，對(duì)常數(shù)的雜交操作采用算術(shù)雜交如公式(4)所示.

(4)

3 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析

本文的實(shí)驗(yàn)數(shù)據(jù)來源于Rob Hyndman網(wǎng)站http:∥www-personal.buseco.edu.an/～hyndman.中整理的關(guān)于宏觀經(jīng)濟(jì)預(yù)測(cè)的數(shù)據(jù).該數(shù)據(jù)是美國(guó)紐約San Francisco 1915年到1996年的電話費(fèi)用數(shù)據(jù)，數(shù)據(jù)具體內(nèi)容請(qǐng)參考網(wǎng)站上的數(shù)據(jù). 此數(shù)據(jù)集中共有984組數(shù)據(jù), 本實(shí)驗(yàn)中采用數(shù)據(jù)集中后30組數(shù)據(jù)作為預(yù)測(cè)數(shù)據(jù), 前面的30組數(shù)據(jù)均作為訓(xùn)練樣本數(shù)據(jù).

3.1 實(shí)驗(yàn)公共參數(shù)設(shè)置

算法參數(shù)設(shè)置如表1所示.

表1 GEP實(shí)驗(yàn)公共參數(shù)設(shè)置

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

實(shí)驗(yàn)選用函數(shù)集F={+, -, *, /}，終結(jié)點(diǎn)集T={x0,x1,x2,x3,x4,x5,x6,x7,x8,x9}，使用隨機(jī)常數(shù)(不完整).實(shí)驗(yàn)運(yùn)行10次找出較好模型為

F=x0/(((x8+x2)*x3)/x8)-x4)+x1)/(x3*x3)+x7+x7/(x2*x2)+(((x6/x3)-(x6-x9))/(x1*x2))*x5+((x0*(x9-x7))-1.203*x8)/x3+0.56*x0/(x1+((x4+x9)-x3)/x9+(x1-x8)/x9 .

(5)

模型(5)的擬合誤差按公式(6)計(jì)算，

(6)

該模型所得的擬合誤差Q=6.987 490，預(yù)測(cè)誤差為0.389 066.擬合結(jié)果如圖3所示.

圖3 訓(xùn)練數(shù)據(jù)集預(yù)測(cè)曲線

3.3 結(jié)果分析

從圖3可以看出，利用本文的算法能很好地對(duì)訓(xùn)練數(shù)據(jù)進(jìn)行擬合，而且誤差在理想范圍內(nèi)，較好地反映真實(shí)情況.通過對(duì)以往樣本數(shù)據(jù)進(jìn)行擬合,本文算法也具有一定效果.

基因表達(dá)式程序設(shè)計(jì)是一種新的自適應(yīng)進(jìn)化算法，具有較好的自組織、自適應(yīng)等特征，文章選用合適的適應(yīng)度函數(shù), 對(duì)常數(shù)創(chuàng)建方法進(jìn)行改進(jìn)，引入附加常數(shù)域，并設(shè)計(jì)算法的遺傳算子與選擇策略, 最后把本文算法應(yīng)用來解決宏觀經(jīng)濟(jì)的預(yù)測(cè)問題.結(jié)果表明，本文算法能自動(dòng)找到較好的模型，并能根據(jù)所上面所創(chuàng)建的模型進(jìn)行較為準(zhǔn)確的預(yù)測(cè).