基于基因表達式編程的私人汽車擁有量建模和預測

摘 要:準確預測私人汽車擁有量，對制定經濟政策和進行經濟宏觀調控、保證社會經濟和諧發展有重要的作用。基因表達式編程(GEP)是新的進化模型，在數據挖掘領域得到了廣泛的關注和研究，對符號回歸任務表現了很強的優勢。闡述了GEP基本原理，GEP進行序列分析的基本方法;根據1990—2007年全國和人汽車擁有量，基于GEP技術挖掘到了其模型。實驗表明，基于GEP技術得到的私人汽車擁有量模型預測精度高、泛化能力強。

關鍵詞:基因表達式編程; 私人汽車量; 預測; 泛化能力

中圖分類號:TP202.7文獻標志碼:A

文章編號:1001-3695(2010)03-0958-03

doi:10.3969/j.issn.10013695.2010.03.041

Modeling and predicting total number of private cars based on GEP

ZHU Ming-fang1a ， WANG Hong-tao2， REN Yanling1b

(1.a.School of Computer Technology， b.School of Electronic Information， Jiangsu Teachers University of Technology， Changzhou Jiangsu 213001， China; 2.Dept. of Computer Science Technolgy， Shaanxi University of Technology， Hanzhong Shaanxi 723001， China)

Abstract:For making economic policies and controlling macro economy， it needs predict the total numbers of private cars. It is a vital role to ensure harmoniously develops the economics. Gene expression programming (GEP) is a novel evolution system and attracts many studies and attention.This paper introduced the principle of GEP， and the basic methods applied GEP to time series analysis. According to the total number of private cars from 1990 to 2007， based on GEP techniques， mined and analyzed prediction model. Illustrating from experiments， the model has a high prediction precision， and good generalization ability.

Key words:gene expression programming(GEP); total number of private cars; prediction; generalization ability

隨著社會經濟的發展、人民生活水平的提高，私家車已經走入了人們的生活，其擁有量反映了人民生活的水平和質量。近幾年，我國私家車擁有量迅速增長，在為人們提供交通便利的同時，也給道路交通部門、政府部門以及人們生活的小區等提出新的課題。在進行道路設計、城市規劃、小區建設時，車輛的流量和停位已經成為一個重要的考慮因素，它也是政府進行石油能源的定價、經濟宏觀調控的主要因素。

準確的預測是科學規劃、有效進行工作部署和實效管理的前提和依據，而準確的預測是建立在事物發展規律基礎上的科學推斷。社會經濟系統是一個開放的大系統，要研究事物的發展變化規律，需要分析與考察問題相關的其他因素，而這些因素的提取和抽象是一項十分困難的任務。如果積累了事物發展的一些歷史數據，則時間序列分析是一個很好的技術。為了預測私人擁有汽車量，本文使用我國近幾年來私家車擁有量的歷史數據，通過歷史數據建立預測模型，從而對私家車擁有量進行預測。

近幾年來，已經出現了將許多預測技術運用到私家車擁有量預測的問題上，諸如灰色系統理論[1]、多元線性回歸分析法[2]、最小二乘法及多項式擬合技術以及神經網絡算法等。這些方法存在以下問題:人為選定預測模型的結構，然后通過統計方法對模型中的參數進行確定，主觀因素濃厚;需要考察與預測變量相關的其他因素，增加了研究難度等。本文應用GEP技術對我國私家車擁有量進行預測研究，GEP在不必預先知道預測模型的結構和參數、不必具備領域背景知識前提下，通過進化能得到結構簡單、預測精度高的模型，避免了對系統進行機理分析建立其預測模型的困難，避免了以回歸方法為基礎的預先設定模型結構，然后通過統計方法確定參數的主觀性。

1 GEP簡介

