基于小生境技术的改进基因表达式编程算法的研究

李煜林

摘  要：提出一种改进的基因表达式编程方法，针对传统基因表达式编程容易出现过早收敛或者陷入局部收敛，进化后期种群多样性软弱及遗传操作随机性大等问题，加入小生境技术对算法进行改进。实验表明，改进的GEP算法能够克服传统GEP算法的不足。

关键词：基因表达式;小生境算法;劃分半径;动态变异策略

中图分类号：TP18          文献标志码：A         文章编号：2095-2945（2019）07-0028-03

Abstract： An improved gene expression programming method is proposed to solve the problems of premature convergence or local convergence， weak population diversity and high randomness of genetic operation in traditional gene expression programming. Niche technology is added to improve the algorithm. Experiments show that the improved GEP algorithm can overcome the shortcomings of the traditional GEP algorithm.

Keywords： gene expression; niche algorithm; partition radius; dynamic mutation strategy

引言

基因表达式编程（gene expression programming，简称GEP）是由葡萄牙进化生物学家兼计算机学家Ferreira于2000年提出的遗传计算家族中的新算法，这种新算法融合遗传算法（Genetic Algorithms，简称GA）中定长线性编码的简单方便的优势与遗传编程（Genetic Programming，简称GP）树形结构灵活多变的优点[3]。研究表明，基因表达式编程算法及针对它的各种改进算法，其最大的优势是可以利用简单的编码来解决相对繁琐的问题，在数据挖掘和函数发现等方面有着突出的效果。当前GEP广泛应用到化学、医学、股票预测、灾害预测、产量预测、经济、管理、测绘等多个领域。一些研究学者发现GEP也存在一些不足之处，如收敛过早、进化后期种群多样性弱、陷入局部收敛、随机操作性强等等。

1 小生境技术

小生境技术借鉴了生物进化过程中，往往喜欢和特征相同的物种相聚在一起，共同繁衍后代的方式，将每一代遗传的个体进行了分类，然后在每个类中选取适应度较高的个体构成一个优秀群体，个体在种群中，以及不同种群之间进行杂交、变异产生新一代个体群，并对新产生的个体群进行适应度评估，通过利用预选机制或排挤机制或分享机制根据实际来解决不同的问题。研究表明，这种小生境技术的遗传算法在解决所需问题时，能够很好的保持种群个体的多样性，也有相对较高的寻优能力和更快的收敛速度。

2 算法的改进

2.1 引入小生境双重划分半径

假设在一个种群当中，通过计算所有个体适应度，选择出N个最优个体，在种群中划分出N个小生境，为了将种群中的个体进行划分，引入小生境的双重划分半径r1和r2，计算任意两个最优个体的共享度Dij，根据任意两个最优个体之间的共享度距离来确认划分半径。

利用双重划分半径将种群中的所有个体划分为最优个体，次优个体，一般个体和排挤个体。次优个体一般处于半径为r1的范围中，一般个体处于半径r1和r2之间，排挤个体处于半径r2之外。通过这样形式的个体划分，目的就是使种群中个体在遗传操作过程不像传统GEP的遗传操作那样随机选择，使遗传操作变的有针对性，可以有效的提高算法的收敛速度。

2.2 个体进行分类遗传操作及动态变异策略

传统GEP中遗传操作的变异、插串、重组等操作是针对种群的所有个体进行的，遗传操作的过程是通过设置固定的概率随机进行，使得算法遗传操作的随机性比较大，这将一定程度上影响算法在寻找全局最优解的速度，在传统GEP的三种遗传操作中，变异算子的遗传操作性是最强的，为了保持种群的丰富性，从而预防过早收敛的现象，传统GEP采用较小的变异概率，这很大程度上是以牺牲收敛速度为代价的。因此，本文通过小生境双重划分半径将种群中的个体进行划分之后进行分类遗传操作，并设计一种动态变异策略，能够有效的降低遗传操作的随机性，在维持种群多样性的同时也在一定程度上提高了算法的收敛速度，具体方法如下：

首先利用小生境双重划分半径对种群中的个体进行分类，划分的类别包括最优个体、次优个体、一般个体和排挤个体。

其中最优个体采用克隆操作，具体操作步骤如下：

（1）创建初始种群;

（2）计算个体适应度;

（3）选择最优个体种群C;

（4）将最优个体种群C克隆，并以较小的概率P1发生变异，形成临时种群C1加入初始种群。

