（计算机软件与理论专业论文）gep解码的局限性分析与对策.pdf

m c o m p u t e rs o f h v a r ea n dt h e o r y m c h a n g s h au n i v e r s i t yo fs c i e n c e & t e c h n o l o g y s u p e r v i s o r p r o f e s s o rh ep e i m a r c h ，2 0 1 1 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的 研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或 集体已经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均 已在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。 作者签名： 日期：沙1 1 年歹月7 日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅。本人授权长沙理工大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 1 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“ ) 作者签名：寻岂日期：2 , o f f 年r 月乙7 日 导师签名： 日期：办，降9 酮 1 日 摘要 基因表达式编程( g e n ee x p r e s s i o np r o g r a m m i n g ，g e p ) 是演化计算的新一代成员，它 结合了遗传算法( g e n e t i ca l g o r i t h m ，g a ) 编码简单，易于操作与遗传程序设计( g e n e t i c p r o g r a m m i a g ，g p ) 表达灵活，搜索能力强的特点，进化效率比遗传程序设计系统高出 1 0 0 - - 6 0 0 0 0 倍，由于其优越的性能吸引了越来越多的研究者参与其中。人们对g e p 个 体编码结构，解码方法，种群初始化，各遗传算子等进行了改进，取得了很好的试验效 果，g e p 与传统人工智能方法相结合进化效率也有所提高。理论上对g e p 的模式定理， 收敛性的研究也取得了一定的成果。现在g e p 已广泛应用于符号回归，分类算法，时 间序列预测等。毕竟g e p 算法的提出到现在不过十来年时间，理论与应用的研究还有 许多领域等待后来者的探索。 本文在前人工作的基础上对g e p 的研究现状、原理、解码方法及应用进行了研究。 本文的主要工作包括以下几个方面的研究与创新： l 、介绍了传统的遗传算法和遗传程序设计的相关理论和技术； 2 、重点介绍了基因表达式编程的各关键因数与算法流程，分析了g e p 与g a 和 g p 的本质不同：g e p 实现了基因型与表现型的分离； 3 、分析了传统g e p 解码方式的不足，提出了一种新的g e p 解码方法：非物理树 g e p 解码，此方法在解码过程中不需真正物理意义上的表达式树的建立与运算，减少了 机器的运算量； 4 、将新解码算法的g e p 应用于符号回归与股票走势的预测，取得了较好的实验结 果； 5 、最后对全文工作进行了总结，分析了本论文存在的问题并对未来发展方向进行 了展望。 关键词：遗传算法；遗传程序设计；基因表达式编程；g e p 解码 a bs t r a c t g e n ee x p r e s s i o np r o g r a m m i n g ( g e p ) i so n eo ft h en e w e s tm e m b e ro fe v o l u t i o n a r y a l g o r i t h m , w h i c hc o m b i n e st h ea d v a n t a g e so fb o mg e n e t i ca l g o r i t h m ( g a ) a n dg e n e t i c p r o g r a m m i n g ( g p ) i th a sa ne a s yo p e r a t i o na n das i m p l ee n c o d e i ta l s oh a saf l e x i b l y e x p r e s s i n gc a p a b i l i t ya n das t r o n gs e a r c h i n ga b i l i t y i t se v o l u t i o n a r ye f f i c i e n c yi s 10 0 - 6 0 0 0 0 t i m e sh i g h e rt h a ng e n e t i cp r o g r a m m i n gs y s t e ma n dt h es u p e r i o rp e r f o r m a n c et h u sh a s a t t r a c t e dag r o w i n gn u m b e ro fr e s e a r c h e r s l o t so fi m p r o v e m e n t so fg e p , s u c ha si n i t i a l p o p u l a t i o n , c h r o m o s o m ec o d i n g ，g e n e t i co p e r a t i o n , h a v eb e e na c h i e v e d a n da l s o ，t h e c o m b i n a t i o n s 诵n lt r a d i t i o n a la r t i f i c i a li n t e l l i g e n c em e t h o d sm a k eb e t t e re v o l u t i o ne f f i c i e n c y r e s e a r c h e so np a t t e r nl a wa n dc o n v e r g e n c eo fg e pi nt h e o r yh a v ea l s oy i e l d e ds o m e o u t p u t s g e pi sn o ww i d e l yu s e di ns y m b o l i cr e g r e s s i o n ，c l a s s i f i c a t i o n , t i m es e r i e sp r e d i c t i o n a f t e ra l l ，s i n c et h ei n v e n t i o no ft h eg e pa l g o r i t h mt h e r ea r eo n l ya b o u tt e ny e a r s m a n yf i e l d s i nb o t l lo ft h e o r i e sa n da p p l i c a t i o n so fg e pa r ew a i t i n gf o rf u r t h e re x p l o r a t i o n s b a s e do nt h ew o r ko fp r e v i o u sr e s e a r c h e r s ，t h i sp a p e rs t u d i e st h er e s e a r c hs t a t u s ， p r i n c i p l e s ，d e c o d i n gm e t h o d sa n da p p l i c a t i o n so fg e et h ew o r km a i n l yi n c l u d e sf i v ep a r t sa s f o l l o w s ： t h ef i r s tp a r td e s c r i b e st h et h e o r i e sa n dt e c h n o l o g i e so ft h et r a d i t i o n a lg e n e t i ca l g o r i t h m s a n dg e n e t i cp r o g r a m m i n g t h es e c o n dp a r ti n t r o d u c e st h ek e yf a c t o r sa n dp r o c e s s e so ft h eg e n ee x p r e s s i o n p r o g r a m m i n ga n da n a l y z e st h ee s s e n t i a ld i f f e r e n c e sa m o n gg e p , g a a n dg p t h et h i r dp a r ta n a l y z e st h ed e f i c i e n c i e so ft r a d i t i o n a lg e pd e c o d i n gm e t h o d sa n d p r o p o s e s an e wg e pd e c o d i n gm e t h o dn a m e l yt h en o n - p h y s i c a l t r e ed e c o d i n g ，w h i c h e s t a b l i s h e sa n do p e r a t e st h ee x p r e s s i o nt r e ei nt h ed e c o d i n gp r o c e s sw i t h o u tar e a lp h y s i c a l s e n s ea n dt h u sc a nr e d u c ec o m p u t a t i o nc o m p l e x i t y ； i nt h ef o u r t hp a r t , t h eg e pa l g o r i t h mi sa p p l i e dt ot h ep r e d i c t i o no ft h es t o c kt r e n da n d s y m b o l i cr e g r e s s i o na n da c h i e v e sg o o dr e s u l t s ； t h el a s to ft h et e x ts u m m a r i z e dt h ep a p e r ，a n a l y z e dt h ep r o b l e m so ft h i ss t u d ya n dt a k e a 9 0 0 dp r o s p e c to ff u t u r ed e v e l o p m e n t k 呵w o r d s ：g e n e t i ca l g o r i t h m ；g e n e t i cp r o g r a m m i n g ；g e n ee x p r e s s i o np r o g r a m m i n g ： g e p d e c o d i n g 目录 】 】 i 1 ：! 6 7 8 8 8 9 2 2 4 遗传算法流程9 2 3 遗传程序设计10 2 - 3 1 遗传程序设计的特点1 0 2 3 2 遗传程序设计的基本要素1 1 2 3 3 遗传程序设计流程1 2 2 4 遗传程序设计的变体1 3 2 5d 、结1 4 第三章基因表达式编程 3 1 染色体与表达式树1 5 3 1 1g e p 编码规则15 3 1 2g e p 解码方式1 6 3 1 3 多基因染色体1 6 3 2g e p 算法要素17 3 2 1 适应匠度函数1 7 3 2 2g e p 中的常数处理1 8 3 2 3 遗传算子1 9 3 3 算法流程2 3 3 4 小结2 3 5 3d 、结3 5 第六章结论与展望 6 1 结1 沦3 6 6 2 展望3 6 参考文献一3 7 到c 谢4 2 附录( 攻读硕士学位期间发表录用论文) _ 。4 3 1 1 论文研究的背景及意义 第一章绪论弟一早三百下匕 电子计算机是2 0 世纪最伟大的发明之一，它极大加速了文明发展的进程，使人们 从繁重重复的事务中解脱出来。人工智能( a r t i f i c i a li n t e l l i g e n c ea i ) 是研究、开发用 于模拟、延伸和扩展人的智能的理论、方法、技术及应用系统的一门新的技术科学。它 为计算机的应用装上了腾飞的翅膀，使计算机可以模拟人类的思考，从某些方面可替代 人脑，所有的应用计算机解决复杂问题的方法都是人工智能的研究方向。现在已经研究 及应用的人工智能方向包括：自然语言处理，知识表现，智能搜索，机器学习，模式识 别，人工神经网络，数据挖掘，演化计算等。 演化计算又称进化计算，是模拟自然界生物进化过程而发展起来的一种通用问题求 解方法。根据达尔文的进化论，地球生物从最初的简单生命物质经过漫长的时空进化到 各种形态各异的动植物，其主要的进化动力是遗传、杂交、变异与自然选择。遗传保证 了物种的相对稳定，杂交与变异产生了区别于上代的相似个体，环境对个体的选择使得 只有越适应环境的个体才越有生存的希望，保证了物种的进化。进化计算即是模拟自然 界生物进化的形式，将所求问题的解编码成一定形态的个体，首先随机产生一定规模个 体组成的初始种群，当然种群中的个体即是问题的可能解，通过选择、遗传、杂交、变 异等算子产生下一代种群，根据一定的适应度规则，通过若干代的进化最终产生完美解 或较理想的解。 较早提出的演化算法是美国m i c h i g a n 大学j h o l l a n d 教授于19 7 5 年首先提出的遗传 算法( g e n e t i c a l g o r i t h m ，g a ) 【l ，发表了第一本比较系统论述遗传算法的专著，自 然系统与人工系统中的适应性( ( a d a p t a t i o ni nn a t u r a la n da r t i f i c i a ls y s t e m s ) ) ) ，较系统 地阐述了该算法。 1 9 8 9 年美国s t a n f o r d 大学的j o h nrk o z a 提出了用层次化的计算机程序来表达问 题的遗传程序设计( g e n e t i cp r o g r a m m i n g ，g p ) 【3 】，成功地解决了许多问题。1 9 9 2 年，k o z a 发表了他的专著遗传程序设计：基于自然选择法则的计算机程序设计【4 】。1 9 9 4 年， 他又出版了 遗传程序设计，第二册：可重用程序的自动发现1 5 1 ，以此完成了遗传程 序设计的较为完整的理论。 2 0 0 1 年1 2 月，c a n d i d a 在遗传算法与遗传程序设计的基础上提出的基因表达式编 绍了基因表达式编程方法及其运用于问题求解、函数挖掘、符号回归、时间序列预测， 细胞自动机、及其进化动力学原理等。c a n d i d a f e r r e i r a 2 0 0 6 年又又出版了第二本专著 g e n ee x p r e s s i o np r o g r a m m i n g ：m a t h e m a t i c a lm o d e l i n gb ya l la r t i f i c i a li n t e l l i g e n e e 对 上述问题进行了更深入的探讨。 自从g e p 问世以来由于其简洁的形式与高效的性能使得越来越多的人们参与其中。 研究人员对基本的g e p 进行了各种改进以适应不同的环境，还使之与传统的人工智能 方法相结合提出了新的改进算法，并将g e p 算法运用到其他方面取得了一定的成果。 人们对g e p 理论的探索也有了一定的进展。 国内外研究做得比较深入的有武汉的康立山教授团队，四川的唐常杰教授团队， i l l i n o i s 大学的c h iz h o u 教授等。下面将从基本g e p 要素的改进，g e p 与传统人工智能 方法相结合，g e p 的应用研究及理论研究的现状进行阐述。 ( 一) g e p 改进及理论研究 l 、g e p 基因结构的改进 文献【1 1 1 提出的基于多层染色体基因表达式编程的遗传进化算法，新算法引入了多 层染色体的概念，利用染色体构建的层次调用模型对个体染色体进行表达，在实际问题 中取得了很好效果。 文献【1 2 1 将基因由基本的头尾结构改进为头身尾三部分。由于简单的g e p 染色体构 成存在着缺陷，以单基因染色体为例，如果基因头部第一个符号为终结符，则该染色体 没有实际价值，因为基因所对应的表达式只是一个终结符。因此，为了保证头部第一个 2 符号不是终结符，考虑在g e p 基因构成中加入一个身部，它相当于原来的头部，而现 在的基因头部将完全由函数符号构成，使得g e p 染色体中的基因将由头、身、尾三部 分构成，这样提高了g e p 的收敛速度和解的质量。 文献f 1 3 】提出了p g e p 口r e f g e n ee x p r e s s i o np r o g r a m m i n g ) ，借鉴了g _ p 中模块化 结构的思想，提出了一种基于g e p 的松散化模块结构，实现了g e p 中的模块重用。松 散模块结构是随着g e p 的演化动态生成的，能在进化过程中作为子函数重用。 2 、g e p 解码方式的改进 文献【1 q 提出的基因后缀表达式解码( g e n ep o s t f i xe x p r e s s i o nd e c o d i n g ，g p e d ) 只需 对染色体简单处理，即可直接得到染色体相对应的后缀表达式，不需要构造和遍历表达 式树，较传统的g e p 解码方法演化效率提高了两倍左右。 文献【1 5 1 提出的基因阅读运算器( g e n er e a d & c o m p u t em a c h i n e ，g r c m ) 方法只需要 对基因进行阅读，不需要层次化构造树，也不用堆栈，就能实现基因评估。 文献【1 6 - 1 提出了一种基于s c a l e 的基因评估方法，s c a l e 是一个约束线性表，这种s c a l e 创建之后可以一直使用。把基因表达至s c a l e 中避免了表达式树的动态生成和释放，提 高了运行效率。 3 、g e p 演化参数的改进 文献【1 7 1 提出了基因空间均匀分布策略，自适应交叉和变异算子以及淘汰算子等方 法，保持种群多样性，提高了进化效率。 种群多样新是生物进化的基础，也是g e p 找到全局最优解的条件，文献【1 8 】将带权 的函数符和终结符引入到g e p 中，解决了种群多样性的问题。 文献【1 9 。2 1 】都对种群初始化提出了优化策略。分别提出了基因空间均匀分布策略，基 于均匀设计的基因表达式编程算法，和可以产生具有较高个体适应度和基因多样性种群 的优势种群产生策略。实验表明，优势初始种群产生策略可以显著提高进化的成功率。 g e p 个体编码中尾部存在着冗余编码，不对表达式树的翻译产生影响，称为中性区 域，文献瞄】对g e p 中性区域存在的特点进行了分析，研究了中性突变在进化中的作用， 表明了中性区域是进化的关键因数。 文献【2 3 】分析了g e p 个体长度的设计对求解效率的影响，设计了称之为开放阅读框 的过滤算子，提出了动态调节个体的有效编码区域，能进化出更高适应度的最优解且减 少了运行时间。 文献【2 4 】通过引入模拟退火算法来调整进化过程中的变异概率，该方法能够根据种群 解的适应度自适应地调整搜索区域，实验验证，该方法提高了算法效率。 3 传统的基因表达式编程算法存在局部优化的缺陷，文献【2 5 1 提出了以基因组多样性制 导的分阶段进化挖掘算法d g g e p 。采用动态遗传算子设计和群体规模控制方法，使进 化更快速跳出局部最优。 传统g e p 采用静态适应度函数，使得后期进化速度和整体质量很难快速提高，文 献【2 6 1 提出了远缘繁殖策略和动态适应度函数策略，增加了种群的多样性且有利于选择较 优的进化个体。 传统g e p 算法存在局部收敛方面的缺陷，为了解决这一问题，文献【2 刀提出了快速跳出 局部最优的v p s g e p 算法。 4 、g e p 与其他传统人工智能方法相结合 模拟退火算法是一种通用的优化算法，理论上算法具有概率的全局优化性能， 模拟退火算法是通过赋予搜索过程一种时变且最终趋于零的概率突跳性，从而可 有效避免陷入局部极小并最终趋于全局最优的串行结构的优化算法。文献1 2 o l 将模 拟退火算法与g e p 相结合，提高了g e p 性能。 文献1 3 1 】【3 2 1 将免疫算法与g e p 相结合，算法通过构造新的病毒和感染机制，使g e p 在进化过程中调整参数，加速了种群进化并避免早熟收敛的发生，提高了进化的速度。 传统人工智能算法人工神经网络，是一种模拟动物神经网络行为特征，进行 分布式并行信息处理的算法数学模型。文献 3 3 3 5 g e p 与传统的神经网络算法相结合产 生了很好的效果。 5 、g e p 理论研究 王悦，唐常杰等1 3 6 ，通过分析g e p 的基因结构，定义了g e p 模式的概念，并从理论角 度解释了g e p 的进化机理以及其强大的最优解发现能力。通过一系列推导获得了公式 化g e p 模式定理，并将该结果与实际g e p 的运行结果对比分析，验证这些理论结果。 g e p 模式定理的提出为g e p 算法改进评估提供了量化的依据。 杜欣，丁立新于 数组定义为：c o u n t n o d cc o u n t a x r w bw 为基因长度 1 、向后找参数 从基因字符串的起始位置开始，设置对应的c o u n t a r r 元素的值，第0 个元素的p a r e n t 域可设置为1 ，其它元素设置为对应的如上说明的值，对应位为函数集字符不用设置 v a l u e 域，直至c o u n t a r r i 不存在父节点。 算法：向后找参数 输入：计算数组c o u n t a r r ，基因字符串，参数实际值 输出：处理后的计算数组c o u n t a r r ，基因最后有效位置i b e g i n 2 7 设置c o u n t a r r 0 元素的各个域，及与其相关的参数节点的p a r e n t 域； i = l ； w h i l e ( c o u n t a r r i 存在父节点) e n d 经过该过程处理，当a = 2 ，b = l 图4 1 对应基因字符串所对应的计算数组如下： 表4 2 向后找参数完成后c o u n t a r r 元素的值 f i e l d 絮二 ol23 4 5678 、 p a r e n t1001l2266 0 】 l357 c h i l d 【i 】 246 8 c h + ba|aba v a l u e 21221 说明：该基因字符串0 8 位为有效位，对应计算数组也如此。 2 、向前推基因值 通过第一步的运算，我们已知基因最后有效位置i ，下面的工作就是从第i 位向前 计算基因值，从第i 位向前找与i 相同p a r e n t 的几位，p a r e n t 相同说明为同一函数的参 数，以这几位为参数，根据p a r e n t 值找到对应的函数，计算，结果保存为p a r e n t 为的v a l u e 域，而后以此方法向前，直至首位，运算最终首位的v a l u e 域的值即为基因的值。 算法：向前推基因值 输入：基因最后有效位置i ，处理后的计算数组c o u n t a r r 输出：基因的值 b e g i n 删l e ( i 0 ) 以最后相同p a r e n t 域的k 位为参数，以第p a r e n t 位为函数计算，结果保存为 第p a r e n t 位的v a l u e 域； 2 2 向前推基因值的具体步骤为：7 , 8 位有相同的 v a l u e 为参数，得出结果作为第6 位的v a l u e ， 位为函数，5 , 6 位v a l u e 为参数，得出结果 ，最后可得第0 位的v a l u e ，即是基因的最终值。 表4 3 计算数组c o u n t a r r 各元素v a l u e 变化( a _ 2 j 产1 ) 汰field 0l23 4 5678 、 p a r e n t10o112266 c h + 幸 ba|aba v 酊u e2l22 1 ( t a i l ) 场l u e 2l2 2 ( t a i l ) 2l v 砒u e 42 l ( t a i l ) 222l v a l u e5 l 4 ( t a i l ) 2l222l 从以上分析可知，向后找参数直至基因的有效尾部，再向前计算基因的值的方法非 常直观且有效，不论函数的参数是多少，同样可以非常简单有效的计算出基因的值。 4 4 小结 性能是遗传程序设计领域的重要研究议题。为进一步提升g e p 的性能，本章就其 g e p 染色体的解读机制做了深入探讨，给出了新型的非物理树g e p 解码算法。技术上 说来，我们先构建一映射数组，从数组头部开始向后找到基因的有效尾部，而后从尾部 向前运算，继而方便地得出基因的值。非物理树g e p 解码算法在解码过程中不需要物 理树的建立与释放，其在不影响原算法其他性质的情况下极大地提高了传统解码算法的 运行速度，在一定程度上解决了g e p 进化过程中表达式树建立和释放消耗巨大时空资 源的瓶颈。 第五章实验与分析 g e p 算法以其优越的性能已应用于科学研究的各个方面，尤其是在符号回归与时间 序列预测中取得很好的效果。下面就应用非物理树g e p 解码算法对符号回归与股票走 势的时间序列预测进行实验与分析。 5 1 符号回归实验与分析 符号回归是数据挖掘中的一种形式，也称函数发现。从实验观察数据中得出相关变 量的函数关系，一直是人们研究解决的问题。符号回归所要解决的问题就是对给定的一 组数据进行函数建模，或者说在数据中挖掘出函数表达式，找出一个符号形式的数学公 式，以指定的精度拟合一组相关变量的有限样本。一般情况下，符号回归的过程包括数 学函数形态的确定、函数中数字常量和系数的确定。传统的线性回归和非线性回归等需 事先指定拟合公式的形式，通过回归分析确定拟合公式中的待定参数，而g e p 符号回 归算法无需事先指定拟合公式的形式，公式的形式和其中的参数均在回归的过程中确 定。因为很多情况下我们没有对问题的先验知识，不知函数关系模型，传统方法很难找 到一定拟合精度的函数关系，而g e p 具有的自适应学习能力，可很好的解决这一难题。 5 1 1 实验 符号回归测试函数y 2 z 。+ x z + x + l ，在( o ，1 0 ) 之间随机生成1 0 个样本。在不 预先知道测试函数类型的前提下，搜索挖掘y2 ，【砷的表达式。这就是只知一组实验数 据，不知其他任何条件，来找出变量的函数关系。 g e p 算法采用单基因染色体，函数集 + ， ，终端集 x ) ，头长1 5 ，变异概率 o 0 8 ，单点重组概率o 3 2 ，选择采用赌盘算法，种群规模1 0 0 ，每次运行直至成功为止。 由于每次运行成功的次数波动很大，少则几次，多则上千，这样很难进行运行时间统计， 故只有让其多次运行才能有很好的统计稳定性。实验采用成功运行1 0 0 0 次，统计运行 时间，下面是在三台不同电脑上，运行3 次，传统g e p 解码与非物理树g e p 解码的对