遺傳規劃自適應建模的JAVA實現及在股票價格預測中的應用

葛志遠　陳會濤

(北京工業大學經濟與管理學院　北京 100124)

?

遺傳規劃自適應建模的JAVA實現及在股票價格預測中的應用

葛志遠陳會濤

(北京工業大學經濟與管理學院北京 100124)

針對如何將遺傳規劃方法與時間序列有效結合，構建基于遺傳規劃的時間序列自適應模型，并通過Java語言輔助算法的實現。相比之前遺傳規劃算法，采用平均值法改進初始群體的生成方式，使變異概率隨著進化代數的增加而遞減，且加入并行計算思想。在算法流程的核心計算環節,將適應度值的計算、個體的復制、交叉、變異操作都從線程的粒度來進行，基于實際運行效果來看，CPU多核運行明顯，算法能夠充分利用多處理器、多核進行計算，提高了運行效率。將改進的遺傳規劃模型應用于我國股票市場上股票價格的預測，將預測結果與經遺傳算法優化的神經網絡方法和傳統遺傳規劃方法進行比較，結果證明改進遺傳規劃方法的預測精度更高，且能夠更直觀地表達輸入與輸出之間的關系。

遺傳規劃時間序列自適應建模股票價格預測

0　引　言

時間序列分析是指通過描述分析歷史數據隨時間變化的規律，預測事物的未來發展趨勢，其在經濟預測領域的研究過程中發揮著重要的作用。在股票市場上，時間序列分析可以用于對股票的未來價格趨勢進行預測，其結果可為股票市場的管理者和投資者提供決策依據。

然而由于股票市場是一個比較復雜的非線性非平穩系統，它同時受多種因素的交互影響，有些因素較容易度量，而有些因素卻難以量化。如果對其進行科學的計算和評價,僅用傳統的統計理論和方法已不能滿足對該領域進行深入研究的需要，迫切需要前沿理論和新技術的充實。

從股票預測方法的研究現狀來看，國內外已有其他學者運用不同的方法對股票市場進行預測研究。Khashei等人[1]認為ARIMA模型能夠較好地處理金融時間序列數據的非線性性質,將ARIMA應用于金融時間序列的分析。Sun等[2]使用RBF神經網絡模型和K均值算法對上證股票價格指數進行預測。尚朝輝等[3]使用遺傳規劃構建了基于遺傳編程理論的股票技術交易模型，證明該模型可以為股票買賣提供策略。Kazem等人[4]建立了基于支持向量機的預測模型來預測股票的市場價格，并以微軟的收盤價進行實證研究。肖菁等[5]運用遺傳算法優化神經網絡的權值和閾值建立了改進的三層BP神經網絡股票預測模型。Mirchandani等人[6]使用遺傳算法優化神經網絡，建立股票價格預測模型，并以孟買股票市場實證研究，結果顯示預測準確率介于50%～80%之間。

通過查閱分析相關文獻，發現基于統計學的股票時間序列的研究一般是建立在股票收益率是獨立的、符合正態分布的假設上；支持向量機方法的長記憶性較差且實施大規模訓練樣本較難，比較適合對小樣本數據進行學習和預測。文獻中，關于遺傳規劃算法在股票價格預測領域的研究，大多數研究者是把遺傳算法與神經網絡相結合，構建出混合模型。但是通過分析發現，在使用遺傳規劃算法優化神經網絡方法的過程中，需要對問題本身有深刻的了解和很好的判斷，整個混合系統的性能要依賴于其他因素，難以使得所有因子達到最優化，一般比較難獲得較好的ANN模型。且神經網絡方法本身是一種黑盒的方法，對于表達并分析被預測系統的輸入與輸出之間的聯系有一定的難度，所以也較難對最終的結果進行完整的解釋和檢驗。

遺傳規劃(GP)是從遺傳算法(GA)中演化和發展起來的一種搜索尋優技術[7]。兩者的主要不同之處是個體表示結構和對數據的處理方式不同[8]。遺傳算法是使用定長的字符串(通常是二進制)來描述問題，而遺傳規劃是用廣義的層次化計算機程序來描述問題，遺傳算法的這種固定的大小，限制了它的應用，使它無法描述一些大小結構變化的問題，缺乏動態可變性。同時由于要事先對字符串的長度進行估計，可能會使結果不夠準確，甚至找不到全局最優解，而遺傳規劃恰好彌補了此方面不足。