基因表達式編程[3](GEP) 由Ferreira于2001年提出，是數據挖掘的新方法，是遺傳算法家族新成員。其特點是將遺傳操作和個體評價的實體相分離，即它是基因型和表現型分離進化算法，是發展完備的遺傳算法，其進化效率比其先輩GP快2~4個數量級。近些年來，它在數據挖掘領域得到了廣泛的關注和研究，已成功應用到函數發現[3，4]、組合優化[5]、分類[6]、聚類[7]、關聯規則[8]、時間序列預測[9]等領域。

GEP的基因型是由頭部和尾部組成的有結構的線性實體，頭部可以包含函數符號(取自函數集FS)和終結符號(取自終結符集TS)，尾部只能包含終結符號。對每個待解決的問題，頭部長度h預先指定，尾部長度t和頭部長度有如式(1)的關系。

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

其中:n表示函數集中函數最大的參數數目。

GEP線性固定長度的基因和柔性分支結構的表達樹間的轉換依賴Karva語言，該語言簡單直觀，實現了GEP的基因編/解碼。

例1 設FS={Q，*，/，-，+}，TS={a，b}，則n=2。若h=15，則t=16，整個基因的長度g=15+16=31。下面是一個可能的基因G1，尾部用粗體標記。

G1: /a Q/b*a b/Qa*b*-ababaababbabbbba

該基因經Karva解碼，其表達樹ET有八個節點，如圖1所示。

基因G1的長度是31，開放閱讀區(open reading frame， ORF)長度只有7，位置8~30形成基因的中性區，GEP的中性區以及發生在其上的遺傳操作是進化成功的關鍵因素。該基因的數學表達式為a/Q(b/(ab))。

GEP有效進化的又一重要因素染色體(基因組)是由多基因組成。一般地，染色體由一個或幾個等長的基因組成，每個基因解碼為一個子表達樹(subET)，各子表達樹通過連接函數形成更復雜的多子單元的表達樹(multisubunit ET)。

例2 設染色體有三個基因，其中h=6， FS={+，-，*，/，Q}，TS={a，b}，則染色體的長度是39，取連接函數是“+”。

圖2是一個可能染色體和對應的各個子表達樹，圖3是染色體的表達樹。

遺傳操作是遺傳算法的核心和精髓。因為GEP遺傳操作發生在染色體的具有線性結構的基因型上，所以GEP有相當豐富的遺傳算子，除了選擇、復制外，還有變異、逆串、轉位和重組等基因突變型算子。需要強調的是，GEP的基因在任何遺傳操作之后，只要保證基因的結構不變，即保證基因的頭部和尾部的內容滿足要求，則基因總是表達一個合法程序。

變異操作可以在染色體的任何位置操作，只要保持染色體的組織結構不變，經變異后產生的新個體均是合法的程序，即基因頭元素可變異成任何FS或TS中的元素，而基因尾元素只能變異成TS中的元素，它是GEP技術中最重要的算子。逆算子限定在GEP基因的頭部，隨機選取頭部的兩個位置，將這兩個位置之間的符號串取逆來引起基因突變的算子，是GEP中重要的操作算子作用。轉位算子是選中基因的一個片斷，它遷移到基因的另外一個位置。有三種轉位算子，即插串算子(IS)、根插串算子(RIS)和基因插串。重組是交換雙親染色體之間的等位基因的一種遺傳操作，有三種重組，即單點重組、兩點重組和基因重組。這些算子的技術細節參見文獻[10]。

2 基于GEP的時間序列預測

2.1 時間序列分析

時間序列分析的任務就是通過分析序列中歷史數據所包含的信息，發現其中所蘊涵的變化規律，為其建立數學模型，運用數據模型進行分析、預測和控制。在經濟、工程和其他各種領域中，到處都存在著需要進一步研究的時間序列，如國家或地方的經濟分析、股市行情分析等都屬于時間序列分析的范疇。對許多問題的研究和解決也就是要研究清楚有關時間序列的發展規律，實現準確的估計、預測和控制。可見，時間序列的分析研究具有非常重要的意義。

