第28章 基因表达式编程算法
基因表达式编程算法是融合了遗传算法和遗传编程优点的一种新的进化算法，它实现了从生物基因表达到基因表达式编程的跨越。它的个体编码方法和结果在表达形式上继承了GA的定长线性编码简单、快捷的优点；在基因表达上继承了GP的树状结构灵活多变的优点。这种把基因型（染色体）和表现型（表达式树）既分离又互相转化的结合，使得基因表达式编程算法克服了GA损失功能复杂性的可能性和GP难以再产生新的变化的可能性，极大地提高了解决问题的能力和效率。本章介绍基因表达式编程算法的原理、基本概念、遗传操作和算法流程。
28.1 基因表达式编程算法的提出
基因表达式编程（Gene Expression Programming，GEP）算法是2001年由葡萄牙的Ferreira博士提出的[89]，2002年Ferreira出版了关于基因表达式编程的第一本专著[90]。
GEP算法在个体的表示、处理和结果的形式等方面与传统遗传算法（GA）及遗传编程（GP）算法有着显著的区别。GEP算法融合了GA算法和GP算法的优点——GEP算法不仅继承了GA算法刚性地使用定长的线性染色体为遗传物质，采用简单编码解决简单问题的优点；而且还继承了GP算法柔性地使用非线性的、不定长的树状结构，采用复杂编码解决复杂问题的优点。所以GEP算法刚柔相济，表现为定长线性串，易于遗传操作，又间接地对应于柔性的具有非线性的树状结构，从而达到了以简单编码解决复杂问题的目的，使得在速度上比传统进化算法提高了2～4个数量级。
GEP算法被广泛用于解决函数发现、关联规则、分类规则挖掘、聚类、时间序列预测、自动控制、多模函数优化等重要问题。
28.2 基因表达式编程算法的原理
GEP算法是一种有导向性的随机搜索算法。基因表达式编程操纵的对象和遗传编程同样是程序，基因表达式编程处理的对象是数值表达式，或者是布尔表达式。
GEP算法的基本步骤为：首先，从随机产生一定数量的染色体个体形成初始种群开始；其次，对这些染色体进行表达，依据一个适应度样本集（问题的输入）计算出每个个体的适应度；最后，个体按照适应度值被选择，进行遗传操作，产生具有新特性的后代。这样的过程反复进行若干代，直到算法发现一个优良解而结束。
GEP算法的核心技术是将变异过程和评估过程完全分开。它的变异过程使用定长的线性符号串，而评估过程采用表达式树，两者之间可以通过规则进行相互转化。对每个具体问题来说，算法执行之前必须确定产生染色体的符号，即选择适合问题解的函数集和终点集；确定基因的结构及基因的头长，每个染色体中的基因数和各基因的连接运算符号；最后还要选择一个适应度函数，确定遗传控制参数。理论和实践均证明了该算法依概率收敛到最优染色体。
28.3 基因表达式编程的基本概念
1. 终结符
终结符是提供给系统数据的最末端结构。终结符自己提供信息，但不处理另外的信息。通常，终结符集合包括基因表达式编程程序中的输入、常量和没有参数的函数。
如果用树状结构来表示程序，则终结符代表树的那些叶节点。当程序运行时，这些叶节点，或者接受外部的输入，或者自己就是一个常量，或者自己计算产生一个量。它们向系统提供信息，以供处理。通常用T表示一个基因表达算法的终结符集合。
2. 函数
基因表达式编程中的函数概念包括系统中其他任何非终结符的中间结构。函数集合可以包括与应用有关问题领域的运算符号，也可以包括程序设计语言中的程序构件，甚至是表示系统中间层次的一种符号。
常见的函数包括：算术运算符，如+、-、×、÷等；初等数学函数，如sin、cos、
等；其他一些函数，如max、min、自定义函数等；布尔运算符，如∨、∧等；关系运算符，如＜、＞、=、≠、≤、≥等；条件运算符，如if-then-else。
函数表示树状结构程序中的非叶节点。根据问题空间的描述不同，要么接受子节点传递的信息，进行处理；要么代表一种抽象子树的中间层次结构。
通常用F表示基因表达算法中的函数集合，每一个函数f∈F记为f（p1，p2，…，pm），其参数个数记为λ（f）；函数参数的最大个数为函数集合的参数数量，记为
λ（F）=max（λ（f）|f∈F）（28.1）
基因表达式编程环境可以用一个表示函数集合F和表示终结符集合T的二元组描述，简记为
GEP=<F，T>（28.2）
3. 函数和终结符集合的选择
基因表达式编程首先需要选择构造程序的函数及终结符集合，选择应该满足以下要求。
（1）充分性：选择的函数和终结符集合要足以能够表示问题的解。至少要对每一个输入定义一个终结符，如果需要，可根据问题的特点，再选择若干常数或无参数的自定义函数。选择哪些函数才能保证能表示问题的解需要经验和尝试。不要选择过大的函数集合，否则将极大地扩大基因表达式编程的搜索空间，大大降低搜索效率。
（2）封闭性：因为寻找的公式可能以任意的方式进行组合，子节点的输出一定要能够被父节点接受。要求所有的终结符和函数的值域及函数的每一个参数的定义域都是相同的。
（3）所有函数在所有输入下都应该是有定义的。
4. GEP中的K-表达式
基因表达式编程的染色体是由K-表达式构成的。Ferreira直观地描述了一种很简单的将表达式线性化方法，这种方法就是K-表达式。对于定义在GEP=<F，T>上的一棵表达式树，按照从上到下、从左到右的顺序遍历，所得到的序列称为表达式树的K-表达式。
【例28.1】 对于算术表达式
sin（（a+b）c2）（28.3）
其表达式树如图28.1（a）所示。
K-表达式是一种很简单、很直观的遍历表达式树的方法。应该注意表达式的K-表达式和先序、后序遍历都存在很大的差异。图28.1（b）、（c）给出了式（28.3）表达的先序、后序遍历序列，图28.1（d）则是sin（（a+b）c2）的K-表达式。
图28.1 sin（（a+b）c2）的各种表现形式
5. GEP的基因与多基因
如果K-表达式长度不够，或者说，K-表达式不完整，那么解码算法中可能没有足够的符号用于构造表达式树，构造的表达式树将是不完整的，也就不能表示一个表达式的完整意义。所以，任意的符号串并不能当成K-表达式作为遗传编码。只有完整的K-表达式才能解码为一个表达式，也才能够作为遗传编码。
Ferreira在提出的GEP算法中对K-表达式作为遗传编码做了一定的限制，使得可以将K-表达式作为遗传编码，进而利用进化计算的力量来进行公式发现。
若有GEP=<F，T>，则头部长度为h的GEP基因是满足下列条件的K-表达式。
（1）长度为h+t，其中
t=h×（λ（F）-1）+1（28.4）
其中，λ（F）为集合F中函数的最大参数个数。
（2）前h个符号a满足a∈F∪T，后t个符号b满足b∈T。基因的前h个符号称为头部，后t个符号称为尾部。
实践证明，如果选择一个过分长的基因编码长度，那么GEP算法的搜索效率将很低。但是，如果基因太短，那么其可以表示的表达式的复杂程度就会很有限。为了解决这个矛盾，Ferreira模拟大自然的解决方案，引入了多基因。在一个GEP算法的染色体中包含多个基因，然后，用一个指定称为连接函数的函数来连接这些基因解码得到的表达式树。
6. 适应度函数
在GEP算法中，由于解答是一个程序，在很多应用中确切地说是一个表达式，对表达式进行评价，就是要评测利用表达式计算得到的数据和训练数据的符合程度。
Ferreira提出了两种评价模型。令T是训练数据集合，包含m组数据，Tj表示训练数据中第j组数据的输入；yj表示对应于Tj的观测数据；
利用公式从Tj计算得到的yj的估计值。M是一个常数。
实际上就是利用绝对误差或相对误差进行评价。
7. 数值常量
数值公式发现是GEP算法的重要应用。在这类应用中，数值常量处理是其中的一个重要特征。在GEP算法中，Ferreira提出了一种随机产生、随机变化的数值常量方法。
28.4 GEP算法的遗传操作
由于GEP算法采用了线性等长编码，因此其遗传操作更加类似于遗传算法。只要在进行遗传操作的过程中满足保持基因的长度且尾部只能出现终结符，那么得到的子代染色体就仍然是合法的基因。所以GEP算法的遗传算子变得非常简单、灵活。如图28.2所示的例子中，设F=｛+，-，∗｝，T=｛a，b｝，头部长度为h=8。
（1）选择。选择算子的设计在GEP算法中没有特殊性，可以选择任何常用的选择算子，如比例选择或锦标赛选择等。通常在遗传算法中为了防止超级个体独霸种群，多采用锦标赛选择算子，在GEP算法中同样适用。
（2）变异。变异作用在单个染色体上，对染色体的每一位进行随机测试，当满足变异概率时，重新产生该位的编码。如果变异位在基因头部，可以重新选择所有的符号，否则只能选择终结符。图28.2演示了父代染色体P，经过变异产生子代S的过程。它变异了第4个位置的编码。
图28.2 变异操作
（3）插串。插串是GEP算法所特有的遗传算子。它随机在基因中选择一段子串，然后将该子串插入到头部随机指定的一个位置（但不能是第1个位置），将头部的其他符号向后顺延。超过头部长度的编码将被截去。图28.3演示了父代染色体P，经过插串操作产生子代S的过程。它选择了第10～12位置的编码，插入到第3个位置，父染色体中的第5～7位置的编码被截掉了。
图28.3 插串操作
（4）根插串。插串算子不允许将选择的串插入到第1个位置，而根插串算子则是专门将选择的子串插入到第1个位置。根插串算子从头部随机选择的一个位置开始向后扫描，找到第1个函数，然后以该位置为起始，选择一段子串，将该子串插入到第1个位置，头部编码依次后移，超过头部的部分被截去。如果扫描过程没有找到函数，则不做任何事情。图28.4演示了父代染色体P经过插串操作产生子代S的过程。它选择了第3～5位置的编码，插入到第3个位置，父染色体中的第5～7位置的编码被截掉了。
图28.4 根插串操作
（5）单点重组。单点重组作用在两个父代染色体上，随机选择一个交叉位置，互换交叉点后面的染色体部分，得到两个子代染色体。
（6）双点重组。双点重组也是作用在两个父代染色体上。在染色体上随机选择两个交叉点，然后互换交叉点之间的染色体部分。
（7）基因重组。基因重组只作用于多基因的染色体。随机选择一个基因，然后交换两个父代染色体相对应的基因。
很显然，经过这些遗传算子的作用，得到的子代染色体仍然符合GEP基因的定义，也能够解码为一棵完整的语法树。
28.5 基本的GEP算法流程
GEP算法的流程如图28.5所示。
图28.5 GEP算法的流程图
在GEP算法中，除了有类似GA算法的单点重组、双点重组、单点变异等以外，还包括插串、根插串等具有独特动作和含义的遗传算子，以便形成具有特色的GEP算法。