基因表达式编程GEP— 第二部分 遗传算法示例与GEP设计思想

网友私信反馈，希望能讲解一个遗传算法的实例，所以本文的内容进行了调整。本文分为三部分，先讲解一个简单的遗传算法例子，让大家对遗传算法有个感性认识。然后通过这个例子介绍一下进化算法中常用的术语，最后介绍GEP算法设计思想。

一、遗传算法示例

求二元函数最大值：

1、个体编码：

遗传算法直接操作的对象是表示个体的线性符号串，所以需要将变量X 1X2编码为符号串。常用的遗传算法编码方法有：二进制编码法、浮点编码法、符号编码法。本示例中采用二进制编码。

因为X 1X2为1到7之间的整数，所以可以采用3位无符号二进制整数表示X 1X2。将X 1X2的编码连起来组成6位无符号二进制整数符号串就形成一个种群个体，表示一个可行解。例如

个体的基因型与表现型之间可以通过编码和解码相互转换。

2、初始化种群

需要为遗传算法准备一些表示起始搜索点的初始种群数据。初始种群中的个体可随机生成，个体数量可人工设置。本例中，我们设置种群规模为4 。例如初始种群如下：

100101 101011 011011 111101

3、个体评估（适应度计算）

遗传算法以个体适应度的大小来评定各个体的优劣程度，从而决定其遗传机会的大小。因为本例中目标函数值总为非负值，并且以求函数最大值为优化目标，所以直接利用目标函数值作为个体适应度。

4、选择运算

基于选择规则和个体适应度大小从当前种群中选取个体进入交配池形成父代种群，要求适应度高的个体有更多的机会遗传到下一代群体中。

本例我们采用轮盘赌选择法（Roulette Wheel Selection）:

· 先计算出种群所有个体适应度总和 ;

· 计算出每个个体的选择概率：，即每个个体被遗传到下一代群体中的概率；

· 所有的个体的概率累积到一起，形成一个0到1的累积概率区域（选择概率大的个体占的区域越大）；

· 生成一个[0,1]区间的随机数，该随机数作为选择指针在累积概率区域中确定被选个体。通过多轮选择生成父代种群；

经过四轮选择，最终形成的父代种群：

111101， 100101，111101，101011

5、重组（交叉）运算

重组（交叉）运算是遗传算法中产生新个体的主要操作。首先随机配对的两个个体，然后一定概率相互交换个体间的部分染色体。通常重组（交叉）运算方法包括单点重组（交叉）、两点重组（交叉）和基因重组（交叉）。本例中采用单点重组（交叉），具体过程如下：

· 对种群进行随机配对；

· 随机设置交叉点位置；

· 相互交换配对个体交叉点后（包括交叉点）染色体；

由上表可知，经过选择与重组后已产生最佳个体"111111"。

6、变异运算

变异运算是从父代个体中随机选择个体，对个体中某一个或一些基因座进行改变。具体操作过程如下：

· 从父代种群按一定比例选取待变异个体；

· 随机产生变异点位置，将变异点原有基因值取反

例如，变异比例为0.25，即从种群4个个体中随机选择一个个体进行变异

7、总结

经过一轮迭代，算法已得到最佳值"111111"。上述示例为了更好地说明问题，选择了一些较好的数值以便能够得到较好的结果，而在实际运算过程中有可能需要多轮迭代才能达到这个最优结果。

二、进化算法常用术语

1、个体 ( individual )：生物学角度，个体表示单个生物。在进化算法中，个体代表问题解空间的一个可行解。

2、基因型：个体的内部表现。比如上节示例中个体100101就是个体的基因型。

3、表现型：个体的外部表现。比如上节示例中个体100101，解码后X 1=4 X2=5就是个体的表现型。

4、编码（coding）:表现型到基因型的映射。

5、解码（decoding）:基因型到表现型的映射。

6、染色体（Chromosome）：基因型个体。比如上节示例中个体100101就是一个染色体

三、GEP设计思想

1、GEP发展历程

通过上边的示例，我们可以了解遗传算法原理非常简单，但这种简单也带来了不足。编解码规则简单以及编码符号串长度固定造成染色体表现形式、功能多样性存在比较大的限制。

斯蒂芬.史密斯 (1980)和克拉姆 (1985)在遗传算法基础上，提出了遗传程序设计（Genetic Programming，GP）算法。采用非线性实体（语法分析树）来解决编码符号串长度固定导致表现能力弱的问题。

上图就是GP算法一个个体（染色体）的示例，a是个体的基因型，b是个体的表现型。GP的编解码规则使其可以产生大小和形状不同的非线性个体，导致其表达方式成为一个更丰富、功能更强的系统。