GEP技術是一個通過人工智能進行數學建模的工具，所以GEP在符號回歸(函數發現)領域研究得最深入，得到成果也最為豐富，同時也表現了強大的挖掘能力。時間序列分析問題是一類特殊的符號回歸問題，它是利用時間序列的歷史數據和當前數據對未來數據進行預測和控制。若將歷史數據和當前數據看做自變量，未來的預測數據看做因變量，則可將時間序列分析轉換成典型的多變量符號回歸問題，因此，GEP技術也能很好地解決時間序列分析問題。

2.2 GEP時間序列分析的方法

在時間序列分析中，觀測的序列數據有一定的間隔(相當于時間間隔)，稱做采樣時間，如一年、一天等。時間序列預測的思想就是通過歷史的觀測數據確定將來的觀測數據，即尋找的一個預測模型，它是一定數量的歷史觀測值的函數。模型中使用的歷史觀測值的個數在時間序列分析中稱做嵌入維數d。嵌入維數越高，則利用的歷史數據越多，模型的復雜度越高。

時間序列分析中另一個參數稱做延遲時間τ，表明觀測數據跳過的個數。延遲時間決定了數據是怎樣處理的，如延遲時間為1，則數據處理是連續的，τ值越大，表明跳過的觀測值越多。

形式上，假設嵌入維數為d，延遲時間為τ，則時間序列分析可表示為式(2)，序列分析的任務就是尋找映射規則f。

yt=f(yt-τ， yt-τ-1， yt-τ-2， …， yt-τ-d+1)(2)

將一維的時間序列按照式(2)的嵌入維數和延遲函數值轉換成平面表示的形式，這樣，時間序列分析轉換成一個具有d個自變量的傳統符號回歸問題。

時間序列預測任務就是建立模型，然后利用模型對未來進行預測，模型在運用前需要通過測試來評價模型的質量。一般地，選擇時間序列前90%的數據進行模型建立，用余下10%的數據對模型進行檢驗和評價，如可采用預測精度對其評價等。

3 實驗和性能分析

3.1 實驗數據和環境