基于遺傳規劃的自適應建模在很多領域均有應用價值。遺傳規劃方法有著強大的符號回歸和處理非線性的能力，可以容易地顯性表達輸出變量與輸入變量間的非線性關系。近年來許多學者對遺傳規劃算法及應用做了大量的研究工作，在實際的應用中取得了很大成功，如今它已成功地被應用于預測[9]、分類[10]、機器學習[11]、圖像處理[12]以及數據挖掘[13]等領域。

本文首先介紹了基于遺傳規劃的自適應建模算法,將遺傳規劃與時間序列相結合,構建了基于遺傳規劃的時間序列自適應模型，并使用Java語言輔助GP自適應算法的實現。然后將GP算法模型應用于我國某支股票價格的預測，相比傳統遺傳規劃算法和GA優化神經網絡方法，該算法具有良好的結構逼近性能和較高的預測精度。

1　基于遺傳規劃的時間序列自適應建模

遺傳規劃的基本原理是，首先隨機產生符合所要解決問題環境的初始群體，構成算法的搜索空間。該群體的每個個體都有一個適應度值，按照“優勝劣汰”的選擇法則，用三種遺傳算子依次處理擁有較高適應度值的個體，然后產生下一代群體,直到達到所設定的終止條件則結束循環。遺傳規劃最重要的特點是群體中的個體是用動態的樹狀結構組成，樹狀結構的層和節點都是可以動態變化的。

遺傳規劃方法的主要步驟如下：

(1) 確定個體的表達方式。遺傳規劃算法最常見的編碼形式為由列表和原子構成LISP的S表達式。其中，列表對應樹結構的非葉子節點，原子對應樹結構的葉子節點。非葉子節點由運算符和初等函數組成，葉子節點包含變量與常量，通常為適用于問題空間領域的最基本元素。

(2) 隨機生成初始群體。非葉子節點集和葉子節點集中的基本元素按一定的隨機選擇方法組合生成初始個體，初始個體達到規定的數目之后組成一個初始群體。本文對傳統算法進行改進，采用平均值法生成初始群體：即首先生成M個個體,求它們的平均適應度,當新生成個體的適應度比當前平均適應度值大的時候，個體即被保留下來。重復此過程,直到保留下來的個體數達到M個為止。此種產生初始群體的方法對于每組個體而言,組平均適應度是一個逐步提高的過程,可以提高初始種群個體的整體適應度和算法的整體收斂效率。

(3) 個體適應度值計算。適應度值是衡量個體對環境適應能力強弱的指標，是個體表達式逼近真實解的近似程度。本文引入適應度函數：

其中yi表示第i個觀測值，T表示觀測值的個數，yi是根據函數表達式得到的與yi相對應的第i個預測值，u表示觀測值的平均值。

(4) 根據設定的遺傳參數對群體中的個體進行復制、交叉和變異遺傳算子操作，以此產生新一代的個體。本文把當前種群中具有最高適應度的函數直接保留到下一代,以保證每代中的最優個體不被破壞。其中，變異操作屬于輔助算子，對保持種群的多樣性功能起著重要的作用，在進化初期，個體的適應度相對較差，因此，本文在進化初期采用較大的變異概率對群體中適應度較差的個體進行變異以加快進化速度。

(5) 重復(3)和(4)，直到滿足設定的終止準則，終止準則一般有：運行進化到規定迭代次數或進化達到規定的允許誤差。

遺傳規劃的整體工作流程如圖1所示。

圖1　遺傳規劃算法流程圖

基于遺傳規劃算法的整個建模過程不依賴于具體問題領域的特定知識即可動態地生成搜索空間。從演化結果和外推與內插的特性方面來看，遺傳規劃建模方法比人工神經網絡更優越的地方是其能得到簡單的顯式表達式。在這樣的背景下，使用遺傳規劃算法進行數據擬合，可以不需要確定方程的具體結構，而只需將數據交給計算機，設定一個精度，然后在經過幾十代甚至幾百代后，就可以得到符合自由曲線變化規律的數學表達式。

