第5卷第4期 智能系统学报 Vol.5 No.4 2010年8月 CAAI Transactions on Intelligent Systems Aug.2010 doi:10.3969/j.issn.16734785.2010.04.003 改进基因表达式编程在股票中的研究与应用 钱晓山12，阳春华 (1.中南大学信息科学与工程学院，湖南长沙410083；2.宜春学院物理科学与工程技术学院，江西宜春336000) 摘要：简要介绍了基因表达式编程方法的基本原理，针对股票指数分析与预测问题，在经典的GEP算法基础上，提 出了一种基于动态变异算子的改进的GEP算法-IGEP(improved GEP)算法，动态变异算子随着进化代数和染色体所 含基因数目不同而变化，从而加快了GE的收敛速度和精确度.还对算法进行了复杂度和收敛性分析.最后设计了 一种基于IGEP的股票指数分析与预测算法，数值实验结果表明该算法优越于经典GEP算法，非常有效且具有较广 泛的通用性 关键词：基因表达式编程；复杂度分析；收敛性分析；股票指数预测 中图分类号：TP18文献标识码：A文章编号：16734785(2010)04-0303-05 Improved gene expression programming algorithm tested by predicting stock indexes QIAN Xiao-shan'2,YANG Chun-hua' (1.School of Information Science and Engineering,Central South University,Changsha 410083,China;2.Physical Science and Technology College,Yichun University,Yichun 336000,China) Abstract:The authors reviewed basic principles of gene expression programming (GEP).On that basis,an im- proved GEP algorithm,or IGEP,was created,based on a dynamic mutation operator.The dynamic mutation opera- tor changed with the gene number of the genome and the number of evolutionary generations.The complexity and convergence properties of the algorithm were investigated.The new IGEP was used to predict stock-market indexes. Simulation results indicated that the IGEP-based model is more accurate than the classical GEP-based model. Keywords:gene expression programming;complexity analysis;convergence analysis;prediction in stock-price index 基因表达式编程]（gene expression program- 1基因表达式编程方法原理 ming,GEP)是葡萄牙科学家C.Ferreira发明的一种 基于基因组(genome)和表现型(phoneme)的新的遗 基因表达式编程的实现技术主要包括编码方 传算法.它与遗传算法(genetic algorithms,GA)和遗 式、遗传算子、插串操作、重组算子、适应度函数选 传规划(genetic programming,.GP)的根本区别在于 择、数值变量等几个部分]，下面就涉及的改进部 他们所采用个体的本性不同：即在GA中个体是固 分作一介绍. 定长度的线形串（染色体）；在GP中个体是长度和 1.1变异算子 形状不同的非线形性实体（分列树），而在基因表达 变异(Mutation)可以发生在染色体内的任何位 式编程中个体首先被编码成固定长度的线形串（基 置，然而，染色体的结构组织必须保持完整.在基因 因组或者染色体)，然后被表达成不同长度和形状 头部，任何符号都可以变异成函数符号或者终点；在 的非线形实体（简单图表示，或者表达式树）. 基因尾部，终点只能变异成终点.通过这种方法，染 色体的结构组织得以保持，由于GEP编码方式的特 点，可以预见变异产生的新个体在结构上是正确的. 收稿日期：200902-15. 值得注意的是，在GEP中既没有变异种类的限制， 基金项目：国家自然科学基金资助项目(60634020,60874069， 60804037):国家"863"资助项目(2006AA04Z181). 也没有一个染色体中变异次数的限制：在所有情况 通信作者：钱晓山.E-mail:qianxiaoshan@126.com. 中，新生的个体在句法上都是正确的
·304 智能系统学报 第5卷 1.2适应度函数选择 为种群大小，L为总进化代数，M为训练集的长度， 除了个体的表示外，还需要定义个体的适应值 证明在算法中计算个体针对M个训练样本的 评价函数.这是本文的研究重点.在GEP中，适应度 复杂度为O(M),算法需要计算种群中各个体的适应度 函数设计非常重要，一般采用如下3种方式： 值，故种群适应度计算的复杂度为O(K*M),因算法 最多进化L代，故算法复杂度为O(K*L*M). f=∑(M-1C-T1), (1) 3.3IGEP算法收敛性分析 (2) 在基于IGEP的复杂函数参数识别反问题球解中， 将适应度函数设计如(4)式所示其中，E=1 in≥2C,henf=,def=l m (3) (Y0-y)2为均方误差和计算公式，简记为SSE.设遗 式中：M为一常量，f是控制适应度∫的取值范围； 传变异率Pm≤0.5，则可得如下2个结论： C()表示第i个基因对应的函数表达式中利用第j 1)IGEP复杂函数反问题求解进化第K代的最 个样本变量数据求得的函数值；TD表示第j个样本 小均方误差和的数学期望满足 中包含的实际测得的该目标函数的真实值；C:是测 k-1 试样本数据总数，n是正确适例的个数.式(1)和式 E(SEa）≤E(SSE)-P,PPue∑E(b,). 台 (2)可以解决任何一个符号回归问题.式(3)主要解 (5) 决逻辑合成问题.在适应度的设计上，目标非常明 2)最小均方误差和以概率收敛，即对任意ε> 确，让系统按照要求的方向进化， 0,有 2 改进的基因表达式编程方法算法 limp(SSEi.>e）=0. (6) 以上分析可看出，基于IGEP的复杂函数参数 2.1IGEP算法描述 识别反问题求解是依概率收敛到全局最优染色体 经典的GEP算法对变异算子的考虑不够，本文 的，但是，由于不是强收敛到全局最优点，因此不能 在做了大量的实验后，就变异算子的变异方法给出 排除收敛到局部最优的可能。 了一种改进的方案.基于改进变异算子的IGEP算 法结构如下[4： 3 数值实验一基于GEP和IGEP的 1)初始化种群，随机产生60组（过大会增大算 法运行时间，过小则很难收敛)初始染色体，每个染 上证指数时间序列分析 色体由5个基因构成，每个基因头长度为15（或更 多)；初始化时采用KARVA编码4： 3.1股票指数预测研究 Q*+-ab c d 股票市场是一个复杂的非线性动力系统，同时 2)按照适应值函数求解初始种群的各染色体 受多种因素的交互影响，对于股票未来价格的精确 的适应值（本文采用的适应度函数） 预测是非常困难的.股市预测被认为是当前时间序 1 列预测中最富挑战性的应用之一，受到数据挖掘界 f(i)=1000×Ei+1' (4) 的广泛关注5].股票指数涨跌数据是一种时间序列 并将适应值排序，保存适应值最高的个体； 数据，它既具有一定的趋势性又具有较大随机性.自 3)执行变异，并按照染色体所含基因的多少决 19世纪股票市场建立以来，股票指数预测模型就成 定变异的基因位个数，本文选择每个基因变异一个 为各国学者研究的焦点.在时间序列预测中，线形的 基因位的方法； 概率统计模型曾得到广泛的应用，如：ARMA模型 4)执行IS插串、RIS插串、Gene插串： 法、AR模型法、阈值自回归、多项式自回归、指数自 5)执行单点重组、两点重组、基因重组； 回归模型等，后来还有灰色预测、混沌时间序列预测 6)运行代数增加1，如果运行达到预先设定的 等方法.如White(1985)[6曾经尝试利用神经网络 最大代数，则停止运行，用图形输出结果并保存到记 来预测BM普通股每日报酬率，但是预测结果不甚 录文件中，否则转到2)继续运行， 理想；Bergerson and Wunsch(1991)I利用S&P指数 2.2IGEP算法复杂度分析： 训练神经网络，预测股价涨跌方向的正确率相当 引理算法的的复杂度是O(K*L*M),其中K 高；Pesaran and Timmermann(990)[8]对过去25年
第4期 钱晓山，等：改进基因表达式编程在股票中的研究与应用 ·305· 的伦敦证券指数进行预测，采用神经网络技术预测 股票指数预测建模：取f（i)=1000×1/ 指数的月变化率可以达到60%的正确性；台湾地区 (E:+1)为适应值函数，并假设股票指数与最近13 的研究中，张文信(1995)以总体经济变量预测股价 天有关，以此最近13天为变量建立微分方程，求解 加权指数走势，其预测正确率约为50%~60%等 算法简述如下： 等.但随着人工神经网络研究的深人，人们认识到它 1)将微分方程作为遗传计算对象（染色体），初 存在的严重不足，在原理上缺乏实质性的突破，同时 始化IGEP种群，从训练数据中挖掘出微分方程和 也缺乏理论依据910]，这些研究结果表明股票指数 初始条件； 是具有可预测性的.基于此，本文提出改进变异算子 2)用Runge-Kutta法求解微分方程，计算出微 的IGEP应用于股票指数的预测 分方程的（作为染色体）适应度，若满足终止条件， 3.2上证指数时间序列模型 成功退出； 以上证指数2003年共239个交易日的数据为 3)执行IGEP的各种操作.产生下一代种群，转1) 训练数据，应用GEP和IGEP方法进行时间序列分 本文在实验中还引人了对于含噪时间序列的处理 析，以2004年的数据作为测试数据.时间序列分析 算法，实验中使用了显微插值法去噪，算法简述如下： 中，一个重要的参数是历史数据长度的选择.我们对 1)对含噪的时间序列用傅立叶变换，去掉高频 历史数据为1~13天分别进行了模型的建立，发现 部分； 对训练数据均能进行准确的模拟.但历史数据天数 2)把时间区间放大m倍(10<m<200); 太短时，由于提供的资料信息太少，预测时效果不 3)对上述结果作反傅里叶变换； 好.GEP的函数集可以包含运算符 4)插值、光滑化、还原（缩小）时间区间， {+,-,*,/}以外再加上其它初等函数.在实 3.3实验数据 验中发现基于基本运算符建立的模型就能够达到较 本文实验数据来源于www.sohu.com财经版， 高的精度，所以在分析中，选择这些运算符作为函数 3.3.1GEP算法[ 集对13天的历史数据进行建摸 使用GEP算法，参考文献[5]给出拟合函数公 该文在求解中，用到了数值常量集合，数值常量 式为 集合C由初始函数任意生成，范围在[-10,10]之 D=du/(d4/(d2-d4)-(d1+d4))+d2/(d/(2 间，常量的个数与基因尾部长度值相同.实验中的参 -d3)-d)+ds/(d3+d/(d-d3）+d6+ 数及参数值如表1所示. d2)+（d6+d4*d6/d)/((d+d2)*(d,- 表1参数定义 da)+d4/(d/(d2+d4-d5-d)+d,)+d2 Table 1 Definition of parameters 式中：d:表示前第13-i天的数据， 参数名 参数值 文献[11]指出此公式拟合曲线的相关系数为 最大代数 300 0.9533. 种群大小 60 利用此式给出训练数据和测试数据的真实数据 函数集 +’,‘-’,*’,/八，‘8，c 与模型数据的曲线比较图，参见图1，图2： 基因头长度 10 基因个数 5 1650 1600 连接符 1550 变异率 0.044 1500 单点重组率 0.3 兰1400 上证指数实际俏 两点重组率 0.3 I350 上证指数模型值 基因重组率 0.1 S插串率 0.1 H期 S插串长度 1,2,3 图1上证指数部分训练数据真实值与模型值比较曲线图 RIS插串率 0.1 Fig.1 The compared curve between the true value and model RIS插串长度 1,2,3 values of the Shanghai index part training data Gene插串率 0.1
·306 智能系统学报 第5卷 c2=-5.418121, 1800 基因5)的c0=-9.595825, 1750 1700 基因6)的c0=6.671539,c1=2.517029, 1650 1600% ·…上证指数实际值 基因7)的c0=-6.272735,c1=-.91211, 1550 ·一上指数模型值 1500 c2=-2.822785, 1450 33332至2宝 基因8)的c0=9.329834,c1=-8.205658, 8卡宁8三早8术3形g333无 基因9)的c0=-9.196594. 日期 利用IGEP算法提供的功能将其转化成数学模 图2上证指数部分测试数据真实值与模型值比较曲线 型即为 图 ￥6 Fig.2 The compared curve between the true value and Y= model values of the Shanghai index part test data 《,-)西+9979676-(P) 7 4.3.2IGEP算法 312(xk+xg） 取f(i)=1000×1(E:+1)为适应值函数， x11+x4+x7x3 +2如+B+与+-型+ 本文使用IGEP算法得到较好的染色体如下所示 2.517029x2x3(x1+x4) -+ (此染色体含3个基因，连接符采用数学运算“+”， (xB+6.671539-x3)x1x 黑体为基因头)： 6+9+x0—+ 人.d5.*,-,d11.*.*,-./人人.d1.d0.-,d6. x1x5+x11+x7+x1-10 d8.d1.d8.d1.d1.c0.d5.d3.d2.d0.cl.d3.d3.9. X123x13 d2.d10+.-.-.d3.+.d12.d3./.d1.*.+.d11. -4.226227x2x(x10-x1） +,+.*.d4.d8.d10.d3.d6.d2.d1.d8.d10.d12. 2x7x5 d11.d10.d12.d11.d1.d9/.d12.*.c0.*,*./.- (x1-5.105316)x1x3(x3-7.068481-3) *.d1.+.d9.d0./.d7.d2.d11.d7.d0.d2.d10.d9. 式中：y表示第14天的值，x:表示前第13-i天的数据 d4.d11.d4.d4.d4.d6.d0.d9.d0/../.d6.*.d0. 上证指数部分训练数据真实值与模型值比较曲 *.-,d2./.d4.+.d2.+..d12.c0.d6.d6.d0.c1. 线如图3所示，其中实线为真实值，虚线为拟合值； c2.d8.d1.d3.d1.d0.d11.d7.d5.d4d1.+.d6./.- 用IGEP预测04年前30天的数据情况如图4所示. c0.+.d6./.d8.d4.d3.d1.d6.*.d8.d12.d12.d3. 1650 真实值 d9.d11.d12.d10.d9.d1.d11.d11.d4.d3.d3. 1600 d4/././.d11.*,d10.*.-,d0./.d12.+.d2. 1550 预测值 1500 +./.d12.c0.d10.d3.d0.cl.d3.d3.d7.d8.d4.d1. 立1450 R1400 d10.d0.d7.d4/.-.d3.d1.d11./.d6.d2.d0.+.c0. 1350 1300 d11.d7.d11.+.d12.d2.d11.d2.d5.d1.d4.d12 50 100150 200250 交易日/天 d9.d11.cl.d11.d12.d4.d10.c2/.+,+,d5.+,*. +.d8.*.d0.d4.+.-.d2.d9.d10.d6.d0.d9.d4. 图3 IGEP算法上证指数部分训练数据真实值与模型 值比较曲线图 d8.d10.c0.d7.d0.cl.d11.d5.d1.d11.d12/.d4.d0. Fig.3 The IGEP algorithm for the compared curve between -,*,d12.*,d3.+,d3.*,d12.d3.+.+,d3. the true value and model values of the Shanghai in- d2.d9.d4.d11.d2.d10.d4.d5.d0.d0.d4.d8.d6 dex part training data d7.c0 实验求出训练数据相关系数为0.9773，测试数 其中： 据相关系数为0.9623.由图3与图4知，其拟合效 基因1)的0=-9.979676，c1=1.375732, 果和预测效果都优于文献[11]的GEP方法，证明了 基因3)的c0=-4.226227, 该文设计算法的优越性。 基因4)的c0=-7.068481,c1=-5.105316
第4期 钱晓山，等：改进基因表达式编程在股票中的研究与应用 307· 800r 700 model based on a neural network-expert system Hybrid 600 [C]//Proeedings of the IEEE International Conference on 500 400 真实值 Neural Network.Seattle,1991::1289-1293. 300 ……预测值 200 [8]PESARAN M H,TIMMERMANN A.A recursive modeling i00 0 approach to predicting UK stock C]//Economic Journal. 5 1015 202530 时间天 Blackwell Publishing.Edward 2000::159-191. 9)]元昌安，唐常杰，左劫，等.基于基因表达式编程的函数 图4IGEP算法上证指数部分训练数据真实值与模型 挖掘一收敛性分析与残差制导进化算法[J刀.四川大学 值比较曲线图(2004年前30天) 学报：.工程科学版，2004,36(6)：100-105. Fig.4 The IGEP algorithm for the compared curve between YUAN Changan,TANG Changjie,ZUO Jie,et al.Func- the true value and model values of the Shanghai in- tion mining based on gene expression programming-conver- dex part training data(formerly 30 days in 2004) gence analysis and remnant-guided evolution algorithm[J]. 4 结束语 Journal of Sichuan University:Engineering Science Edition, 2004,36(6):100-105 用GEP进行预测，不需要知道各因素间的因果 [0]段磊，唐常杰，左哉，等.基于基因表达式编程的抗噪声 关系，只需要提供足够的实验或者实验数据，无须知 数据的函数挖掘方法[刀，计算机研究与发展，2004,41 道目标函数，就可以达到准确预测的目的.本文 (10a1684-1689.. 创新点在于提出了一种新的IGEP算法，可得到准 DUAN Lei,TANG Changjie,Zuo Jie,et al.An anti-noise 确的函数表达式，通过实例计算和分析可知，此方法 method for function mining based on CEP[J]].Journal of 优于文献[11]的GEP方法，并充分发挥了进化算法 Computer Research and Development,2004,41(10)): 1684-1689., 内含的并行性，从而使得算法在求解速度上远远快 [11]廖勇.基于基因表达式编程的股票指数和价格序列分 于普通的算法 析[D.成都：：四川大学，2005 参考文献： LIAO Yong,Time series prediction in stock-price index and stock-price based on Gene Expression programming [1]FERREIA C.Gene expression programming:a new adaptive [D].chengdu:Sichuan University,2005.. algorithm for solving problems [J].Complex Systems, [12]李曲，蔡之华，朱利等.基因表达式编程方法在采煤工 2001,13(2)87-129. 作面瓦斯涌出量预测中的应用[刀]应用基础与工程科 [2]MITCHELL M.An introduction to genetic algorithms[M]. 学学报，2003,12(1))505 Cambridge::IMIT Press,1996::143-164. LI Qu,CAI Zhihua,ZHU Li,et al.Application of gene 3 ]FERREIRA C.Gene expression programming:mathematical expression programming in predicting the amount of gas e- modeling by an arifcial intelgence[M].2nd Ed.Mit mited from coal facefJ].Journal of Basic Science and Press Cambridge,Massachusetts o London,England Spring-g- Engneering,2003,12(1)):05 er2006:f82-85.5, 作者简介： [4]张克俊.求解反问题的改进的基因表达式编程研究[D] 钱晓山，男，1980年生，讲师，博士 南鲳：江西理工大学，2006.6. 研究生，主要研究方向：复杂工业过程 ZHANG Kejun.The study of improving gene expression pro-o- 建模、优化控制 gramming for solving the inverse problem[D]].Nanchang: liangxi University of science and technology,2006.6 [5]ZUO Jie,TANG Changjie,LI Chuan,et al.Time series prediction based on gene expression programming[Cl//In-n- termational Conference for Web Information Age 2004.Ber-er 阳春华，女，1965年生，教授，博士 ling Heidelberg:Springer Verlag 2004:5564.4. 生导师，获”湖南省青年科技奖”、”湖 6 ]]ECONOMIC W H.Prediction using neural networks:the 南省十大杰出女性”，主要研究方向为 case of IBM daily stok returns[C]//IEE Internationalal 复杂工业过程建模、优化控制：智能信 Conference on Neural Network.1988:3451458 58. 息处理 [7]]BERGERSON K,WUNSCH D C.A commodity trading:
[8] PESARAN M H,TIMMERMANN A. A recursive modeling approach to predicting UK stock [ C] //Economic Journal, Blackwell Publishing,Edward 2000: 159-191. ZHANG Kejun. The study of improving gene expression programming for solving the inverse problem[ D] . Nanchang: liangxi University of science and technology,2006. 参考文献: 500 5 [2] MITCHELL M. An introduction to genetic algorithms[ M] . Cambridge: MIT Press,1996: 143-164. 作者简介: 真实值 ………预测值 800 600 LIAO Yong,Time series prediction in stock-price index and stock-price based on Gene Expression programming [D] . chengdu: Sichuan University,2005. 400 200 用 GEP进行预测,不需要知道各因素间的因果 关系,只需要提供足够的实验或者实验数据,无须知 道目标函数,就可以达到准确预测的目的.本文 创新点在于提出了一种新的IGEP算法,可得到准 确的函数表达式,通过实例计算和分析可知,此方法 优于文献[11] 的 GEP方法,并充分发挥了进化算法 内含的并行性,从而使得算法在求解速度上远远快 于普通的算法. [5] ZUO Jie,TANG Changjie,LI Chuan,et al. Time series prediction based on gene expression programming[ C]//Intermational Conference for Web Information Age 2004. Berling Heidelberg: Springer Verlag,2004: 5564. 钱晓山,男,1980年生,讲师,博士 研究生,主要研究方向: 复杂工业过程 建模、优化控制. LI Qu,CAI Zhihua,ZHU Li,et al. Application of gene expression programming in predicting the amount of gas emited from coal face[J] . Journal of Basic Science and Engneering,2003,12(1) :50-5. [4] 张克俊.求解反问题的改进的基因表达式编程研究[D] . 南昌: 江西理工大学,2006. O 700 [7] BERGERSON K,WUNSCH D C. A commodity trading [11]廖勇.基于基因表达式编程的股票指数和价格序列分 析[D] .成都: 四川大学,2005. Fig.4 The IGEP algorithm for the compared curve between the true value and model values of the Shanghai index part training data(formerly 30 days in 2004) 3 ] FERREIRA C. Gene expression programming: mathematical modeling by an arifcial intelgence[ M].2nd Ed. Mit Press Cambridge,Massachusetts o London,England Springer 2006: 82-85, 6 ] ECONOMIC W H. Prediction using neural networks: the case of IBM daily stok returns[ C] //IEE International Conference on Neural Network. 1988: 451458 12] 李曲,蔡之华,朱利等.基因表达式编程方法在采煤工 作面瓦斯涌出量预测中的应用[J]].应用基础与工程科 学学报,2003,12(1) :50-5 9] 元昌安,唐常杰,左劫,等.基于基因表达式编程的函数 挖掘一收敛性分析与残差制导进化算法[J] .四川大学 学报:工程科学版,2004,36(6) :100-105. [1] FERREIA C. Gene expression programming: a new adaptive algorithm for solving problems [J]. Complex Systems, 2001,13(2) : 87-129 图4 IGEP算法上证指数部分训练数据真实值与模型 值比较曲线图(2004年前30天) DUAN Lei,TANG Changjie,Zuo Jie,et al. An anti-noise method for function mining based on CEP[J] . Journal of Computer Research and Development,2004,41(10) : 1684-1689. 307· 4 结束语 model based on a neural network-expert system Hybrid [C]//Proeedings of the IEEE International Conference on Neural Network,Seattle,1991: 1289-1293. YUAN Changan,TANG Changjie,ZUO Jie,et al. Function mining based on gene expression programming-convergence analysis and remnant-guided evolution algorithm[J] . Journal of Sichuan University: Engineering Science Edition, 2004,36(6) :100-105. 第4期 1 0 15 2 0 2 5 3 0 i00 [10] 阳春华,女,1965年生,教授,博士 生导师,获"湖南省青年科技奖"、"湖 南省十大杰出女性",主要研究方向为 复杂工业过程建模、优化控制;智能信 息处理. 段磊,唐常杰,左哉,等.基于基因表达式编程的抗噪声 数据的函数挖掘方法[J] .计算机研究与发展,2004,41 (10) :1684-1689. 时间/天 钱晓山,等: 改进基因表达式编程在股票中的研究与应用 300