1.1.4 遗传编程

实际上，把GA和计算机程序结合起来的思想早已出现，Holland把产生式语言和GA结合起来实现分类系统，还有一些GA应用领域的研究者将类似于GA的遗传操作应用于树型结构的程序上。1985年，N. L. Cramer首先提出将GA应用于树型程序，一些重要的概念如程序的树型结构、终止要求、子树交叉等被提出[19]。1989年，Stanford大学的J. R. Koza创造性地提出了基于自然选择原则用层次化的计算机程序来表达问题的遗传程序设计方法。1992年，Koza出版了专著《遗传编程：论采用自然选择方法的计算机编程》[20]；1994年，Koza又出版了《遗传程序设计（第二册）：可重用程序的自动发现》[21]，深化了遗传程序设计的研究，程序设计自动化展开了新局面。自20世纪90年代以来，Koza利用1000台350MHz的PC自动进化出30多项模拟电子电路专利。这些能自动设计出具有专利水平的设计成果的基于GP的“自动发明机器”成为了新一代计算智能的代表。2000年，Koza进化出了超越传统控制器的新型控制器。2004年国际遗传与进化计算国际会议颁发了首届全球挑战人类设计锦标赛，获奖成果包括利用遗传编程（GP）实现的量子电路设计，美国国家航空航天局进化出的性能优异、外形奇特的天线，康奈尔大学Lipson进化出的机构设计史上的一个难题——实现直线运动的连杆机构，美国著名的喷气推进实验室进化出的特殊的电子电路。

GP又称基因编程，是借鉴生物界的自然选择和遗传机制，利用GA的进化原理来自动进化出计算机程序的全局优化搜索算法。GP常采用树型结构来表示计算机程序，从而解决问题。对于许多问题，包括人工智能和机器学习上的问题都可看作需要发现一个计算机程序，即对特定输入产生特定输出的程序，形式化为程序归纳，那么GP提供了实现程序归纳的方法。

GP是一种从生物进化过程得到灵感的自动化生成和选择计算机程序来完成用户定义的任务的技术。从理论上讲，人类只需要告诉计算机“需要完成什么”，而不用告诉它“如何去完成”，最终可能实现真正意义上的人工智能：自动化的发明机器。GP是一种特殊的利用进化算法的机器学习技术，它开始于一群由随机生成的千百万个计算机程序组成的“人群”，然后根据一个程序完成给定的任务的能力来确定某个程序的适合度，应用达尔文的自然选择（适者生存）确定胜出的程序，计算机程序间也模拟两性组合、变异、基因复制、基因删除等代代进化，直到达到预先确定的某个中止条件为止。

GP在程序运行过程中会产生适用于给定问题的初始群体，然后不断地进化，进化过程类似于自然界的生物进化，最终寻找到用户问题的最优解。在GP运行时，要提前确定解决用户问题时所有可能需要的集合，如函数集和终止符集。函数集可以是算术运算符（+、−、×、/等）、数学函数（sin、cos、exp、tan等）、布尔运算符（AND、OR、NOT等）、条件表达式（if-then-else）等，还可以是程序中的子程序及其他可定义的函数。终止符集含有与问题相适应的变量、随机常数等，如终止符集T={p，x}，其中p为随机数，x为输入变量。最终程序可通过集合来随机生成初始群体，然后确定适应度标准，以此来评价程序解决问题的能力，类似于自然界中的适者生存。在进化过程中，个体可进行复制及交叉等遗传操作，与自然界的进化相似，也有可能产生变异的个体。适应度值较低的个体消亡，适应度值较高的个体经过许多代进化，就会有用户所需的解产生。但GP并不能保证每次运行都能求得问题的解，须对参数的设置进行多次实验，可以说GP算法所得结果与实验过程有着紧密的联系。同时，其自组织性保证它能根据所给数据产生结构复杂、高精度的函数模型。

函数集中的元素代表解决问题的基本方法，而终止符集中的元素代表问题的基本要素，一个合适的函数集和终止符集将会对寻找最优个体的过程起到积极的作用，因此我们在选取函数集和终止符集的时候，通常遵循以下原则：首先，函数集和终止符集的选择要满足充分性和有效性，即函数集和终止符集要能充分表达问题，并且只能产生语法正确的个体；其次，函数要具有在终止符集上的封闭化，即函数集中的任何函数的返回值仍应属于终止符集，这样能够保证最终得到的是可取的解；最后，函数集中的函数个数不能过多，以免在寻优过程中因搜索空间太大而降低寻优效率。

GP简单通用、稳健性强，并且对非线性复杂问题显示出很强的求解能力，因而被成功地应用于许多不同的领域。理论上，凡是根据多个输入值而得到一个值的函数，如：对于f(x1，x2，…，xn)这样的函数都可以使用GP来生成。当对于逻辑上比较简单的程序，直接可以手工编写，而没有必要用GP来产生，但对于一些逻辑上比较复杂的程序则可以用它来自动进化生成一个程序[22]。

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

GP在具体实现上，有如下特点：

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

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

（3）GP的每一代的个体的长度（深度）一般是不同的，即使在同一代中，个体的长度（深度）也是不同的。

（4）GP所消耗的资源是不可控的，需要消耗大量的内存空间，因而每一代的进化都比较慢。