遗传程序设计方法综述.docx

遗传程序设计方法综述.docx

《遗传程序设计方法综述.docx》由会员分享，可在线阅读，更多相关《遗传程序设计方法综述.docx（10页珍藏版）》请在冰点文库上搜索。

遗传程序设计方法综述

刘大有①卢奕南①王飞①梁艳春②

①（吉林大学计算机科学系长春130023）

②（吉林大学数学系长春130023）

（dyliu@ccpublicjlcn）

摘要近年来，遗传程序设计（geneticprogramming,GP）的研究引起了人们很大的关注，它运用遗传算法（geneticalgorithm,GA）的思想，通过生成计算机程序来解决问题介绍了遗传程序设计的研究状况以及目前的研究进展，概述了它的基本算法、主要特点、理论与技术，同时介绍了一些GP实现系统以及主要的应用领域,最后探讨了遗传程序设计的研究方向.

关键词遗传算法（GA）,遗传程序设计（GP）,自然进化，程序归纳

中图法分类号TP301.6

GENETICPROGRAMMINGPARADIGM:

ASURVEY

LUDa-You®,LUYi-Nan®,WANGFei①，andLRNGYan-Chun②

①（DepartmentcfComputerScience,JilinUniversity,Changchun130023）

②（DeparimentcfMathematics,JilinUniversity,Changchun130023）

AbstractResearchongeneticprogramming（GP）hasattractedalotofattentionrecentlyGPsolvesproblemsbyusingideasfromgeneticalgorithmsandgeneratingcomputerprogramsTheresearchstateandadvancesintheGParediscussedandsurveyed,andthebasicalgorithms,theoryandrnplementationtechniquesoftheGPareoutlinedSomeGPsystemsandtheirmainapplicatfensarealsointroducedFurtherresearchdirectionsofgeneralinterestonthistopicareproposed

Keywordsgeneticalgorithm,geneticprogramming,naturalevolution,programinduction

1引言

遗传程序设计是借鉴生物界的自然选择和遗传机制,在遗传算法的基础上发展起来的搜索算法，它已成为进化计算的一个新分支在标准的遗传算法中，由定长字符串（问题的可行解）组成的群体借助于复制、交叉、变异等遗传操作不断进化找到问题的最优解或次优解遗传程序设计运用遗传算法的思想,常采用树的结构来表示计算机程序，从而解决问题对于许多问题，包括人工智能和机器学习上的问题都可看做是需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么遗传程序设计提供了实现程序归纳的方法"!

实际上把遗传算法和计算机程序结合起来的思想早已出现在遗传算法中,Holland把产生式语言和遗传算法结合起来实现分类系统，还有一些遗传算法应用领域的研究者将类似于遗传算法的遗传操作施加于树结构的程序上1989年，美国斯坦福大学的Koza基于自然选择原则创造性地提出了用层次化的计算机程序来表达问题的遗传程序设计（geneticprogrammmg,GP）方法，成功地解决了许多问题1992年,Koza发表了他的专著《遗传程序设计：

基于自然选择法则的计算机程序设计》⑴1994年，他又出版了《遗传程序设计，第二册：

可重用程序的自动发现》⑵，深化了遗传程序设计的研究，使程序设计自动化展现了新局面

近年来，遗传程序设计运用遗传算法的思想自动生成计算机程序解决了许多问题，如预测、分类、符号回归和图像处理等，作为一种新技术它已经与遗传算法并驾齐驱1996年，举行了第1次遗传程序设计国际会议，该领域已引起越来越多的相关学者们的兴趣

本文第2节描述了遗传程序设计的基本算法、主要特点，并从遗传程序设计的技术和理论两方面概述了目前的研究现状，介绍了一些遗传程序设计的实现系统以及主要应用领域;第3节指出了该领域新的热点研究方向.

2理论、技术和应用

GP理论和技术研究主要包括程序结构、GP操作、适应度评价、GP个体表示法、模式定理、GP系统和GP应用等方面遗传程序设计的基本算法又涉及了程序结构的形成、GP操作、适应度评价和GP个体表示法等4方面技术在具体介绍每一技术之前，我们首先对遗传程序设计的基本算法作简单描述

GP的基本算法：

（1）随机生成初始群体,其中个体是由表示问题的函数和终止符随机组合而成的计算机程序

（2）循环执行下列各步直到满足终止准则为止

①运行群体中的每个计算机程序，并对其赋予适应度；

