楊 磊，賴志杰，蘇柱華，何朝彬，彭紅星，陳 皓，嚴玉寧

（1.華南農(nóng)業(yè)大學數(shù)學與信息學院，廣東 廣州 510642；2.廣東省科技創(chuàng)新監(jiān)測研究中心，廣東 廣州 510033；3.廣東省農(nóng)科院農(nóng)業(yè)經(jīng)濟與農(nóng)村發(fā)展研究所，廣東 廣州 510640；4.廣東村村通科技有限公司，廣東 廣州 510045）

?

基于改進基因表達式程序設(shè)計的菠菜價格建模及預測

楊 磊1，賴志杰2，蘇柱華3，何朝彬1，彭紅星1，陳 皓4，嚴玉寧4

（1.華南農(nóng)業(yè)大學數(shù)學與信息學院，廣東 廣州 510642；2.廣東省科技創(chuàng)新監(jiān)測研究中心，廣東 廣州 510033；3.廣東省農(nóng)科院農(nóng)業(yè)經(jīng)濟與農(nóng)村發(fā)展研究所，廣東 廣州 510640；4.廣東村村通科技有限公司，廣東 廣州 510045）

摘 要：基因表達式程序設(shè)計（GEP）是一種基于基因型和表現(xiàn)型的新型進化算法。針對傳統(tǒng)GEP遺傳算子進行建模及預測時容易受到噪聲干擾，導致過早收斂，陷入局部最優(yōu)等缺點，提出了一種新型GEP算法，增加了“倒串”和“基因提取”算子，該新型算法可以提高基因的有效利用率，具有更高的收斂速度和求解精度，且能更好的避免早熟現(xiàn)象。將該新型GEP算法用在菠菜價格預測上，通過對訓練數(shù)據(jù)進行分析和進化創(chuàng)建數(shù)學模型，實現(xiàn)菠菜價格的仿真與預測，通過多組實驗證明，該新型基因表達式程序設(shè)計算法在菠菜價格預測上具有更快的收斂速度和更高的精度。

關(guān)鍵詞：GEP；IGEP；菠菜價格預測；基因利用率；基因提取

蔬菜產(chǎn)業(yè)對農(nóng)業(yè)乃至整個國民經(jīng)濟的發(fā)展起著至關(guān)重要的作用，保持蔬菜價格的穩(wěn)定是一件關(guān)乎民生的大事。蔬菜價格預測可以幫助相關(guān)部門采取措施減緩價格的波動，保持市場價格平穩(wěn)，促進國民經(jīng)濟的健康發(fā)展。從國內(nèi)外研究動態(tài)來看，價格預測在社會經(jīng)濟、電力負荷［1］、交通運輸?shù)阮I(lǐng)域取得了較大進展。在農(nóng)產(chǎn)品市場價格預測方面，Henry［2］對美國棉花產(chǎn)量進行了回歸預測，預測結(jié)果比當時美國農(nóng)業(yè)部的預測結(jié)果更為準確。Sarle研究了利用樣本數(shù)據(jù)建立了生豬價格預測方程，擬合優(yōu)度達0.75［3］。Jarrett采用指數(shù)平滑法對澳大利亞羊毛價格進行短期預測，結(jié)果表明指數(shù)平滑法對轉(zhuǎn)折點的預測具有優(yōu)勢［4］。Schmitz等［5］利用Box-Jenkins法和指數(shù)平滑法對生豬日價格進行預測，結(jié)果表明時間序列法與因果關(guān)系模型相比并不遜色。崔國利采用混沌神經(jīng)網(wǎng)絡(luò)模型和ARIMA模型來對大白菜價格進行建模及預測，結(jié)論顯示混沌神經(jīng)網(wǎng)模型預測結(jié)果與實際價格的平均相對誤差較?。?］。朱曉霞［7］利用馬爾可夫鏈分析模擬驗證了蔬菜價格波動周期的可預測性。綜上所述，國外主要采用計量經(jīng)濟學方法進行蔬菜價格預測，國內(nèi)主要用神經(jīng)網(wǎng)絡(luò)，基于智能算法進行預測的并不多。

