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

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

（1.華南農業大學數學與信息學院，廣東 廣州 510642；2.廣東省科技創新監測研究中心，廣東 廣州 510033；3.廣東省農科院農業經濟與農村發展研究所，廣東 廣州 510640；4.廣東村村通科技有限公司，廣東 廣州 510045）

?

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

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

（1.華南農業大學數學與信息學院，廣東 廣州 510642；2.廣東省科技創新監測研究中心，廣東 廣州 510033；3.廣東省農科院農業經濟與農村發展研究所，廣東 廣州 510640；4.廣東村村通科技有限公司，廣東 廣州 510045）

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

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

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

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

1　基因表達式程序設計

1.1 基因表達式程序設計概述

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

1.2 基因表達式程序設計

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1.3 基因表達式程序設計步驟

GEP算法如下：

輸入：GEP進化參數值，數據集

輸出：目標函數最優解，適應度

1）創建初始化群體；

2）染色體解碼；

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

4） 進化操作產生下一代，轉到2；

2　一種新型的基因表達式程序設計

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

基因提取算子的算法：

輸入：單條染色體

輸出：經提取的染色體

（1）逐個檢查基因組，若遇到首位為終結符的基因組，標記該終結符，轉到2。若檢查完所有基因組沒有發現首位為終結符的基因組，算法結束。

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

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

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

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

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

3.1 預測方法

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

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

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

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

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

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

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

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

3.2 預測結果對比分析

為了驗證GEP在菠菜價格預測運用的可行性以及IGEP的優越性，進行一系列實驗分析。圖3展示了在一次試驗中運行200代，每一代GEP與 IGEP的基因利用率對比。可以看出，IGEP的基因利用率明顯的比GEP高。

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

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

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

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

表2　進化需要代數對比

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

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

表3　GEP參數

經過10次的實驗，得出10組預測值，取平均值，結果見表4。

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

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

4　結論

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

參考文獻：

［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］ 崔國利.基于混沌神經網絡模型的我國蔬菜價格短期預測研究［D］.北京：中國農業科學院，2013.

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

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

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

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

［11］ 左劼.基因表達式編程核心技術研究［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］ 李茵.基于基因表達式編程的糧食產量預測研究［D］.楊凌：西北農林科技大學，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］ 黃蘭麗. 基因表達式程序設計在符號回歸中的應用研究［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