（控制理论与控制工程专业论文）改进的基因表达式编程算法的研究及其应用.pdf

武汉科技大学硕士学位论文第1 页 摘要 进化计算是当前人工智能、知识工程、数据挖掘中的研究热点。遗传算法和遗传编程 是众多进化计算模型中的两个最典型的模型。f c a n d i d a 于2 0 0 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 p 是一种新型的遗传算 法，它继承了遗传算法( g e n e t i ca l g o r i t h m ，g a ) 和遗传程序设计( g e n e t i cp r o g r a m m i n g , g p ) 的优点，并且具有更高的效率和更强的搜索能力，既具有遗传算法的简单性，又具有遗传 编程的功能。在对很多问题的求解效率上，比普通的遗传编程高2 4 个数量级。它是借鉴 生物选择和进化机制发展起来的一种高度并行、随机、自适应搜索算法。 本文首先介绍了基因表达式编程算法，然后将其改进后应用于求解作业车间调度问题 和自动聚类问题。 作业车间调度问题是许多实际生产调度问题的简化模型，其研究具有重要的理论意义 和工程价值。基因表达式编程算法结合了遗传算法和遗传编程的优点，具有更强的解决问 题的能力，对基因表达式编程算法进行改进使其在作业车间调度问题的应用上更加有效。 最后应用一个实例来验证提出的方法的有效性，获得的调度方案的时间非常短，这个实验 结果表明了提出的算法是有效的。数据挖掘的目的是从海量的数据中提取人们感兴趣的， 有价值的知识和重要的信息。聚类分析是数据挖掘的一个重要研究领域，它在商业、生物、 医学、地质、w e b 文档等方面都有重要的应用，是当前的研究热点之一。应用改进的g e p 算法在不需要先验知识的条件下对数据样本进行自动聚类，最后通过两组实验来验证此方 法在自动聚类中的应用是非常有效的。 关键词：基因表达式编程；遗传算法；作业车间调度；调度方案；自动聚类 第1 i 页 武汉科技大学硕士学位论文 a b s t r a c t e v o l u t i o n a r yc o m p u t a t i o ni s ah o tp o i n ti nt h er e s e a r c ha r e ao fa r t i f i c i a li n t e l l i g e n c e ， k n o w l e d g ee n g i n e e r i n ga n dd a t am i n i n g g e n e t i ca l g o r i t h ma n dg e n e t i cp r o g r a m m i n ga r et h e m o s ti m p o r t a n tc o m p u t a t i o nm o d e l si ne v o l u t i o n a r yc o m p u t a t i o n i n2 0 01 ，f c a n d i d ap r o p o s e d an e we v o l u t i o n a r yc o m p u t a t i o nm e t h o dn a m e dg 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 pi s al a t e l yg e n e t i ca l g o r i t h mp r o g r a m m i n g , s i m p l e rr e p r e s e n t a t i o na n dt h ec r e a t i o no fh i g h e rl e v e l s o fc o m p l e x i t yt h a ng pa n dg a g e pi s 弱s i m p l e 嬲g e n e t i ca l g o r i t h m ，a n d 勰f u n c t i o n a la s g e n e t i cp r o g r a m m i n g b u tf o r t h em o s tp r o b l e m s ，g e pi sm u c hf a s t e r t h a ng e n e t i c p r o g r a m m i n gi n2t o4m a g n i t u d e s i ti sh i g h l yp a r a l l e l ，r a n d o m ，a u t o a d a p t e ds e a r c ha l g o r i t h m d e p e n do n a k i n do fw h i e ht h eb i o l o g i c a lc h o i c ea n dt h ee v o l u t i o nm e c h a n i s m 砸sp a p e l i n t r o d u c e st h em e a n so ft h eg e pf i r s t l y t h e n ，g e n ee x p r e s s i o np r o g r a m m i n gi s i m p r o v e da n dp r o p o s e dt os o l v ej o bs h o ps c h e d u l i n gp r o b l e ma n da u t o m a t i cc l u s t e r i n gp r o b l e m j o bs h o ps c h e d u l i n gp r o b l e mi st h er e d u c e dm o d e lo fm a n ya c t u a ls c h e d u l i n gp r o b l e m ，i t s r e s e a r c hh a si m p o r t a n tt h e o r ys i g n i f i c a n c ea n de n g i n e e r i n gw o r t h g e pc o m b i n e st h ea d v a n t a g e s o fg e n e t i ca l g o r i t h ma n dg e n e t i cp r o g r a m m i n g ，i th a sm o r ep o w e r f u la b i l i t yw h i c hs o l v e s p r o b l e m g e n ee x p r e s s i o np r o g r a m m i n ga l g o r i t h mi sp r o p o s e df o ra p p l y i n gi n t oj o bs h o p s c h e d u l i n gp r o b l e me f f i c i e n t l y i no r d e rt ov e r i f yt h ee f f e c t i v e n e s so ft h ep r o p o s e dm e t h o d ，a n e x a m p l ew a su s e df o re x p e r i m e n t t h eo b t a i n e ds c h e d u l i n gs o l u t i o nt i m ei sq u i t es h o r t t h e e x p e r i m e n tr e s u l ts h o w st h a tt h ep r o p o s e da l g o r i t h mi se f f i c i e n t t h ep u r p o s eo f d a t am i n i n gi s t oa b s t r a c tp o t e n t i a l v a l u a b l ek n o w l e d g ea n du s e f u li n f o l t n a t i o nf r o mp l e n t i f u ld a t a c l u s t e r a n a l y s i si so n eo ft h er e s e a r c hd o m a i n so fd a t am i n i n g ，w h i c hh a si m p o r t a n ta p p l i a n c e si nm a n y d o m a i n ss u c ha si nb u s i n e s s ，b i o l o g y ，m e d i c i n e ，g e o g r a p h y , w e ba r c h i v e ，a n di tb e c o m e so n eo f t h eh o tr e s e a r c hp r o b l e m s w i t h o u ta n y p r i o rk n o w l e d g e ，i m p r o v e d g e n ee x p r e s s i o n p r o g r a m m i n gi su s e dt os o l v ec l u s t e r i n ga u t o m a t i c a l l yo nv a r i o u sd a t as e t s f i n a l l y , t w o k i n d so f c l u s t e r i n gd a t aa r ee x p e r i m e n t e dt ov e r i f yt h ee f f e c t i v e n e s so f t h ep r o p o s e da p p r o a c h k e yw o r d s ：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 n e t i ca l g o r i t h m s ；j o bs h o ps c h e d u l i n g ；s c h e d u l i n g s o l u t i o n ；a u t o m a t i cc l u s t e r 武汉科技大学 研究生学位论文创新性声明 本人郑重声明：所呈交的学位论文是本人在导师指导下，独立进行研 究所取得的成果。除了文中已经注明引用的内容或属合作研究共同完成的 工作外，本论文不包含任何其他个人或集体已经发表或撰写过的作品成果。 对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 论文作者签名： 研究生学位论文版权使用授权声明 本论文的研究成果归武汉科技大学所有，其研究内容不得以其它单位 的名义发表。本人完全了解武汉科技大学有关保留、使用学位论文的规定， 同意学校保留并向有关部门( 按照武汉科技大学关于研究生学位论文收录 工作的规定执行) 送交论文的复印件和电子版本，允许论文被查阅和借阅， 同意学校将本论文的全部或部分内容编入学校认可的国家相关数据库进行 检索和对外服务。 论文作者签名：塑三堡 指导教师签名： 殛垒鱼 日期：塑壁塑空皇 武汉科技大学硕士学位论文第1 页 第一章绪论 1 1 引言 生物的进化是一个奇妙的优化过程，它通过选择淘汰、突然变异、基因遗传等规律产 生适应环境变化的优良物种。遗传算法( g e n e t i ca l g o r i t h m ) 是根据生物进化思想而启发 得出的，是近3 0 年来发展起来的一种崭新的全局优化算法【i - 4 。1 9 7 5 年，霍兰德( h o l l a n d ) 教授首次提出了g a 算法的基本思想，它借用了生物遗传学和自然选择机理，通过自然选择、 遗传、变异等作用机制，实现个体的适应性的提高。从某种程度上说遗传算法是对生物进 化过程进行的数学方式仿真。它体现了自然界中“物竞天择、适者生存”进化过程【5 卅。 与自然界相似，遗传算法对求解问题的本身一无所知，它所需要的仅是对算法所产生 的每个染色体进行评价，把问题的解表示成染色体，并基于适应值来选择染色体，使适应 性好的染色体有更多的繁殖机会，在算法中也即是编码的串。并且，在执行遗传算法之前， 给出一群染色体，称为初始种群也即是假设解。然后，把这些假设解置于问题的“环境 中，也即一个适应度函数中来评价。并按适者生存的原则，从中选择出较适应环境的染色 体进行复制，淘汰低适应度的个体，再通过交叉，变异过程产生更适应环境的新一代染色 体群。对这个新种群进行下一轮进化，直到产生最适合环境的值。它适合于复杂系统计算 优化的自适应概率优化技术。 与其他一些优化算法相比，遗传算法主要有下述几个特点： 1 ) 变量的编码作为运算对象。传统的优化算法往往直接利用决策变量的实际值进行优化 计算，但遗传算法是以决策变量的某种形式编码，而引入和应用遗传操作算予。 2 ) 遗传算法直接以目标函数值作为搜索信息。传统的优化算法往往不只需要目标函数值， 还需要目标函数的导数等其它信息。这样对许多目标函数无法求导或很难求导的函数， 遗传算法就比较方便。 3 ) 遗传算法使用概率搜索技术。通过自适应概率搜索技术，用选择、交叉、变异等运算， 以一种概率的方式来进行，从而增加了其搜索过程的灵活性。实践和理论都已证明了 在一定条件下遗传算法总是以概率1 收敛于问题的最优解。 4 ) 不必非常明确描述问题的全部特征，通用性和鲁棒性强，能很快适应问题和环境的变 化；对领域知识依赖程度低，不受搜索空间限制性假设的约束，不必要求连续性、可 导或单峰等。 5 ) 多点进行搜索，如同在搜索空间上覆盖的一张网，搜索的全局性强，不易陷入局部最 优，具有隐并行性，非常适合于并行计算。 由于以上特点遗传算法已用于求解一些带有应用前景的问题，例如遗传程序设计、函 数优化、排序问题、人工神经网络、分类系统、计算机图像处理和机器人运动规划等。在 研究过程中，人们对g a 进行了各种改进方法，使得它的应用领域不断扩大，优化和机器学 习的能力也显著提高。 第2 页武汉科技大学硕士学位论文 遗传编程( g e n e t i cp r o g r a m m i n g ) 在遗传算法的基础上i 主1 k o z a 教授发展起来，是进化 计算方法的一个新分支。短短数年，g p 已经取得了巨大成果并仍在迅猛发展，虽然其理论 比起传统的遗传算法( g a ) 仍然不够完善，但已经在众多科技领域取得成功应用【7 】。它使 用了一种非线性的、可用不同大小和形状的树型结构来解决更复杂的问题，这在g a 的能力 之外。但由于它的这种实体非常的庞大以及占用大量的空间导致了复制操作很困难；更重 要的一点是遗传操作直接在解析树上进行，因此操作的有效性检查需要耗费可观的计算资 源。 基因表达式编程( 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 ) 是葡萄牙科学家c a n d i d a f e r r e i r a 在2 0 0 1 年提出的一种基于基因型( g e n o m e ) 和表现型( p h e n o m e ) 的基因算法。它 是遗传计算家族革命性的新成员，是借鉴生物遗传的基因表达规律提出的知识发现新技 术。g e p 模拟生物进化过程对问题进行优化求解，以适者生存原理消解不良结构，以遗传 实现继承，以变异求得发展。 g e p 融合了g a 和g p 的优点【8 1 。它与遗传算法和遗传程序设计的根本区别在于它们所采 用的个体的本性不同：在g a 中个体是固定长度的线性串( 染色体) ；在g p 中个体是长度 和形状不同的非线性实体( 树结构) ；而在基因表达式编程中个体被编码成固定长度的线 性串( 基因组或者染色体) ，然后被表示成不同长度和形状的非线性实体( 简单图或者表 达树) 。这样，g e p 就克服了g a 损失功能复杂性的可能性和g p 难以再产生新的变化的可 能性。所以说，g e p 是g a 和g p 的继承和发展，它综合了g a 和g p 的优点，具有更强的解决 问题的能力。 g e p 同传统的g a 和g p 在一些步骤框架上相似，但在个体的编码方法及结果的表现上 有明显的区别。图1 1 是g a ，g p 和g e p 的关系，表述了这一发展过程【2 4 j 。 ! 兰竺：兰三竺竺竺 一 图1 1g a 、g p f ? i i g e p i 默系 我们不妨将g a l l 喻为父本，它刚性地使用定长的线性b i t 串( 染色体) 为遗传物质， 采用简单编码解决简单问题；遗传编程g p l l 喻为母本，它柔性地使用非线性的、不定长的 树结构，采用复杂编码解决复杂问题；而g e p 继承了父母的优点，它刚柔相济，表现为定 武汉科技大学硕士学位论文第3 页 长线性串，易于遗传操作，又间接地对应于柔性的具有非线性的树结构，从而达到了简单 编码解决复杂问题的目的。 1 2 基因表达式编程技术的研究意义及研究现状 基因表达式编程( 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 ) 是c a n d i d af e r r e i r a 于2 0 0 1 年 提出的【9 】，是遗传算法家族的新成员，借鉴生物遗传的基因表达规律提出的知识发现新技 术。具有极强的函数发现能力和很高的效率，并且在函数发现时不需要任何先验知识，无 需预存函数模的类型，避免了传统算法建模时事先选定函数类型的盲目性。c a n d i d af e r r e i r a 提出g e p 算法后，引起了国内外很多学者的研究兴趣。 近几年g e p 的原创者c a n d i d af e r r e i r a 对g e p 又进行了深入细致的研究，使用了大量的 实验从不同的角度探讨了g e p 各个遗传操作的效率，同时也研究了g e p 在有关领域的应用， 包括分类、神经网络等方面【n 1 3 】。 z h o uc h i 等利用g e p 算法对分类规则进行了研究，于2 0 0 3 年在i e e et r a n s a c t i o n so n e v o l u t i o n a r yc o m p u t a t i o n ，v 7 n 6 发表了论文“e v o l v i n ga c c u r a t ea n dc o m p a c tc l a s s i f i c a t i o n r u l e sw i t hg e n ee x p r e s s i o np r o g r a m m i n g 【1 4 】。其研究结果表明g e p 算法应用于分类的有效性。 y o r i c kh a r d y 等在国际杂志现代物理学上发表论文“g e n ee x p r e s s i o np r o g r a m m i n g a n do n e d i m e n s i o n a lc h a o t i cm a p s ，将g e p 应用于一维混沌映射【l 5 1 。 国内的许多学者在g e p 算法的基础上，针对不同应用提出了效率更高和适应性更强的 算法。 z u oj i e 等利用g e p 技术对关联规则进行了研究，于2 0 0 2 年在国际会议w a i m 0 2 上发表 了论文m i n i n gp r e d i c a t ea s s o c i a t i o nr u l eb yg e n ee x p r e s s i o np r o g r a m m i n g ) ) l 1 6 j 。 文献【1 7 】讨论了两种新的基于g e p 的时间序列模型构造方法。一种是传统的滑动窗口 预测法( g e p s w p m ) ，即找到在一个窗口大小内的前后数据之间的函数关系，然后使用 该关系来进行预测。另外一种则是通过分析整个测试数据，建立关于时间序列的微分方程， 然后通过该微分方程进行预测( g e p d e p m ) 。 文献i 18 】提出了残差制导进化算法( r g e a ) ，算法的主要思想是对g e p 的遗传操作进 行改进，以使下一代群体中残差平方和小于上一代最小残差平方的染色体个数尽可能多。 算法对几种有可能产生比当前最佳染色体更好的个体的遗传操作，分配指标任务，即要求 该遗传操作在每一代操作中生成的残差平方和小于上一代最小残差平方的染色体个数至 少要达到规定的阈值，若没有完成，则在本代遗传操作中调整其遗传率，重新进行遗传操 作。 文献【1 9 】借鉴生物具有的趋利避害( s e e ka d v a n t a g e ，a v o i dd i s a d v a n t a g e ) 天性，提出了 “弱适应模型”( w e a k a d a p t i v em o d e l ) ，设计了在弱适应模型下基于相对误差计算适应 度的算法( r e f a ) 。 文献 2 0 】提出并实现了任意维定义域上的一致表达式和分域表达式的挖掘方法，提出 了g e p u e m ( 一致函数表达式的挖掘) 算法和g e p m e m ( 分域函数表达式挖掘) 算法以 第4 页武汉科技大学硕士学位论文 及g e p b d m ( 二域式挖掘) 算法。从而实现了分段函数的挖掘。 文献【2 1 1 提出了基于转基因技术的基因表达式编程方法，通过注入转基因，引导进化 方向，控制知识发现过程。 文献 2 2 】对基于重叠表达的多基因进化算法进行了研究，借鉴生物基因片段重叠表达， 引入重叠基因概念，节约了表达空间。 文献 2 3 1 通过回溯策略，对提高基因表达式编程发现知识效率进行了研究，借鉴生物 “返祖现象 ，引入回溯检查点概念和可回溯g e p 算法、设计了等比递增检查点序列和加 速递增检查点序列，约束回溯过程。 目前，国内有四川大学、武汉大学、中国地质和中国科学技术大学等少数的高校对g e p 算法也进行了研究。通过注入转基因，引导进化方向，控制知识发现过程；重叠基因表达， 借鉴生物基因片段重叠表达，引入重叠基因概念，节约了表达空间。回溯进化借鉴生物“返 祖现象，引入g e p 回溯算法、回溯检查点，设计等比递增检查点序列和加速递增检查点 序列，约束回溯过程。实验表明，这些技术在一定的场合下分别提高了知识发现的性能1 至2 个数量级。 西安交通大学以演化计算为主题的研究工作也逐渐活跃起来，几乎在每个一级学科中 都有演化计算的研究者，主要集中在演化计算在各学科的工程应用，在b b s 上的人工智能 版经常可以见到一些有关演化计算的讨论与交流。西安交通大学的诊断与控制学研究所在 1 9 9 4 年就开始了对演化计算在故障监测与诊断中的应用研究，目前，主要集中在诊断信息 的智能处理和诊断知识的自动获取两个方向。随着国内对演化计算认识的逐渐深入，演化 计算的研究与应用必将取得更多的成果。 四川大学唐常杰教授在2 0 0 0 年底开始了对g e p 的跟踪性研究，在公式发现、函数挖掘、 关联规则发现、因子分解、太阳黑子预测中获得好的进展。 g e p 是一种知识发现的仿生计算新技术。g e p 模拟生物进化过程对问题进行优化求解。 g e p 融合了g a 和g p 的优点，通过简单紧凑的编码解决复杂应用问题。定长线性编码使进 化过程简单有效，解码为表达式树，使进化结果清晰明了，有很强的解决实际问题的能力。 从2 0 0 1 年以来g e p 的首批研究成果出现，受到学术界的高度关注，一批研究成果和软件相 继问世。 1 3 本文的主要研究内容及组织结构 基因表达式编程( 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 p 的搜索空间。 下面是文章主要研究内容和结构安排的简要介绍： 第一章为绪论部分，阐述了课题研究的背景，介绍了国内外研究概况。 第二章介绍了基因表达式的基本概念，给出了基因表达式编程的基本方法，详细描述 了基因表达式编程算法从编码结构、遗传操作以及适应度函数等各个方面。并对基因表达 武汉科技大学硕士学位论文第5 页 式和其他遗传算法进行比较，概括了g e p 的优越性。 第三章首先介绍了车间调度问题，重点研究了了采用一种新颖的方法一改进的基因 表达式编程算法来求解作业车间调度问题。 第四章首先介绍了自动聚类问题，详细描述了改进的基因表达式编程算法在自动聚类 问题的应用。 第五章对是全文的总结，主要对全文内容进行简要回顾，并指出本设计的主要创新点 所在。 第6 页武汉科技大学硕士学位论文 第二章基因表达式编程 2 1 进化计算简介 进化计算( e v o l u t i o n a r yc o m p u t a t i o n ) ，或称演化计算，其特点是群体搜索策略和群 体中个体之间的信息交换。进化计算以达尔文进化论为依据来设计、控制和优化人工系统， 它包括遗传算法( g e n e t i ca l g o r i t h m ) 、进化策略( e v o l u t i o n a r ys t r a t e g i e s ) 和进化规划 ( e v o l u t i o n a r yp r o g r a m m i n g ) 。尽管它们之间很相似，但历史上这三种算法是彼此独立发 展起来的【2 5 1 。 遗传算法是由美国j h o l l a n d 创建，后由k d e j o n g ，j g r e f e n s t e t t e ，d g o l d b e r g 和l d a 访s 等人进行了改进；进化规划最早由美国的l j g f o g e l ，a j o w e n s 和m j w a l s h 提出； 进化策略是由德国的i r e c h e n b e r g 幂 f l h p s c h w e f e l 建立的。三种算法既有许多相似之处， 同时也有很大的不同。进化规划和进化策略都把变异作为主要的搜索算子，而在标准遗传 算法中，变异只处于次要地位；交叉在标准遗传算法中起着重要作用，而在进化规划中被 完全省去，在进化策略中与自适应结合在一起使用非常重要；标准遗传算法和进化规划都 强调随机选择机制的重要性，而从进化策略的角度看，选择是完全确定的，没有合理的根 据表明随机选择原则的重要性；进化规划和进化策略确定地把某些个体排除在被选择复制 之外，而标准遗传算法一般对每个个体都指定一个非零选择概率。 进化计算能够解决采用传统的方法不能解决的问题，通过输入问题及问题应满足的条 件、结果评价标准，就可以自动得到问题的解，不需要用户的干预。因此遗传算法、进化 策略和进化规划三种算法在工程的应用中各有各的无可比拟的优势。 2 1 1 遗传算法 将生物现象应用到人工领域的仿生学己经越来越被人们看好。将生物进化过程应用到 人工智能领域，也是一个越来越被看好的方向。这方面的研究形成了进化计算这一广阔的 分支。在数量众多的进化计算算法中，各种算法都以生物进化作为算法的背景，但是，每 一种算法都具有自己的特点，有的侧重于生物个体的变异，有的侧重于个体之间的杂交， 有的主要利用每一个个体自身进行搜索，具有较强的局部搜索能力，而有的主要利用群体 间个体之间的相互影响，具有较强的全局搜索能力。 遗传算法是仿真生物遗传学和自然选择机理，通过人工方式所构造的一类搜索算法， 从某种程度上说遗传算法是对生物进化过程进行的数学方式仿真。美国密执安大学的 h o l l a n d 教授于6 0 年代在他的著作( ( 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 ) ) 中首次提出 遗传算法的思想。到了8 0 年代，在一系列研究工作基础上，由g 0 1 d b e r g 进行归纳总结，形 成了遗传算法的基本框架【2 6 】。 遗传算法自从1 9 5 6 年提出以来，在国际上已经形成了一个比较活跃的研究领域，已召 开了多次比较重要的国际会议和创办了很多相关的国际刊物。遗传算法已用于求解带有应 武汉科技大学硕士学位论文第7 页 用前景的一些问题，例如遗传程序设计、函数优化、排序问题、人工神经网络、分类系统、 计算机图像处理和机器人运动规划等。 遗传算法类似于自然进化，通过作用于基因寻找好的个体来求解问题。在遗传算法中， 通过随机方式产生若干个所求解问题的数字编码，形成初始群体；通过适应度函数给每个 个体一个数值评价，淘汰低适应度的个体，选择高适应度的个体参加遗传操作，经过遗传 操作后的个体集合形成下一代新的种群。对这个新种群进行下一轮进化。 基因遗传原理认为遗传以密码方式存在细胞中，并以基因形式包含在染色体内。每个 基因有特殊的位置并控制某种特殊性质。所以，每个基因产生的个体对环境具有某种适应 性，基因突变和基因杂交可产生更适应于环境的后代。经过存优去劣的自然淘汰，适应性 高的基因结构得以保存下来。遗传算法是从代表问题的可能潜在解集的一个种群 ( p o p u l a t i o n ) 开始的，而一个种群则由经过基因( g e n e ) 编码( c o d i n g ) 的一定数目的个 体( i n d i v i d u a l ) 组成。每个个体实际是带有特征的实体的染色体( c h r o m o s o m e ) 。染色体 作为遗传物质的主要载体，由多个基因组成，其内部表现是基因组合，它决定了个体的外 部表现。要实现个体的进化，首先需要实现从表现型到基因型的映射，即编码工作，以便 产生初始种群。初始种群产生后，按照适者生存和优胜劣汰的原理，逐代( g e n e r a t i o n ) 演 化产生越来越好的近似解。在每一代，根据问题域中个体的适应度( f i t n e s s ) 大小挑选 ( s e l e c t i o n ) 个体，并借助遗传算子( g e n e t i co p e r a t o r s ) 进行组合交叉( c r o s s o v e r ) 和变异 ( m u t a t i o n ) ，产生出代表新的解集的种群。这个过程将导致种群像自然进化一样的后生 代种群比前代更加适应于环境，末代种群中的最优个体经过解码( d e c o d i n g ) ，可以作为 问题近似最优解。 传统遗传算法的基本步骤如下： 1 ) 初始化群体； 2 ) 计算群体上每个个体的适应度值； 3 ) 按由个体适应度值所决定的某个规则选择将进入下一代的个体； 4 ) 按概率p 。进行交叉操作； 5 ) 按概率p m 进行突变操作； 6 ) 没有满足某种停止条件，则转第( 2 ) 步，否则进入( 7 ) 。 7 ) 输出种群中适应度值最优的个体作为问题的满意解或最优解。 程序的停止条件最简单的有如下二种：完成了预先给定的进化代数则停止；种群中的 最优个体在连续若干代没有改进或平均适应度在连续若干代基本没有改进时停止。 2 1 2 遗传编程 遗传编程( g e n e t i cp r o g r a m m i n g ，g p ) ，也称为遗传程序设计，或遗传规划，是在遗 传算法的基础上发展起来的，它采用了一种全新的个体描述方法，其实质是采用层次结构 来描述解决问题的计算机程序。因此，遗传编程是程序自动生成技术的利器。 遗传编程是对遗传算法的一次突破性发展，它对群体中表示独立的计算机程序的个体 第8 页武汉科技大学硕士学位论文 ( 而不是g a 中的固定长度的二进制字符串) 进行操作，克服了传统遗传算法在表示方法上 的局限，采用了更为灵活的可变分层结构。根据对问题的求解要求，遗传编程采用了上层 描述方法，自动生成解决问题的程序。因此，它是一种不局限于某一领域的“遗传或进化 搜索技术。从达尔文“适者生存”理论中得到启示，遗传编程以适应度为标准，运用交 叉、突变、复制和删除等手段使一代代的计算机程序不断进化，正如大自然选择进化着数 量众多，形态各异的物种一样。g p 强大的问题解决能力，使其应用也很广泛。 在遗传编程中，构成染色体结构的主要元素是函数集合和变常量集合。染色体结构在 初始化以及进化的过程中，根据问题的具体要求，在指定的函数集合和变常量集合中选定 符号构成树形结构的程序。树形结构的遗传编码是遗传编程的重要特征。 作为进化计算的成员，遗传编程中也有系列的遗传算子，例如，重组算子、变异算子 等等。这些遗传算子直接作用在树形结构，例如：常用的重组算子随机选定两棵父代个体 的程序树中的节点，然后交换以选定节点为根节点的子树。由于遗传编程能处理树形的程 序结构，所以遗传编程已经被广泛应用于优化控制、符号回归、公式发现等领域。虽然遗 传编程有很广阔的前景，但它也存在很多不足，例如，它直接处理树形结构效率低下，代 码膨胀影响搜索效率等等。 2 1 3 其他进化算法 除了应用最广的遗传算法和遗传编程，进化规划和进化策略也各有特色。他们各自强 调的侧重点不同，应用起来都有自己的适合领域。 进化规划算法直接用问题空间的变量作为遗传编码，它的遗传编码的表示方式根据问 题的解的形式来确定，因此进化规划就不需要编码和译码过程。进化规划不使用重组等遗 传算子，仅采用变异算予，标准的进化规划采用高斯变异算子。进化规划算法现在被广泛 应用在组合优化、函数优化、自动控制、游戏理论、路径规划等问题上。 进化策略最初用来解决工程上的一些无法用传统的数学线性方法求解的非线性模型 的数值问题。进化策略着重研究子代与父代行为特征之间的联系，并且，进化策略不像遗 传算法那样对变量的编码串进行操作，而是对变量本身的操作。进化策略己经在非线性优 化、系统识别等方面显示出比传统经典方法更加强大的能力。 2 1 4 进化计算的本质 探究其本质，进化计算是一种随机搜索的优化算法，具有非确定性，并且拥有强大的 解决问题的能力。在很多复杂的非线性问题的求解上，进化算法都是非常有效的分析工具。 由数值分析的角度来看，进化计算可视为随机搜索的优化算法。因为其本质是非确定 性的，所以能搜寻问题空间罩所有的可能解答。而在进化计算的群体中，大量个体随着环 境的变化，进行变化、选择，进而形成各种各样的个体。不同个体也就代表了用以解决问 题的不同途径与其信息，进化计算含有多样性以解决问题的能力。在很多复杂的非线性的 问题上，没有现成的可利用解析方法，进化计算便成为最有效的分析手段。 武汉科技大学硕士学位论文第9 页 由自然进化的角度来看，进化是在动态变化的环境下的一种适应过程，而并非在静态 环境下的最优化过程。在进化过程中的系统有趋向复杂的倾向。因此进化可理解为适应性 复杂系统的变化过程，同时也是在生命与智慧本质中的必要的基本过程。由物理的观点来 看，复杂是产生在非线性动力学里介于混沌与秩序间的现象。复杂带来信息的产生与变化。 经典物理学中描述运动的动力学是确定性的，无法描述进化过程。但热力学里，处于非平 衡状态的耗散性结构却可以描述进化过程。而动力学和热力学问的歧异，也就蕴含着关于 进化本质的最大奥秘。 在大自然里的生物并非由单一简单的机能形成，而是由大量的个体聚集的复杂系统所 构成。生物形成的复杂系统会随着环境改变，适应环境，从而“寻求 生存。所以生命现 象以及由其衍生的智慧行为，是适应性复杂系统的表现。由适应性复杂系统的观点，可以 归纳出四项生命智能的基本特质复杂、进化、交感、适应。这四项特质彼此相依相存， 只是生命本质的不同方式呈现。 进化计算是目前数据挖掘和人工智能领域的研究热点。人工智能的发展有符号主义、 连接主义和行为主义等不同的分支。近年来，在各个分支的研究和应用上都取得了巨大的 进展，也各有一些缺陷。为了克服这些缺陷，人们开始另辟蹊径，转而向大自然学习，从 而形成了模拟自然界生物进化的进化计算。 本文主要关注的基因表达式编程，是进化计算的一个分支，由遗传算法和遗传编程融 合而成。 2 2 基因表达式编程( g e p ) 从形式上，g e p 和遗传算法类似，是一种进化计算方法，采用了个体表现型和遗传编 码不同的设计思路采用等长线性符号编码唧。由于编码特别巧妙，使得遗传操作非常简单。 基于类似标准遗传操作算法的遗传操作。从工程上，g e p 和遗传编程类似，能发现解释问 题本质的规则、公式、以及描述问题解答过程的程序等等。处于g e p 综合了遗传算法和遗 传编程两者之间的优点，使得g e p 的创始人c a n d i d a 声称，g e p 在解决复杂问题的时候，比 传统的遗传编程方法效率高出了2 4 个数量级【l 引，到目前为止，g e p 已经被应用到符号回归、 分类、数据挖掘、逻辑综合等领域【2 。 基因表达式编程操纵的对象和遗传编程是一样的，更确切的讲，基于基因表达式编程 处理的对象是表达式( 数值表达式，或者布尔表达式) 同时， “e x p r e s s i o n 也有“表达 式 这个含义。所以将g e n ee x p r e s s i o np r o g r a m m i n g 译为基因表达式编程。 2 2 1 函数和终结符 基因表达式编程和遗传程序设计一样，是在遗传算法的基础上发展起来的。它和遗 传程序设计一样，采用了一种全新的不同于遗传算法的个体描述方法，其实质是用广义的 层次化计算机程序描绘问题【3 2 1 。对这种广义的层次化计算机程序作形式化描述需要两类符 号：即终结符和函数。它们是构造基因表达式编程中的一个程序的元语。 第1 0 页武汉科技大学硕士学位论文 ( 1 ) 终结符 终结符是提供给系统值的最末端结构。终结符自己提供信息，但不处理另外的信息。 通常，终结符集合包括g e p 中的输入、常量、或者没有参数的函数、树形结构中终结符表 示树的叶节点。当程序运行的时候，叶节点要么接受外部的输入，要么自己就是一个常量， 或者产生一个量。它们向系统提供信息，以供系统处理。 ( 2 ) 函数集合 g e p 中的函数概念相当广泛，它包括系统中的其他任何非终结符的中间结构。包括与 应用有关的问题领域的运算符号和程序构件，甚至是表示系统中间层次的一种符号。对于 以公式发现为目标的应用中，以下是一些常见的函数： 算术运算符，例如+ ， ，木，等； 初等数学函数，例j t l s i n ，c o s ，s q r t ，e x p ，l o g 等； 其他一些函数，例j t l m a x ，m i n 等； 布尔运算符，例如v ，八，等； 关系运算符，例如 ，= ，s ，之等； 条件运算符，i f - t h e n e l s e ； 自定义函数。 2 2 2 选择函数和终结符集合 设计一个基因表达式编程，首先就是要选择能用于构造程序的函数及终结符集合。集 合的选择应该满足几个要求： ( 1 ) 充分性 即选择的函数和终结符集合要足以能够表示问题的解。终结符的选择相对比较简单， 至少要对每一个输入定义一个终结符，如果需要，可根据问题的特点，再选择若干常数， 或者无参数的自定义函数。但是，选择哪些函数才能保证能表示问题的解，却是一个需要 经验和尝试才能解决的问题。同时，也最好不要选择过大的函数集合，过大的函数集合， 将极大地扩大基因表达式编程的搜索空间，大大降低搜索效率。 ( 2 ) 封闭性 因为寻找的公式可能以任意的方式进行组合，子节点的输出一定要能够被父节点接 受。所以，实际上要求所有的终结符和函数的值域、函数的每一个参数的定义域都是相同 的。例如，如果问题中的输入是布尔类型的数据，那么函数集合中就不能包含算术运算符。 因为，算术运算符只接受数值类型的输入，而不能接受布尔类型的输入。 ( 3 ) 作为( 2 ) 的特例，所有函数在所有输入下都应该是有定义的 例如，对于函数、厂如果不能保证其输入数据都为非负数，那么就需要对函数进行一些 调整，使得、厂都有意义。比如，修改、厂的定义为计算参数的绝对值的平方根。 对于第( 3 ) 点的要求不是绝对的，可以采用“罚函数 等方法进行克服。但是第( 1 ) 、( 2 ) 点的要求是基本的。如果函数集合和终结符和不满足上面的条件，贝j j g e p 就不能够正常运 武汉科技大学硕士学位论文第1 1 页 行。像普通的算术表达式相关的函数集合、布尔表达式相关的函数集合都满足，或稍做修 改后就满足要求。 2 2 3 基因表达式编程的编码结构 基因表达式编程遗传操作的基本单位是染色体( c h r o m o s o m e ) ，遗传信息载体的最小 单位是基因( g e n e ) 。染色体由一个或多个基因组成，基因由线性的定长字符串编码而成。 基因由头( h e a d ) 和尾( t a i l ) 组成，头部包含了变量集( v a r i a b l es e t ) 中的变量和函 数集( f u n c t i o ns e t ) 中的函数，而尾部只包含了变量。 基因表达式编程由c a n d i d af e r r e i r a 于2 0 0 1 年1 2 月首次提出。g e p 在继承g a 和g p 的思想 的基础上，创新性地提出基因型( ( 染色体) 和表现型( 表达式树) 既分离又相互转化的模 型，克服了g a 和g p 的不足，提高了解决问题的能力和效率。 在g e p 中，基因型即演化实体是染色体，染色体实际就是用连接运算符( l i n ko p e r a t o r ) 连接起来的多个基因。和g a 相同，基因是线性的定长的字符串，然而g e p g i j 新地把字符串 分为头部和尾部两部分。头尾长度( 分别记为h ，0 有如下关系： t = h ( 刀一1 ) + 1 ( 1 1 ) 其中r 是函数符集中含有最大目数的函数的目数。考虑一个函数符集f = + ，q ) ， 其中+ ，幸和都是两目函数，q 表示