基于改进基因表达式程序设计的菠菜价格建模及预测

杨 磊，赖志杰，苏柱华，何朝彬，彭红星，陈 皓，严玉宁

（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