我們根據如上所述的基于遺傳規劃的自適應建模算法，結合時間序列元素，建立股票價格預測模型。根據需求功能特性的描述，將算法的功能劃分為四個模塊：模型個體的編碼模塊、基于遺傳規劃的算法模塊、系統的控制界面以及數據接口模塊。如圖2所示，算法的基本原理是通過遺傳規劃算法的搜索求解功能，通過研究對象自身的歷史數據，來尋找符合研究對象特征的最優模型。

圖2　基于遺傳規劃的股價預測模型及算法模塊劃分

2　算法設計

遺傳規劃方法的任務是，從許多候選的自動生成求解實際問題的計算機程序所組成的搜索空間中，通過優化尋找出一個具有最佳適應度的計算機程序。Java語言是一種可以撰寫跨平臺應用軟件的面向對象的程序設計語言。因此本文使用Java編程語言[14]輔助算法的實現，通過面向對象的思想和方式，幫助我們實現對所要解決的問題進行抽象與建模，也更利于用我們易理解的方式對算法進行分析、設計與編程。同時開發了MySQL數據庫接口，建模采用的原始數據保存在MySQL數據庫中，在安裝了標準的Java1.7虛擬機的電腦上運行。

2.1結構設計

(1) 二叉樹

本算法用到的典型的數據結構是二叉樹結構。系統使用二叉樹結構來描述模型，即：樹結構中的非終端節點為函數，包括簡單的計算操作(﹢、-、*、/)、函數(sin,cos,tan,exp,power,log)等。樹結構的終端節點為變量或者常量，從而使得一棵二叉樹即是一個模型表達式。

在上述結構中，簡單的計算操作是二元的，函數有一元的，也有二元的。由這些元素組成的樹結構中，每個節點至多有兩個孩子節點。本文直接采用二叉樹來表示。

(2) 數組列表ArrayList

遺傳規劃算法的個體種群采用ArrayList結構。ArrayList結構是一種線性數據結構形式，它會在刪除掉某些元素時自動縮小，這樣就不必檢查個體種群中所有的元素，只需要查詢它是否帶有要尋找中的值就好。

(3) 矩陣Matrix

原始數據采用矩陣的數據結構來表示。不論是待擬合系統的輸入數據，還是輸出數據，均采用矩陣結構。采用矩陣結構來描述數據的另一個好處是可擴展性。例如對于多變量聯立方程組模型，矩陣結構就能夠很輕松實現，而對于向量式的數據結構就難以描述多變量聯立方程組。

2.2數據接口設計

本算法通過主模型中的getData方法。實現對外部數據的讀取，在算法的主模型GpModel類中，設計了一個方法getData()，該方法實現從數據庫中讀取數據，并且在模型的初始化方法init()中調用，從而使得算法模型與外部數據關聯。如果要使用系統應用于其他領域的建模，只需要重寫getData()方法。

2.3并行算法設計

由于我們的算法需要大量的運算，通常群體的大小在幾百以上，進化的代數也在幾百以上，這僅是小規模的運算。因此，從性能上考慮，充分利用CPU以及多核，將能夠提高算法的運行效率。基于以上考慮，我們在算法流程的核心計算環節,將適應度值的計算、兩個個體的交叉操作、個體的變異操作、個體的復制操作都從線程的粒度來進行，從而使得算法能夠充分利用多處理器、多核來進行計算。

算法的并行流程如下：

begin

(1)initialization

產生一個初始群體

(2)whilerunningdo

(2.1) 并行評估整個群體的適應度值

(2.2) 判斷是否已經達到搜索終止條件

(2.3) 并行進行遺傳算子的操作

選擇父代

根據隨機概率進行交叉操作、復制操作和變異操作

//this.fileout();

//保存排序之前的數據

(2.4) 子代取代父代，形成新一代個體

endwhile

end

算法采用線程的方式來進行并行計算,使得多計算資源下解決問題的耗時少于單個計算資源下的耗時，因此提高了計算機系統的處理能力和計算速度，與此同時算法的效率大為提升?；趯嶋H的運行效果可以看出，CPU多核運行是明顯的，并且還沒有達到飽和運行的狀態。