但GP算法也存在很大的问题：一是由于个体长度不固定，表现结构比较复杂造成存储需要大量的空间，二是由于重组、变异等遗传运算受到限制，因为有些运算可能会造成运算后染色体无法存活（语法树结构不合法），如下图所示：个体进行以过变异运算，箭头所示的运算符由"sqrt"变异成为"*"，但这种变异造成原来语法树结构不合法。

针对GA(遗传算法)和GP算法的不同特点，生物学家Ferreira提出了GEP算法。GEP算法融合了GA和GP的优点，在基因型（内部表示）形式上，它继承了GA的定长线性编码的特点；在表现型（外部表示）上，它继承了GP的树形结构的特点，用简单编码解决复杂问题。为了解决染色体存活问题，GEP引入了基因头尾约束，保证染色体在遗传操作下全部存活。

2、GEP设计思想

GEP与GA和GP本质的区别在于个体编码方式。GEP在基因型上将个体编码为固定长度的线性串，解码时通过特殊的规则将线性串映射成大小、形状都不相同的非线性实体树，从而实现利用简单编码解决复杂问题。

（1）编码规则

这里先要引入一个概念：基因（Gene）。基因与染色体都是用于种群个体的基因型（内部表示）。一个个体就是一个染色体，而一个染色体可以包含一个基因也可以包含多个基因（具体包含多少个基因可以根据求解问题的复杂程序在算法执行前设定）。

组成GEP基因的编码符号分为两种：函数符号集（运算符和其他初等函数），通常简称F；终端符号集（变量和常数等），通常简称T。基因编码分为两部分：头部（Head）和尾部（Tail）。。其中头部的符号可以来自F、T符号集，而尾部的符号只能来自T符号集。

设头部长度为h，尾部长度为t，则两者之间存在以下关系：

其中n为函数符号集F中函数最大操作目数。

例：假定一个基因由F=｛q，*，+，-，/｝(q，平方根)，T={a，b}两个符号集的元素组成，则F集合中最大操作目数n=2 。若头部长度h=15 ，则尾部长度：

t=15*（2-1）+1=16

基因的长度为h+t = 31。下图为一个基因的示例（粗体标识的为尾部）

（2）解码规则

基因转换为对应的表达树的过程：

· 取出基因的第一个元素作为表达式树的根，即这个元素构成表达式树的第一行；

· 依次从基因队列中取出元素放到上一级元素的下边，所放顺序为从左向右，所放数量为上一级元素的参数个数；

· 重复上述操作，直至表达树所有分支的最下级元素都为T集合元素；

例：

基因：

解码得到的表达式树：

大家可能会发现基因总长为31位，但解码得到的表达式树只用到了基因中的前8位，基因有效位数为8。这是正常的，这个特点正是GEP精妙之处，即基因中不是所有元素都参与表达式树的构造。基因中可能存在未编码的部分。这种编码规则有什么好处呢。我们来看一个例子，让我们"见证奇迹"：

假设上边例子中的基因发生了变异，基因中第6位上的"a"变异为"＋"：

解码后的表达式树为：

基因的有效位数为20，以过变异表达式树的大小和形状发生了很大的变化。通过遗传操作，表达式树不仅可以变长，也可以变短。比如把原基因中第3位由"＋"变为"Q"，得到：

表达式树为：

基因的有效位数为4，表达式树变得更为短小。

上述例子说明，虽然GEP基因的长度是固定的，但是它们具有转换成不同大小和形状的表达式树的潜力。最简单的情况是整个表达式树仅由一个元素构成（当基因的第一个元素就是T集合元素），最复杂的情况是表达式树由基因中的所有元素构成（当头中所有元素都是函数，且函数都具有最大参数个数n）。

只要严格遵守基因编码规则，即始终保持头部和尾部的边界禁止表示函数的符号出现在尾部，不论对基因进行多么复杂的变异、重组等操作，产生的表达式树始终都是正确。

3、多基因染色体

GEP算法引入多基因染色体概念，即染色体可以由多个等长的基因构成。多基因染色体中每一个基因对应一个表达式子树。子树可以通过事先定义的连接符连接成一个大的表达式树。对于每个求解问题，基因的数目和基因头的长度都可以根据情况来选定。多基因染色体在复杂问题的求解中非常有用。

例：染色体包含三个基因，每个基因长度均为13

图中a为三基因染色体，b为染色体所包含的三个基因解码得到的三个表达子树。

如果大家对此话题感兴趣，欢迎大家点击"关注"。同时大家还可以点击下边“了解更多”链接，下载其中SFM系统，SFM就是基于GEP算法研发的一款函数挖掘软件。通过SFM试用，对大家理解GEP的设计思想会很有帮助。