（农业机械化工程专业论文）遗传规划多分类系统的实现.pdf

摘要 随着科技的不断进步，模式识别，机器人控制，神经网络的合成，符号回归等难 题急待解决。这个时候，遗传规划( g p ) 方法应运而生，它是一种关于产生问题解 的计算机程序或者其他复杂结构的自动方法。而关于如何解决多类别的分类问题，成 了近几年研究重点之一。 遗传规划是一种新型的搜索寻优方法。它仿效生物界中进化和遗传的过程，遵从 “优胜劣汰，适者生存 原则，从一组随机生成的初始可行解开始，通过复制、交叉 和变异等遗传操作，逐步迭代而逼近问题的最优解。本文阐述了遗传规划算法的原理 和进化计算的基本知识；介绍了相关分类技术；分析了遗传规划的特点；研究了运用 遗传规划解决分类问题的方法模型；设计出一个基于c + + 语言的遗传规划多分类系统 用以解决各种分类问题；并针对遗传规划在多类分类问题中的技术局限进行了改进。 为了扩大遗传规划的应用范围，提高其解决分类问题的效率。在查阅大量文献资 料和结合当前实际需要的基础上，提出了设计一个通用的以遗传规划为核心的多分类 系统。系统设计借鉴了国外己相对成熟的技术，结合了数据结构中二叉树的原理，并 利用c + + 语言强大的面向对象功能，将次系统初步建立起来。该系统可满足大多数的 分类要求。由于其良好的通用性和模块化编程，该系统可使用静态边界分类和动态边 界分类，只需要细微改动即可完成。系统运行时只需要有足够的文本文件的数据，大 大简化了使用方法。除了简易地使用性，系统的精度也有大大提高，而且训练的时间 越长，分类的精度越高。 系统设计依据低成本、易操作性、高可靠性的原则，采用标准c + + 语言来进行设 计，缩短了开发周期，提高了程序的可读性，移植性，模块化设计使得程序易于修改 和升级，便于维护。 设计利用现代计算机技术、数据结构和c + + 语言实现了基于遗传规划的多分类系 统，适应了当前国内的需要和发展。系统可以解决大多数的分类问题，经过一定改进 还可以应用到符号回归方面，有很好的应用前景。 关键词：遗传规划，多分类系统，c + + ，程序设计 t h ed e s i g no fac l a s s i f i c a t i o ns y s t e mf o rg e n e t i cp r o g r a m m i n g a u t h o r ：w a n gm e n g s u p e r v i s o r ：l iy a m i n s p e c i a l t y ：a g r i c u l t u r a lm e c h a n i z a t i o ne n g i n e e r i n g a b s t r a c t w i t ht h ed e v e l o p i n go fs c i e n c e ，m o d ei d e n t y ，t h ec o n t r o lo fr o b o t ，a n dt h ec o n p o s eo fn e r v en e t ，a l lo f t h e ma r et h ep r o b l e m sn e e dt ob ed o n e i nt h i st i m e ，t h eg e n e t i cp r o g r a m m i n gc o m e so u t ，i ti sam e t h o d w h i c hc a l ls o l v eh o wt op r o d u c et h ep r o g r a m m i n go ft h ep r o b l e ma n dt h er e s tc o m p l i c a t e ds t r u c t u r e s o h o wt os o l v et h ep r o b l e m so ft h ec l a s s i f i c a t i o nc o m e st ob et h ee m p h a s e si nr e s e n ty e a r s g e n e t i cp r o g r a m m i n g ( g p ) i san e wt e c h n o l o g yf o ro p t i m i z a t i o n ，w h i c hs i m u l a t e si n h e r i ta n d e v o l u t i o ni nt h en a t u r ea n dg e t so p t i m a ls o u t i o n st h r o u g hr e p r o d u c t i o n ，c r o s s o v e ra n dm u t a t i o n o p e r a t i o n s t h i sp a p e rd e s c r i b e st h eb a s i cp r i n c i p l eo fg e n e t i cp r o g r a m m i n ga n dt h ek n o w l e d g eo f e v o l u t i o n a r yc o m p u t a t i o n ，i n t r o d u c e st h er e l a t e dc l a s s i f i c a t i o nt e c h n o l o g y ，a n a l y s e st h ec h a r a c t e r i s t i c so f g pa n dt h ei m p l e m e n t a t i o nm e t h o d so fc l a s s i f i c a t i o np r o b l e m s i n d i c a t e st h el i m i t a t i o no fg pi n m u l t i c l a s s i f i c a t i o np r o b l e n s ，i m p r o v e sg pb a s e di t sd i s a d v a n t a g e s w en e e dt oe x t e n dt h er a n g eo ft h eg e n e t i cp r o g r a m m i n ga p p l i c a t i o n ，a n dh e i g h t e nt h ee f f i c i e n c yo f s o l v i n gt h ec l a s s i f i c a t i o np r o b l e m s a f t e rc o l l e c t i o no ft h ei n f o r m a t i o n ，ib r i n gf o r w a r da np r o j e c t i o n a b o u tt h ec l a s s i f i c a t i o ns y s t e mb a s e do ng e n e t i cp r o g r a m m i n g t h ed e s i g no fs y s t e mu s et h ea d v a n c e d f o r e i g nt e c h n i ca n dt h em e t h o do ft h ed a t as t r c t u r ea n dt h ec + + p r o g r a m a n g u a g e a n dt h e nw ec a n e s t a b l i s ht h es y s t e mi np r i m a r y t h i ss y s t e mc a ns o l v eam a j o r i t yo fc l a s s i f i c a t i o np r o b l e m s b e c a u s eo f i t se x c e l l e n tu n i v e r s a la n dm o d u l a r i z a t i o n ，t h es y s t e mc a nr u nw i t hc e n t e r e dd y n a m i cr a n g es e l e c t i o n a n ds l o t t e dd y n a m i cr a n g es e l e c t i o n f o rt h er u n n i n go ft h es y s t e m ，t h e r em u s tb ee n o u g hd a t a f i l e s ，t h a tm a k ei te a s yt or a n t h ep r e c i s i o no ft h es y s t e mh a sa l s ob e e nh e i g h t ，a n dt h em o r et i m eb e e n t a k e ni nt r a i n n i n g ，t h em o r ee x a c tt h ec l a s s i f i c a t i o n t h ed e s i g no ft h ec l a s s i f i c a t i o ns y s t e mm u s td c r e a s et h ec o s t ，p r e d i g e s tt h eo p e r a t i o n ，a n dh e i g h tt h e s e c u r i t y w i t ht h eu s i n go ft h ec + + l a n g u a g e w em a k et h ep r o g r a mb ee a s yt oa m e n da n dr e p l a n t t h ed e s i g nr e a l i z et h ec l a s s i f i c a t i o ns y s t e m ，a d a p tt h er e s e n td e m a n da n dd e v e l o p i n gi nt h e c o u n t r y 。i tc a ns o l v eal o to fp r o b l e m s ，h a sav e r yb r o a da p p l i c a t i o nf o r e g r o u n d k e yw o r d s ：g e n e t i cg r o g r a m m i n g ；c l a s s f i c i a t i o ns y s t e m ；c + + l a n g u a g e ；d e s i g no f s y s t e m ； 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得塑i 垦盔些盘堂或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者躲丑巍 签字日期k 口e 年乡月沙日 学位论文版权使用授权书 本学位论文作者完全了解塑垦盔些盘堂有关保留、使用学位论文的规定，有 权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。 本人授权塑皇垦盛些盘鲎可以将学位论文的全部或部分内容编入有关数据库进行检 索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名： 翟甄 导师签名： 旃也弧 签字日期：灵嘲年 月b e l 签字日期：物9 孑年毒月劢e l 学位论文作者毕业后去向： 工作单位： 通讯地址： 电话： 邮编： 遗传规划多分类系统的实现 1 1 研究背景 1 引言 分类问题也被称作模式识别问题，是机器学习的一个分支，它在信息领域是一个热门的研究 方向。多类分类问题是模式识别的主要分支，在实际生活中有着广泛的应用。在医学图像中找出 异常像素区域进行医疗诊断，在一系列语音流中进行单词或者短语识别，在众多信用卡的记录中 认定非法偷盗提取等仅仅是众多实例中的三个【i - j 。在许多情况下，用人工方法进行识别与分类 过于昂贵，而且耗时耗力。随着信息与网络技术的发展，需要识别与分类处理的数据量日益增大。 在这种背景下，借助计算机进行精确分类与识别不仅是必要的，而且将具有广泛的社会效益与经 济效益。 一些传统的分类方法大都是以统计学为基础，有关样本的先验知识对分类器的分类精度有很 大的影响，然而在许多实际的分类问题中无法取得准确的先验知识，不能指出或找到某一分类问 题的所有内部特征及复杂的相互关系。决策树分类方法是当今较成熟的分类技术，但是构造简单 且精确的决策树是一项艰巨的任务。另外，像神经网络这样的学习算法由于在确定网络结构时有 诸多因素需要考虑，甚至于初值选取不当都有可能导致局部收敛或发散，其特性很难把握。遗传 算法作为一种基于生物进化和遗传思想的全局随机搜索算法也应用到分类问题中，但它在规则的 表示上不是很灵活。支持向量机( s v m ) 也是一种针对分类和回归的机器学习方法，最初s v m 主要 用来解决两类分类问题，不易直接用于多类分类，如何将其有效地推广到多类分类问题还是一个 正在研究的问题p 。 作为进化计算的又一分支遗传规划( g p ：g e n e t i cp r o g r a m m i n g ) ，又叫遗传程序设计，是 在遗传算法的基础上引入自动程序设计的一种全新的方法。它能动态产生预测分析的最优非线性 结构，也能在多类模式的分类问题里，在所获得数据和数学表达式之间发现联系。它不需要数据 统计分布的预处理知识，就可自动发现某一类判别式的特征阁。显而易见，遗传规划技术在分类 问题中的成功应用，将在工农医中具有广泛的应用性，也为研究者提供一个新的解决复杂问题的 强有力的工具，具有重大的应用价值和现实意义。 1 2 国内外研究现状 遗传规划( g p ) 是一种进化符合一些客观标准程序的方法，与遗传算法有密切联系。它试图研 究计算科学中的一个中心问题：计算机怎样在没有明显编程情况下来解决问题。它把不同领域的 问题都归结为寻找满足给定约束的计算机程序发现问题，也就是在可能的程序空间中寻找最优 或满意的计算机程序【i j o1 9 8 9 年，美国斯坦佛大学的k o z a 基于自然选择原则创造性地提出了 用层次化的计算机程序来表达问题的遗传规划方法。1 9 9 2 年，他出版了专著遗传规划应 用自然选择法则的计算机程序设计，全面介绍了遗传规划的原理及应用实例l o1 9 9 4 年，他 又出版了第二部专著遗传规划仑：可再用程序的自动发现，提出了自动定义函数的概念，并 引入了子程序的概念pj 。 1 9 9 9 年他又和f o r e s t 等人写了遗传规划：达尔文创造和问题求解，提出了结构改变算 河北农业大学硕十学位( 毕业) 论文 子，它是一组控制子程序、迭代结构、递归式和内存的高级遗传算子。并着重介绍了遗传规划在 模拟电子电路自动合成中的应用 - v o 从9 0 年代至现在，遗传规划不断向广度和深度发展。 自那时起，世界各国科学家对遗传规划进行了深入研究。英国伦敦大学的w i l lj a m ( b i l l ) l a n g h o n 教授与e s s e x 大学的r i e a r d op o l l 教授对g p 教学基础与程序段( f r a g m e n t s ) 进行了研i l u j 究。美国麻省理工大学人工智能研究室的u n a m a y0 r e i1 1 y 教授对g p 的积木块( b u l l d i n g b l o c k ) 假设与理论进行了探索i l ，加拿大m e m o r i a l 大学的w o l f g a n gb a n z h a 教授进行了线形与图形表 示的研究t l z 我国云庆夏、王占权教授等对g p 的收敛性进行了研究l i 引；牛惠民教授对模糊随机网 络与复合遗传规划进行了研究【i 刿等。这些研究已将g p 从原有的单一树状结构表示法发展成为自 由树、线性、图像与语法等组成的表示法群，己从原来的以u s p 为代表的程序表达语言扩展为人 们更为熟悉、应用更为广泛的c c + + 表述语言，从原来的符号回归应用领域扩展到计划与规划最 佳控制，计算机视觉与图像处理、游戏策略，智能机器人足球，以及分类与识别问题等众多领域。 在这些众多种类的g p 中，以树形结构及其类似树形结构为基础的g p 仍占据主流地位，是目前最 为常用的表示模式。 遗传规划自动地在可能的程序空间中寻找最优化或者最满意的计算机程序，其采用灵活的计 算机程序结果表示和强大的进化学习搜索能力，引起了世界各国学者的广泛关注。遗传规划在 机器人路径规划、预测、分类、数据挖掘等方面有了一些应用。但总体来说，遗传规划是一项很 新的理论，人们对它的研究还不全面，使得它的性能没有得到充分发挥。遗传规划作为一种新的 分类方法，至少还存在着以下问题： ( 1 ) 遗传程序分类转化问题。目前，对于多类分类问题。遗传规划技术还不能准确地将输出转 化为一系列的类别标定，分类的准确率较低。 ( 2 ) 数字终端的优化问题。数字终端是终端集( t e r m i n a l s ) 的重要组成部分，是在系统生成初 始群体或者变异操作过程中随机产生的。其值直接影响着遗传规划的进化速度和学习效率，如何 对这些数字终端进行优化还需要进一步的研究。 ( 3 ) 遗传规划在解决复杂问题的时候，需要从一个相当大的状态空间搜索到好的解，往往会造 成“规模爆炸”。即作为程序个体表示的抽象语法树的深度和广度，在进化过程中不断增大。 而与此同时作为解的群体却没有任何的改进。k o z a 发现导致算法的“规模爆炸”的主要原因 是“内含子”的大量产生。如何降低进化过程中的“内含子”也是遗传规划研究的重点。 遗传规划的基本思想是：随机产生一个适用于所给问题环境的初始种群，即搜索空间，种群 中的每个个体为树状结构( 又称为s 表达式) ，计算每个个体的适应值；依据达尔文的进化原则， 选择遗传算子( 复制、交叉、变异等) 对种群不断进行迭代优化，直到在某一代上找到最优解或 近似最优解。 从9 0 年代至今，遗传规划不断向广度和深度发展。由于遗传规划用层次性的结构性语言表达 问题，因而应用领域非常广泛，如知识发现系统【2 4 1 ，非线性系统数学建模f 2 4 】人工智能【1 6 】控制系 统【j 川和社会经济等领域。近几年来，遗传规划的应用在以下几个方面表现比较突出。 ( 1 ) 机器人路径规划 移动机器人在进行工作时，往往要求根据某一准则( 如行走路线总长度最短、能量消耗最小等) 在工作区间中沿着一条最优( 或次优) 的路径行走。机器人路径规划问题可表示为一个有约束的优 化问题，许多学者探索了利用遗传规划规划机器人行走路径的可能性。k o z a 本人也描述了遗传规 2 遗传规划多分类系统的实现 划进化一个由算术操作和条件操作组成的计算机程序实现一个实时优化控制策略，使机器人在最 短时间内移动到指定点等【j j 。 ( 2 ) 预测和分类 遗传规划能动态产生预测分析的最优非线性结构，也能在多类模式的分类问题里，在所获得 数据和数学表达式之间发现联系，它不需要数据统计分布的预处理知识，就可自动发现某一类判 别式特征。它被广泛的应用于金融、医疗、电力系统负载等领域。 ( 3 ) 图像和信号处理 图像处理是计算机视觉中的一个重要研究领域，在图像处理中，不可避免的会产生一些误差， 如何使这些误差最小是计算机视觉达到实用化的重要要求。a t s u s h i 利用遗传规划产生有图像训 练集的对象模型川j 。遗传规划还可应用于图像恢复、图像压缩、图像检索等。 ( 4 ) 数据挖掘 数据挖掘就是从大型数据库的数据中提取人们感兴趣的知识。这些知识是隐含的、事先未知 的潜在有用信息，提取的知识表示为概念、规则、规律、模式等形式。a n d r e w 提出了一个基于遗 传规划的简单且有多种用途的数据挖掘系统【j 引。 ( 5 ) 信息检索 所谓信息检索就是用户提出一个查询，通常以关键字的形式输入，计算机通过关键字匹配， 返回有关的文档，用户自己查看文档，获取所需要的信息。遗传规划应用于信息检索系统是为了 改善通过关联反馈的布尔查询表述。d o n a l d 把文献视为在索引条件空间里的向量，布尔查询视为 剖析树，利用遗传规划的机制，调整查询来改善精度和检索i j 引。s m i h t 把布尔查询当作遗传规划 的有机体来繁殖产生新的有机体，根据检索的匹配程度赋予繁殖选中的几率l j 川。除此之外，遗传 规划在响应a g e n t ，电子电路设计以及进化硬件等方面的应用也非常成功，随着时间的推移，遗 传规划的应用范围会越来越大，将为人们提供一个崭新的解决复杂问题的强有力工具。 1 3 主要研究内容及要面临的问题 阐述了遗传规划多分类的基本原理，并利用c + + 语言和数据结构来进行编程，最终实现一个 多分类系统。 认真研究分析了遗传规划的原理及其解决问题的步骤，尝试性地对遗传规划在多类分类问题 中的技术进行了改进，所作的主要工作归纳如下一剀： ( 1 ) 建立了两种新的基丁动态边界的遗传规划的多类分类模型。如何将遗传程序的输出准确地 转化为类别标定? 一种简单的方法就是事先固定边界值，该方法称为静态选择边界，即基于静态 边界的遗传规划分类模型。但是这种手动选择分类边界的方法往往会造成不必要的复杂程序，需 要太多的先验知识，并可能导致学习训练的时间长，且精度不高。为了解决这些问题，本文在静 态边界的基础上进行改进，建立了一种基于动态边界的多类分类模型，即基于中心的动态边界选 择，将遗传程序输出的实数值转化为合适的类别标定。 ( 2 ) 采用遗传规划解决特定问题需要确定终端集。终端集由特征终端和常量( 又叫数字终端) 构成，特征终端是从问题领域中抽取的特征值，而常量是一些实数，由系统生成初始群体或变异 操作时产生。常量是否合适直接影响着分类精度和进化速度。 3 河北农业大学硕士学位( 毕业) 论文 该系统实现后，就可根据训练机和测试机来完成对数据的分类整理。 遗传规划是一种在可能空间中寻找合适计算机程序的自适应搜索算法。其搜索过程从本质上 从属于随机搜索算法，但其空间遍历性比传统的启发式搜索要好，遗传操作使得路径可以随机跳 跃至不同的子空间，从而在全局空间中以若干搜索集的并集的方式从时序过程方面逼近全集。遗 传规划的众多优势特性对其寻找最优解提供了一定的优势。 分类识别就是对输入信息的类别辨认过程。遗传规划不需要先验知识，但是遗传程序的输出 结果将返回一个单一的实数值。对于分类问题，必须将遗传程序的输出结果准确地转化为一系列 的类别标定。而两类分类问题，结果的正负值可以作为分类的标准。但是对于多类分类问题，如 何寻找合适的分类边界，确定适应度，是一个十分复杂的问题。 4 遗传规划多分类系统的实现 2 1 遗传规划的基本原理 2 遗传规划 遗传规划( g e n e t i c p r o g r a n l i n i n g ，简称g p ) 就是在遗传算法的基础上引入自动程序设计的一 种全新的方法。它的基本思想是，随机产生一个适合于所给问题环境的初始群体，即问题的搜索 空间；构成群体( p o p u l a t i n n ) 的个体( i n d i v i d u a l ) 都有一个适应度值：依据达尔文适者生存原则， 用遗传处理得到高适应度的个体，产生下一代群体：如此进化下去，直到给定问题的解或近似解 在某一代上出现为止【2 5 2 7 1 。采用g p 算法解决问题时需要确定以下五个要素【2 8 。3 0 】： 终止符集：由输入变量与常量构成。 在基于树的g p 中由于这些输入，常数在树分支的端点，也称叶结点。若把选择的特征( 输入 构成训练集，则g p 无异于其它的机器学习系统，所不同的是它如何表示特征( 输入) 。在g p 系统 中每个特征可作为终止符集来构造程序结构。在典型的基于树的g p 中，在运行的开始实数在给 定的常数集随机产生，称其为随机常数。 函数集：包含与应用有关的，适合于问题领域的参数，可以使用的函数范围很广泛，包括 算数运算，数学函数，也可使用任何程序设计语言中的程序构件。例如：算术运算符( + ，一， ，数学函数( s i n ，c o s ，t a n ，等) ，布尔运算符，条件表达式( i f t h e n e l s e ) 等。 用在g p 系统中的函数和终止符应足以能够表示问题的解，即满足充分性。另一方面最好不使 用大的函数集合，它将扩大搜索空间，有时会使问题的搜索更加困难。函数集合另一个重要的特 性是封闭性，即函数集中的任何函数的返回值及数据类型以及终止符集中符合终止符的可能取值 及数据类型都可以作为函数集中函数的参数。也就是说，函数集中的函数对其所有可能参数的组 合都是有定义的和封闭的。例如标准除法不能接受o 作为输入，因此定义一个新的除法称为保护 型除法，若除数是0 ，则函数返回值为0 或一个很大的数。 适应度( f i t n e s s ) ：适应度评价函数是评价种群个体性能的函数( 该性能代表个体解决目标 问题的能力) 。种群中每个个体都会依照适应度函数算出一个适应度值。 算法控制参数：包括种群的大小，遗传操作如交叉、复制、变异的概率。 终止条件：终止条件通常是预先给定的，可以是最大进化代数或是最大适应度值。 这五个要素中，前三个决定了算法的搜索空间，而后面两个则决定了算法的质量和速度。 遗传规划是通过以下步骤来解决问题的【纠删j ： ( 1 ) 确定输入及控制参量 主要包括：确定函数集和终止符集，根据问题的特点，合理确定解决问题所需要的函数集 及终止符集( 包括变量和常量) ；确定评价方法，群体中的每个个体是否适应环境，影响着对其 进行遗传操作，因此，必须选择某种方式对其适应性进行评价；确定控制参量，如群体大小， 迭代次数，交叉概率等；程序运行终止准则；最优结果确定及其参数。 ( 2 ) 随机产生初始解依照指定的形成规则随机生成初始群体( 初始解) 。 ( 3 ) 重复执行以下步骤，直至i , - k ，足要求为止。 评价群体中每一个个体，根据其解决问题的优劣程度，给每一个个体赋予一个适应度。 5 河北农业大学硕士学位( 毕业) 论文 生成新一代群体，即首先根据概率准则，选择适应度高的个体，复制到新一代群体中，接 着随机选择适应度比较高的两个个体，进行随机交叉，产生新一代个体，然后在子女个体中根据 概率进行变异操作。 ( 4 ) 在所有的迭代结果中，选择最好的结果作为遗传程序设计的解。 根据遗传规划的基本思想，遗传程序设计的一次运行并不能保证能够得到问题的解，如何确 定控制参数才使遗传程序设计达到最佳效果，这与所给问题环境有关，通常经多次反复实验而定。 图1 是g p 的流程图，图中n 表示群体中的个体数，变量i 表示一个个体，变量g e n 是当前代 的代号。 6 图1g p 流程图 f i g it h eg pf l o wc h a r t 遗传规划多分类系统的实现 2 2 遗传规划的重要特征 总的看来，遗传规划求解问题时的重要特征如下【4 , 1 8 , 2 9 , 3 2 】： ( 1 ) 产生的结果具有层次化的特点； ( 2 ) 随着进化的延续，个体不断朝问题答案的方向动态地发展； ( 3 ) 不需要事先确定或限制最终答案的结构或大小，遗传规划将根据环境自动确定。这样， 系统观测物理世界的窗口得以扩大，最终导致找到问题的真实答案。 ( 4 )输入、中间结果和输出是问题的自然描述，无需或少需对输入数据的预处理和对输入 结果的后处理。由此而产生的计算机程序便是由问题自然描述的函数组成。 必须指出，在遗传规划中，个体结构变化是主动的，它们并不是对问题答案的被动式编码， 这一点完全不同于遗传算法。个体结构在遗传时能从当前状态主动地改变其结构和大小进化成新 的、更优的状态。 2 3 遗传规划的个体描述方法 在遗传规划中，首先要解决的问题是如何用一系列可行的函数对个体进行描述，而这种函数 能反复地由n 个函数f = ( f l ，f 2 ，f 3 f n ) 和1 1 1 个终止符t = ( t l ，t 2 t n ) 组合而成。函数 集f 中每个特定的函数f 1 假定有z ( f 1 ) ( z = 1 ，2 ，3 ，n ) 个自变量，则对函数f 1 ，f 2 ， f n 来说，相应有的自变量个数分别为： z ( f 1 ) ，z ( f 2 ) ，z ( f n ) 函数集内的函数可以是： ( 1 ) 算术运算符，如+ ，一，等： ( 2 ) 标准数学函数，如s i n ，c o s ，e x p ，l o g 等； ( 3 )布尔运算符，如a n d ，o r ，n o t 等； ( 4 )条件表达式，如i f 等： ( 5 ) 任何其他可定义的函数： 终止符可以是变量( 如描述系统的输入、感触器、识别器、状态变量等) 或常量( 如布尔常 量n i l 等) 。有时，终止符隐含着函数关系，为简化起见将它视为无自变量的函数。 一般来说，在遗传规划中，将问题的输入部分用终止符( 值) 进行抽象，而用操作符( 函数) 来 模拟将对输入进行的处理，输出即为优化结果方法。这样，终止符集与函数集一起就构成解决问 题的一个完备方案。遗传规划的每个个体都是不同终止符和函数的组合，实际上就是一个待选方 案。 2 4 遗传规划初始群体的形成 初始群体由众多初始个体组成，初始个体为所要解决问题的各种可能的符号表达式( 算法树) ， 它通过随机方法产生，开始时，在函数集f 中安均匀分布随机地选出一个函数作为算法树的根结 点，我们把根结点的选择限制在函数集f 中是为了生成一个层次化的复杂结构；相反，若从终止 符集t 中随机选择根结点，则生成只有一个终止符的退化结构。图2 ( a ) 描述了函数“+ ”( 具有 7 河北农业大学硕士学位( 毕业) 论文 2 个自变量) 为根结点的算法树，函数“+ ”是随机地从函数集f 中选出的。一般情况下，从函 数集f 中选出的函数f 如果具有z ( f ) 个自变量，那么就要从节点发出z ( f ) 条件然后，对于 每条从节点发山的线，从函数集f 和终止符集t 的并集c = f u t 中再按均匀分布随机地选出一个 元素作为该条件的尾节点。如果此时选出的是一个函数，则重复执行上述过程。例如，若函数“” 从并集c 中被选出，则函数“”将作为非根内节点，如图2 ( b ) 中的点2 所示。由于函数“” 具有两个自变量，则从节点“”发出两条线。如果从并集c 中被选出的是终止符，它作为从节 点中发出的线的尾节点，则该分支上的树就终止生长。例如，在图2 ( c ) 中，恰巧终止符a 、b 、c 分布从并集c 中被选出，并作为树中各分支的尾节点，这时整个算法树生成过程终止。 ( a ) 2 ( b ) 图2 算法生成树过程 f i g2t h ep r o g r e s so f ap a r s et r e e 上述过程从上到下、从左到右不断重复，直到一棵完整的树生成为止。 2 5 初始个体生成的几种方法 ( c ) 初始个体的生成可采用不同的方法，不同的方法将产生不同的初始个体。常用的方法有三种， 即完全法、生长法、和混合、法1 8 , 9 , 1 8 , 4 5 j 。 ( 1 ) 完全法。用完全法产生的初始个体，每一叶子的深度都等于给定的最大深度( 叶子的 深度是指叶子距树根的层数) 。其实现方法是：若待定结点的深度小于给定的最大深度。则该结 点的选择将限制在函数集内，若待定结点的深度等于给定的最大深度，则该结点仅从终止符集内 选取。如此产生的个体树都是平衡的满二叉树，个体的结构形态比较单一，而且一旦规定初始树 深度，则个体的结点数较大，达到最大结点数n = 2 “一1 ( 在函数都为二目操作符时) 。显然，这种 方法增大了有用基因出现的概率，但同时将大量引入冗余的基因。 ( 2 ) 生长法：用生长法产生的初始个体具有不同的形态，每一叶子的深度不一定都等于给 定的最大深度。其实现方法是：若待定结点的深度小于给定的最大深度，则该结点的选择将限制 在函数集与终止符集组成的并集内：若待定结点的深度等于给定的最大深度，则该结点仅从终止 符集内选取。一般来说，此法并不规定个体树的最大深度，各结点的选择仅根据父结点的要求而 产生，不受附加条件限制。但是生长产生的个体树形多变，结构极不平衡。如果不加限制，树的 8 遗传规划多分类系统的实现 深度可能会相差悬殊，甚至出现一些体形异常庞大的树，而大量叶结点为空的个体，不利于计算 机存储，浪费大量存储空间和计算时间。 ( 3 ) 混合法：混合法是完全法和生长法的综合。其实现方法是：初始个体的深度在2 至给定 的最大深度之间均匀选取，这时每一种深度下的初始个体树所占百分比n 为： n = l o o ( 给定的最大深度一2 + 1 ) 在每一种深度中，5 0 的初始个体用完全法产生，另5 0 的初始个体用生长法产生。混合法 随机选用生长法或完全法生成具体的初始个体，以达到既保证群体中基冈数量，又增加个体多样 性的目的。 2 6 适应性度量 适应性是遗传规划中自然选择的驱动力。利用适应性来控制群体中结构改变的过程。度量适 应性的方法有多种：一种是显式方法，另一种式隐式方法。而显式方法最常用，本文仅讨论这种 方法。 在显式方法中，借助于具体问题的显式估值方法，对个体赋予一适应性测度值。常见的适应 性测度有下列四种：原始适应度、标准适应度、调整适应度、归一化适应度。 ( 1 原始适应度 原始适应度是问题适应性自然描述的一种度量。例如，人工蚂蚁问题中研究蚂蚁吃掉的食物 块数，吃掉的食物越多越好，原始适应度便是被蚂蚁吃掉的食物块数。 当原始适应度定义为误差时，也就是在一组适应度计算试例中，个体返同值与测试值之间的 距离之总和。如果符合表达式是整数型或浮点型，那么距离之和表现为符号表达式的返回值与实 测值之间的距离绝对值的总和。在群体中，子代t 某一个体i 的原始适应度r ( i ，t ) 定义为： 监 r ( i ，t ) = ：is ( f ，) - c ( j ) i = l 式中s ( i ，j ) 个体i 在适应度计算试例j 下的返回值； n 。适应度计算试例数； c ( j ) 适应度计算试例j 的实测值或正确值。 如果符号表达式是布尔型或字符型，那么距离之和表现为符号表达式的返回值与实测值之间 的符合不匹配的个数。 如果符号表达式赛是实数型，那么距离只好可用其平方和的平方根来代替，这样可以增加距 离对适应度的影响。 由于原始适应度是问题的自然表达，因此原始适应度的最佳值为越小越好( 当原始适应度为 误差时) ，或越大越好( 当原始适应度为吃掉的食物块数时) 。 ( 2 ) 标准适应度 标准适应度s ( i ，t ) 是原始适应度又一描述，即标准适应度总是表现为数值越小适应度越好。 于是有两种情况发生：i ) 对于某些问题，若原始适应度越大越好( 如人工蚂蚁问题，若使人工蚂 蚁吃掉的食物块数越多越好，则原始适应度越大越好) ，则标志适应度可定义如下： 9 河北农业大学硕士学位( 毕业) 论文 s ( i ，t ) = r 。，一r ( i ，t ) 式中k 。为原始适应度所能达到的最大值。ii ) 对于另外一些问题，若原始适应度越低越 好( 如对于最优控制问题，若使控制成本越小越好，则原始适应度越低越好) ，则标准适应度即 为原始适应度，即： s ( i ，t ) = r ( i ，t ) ( 2 ) 调整适应度 子代t 中个体i 的调整适应度a ( i ，t ) 由标准是引导计算而得，即： 口( t f ) 2 斋高 通常s ( i ，t ) o ，则a ( i ，t ) o ，1 ，且调整适应度值越人，个体越优良。当标准适应度接近 0 时，调整适应度具有扩大标准适应度值微小差别的好处。这一情况常常出现在进化的最后几代 中。随着群体的不断进化，着重点就要放在区分好的和更好的个体上，他们的差别往往很小。特 别是当接近一个正确答案时，标准适应度接近0 ，这时调整适应度的扩张能力就显得特别有效。 例如，当标准适应度取值介于0 ( 最佳) 和6 4 ( 最差) 之间时，标准适应度为6 4 、6 3 的两个较 差个体的调整适应度分别为0 0 1 5 4 、0 0 1 5 6 ，其差别为0 0 0 0 2 。但是，标准适应度为4 、3 的两 个优良个体的调整适应度分别为0 2 0 、0 2 5 ，其差别为0 0 5 。 ( 4 ) 归一化适应度 归一化适应度n ( i ，t ) 由调整适应度计算而得，即： 俐i = 磐 蕊力 躺 式中卜群体重点个体数目。归一化由三个理想的特征，即： ( 1 )n ( i ，t ) 0 ，1 ； ( 2 ) 适应度值越大，个体越优良； ( 3 ) ”( 七，f ) = l ； 如果个体选择方法是基于适应性一比例适应度原则，那么归一化适应度直接可作为个体选择 的概率。 顺便指出，适应度通常用一组适应度计算试例进行估值。该组计算试例是群体中每一个体( 符 合表达式) 适应性估值的基础，它反映了众多有代表性的环境，从而有效地获得不同个体的适应 性估值。显然。该组计算试例仅仅是问题的整个值域空间中一些典型取样，而该空间通常很大或 无限。然而，对于自变量不多的一些问题( 如布尔函数) 来说，适应度计算试例可取自变量的所 有可能组合。此时，该组适应度计算试例即是整个值域空间的代表。 1 0 遗传规划多分类系统的实现 2 7 基本算子 遗传规划中的基本算子包括复制、交叉和变异。在计算群体适应度之后，依次进行这些操作。 完成一次迭代，群体于是得以进化【8 , 9 , 1 8 , 2 6 , 4 6 】。 1 复制 当复制操作发生时，一个亲代个体繁殖一个后代个体。复制过程由两部分组成：首先，根据 适应度按照不同的选择方法从群体中选出一个亲代个体；其次，被选出的亲代个体在未经过任何 变化的条件下从当前代复制到新一代中。 根据适应度，有许多不同的亲代选择方法。 i ) 适应度一比例选择法。该选择法是一种最常用的选择方法，其含意是个体适应度越高，被 选中的概率越大。如果f ( s ；( t ) ) 是个体s ；( t ) 在第t 代的适应度，那么该个体被选中进行复制的 概率p 为： p ：丝垡 厂( ( f ) ) = l 式中 卜群体中的个体数目。 特别地，当f ( s ；( t ) ) 是归一化适应度n ( s ；( t ) ) 时，个体s - ( t ) 被选中进行复制的概率就为 n ( s 。( t ) ) 。 i i ) 贪婪选择法。当群体中的个体数超过1 0 0 0 时，进化过程消耗的计算时间特别长，有必要 偏袒适应度较高的优良个体，优先选择它们，以缩短计算时间。为此，将个体按归一化适应度从 大到小排序，将群体分为i 、i i 两组。i 组由归一化适应度较高的优良个体组成；余下的归为i i 组。进行个体选择时，8 0 的时在i 组中选择，2 0 的时间在i i 组中选择。 i i i ) 极差选择法。这种方法将个体按适应度的大小分成许多个级别，个体根据种群中个体适 应度的级别( 而不是适应度) 进行选择。于是，适应度较高的个体具有适当的选择优势，从而降 低适应度特高的个体被优先选择的可能性。与此同时，极差选择法可扩大适应度值相差不大的个 体间的差别，利用分级线的位置使较优的个体能较多地被选中。 i v ) 竞争选择法。这种方法是：首先从群体中随机选出组个体，然后在该组个体中选出一 个具有高适应度的个体。 有必要指出，亲代个体在选择完成后仍留在当前代群体中，而且亲代个体可被多次选中参与 复制。由于被复制的个体在结构上未发生变化，因此这些个体的适应度无需重新计算，这样可节 省许多计算时间。 2 交换 在遗传规划中，交换是生成新个体的活动。新个体通过亲代个体提供不同组成部分而产生。 交换时，两个亲代个体产生来年改革子代个体。 i ) 交换操作的实现方法。与复制过程相类似，第一个亲代个体根据上述的某种选择方法从群 体中选出，第二个亲代个体也采用相同的选择方法从群体中选出，但两者选择过程独立。这样 来，所选出的两个亲代个体结构、大小可能均不相同。交换时，在每个亲代个体的算法树上分别 河北农业大学硕十学位( 毕业) 论文 按均匀概率分布随机选择一个交换点，于是产生一棵以交换点为根的子树，该子树包含交换点一 下的所有子树。具有这样特点的一棵子树称为一个交换段。有时，一个交换段仅是一个叶子。 为了生成第一个子代个体，第一个亲代个体删掉其交换段后，将第二个亲代个体的交换段插 入到它的交换点处，这样第一个子代个体便产生了。同样，第二个子代个体也是通过第二个亲代 个体删掉其交换段后，将第一个亲代个体的交换段插入到它的交换点后而形成。 i i ) 交换操作的一般特征。由于交换时整个子树被交换，次不管亲代个体和交换点如何选 择，交换所产生的新的( 子代) 符号表达式总是语法上合法的表达式。 如果一个亲代个体的交换段恰为一个终止符( 叶子) ，而另一个亲代个体的交换段为一棵子 树，那么在交换时，第一个亲代个体的这个叶子( 交换段) 将插在第二个亲代个体剩余段的交换 点处，第二个亲代个体的子树( 交换段) 将插在第一个亲代个体剩余段的交换点处。这样，交换 操作往往汇产生深度较大的子代个体。 如果两个亲代个体的交换段均为终止符，那么交换操作仅表现为两颗树之间的叶子交换。这 相当与一棵树的叶子发生突变。因此，点突变时交换操作的一阵退化表现。 如果一个亲代个体的交换段恰为整个树( 即交换点为根) ，而另一个亲代个体的交换段为一 棵子树，那么在交换时，第一个亲代个体将整个插在第二个亲代个体剩余段的交换点处，第一个 亲代个体变为子代个体的一棵子树。这也，往往会产生深度很大的子代个体。 在交换操作中，子代个体的大小( 一般用树的深度衡量) 应有一定的限制。这种限制将防治 因少数子代个体太大而花费太多的计算时间。如果两个亲代个体交换后产生两个巨型子代个体， 那