（计算机软件与理论专业论文）基于基因表达式编程的分类算法研究及应用.pdf

浙江工业大学硕十学位论文 基于基因表达式编程的分类算法研究及其应用 摘要 数据挖掘是当今计算机应用技术和理论研究中最热门的领域之一，经过二十多年的发 展，已经逐渐建立起系统的挖掘理论和成熟的挖掘技术。分类规则挖掘作为数据挖掘的一 个重要分支，引起了不同领域学者的广泛关注，其中以遗传算法和遗传程序设计为代表的 演化计算方法因为其智能性、并行性、不确定性等诸多特点成为其中一个特殊的分支。基 因表达式编程是在结合遗传算法和遗传程序设计的优点的基础上提出的一种新的遗传算 法，在数学建模方面取得了非常好的效果并在许多工程领域取得了应用。 本文以基因表达式编程和分类规则挖掘为主要研究对象，研究基于基因表达式编程的 神经网络和决策树算法及其在分类规则挖掘中的应用。本文的主要工作和成果如下： 1 在简要介绍g e p 技术主要思想的基础上，分析了基因表达式编程的编码特点及其 技术优势的实质，总结了一些比较有影响的g e p 分类方法，着重讨论和比较了基本g e p 分类方法和精确与简洁g e p 分类方法。 2 分析指出了传统g e p 神经网络方法不能用于二次及以上建模问题的缺陷，并提出 了一种混合式g e p 神经网络方法，并在此基础上进一步提出了一种改进的g e p 神经网络 演化方法，实验证明该方法在回归和分类问题中均能取得良好的效果。 3 针对g e p 神经网络解决多分类问题需要进行数据切分的不便之处，引入g e p 决策 树算法，并针对该算法在常数数值数组产生策略中的几点不足，提出了一种基于均匀常数 分布的g e p 决策树算法，实验证明该算法优于传统c 4 5 算法和标准g e p 决策树算法。 4 在开源数据挖掘平台w e k a 上独立实现了混合式g e p 神经网络算法，在丌源演化 计算研究平台e c j 上独立实现了标准g e p 决策树算法和基于均匀常数分布的g e p 决策树 算法，为针对各种算法的验证和比较提供了支持。 关键词：基因表达式编程，神经网络，决策树，回归，分类 浙江t 业火学硕 ：学位论文 r es e a r c ha n da p p l i c a t i o no f g e n ee x p r e s s i o np r o g ra 僵m i n gb a s e d c l a ss i f i c a t i o na l g o i u t h m s a b s t r a c t da _ t am i 血g ( d m ) i so n eo ft h eh o 骶s tr e s e a r c ht o p i c si i lc 1 t e n tc o m p u t e ra p p l i c a t i o n t e c h i l o l o g ) ra n dt 1 1 e o 眄r e s e a r c ha r e 色w i t l lt 1 1 ed e v e l o p m e n to fm o r em a n2 0y e a r s ，i th a s e s t a _ b l i s h e ds y s t e m a t i ct l l e o 巧a n dm a t u r et e c l l i l o l o g y c 1 a s s i f i c a t i o ni so n eo ft h em o s ti r r l p o r t a n t b m c h e so fd ma i l di th a sg o t t e n 晰d ea 仕e n t i o nb ye x p e n s 舶mv 撕o u sf i e l d s e v o l u t i o n a 巧 c o m p u t a t i o n ( e c ) w 1 1 i c hi sr e p r e s e n t e db yg e n e t i ca l g o r i t h m s ( g a s ) a n dg e n e t i cp r o g r a m m i n g ( g p ) h a sb e c o m eas p e c i a lb 舢c hf o ri t s 证q u ec o m b i r 哦i o no fi n t e l l i g e n c e ，p a r a l l e l i s m g e n e e x p r e s s i o np r o g 姗m i n g ( g e p ) i sak j n do fn e wg e n e t i ca j g o 打t h m sc o m b i n i n gt l l ea d v a n t a g e s o fb o m g a sa l l dg p ，w l l i c hh a sa c l l i e v e dg o o dp e r f o m a n c emm a 血e m a t i c a lm o d e l i n ga n dh a s b e e na p p l i e dm m a n ye n g m e e r i n gf i e l d ss u c c e s s 向l l y i nt 1 1 i st l l e s i s ，o u rm a i l la t t e n t i o nf o c u s e do ng e p 锄dc l a s s i f i c a t i o i l ，w ed i dr e s e a r c ho ng e p n e u m ln 咖o r k ( g e p n n ) a 1 1 dg e p d e c i s i o n 仃e e ( g e p d t ) a l g o r i t h m s 嬲、e l l 鹊i t s 印p l i c a t i o n 洫c l a s s i f i c a t i o n t h em a i nw o r ka n da c k e v e m e n t sa r ea sf 0 u o 、v s ： 1 t h ee n c o d m gc h a r a c t e r i s t i c 锄dt l l eh y p o s t a s i so fa d v a n t a g e s 、v e r ea n a j y z e db a s e do nt h e i n t r o d u c t i o no ft 1 1 em a i ni d e ao fg e p s o m ei n n u e n t i a lg e pb a s e dc l a s s i f i c a t i o nm e t h o d sw e r e s l m m l a r i z e d ，e s p e c i a l l yd i s c u s s e d 锄dc o m p a r e dt h eb a s i cg e pc l a s s i f i c a t i o nm e t h o da 1 1 da i l a c c u r a t ea j l dc o m p a c tg e pc l a s s i f i c a t i o nm e t l l o d 2 t h ed e f e c tt t l a t 仃a d i t i o n a jg e p n nc 锄tb eu s e di nq 陇d r a t i co rm o r ec o m p l e xm o d e l i n g ，a 峪p o i n t e do u t ，a n d p r o p o s e dal 【i n do fh y b r i dg e pn e u f a ln e t 、v o r km e m o d ( h g e p n n ) ， m n h e rm o r e ，a ni m p r o v e dm e t h o df o re v o l v i n gg e pn e m a ln e “v o r kw a u sp r o p o s e db a s e do n h g e p n n e x p e r i m e n t ss h o w e dt h a tg o o dr e s u l t sc a nb ea c m e v e db o t hi ns y m b o l i cr e 铲e s s i o n a n dc l a s s i f i c a t i o np r o b l e m 3 a c c o r d i n gt ot l l et r o u b l eo fs p l i t t i n gd a t as e t si i lm u l t i c 1 2 u s s i f i c a t i o np r o b l e mf o rg e p n e u r a ln e m o r km e t h o d s ，g e pd e c i s i o n 仃e ea j g o r i t h mw a si n t r o d u c e d w ep r o p o s e dac o n s t a n t s u n i f o 衄d i 矧b u t i o nb a s e dg e pd e c i s i o n 骶ea j g o r i t d c g e p d db a s e do nt t l e i i 浙江丁业大学硕一i ：学位论文 d e f i c i e n c i e so fc o n s t a n t sa r r a ys t r a t e g yf o rs t a n d a r dg e pd e c i s i o nt r e ea l g o r i t h m e x p e 订m e n t s s h o w e dt h a tu d c g e p d ta l g o r i t h m 、v a sb e t t e rt 1 1 a l ln a d i t i o n a lc 4 5a l g o r i t h ma i l ds 切n d a r d g e p d t 甜g o t h m 4 1 1 1 eh g e p n na l g o r i 岫l 、懈i m p l e m e n t e di no p e ns o u r c ed a 诅m i n i n gp l a t f o mw e k a a s 、v e l la ss t a i l d a r dg e p d t a l g o r i t h ma j l du d c - g e p d ta j g o r i t h mi ne v o l u t i o m yc o m p u t a t i o n r e s e a r c hp l a t f o 珊e c j ，w m c hs u p p o m dm ev a l i d a t i o na 1 1 dc o m p 撕s o no fd i 仃e r e n ta l g o 酬恤s k e yw o r d s ：g e n ee x p r e s s i o np r o g r ；u n i n i l l g ，n e u r a ln e t 、) r o r k ，d e c i s i o nt r e e ，s y m b o l i c r e g r e s s i o 玛c l a s s i f i c a t i o n 浙江工业大学 学位论文原创性声明 本人郑重声明：所提交的学位论文是本人在导师的指导下，独立进行研究工作 所取得的研究成果。除文中已经加以标注引用的内容外，本论文不包含其他个人或 集体已经发表或撰写过的研究成果，也不含为获得浙江工业大学或其它教育机构的 学位证书而使用过的材料。对本文的研究作出重要贡献的个人和集体，均已在文中 以明确方式标明。本人承担本声明的法律责任。 储戳：馓 醐矽膊场胁加 j 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留 并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本 人授权浙江工业大学可以将本学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文，将本人的学位 论文委托研究生院向中国学术期刊( 光盘版) 电子杂志社的中国博士学位论文全 文数据库、中国优秀硕士学位论文全文数据库投稿，希望中国博士学位论文 全文数据库、中国优秀硕士学位论文全文数据库给予出版，并同意在中国博 硕士学位论文评价数据库和c n k i 系列数据库中使用，同意按章程规定享受相关 权益。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密口。 作者签名： 导师签名： 以上相应方框内打“ ) 日期：矿年f 月彩日 日期：2 j 婚睁、钞月日 浙江丁业人学硕十学位论文 第1 章绪论 1 1 论文选题及其研究意义 数据挖掘( d a t am i n i n g ，d m ) 【1 】是当今计算机应用技术和理论研究中最热门的领域 之一。随着信息技术的发展，特别是数据库技术和数据仓库技术的发展，人们获取数据的 速度远远超过人类从数据中吸取信息的速度。很多企业和组织以超乎我们想象的数度搜集 信息，存储信息，但是很少有企业能够真j 下地将这些信息转化成能够为自己服务的资源。 人们每天所提到的信息化，在企业和组织的日常运作中仅仅反映为数字化或者无纸化办 公。信息化没有因为我们主观上的乐观而变成美好的现实，信息化离我们还十分遥远。随 着我们对于信息化理解的深入，越来越多的学者关注如何让这些堆积如山的数据为我们所 用。强大的社会需求是研究的最大动力，如何有效地利用数据为自己的商业决策提供科学 的支持，成为众多企业所关注的重要问题。在这样的环境下，数据挖掘技术应运而生。 数据挖掘技术经过十多年的发展，已经逐渐建立起系统的挖掘理论和成熟的挖掘技 术；成为一门以关联规则挖掘、分类规则挖掘、聚类规则挖掘为主要形式，以数据库技术、 统计学、人工智能、可视化技术和信息技术为主要工具的多学科交叉的应用技术。其应用 范围也从最初的商业应用逐渐扩展到医疗、金融、生物、电信、军事、体育等诸多领域。 数据挖掘成为越来越多的科学家、研究人员、工程应用人员、商人、医生所关注的对象。 分类( c l a l s s i f i c a t i o n ) 规则挖掘作为数据挖掘的一个重要分支，在过去的十多年中引 起很多来自不同领域的学者的注意。学者们提出了以信息论为基础的决策树算法、以概率 论为基础的贝叶斯( b a y e s i a l l ) 方法，以神经科学为基础的神经网络方法( n e 删n e r k ， n n ) 等等，这些算法基本上都是确定性算法。以自然进化为基础的演化计算技术因为其 智能性、并行性、不确定性等诸多特点成为其中一个特殊的分支。 演化计算( e v o l u t i o n a r yc o m p u t a t i o n ) 引中最重要的分支是遗传算法【3 4 1 ( g e n e t i c a l g o r i t h m s ，g a s ) 。遗传程序设计( g e n e t i cp r o gr _ a 舢嘶n g ，g p ) 【5 6 j 是遗传算法的一个变 体。遗传算法和遗传程序设计这两个算法虽然都遵循自然界优胜劣汰的基本原理，但是它 们最初在工程应用领域具有不同的功能：遗传算法主要用于函数优化，而遗传程序设计则 主要用于建模。以遗传算法和遗传程序设计为代表的演化计算在工程应用等优化问题中与 l 浙江工业人学硕士学位论文 传统的数学方法相比，表现出非常明显的优势。而且近年来演化计算在数据挖掘，特别是 分类规则挖掘中的应用研究已经取得了相当大的发展。虽然很多学者认为演化计算只是优 化和搜索算法，但是它在数据挖掘领域的良好效果已经使其成为数据挖掘中不可或缺的一 个重要工具。 基因表达式编程( g e n ee x p r e s s i o np r 0 酉a 删m n g ，g e p ) i m l 是c f e r r e h 在遗传算法 和遗传程序设计的基础上提出的一种新的遗传算法，它同传统的遗传算法和遗传程序设计 在主要步骤上非常相似，但在个体的编码方式及结果的表现形式上有明显的区别。基因表 达式编程同时结合了遗传算法和遗传程序设计的优点，克服了它们各自的缺点，为解决复 杂的建模和优化问题提供了巨大的潜力。正因为其优点和良好的效果，使得基因表达式编 程在并不漫长的时间里引起了演化计算领域的广泛关注甚至争议。 本文以基因表达式编程和分类规则挖掘作为主要对象，研究基于基因表达式编程的神 经网络和决策树算法在分类规则挖掘应用中的几个重要问题。本文所关注的问题在演化计 算和数据挖掘领域均是新出现的热点理论问题，是演化计算应用研究的重要方向和学科前 沿研究方向，是演化计算和数据挖掘相结合的学科交叉问题。本文通过解决现有基于g e p 神经网络和决策树算法在分类规则挖掘技术中存在的问题，将明显提高分类规则挖掘的精 度和效率，在商业、医疗、金融等领域具有重要的实用价值和广泛的应用前景。 1 2 选题的国内外研究现状 分类规则挖掘是数据挖掘的一个重要分支，同时也是机器学习、模式识别、专家系统、 统计学和神经生物学的研究领域，并已开发出许多相应的算法，主要包括决策树方法、贝 叶斯方法、神经网络方法、七最近邻方法、粗糙集方法、基于案例的推理方法和遗传算法 等。分类规则的预测的准确率、计算速度、鲁棒性、可伸缩性和可解释性是评估分类规则 的五个标准【l 】。已有许多关于不同分类方法的比较，并且该问题仍然是一个研究课题。需 要说明的是，没有一种方法对于所有的数据均优于其它的方法。在衡量一个方法的时候必 须考虑以上五个标准，并且可能设计折衷，使得寻求更好的方法进一步复杂化。 1 2 1 决策树 从第一个具有实用价值的决策树算法的提出到今天决策树算法的广泛应用，决策树算 法的发展经历了一个由简单到复杂、由浅显到深入的过程。 最早的决策树学习系统要追溯到h 岫t 等人于1 9 6 6 年提出了第一个用于构造决策树的 概念学习系统c l s 【1 0 】。在c l s 的基础上，后人陆续提出了多种决策树学习算法，其中最为 2 浙江工业人学硕十学位论文 有影响的是q u i n l a n 于1 9 8 6 年提出的i d 3 算法【1 1 】。i d 3 算法是最经典的决策树算法，应用非常 广泛，但它存在着许多不足，因此，q u i n j a i l 于1 9 9 3 年又提出了c 4 5 系统。 c 4 5 算法【1 2 1 是以i d 3 算法为核心的完整的决策树生成系统。它通过两个步骤来建立决 策树：树的生成阶段和树的剪枝阶段。与i d 3 算法相比，c 4 5 算法在效率上有了很大的提高， 不仅可以直接处理连续型属性，还可以允许训练样本集中出现属性空缺的样本。但是，c 4 5 算法没有考虑属性之间的联系，仍然是一个单变量的决策树系统。i d 3 算法和c 4 5 算法虽然 在对训练样本集的学习中可以尽可能多地挖掘信息，但其生成的决策树分枝较多，规模较 大。 为了简化决策树的规模，提高生成决策树的效率等问题，又提出了一系列的决策树算 法，典型的有c a r t ，s l i q ，s p 对n t 等1 1 3 15 1 ，这里不再详细讨论。 1 2 2 神经网络 神经网络【1 6 ，1 7 1 是分类规则挖掘方法中最活跃的分支之一。神经网络是以被称为感知器 的单元为基础的。一个感知器的学习过程，或者说神经网络的学习就是通过各种方法来学 习这些权值，因为这些连接权值中存储着求解这些具体问题所需要的知识。b p 神经网络是 多层感知器中最著名的训练算法。神经网络具有对噪声数据的承受能力，尤其是它对未经 训练的数据的分类能力。实验表明，神经网络在某些分类问题上具有比符号方法更好的表 现。 但是神经网络的一个缺点在于对于学习过程，没有一个通用的规则可以指定什么样的 网络结构、什么样的训练方法、什么样的参数选择比较合适。它所采用的规则是“试误法”， 也就是试验大量的神经网络，最后找到一个合适的解。而关于网络结构和参数设置的问题， 只要依靠个人经验。所以，在很多情况下人们批评神经网络的训练时间过长。另一方面， 由于人们很难解释蕴含在学习权中的意义。因而神经网络也被人们称为“黑盒”。 1 2 3 遗传算法 基于遗传算法和遗传程序设计的遗传分类器以其全局搜索和并行性逐渐为很多研究 人员所关注。遗传算法的主要特点是编码简单，具有很好的全局搜索和局部搜索能力，不 容易陷入局部最优。虽然两种方法的编码方式不同，但是这两种技术在数据挖掘，特别是 在分类规则挖掘中都取得了很好的效果。其中d e g o l d b e 唱【3 】在遗传算法领域的重要工作 和j k o d l 8 1 在遗传程序设计领域的工作都成为演化计算领域的开创性工作。a a f r e i t a s 【1 9 】 浙江工业大学硕士学位论文 对演化计算在数据挖掘中的应用做了非常详细的总结。 随着人们对遗传算法和遗传程序设计研究的深入，它们编码的各自局限性越来越多地 暴露出来。为了解决这些问题，很多学者试图从编码的角度来对遗传算法和遗传程序设计 进行改进。其中最重要的方法之一就是基因表达式编程方法。 2 0 0 1 年c f e r r e i r a 在结合遗传算法和遗传编程的优点的基础上提出了基因表达式编 程的概念，并相继发表了一些相关理论基础及应用实例的文章和专著，详细讨论了将基因 表达式编程方法运用于数据挖掘中的基本方法【7 捌。近年来，国内外很多学者都在进行基因 表达式编程的研究，并将其应用于许多领域，取得了较大进展。四川大学唐常杰教授等对 基因表达式编程技术本身及其在数据挖掘中的应用进行了较为系统和深入的研究，取得了 一系列的研究成果【2 0 。2 5 1 。中国地质大学檗之华教授等将基因表达式编程应用于实际工程中 的采煤工作面瓦斯涌出量预测，取得了良好的效果【2 6 j 。伊利诺大学芝加哥分校学者c h iz h o u 等在改进基因表达式编程技术本身的基础上，提出了用基因表达式编程演化分类规则的另 一种方法【2 7 ，2 剐。犹他州立大学的r o b e r tg e m p e l e r 将基因表达式编程成功应用于数字图像压 缩【2 9 1 。随着越来越多的学者不断关注基因表达式编程，关于基因表达式编程在数据挖掘中 特别是在分类规则中的研究和应用将会取得更大的发展。 本文的主要研究内容是基于基因表达式编程的神经网络和决策树算法研究及其在分 类规则挖掘中的应用，它们分别是基因表达式编程与神经网络算法和基因表达式编程与决 策树算法的结合，目前只有基因表达式编程的发明者c 锄d i d a 对其进行了初步的描述，在 理论和实践方面均留下了许多空白值得进一步深入研究。 1 2 4 其它分类方法 在许多实际应用中，某些训练样本集可能是很不精确的，在这样的情况下，可能很难 得到确定的分类规则。有一类方法能够用来推断出一些近似的规则，这种方法就是粗糙集 的方法。粗糙集理论是由波兰学者z p a w l a k 在1 9 8 2 年提出的【3 0 】，并于1 9 9 1 年出版了专 著【3 1 1 ，系统地阐述了该理论，奠定了严密的数学基础。粗糙集是一种对于不完整和不精 确信息进行建模的较好的数学工具，并广泛应用于数据挖掘中【3 2 捌】。 另一个主要的研究分支就是基于统计学技术的分类方法。经典的统计学技术基本上来 源于f i s h e r 关于线性可分的早期工作。这一类方法通常假定存在某种已知的密度函数。现 代统计模型包括七最近邻方法【3 5 1 和支持向量机3 6 1 通常都是与分布无关的方法。贝叶斯分 类工具也是一类十分活跃的统计学分类方法，分类算法的比较发现，一种称为朴素贝叶斯 4 浙江工业大学硕十学位论文 分类3 7 1 的简单贝叶斯算法可以与决策树和神经网络分类算法相媲美。另外，还有使用一 个问题解的数据库来求解新问题的基于案例的推理方法【3 8 】。鉴于本文主要讨论的是演化 计算方法在分类规则挖掘中的研究与应用，这里我们不进一步讨论相关的统计学方法。 1 3 论文的主要研究内容 本文的结构安排如下： 第1 章绪论 介绍了论文的选题及其研究意义、选题的国内外研究现状和主要的研究内容。 第2 章基因表达式编程概述 作为全文的理论基础，本章在简单介绍遗传算法和遗传程序设计的基础上引出了 基因表达式编程的概念，详细介绍了基因表达式编程的起源、特点及其基本算法，并 分析了基因表达式编程的编码优势和高效的内在原因。 第3 章g e p 分类方法研究及其应用 详细介绍了两种主要的g e p 分类方法并对它们进行了比较，然后简单介绍了几种 较为有影响的g e p 分类方法，对分类规则挖掘中的一些问题进行了探讨。最后通过一 个具体实例介绍了基本g e p 分类方法在分类规则挖掘中的应用及其效果。 第4 章g e p 神经网络及其改进算法 详细介绍了标准g e p 神经网络算法结构及其特殊遗传算子，并对其缺陷进行了 分析和说明，在此基础上提出了两种改进的g e p 神经网络算法，通过在基准数据和 实际乳腺癌诊断问题上的实验验证了它们在回归和分类问题中的效果，并对结果进行 了分析。 第5 章基于g e p 决策树的分类规则挖掘 分别介绍了处理名词性属性和数值性属性两种类型的g e p 决策树算法，分析了 标准g e p 决策树算法在数值常数数组策略上的缺点，提出了一种基于均匀常数分布 的g e p 决策树算法，通过在基准数据和实际乳腺癌诊断问题上的实验验证了其效果， 并对实验结果进行了较为深入的分析，指出了这种改进算法的优势所在。 第6 章结论与展望 总结了论文的主要工作和后续工作。 5 浙江工业大学硕士学位论文 第2 章基因表达式编程概述 前面我们已经提到，基因表达式编程是在遗传算法和遗传程序设计的基础上提出的一 种新的遗传算法。下面先对遗传算法和遗传程序设计做一个简单的介绍，在此基础上引出 基因表达式编程的概念，并对其进行系统介绍，最后将对其编码特点进行分析。本章关于 基因表达式编程的主要概念引卧8 】。 2 1遗传算法与遗传程序设计简介 2 1 1遗传算法 如前所述，遗传算法是美国密执安大学的j h o l l 锄d 及学生们在2 0 世纪6 0 年代发明 的一种将生物进化理论运用于计算机系统的全局优化自适应概率搜索算法。 传统的经典遗传算法采用若干个定长的二进制符号串来对备选解进行编码，这若干个 个体构成一个种群( p o p u l a t i o n ) ，每个个体被称为个体( i n d i v i d u a l ) ，这些个体的每一位 被称为等位基因( a l l e l e ) ，等位基因可以是 0 ，1 ) 中的任意一个。每次循环的时候，种群 的每一个个体根据当前问题的特点预先设定好的方法对个体的好坏进行评价。这个过程称 为适应度( f i t l l e s s ) 评价。种群中的个体按照与个体适应度成比例的概率来决定其是否能 够被选加入到下一个种群中。这些被选中的到下一个种群中个体要在遗传操作的作用下发 生一些改变，最典型的有杂交( c r o s s o v e r ) 和变异( m 毗l t i o n ) 。在经过这些遗传操作之 后，再次对新的种群中的每个个体计算其适应度。如此一次一次地运行下去，直到满足某 一个预先设定的条件。遗传算法的基本流程见图2 1 所示。 6 浙江工业大学硕士学位论文 图2 1遗传算法的基本流程 为解决各种优化计算问题，人们提出了各种各样的优化算法，如单纯形法、梯度法、 动态规划法、分枝定界法等。这些优化算法各有各的长度，各有各的适用范围，也各有各 的限制。遗传算法是一类可用于复杂系统优化计算的具有鲁棒性的搜索算法，与传统的优 化算法相比，主要有以下特点1 4 j ： 1 遗传算法以决策变量的编码作为主要的运算对象。传统的优化算法往往直接决策 变量的实际值本身，而遗传算法处理决策变量的某种编码形式，使得我们可以借鉴生物学 中的染色体和基因的概述，可以模仿自然界生物的遗传和进化机理，也使得我们能够方便 的应用遗传操作算子。 2 直接以目标函数值作为搜索信息，无需导数等其它辅助信息。 3 同时使用用多个搜索点的搜索信息，具有隐含并行性。 4 使用概率搜索技术，增加了灵活性。 遗传算法提供了一种求解复杂系统优化问题的通用框架，不依赖于问题的具体领域， 具有很强的鲁棒性，所以广泛应用于函数优化、组合优化、生产调度、自动控制、机器 人学、图像处理、人工生命、遗传编程和机器学习等领域。 7 浙江工业大学硕士学位论文 2 1 2 遗传程序设计 遗传程序设计是传统遗传算法的一个衍生和变体。它与遗传算法的主要区别在于种群 中的每个个体不是二进制字符串而是计算机程序。每个计算机程序由一个语法分析树来表 示。每个内部节点( 非叶节点) 由一个函数构成，叶节点由函数所对应的参数构成( 如图 2 2 所示) 。采用g p 求解问题需要确定一下5 个方面的问题： 1 选取适合作为终端节点的元素的集合，这些终端节点作为程序的输入。 2 根据问题的特点，选取合适的函数集合。 3 选取适当的适应度来对种群中的个体在训练数据上的性能进行评价。 4 选择合理的运行参数。 5 根据需要，选择合适的停机条件。 其中函数集合的选择和终端节点的选择应该满足封闭性，即这些函数和终端节点所完 成的运算得到的结构应该仍然属于终端节点集。 图2 2 一个g p 的语法树结构和它对应的数学表达式 g p 除了所使用的个体的性质与遗传算法不同以外，其它的遗传操作与遗传算法基本 类似。但是g p 有一个缺点是由于其树结构的特点，它进行遗传操作的时候比较复杂。同 时，由于树结构的子树杂交和变异，容易导致个体的树结构大小随着运行次数的增加而无 限增长。这种无限增长的问题被称为代码膨胀。 代码膨胀( c o d eb l o a t ) 【5 3 9 ，4 0 1 问题对于g p 来说十分严重。首先，它占用大量计算资 源，使得搜索过程越来越慢，直到最后可用资源耗尽迫使搜索过程终止。其次，膨胀的备 选解经常难于用合理的办法给予改进，从而妨碍g p 产生和发现新的更好的解。第三，膨 胀会减缓适应度评价过程。总之，膨胀导致g p 不得不和时间赛跑，在膨胀迫使搜索过程 停止以前找到最优解。 8 浙江下业大学硕士学位论文 对于寻找代码膨胀解决办法的问题。很多学者投入大量精力研究解决代码膨胀的办 法，而且根据现有理论在这方面已经取得了一定的进展。很多学者仍然在从不同的方面对 现有的g p 技术进行改进。其中重要的仍然是两个主要方面：一种是通过改进新生成的个 体的产生策略，使g p 能够在代码膨胀出现之前更有效的进行搜索，找到更好的解。另一 种是通过各种方式抑制代码膨胀也是一种很好的解决办法。 以上这些方法在解决代码膨胀问题的时候都是基于g p 的表现型为树结构的情况下 进行的，为了避免树结构的无限增长导致的代码膨胀，采用类似于遗传算法的字符串结构 的编码方式来解决该问题的思想逐步为一些学者所采用，其中b g p 【4 1 ，4 2 1 和g e p 【8 1 就是两 个主要代表。 2 2 基因表达式编程的起源和特点 由于遗传算法和遗传程序设计分别存在自己的缺点和限制。基因表达式编程可以说是 遗传算法和遗传程序设计发展道路上的一个不可避免的产物。c f e 玎e h 本人在她的第一 本关于基因表达式编程的书里面也提到，她是在学习遗传算法和遗传程序设计的过程中开 发出基因表达式编程系统的。c f e r r e i m 在她的书中从进化学和生物化学的角度详细论述 了基因表达式编程比遗传算法和遗传程序设计更优越的理论基础。有些遗传程序设计的拥 护者认为基因表达式编程只不过“旧瓶装新酒”；一些研究人员认为基因表达式编程方法是 基于遗传程序设计的线性表达串的特例；四川大学唐常杰教授对基因表达式编程的沿革阐 述了如下的观点【4 3 j ： “遗传算法比喻为父体，它刚性地使用定长的线性字符串作为遗传物质，采用简单编 码解决简单问题；遗传程序设计比喻为母体，它柔性地使用非线性的，不定长的树结构， 采用复杂结构解决复杂问题；而基因表达式编程继承了父母的优点，它刚柔相济，表现为 定长线性串，易于遗传操作，又简介地对应于柔性的具有非线性结构的树结构，从而达到 了简单编码解决复杂问题的目的，使得在速度上比g a 和g p 提高了1 0 0 6 0 0 0 0 倍。” 9 浙江工业大学硕士学位论文 图2 3g e p 与g a 和g p 的继承关系图 唐常杰教授关于基因表达式编程的沿革的客观评价形象而生动地描述了基因表达式 编程与传统的遗传算法和遗传程序设计的关系，也简要概括了基因表达式编程的性质和特 点。关于其性质的介绍将是本章后续部分的主要内容。 2 3 基因表达式编程的组织结构 基本基因表达式算法的基本步骤从随机产生一定数量的染色体个体( 初始种群) 开始。 然后对这些染色体进行表达，依靠一个适应度样本集( 也称为选择环境，即问题的输入) 计算出每个个体的适应度。然后个体按照其适应度被选中，进行有修饰的复制。留下具有 新特性的后代。接下来，这些新的个体也要经历相同的发展过程：基因组的表达，面临选 择环境，选择和有修饰的复制。该过程重复若干代，直到发现一个优良解。 像所有的遗传算法一样，g e p 采用个体种群，而且最开始必须产生初始种群。后续 的种群都是这些初始种群或者奠基种群经过遗传修饰得到的后代。我们已经看到，在基因 型表现型系统中，我们只需要产生个体染色体，然后由发展过程来控制后续工作。因此， 在g e p 中，只需要随机产生初始种群的简单个体染色体结构。而且这是一个非常小的任 务。 对每个问题而言，我们必须选择产生染色体的符号，也就是说，我们必须选择适合解 决当前问题的函数集和终点集。我们还要选定每个基因的长度，每个染色体中的基因个数， 以及这些染色体的表达式之间如何相互作用。最后，我们必须提供一个选择环境( 适应度 样本集) 来计算个体的适应度。然后，个体按照其适应度被选中，进行有修饰的复制，在 下一代中产生新的成员。这个种群经历同样的发展过程，产生另一代新的群体。该过程重 复若干代，直到发现一个优良解。 1 0 浙江工业大学硕十学位论文 2 3 1 基因的结构和功能组织 g e p 的基因由一头( h e a d ) 一尾( 阿1 ) 两部分构成。头部由包含既代表函数又代表 终点的符号构成，而尾部仅仅含有终点。对每个问题而言，头部长度h 是选定的，而尾部 长度，是厅和刀的函数，其中，z 是所需变量数最多的函数的参数个数( 也称为最大操作数) ， f 的大小由下面的方程得到： f = 办( 刀一1 ) + 1 ( 2 1 ) 采用这种头尾划分的好处在于，一方面整个基因的结构在设定字符集和头部长度之后 就能够确定，另一方面，整个基因在上面这个公式的前提下一定能够保证结构上的正确性， 而不用担心会产生任何非法的个体。 考虑如下这个由函数集为f = 妇，宰，一，+ 和终点集为r = 口，6 构成的基因。在这里，厅= 2 ； 如果我们选择j i l = 1 5 ，那么f = 1 5 ( 2 1 ) + l _ 1 6 ；所以基因g 的长度为1 5 + 1 6 = 3 1 。下面给出一 个这样的基因( 尾部用粗体标识) ： 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 b + a a q a b + + b + b a b b a b b b a b a b b a a a 它编码成如下表达式树： 图2 - 4g e p 的表达式村结构 虽然基因的长度已定，但是它们还是具有转换成不同大小和形状的表达式树的潜力 ( 后面我们将通过遗传操作来作为演示) ，最简单的情况是整个表达式树仅仅由一个节点 构成( 当基因的第一个元素是终点时) ，最复杂的情况是表达式树由基因中的所有节点构成 ( 当头中所有的元素都是函数，而且函数都具有最大参数个数力) 。 从以上的例子很容易看出，不论对基因组进行多么深刻的修饰，产生的表达式树始终 浙江丁业人学硕士学位论文 是正确的。显然，基因的组织结构必须保留，即始终保持头部和尾部的边界而且禁止表示 函数的符号出现在尾部里面。 2 3 2k 表达式 在g e p 中，遗传编码染色体是固定长度的线性字符串。一个染色体可能包含一个或 多个基因。g e p 染色体在编码成表达式树时，虽然起始点通常都是某个基因的第一个基 因位，然而终点并不一定是该基因的最后一个基因位。也就是说，整个基因中有一部分被 编码到了树结构中，而另一部分则没有在这种树结构中出现。这里出现的部分叫做公开阅 读框( o p e nr e a d i n gf r 锄e ，o r f ) ，这些o r f 称为k - 表达式( k - e x p r e s s i o n ) ，它是g e p 的表现型。而基因中没有出现的部分被称为非编码区域，它对g e p 的进化起着重要的作 用。 k 表达式是一种很简单直观的遍历表达式树的方法，对于一棵表达式树，按照从上 到下，从左到右的顺序遍历，就得到该表达式树的k 一表达式。值得注意的是，表达式树 的k 表达式和先序、中序和后序遍历都存在很大的差异。例如，对于如下算术表达式： ( 口+ 6 ) “c d )( 2 2 ) 它所对应的表达式树结构如图2 5 ( a ) 所示。该表达式树对应的先序、中序、后序遍历序列 和k - 表达式分别如图2 - 5 ( b ) ，( c ) ，( d ) ，( e ) 所示。 q + a b 一c d ( b ) a + b c 一d q ( c ) a b + c d 一q ( d ) q + 一a b c d ( e ) ( a ) 图2 5 式( 2 2 ) 对应的表达式结构及其先序、中序、后序和k 一表达式序列 如果k 表达式仅仅作为一种表达式的表述方式，并没有什么优点，它不像前缀，后 1 2 浙江t 业大学硕士学位论文 缀序列有很好的结构性，也不像中缀序列具有很好的可理解性。但是，当k 表达式作为 遗传编码的时候却具有其他线性表示方法所不具有的很多优点。从k 表达式的解码过程 看，无论k 表达式是如何编码的，都一定能按照步骤一步一步进行解码，同时，只要k 表达式的长度足够，不一定能解码完成，表示出一棵完整的表达式树。这些特点使得k 表达式作为遗传编码具有极大的灵活性，进化过程中的各种算子不必采用特别复杂的设 计，就能保证产生的新的染色体仍然能合法地解码为完整的表达式树】。 将一棵表达式树编码为k 表达式算法和将一个k 表达式树解码为一棵表达式树算法 分别如图2 6 和图2 7 所示。 算法2 1 ：k 一表达式编码算法 输入：表达式树t 输出：k 表达式符号串k 步骤： 1 设置队列q 为空； 2 k 初始化为空串； 3 将表达式树t 的根节点添加到队列q 尾部； 4 、砌l eq 不空d o 5 从q 头部取出一个元素n ； 6 k 卜k + 刀； 将n 添加到k 尾部 7 i f n 是终结符t h e n 8 c o n t i n u e ； 9 e n di f 1 0 f o rn 的每一个子节点md o 1 1 将m 添加到q 尾部； 1 2 e n df o r 1 3 e n d w l l i l e 1 4 r e t u mk ： 图2 石k 表达式编码算法 算法2 2 ：k 表达式解码算法 浙江工业入学硕士学位论文 输入：k 表达式符号串k 输出：表达式树t 步骤： 1 设置队列q 为空； 2 p 卜o ； 定义k 的下标指针) 3 r 卜刀洲n o d e ( 局) ； 4 p 卜p + l ； 5 将t 添加到队列q 尾部； 6 、m l eq 不空d o 7 从q 头部取出一个元素n ； 8 i f n 是终结符t h e n 9 c o n t i l l u e ： 10 e n di f 1 1 口卜五( 疗) ； 取得函数n 的参数个数) 1 2 f o rf = lt o 口d o 1 3 构造节点掰卜，z 伽n o d e ( 局) ； 1 4 将节点m 作为节点n 的第f 个子节点； 1 5 p 卜p + 1 ； 1 6 将m 添加到q 尾部； 1 7 e n df o r 1 8 e n dw 1 1 i l e 1 9 r e t u mt 图2 7k 表达式解码算法 算法2 1 的每一步都是确定的，而表达式的规模是有限的，很显然，算法2 1 一定能 够正常结束。但是，算法2 2 的第1 3 步访问岛的时候，如果k 表达式长度不够，就有可 能出现数组访问越界的情况，但是g e p 算法中基因采取了由满足式( 2 1 ) 所示的头尾结构 组成，保证了所有k 表达式都能够顺利解码成表达式树结构。 1 4 浙江工业大学硕十学位论文 2 3 3 多基因染色体及连接函数 实践证明，如果选择一个过分长的基因编码长度，g e p 的搜索效率将大大降低。但 是，如果基因太短，可以表示的表达式的复杂程序就非常有限。为了解决这个矛盾，c a n d i d a 模拟大自然的解决方案，引入了多基因。对于每个问题，基因的数目以及头的长度都根据 情况来选定。每一个基因可以对一个子表达式树进行编码而且子表达式树相互作用构成一 个更复杂的实体。 例如，考虑如下长度为4 ，由2 个基因长度均为g = 9 的基因构成的染色体( 尾部由 黑体标识) ： 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 + 一a a d b d