基因表達式程序設計在宏觀經濟預測中的應用

鄢靖豐

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

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

1 GEP算法思路框架與實現過程

圖1 算法流程圖

GEP求解函數優化與建模問題主要包括GEP個體編碼及表示、適應度函數設計、常數創建以及GEP的遺傳操作等，算法求解一般問題的思路框架如圖1所示.

1.1 算法編碼方案

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

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

(1)

圖2 基因表達樹

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

1.2 適應度函數的設計

在自然界中，個體適應度值就是代表它的繁殖能力，將直接關系到后代的質量與數量.在演化計算中，適應度值是用來區分群體中個體好壞的標準，是算法演化過程的驅動力，是算法進行自然選擇的唯一依據[4，5].計算個體適應度值通常會占用較大的計算資源，為此，正確地選擇適應度函數對于演化計算順利進行很關鍵.

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

(2)

(3)

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

1.3 遺傳算子的設計

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

1.3.1 選擇復制算子(replication)

使用某種選擇策略對各個體分配選擇概率，選擇概率及繁殖概率pr，使用轉盤來選擇個體繁殖，為保證算法的收斂性，我們還采用擇優的選擇策略[8]，即將上代最后的個體保留在當前新的群體中.

1.3.2 變異算子(mutation)

變異是從父體中選擇一個染色體(染色體是由一個基因或多個基因組成)，再從染色體中選擇變異的節點，若選擇的節點為頭部內的節點，則只能變異為運算符集里面的其它元素；若選擇的節點為身部內的節點，則可變異為運算符集和終端集里面的元素；若選擇的節點為尾部的節點，則只能變異為終端集里面的元素.對頭部和身部的節點變異為其它的節點可以采取類似于轉盤賭選擇策略的辦法[9]來生成變異后的元素，即變異成適應值大的運算符的概率選擇應該較大.

1.3.3 移植算子(transposition)

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

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

把第2 個基因通過Gene transposition 操作到第1 個基因的位置上，其結果

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

1.3.4 重組算子(recombination)

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

2 算法的改進

由于GEP線性串和表達式樹之間的映射關系，使得它可以在問題求解空間無約束的搜索，并且產生有效的程序結構，但是在確定程序的結構后，如果參數選取不當也會導致所建立的系統不穩定.因此， 較好的常數創建對算法的效率與穩定性非常重要.

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

(4)

3 實驗數據與結果分析

本文的實驗數據來源于Rob Hyndman網站http:∥www-personal.buseco.edu.an/～hyndman.中整理的關于宏觀經濟預測的數據.該數據是美國紐約San Francisco 1915年到1996年的電話費用數據，數據具體內容請參考網站上的數據. 此數據集中共有984組數據, 本實驗中采用數據集中后30組數據作為預測數據, 前面的30組數據均作為訓練樣本數據.

3.1 實驗公共參數設置

算法參數設置如表1所示.

表1 GEP實驗公共參數設置

3.2 實驗

實驗選用函數集F={+, -, *, /}，終結點集T={x0,x1,x2,x3,x4,x5,x6,x7,x8,x9}，使用隨機常數(不完整).實驗運行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)計算，

(6)

該模型所得的擬合誤差Q=6.987 490，預測誤差為0.389 066.擬合結果如圖3所示.

圖3 訓練數據集預測曲線

3.3 結果分析

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

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