2.4算法主程序設計

系統的主程序是GPMainFrame.java，這個類也是系統的主界面。在這個類中定義了遺傳規劃模型GpModel.java的一個實例，從而進行基于遺傳規劃的算法操作。

算法主程序GpModel.java中進行算法進化的主流程代碼如下：

publicvoidevolution() {

while(round

//操作界面有一個按鈕，用來設置stop標志位

round++;

this.calculateFitness();//計算群體適應值，是并行計算

this.sortPopulation();

//排序

this.fileout();

//保存數據

if(this.achieveGoal())stop=true;

//如果達到目標要求，則進化結束

this.resetNextGen();

//初始化下一代個體

this.operator();

//進行遺傳操作，完成一整代個體的更新

this.updateGeneration();

//下一代群體替代現有群體

}

}

3　算法實現

從功能的角度,要實現基于遺傳規劃的時間序列自適應建模算法，需要實現以下幾個方面的算法：

(1) 數符號集與終端節點集的表達。系統需要定義好通用的數學表達式中的函數符號集、常數和變量集。除此以外，需要留有用戶自定義變量集的接口，比如用戶需定義n個變量，那么，系統能夠很方便地實現具有n個變量的數學表達式的生成與進化。

(2) 模型個體的編碼與解碼。模型個體是由二叉樹結構組成，在生成模型個體的時候，直接以二叉樹結構來表示，而解碼則是通過遍歷將二叉樹個體以字符串方式，按照通常數學表達式的語法來輸出。

(3) 遺傳規劃算法的進化。實現模型個體的適應值評價、各遺傳算子(復制、交叉和變異)的操作。

(4) 基本的算法控制界面。包括算法進化的開始、暫停進化和輸出算法當前搜索的結果。算法進化的開始包括群體的初始化、進化循環啟動功能；暫停進化主要是將進化循環條件置為false；當前結果的輸出則是以文本的方式展示當前群體。

(5) 算法與模擬系統的數據接口。系統能夠讀取數據庫中設定的數據，然后根據算法來完成建模。

我們的主要任務是實現算法的過程，不需要復雜的操作界面。由于基于文本的命令行界面，需要操作者掌握很多復雜的命令語句與參數，非計算機專業的使用者很難接受這種使用起來不直觀的界面。隨著人際交互技術的日益發展，界面友好的圖形用戶接口(GUI)越來越受到大家歡迎。因此，當前為算法過程的監控和實現設計了一個簡單的圖形用戶界面。在界面中左側有“開始”、“刷新”、“繼續”和“暫?！彼膫€按鈕，右側是一個顯示算法演化過程中生成的模型情況的文本框。其中“開始”按鈕用于啟動建模算法，“刷新”按鈕則將在界面的右邊的文本框中添加當前的模型進化情況，“暫?！卑粹o則可以中止當前的算法循環，“繼續”按鈕可以恢復由于“暫停”按鈕所中止的循環。

算法的軟件包如圖3所示。

圖3　算法軟件包

4　應用研究

4.1樣本數據

由于算法的靈活性，我們可以對任意一只股票的每日收盤價在任意區段內的時間序列進行建模。使用CSMAR數據庫查詢系統，本文選取了中信銀行(代碼601998)從2011年1月4日至2011年12月30日區間的股票收盤價作為建模的樣本數據,共234個工作日數據,選取前224個收盤價作為訓練樣本,通過分析這些歷史數據建立遺傳規劃模型,然后預測后10天的收盤價。

4.2參數選擇

算法的基本參數設置如表1所示。

表1　GP算法基本參數

為了保證模型的復雜度，避免群體中產生大量的Xt-1及類似的個體，我們在初始群體生成時人為地增加了函數節點產生的概率，并且隨著個體生成時二叉樹的層級的增加使用線性遞減函數來降低函數節點的生成概率。

4.3結果分析

一般的股票價格預測模型需要事先設定具體的函數形式及具備一些假設前提條件，而遺傳規劃方法從數據出發，無需對初始數據進行預處理,能自動生成并尋找函數關系。將所確定的模型用簡單明了的結構形式顯式表達，具有很強的解釋性，在對輸入輸出數據進行無需大量預處理的情況下，即能準確找到適合數據所呈現的規律的模型。這里所說的無需大量預處理即是無需對輸入輸出數據進行歸一化和平穩化處理。表2列出了經10次運算后此支股票價格自適應建模算法得到適應度最好的模型。

