（计算机应用技术专业论文）基于遗传规划的多类分类技术研究.pdf

摘要 分类问题尤其是多类分类问题一直是数据挖掘研究的热点问题。在实际应用中， 如图像识别，文本分类等等，需要处理的数据都是海量和多类别的。如何解决多类别 的分类问题，是近几年研究的重点之一。本文将新的遗传学习算法遗传规划 ( g e n e t i cp r o g r a m m i n g ) 用于多类分类问题中，对其算法进行了尝试性地改进。 遗传规划是一种新型的搜索寻优方法。它仿效生物界中进化和遗传的过程，遵从 “优胜劣汰，适者生存”原则，从一组随机生成的初始可行解开始，通过复制、交叉 和变异等遗传操作，逐步迭代而逼近问题的最优解。本文阐述了遗传规划算法的原理 和进化计算的基本知识；介绍了相关分类技术；分析了遗传规划的特点；研究了运用 遗传规划解决分类问题的方法模型；并针对遗传规划在多类分类问题中的技术局限进 行了改进。 本文主要从三个方面对基于遗传规划的多类分类技术进行改进。首先在基于静态 选择边界模型( s t a t i cr a n g es e l e c t i o n ，s r s ) 的基础上进行改进，建立了两种动态分 类模型：基于中心的动态边界选择和基于狭槽的动态边界选择，对这两种模型进行了 相应的算法设计。第二，将梯度下降搜索算法引入到遗传规划中。遗传规划整体算法 仍然运用全局搜索，只是在确定遗传程序数字终端时运用了梯度下降搜索的方法，不 影响遗传规划整体的束搜索和遗传操作。第三，遗传程序在进行遗传操作的过程中， 会产生很多冗余。本文提出一种在单个程序进化过程中定期清除冗余的方法。该方法 既不影响遗传规划的结构和进化过程，又可以提高精度，加速演变。最后，进行了实 验设计，通过五个不同难度的图像数据样本集( s h a p e ，c o i n ) 对以上三方面的改进进 行验证。实验结果表明，s r s 法在较简单的两类分类问题中效果较好，而基于动态的 边界选择模型为解决遗传程序的输出转化为类别标定的分类问题，尤其是较复杂的多 类分类问题提供了新的解决方法；梯度下降搜索算法提高了群体的进化速度和学习效 率；遗传程序进化过程中定期对终端集进行简化，在一定程度上改善了分类性能。 本文在遗传规划技术三个方面的改进不同程度地提高了遗传规划的分类性能，但 这仅仅是一个初步的探索，需要进一步研究探讨。 关键词遗传规划；g p ：多类分类；梯度下降法；动态选择边界 t h er e s e a r c ho ng e n e t i cp r o g r a m m i n g t e c h n i q u e sf o rm u l t i - c l a s s i f i c a t i o n a u t h o r m ax i a o l i s u p e r v i s o r ：p r o f e s s o rt e n gg u i f a z l a o ug u i h o n g m a j o r ：c o m p u t e r a p p l i e dt e c h n o l o g y a b s t r a c t c l a s s i f i c a t i o n , p a r t i c u l a rm u l t i - c l a s s i f i c a t i o np r o b l e mh a sb e e nah o tt o p i ci nd a t a m i n i n g p r a c t i c a lp r o b l e m ss u c h 越o b j e c tr e c o g n i t i o na n dt e x tc l a s s i f i c a t i o nn e e dt od e a l w i t hh u g ea n dm u t i l - c a t e g o r yd a t a i ti so n eo f t h ei m p o r t a n t c h a l l e n g e sh o wt os o l v el a r g e s c a l ea n dm u t i l - c l a s sp r o b l e m si nr e c e n ty e a r s t h i sp a p e rd e s c r i b e st h eu s eo ft h en c w - g e n e t i cs t u d ya l g o r i t h m 电e n e t i cp r o g r a m m i n gt os o l v em u l t i - c l a s s i f i c a t i o np r o b l e m s b ym a k i n gab i tt e n t a t i v ei m p r o v e m e n t i nt h ea 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 p ) i san e vt 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 s i n h e r i ta n de 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 l 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 no p e r a t i o n s t l l 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 c p r o g r a m m i n ga n dt h ek n o w l e d g eo fe v o l u t i o n a r yc o m p u t a t i o n , i n b o d u c e st h er e l a t e d c 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 fg pa n dt h ei m p l e m e n t a t i o n m e t h o d so fc l a s s i f i c a t i 0 0p 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 nm u l t i c l a s s i f i c a t i o n p r o b l e m 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 t h i st h e s i sf o c u s e s0 1 1t h r e es i d e st oi m p r o v et h em u l t i - - c l a s s i f i c a t i o nt e c h n o l o g yi ng e t h em a i nr e s e a r c hc o n t r i b u t i o no f t h et h e s i sc a nb es u m m a r i z e da sf o l l o w s ：f i r s t , t h e0 e w d y n a m i cs t r a t e g i e s ，i n c l u d i n gc e n t e r e dd y n a m i cr a n g es e l e c t i o na n ds l o t t e dd y n a m i c r a n g es e l e c t i o n ，w c a ef o u n dt oi m p r o v et h ep e r f o r m a n c eo ft h es y s t e m ，o v e rt h es t a n d a r d s r s s e c o n d , g r a d i e n t - d e c e n ts e a r c ho ni n d i v i d u a lp r o g r a m si si n l r o d u c e dt og pi nt h e p a p e r g pi ss t i l lu s e da sag l o b a lb e a ms e a r c h ，b u tl o c a lg r a d i e n t - d e s c e n ts e a r c hi sm a d e o np r o g r a m s t h i r d , s i m p l i f i c a t i o no fp r o g r a m sd u r i n ge v o l u t i o ni si n t r o d u c e di nt h i s a r t i c l e a na l g o r i t h mi sd e s c r i b e dt h a tr e m o v e sr e d u n d a n c yf r o ma p r o g r a m ，a n di su s e do n a l lp r o g r a m sp e r i o d i c a l l yd u r i n ge v o l u t i o n f i n a l l y , t h ee x p e r i m e n t st h r o u g hf i v ei m a g e d a t a s e t s ( s h a p e c o i n ) a r es e t t h ee x p e r i m e n t a lr e s u l t ss h o wt h a t ：s r sw a s s e e nt op e r f o r m w e l lo ot h et w o - c l a s s i f i c a t i o na n de a s yp r o b l e m s ，b u tc 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 nw e r es e t oo u t p e r f o r m e dt h es t a n d a r ds r s0 0t h e h a r d e rm u l t i - c l a s s i f i c a t i o np r o b l e m s ；t h eu s eo fg r a d i e n t - d e c e n ts e a r c hp r o d u c e de x c e l l e n t r e s u l t s ，t r a i n i n gt i m e sw e r es h o r t e n e df o re a s yp r o b l e m s ，a n dt e s ts e ta c c u r a c i e sw e r e i m p r o v e df o rh a r d e rp r o b l e m s ；s i m p l i f i c a t i o ni m p r o v e dt h ec l a s s i f i c a t i o na c c u r a c y , p a r t i c u l a r l yf o rt h eh a r d e rp r o b l e m s t h ep a p e ri nt h et l l e r es i d e sh a si m p r o v e dt h ee l a s s i f i c a t i 0 0p e 而o r m a n c ei ng p b u t t h a ti so n l yap r e l i m i n a r ye x p l o r a t i o n , n e e d i n gf u r t h e rs t i j d y k e yw o r d s ：g e n e t i cp r o g r a m m i n g ；g p ；m u l t i - c l a s s i f i c a t i o n ；g r a d i e n t - d e c e n t ；d y n a m i c r a n g es e l e c t i o n 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究 成果。据我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得塑i 堡盔些盘堂或其他教育机构的学 位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文 中作了明确的说明并表示谢意。 学位论文作者签名：与晚；q 签字日期：2 口0 7 年月i o 日 学位论文版权使用授权书 本学位论文作者完全了解塑a 垦壅些盘堂有关保留、使用学位论文的规定， 有权保留并向国家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借 阅。本人授权塑些盔些盘堂可以将学位论文的全部或部分内容编入有关数据库进行 检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：弓日笼石，j 导师签名： 签字日期：加订年月0 日 学位论文作者毕业后去向： 工作单位： 通讯地址： 掷期。7 年月日 电话： 邮编： 基于遗传规划的多类分类技术研究 1 1 研究背景 i 绪论 分类问题也被称作模式识别问题，是机器学习的一个分支，它在信息领域是一个热门的研究 方向。多类分类问题是模式识别的主要分支，在实际生活中有着广泛的应用。在医学图像中找出 异常像素区域进行医疗诊断，在一系列语音流中进行单词或者短语识别，在众多信用卡的记录中 认定非法偷盗提取等仅仅是众多实例中的三个1 1 习。在许多情况下，用人工方法进行识别与分类过 于昂贵，而且耗时耗力。随着信息与网络技术的发展，需要识别与分类处理的数据量日益增大。 在这种背景下，借助计算机进行精确分类与识别不仅是必要的，而且将具有广泛的社会效益与经 济效益。 一些传统的分类方法大都是以统计学为基础，有关样本的先验知识对分类器的分类精度有很 大的影响，然而在许多实际的分类问题中无法取得准确的先验知识，不能指出或找到某一分类问 题的所有内部特征及复杂的相互关系。决策树分类方法是当今较成熟的分类技术，但是构造简单 且精确的决策树是一项艰巨的任务。另外，像神经网络这样的学习算法由于在确定网络结构时有 诸多因素需要考虑，甚至于初值选取不当都有可能导致局部收敛或发散，其特性很难把握。遗传 算法作为一种基于生物进化和遗传思想的全局随机搜索算法也应用到分类问题中，但它在规则的 表示上不是很灵活。支持向量机( s v g ) 也是一种针对分类和回归的机器学习方法，最初s l g 主 要用来解决两类分类问题，不易直接用于多类分类，如何将其有效地推广到多类分类问题还是一 个正在研究的问题”州。 作为进化计算的又一分支遗传规划( g e n e t i cp r o g r a m m i n g ，简称g p ) ，又叫遗传程序 设计，是在遗传算法的基础上引入自动程序设计的一种全新的方法。它能动态产生预测分析的最 优非线性结构，也能在多类模式的分类问题里，在所获得数据和数学表达式之间发现联系。它不 需要数据统计分布的预处理知识，就可自动发现某一类判别式的特征p j 。显而易见，遗传规划技 术在分类问题中的成功应用，将在工农医中具有广泛的应用性，也为研究者提供一个新的解决复 杂问题的强有力的工具，具有重大的应用价值和现实意义。 1 2 研究现状 遗传规划方法是近几年才出现的一种新方法。遗传规划是一种进化符合一些客观标准程序的 方法。1 9 9 2 年，美国斯坦福大学j o h nk o z a 教授将这一计算机自动程序设计思想引入遗传算法g 鸹 ( g e n e t i c s a l g o r i t h m s ) m 】中，创立了遗传规划1 8 ，j 。与遗传算法需要将问题的解编码成固定长度 的二进制( 或其他) 字符串不同，遗传规划使用一种更加灵活的方式分层结构来表示解空间。 这些结构的叶结点是问题的演示变量或者特征，中间结点则是组合这些叶结点的函数或者操作 符。这样，遗传规划就可以直接用达尔文进化思想对这些具有分层结构的解进行演变学习，从而 克服遗传算法在表示方式上的局限性，对群体( p o p u l a t i o n ) 中独立的程序个体遗传程序进行 河北农业大学硕士学位( 毕业) 论文 操作，进而生成解决问题的程序。 自那时起，世界各国科学家对遗传规划进行了深入研究。英国伦敦大学的w i l l i a m ( b i l l ) l a n g d o n 教授与e s s e x 大学的r i c a r d op o l l 教授对g p 教学基础与程序段( f r a g m e n t s ) 进行了研究l l e l ； 美国麻省理工大学人工智能研究室的u n a m a yo r e i l l y 教授对g p 的积木块( b u i l d i n gb l o c k ) 假设 与理论进行了探索”l 】；加拿大m e m o r i a l 大学的w o l f g a n gb a n z h a f 教授进行了线形与图形表示的研 究i j 目；澳大利亚皇家墨尔本理工大学的v i c t o rc i e s i e l s k i 教授与张孟杰博士等对g p 用于多类领域进 行了研究【”j ；意大利p a r m a 大学s t e f a n oc a g n o n i 教授，墨西哥o g u s t a v o 教授与张孟杰博士对g p 与图像识别与信号处理进行了研究1 1 6 “1 7 1 ；我国云庆夏、王占权教授等对g p 的收敛性进行了研究【1 8 1 ； 牛惠民教授对模糊随机网络与复合遗传规划进行了研究 1 e l 等。这些研究己将g p 从原有的单一树 状结构表示法发展成为自由树、线性、图像与语法等组成的表示法群，已从原来的以l i s p 为代表 的程序表达语言扩展为人们更为熟悉、应用更为广泛的c 厄+ + 表述语言，从原来的符号回归应用 领域扩展到计划与规划最佳控制，计算机视觉与图像处理、游戏策略，智能机器人足球，以及分 类与识别问题等众多领域。在这些众多种类的g p 中以树形结构及其类似树形结构( t r e el i k e ) 为基础的g p 仍占据主流地位，是目前最为常用的表示模式。 遗传规划自动地在可能的程序空间中寻找最优化或者最满意的计算机程序，其采用灵活的计 算机程序结果表示和强大的进化学习搜索能力，引起了世界各国学者的广泛关注闭。遗传规划在 机器人路径规划、预测、分类、数据挖掘等方面有了一些应用。但总体来说，遗传规划是一项很 新的理论，人们对它的研究还不全面，使得它的性能没有得到充分发挥。遗传规划作为一种新的 分类方法，至少还存在着以下问题： ( 1 ) 遗传程序分类转化问题。目前，对于多类分类问题。遗传规划技术还不能准确地将输 出转化为一系列的类别标定，分类的准确率较低。 ( 2 ) 数字终端的优化问题。数字终端是终端集( t e r m i n a l s ) 的重要组成部分，是在系统生 成初始群体或者变异操作过程中随机产生的。其值直接影响着遗传规划的进化速度和学习效率， 如何对这些数字终端进行优化还需要进一步的研究。 ( 3 ) 遗传规划在解决复杂问题的时候，需要从一个相当大的状态空间搜索到好的解，往往 会造成。规模爆炸”。即作为程序个体表示的抽象语法树的深度和广度，在进化过程中不断增大 而与此同时作为解的群体却没有任何的改进。k o z a 发现导致算法的“规模爆炸”的主要原因是“内 含子”的大量产生如何降低进化过程中的“内含子”也是遗传规划研究的重点。 1 3 本文研究思路 遗传规划是一种在可能空间中寻找合适计算机程序的自适应搜索算法。其搜索过程从本质上 从属于随机搜索算法，但其空间遍历性比传统的启发式搜索要好，遗传操作使得路径可以随机跳 跃至不同的子空间，从而在全局空间中以若干搜索集的并集的方式从时序过程方面逼近全集。遗 传规划的众多优势特性对其寻找最优解提供了一定的优势。 分类识别就是对输入信息的类别辨认过程。遗传规划不需要先验知识，但是遗传程序的输出 结果将返回一个单一的实数值。对于分类问题，必须将遗传程序的输出结果准确地转化为一系列 2 基于遗传规划的多类分类技术研究 的类别标定。而两类分类问题结果的正负值可以作为分类的标准。但是对于多类分类问题，如 何寻找合适的分类边界，确定适应度，是一个十分复杂的问题。 本文认真研究分析了遗传规划的原理及其解决问题的步骤，尝试性地对遗传规划在多类分类 问题中的技术进行了改进，所作的主要工作归纳如下： ( 1 ) 建立了两种新的基于动态边界的遗传规划的多类分类模型。如何将遗传程序的输出准 确地转化为类别标定? 一种简单的方法就是事先固定边界值，该方法称为静态选择边界( s t a t i c r a n g es t a t i c ，简称s r s ) ，即基于静态边界的遗传规划分类模型。但是这种手动选择分类边界的 方法往往会造成不必要的复杂程序，需要太多的先验知识，并可能导致学习训练的时间长，且精 度不高。为了解决这些问题，本文在s r s 的基础上进行改进，建立了两种基于动态边界的多类分 类模型，即基于中心的动态边界选择和基于狭槽的动态边界选择，将遗传程序输出的实数值转化 为合适的类别标定。 ( 2 ) 采用遗传规划解决特定问题需要确定终端集。终端集由特征终端和常量( 又叫数字终 端) 构成，特征终端是从问题领域中抽取的特征值，而常量是一些实数，由系统生成初始群体或 变异操作时产生。常量是否合适直接影响着分类精度和进化速度。本文引入梯度下降搜索算法来 对遗传程序的数字终端进行优化设计，优化数字终端，以提高分类的精度和效率。 ( 3 ) 遗传程序在进行遗传操作的过程中，会产生大量“内含子”。第六章中提出一种在单 个程序进化过程中定期清除。内含子”的方法。该方法既不影响遗传规划的进化过程，又可以提 高精度，加速演变。 1 4 论文内容安排 第一章绪论，简要阐述了本文的研究背景，系统总结了国内外的研究现状，说明了本文的 研究目的，研究内容和思路。 第二章介绍了进化计算的基本理论，包括遗传算法，进化策略，进化规划，研究了遗传规 划的基本原理，并对遗传规划的特点进行了归纳。 第三章回顾了当前几个主要的分类技术以及运用遗传规划解决分类问题的步骤，分析了基 于遗传规划的多类分类问题的现有技术。 第四章本文的重点，阐述基于遗传规划的多类分类技术的改进。主要从三个方面对遗传规 划技术进行了改进：第一，在s r s 的基础上改进建立了两种基于动态的边界选择模型：基于中心 的动态边界选择和基于狭槽的动态边界选择。这两种动态边界选择模型可以根据遗传程序输出值 动态调整分类边界，并且分类的顺序也可呈非线性分布：第二，将梯度下降搜索算法引入到遗传 规划中，在不影响遗传规划束搜索的情况下，对数字终端进行优化；第三，提出了一种在遗传程 序进化过程中减少“内含子”的简化方法。 第五章运用s h a p e 、c o i n 两个数据集形成的五个数据样本进行实验验证，并对结果进行了 分析。 第六章结论与展望，对本文的工作作了总结，并指出今后需要进一步探讨的问题。 3 河北农业大学硕士学位( 毕业) 论文 2 遗传规划的基本理论 遗传规划是借鉴生物界的自然选择和遗传机制，在遗传算法基础上发展起来的通过自动生成 计算机程序( 表达式) 来解决问题的一种进化方法。 2 1 进化计算 进化计算是一系列搜索技术，包括进化规划、进化策略、遗传算法、遗传规划等口”。尽管进 化算法有很多变化，但他们都是基于自然进化过程的基本计算模型。与传统的基于微积分方法和 穷举法等优化算法相比，进化计算是一种成熟的具有高鲁棒性和广泛适用性的全局优化方法，具 有自组织、自适应、自学习的特性，能够不受问题性质的限制，有效地处理传统优化算法难以解 决的复杂问题1 2 2 1 。近年来，国际上掀起了进化计算的研究热潮，各种新的研究结果和应用实例不 断涌现。 2 1 1 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ) 最早是由h o l l a n d 于7 0 年代提出的，是模仿生物遗传学和自然选 择机理，通过人工方式构造的一类优化搜索算法，是对生物进化过程进行的一种数学仿真，是进化 计算的一种最重要形式i l m 。 遗传算法是一种基于空间搜索的算法，它通过自然选择、遗传、变异等操作以及达尔文适者 生存的理论，模拟自然进化过程来寻找所求问题的解。其运算基础是字符串，就相当于生物学中 的染色体。字符串由一系列字符组成，每个字符都有特定的含义，反应所解决问题的某个特征田】。 遗传算法的特点是： ( 1 ) 遗传算法将搜索过程作用在编码后的字符串上，不直接作用在优化问题的具体变量上， 在搜索中用到的是随机的变换规则，而不是确定的规则，并且在搜索时采用启发式搜索，而不是 盲目的穷举，所以具有较高的搜索效率。 ( 2 ) 遗传算法不像其它的大多数优化算法都是基于线性、凸性、可微性等要求。它不需要 导数等其他辅助信息，对问题的依赖性较小，因此具有高度的非线性，适用范围更广。 ( 3 ) 遗传算法从一组初始点开始搜索而不是从某个单一的初始点开始，并且给出的是一 组优化解，而不是一个优化解，这样可以给设计者更大的选择余地，能在解空间内充分搜索，具 有全局优化能力。 正是基于以上优点，遗传算法对于优化工作者来说充满了吸引力。但是由于遗传算法用字符 串表达问题，而且字符串的长度常常是固定的，这就限制了它的应用自然界的问题往往很复杂， 通常不能用简单的字符串表达所有的性质，因此有必要改进遗传算法的表达形式。 4 基于遗传规划的多类分类技术研究 2 1 2 进化规划 进化规划，又叫进化编程，由美国人l j f o g e l 于2 0 世纪6 0 年代提出的一种模仿人类智能 的方法1 2 ”。他提出采用有限字符集上的符号序列表示模拟的环境，采用有限状态机的演化表示智 能系统来预测问题田j 。这种状态机的状态变换是通过对应的离散有界集上进行的均匀随机变异来 修改的。进化规划根据正确预测的符号数来度量适应值。通过变异，为父代群体中的每个机器状 态产生一个子代。父代和子代最好的部分被选择生存下来。这种方法与遗传算法有许多共同之处， 但不像遗传算法那样注重父代与子代的遗传细节，而是从整体的角度出发来模拟生物进化过程 的。它着眼于整个群体的进化，强调的是“物种的进化过程”，把侧重点放在父代与子代表现行 为的联系上。所以在进化规划中不使用个体交叉之类的遗传操作，个体的变异操作是唯一的一种 晟优个体搜索方法，这也是进化规划的独特之处。 2 1 3 进化策略 进化策略是一类模仿自然进化原理以求解参数优化问题的算法。它是i 扫r e c h e n b e r g 、s c h w e f e l 和p e t e r b i e r 于1 9 6 4 年提出的【1 9 1 。它的基本思想是：首先随机产生一个离散的初始个体，然后将 一个满足二项分布的变异作用在初始个体上，这样得到一个新的个体，从这两个个体中选择适应 值较大的个体作为下一代的副个体，这就完成一次循环。 进化策略与遗传算法的区别：首先两者的复制参数不同，遗传算法的复制参数( 交叉和变异 的可能性) 在进化过程中保持不变，而进化策略适时改变这些参数：其次，两者表示个体的方式 不同。进化策略在浮点矢量上运行，而遗传算法一般运行在二进制矢量上 2 4 1 与进化规划不同的是，进化策略的选择是确定的，将编码结构视为个体的抽象，所以可以通 过重组来生成新的个体。 2 2 遗传规划 2 2 1 遗传规划基本原理 遗传规划( g e n e t i cp r o g r a n m t i n g ，简称g p ) 就是在遗传算法的基础上引入自动程序设计的一 种全新的方法。它的基本思想是随机产生一个适合于所给问题环境的初始群体，即问题的搜索 空间；构成群体( p o p u l a t i o n ) 的个体( i n d i v i d u a l ) 都有一个适应度值；依据达尔文适者生存原则， 用遗传处理得到高适应度的个体，产生下一代群体；如此进化下去，直到给定问题的解或近似解 在某一代上出现为止 2 f , - - 2 7 。 采用g p 算法解决问题时需要确定以下五个要素 2 s - 3 0 1 ： 终止符集( t e r m i n a ls e t s ) ：由输入变量与常量构成。 在基于树的g p 中由于这些输入，常数在树分支的端点，也称叶结点。若把选择的特征( 输入) 构成训练集，则g p 无异于其它的机器学习系统，所不同的是它如何表示特征( 输入) 在g p 系 统中每个特征可作为终止符集来构造程序结构。在典型的基于树的g p 中，在运行的开始实数在给 5 河北农业大学硕士学位( 毕业) 论文 定的常数集随机产生，称其为随机常数。 函数集( f u n c t i o ns e t s ) ：包含与应用有关的，适合于问题领域的参数，可以使用的函数 范围很广泛，包括算数运算，数学函数，也可使用任何程序设计语言中的程序构件。例如：算术 运算符( + ，一，) ，数学函数( s i n ，c o s ，切i i te x p ，l o g 等) ，布尔运算符，条件表达式( i f - t h e n - c l s e ) 等。 用在g p 系统中的函数和终止符应足以能够表示问题的解，即满足充分性。另一方面最好不使 用大的函数集合，它将扩大搜索空问，有时会使问题的搜索更加困难。函数集合另一个重要的特 性是封闭性，即函数集中的任何函数的返回值及数据类型以及终止符集中符合终止符的可能取值 及数据类型都可以作为函数集中函数的参数。也就是说，函数集中的函数对其所有可能参数的组 合都是有定义的和封闭的。例如标准除法不能接受0 作为输入，因此定义一个新的除法称为保护 型除法，若除数是0 ，则函数返回值为0 或一个很大的数。 适应度( f i t n e s s ) ：适应度评价函数是评价种群个体性能的函数( 该性能代表个体解决目 标问题的能力) 种群中每个个体都会依照适应度函数算出一个适应度值。 算法控制参数：包括种群的大小，遗传操作如交叉、复制、变异的概率。 终止条件：终止条件通常是预先给定的，可以是最大进化代数或是晟大适应度值。 这五个要素中，前三个决定了算法的搜索空间，而后面两个则决定了算法的质量和速度。 遗传规划是通过以下步骤来解决问题的口 3 9 1 ： ( 1 ) 确定输入及控制参量 主要包括：确定函数集和终止符集，根据问题的特点，合理确定解决问题所需要的函数集 及终止符集( 包括变量和常量) ；确定评价方法，群体中的每个个体是否适应环境，影响着对 其进行遗传操作，因此，必须选择某种方式对其适应性进行评价；确定控制参量，如群体大小， 迭代次数，交叉概率等；程序运行终止准则；最优结果确定及其参数。 ( 2 ) 随机产生初始解 依照指定的形成规则随机生成初始群体( 初始解) 。 ( 3 ) 重复执行以下步骤，直到满足要求为止 评价群体中每一个个体，根据其解决问题的优劣程度，给每一个个体赋予一个适应度。 生成新一代群体，即首先根据概率准则，选择适应度高的个体，复制到新一代群体中， 接着随机选择适应度比较高的两个个体，进行随机交叉，产生新一代个体，然后在子女个体中根 据概率进行变异操作。 ( 4 ) 在所有的迭代结果中，选择最好的结果作为遗传程序设计的解。 根据遗传规划的基本思想，遗传程序设计的一次运行并不能保证能够得到问题的解，如何确 定控制参数才使遗传程序设计达到最佳效果，这与所给问题环境有关，通常经多次反复实验而定。 图l 是g p 的流程图，图中n 表示群体中的个体数，变量i 表示一个个体，变量g e n 是当前代的 代号 6 基于遗传规划的多类分类技术研究 i l 产生初始群体 入 是否满足 y 停止规则 0 n1r g c r 产g 。n + l 计算个体的适应度值显示结果 j 上上 l t ；o i【 结束 l y 人 丫 按概率选择父母个体 士 执行交叉操作 + 按概率选择子女个体 + 执行变异操作 + f 件l 田1g p 计算基本漉程 f i g1g 础p r o g r a m m i n gf l o w c h a r t 7 河北农业大学硕士学位( 毕业) 论文 2 2 2 遗传规划的特点 遗传规划是在遗传算法的基础上发展起来的全局搜索算法，但它克服了一些遗传算法的缺 陷与遗传算法有一定的区别，主要表现在以下几个方面 3 0 , 3 q ： ( 1 ) 由于遗传算法直接对定长字符串进行操作，所以不能描述层次的问题。而遗传规划个 体的树形表达方式则弥补了这一点。 ( 2 ) 遗传算法定长的字符串描述方法不具备动态可变性，每一种结构仅适用于某类问题的 求解。而遗传规划的程序结构不再考虑等位基因的位置，这带来了极大的灵活性，具有动态改变 大小、形状的能力。 遗传规划注重解的适应性，其主要特点 3 2 3 4 ： ( i ) 自适应性白适应性主要是指在计算过程中所获得的可用信息被作为引导搜索路径走向 的因素并据此对算法加以某种调整，以增强其求解问题的能力。 ( 2 ) 逼近晟优性遗传规划在从搜索开始到当前时刻为之所积累的信息的基础上，以逼近最 佳方式对搜索空间的未来轨迹加以定位。 ( 3 ) 求解的动态性遗传规划是以动态的方式寻找并确定解的结构。解的结构和形态作为求 解方法所提供答案的一部分，亦非监督学习来获得，而不是被预先给定较强的约束和限制，并且 不依赖于问题相关的先验知识。 ( 4 ) 空间搜索特性遗传规划以随机搜索方式，形成了空间演化轨迹，由于随机机制的引入， 使得遗传程序的搜索可能避免神经网络中梯度下降法调整权值的那些缺陷，从整体上进行结构的 随机结合，使得结构获得逼近最优效果 2 2 3 遗传规划的结构 遗传规划算法中每一代群体的个体均采用一种动态的树状结构。树的结点由叶结点和函数集 组成。叶结点由输入变量与常量组成，而函数集用 于将叶结点连接起来，形成一个表达式，每代表达 式即为向量的一个潜在解。函数集可以由算数运算 符( + ，) 、数学函数、布尔运算符、条件运 算符等构成。在树状结构中，函数集表现为树的根 结点和内部结点树的层和结点都是可以变化的p ”。 图2 是一个函数计算程序的树状结构的例子。事实 上，每个树状结构对应着一个计算机程序。叶结点 中的变量相当于计算机程序的输入变量，而树结构 所代表的表达式的值即为计算机程序的输出值。 2 2 4 个体的描述方法 b 田2 ( ( k - 2 ) + 呻) 3 5 6 7 8 ) 的树状结构 f i g2 a p a r s ef r e eo f ( ( x - 2 ) + c o s ( y ) 3 5 6 7 8 ) 在遗传规划中，首先要解决的问题是如何用一系列可行的函数对个体进行描述，而这种函数 基于遗传规划的多类分类技术研究 能反复地由n 个函数f = ( f l ，位，丘i ) 和m 个终止符t = ( t l , t 2 ，t m ) 组合而成，函数集f 中每个特定的函数的参数a r g ( ) 也不一定相同i ”9 】。 一般来说，在遗传规划中，将问题的输入部分用终止符( 值) 进行抽象，而用操作符( 函数) 来模拟将对输入进行的处理，输出即为优化结果方法。这样，终止符集与函数集一起就构成解决 问题的一个完备方案。遗传规划的每个个体都是不同终止符和函数的组合，实际上就是一个待选 方案。 2 2 5 初始群体的生成 执行遗传规划的第一步是初始化群体，意味着生成各种各样的以备进化的程序结构，对于不 同类型的结构初始过程也不同。一个遗传程序运行的主要参数是一个程序所允许的最大规模。对 遗传程序中的树来说，此参数可作为树的最大深度或其最大的结点个数。下面介绍初始群体的生 成。 1 初始个体生成原理【8 ，o “4 】 初始群体是遗传规划迭代的起点，由众多独立的个体组成。初始个体为所要求解的问题的各 种可能的符号表达式( 算法树) ，它通过随机方法产生。 开始时，在函数集f 中按均匀分布随机地选出一个函数作为算法树的根结点。为了生成一个 层次化的复杂结构把根结点的选择限制在函数集f ，相反，若从终止符集中选取根结点，则生 成只有一个终止符集的退化结构。图3 ( a ) 描述了函数。+ ”为根结点的算法树，函数“+ ”是随 机地从函数集f 中选出的。一般情况下，从函数集f 中选出的函数f - 如果有a t g ( d 个变量，那么 就要从结点发出a r g ( f ) 条线。然后，对于每条从结点发出的线，从函数集f 和终止符集t 的并集 c = f u t 中再按均匀分布随机地选出一个元素作为该条线的尾结点。如果此时选出的是一个函数， 则重复执行上述过程。例如，若函数。”从并集中被选出，则函数”将作为非根内结点，如 图3 ( b ) 中的点2 所示。由于函数q ”具有两个自变量，则从结点函数o ”发出的两条线的尾 结点，则该分支上的树就终止生长。例如，在图3 ( c ) 中，恰巧终止符a ，b ，c 分别从并集c 中被选出，并作为树中各分支的尾结点，这时整个算法树生成过程终止。 上述过程从上到下，从左到右不断重复，直到一棵结点带标号的、分支有序的树生成为止。 田3 算法树生成过程 f i 9 3t h e i x o g r e s s o f a 砰m 嘛 ( c ) 9 河北农业大学硕士学位( 毕业) 论文 2 初始个体生成的几种方法【8 9 1 8 目 初始随机树的生成有多种。初始群体中的树应有不同的大小和形状。常用的方法有三种，即 完全法，生长法和混合法。 ( 1 ) 完全法( f u l l ) ：用完全法产生的初始个体，每一个叶子的深度都等于给定的最大深度 其实现方法是：若待定结点的深度小于给定的最大深度。则该结点的选择将限制在函数集内，若 待定结点的深度等于给定的最大深度，则该结点仅从终止符集内选取。如此产生的个体树都是平 衡的满二叉树，个体的结构形态比较单一，而且一旦规定初始树深度，则个体的结点数较大，达 到最大结点数n = 2 h - 1 ( 在函数都为二目操作符时) 。显然，这种方法增大了有用基因出现的概 率，但同时将大量引入冗余的基因。 ( 2 ) 生长法( g r o w ) ：用生长法产生的初始个体具有不同的形态，每一叶子的深度不一定 都等于给定的最大深度。其实现方法是：若待定结点的深度小于给定的最大深度，则该结点的选 择将限制在函数集与终止符集组成的并集内；若待定结点的深度等于给定的最大深度，则该结点 仅从终止符集内选取。一般来说，此法并不规定个体树的最大深度，各结点的选择仅根据父结点 的要求而产生，不受附加条件限制。但是生长产生的个体树形多变，结构极不平衡。如果不加限 制，树的深度可能会相差悬殊，甚至出现一些体形异常庞大的树，而大量叶结点为空的个体，不 利于计算机存储浪费大量存储空间和计算时间。 ( 3 ) 混合法( r a m p e dh a l f a n d h a l f ) ：生长法与完全法各有利弊。在一定的初始深度限制下， 完全法产生的个体包含的基因数多，而个体形态单调，甚至会出现雷同个体；生长法产生的个体 形态多变，但基因数相对较少，优良基因出现的几率相应减少。如果在初始群体中单用某一种方 法产生所有个体显然不利于群体的进化。混合法是完全法和生长法的综合，可以折中两种方法 的优点。混合法随机选用生长法或完全法生成具体的初始个体，以达到既保证群体中基因数量， 又增加个体多样性的目的。实际应用中可以规定一定比例的个体用生长法产生，剩下的则采用完 全法，针对某一特定个体，生成方法是随机的。 2 2 6 遗传规划的适应度评价方法 遗传规划既不是一个爬山系统也不穷举所有可能的计算机程序空间。它是一种束搜索( b e a m s e a r c h ) ，束是g p 群体。当然g p 必须选择群体中的成员进行诸如交叉、变异、复制等操作 g p 的评价尺度为适应性函数，它与问题有关j 适应性是g p 中自然选择的驱动力，利用适应性来 控制群体中结构改变的过程。仿照自然界适者生存优胜劣汰的原理，可用其适应度函数值表达个 体对环境的适应程度及繁衍到下一代的可能性。在设计数学算法的时候，适应度函数可以表述为 个体的一个属性。表示其竞争能力适应度函数值的大小描述这个个体的优劣程度，它取决于程 序的目标函数。在程序进化的任何一代群体进入下一代的过程中，适应度函数用来评价所有个体 的性质，决定哪些个体被复制进入下一代的进化，哪些被淘汰。同时，如果采用的选择机制是按 比例复制那么个体的适应度函数与群体中其它所有的个体相比较，决定它被复制，进入下一代 进化的数量。所以，适应度函数对问题的解决有决定性的意义。 常见的适应性测度有下列四种 e 9 , 1 5 4 5 ：原始适应度，标准适应度，调整适应度，归一化适应 度 1 0 基于遗传规划的多类分类技术研究 ( 1 ) 原始适应度( f a w f i m e s s ) 原始适应度是问题适应性自然描述的一种度量。当原始适应度定义为误差时也就是在一 组适应度计算实例中，个体返回值与实测值之间的距离之总和。如果符号表达式是整数或浮点型， 那么距离之和表现为符号表达式的返回值与实测值之间的距离