數據來自國家統計局網站的私人汽車擁有量(http://www.stats.gov.cn/tjsj/ndsj/)，選1990—2007年各年全國私人汽車擁有量的數據。實驗中，設嵌入維數為3，延遲時間設為1，則18個序列的數據轉換成了15行4列的數據矩陣。使用前13個數據建立預測模型，后面2個數據作檢驗，檢驗使用相對誤差和如式(3)的χ-方檢驗標準。

Ri=nnj=1(TjPij)-(nj=1Tj)(nj=1Pij)[nj=1T2j-(nj=1Tj)2][nj=1P2ij-(nj=1Pij)2](3)

其中:Tj是第j個目標值，Pij是第i個程序對第j個樣例的預測值。

程序用Eclipse3.1+Java編寫。為了挖掘滿足一定精度盡可能簡單的模型，GEP各參數設定如下:種群規模30，頭部長度為4，基因個數2，連接函數為“+”，FS={+，-，*，/}， TS={a，b，c｝分別表示預測點前1~3個觀測年份數據，其他參數值如表1所示。

適應度函數選帶有選擇帶寬的相對誤差構建的適應度函數，如式(4)所示。

fi=nj=1(R-Pij-TjTj×100)(4)

其中:R是選擇范圍，取R=100;fi是第i個個體的適應度函數值，可見，最大適應度函數值fmax=1 300。其他記號含義同式(3)，精度為10%，進化代數為5 000代。

3.2 實驗分析

根據以上參數設定，經過多次運行，均能得到較好的預測模型。其中一次的進化模型見式(5)。

yt=yt-1+2yt-1yt-3+y2t-3yt-1+yt-2(5)

用該模型對2006年和2007年全國私車擁有量進行預測檢驗。其模型值、實際值以及相對誤差如表2所示。

在測試數據上，模型的適應度值達到了197.20，χ方值為1，相對平方誤差根(RRSE)為0.159。在訓練數據上，模型的適應度函數值為1 264.82，χ方值為0.998 7，相對平方誤差根為0.038。可見，模型有很高的精度和良好的泛化能力。應該注意到，由于是通過數據挖掘技術獲得的模型，在挖掘中沒有考慮模型的可理解性因素，所以式(5)看起來簡單、精確，但可理解性不強。

圖4是在一個坐標軸上展示該模型預測值與實際值各年的情況。

3.3 模型利用

實驗驗證，本文得到的模型是可靠的，有很高的準確性，故本節試用該方法得到的模型作短期預測，分別對2008年和2009年的私車擁有量進行預測。

將訓練數據和測試數據合并，形成新的訓練數據，依據以上參數進化模型。需要說明的是，對2009年總量預測時，使用的是2008年的模型值，而非實際值。

進化得到的模型對2008年預測值為3 544.26萬輛，2009年為4 350.19萬輛，預測建立在可信的模型上。對預測結果應合理分析后再加以利用，以便為決策和管理服務。畢竟社會系統是一個開放的大系統，系統間各個因素相互制約相互影響，紛繁復雜。

4 結束語

GEP是遺傳算法家族的新成員，在符號回歸領域有很強的能力，已經取得很多研究成果。時間序列分析是一類特殊的符號回歸問題，本文基于GEP技術對我國私人汽車擁有量進行了時間序列分析，建立了可靠的預測模型。該方法克服了時間序列分析中使用機理分析得到系統動力學模型的困難，或者主觀地設定系統的模型形式，然后進行參數確定方法的人為因素色彩。通過控制嵌入維數和函數符號集的方式控制模型復雜度和精度之間的矛盾。

模型在測試數據集上的相對平方誤差根為0.159，在訓練集上為0.038，因此模型有很高的精度和良好的泛化能力。對2008年和2009年的我國私人汽車擁有量進行了預測，可幫助汽車量管理的有關部門進行科學管理和工作部署。

下一步將結合領域知識，從理論的高度研究如何將領域知識融入GEP的挖掘模型過程中，挖到有趣的模型，增強模型的可理解性。

參考文獻:

[1]

朱開永，周圣武，婁可元，等.基于私家車保有量的預測與調控的灰色模型研究[J].中國礦業大學學報，2008，37(6):868872.

[2]鄢敏.城市私人小汽車增長影響因素研究[J].交通標準化，2009(5): 142145.

[3]FERREIRA C. Gene expression programming: a new adaptive algorithm for solving problems [J]. Complex Systems， 2001， 13(2):87129.

[4]朱軍，唐常杰， 魏大剛，等.基于動態適應度的基因表達式編程挖掘反函數[J].計算機應用研究，2007，25(9):4042.

[5]朱明放.基于基因表達式編程的TSP問題求解[J].計算機工程與應用，2008，44(23):5355.

[6]DUAN Lei， TANG Changjie， ZHANG Tianqing，et al. Distance guided classification with gene expression programming[C]//Proc of Advanced Data Mining Applications. Heidelberg: SpringerVerlag， 2006: 239246.

[7]陳瑜，唐常杰，葉尚玉，等.基于基因表達式編程的自動聚類方法[J].四川大學學報:工程科學版，2007，39(6): 107112.

[8]曾濤，唐常杰，朱明放，等. 基于人工免疫和基因表達式編程的多維復雜關聯規則挖掘方法[J].四川大學學報:工程科學版，2006，38(5):136142.

[9]ZUO Jie， TANG Changjie， LI Chuan，et al. Time series prediction based on gene expression programming[C]//Proc of International Conference for Web Information Age. Heidelberg: SpringerVerlag， 2004:239246.

[10]FERREIRA C. Gene expression programming: mathematical modeling by an artificial intelligence[M]. 2nd ed. Heidelberg: SpringerVerlag， 2006.