种群中的次优个体由于小生境分享机制强制降低了其个体适应度，但是其个体基因表现型还是优良的，仅次于最优个体，为了保持种群多样性，我们将次优个体按较大的概率P2发生变异，避免出现适应度相对较高的个体扎堆现象;对于种群重的排挤个体，同样被小生境分享机制提高了其个体的适应度，也就意味着其被选择的机率被提高，然后将排挤个体按一定的概率P3发生变异，以便得到更好基因个体。

经过这种分类遗传操作之后，种群中的最优个体克隆变异，次优个体和排挤个体通过动态变异策略调整变异概率之后，弱势群体适应度被提高，被选择繁衍的概率被加大，种群中的个体多样性明显变得丰富，同时由于次优个体被大概率的突变使得与最优个体基因表现性相似的个体明显被减少，避免次优个体扎堆最优个体的现象，有助于预防算法进化过程出现过早收敛和陷入局部收敛，引领进化走向全局最优。

结合小生境算法和传统GEP算法，通过上述两点改进之后得到改进GEP算法，具体算法框架如下：

（1）创建初始种群;

（2）设置基因表达式控制参数;

（3）计算种群中个体适应度;

（4）判断每一代是否达到最优解，如果达到，输出结果，算法结束;否则继续下一步;

（5）按照轮盘赌法选择输出个体进行下一步;

（6）选择最优个体群体，设置克隆参數，进行克隆操作;

（7）确定小生境个数，计算最优个体之间的共享度距离sD;

（8）设置划分参数，利用小生境双重划分半径划分出次优个体、一般个体和排挤个体;

（9）分别计算次优个体以及排挤个体与最优个体的共享度Si，得到调整适应度fs（i）;

（10）设置动态变异策略参数，遗传操作;

（11）生成新的个体种群，返回第三步。

3 仿真实验与分析

为了验证改进的GEP在解决传统GEP进化后期种群多样性软弱，过早收敛，随机操作性等问题是否有效，设计模拟实验分析改进效果。

根据函数y=a3-a2-a-1在取值范围[-5，5]中随机选取，得到平均分布的30组数据作为训练数据，其他的参数设置如表1所示。

4 结论与分析

从图1我们可以发现，随着进化代数不断增加，传统GEP中种群平均共享度距离明显降低，也就是说此时种群多样性也随之降低，由于种群多样性的不足，算法容易出现过早收敛或者陷入局部收敛，无法达到全局最优，导致在对函数的挖掘过程中出现挖掘不成功的现象，而改进的GEP在进化代数增加的过程中，仍然能够保持较大的种群平均共享度距离，也就是能够保持种群多样性，这样也就能够避免算法过早收敛或陷入局部收敛，也不会出现函数挖掘不成功的现象;从表2我们可以看出，改进的GEP在达到收敛的平均代数远远小于传统GEP，改进的GEP在收敛速度上要优于传统GEP。

为此，我们可以得出结论，利用小生境算法与传统基因表达式编程算法相结合，采用本文提出的小生境双重划分半径对种群中的个体进行划分，对划分的个体分类遗传操作，并设计动态变异策略实施个体动态调整变异概率，得到改进的基因表达式编程算法，能够有效的解决传统GEP中种群多样性软弱的问题，防止过早收敛和陷入局部收敛，通过收敛速度的对比我们可以发现，由于改进的GEP采用个体分类操作和动态变异策略，能够有效地解决传统GEP随机操作性过大的问题，同时在收敛速度上也有所提高，也就意味着本文中对传统GEP的改进是具有效果的。

参考文献：

[1]元昌安，彭昱忠，覃晓，等.基因表达式编程算法原理与应用[M].北京：科学出版社，2010.

[2]Fatih Ozcan. Gene expression programming based formulations for splitting tensile strength of concrete[J].Construction and Building MATERIALS，2012，26（1）：404-410.

[3]Piotr， Ewa. Agent～Based Gene Expression Programming for Solving the RCPSP/max Problem[J]. ICANNGA 2009， LNCS 5495， 2009：203-212.

[4]刘小生，李胜，赵相博.基于基因表达式编程的PM_（2.5）浓度预测模型研究[J].江西理工大学学报，2013，05：1-5.

[5]王艳.基因表达式编程在时序变形数据处理中的应用[J].河南科技，2014，24：153.