②运行下面两个主要操作产生新的计算机程序群体

i）把当前一代计算机程序复制成新一代计算机程序，被复制的个体依其适应度随机选定

ii）随机选定双亲个体部位进行交叉操作产生新个体，双亲个体也依适应度随机选定

（3）用结果标定法确定的程序被认为是运行的结果，它可能是一个正确（或近似）的问题答案

从上述算法可以看出GP的本质是运用GA的思想，通过进化可执行程序来解决问题GP的主要特点在于它是可变长的、层次化的、常常是树结构的' ©1994-2006ChinaAcademicJournalElectronicPublis遗传材料，而且大多数情况下，程序个体是可执行的，也就是说常常通过某类解释器解释程序，以获得个体的适应度评价对于传统GA来说，个体通常是定长的位串或字符串而且个体的适应度评价由其结构和所要解决的问题来确定

在GP系统执行基本算法之前,要进行5个准备工作:

确定终止符集、函数集、适应度函数、控制参数、终止准则选择函数和终止符要满足充分性，即能充分地表达问题合理选择它们是机器学习中的一个共同问题适应度评价随着问题的不同而异，对一些问题要结合正确性、简洁性、时间等综合因素确定适应度评价终止符集、函数集以及适应度评价的确定不仅会影响程序搜索空间、搜索的难易程度，而且还会影响问题的最终解决其中，如何确定优化的控制参数，目前尚未得到解决

21程序结构的形成

程序结构的形成主要包含两个方面:

不同数据类型的结构和模块化结构

（1）不同数据类型的结构

标准GP使用树结构表示个体，为了对进化的结构能简便地进行操纵，每个程序元素要返回同一种数据类型，即满足封闭原则⑴,但许多问题需要处理不同的数据类型，因此有必要对结构以及对结构施加的操作增加一些限制，否则会出现语法上不正确的解Koza'u引进“限制语法结构”概念，解除了封闭限制来处理上述数据类型不同的问题他定义了一个规则集合对语法树上的每个函数的各个参数指定所需的终止符集和函数集，使得在初始化个体和进行遗传操作时通过类型限制确保语法上正确的个体被生成尤其在交叉操作时，第1个点选择后，第2个点的选择必须使其类型与第1个点相匹配但他未能提供统一、自动的机制将语法限制溶入GP中⑵.Montana⑶在Koza工作的基础之上,提出了强类型GP（stronglytypedGP,STGP）系统该方法只须预先指定函数、常量的数据类型,然后通过类型匹配、最大深度限制检查和类型表生成，建立数据类型正确的语法树,完成对群体的初始化，而且在进化过程中能保证不同的遗传操作生成数据类型正确的语法树，从而使STGP的搜索空间是合法的语法树集合他不仅提供统一的机制解决多数据类型问题,还引进了类属函数和类属数据类型的概念，通过减少函数集的数目，有效地降低了搜索空间和时间Haynes从进化协作策略的角度指出STGP方法比一般的GP方法更优越然后他又从面向对象的程序House.Allrightsreserved,设计出发，对数据类型进行层次分类，提出了类型继承的概念，基于此能产生更丰富的语法⑷，更有利于一些问题的求解以上几种方法都采用语法上的类型限制实现了程序结构的限制Janiknow151提出了与Montana的STGP类似的方法CGP（constrainedGP）.CGP可形成多种形式上的限制，在指定语法限制的同时，还利用特定问题的知识指定语义限制，排除了没有意义的那些子空间，是一个处理解空间限制的好方法Clack和Yu⑹也对STGP作了改进，可处理参数为函数类型的情况上述方法对给定的函数限制了其所能接受的参数范围，但是它们对这种多数据类型的结构缺乏更高层次的表示Whigham巧米用上下文无关文法CFG（contextfreegrammar）表示个体结构，并用这种文法指导交叉、变异操作它同前面的几个方法一样，都克服了GP可能出现语法上不正确解的不足此方法可自动保证数据类型一致，并能操纵由文法得到的明确制导树来维持语法，同时文法本身也通过学习新的产生式来进化,还可利用领域的专家知识构造文法因此该方法缩小了可能的搜索空间，从而具有发现答案的更大可能性Gruau181提倡使用语法指导GP的结构生成，并使用外部文法形成单元编码的表达式来构造人工神经网络,很好地解决了一类平衡问题

（2）模块化结构