表2　選取最優模型

對表2模型進行簡化，得到的模型如下：

GP模型：Xt-1-0.0017×Xt-4+0.0003×Xt-10

為了討論上述模型的合理性，我們應用理論分析的方法，對該時間序列建立經遺傳算法(GA)優化的神經網絡模型以及傳統GP模型，以評價算法的可行性。

分別用本文改進的GP模型與文獻[6]中提出的GA優化的神經網絡方法以及傳統GP算法3個不同的算法對2011年12月16日至2011年12月30日共10個工作日數據進行預測，其中對改進前后的GP算法各運行10次，分析運算性能如表3所示。

表3　運算性能比較

從表3可以看出，相對傳統GP算法，經改進的GP并行算法收斂次數較多，且平均CPU耗時較少。

三種方法的實際預測結果如表4和圖4所示。

表4　實際值與各模型預測值比較

圖4　各模型預測效果圖

計算各個模型預測值與實際值的相對誤差如表5所示。

表5　各模型相對誤差比較

由表5可以看出，GP模型中預測值的相對誤差普遍較低，最小是0.00%，預測值均在實際值附近浮動,GA優化神經網絡次之，傳統GP算法模型中的相對誤差較大。

為了更加全面地描述三個不同模型對股票價格的預測效果,本文采用平均絕對百分比誤差(MAPE) 和均方根誤差(RMSE) 兩個指標來衡量模型預測效果的好壞(第一個指標是相對指標,第二個指標是絕對指標)。兩個評價指標的定義分別為:

表6　各模型預測效果比較

從表6可以看出，無論是MAPE還是RMSE,改進遺傳規劃模型的預測誤差都小于GA優化神經網絡模型和傳統GP模型，表明改進遺傳規劃方法預測效果優于另外兩種模型，而GA優化神經網絡模型的預測效果又優于傳統GP模型。

進一步分析GP模型的結構：Xt-1-0.0017×Xt-4+ 0.0003×Xt-10，包含元素Xt-1，Xt-4，Xt-10，分別代表N天前的收盤價。這說明第t-1天，t-4天，和t-10天對第t天股票價格的關聯和影響比較大，即是說股票價格的歷史數據對未來的價格產生著一定程度影響，股票價格并不完全是隨機的。另一方面，遺傳規劃自適應建模的結果中含有Xt-10元素，證明遺傳規劃方法具有較強的自適應搜索能力，可以準確地找出影響股票價格變化的因素。

5　結　語

本文通過Java實現的遺傳規劃并行算法具有強大的啟發式搜索尋優能力。從運行過程看到，算法具有較快的運算速度和結構逼近性能，證明該算法在處理股票價格數據這種非線性時間序列預測方面具有較好的應用價值。在股票預測領域運用遺傳規劃方法的自適應搜索特性建模，能很快找到影響股票價格變化的影響因子，提高預測的精度，從另一個角度證實了遺傳規劃的自適應建模在預測領域的優越性。而且在處理歷史數據中，采用遺傳規劃進行數據擬合時，不需要預先確定方程的結構形式，不需對數據進行預處理，大大減輕了我們在數據處理方面的工作量。相比神經網絡的黑箱方法，GP方法建模結果具有多樣性，可以比較容易且直觀地表達并分析被預測系統的輸入與輸出之間的聯系。從預測結果還可以看出股票市場的未來價格變化并不能認為是完全隨機的，其有受到過去一段時間歷史價格的影響。因此，投資者在股票市場投資時，把過去的價格變化因素考慮在內，有助于股票投資者在一定程度上做出正確的決策。

[1]KhasheiMehdi,RafieiFarimahMokhatab,BijariMehdi.HybridFuzzyAuto-RegressiveIntegratedMovingAverageModelforForecastingtheForeignExchangeMarkets[J].InternationalJournalofComputationalIntelligenceSystems,2013,6(5):954-968.

