（计算机软件与理论专业论文）自动程序设计方法研究及其在多类模式分类中的应用.pdf

东华大学学位论文原创性声明 本人郑重声明：我恪守学术道德，崇尚严谨学风。所呈交的学位论文，是本人在导师的 指导下，独立进行研究工作所取得的成果。除文中已明确注明和引用的内容外，本论文不包 含任何其他个人或集体已经发表或撰写过的作品及成果的内容。论文为本人亲自撰写，我对 所写的内容负责，并完全意识到本声明的法律结果由本人承担。 学位论文作者躲j 和蹲彳 日期：_ ，a 厂年月o 日 东华大学学位论文版权使用授权书 学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家 有关部门或机构送交论文的复印件和电子版，允许论文被查阅或借阅。本人授权东华大学可 以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等 复制手段保存和汇编本学位论文。 保密e 五在 1 年解密后适用本版权书。 本学位论文属于 不保密口。 学位论文作者签名 j 榉午 日期：厂年f 月f e t 指导教师签名 了嚏享， 日期：b ，年月1 1e t 自动程序设计方法研究及其在多类模式分类中的应用 自动程序设计方法研究及其在多类模式分类中的应用 摘要 人工智能和机器学习的共同目标是让计算机在没有明确的程 序指导下解决问题，因此在过去的几十年里，有关计算机代码的人 工演化是一项迅猛发展的技术，各相关领域的人们都期望能有一种 自动化系统，将针对问题的细致描述( 用数据结构、函数等相对简 单的表达方式) 作为输入，然后就能得到满意的解决方案。自动程 序设计( a p ) 就是实现这种自动化系统的技术。现有的主要方法包 括：遗传程序设计( g p ) ，交叉爬山程序设计( x o h c ) ，交叉模拟退火 程序设计( x o s a ) 。 本文借鉴微粒群算法( p s o ) 中种群参考的思想，对交叉爬山程 序设计进行改进，提出基于种群参考的交叉爬山程序设计 ( s x o h c ) ：在交叉爬山程序设计种群进化的同时加入与种群的历史 最优解交叉的操作，以使个体在进化过程中得到种群中有利的进化 信息从而提高搜索能力，并在一定程度上避免个体早熟现象。同样 本文把种群参考的思想结合到交叉模拟退火程序设计中，提出基于 种群参考的交叉模拟退火程序设计( s x o s a ) ，实验证明此方法提高 了交叉模拟退火程序设计的优化能力。 另外，本文利用微粒群算法来优化自动程序设计进化过程中的 常量节点，提出基于p s o 参数估计的自动程序设计方法，提高解的 自动程序设计方法研究及其在多类模式分类中的庶用 精度，避免由于常量节点的值不合适而导致好的解结构被淘汰的现 象。 k o z a 矛o 用遗传程序设计成功解决两类模式分类问题，当程序 返回非负数时输入样本属于一类，记类1 ，否则属于另一类，记类 一1 。k i s h o r e 把n 类模式分类问题分解成n 个两类分类问题，需要求n 个分类表达式。第i 个分类表达式判定第i 类，属于第i 类的样本属于 类1 ，不属于第i 类的所有样本属于类一1 。它的缺点是随着类别数目 的增加，训练时间会增加地很快。本文提出一种用自动程序设计解 决多类模式分类问题的直接方法，此方法只要求一个分类表达式， 利用分类表达式的不同输出值来区分不同的类。对于n 类模式分类 问题，记第0 ，1 ，2 ，n 1 类，那我们就用自动程序设计方法进化分 类表达式使之对于第i 类样本的特征属性输入，输出值为i 。这样我 们就可以直接根据分类表达式的输出值预测样本的类别了。而且本 文提出相应于此多类模式分类方法的一种应用较广的函数集和终 点集方案，并用基于种群参考的交叉爬山程序设计( s x 0 h c ) 来实 现，对u c id a t a b a s e 的n e w t h y r o i d 数据进行实验，结果表明此方法 是可行的。 关键词：自动程序设计，交叉爬山程序设计，交叉模拟退火程 序设计，遗传程序设计，种群参考，多类模式分类 自动程序设计方法研究及其在多类模式分类中的应用 r e s e a r c h0 na u t o m a t i cp r o g r a m m i n g a p p r o a c h e sa n dt h e i ra p p l i c a t l 0 ni n m u i j i c a t e g o r yp a t t e r n c l a ss i f i c a t l 0 n a b s t r a c t t h ec o m m o ng o a lo fa r t i f i c i a li n t e l l i g e n c ea n dm a c h i n el e a r n i n gi s t ol e t c o m p u t e rl e a r n t os o l v e p r o b l e m sw i t h o u tb e i n ge x p l i c i t l y p r o g r a m m e d s o i nt h e p a s t d e c a d e sc o d ee v o l u t i o n t e c h n i q u e d e v e l o p e dv e r yf a s t p e o p l ei nt h er e l a t i v ea r e a sa l lw a n ta na u t o m a t i c s y s t e mt h a tc a ny i e l das a t i s f a c t o r ys o l u t i o nw h i l ei ti sg i v e na si n p u t s o m ed e t a i l e dd e s c r i p t i o n so fap r o b l e m ，s u c ha sd a t as t r u c t u r e sa n d f u n c t i o n s a u t o m a t i cp r o g r a m m i n g ( a p ) i st h et e c h n i q u et oi m p l e m e n t t h ea u t o m a t i cs y s t e m n o w a d a y st h e r ea r et h r e em a jo ra p p r o a c h e s g e n e t i c p r o g r a m m i n g ( g p ) ， c r o s s o v e r h i l l c l i m b i n g ( x o h c ) ， c r o s s o v e rs i m u l a t e da n n e a l i n g ( x o s a ) i nt h i sp a p e r ，w eu s et h et h o u g h to fs w a r mr e f e r e n c eo fp a r t i c l e s w a r mo p t i m i z a t i o n ( p s o ) t oi m p r o v ex o h c ，a n dp r o p o s es w a r m r e f e r e n c eb a s e dx o h c ( s x o h c ) t h em a i ni d e ai st oa d dc r o s s o v e r o p e r a t i o nw i t ht h eh i s t o r i c a lb e s ts o l u t i o no ft h ew h o l es w a r mw h i l e e v e r yi n d i v i d u a le v o l v e su s i n gx o h c ，b yw h i c hi n d i v i d u a l sc a ng e t i n s t r u c t i v ee v o l u t i o ni n f o r m a t i o na n de n h a n c et h e i rs e a r c h i n ga b i l i t i e s 3 自动程序设计方法研究及其在多类模式分类中的应用 a n da v o i dp r e m a t u r ec o n v e r g e n c ep h e n o m e n at os o m ee x t e n d w eu s e t h es a m et h o u g h tt o i m p r o v ex o s aa n dp r o p o s es w a r mr e f e r e n c e b a s e d x o s a ( s x o s a ) e x p e r i m e n t s s h o wt h a tt h e i m p r o v e m e n t e n h a n c e st h eo p t i m i z a t i o na b i l i t i e so fx o h ca n dx o s a t h e nw ep r o p o s ep s op a r a m e t r i ce s t i m a t eb a s e da u t o m a t i c p r o g r a m m i n ga p p r o a c h ，i nw h i c hw eu s ep s oa l g o r i t h mt oo p t i m i z e c o n s t a n t p a r a m e t e r s o fi n d i v i d u a l s d u r i n g e v o l u t i o nt o g e tm o r e a c c u r a t es o l u t i o n sa n da v o i dt h a tg o o ds o l u t i o ns t r u c t u r e sa r ed i s c a r d e d w h i l et h e i rp a r a m e t e r sa r eb a d k o z au s e sg e n e t i cp r o g r a m m i n gt os o l v et w o - c a t e g o r y ( c l a s s ) p a t t e r nc l a s s i f i c a t i o np r o b l e m ，i nw h i c hi ft h ep r o g r a mr e t u r n sav a l u e 兰0 ，t h eg i v e ni n p u ts a m p l ei sa s s i g n e dt oo n ec l a s s ，d e n o t e da sc l a s s1 ， o ri ti s a s s i g n e dt o t h eo t h e r , d e n o t e da sc l a s s - 1 k i s h o r et r e a t s n c a t e g o r y c l a s s i f i c a t i o n p r o b l e ma s nt w o - c a t e g o r yc l a s s i f i c a t i o n p r o b l e m t h a tm e a n si tn e e d s t oe v o l v enc l a s s i f i e re x p r e s s i o n s ( g p c e ) f o ra n c a t e g o r yp r o b l e ma n de a c hg p c ei s t r a i n e dt or e c o g n i z e s a m p l e sb e l o n g i n gt o i t so w nc l a s sa n dr e j e c ts a m p l e sb e l o n g i n gt o o t h e rc l a s s e s i t sb a s i cd r a w b a c ki st h a tt h et r a i n i n gt i m ew i l li n c r e a s e q u i c k l yw h i l et h en u m b e ro fc a t e g o r yi n c r e a s e s i nt h i sp a p e r , w e p r o p o s ea na p p r o a c ht h a tu s e sa u t o m a t i cp r o g r a m m i n gt od i r e c t l ys o l v e t h em u l t i c a t e g o r y p r o b l e ma n dn e e d se v o l v i n go n l y o n ec l a s s i f i e r e x p r e s s i o n ( a p c e ) f o ran c a t e g o r yc l a s s i f i c a t i o np r o b l e m ，w en a m e 4 自动程序设计方法研究及其在多类模式分类中的廊用 t h ec l a s s e sa sc l a s s0 ，c l a s s1 ，c l a s s2 ，c l a s sn 一1 ，a n dt h e nu s e a u t o m a t i cp r o g r a m m i n gt e c h n i q u et ot r a i no n ea p c ew h i c hr e t u r n si w h i l et h eg i v e ni n p u ts a m p l eb e l o n g st oc l a s si t h e nw ec a nu s et h i s a p c et op r e d i c ts a m p l e s c l a s sa c c o r d i n gt ot h e i ro u t p u t w ep r o p o s ea f u n c t i o ns e ta n dt e r m i n a ls e t ，w h i c hc a nb eu s e dw i d e l y , f o rt h i s m u l t i c a t e g o r yc l a s s i f i c a t i o na p p r o a c ha n du s es x o h c t oi m p l e m e n ti t w et e s ti tw i t ht h en e w t h y r o i dd a t ao fu c id a t a b a s ea n dr e s u l t ss h o w i tw o r k sw e l l 基i i 乜i 旦g ( c o m p u t e rs o f t w a r ea n dt h e o r y ) s u p e r v i s e db y 旦i 旦g 基i 垦q 亟q 旦g ，l ! i 垒j i 坠 k e yw o r d s ：a u t o m a t i cp r o g r a m m i n g ，c r o s s o v e rh i l lc l i m b i n g ， c r o s s o v e rs i m u l a t e da n n e a l i n g ，g e n e t i cp r o g r a m m i n g ，s w a r mr e f e r e n c e ， m u l t i c a t e g o r yp a t t e r nc l a s s i f i c a t i o n 5 自动程序设计方法研究及其在多类模式分类中的应用 第一章绪论 1 1 自动程序设计的发展现状 人工智能和机器学习的共同目标是让计算机在没有明确的程序指导下解 决问题，因此在过去的几十年里，有关计算机代码的人工演化是一项迅猛发展 的技术，各相关领域的人们都期望能有一种自动化系统，将针对问题的细致描 述( 用数据结构、函数等相对简单的表达方式) 作为输入，然后就能得到满意 的解决方案。k o z a 1 】在1 9 9 2 年提出遗传程序设计( g p ) 方法，利用层次化的 计算机程序( 一般为树结构) 来表达解决问题的方案( 解) ，而解决问题的最 佳方案( 最优解) 可以借助遗传算法( g a ) 的思想通过不断演化寻得。g p 对解决自动程序设计( 自动编程系统) 虽尚显稚幼，但它的确开创了新思路， 从长远看来，它对计算机程序自动设计的发展有着革命性的作用。由于像g p 这样的自动程序设计方法的个体表示不拘于某种特定的形式，具有很强的表达 能力，所以他们可应用于多个领域：系统建模吧符号回归1 , 1 6 ，分类2 ，3 1 ，算法设 计 2 l 】，常微分方程组的演化建模，轮机实时仿真，数据挖掘吲。 o r e i l l y 等人【3 j 在1 9 9 5 年提出了交叉爬山程序设计( c r o s s o v e rh i l l c l i m b i n g ，x o h c ) 和交叉模拟退火程序设计( c r o s s o v e rs i m u l a t e d a n n e a l i n g ，x o s a ) 两种自动程序设计方法。这两种方法的基本思想是：通过g p 的交叉算子产生邻域解，以爬山算法和模拟退火算法的准则来接受新解，不断 进化以搜索最优解。文献【3 】的实验证明交叉爬山程序设计比传统的遗传程序 设计搜索最优解更快，精度更高，但是交叉模拟退火程序设计则没有预想中效 果那么好。另外0 r e i l l y 还尝试将交叉爬山程序设计，交叉模拟退火程序设 计与遗传程序设计结合，实验证明搜索能力比单纯的遗传程序设计有所提高， 但是并不一定比单纯的交叉爬山程序设计好。 自动程序设计中个体的常量节点在种群初始化时生成，除了变异的时候可 能会改变之外就不会变了，但是如果常量节点的取值范围是连续的话，就很难 通过演化来得到合适的值，还会造成一些好的结构因为常量参数不合适而被淘 囊动穆_ 亭设计方法磅究爰其在多类模式分娄中越摩瘸 汰。曹宏庆【13 j 把遗传算法( g a ) 绪合到遗传程序设计中米优化个体中常量节点， 并得到比传统遗传程序设计更精确的解。卢奕南l 、s h a r m a n “1 等人阁模拟邋 火算法( s a a ) 采鼗继遗钱程序设诗个体黪豢量参数也季譬列较好懿薅。 模式分类是自动程序设计的一个重要应用领域。k o z k l l , 2 】利用遗传程序设 计f g 玲戒凌解决溪类分类阉题，当程彦返回 受鼗鼓输入襻本演予一类，记炎 1 ，否则属于另一类，记类一1 。k i s h o r e f 3 l 把n 类模式分类问题分解成n 个两类分 黉问题，需要求n 个分类表达式。第i 个分类表遮式( g p c e i ) 潮定第i 必，属于 第i 类的样本属于类1 ，不属于第i 类的所有样本燧于类一i 。 1 ，2 本文的研究内容 本文偌鉴微粒群算法( p s o ) 中融群参考的恩想，对交叉爬山程序设计进行 改进，提出基于种群参考的交叉爬山程序设计：在交叉爬山程序设计种群进化 熬嗣薅热入与耱瓣麴历史最糖翳交叉瓣臻 擘，叛经令 誊在送豫过程中缮弱耱癸 的有利谶化信息从而提高搜索能力，并在一定程度上避免个体早熟现象。同样 本文把释群参考鹃惑怒结合到交叉模叛退火程序设计中，提赉基于稀群参考豹 交叉模拟退火程序设计。 另外，本文利用微粒群算法来优化自动程序设计进化过程中的常艟节点， 提出基予p s o 参数估计豹自动程序设计方法，提高了解的精发，并露效避兔 由于常爨节点的值不合邋而导致好的解结构被淘汰的现象。 在瘦薅方瑟，本文援塞一耱翅鑫动疆彦设诗簿浃多炎模式分类闫遴兹壹接 方法，此方法只壤求一个分类表达式，利用分裟表达式的不同输出值米区分不 闰的类。对予n 类模式分类闻怒，记第0 ，l ，2 ，n 1 黉，那我稻就糟宣动稳 膨设计方法进化分类表达式使之对于第i 类样零的特征属性输入，输出值为i 。 这样我们就可以直接根据分类淡达式的输出值预测样本的类别了。而阻本文还 提出摆癍子蓝多类模式分类方法翡一季孛应羁较广魏丞数集稳终点集方案，著周 蕊于种群参考的交叉爬山程序设计( s x o h c ) 来实现，对u c id a t a b a s d 7 1 的 n e w t h y r o i d 数据避行实验，结聚表明魏方法趸胃行蕊。 9 叁动程房设诗方法磺究鼓蒸在多类搂戏劳类孛斡瘟露 1 3 本文豹文牵结构 蓦二搴，分缨垂动程序设谤最早瓣痿发式避耽方法遗转稷淳设谤 g p ) ， 北方法也是迄今海止应耀最广黪基动援廖设诗方法。 茧三牵，奔缓o r e i l l y 珏3 爨窭酶舅一耱童韵程亭竣诗方法一交叉蕊出程游 竣诗，并挺窭一耱基于耱群参考戆交叉爬由疆净浚计。( 取鑫颧士鬻瓣发表豹 攀术论文f l 】) 蓁秘章，分缁o r e i i l y 珏1 提氆豹又一静窦韵程彦设计方法交叉模叛逶火 稷序设计，并提出一种熬于种群参考的交叉模拟退火程序设计。 第点零，疆懋基于微粒群( p s o ) 参数毽毒 豹鸯裁程序设诗方法，帮在耱 鼗避化越过程中艨微粒瓣算法去侥化个体( 撼) 的鬻数节点。( 取鑫颓絮麟 发袭懿攀术论文【2 】) 第六章，提磁鼹鑫麓程痔竣诗褥鬟翡努类表达式翁不弱输蕊蓬亲囊接解决 弗类模式分类闷越的方泌。 第七章，慧缭与震鬻。 1 0 自动程序设计方法研究及其在多类模式分类中的应用 第二章遗传程序设计( g p ) 简介1 6 _ 3 2 1 遗传程序设计( g e n e t i cp r o g r a m m i n g ，以下简称g p ) 的思想是s t a n f o r d 大学 的j r k o z a 在2 0 世纪9 0 年代初提出的，他为自动程序设计开辟了先河，从 而引领自动程序设计在近十年来得到快速的发展和广泛的应用。遗传程序设计 与遗传算法的基本思想相似，但在求解程序的自适应进化模拟中发展了结构上 的复杂性。k o z a 所指的“程序”术语的背景来源于l i s p 语言编写程序的形式 特性。l i s p 语言中的s - 表达式突出表达了树结构的符号描述机制，l i s p 这种 人工智能语言本身是由符号表示方式的s 一表达式结构组成的，所以这里的“程 序”和“语句”具有某种同一性。“程序”的大小、形式和结构不是预先能够 确定的，而是在世代演化中动态地变化。 由于g p 采用一种更自然的表示方式，因而应用领域非常广，在解决人工 智能、机器学习、控制以及分子生物学等领域的问题中效果尤其显著。尽管目 前g p 的水平不足以产生出完善的程序，但其巨大的应用潜力已经受到许多学 者特别的关注 1 - 3 , 8 , 1 6 , 1 9 2 1 】。 2 1g p 的原理和方法 从广义问题求解的观点来看，人工智能、符号推理和机器学习中的许多方 法可被视为是旨在找出根据样本集就能产生合理信号集方案的某种计算机编 程过程。g p 是在可能空间中寻找合适的计算机程序的自适应探索算法。 g p 是在自然选择的基础上，在计算机时代才能实现的一种解题方法。其 基本思想是：随机产生一个适合于给定环境的初始群体，即问题的搜索空间， 与遗传算法类似，构成群体的个体都有一个适应度，依据达尔文适者生存原则， 用遗传算子处理得到高适应度的个体，产生下一代的群体，如此进化下去，直 到给定问题的解或近似解在某一代上出现。 作为g p 的重要特点之一，组成群体的个体采用一种动态的树状结构。描 述树的节点由终点( t e r m i n a l s ) 、原始函数( p r i m i t i v ef u n c t i o n s ) 组成。其中终点也 称为叶节点，是将问题分级划分为子问题后最基本的解的成分。这种树状的层 叁动稚_ 亭设毒 方法醑究及慕在多笺筷式分类孛熬藏焉 与节点均是可变化豹。终点是问题的原始变量，根节点秘中闻节点统称为内部 节点，是组合这魑原始变量的函数。它们很类似于l i s p 语言中的s 一表达式。这 样，每令分爱缝稳怼瘦凝题敬一令霹链释，逸可疆理鼹为求憋该超题鹣一令谤 算机程序。 2 1 1g p 的基本算法”。“1 g p 的基本算法如下： ( 1 ) 随机生成初始群体，其中个体是融表示阀题的函数和终点随机缀合而 成的计算机程序。 2 ) 镖繇执行下列各步壹型潢是终盘雄则为止： 运行群体中的每个计算机程序，并对其赋予适应度； 运行下瑟瑟令主要操俸产生耨豹诗算辊稷痔群体： i ) 从当前代群体中依其适应度随机选定个体复制到新一代群体中( 适 应度越好越容翳被选中) 。 i o n 概率p c 选中霈交叉的个体，然后随机选定双亲个体部位进孝子交叉 操作产生新个体。 i i i ) 班壤率p m 选中露变异豹令# ，然螽夔樵选定令钵部德送行交异操蠓 产生新个体。 ( 3 ) 孺上述遴纯过程中得到静袋簿计辫枫程序作为运行静蘩莱，它可能是 一个正确( 或近似) 的问题答案。 从上述算法可以看出g p 的本质是运用g a 的恩怨，通过迸化可执行程序来 鼹决闯题。g p 的主要特点在于它是可交长的、层次化的、豢常是撼结构豹遗 传材料，而且大多数情况下，程序个体怒可执行的。也就是说常常通过某类解 释器簿释狴痔，激获餐个俸魏逶笾度译馀。嚣予传统g a 来谖，令咎逶露是定 长的位串绒字符串而且个体的适应度评价由其结构和所要解决的问题米确定。 g p 的箨法设诗需要礤先确定六个闷熬，包括定义拐始函数粲f 、定义终点 集t 、适成度的评价方法、确定遗传操作的控制参数、初始个体的产生方法和 终止运行的条件，其中遗传操作、适应鹰评价和初始个体的产奠三是算法设计的 关键掰在。 1 2 自动程序设计方法研究及其在多类模式分类中的应用 2 2g p 的遗传操作 g p 遗传操作除了包括基本的选择( s e l e c t i o n ) 、交叉( c r o s s o v e r ) 和变异 f m u t a t i o n ) c ，b ，还可以引入一些次级操作来更多地反映遗传程序结构的变化。 其中选择的原理跟遗传算法g a 一样。 2 2 1 交叉操作 交叉以如下的方式创造出两个新个体。从当前群体中，根据适应度挑选两 个个体，即父个体。两个父个体的不同部件( 如子树、子程序、子路径、子公 式等) 重新组合产生两个子个体。例如，考虑下面计算机程序( 用l i s p 语言表 示1 ： ( + ( + 0 2 3 4 z ) ( 一x 0 7 6 8 ) ) 它表示o 2 3 4 z + x 一0 7 6 8 ，同样考虑第二个程序： ( + ( + zy ) ( + y ( + 0 31 4 z ) ) 它表示z y ( y + o 3 1 4 z ) 。如图2 - 1 所示，将两个父个体表示为带标号的树，内部 节点对应于( + 、- 、+ 、) 终点( 叶节点) 对应于数据。 交叉操作通过交换两棵树的子树产生后代，被交换的两棵子树是被随机 选择的。例如第一棵树的节点2 被随机的选择作为第一个父个体的交叉点，第 二棵树的节点5 被随机选择作为第二个父个体的交叉点，两个被交换部分是以 这两个交叉点为根的子树。剩余体( r e m a i n d e r ) 为父个体去掉交换部分后的剩余 部分。第一个新个体是把第二个父个体的交换部分插入在第一个父个体的剩余 体的交叉点上得到的树；第二个新个体是把第一个父个体的交换部分插入在第 二个父个体的剩余体的交叉点上得到的树。两个新个体如图2 所示，分别是： ( + ( + y ( + o 3 14 z ) ) ( - x o 7 6 8 ) ) ； ( + ( 4z y ) ( + 0 2 3 4 z ) ) 交叉操作满足终点集封闭性原则，总是生成合理的下一代个体。由于父个 体是基于适应度挑选出来的，它在解决给定问题时有一定的效果，它们的部件 重新组合产生新一代个体，可能更适合于所给问题。 自动程序设计方法研究及其在多类模式分类中的应用 ( + o 2 3 4 z ) ( 一x ot 6 8 ) ) o “z 7 ) ( + 7 ( o 3 1 4 ： ) ) ) ：02 3 4 z + = 一07 6 8 ：z 7 ( 7 + 0 3 t 4 z ) a b 图2 - i 交叉前的两个父个体 ( + ( + 7 ( 0 3 1 4 0 ) ( - x o 7 6 8 ) ) ( ( 十z 7 ) ( o z 3 4 z ) ) ：0 3 1 4 7 z + z 一0 7 6 8：8 2 3 4 z z 7 2 2 2 变异操作 图2 - 2 交叉后的两个子个体 变异操作用在g p 中的基本做法是：由程序随机产生一个新的子树，以代 替被突变概率选中节点以下的原有子树部分。除了基本变异操作外，还可以采 用一种收缩变异操作，其方法是随机选择一个中间节点，将该节点以下的子树 部分移到其上一个节点位置，同时删除上一节点的其它子树。 2 2 3 次级操作 g p 中经常应用两种次级操作：一种是化简操作，它将复杂的结构对应的 s 一表达式做适当的简化，例如，( ( ( 3 + x ) + ( 2 1 ) ) + e x p ( x 一( 3 + 2 ) ) ) 可简化为 ( ( 3 + + ) + e x p ( x 一6 ) ) ；另一种是封装( e n c a p s u l a t i o n ) 操作，它将进化中出现频次较 1 4 自动程序设计力法研究及其在多类模式分类中的应用 多的于树封装为用户定义函数，并给它冠名，加入到函数集中备用。它可以比 喻- n 0 无性繁殖方式，用于培养好的基因积木块。 2 24 个体大小限制” 由于个体在进化的过程中结构大小不断变化，可能变得很大，通过控制个 体的结构的大小可以控制进化时间，文献 2 6 实验还表明结构小的个体更容易 进化出最优解。个体结构大小的控制方法有：树深控制，节点数控制。 2 3 适应度评价 个体适应度是通过运行试例集而获得的对个体质量的一种测量，对它的评 价会占用较大的计算资源，因此正确地选择评价函数和试例集对解决问题来说 是很关键的。其中最简单的方法是使用固定的试例集，即全部训练集。例如求 解曲线拟合问题，设要拟合的函数为v 0 ( x ) ，个体对应的程序为f ( x ) ，取n 个 训练样本点x i ，i = 0 ，1 ，n 1 ，则适应度可取其残差平方和： f i t n e s s ( f ) = n - 1 ( f ( z ，) 一f 0 ( x ，) ) 2 ( 2 1 ) 2 4 初始遗传程序的生成 初始遗传程序的生成过程一般从根节点开始，从原始函数集中随机选择一 个作为根节点，然后根据其变量数或操作符数目产生同样数目的子节点，然后 在每个子节点做下一层的继续展开，直到所有树分支到达终点，最终形成一个 分层树状结构，代表一个初始遗传程序。 k o z a 将遗传程序生成方法按其大小和形式分为以下四种：完全生成法 ( f u l l c r e a t i o nm e t h o d ) 、生长法( g r o wc r e a t i o nm e t h o d ) 、斜坡生成法( r a m p e d c r e a t i o nm e t h o d ) 和斜坡对半生成法( r a m p e dh a l f - a n d h a l f c r e a t i o nm e t h o d ) 。其 中斜坡生成法将最大生成深度作为种群的一种参数处理。例如，取 2 ，6 区间 数。当产生5 0 个个体的种群时，先产生最大深度为2 的1 0 个个体，然后产生 最大深度为3 的1 0 个个体，依次类推，最后产生最大深度为6 的1 0 个个体， 这样种群中的个体结构大小呈均匀分布。斜坡生成法在实际生成遗传程序时可 皇动稚痔设亡 方法研究及藏在多娄模式分类孛豹盛用 致地逸撵完全生成法线生长法。斜坡对半生戏法与斜坡生成法不弱黪是，在 生成每个遗传程序时可以随机地选择采用完全生成法戏生长法。k o z a 认为这 耱方法最佳，霹戳产生扶大4 , n 澎式鸷有穰多变诧憨黪群。 自动程序设计方法研究及扎在多类模式分类中的应用 3 1 引言 第三章基于种群参考的交叉爬山程序设计 o r e i l l y 等人 i5 】在1 9 9 5 年提出交叉爬山程序设计( c r o s s o v e rh i l lc l i m b i n g x o h c ) ，它的基本思想是：通过遗传程序设计的交叉操作产生邻域解( 计算机 程序) ，以爬山法作为新解的接受准则来搜索最优解。文献 1 3 ，1 5 的实验证明 交叉爬山程序设计比传统的遗传程序设计更快搜索到最优解，精度更高。然而 由于它本质上是一种单点局部搜索算法，可能陷入局部最优。为此本文借鉴微 粒群算法中的种群参考的思想 1 2 ，提出基于种群参考的交叉爬山程序设计 ( s x o h c ) 以提高搜索到全局最优解的概率。另外，本文还提出计算机程序个 体的松紧邻域解概念，扩充x o h c 的邻域解概念，在进化初期使用松邻域解 搜索以扩大搜索范围，得到较好初期解。 3 2 交叉爬山程序设计( x o h c ) 简介”5 交叉爬山程序设计先根据问题的所选取的函数集和终点集随机生成一个 树型的程序个体作为初始解，然后以这个初始解作为当前解出发进行搜索，随 机生成一个新解( 新个体) 作为配偶解，当前解与配偶解交叉产生邻域解，如 果邻域解比当前解好的话，接受邻域解为当前解，否则当前解不变。下一次搜 索同样随机产生一个新配偶解做交叉搜索。不过对于一个新的配偶解x o h c 不只是利用一次，当当前解与其交叉没有产生更优的个体的话，重新随机选择 当前解和配偶解的交叉点再做一次交叉，直到找到更优的解或者达到一定的交 叉次数( m a t ex ot r i e sl i m i t ) 。由于这样是单点的搜索方法，且运用了爬山 法的思想，所以可能得到的只是局部的最优解，为了解决这个问题o r e i l l y 利用多次搜索的方法，即记录从一个初始解出发搜索过程中交叉操作的次数， 如果达到一定的次数( x ot r i e sl i m i t ) ，就重新随机产生新的初始解进行搜索， 最后取整个搜索过程中的最优解( 全局最优解) 作为结果输出。 自动程序设计方法研究及其在多樊模式分类中的应用 3 2 1 算法步骤 交叉爬山程序设计的解空间表示方法跟传统的遗传程序设计方法一样采 用树型结构来表示，所以我们这里讨论的解是表示解决问题的程序( 树) ，具 体的步骤如下： ( 1 ) 在解空间里随机选取一个初始解作为当前解s o l u t i o nc u r r e n t 。置当前解交 叉计数x ot r i e s = o ； ( 2 ) 随机产生一个新s o l u t i o n _ d o n o r ，置配偶交叉计数m a t e x o t r i e s = o 。 ( 3 ) 按照遗传程序设计的交叉算子，把当前解s o l u t i o n _ c u r r e n t 和新解进行交叉， 把当前解的交叉后代作为邻域解s o l u t i o nc a n d i t a t e 。m a t ex ot r i e s 增1 ， x ot r i e s 增l 。 ( 4 ) 如果邻域解比当前解差，j j m a t e x o t r i e s m a t e x o t r i e s l i m i t ( 预设参数) ， 当前解和新解保持不变，转( 3 ) ，否则转( 5 ) 。 ( 5 ) 如果邻域解比当前解s o l u t i o n _ c u r r e n t 好，用邻域解替代当前解，否则当前解 不变。如果x o _ t r i e s m a t ex ot r i e s _ c h a n g e o o s + g e n e r a t i o n 、 0 m a t e x o t r i e s c h a n g ep o s 1 m a t e x o t r i e s l i m i t ：2n e w _ m a t ex ot r i e s l i m i t ； 随机生成树深为w _ d e p t h 的新配偶解m a t e ； i f ( g t i g h t _ c r o s s _ p o s + g e n e r a t i o n )，o t i g h t _ c r o s s _ p o s l( + 1 ) p i 】与m a t e 不断交叉直到得到更好的松邻域解或交叉次数达到 m a t e x o t r i e s l i m i t 次； i f ( 得到更好的松邻域解) 用此松邻域解替换p i ； e l s e ( + 2 ) p 【i 】与m a t e 不断交叉直到得到更好的紧邻域解或交叉次数达到 m a t ex ot r i e s _ l i m i t 次： i f ( 得到更好的紧邻域解) 用此紧邻域解替换p i ； r = r a n d ( ) ； 取 o ，1 】区间上的随机数。 i f ( r p g _ x o a g r o b i l i t y )0 p g x o _ _ p r o b i l i t y l( + 3 ) p 啪与p g 不断交叉直到得到更好的紧邻域解或交叉次数到达 m a t e x o t r i e s l i m i t 次； i f ( 得到更好的紧邻域解) 用此紧邻域解替换p i 】； i f ( f i t n e s s ( p i ) f i t n e s s ( p g ) ) 重置全局最优解； e n d g ：= g + 1 ； u n t i l 满足结束条件( 1 ) ； 将p ( g ) 中的最佳个体作为系统的输出； 自动程序设计方法研究及其在多类模式分类中的应用 注意：算法中适应度以小为好；如果邻域解的节点数超过m a x g e n n u m 的话 此解被抛弃；( + 3 ) 中p i 】与p g j 新t 交叉时只是取p g 的一个拷贝，p g 本身保持不 变。 3 3 3 算法解析 本算法在开始的时候( + 1 ) ，则g m a t ex ot r i e s _ _ c h a n g e a ) o s4 9 e n e r a t i o n 时，增大与新解的交叉次数限制是为了 提高搜索能力，避免早熟。而此算法的关键一步( + 3 ) 就是在个体以爬山法每进 化一代之后以一定的概率p g _ x o _ p r o b i l i t y 与种群当前的最优解p g 进行交叉， 从而使个体在进化过程中从种群中获得指导性的参考信息，以提高搜索到最优 解的速度和概率，并避免早熟现象。 3 4 实验 自动程序设计的一个重要应用是解决符号回归( s y m b o l i cr e g r e s s i o n ) 问题， 则预先给定样本数据序列，或者按预定的函数取样计算一个样本序列，用自动 程序设计来获得一些好的程序( 函数) ，从而用发现的函数近似这些样本序列 【16 下面我们用s x o h c 程序设计方法对f = s i n ( x ) ，x 【o ，2 进行多项式拟合。则 运算符集为 + ，一，+ ，终点集为 x ，r n d c o n s t ，其r n d c o n s t 表示常量，这里 我们取 一1 ，1 之间的随机实数。取【o ，2 】区间上的5 0 个测试样本点，x i = i 2 5 0 ， i = l ，2 5 0 。设s x o h c 程序设计求得的拟合函数为f ( x ) ，取适应度为： f i t n e s s = 竺。 f ( x 。) - s i n ( x ；) l ( 3 1 ) 初始化种群采用斜坡生成法，取初始化树深为4 ，5 ，6 。其它参数如下： p o p s i z e = 5 0 ； g e n e r a t i o n = 5 0 0 ； w _ d e p t h = 3 ： 自础程序设计方法研究髓蕻往多类模式分类中的应甩 m a t e x o t r i e s _ l i m i t 。5 ； m a t ex ot r i e s _ c h a n g e _ p o s 2 0 7 ： n e w m a t e x o t r i e s 一1 i m i t 一1 0 ； t i g h t _ c r o s s o s = 0 - 3 ； p gx o - p r o b i l i t y = o 5 ； m a x g e n n u m = 1 0 2 4 ； 我们在i n t e l4c p u2 0 0 ，2 5 6r a m 的机器上采用v c + + 编程实现，计算八次 得到的缎优解翔表3 1 新示。 袁3 1 由袭3 一i 可鼹，s x o h c 是稳健有效的，其中六次俊亿螅羧饶解懿逶瘟度小 于或等于0 0 5 ，其中三次还达到了o 0 1 级的精确度。我们把第一次的结果化简 褥到下蕊静式子： f i ( x ) = x - 0 0 0 2 2 6