基因表達式程序設(shè)計（Gene Exp ression Programming，GEP）是一種基于基因組（Genome）和表現(xiàn)型 （Phenome）的新型進化算法。它被廣泛應用于解決因子分解、函數(shù)參數(shù)優(yōu)化、進化建模、關(guān)聯(lián)規(guī)則挖掘、分類與聚類、太陽黑子預測等問題，獲得了較好的結(jié)果［8-11］。本文將基因表達式程序設(shè)計進行改進并應用于菠菜價格預測，實驗結(jié)果表明改進后的基因表達式程序設(shè)計效率更高，預測結(jié)果更接近于真實值。

1　基因表達式程序設(shè)計

1.1 基因表達式程序設(shè)計概述

基因表達式程序設(shè)計是葡萄牙科學家Ferreira 于2001年提出的新型進化算法［12］。它吸取了遺傳程序設(shè)計 （Genetic Programming， GP）［13］和遺傳算法 （Genetic Algorithm， GA）［14］的優(yōu)點，是一種高效率的進化算法。Ferreira發(fā)明了Karva語言來讀取和表達編碼在GEP染色體中的信息，使得染色體允許多基因組的存在，簡化了構(gòu)建一個功能強大的基因型/表現(xiàn)型系統(tǒng)的過程。這些優(yōu)點使得GEP比其他的傳統(tǒng)遺傳算法快2～4個數(shù)量級。

1.2 基因表達式程序設(shè)計

1.2.1 染色體的組成結(jié)構(gòu) （1）基因。GEP的基因由線性字符串組成，分為頭部和尾部。設(shè)F為函數(shù)符號集，T為終結(jié)符號集，則頭部由F，T中的符號隨機組成，而尾部只能由T中符號組成。設(shè)一個基因長度為l，頭部長度為h，尾部長度為t，基因包含的函數(shù)符中函數(shù)最大操作目數(shù)為n（如函數(shù)符為“+”時n為2），則有如下公式：

表達式（1）就是隨機生成的一個基因組（淺色表示頭部，深色表示尾部） 。

（2）表達式樹（Expression Tree，ET）。表達式（1）稱為K-表達式（K-expressions）。利用從上而下，從左到右規(guī)制，表達式（1）可以轉(zhuǎn)化為圖1的表達式樹。

圖1　表達式（1）對應的表達式樹

（3）染色體。在GEP中，解決復雜問題時，往往采用多個基因組構(gòu)成染色體，然后各個基因組使用一個連接符連接起來。下式為2個基因組成的染色體（深色部分為各基因組尾部）：

該染色體有2個ORF（open reading frame），每個ORF對應的子表達式樹（sub_ET）之間用連接函數(shù)“+”連接時，染色體的表達式樹見圖2。

1.2.2 適應度的計算 基因表達式程序設(shè)計有兩種適應度函數(shù)的評價模型——基于絕對誤差的模型和基于相對誤差的模型：

式中，M為選擇范圍，C（i，j）為染色體個體i對于適應度樣本j（來自集合Cr中）的返回值。Tj是適應度樣本的目標值。當該個體為對應的完美解時，C（i，j）= Tj，fi= fmax= CrM。

1.2.3 選擇函數(shù) GEP根據(jù)適應度來選擇進行遺傳的父代。選擇概率公式如下：

式中，Pi表示個體i的被選中概率，fi為該個體的適應度，為種群的總適應度。父代選擇的方法很多，如輪盤賭選擇法、隨機遍歷抽樣法、錦標賽選擇法等。本研究采用輪盤賭選擇法。

圖2　表達式（2）對應的表達式樹

1.2.4 染色體的遺傳操作 基本的GEP遺傳操作算子有選擇、變異、倒串、插串、根插串、基因變換、單點重組、兩點重組、基因重組等。