[2]SunBin,LiTieke.ForecastingandIdentificationofStockMarketbasedonModifiedRBFNeuralNetwork[C]//Proceedingsof2010IEEEthe17thInternationalConferenceonIndustrialEngineeringandEngineeringManagement,Xiamen,IEEE,2010(1):424-427.

[3] 尚朝輝，甄九州.基于遺傳編程的技術分析在股票市場預測中的建模與應用[J].首都經濟貿易大學學報，2014,16(2):28-35.

[4]KazemAhmad,SharifiEbrahim,HussainFarookhKhadeer.Supportvectorregressionwithchaos-basedfireflyalgorithmforstockmarketpriceforecasting[J].AppliedSoftComputing，2013,13(2):947-958.

[5] 肖菁，潘中亮.股票價格短期預測的LM遺傳神經網絡算法[J].計算機應用2012,32(S1)：144-146.

[6]MirchandaniBhisham,ShahCinjal,NagarshethKaushal.StockMarketTrendPredictionMarquardtNeuralNetworkOptimizedbyGeneticAlgorithm[C]//Phuket：4thInternationalConferenceonSoftwareTechnologyandEngineering,2012： 521-527.

[7] 王宇平.進化計算的理論和方法[M].北京：科學出版社，2011.

[8] 王璐.遺傳算法與遺傳規劃的對比性研究[D].吉林：吉林大學，2011.

[9] 黃安強，李夢，楊豐梅.基于改進遺傳規劃算法的非線性集成預測新方法[J].系統科學與數學,2013，33(11)：1332-1344.

[10] 王璞.基于遺傳規劃的分類算法研究[D].合肥:中國科學技術大學,2013.

[11] 李擎,張超,徐銀梅,等.基于專用遺傳算法和改進粒子群算法的移動機器人路徑規劃[C]//安徽：第三十一屆中國控制會議論文集D卷，2012：830-838.

[12] 林齡，潘峰.一種基于遺傳規劃的多特征圖像排序算法[J].計算機應用與軟件，2013,30(12)：190-193.

[13] 王安華.遺傳規劃在非復雜業務流程挖掘中的應用研究[D].上海:復旦大學,2010.

[14]CaySHorstmann,GaryComell.JAVA核心技術(卷1)[M].北京：機械工業出版社,2008.

IMPLEMENTINGJAVAINGENETICPROGRAMMINGADAPTIVEMODELLINGANDITSAPPLICATIONINSTOCKPRICEPREDICTION

GeZhiyuanChenHuitao

(School of Economics and Management,Beijing University of Technology,Beijing 100124,China)

Aimingatthewaytocombinethegeneticprogrammingmethodwithtimeserieseffectively,webuiltthegeneticprogramming-basedadaptivetimeseriesmodel,andimplementeditbyJavalanguageassistedalgorithm.Comparedwithpreviousgeneticprogrammingalgorithm,itusestheaveragevaluemethodtoimprovethegenerationmannerofinitialpopulation,makesthemutationprobabilitydecreasealongwiththeincreaseofevolutionalgebra.Moreover,theideaofparallelcomputingisintroduced,inthecorepartofthealgorithm,thecalculationoffitnessvalue,theoperationsofindividualcopy,thecrossoverandthemutationarecarriedoutfromthethreadgranularity.Basedontheactualoperationresults,theCPUoperatesclearlyinmulti-coremode,thealgorithmcantakefulladvantagesofmulti-processorandmulti-coreincomputationandthisimprovestheefficiencyofoperation.ApplyingthegeneticprogrammingmodeltothepredictionofstockspricesinChina’ssecuritiesmarket,wecomparedthepredictionresultswiththatoftheartificialneuralnetworkoptimisedbygeneticalgorithmandthetraditionalgeneticprogramming,resultsshowedthatthepredictionprecisionoftheimprovedgeneticprogrammingwashigher,andcouldmoreintuitivelyexpresstherelationshipbetweeninputandoutput.

GeneticprogrammingTimeseriesAdaptivemodellingStockpricePrediction

2014-08-13。葛志遠，副教授，主研領域：Web技術，管理模型，遺傳規劃。陳會濤，碩士生。

TP311.1

ADOI:10.3969/j.issn.1000-386x.2016.03.027