第22章　遗传编程

22.1　遗传编程的提出

遗传编程（Genetic Programming，GP），1992年由美国Standford大学的Koza在他出版的第一本著作Genetic Programming：On the Programming of Computers by Means of Natural Selection中提出的^[70]。遗传算法用字符串表达问题，而遗传编程采用层次化的树结构表达问题，类似于计算机程序分行或分段描述问题，这样有利于根据环境状态自动改变程序的结构和大小，以适应对问题的结构和大小的灵活处理。

遗传编程算法是一种在可能空间中寻找合适的计算机程序的自适应搜索算法，本质上属于随机搜索算法，但其空间遍历性比传统的启发式搜索要好，遗传操作使得路径可随机跳跃到不同的子空间，从而在全局空间中以若干搜索集的并集方式从时序过程方面逼近全集。

22.2　遗传编程的原理及基本操作

遗传编程的原理和遗传算法类似，都要随机产生一个适用于给定问题的初始种群，即搜索空间；不同的是，遗传编程种群中的每个个体为树状结构（也称程序树）。二者同样需要计算每个个体的适应度值；选择遗传算子（复制、交叉、突变等）对种群不断进行迭代优化，直到找到最优解或近似最优解。因此，遗传编程被看作遗传算法的特殊情况。

1. 遗传编程的基本概念

下面给出遗传编程的几个基本概念。

（1）函数集。函数集F包含n个函数：

F=｛f₁，f₂，…，f_n｝（22.1）

其中函数集内的f_i包括运算符（+、-、∗、÷，布尔运算符等）或函数（sin、tan等），以及一些表达式（循环表达式与条件表达式等）。

（2）终止符集。终止符集T包含m个终止符：

T=｛t_i，t₂，…，t_m｝（22.2）

终止符集内的终止符可以是x、y、z等变量或a、b、π等常量。

将上述函数f_i和终止符t_j组合，可以得到4种函数描述的层次化的树状结构形式如下：

y₁=a+b∗x

y₂=a∗+exp（b∗x）

y₃=a+b∗logx

y₄=a∗x^b=a∗x↑b

函数集应满足闭合性，即每个函数都应能够接受任何终止符或任何函数的输出作为输入，以确保GP中产生语法正确的个体。此外，函数集与终止符集还应满足Koza所说的充分性，即所提供的终止符与函数应该可以用来表示出问题的解。因此，通常要为遗传编程系统提供冗余的函数及终止符，而后在进化中剔除那些用处不大的函数和终止符。

（3）适应度。个体适应度是衡量个体表达式逼近最优解的优劣程度。

（4）控制运行的参数（变量）。

（5）表明结果的方法和终止运行的准则。

遗传编程中适应度函数、控制参数、表明结果的方法和终止运行的准则与遗传算法类似，这里不再赘述。其中最重要的控制参数是群体大小和迭代次数。

2. 遗传编程的个体表示法

遗传编程的个体表示法根据其基本结构可大致分为3种：树状结构、线性结构和基于图形的结构。其中最常见的每个个体都是一个以树状结构来表示的程序或表达式。如图22.1所示，树A与树B分别代表两个个体（多项式）：［（x²）+（5x）］-9和（3×x）×（x÷1）。可见，遗传编程中的个体具有分层结构。树中的节点可分为两类：一类位于内部的节点称为“函数”，另一类位于端点的叶节点称为“终止符”。图22.1中的函数都是基本算术运算，如+、-、×、÷等，由简单的基本运算进行组合表示复杂的表达式。图22.1中的终止符包括变量x和常量9、5、3等。称虚线以上的2个节点（-和×）为根节点。就表示方法而言，遗传编程输出的解是显式的直接的表达式或程序。

3. 初始个体的生成及基本操作

GP的初始群体（第0代）中的个体是随机生成的，由给定的函数和终止符构成程序，生成初始群体的过程可看作在程序空间中的盲目搜索。生成初始个体时，首先从函数集中随机选取一个函数作为根节点，如图22.1中的“-”和“×”。根据该函数所处理的自变量数目（相当于节点的度）选择同样数量的子节点，此时可以随机地从函数集与终止符集的并集中选取。“-”与“×”都是二元操作符，因此各有两个子节点。以个体A为例，其左节点选中的是函数“+”，将重复上述操作；而其右节点选中终止符“9”，则该子树停止生长。左子树继续生长，直到树中各分支都选择终止符作为子节点为止。生成初始个体时，为控制个体的大小，可以规定叶节点的最大深度（即叶节点的最大层数），在个体A中节点最大深度为3，也可以将所有叶节点的深度统一规定为最大深度。