在GP研究中，问题表示由与问题有关的原始函数集来定义函数作为树的内部节点，终止符作为叶节点，由这些元素组成的程序构成了GP的搜索空间,通过改变原始函数集，扩展问题表示,从而改变结构的组成，这样不仅动态地改变GP的行为，而且可减少程序的平均大小实际上，从传统的程序设计角度来说，就是采用了重用和模块化的思想通常有如下3种改变模块化结构的方式：

①自动定义函数（automaticdefinedfunction,ADF）

自动定义函数是koza[1]引入的一种关键技术,是一种嵌套的自动程序设计技术一个自动定义函数是遗传程序运行中动态进化着的一个函数（子程序、过程、模块），是一棵单独的树，可被同时进化着的一个程序（如一个主函数）所调用

在此方法中，每个个体程序由几个函数分支和一个（或多个）产生结果的主分支（程序体）组成，其中产生结果的分支能够调用一个或几个自动定义函数，一个函数分支也可调用已定义的函数，形成函数的层次化的自动定义每个函数分支有固定数目的

©1994-2006ChinaAcademicJournalElectronicPublic参数，由指定的原始终止符和函数集构成随着程序体的进化,ADF的定义也在不断进化，同时ADF分支上的遗传操作必须满足一些语法限制例如交叉只在同一类型的两个分支中进行，其中分支的类型由分支中定义的函数和终止符所确定对于结构一致的程序群体来说，分支归类是最简单的归类规则,即对群体中程序的每个分支设置为一个单独的类型，交叉操作只交换来自同一类型分支中的子树ADF的定义也在不断进化

通常ADF的数目和相互调用关系是固定的，对于个体为非固定的程序结构（即个体结构没有固定的函数分支和程序分支）来说，群体由许多不同结构的程序组成，那么会出现如何形成合适的程序结构的问题1994年,Koza⑵提出了分支复制、参数复制、分支产生、参数产生、分支删除和参数删除等6种操作，这些操作能动态改变这种非固定的程序结构，但需要更多的计算资源

采用ADF的GP算法（记为ADF-GP）,由于通过调用自动发现的了程序,生成了更复杂的程序，从而简化了程序树的结构，增强了搜索能力，提高了效率许多例子都显示出它的通用性、灵活性、高性能,尤其特别适用于复杂逻辑电路设计与大型科学计算但在理论上尚未能论证ADF-GP比标准GP更有效,而且从解决问题的角度来看，这种自动定义函数也并没有明确的含义，不能与问题的特定子目标相对应“°!

②模块获取（moduleacquisitbn,MA）

模块获取方法是Angeline和PoHack继Koza的遗传程序设计方法之后提出的在动态遗传算法GeLB中采用的一种方法山！

模块是通过消去某个个体子树而形成的参数化的具有唯一名字的函数形式该方法引进两个新的遗传变异操作：

压缩和扩展压缩操作随机选择程序中的一个节点，从中抽取一个模块，存入模块库中.扩展操作是压缩的逆操作，通过选择模块名，把它所代表的模块还原到它所在的树中去压缩操作吸取可能有用的模块,防止模块被其它遗传操作所破坏，还可被其它程序所调用，增强了原语言的表达能力，又降低了个体的平均大小扩展操作弥补了压缩操作所造成的群体多样性方面的损失Angeline用此方法解决了汉诺塔问题以及TTT游戏问题Kinnear1101在N-奇偶性问题中对ADF-GP和MA-GP作了比较，他认为ADF-GP之所以具有更好的性能,在于它不断地调用自动定义的函数这种采用MA的GP算法（记为House.Allrightsreserved,

MA-GP）的缺陷在于扩展了过多的模块，往往大多数模块是无用的,而且一个模块库要跟踪所有模块,会增加许多内存上的开销，从应用的角度来看是程序遗传进化的结果，通常与实际问题没有什么本质上的联系此方法不能产生令人鼓舞的结果

③自适应表不（adaptiverepresentatbn,AR）

自适应表小是Rosea和Ballard提出的层次化遗传程序设计方法（hierarchicalGP）中所采用的方法'⑵该方法跟踪进化轨迹,根据某种标准选出候选块，归纳生成新函数，再用这些新函数扩展函数集，实现问题表示的自动改变它与MA有相似之处，但AR的块是个体树中以给定深度的某节点为根的整个子树，而MA中的模块通常由深度压缩操作去掉某深度下的所有子树形成，而且MA的模块选择是随机的,AR法是以某种标准发现构造块，形成新函数，这样不需额外的遗传操作（扩展操作）.与Koza的ADF不同之处在于,AR中的函数是根据启发式知识或群体的统计信息来定义，而ADF是自动定义的Rosea和Ballard在N-奇偶性问题实验中比较了标准GP,ADF-GP及AR-GP,得出的结果是:

就获得解的代数及解的大小来说,AR-GP显示了优越的性能后来Rosea和Ballard又提出了借助学习的自适应表tjs（adapliverepresentationthroughlearning,ARL）算法网，用进化的子程序集扩展原函数集通过父子之间的适应度差别、群体的统计信息以及个体程序的性能等完成库中子程序的产生和删除，使得进化的子程序集吸取了进化过程中出现的共同知识，从而获得解决问题的必要结构ARL成功地控制了动态、不确定环境下的一个agent的行为

上述这几种方法具有两个基本共性：

归纳非递归程序和采用模块形式但也不能仅仅是因为程序设计者推崇模块思想，就相信这种思想会对程序的进化起更好的作用.

标准GP中可变长的树结构与传统GA的线性定长字符串相比，它更能丰富地表达问题，但由此也付出了一定代价，即搜索集变得很大，必须对结构加以深度或节点数目上的限制，而且在树的进化过程中，程序的有些代码对结果没有作用或不能简洁地表达行为，使得程序变得很大，这些现象称为膨胀（bloat）,有必要对此进行研究

22遗传操作

由于GP的层次化结构，所以存在许多不同形式的变异操作和交叉操作

©1994-2006ChinaAcademicJournalElectronicPublis

子树变异操作:

用随机产生的子树来代替个体中任意选择的一子树

点变异操作:

在个体上随机选择一个变异点，若变异点是函数，则用与其有相同分支数的另一函数来替换，若变异点是终止符，则用另一终止符替换

置换操作：

改变函数的参数次序，其中交换（svap）操作是它的一个特例，只作用在两个参数的函数上

产生操作:

采用初始化个体的方法生成新个体

常数变异操作:

终止符分变量和常量两种常量通常出现在符号回归问题中，首先要在某个与问题有关的区间内生成特定类型的随机数，再对其进行调整、变异

一点交叉:

在两个个体中，从根开始寻找形状相同的最大子树（即子树中的每个节点有相同分支数），在这两棵相同的子树中随机选择交叉点（它们是两了树中拓扑位置相同的两个点），然后执行标准GP操作,它和点变异一起用在Poli的模式定理'⑷中.

自交叉操作:

使用一个单独个体代表两个父亲，进行标准GP交叉操作

模块/盒式交叉:

标准的交叉操作仅允许交换整个子树，不可能交换树路径当中的一块，而在模块/盒式操作中，在第1个个体中定义一个模块,再在第2个个体中定义另一块，前者的模块被后者的模块所代替，用相应的方法来处理先前模块的参数与实际传给它的参数个数不匹配的问题Kinnear在基本GP方法中使用了各种形式的模块交叉，甚至还有模块自交叉，性能有所加强

强/弱上下文保持交叉（strongcontextpreservingcrossover,SCPC/weakcontextpreservingcrossover,WCPC）:

D'Haeseleer提出的两个交叉操作分别为强上下文保持交叉（SCPC）和弱上下文保持交叉（WCPC）[151.通过引进一个坐标系来识别树的节点位置,SCPC对具有相同位置交叉点的两个子树进行交换,而WCPC稍微放松了些限制，允许第1棵树选定的交叉点下的整个子树与第2棵树的同等位置的节点下的任何子树相交换，他使用这些操作解决了Koza的4个问题，如避开障碍的机器人、11型布尔复合算子等实验表明对于大部分问题来说，同只使用标准交叉操作的结果相比，SCPC与标准的交叉操作的结合会达到更好的性能指标（为获得具有99%可能性的解所要处理的最少的个体数目），而只有WCPC操作的执行效果很差

在GA中，变异操作常看做是一个小操作，同样House.Allrightsreserved,在GP中，Koza[1]认为变异对程序的进化不会起很大的作用,但随着GP应用的不断扩展，变异操作越来越多地加以使用最近，一些交叉和变异操作的比较实验显示出变异的优势,Chellapillall617]仅使用一系列变异操作（不使用交叉操作），在4个简单问题上取得了很好的结果他甚至表明了这种方法获得的性能要优于标准的GP.Luke和Spector"81通过大量实验分析交叉、变异的有效性,认为两者的相对性能受较多因素影响并与具体的问题有关交叉操作并不总是最适宜的操作