（1）選擇算子。選擇算子根據(jù)個體的適應度和輪盤賭的偶然性來選擇個體。按照群體中個體數(shù)目進行相應次數(shù)的旋轉(zhuǎn)，從而始終保持群體大小不變。

（2）變異算子。變異作用在單個染色體上，對染色體的每一位進行隨機測試，當滿足變異概率時，將重新產(chǎn)生該位的編碼。表達式（3）中，第一個基因組的3號基因位發(fā)生變異時的父代及子代（/為發(fā)生變異的基因位）。

（3）倒串算子。本研究添加的倒串算子作用于某個基因組頭部。隨機地在頭部基因中選取某一段子串，然后以該子串中心為對稱各字符位置順序?qū)φ{(diào)。表達式（4）中，第2個基因組頭部發(fā)生倒串（-baa為發(fā)生倒串的基因位）。

（4）插串（即IS插串）。從染色體中隨機選擇一子串，并將其插入到某一基因的頭部除起始位置外的隨機位置，插入位置的基因往后移，超出頭部的基因截掉。表達式（5）中，頭部1號基因位后面的2個基因被截掉了（baa為插入的子串）

（5）根插串（即RIS插串）。根插串只能將選擇的子串插入到頭部的起始位置，選擇的子串要保證是函數(shù)。根插串時，在染色體中隨機地選取一個位置往后找，若找到函數(shù)，則獲取一個子串，若沒有找到函數(shù)則不做任何操作。表達式（6）中，頭部1號基因位后面的基因被截掉了（/ba為插入的子串）。

（6）基因變換。隨機選取一個完整的基因組，然后插入到染色體的起始位置，被選中的基因組在新個體中被刪除，表達式（7）即為基因變換（*-baabbaaba為選取的基因組）。

（7）單點重組。單點重組時，父代染色體相互配對，隨機選取一個位置，交換兩父代染色體該點后面的所有基因。表達式（8）是單點重組的實例（baababb和abbaaba為交換的基因）。

（8）兩點重組。在染色體上隨機選取兩點，交換兩點之間的基因，如表達式（9）所示，baab 和abba為交換的基因。

（9）基因重組?；蛑亟M作用于多基因組染色體，選擇好兩個父代染色體，隨機選擇一個基因組，交換兩個父代染色體基因組（*-baabbaaba 和-a+b-aaabab為交換的基因組），如表達式（10）所示。

1.3 基因表達式程序設(shè)計步驟

GEP算法如下：

輸入：GEP進化參數(shù)值，數(shù)據(jù)集

輸出：目標函數(shù)最優(yōu)解，適應度

1）創(chuàng)建初始化群體；

2）染色體解碼；

3）計算每個個體的適應度。若找到完美解或者符合約束條件，則停止進化，否則繼續(xù)轉(zhuǎn)到4；

4） 進化操作產(chǎn)生下一代，轉(zhuǎn)到2；

2　一種新型的基因表達式程序設(shè)計

基因表達式程序設(shè)計自2001年提出以來，許多學者從不同角度對其改進［15］。有學者在提出染色體進化中實現(xiàn)動態(tài)增減；有學者在遺傳算子概率上進行改良［16］。本研究為了提升基因有效利用率，當出現(xiàn)基因組首位基因為終結(jié)符時，將該位基因提取出來，把它連接到其他的基因組中去，原基因組的頭部前移一位，最后補上一位頭部基因。本研究將該操作命名為“基因提取”，也就是新增加了一種進化算子，該算子作用于基因重組之后，形成下一代種群之前。

基因提取算子的算法：

輸入：單條染色體

輸出：經(jīng)提取的染色體

（1）逐個檢查基因組，若遇到首位為終結(jié)符的基因組，標記該終結(jié)符，轉(zhuǎn)到2。若檢查完所有基因組沒有發(fā)現(xiàn)首位為終結(jié)符的基因組，算法結(jié)束。

（2）尋找首位基因為非終結(jié)符的、有效基因最短并比基因頭部長度至少短兩位的基因組，若尋到則轉(zhuǎn)到3，否則算法結(jié)束。

（3）將尋找到的基因組頭部后移兩位，然后在首位填入連接符，第二位填入步驟1找的終結(jié)符，轉(zhuǎn)到1。

表1　全國菠菜的平均價格（元/500 g）

3　新型基因表達式程序設(shè)計在菠菜價格預測方面的應用

GEP最為常用的應用之一就是進行預測［17］，例如糧食產(chǎn)量預測［18］，股票預測，故障預測［19］等。原因是因為GEP只根據(jù)適應度函數(shù)來進化，無需人為干預就可以得到準確的結(jié)果，在函數(shù)回歸［20］中有著強大的發(fā)現(xiàn)能力。預測往往是函數(shù)回歸問題。

3.1 預測方法

由于蔬菜具有季節(jié)性，一種蔬菜上市維持的周期較短，因此單從季度來說，出于精度考慮，不宜進行較遠時間的預測。本項目主要研究IGEP在短期菠菜價格預測的應用。菠菜價格為弱變化時間序列，采用滑動窗口預測法進行菠菜價格的預測。利用C#語言制作成菠菜價格預測工具。下面是一次菠菜價格預測的過程。

3.1.1 導入數(shù)據(jù) 試驗的數(shù)據(jù)選擇了2014年1月19日至2014年4月3日的全國菠菜每日的平均價格，如表1所示，共75個數(shù)據(jù)，前67個數(shù)據(jù)作為訓練集，后8個數(shù)據(jù)作為預測評估的評估集。當滑動窗口寬度為5時，數(shù)據(jù)處理后可以得到62組訓練數(shù)據(jù)。

3.1.2 參數(shù)設(shè)置 本試驗中，設(shè)置了頭部長度為10，終結(jié)符個數(shù)為5，基因組數(shù)為8，染色體數(shù)為10。根據(jù)公式（1）可以得出此染色體的基因組尾部長度為11，因此該基因組的長度為21。一條染色體的長度為21×8，即168。操作符集｛+，-，*，/，Q，S，C，E，L｝，終結(jié)符集為｛a， b， c， d， e｝分別代表連續(xù)5 d的價格。導入數(shù)據(jù)處理后得到的訓練集有62組數(shù)據(jù)，由于選擇范圍為10，因此適應度最大值為620。

3.1.3 GEP進化 導入數(shù)據(jù)，設(shè)置好參數(shù)后，GEP開始進化。通過輪盤賭選擇法選擇父體，然后基因群體經(jīng)過變異、倒串、插串、根插串等遺傳算子的修飾，不斷地向著適應度最大的方向的進化。

3.1.4 進化結(jié)束，得出預測公式 達到設(shè)定的進化代數(shù)后，GEP停止進化。選取適應度最大的作為設(shè)定條件下的最優(yōu)解輸出。本次試驗中，最優(yōu)解的染色體及菠菜預測公式如下：

SL+**a//b*baedbadaaecS～SSb+-dbQeebcacadcbbSc /C～Ee/Seeedbdbbadcd～Q*cQS～SSLbacccdddbcdSL+-S/+-*decaccadeabCLca～cS*/Cddbdbddddac+c-EcLc～S*dbcdaaecdbd～-ee/cSeCScbbcedbbcba

將染色體解碼為表達式樹，再轉(zhuǎn)化為表達式，并化簡。然后用接符“+”連接每個表達式，即可得出最終的菠菜價格預測公式如下：

圖3　GEP與IGEP的基因利用率對比

3.2 預測結(jié)果對比分析

為了驗證GEP在菠菜價格預測運用的可行性以及IGEP的優(yōu)越性，進行一系列實驗分析。圖3展示了在一次試驗中運行200代，每一代GEP與 IGEP的基因利用率對比?？梢钥闯觯琁GEP的基因利用率明顯的比GEP高。

為找出基因利用率的提高對進化的影響，設(shè)計對比試驗。首先設(shè)定進化結(jié)束的條件，當達到給定的誤差范圍后就停止進化。表2是在100次試驗中不同誤差范圍，GEP和IGEP所需的平均進化代數(shù)。從表2可以看出，在誤差范圍較大時，IGEP進化速度沒有GEP快，誤差范圍較小的時候，IGEP進化速度比GEP快。因此，在指定進化代數(shù)作為結(jié)束條件的價格預測中，IGEP進化出的解，也就是預測函數(shù)，會比GEP得出的更優(yōu)秀。

評價預測函數(shù)可以從兩方面著手，一是對訓練集的預測擬合程度，二是對驗證集預測的誤差。圖4顯示了在一次對比試驗中兩種算法的訓練預測情況，改進后的訓練預測更加接近真實值。同時說明，改進后的算法能夠進化到更接近完美解，適應度比改進前的好，訓練預測得也更好。

圖5顯示了基本算法與改進算法的驗證集預測情況，可以看到，改進算法的預測值與真實值更加接近，也就是說，改進算法能克服局部最優(yōu)解問題，預測精度比基本算法的好，這也說明了改進算法的優(yōu)良性。

上述只是在單次試驗中的對比情況，為了得到更準確的結(jié)論，接著進行了10次預測試驗，每次實驗的條件保持一致。然后取預測的平均值，根據(jù)預測的誤差來評價基本算法與改進的算法。實驗中的GEP參數(shù)如表3所示。

表2　進化需要代數(shù)對比

圖4　基本算法與改進算法的訓練擬合度對比

圖5　基本算法與改進算法的預測對比

表3　GEP參數(shù)

經(jīng)過10次的實驗，得出10組預測值，取平均值，結(jié)果見表4。

表4　GEP與IGEP蔬菜價格（元/500 g） 預測對比

在菠菜價格預測中，基于“基因提取”算子和“倒串”算子的新型基因表達式程序設(shè)計的預測價格與真實價格的相對誤差是6.33%，比GEP （12.04%）的精確度要高，更接近于真實的菠菜價格。這也說明，新型的基因表達式程序設(shè)計算法在菠菜價格上的預測是可行的，有實際參考價值的。

4　結(jié)論

本研究針對傳統(tǒng)基因表達式程序設(shè)計在進化過程中基因利用率不高的缺點，提出了一種新的基于“基因提取”算子和“倒串”算子的改進方法，并將該算法用于菠菜價格預測。通過多組對比實驗證明了基因表達式程序設(shè)計在菠菜價格預測的可行性與新型基因表達式程序設(shè)計的優(yōu)越性。與傳統(tǒng)GEP相比，采用新型的IGEP的建模與預測結(jié)果更為精確，并能改善傳統(tǒng)GEP的早熟、易陷入局部最優(yōu)及過擬合現(xiàn)象，更適合用于解決建模及預測中的復雜時間序列問題。研究表明，新型的基因表達程序設(shè)計在蔬菜價格預測上具有一定的實用價值，但本研究只是利用時間序列預測方法，沒有考慮到其他的因子。影響蔬菜價格的因素很多，如溫度、天氣等，今后研究可以將這些因子引入蔬菜價格的基因表達程序設(shè)計預測中去。

參考文獻：

［1］ Jinliang Yin，Lim in Huo，Lirui Guo and Jie Hu.Short-Term Load Forecasting Based on Improved Gene Expression Programming［J］.Proceedings of the 7th World Congress on Intelligent Control and Automation，2008，5647-5650.

［2］ Henry L M.Forecasting the Yield and the Price of Cotton［M］.New York： The Macmillan Company，1917：100-113.

［3］ Sarle C F.The forecasting of the price of hogs［J］.American Economic Review，1925，15（3）：1-22.

［4］ Jarrett F G..Short term forecasting of Australian wool prices［J］.Australian Economic Paper，1965（4）：93-102.

［5］ Schmitz A，Watts D G.Forecasting wheat yield： an application of parametric time series modeling［J］.American Journal of Agricultural Economics，1970，52：247-254.

［6］ 崔國利.基于混沌神經(jīng)網(wǎng)絡(luò)模型的我國蔬菜價格短期預測研究［D］.北京：中國農(nóng)業(yè)科學院，2013.

［7］ 朱曉霞.蔬菜價格波動周期的馬爾可夫鏈分析與預測［J］.生產(chǎn)力研究，2012，8，143-146.

［8］ 元昌安，彭昱忠，覃曉，等.基因表達式編程算法原理與應用［M］.北京：科學出版社，2010：37-40.

［9］ 廖勇.基于基因表達式編程的股票指數(shù)和價格時間序列分析［D］.成都：四川大學，2005.

［10］ 周愛民，曹宏慶，康立山，等.用遺傳程序設(shè)計實現(xiàn)復雜函數(shù)的自動建模［J］.系統(tǒng)仿真學報，2003 （6）：44-46.

［11］ 左劼.基因表達式編程核心技術(shù)研究［D］.成都：四川大學，2004.

［12］ Ferreira C. Gene Expression Programming：A New Adaptive algorithm for Solving Problems［M］.Soft Computing and Industry. Springer London，2002.

［13］ 潘正君，康立山，陳毓屏.演化計算［M］.北京：清華大學出版社，2000.

［14］ Mitchell M. An introduction to genetic algorithms［M］.Cambridge：MIT press，1998.

［15］ Noah Ryana，David Hiblerb. Robust Gene Expression Programming［J］. Procedia Computer Science，2011，6：165-170.

［16］ 劉昆.基于GEP的金屬疲勞時間預測模型［D］.武漢：武漢理工大學，2010.

［17］ 張景廣.基于基因表達式編程的組合預測方法研究［D］.武漢：華中科技大學，2011.

［18］ 李茵.基于基因表達式編程的糧食產(chǎn)量預測研究［D］.楊凌：西北農(nóng)林科技大學，2010.

［19］ Zhang Y Q，Xiao J，Sun S J.BS-GEP Algorithm for Prediction of Software Failure Series［J］.Journal of Software，2012，7：243-248.

［20］ 黃蘭麗. 基因表達式程序設(shè)計在符號回歸中的應用研究［D］.廣州：華南師范大學，2007.

（責任編輯白雪娜）

Modeling and prediction of spinach price based on improved gene expression programming

YANG Lei1，LAI Zhi-jie2，SU Zhu-hua3，HE Chao-bin1，PENG Hong-xing1，CHEN Hao4，YAN Yu-ning4

（1.College of Mathematics and Informatics， South China Agricultural University， Guangzhou 510642， China；2.Guangdong Science and Technology Innovation Monitoring and Research Center， Guangzhou 510033， China；3.Institute of Agricultural Economits and Rural Development， Guangdong Academy of Agricultural Sciences， Guangzhou 510640， China；4.Guangdong Cuncuntong Technology Co.， Ltd.， Guangzhou 510045， China）

Key words：gene expression programming； improved gene expression programming； spinach price prediction；utilization of gene； gene extraction

Abstract：Gene expression programming （GEP） is a new evolutionary algorithm based on genotype and phenotype， the genetic operators of traditional GEP are easily influenced by noise， leading to premature convergence and local solution.This paper proposes an improved GEP （IGEP）algorithm， which increases the “inverted series”and “extract” operator， can effectively increase the utilization rate of genes， and the convergence speed and solution precision is higher， can avoid the premature phenomenon.The improved GEP algorithm is used to predict the price of spinach.Through the analysis and evolution of training data to create a mathematical model，the simulation and prediction of spinach price is realized.The results show that the new IGEP algorithm has faster convergence speed and higher accuracy in the prediction of spinach price.

中圖分類號：S636.1；O141.41

文獻標識碼：A

文章編號：1004-874X（2016）01-0151-08

收稿日期：2015-09-06

基金項目：廣東省科技計劃項目（2015A020209119，2014A020208087，2012B040500054）

作者簡介：楊磊（1978-），男，博士，講師，E-mail: yanglei_s@scau.edu.cn