[科普中国]-遗传编程

简介

遗传编程是一种特殊的利用进化算法的机器学习技术， 它开始于一群由随机生成的千百万个计算机程序组成的"人群"，然后根据一个程序完成给定的任务的能力来确定某个程序的适合度，应用达尔文的自然选择（适者生存）确定胜出的程序，计算机程序间也模拟两性组合，变异，基因复制，基因删除等代代进化，直到达到预先确定的某个中止条件为止。遗传编程的基本思想也是借鉴了自然界生物进化理论和遗传的原理，是一种自动随机产生搜索程序的方法。由于该算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强，并且对非线性复杂问题显示出很强的求解能力，因而被成功地应用于许多不同的领域，并且在近几年中得到了更深入的研究。

使用范围及特点GP的适用范围是非常广泛的，理论上凡是根据多个输入值而得到一个值的函数，如:对于f(x1，x2，… ，xn)这样的函数都可以使用GP来生成。当对于逻辑上比较简单的程序，直接可以用手工编写，而没有必要用GP来产生，但对于一些逻辑上比较复杂的程序则可以用它来自动进化生成一个程序。

例如:对于有较多控制响应的Agent，产生其控制程序是非常困难的，它们往往是根据多个外界刺激而产生相应的决策(动作)，这类程序就可以用GP来生成。

在具体实现上，它有如下一些特点:

(1)GP求解的是一个描述问题的程序(或者说是一个算法)。

(2)GP通常用树型结构来表示，描述相对复杂。

(3)GP的每一代的个体的长度(深度)一般是不同的，即使在同一代中的个体之间的长度(深度)也是不同的。

(4)GP所消耗的资源是不可控的(这里所指的不可控是指不能精确的描述)，需要消耗大量的内存空间，因而每一代的进化都比较慢。2

实现过程语言的选择遗传编程在不同的语言上有不同的实现方法。对于遗传编程所生成的程序既可以看成是程序又可以看成是数据。在遗传编程的过程中它是数据，需要对它进行随机生成、交叉操作、变异、评估等操作;在遗传编程结束后，它又是程序，需要执行它。Lisp语言非常适合于遗传编程，因为Lisp语言可以对程序本身进行操作，然后再执行。3

程序表示方法程序可以有两种表示方法:树型结构表示法和字符串表示方法。树型结构表示方法结构清晰，在进行交叉和变异操作时比较简单，但需要占用较大的存贮空间，由于遗传编程每一代需要用到大量的树结构，所以存贮开销是非常大的，空间复杂度是遗传编程中需要研究的一个课题；对字符串来表示程序可以节省大量的存贮空间，但进行遗传操作时比较困难，如在选择“双亲”的随机交叉点或变异点时比较复杂，需要进行转换。

对于Lisp语言来说，其本身就是字符串，所以比较适合用字符串来表示遗传程序；对于C语言来说，这两种方法就都可以选择了。所以共有4种结合方式:C语言+树型结构、C语言+字符串表示、Lisp+树型结构、Lisp+字符串表示，其中第三种方式不常用(这里所指的C语言是代表除了Lisp以外的大部分其它通用语言)。

用Lisp语言来表示树型结构则比较少用，因为没有必要。若用C语言来表示字符串结构，则与Lisp语言相似，比较简单，可以把遗传程序当作数据来处理，把程序表示成伪Lisp语言，等到遗传结束以后，再把它当作程序来使用，当然，在进行性能评估时也要当作程序来进行执行，这一点下面会作具体的描述。2

程序执行方法对于Lisp语言来说程序的执行是比较简单的，因为遗传生成的数据就是程序，可以立即执行。而对于C语言来说就是非常复杂的了，因为C语言生成的程序仅仅是数据而已，不可以拿来执行。为此，必须设计一个解释器，来解释所生成的程序，对于树型结构和字符串型结构需要生成不同的解释器。4但对于不同的应用需有不同的解释方法，所以解释后的执行方法也是不同的，为了做到通用，设计了一个执行接口，对于所有的应用，可以使用相同的解释器，称之为虚拟机，只有执行部分可以是变化的，对于不同的应用，调用不同的执行函数。

评估函数选择对于不同的应用，需要选择不同的评估函数，所以在程序设计上就不能作出一个通用的评估函数。评估函数的取法，当前也是一个需要研究的课题，目前还没有一个通用的有效的设置方法。对于这种情况，可以设置一个通用接口(利用类的多态性)，对于不同的应用设置不同的评估函数(用一个子类来实现这个接口)。

发展过程遗传编程的首批试验由斯蒂芬.史密斯 (1980)和克拉姆 (1985)发表。约翰.Koza(1992)也写了一本著名的书，来介绍遗传编程。

使用遗传编程的计算机程序可以用很多种编程语言来写成。早期（或者说传统）的GP实现中，程序的指令和数据的值使用树状结构的组织方式，所以那些本来就提供树状组织形式的编程语言最适合与GP，例如Koza使用的Lisp语言。其他形式的GP也被提倡和实现，例如相对简单的适合传统编程语言（例如Fortran， BASIC， andC）的线性遗传编程。有商业化的GP软件把线性遗传编程和汇编语言结合来获得更好的性能，也有的实现方法直接生成汇编程序。

遗传编程所需的计算量非常之大(处理大量候选的计算机程序)，以至于在90年代的时候它只能用来解决一些简单的问题。近年来，随着遗传编程技术自身的发展和中央处理器计算能力的指数级提升，GP开始产生了一大批显著的结果。例如在2004年左右，GP在多个领域取得近40项成果：量子计算，电子设计，游戏比赛，排序，搜索等等。这些计算机自动生成的程序（算法）中有些与2000年后人工产生的发明十分类似，甚至有两项结果产生了可以申请专利的新发明。

在90年代，人们普遍认为为遗传编程发展一个理论十分困难，GP在各种搜索技术中也处于劣势。2000年后，GP的理论取得重大发展，建立确切的GP概率模型和马尔可夫链模型已成为可能。遗传编程比遗传算法适用的范围更广（实际上包含了遗传算法）

Juergen Schmidhuber进一步提出了宏遗传编程，一种使用遗传编程来生成一个遗传编程系统的技术。一些评论认为宏遗传编程在理论上不可行，但是需要更多的研究再确认。1