遗传算子的设计是GP的关键技术，但目前为止还没有发现设计遗传算子的通用方法

在GA和GP中，常采用交叉和变异操作来生成个体，但在PIPE（probabilisticincrementalprogramevolution）[1917j法中，它同GP一样用树表示程序，但新树的生成不是采用GP的遗传操作（交叉、变异），而是用一个概率树来指导树的生成，其中概率树的每个节点是一个向量，表示每个函数和终止符在此节点出现的概率，概率树也要不断地更新

对于常数处理问题，曹宏庆和康立山等刘在其混合演化建模方法中，以遗传程序设计优化模型结构，用GA优化模型参数，保证算法在得到好的结构的同时，也获得好的系数，显著地提高了求解的质量

23个体表示方法

在大多数GP的研究工作中，均采用可变长的层次化的树结构来表示个体，最初，Koza[1J采用Lisp语言的S-表达式的前缀语法实现算法目前，采用C语言和C++实现算法的工作正在增加

线性表示个体方法:

GA对线性染色体表示的个体进行程序归纳并不是很新的想法，早在1985年Cramer1211提出了一种线性语言JB,采用一个整数表表示个体，表分割成的子字符串为解决问题所定义的低层原函数,并采用GA的遗传操作，由产生的短序列程序计算简单函数在这个自适应系统中，他讨论了使用该语言进行程序归纳所产生的程序正确性问题，继而提出基于树的TB语言Perkis㈣实现了基于栈的GP,用一个线性后缀形式的线性染色体结构表示个体，采用一个FORTH型操作对象栈，用来存取操作数，解决语法错误问题Nordin1231使用有限的机器码集合实现一个系统，在该系统中个体表示是二进制机器码，无须像基于树的GP那样为计算个体适应度进行解释或编译，而是直接操纵二进制码此方法虽大大加快GP进程，但不具备、 ©1994-2006ChinaAcademicJournalElectronicPublis一般性，因为程序是固定长，专门针对SUNSPARCRISC指令集合且仅涉及了几个指令还有一些研究者对Nordin的工作进行了扩展后来Nordin对自己的工作进行了改进口气进化了具有复杂指令集合（如大多数PC机的NTELX86芯片）的机器码

有向非循环图的表示方法:

一般GP群体中的个体是森林中的树Handley1251和Keijzer1261用有向非循环图（DAG）来表示语法树的整个群体，由于群体中的许多个体来自相同或相近的父体，它们拥有很多公用代码，因此减少了群体的内存需求,而且避免了同一子树在不同个体甚至不同代的重复评价Handley进一步指出，如果GP中的函数没有副作用,那么运行时间会有大幅下降

并行分布式GP（paralleldistributedGP,PDGP）的图表示在PDGP中，程序由完全不同于树的有向图来表示，但是图中的节点是预先定义的网格上的节点，它们之间的连接有一定的限制节点含有程序的函数和终止符,一个连接代表控制流，一个节点可有多个输出，它计算的结果很快地被程序的其它部分所使用，这种重用性使得这一方法更加有效此方法可解决符号压缩、人工蚂蚁、人工神经网络等问题,在割草机和最大问题中同标准GP和ADF-GP相比，性能有所提高⑶彩

并行结构发现和组合（parallelarchitecturediscoveryandorchestratbn,PADO）的有向图表Z5：

Teller顷设计的PADO结构,是处理信号和图像的分类系统此系统由几组程序组成，每组识别一特定类别的图像，最高输出值的组所代表的类别就是输出结果，其中每个组的输出是组中的那些程序输出的一个线性组合，而且用遗传程序设计方法进化程序程序由有向图表示,弧代表可能的控制流，节点完成行为,并对下一步的可能控制流作出决策，程序共享索引内存在此程序表示中，存在循环问题,Teller采用一般的时间方法来处理这里的程序不是一般GP中的函数映射关系，而是一个算法（过程）.实验表明，如果在PADO中使用树来表示个体,那么即使花费大量时间和内存空间，但也只能达到75%的识别率比Teller系统达到的识别率还低5%.Teller方法有望成为处理一般的目标识别问题的一种新方法

多交叉作用的程序（multipleinteractingprograms,MIPs）:

Angeline"们为表示复杂行为定义