遗传编程的基本操作包括复制、交叉、突变等。通常，上述操作以适应度为基础随机进行，即个体的适应度越大，它被选中的概率越大。其中，复制操作即基于适应度，随机地选择一个个体，将其复制到下一代群体中。而交叉操作是从两个随机选取的父代个体中产生两个子代个体。两个交叉点分别在父代个体中随机选取。接前例，如图22.2与图22.3所示，个体A中选中交叉点为“+”，而个体B中为“÷”，则自两个节点以下的子树进行互换生成两个子代个体A′：（x÷1）-9和B′：（3×x）［（x×x）+（5×x）］。

通过突变操作，从基于适应度随机选出的一个父代个体中，产生一个子代个体。随机选中父代个体上的突变点后，该节点处的子树就被删除，而后应用类似于生成初始个体的生长方法生成新的子树。接前例中的个体B，如选中“÷”为突变点，则子树（x÷1）将被删除，置换成随机生成的（9-5），如图22.4所示。生成新个体B′：（3×x）×（9-5）。很多人认为突变对于遗传编程不是非常重要，有的GP系统中不包括突变操作。突变操作是个体的树状结构的某个分支被一个随机出现的结构所替代，这种操作可以扩充种群结构的多样性。

综上所述，遗传编程的种群中每个个体的大小、结构和内容都是动态变化的，这是由遗传操作来实现的。因此，遗传编程是一种可变结构的更为灵活的算法。

22.3　遗传编程算法的设计步骤及流程

遗传编程算法的设计步骤一般分为以下3个部分。

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

（2）对群体循环执行遗传操作，直至满足终止准则为止。遗传操作包括以下两个步骤。

①为群体中的个体选择合适的适应度值。

②采用复制操作、交叉操作和变异操作的遗传操作，产生一个新的群体，新群体中个体的选择是根据其适应度随机选择的。

（3）遗传编程算法满足终止条件后，要找出一个结果作为问题的解（确定结果的方法有全局最优个体法、末代最佳个体法和多种解答法）。

遗传编程算法的流程如图22.5所示。

22.4　遗传编程算法的本质属性

遗传编程的创始人Koza等学者归纳了如下16种自动编程系统的本质属性。

（1）自动编程系统从对指定问题的上层描述开始（始于“需要做什么”）。

（2）系统产生的结果形式是一系列能令人满意地解决问题的步骤（告诉人们“如何做”）。

（3）系统将产生一个可在计算机上运行的实体（产生一个计算机程序）。

（4）系统可以自动确定必须执行的步骤数目，因而用户无须事先规定解的确切规模（即自动确定程序规模）。

（5）系统能够自动将有用的步骤组织起来以便重用，即代码重用。

（6）系统能够重用具有不同实参（用实参代替的形式参数或哑变量）的步骤组合（参数化重用）。

（7）系统有使用中间存储的能力。其可利用的中间存储形式包括单个变量、向量、矩阵、数组、堆栈、队列、表、相关存储等数据结构。

（8）系统能够执行迭代、循环和递归操作。

（9）系统可以进而将步骤自动组织成一个分层结构。

（10）系统能够自动确定程序的结构。即自动地确定是否使用子程序、迭代、循环、递归和中间存储，以及确定各子程序、迭代、循环、递归和中间存储所具有的自变量的数目。

（11）系统具有宽泛的编程结构。它能够模拟编程人员认为有用的编程结构（包括宏、库、指针、条件运算、逻辑函数、整型函数、浮点型函数、复合值函数、多输入、多输出和机器码指令等）。

（12）系统是严格定义的，它在严格定义的方式下运作并严格地区分哪些是必须由用户提供的、哪些是由系统交付的。

（13）系统不依赖于所解决的问题，它不必为每个新问题修改自己的可执行步骤。

（14）系统应具有广泛的适用性，可为许多不同领域中的问题提供令人满意的解。

（15）系统对同一个问题的较大的版本有良好的可扩充性。

（16）系统产生的结果可以与那些程序员、工程师、数学家和设计师得出的结果相媲美。

由于上述特点，因此遗传编程可用多种语言（如LISP、C、C++、Prolog等）编写遗传编程系统，它们被广泛应用于系统辨识、控制、分类、设计、最优化等诸多领域，并取得了令人满意的效果。