采用混合策略的改进基因表达式编程*

王超学，张婧菁，吴书玲

西安建筑科技大学 信息与控制工程学院，西安 710055

采用混合策略的改进基因表达式编程*

王超学，张婧菁+，吴书玲

西安建筑科技大学 信息与控制工程学院，西安 710055

WANG Chaoxue,ZHANG Jingjing,WU Shuling.Improved gene expression programming algorithm used by hybrid strategy.Journal of Frontiers of Computer Science and Technology,2017,11(1):163-170.

基因表达式编程（gene expression programming，GEP）是一种新型的进化算法，在函数发现领域具有很好的应用。针对传统GEP存在的不足，提出了一种采用混合策略的改进基因表达式编程算法（improved gene expression programming algorithm used by hybrid strategy，HSI-GEP）。主要有两点改进：（1）采用镜像和重启机制对种群中的较差个体进行替换，以提高种群的质量和多样性；（2）在原有锦标赛选择之前引入克隆选择，以提高算法对优质解的开采能力。与权威文献中改进的GEP算法关于函数发现问题的大量对比实验表明，HSIGEP算法求解质量高，收敛速度快，具有明显的竞争力。

基因表达式编程（GEP）；镜像替换；重启机制；克隆选择

1 引言

基因表达式编程（gene expression programming，GEP）[1-2]由Ferreira在2001年提出，是进化算法的新成果。GEP继承了遗传算法（genetic algorithm，GA）与遗传编程（genetic programming，GP）的优点，具有GA编码、操作的简洁性和GP求解复杂问题强有力的空间搜索能力，成为函数发现的有力工具，并且在机械工程、材料科学、医学等领域取得了广泛应用。如Kara[3]使用GEP建立了没有箍筋的钢纤维加强混凝土梁的切变强度的经验模型，在预测钢纤维加强混凝土梁的切变强度方面表现出了优势。Traore等人[4]使用GEP建立了西非热带干旱地区的土壤水分蒸发蒸腾损失总量模型，与其他方法对比后发现GEP模型的精确度更高。

但是在实际应用中GEP依然存在着收敛速度慢，容易陷入局部最优的问题。目前，许多学者在函数发现领域对传统的基因表达式编程算法进行不同程度的改进，主要有：林毅申等人[5]将小生境技术引入到GEP中，并将聚类分析与遗传机制相结合来控制收敛的小生境数目，提高算法的全局寻优能力。姜玥等人[6]采用远缘繁殖和动态适应度函数策略对种群的进化进行干预，增加了多样性并且有利于选择优质个体，提高了标准GEP的性能。莫海芳等人[7]采用GEP编码的克隆选择算法实现函数建模，提高解的质量的同时也提高了收敛速度。张永强等人[8]引入优质种群产生策略和变种群策略来提高算法的收敛速度和种群的多样性。

为了进一步改善GEP的性能，本文提出了一种采用混合策略的改进基因表达式编程算法（improved gene expression programming algorithm used by hybrid strategy，HSI-GEP）。主要改进点如下：采用镜像和重启机制对较差个体进行替换，提高算法的全局搜索能力；在原有锦标赛选择之前引入克隆选择，提高算法对优质解的开采能力。为了验证HSI-GEP算法的优越性，本文针对函数发现问题与权威文献中改进的GEP算法进行了对比实验。结果表明，HSIGEP算法在进化过程中能够有效地克服停滞和早熟收敛现象，具有明显的竞争力。

2 GEP简介

GEP综合了遗传算法和遗传编程的优点，具有更强的问题解决能力。GEP与二者的本质区别在于：在GA中个体由固定长度的线性串来表示，GP中个体由不同大小和形状的非线性实体所表示，而GEP将个体先编码为固定长度的线性串，再表示成大小和形状都不同的非线性实体。

GEP算法可以定义为九元组：GEP={C,E,P0,M,φ,Γ,Φ,Π,Τ}。式中C为个体的编码方式；E为个体适应度评价函数；P0为初始种群；M为群体规模；φ为选择算子；Γ为重组算子；Φ为变异算子；∏为插串算子；T为遗传运算终止条件。

标准GEP算法的操作流程如下[9]：（1）输入相关参数，创建初始化群体；（2）计算每个个体的适应度函数，若不满足终止条件，继续下一步，否则结束；（3）保留最优个体；（4）选择操作；（5）变异；（6）插串操作（倒串、IS插串、RIS插串、基因变化）；（7）重组操作（单点重组、两点重组、基因重组）；（8）转到（2）。

3 采用混合策略的改进基因表达式编程

本文提出的采用混合策略的改进基因表达式编程算法（HSI-GEP）流程图如图1所示。

3.1 适应度函数

统计学中，用于评价两组数据符合程度的方法

更多是采用复相关系数法。本文的适应度函数为：

即统计学中的复相关系数的平方[10]。

其中，yj表示观测数据；表示利用公式从观测数据计算得到的yj的预测值；为变量y的平均值；SSE为残差平方和；SST为总离差平方和。

Fig.1 Flowchart of HSI-GEP图1 HSI-GEP算法流程图

3.2 终止条件

在进化操作中，终止条件有多种判断标准。例如适应度值达到最大值1，或者种群的迭代次数达到预先设定值。本文算法的终止条件采用的是最大迭代次数。

3.3 种群信息熵

种群多样性代表种群中个体间的差异程度。多样性是影响进化算法性能的关键因素。目前，评价种群多样性的方法主要有适应度方差[11]、信息熵[12]、带权的多样性测度[13]等。信息熵是一种表示状态多样性和丰富程度的定量计量标尺。与其他方法相比，采用信息熵来评价种群的多样性，能够较容易地与种群中的个体相对应，更能够客观地反映其多样性的含义，易于理解。

本文采用信息熵的方式来判断种群多样性的优劣。由信息熵的计算公式可知，当种群中的所有个体在同一基因位置上的等位基因各不相同时，种群的信息熵最大，个体间的差异度最大，此时种群的多样性最好。衡量种群多样性的信息熵的具体计算方式如下：

（1）统计出第i个函数符或终止符在种群的同一基因位置j上出现的次数Cij。

（2）求出第i个函数符或终止符在该种群的同一基因位置j上出现的概率Pij：

（3）计算种群的信息熵：

其中，L为每个个体的基因位置的总数，即每个个体的总长度；S为函数符和终止符的总数。

3.4 镜像和重启机制

在进化过程的初期，种群的多样性比较高，但随着迭代次数的增大，种群中的多样性就会降低。依据这个思想，本文把种群多样性的判断分为3个阶段，并且设定不同的阈值。当种群的多样性低于预先设定的阈值时，就采用镜像和重启机制替换掉部分较差的个体，提高种群多样性，增强空间搜索能力。具体操作步骤如下所示：

（1）分别计算理想种群和当前种群的多样性熵值，记为Hl和Hp。

（2）根据种群的最大迭代次数MaxGene，设置3个多样性判断阶段，分别为1～MaxGene/3、MaxGene/3～2×MaxGene/3、2×MaxGene/3～MaxGene，对应的种群阈值h可以分别设定为0.5、0.4、0.3。如果Hp＜h×Hl，则对当前种群进行镜像和重启操作。

（3）依据适应度把种群中的个体进行排序，然后选出适应度最差的m个个体和次差的n个个体。

（4）采用重启机制，即随机产生m个个体替换掉适应度最差的m个个体；采用镜像机制，即对适应度次差的n个个体进行镜像处理。镜像处理实际上是对于每一个个体中的函数符用其相对应的镜像函数符来替换。例如，functionSet={+，-，*，/，Sin，Cos，ln，exp}，则该函数符集合的镜像函数符集合为mirrorfunctionSet={-，+，/，*，Cos，Sin，exp，ln}。

3.5 选择算子

克隆选择算法的实质是先通过克隆繁殖优良个体，进而通过变异对其邻近区域进行搜索，从而选择出更优的个体。因此克隆选择具有收敛速度快，搜索精度高的特点。而锦标赛选择在一定程度上，也能避免过早收敛和停滞现象的发生。精英个体是种群进化到当前为止算法搜索到的适应度值最高的个体，它具有最好的基因结构和优良特性。精英策略就是算法在进化过程中，保证迄今出现的最优个体不会被选择、交叉和变异操作所丢失和破坏。本文在原有锦标赛选择之前引入了克隆选择，提出带有精英策略的混合选择操作。具体如下：

（1）根据个体的适应度从父本种群中选择最优的a%的个体。

（2）把选择的a%的个体均克隆b次，并对这些克隆后的个体进行变异操作。

（3）计算被选择的父本和变异后子代的适应度。如果某一个子代个体的适应度大于其父本和兄弟的适应度，则该子代个体将被选入下一代种群中；反之，则不选入。克隆选择后，被选择进入到下一代的克隆个体数量c最多等于被克隆的a%的个体数量[14]。

（4）采用竞赛规模为s的锦标赛选择算子从父本种群中选择剩余的N-c个个体，以满足种群规模N。

（5）找出该代中适应度最好的个体pbest，与目前为止保存的适应度最好的个体pmax进行比较，如果适应度pbest＞pmax，则用pbest对pmax进行更新；反之，则用pmax替换掉该代中适应度最差的个体。这样做的目的是保证最好的个体能够进入种群，参与各种遗传操作。

3.6 HSI-GEP算法机理分析

本文首先采用镜像和重启机制替换种群中的部分较差个体，向种群中引入一些新的个体和镜像个体，提高了种群的质量和多样性，进而提高了算法的全局搜索能力。其次引入了带有精英策略的混合选择操作，兼顾了算法的全局搜索和局部搜索，使得算法可以在优质解的区域展开更精细的局部搜索，缩短了寻优时间，提高了算法的收敛速度和对优质解的开采能力。

选择算子是进化算法中重要的算子，体现了自然界中优胜劣汰的基本规律，直接影响进化算法的性能。算法的收敛性是由选择算子来保证的。克隆选择算法是人工免疫算法的一种，文献[15]已经证明了该算法的收敛性。锦标赛选择是进化算法中常见的选择算子，可以在一定程度上保证算法的收敛性。文献[16]也已经证明了带有精英策略的GEP算法在函数发现中的全局收敛性。本文把克隆选择算法的思想与锦标赛选择结合起来，组成混合选择算子，在提高算法收敛速度的同时，并没有影响原来算法的收敛性。同时，带有精英策略的混合选择操作进一步保证算法在理论上以概率1收敛到全局最优解。

4 实验和结果

本文设计了两个实验来验证HSI-GEP算法在函数发现领域的有效性和竞争力，实验的运行参数设置见表1。实验程序使用Matlab 2009a实现，实验环境为Windows 7操作系统，Intel Core i7 3.40 GHz处理器，4 GB内存。

4.1 HSI-GEP算法的有效性实验

Ferreira在文献[1]中采用的F函数具有自变量个数少，维度高的特点，多次出现在各个权威文献中，具有一定的对比价值。为了评价HSI-GEP算法各因子的影响效果，本文采用F函数来验证HSI-GEP算法的有效性，具体公式如式（5）所示。

其中，an是由非负整数组成的，an=0,1,2,…。实验中，首先根据F函数随机产生10组训练样本数据集，然后利用HSI-GEP算法对样本数据集进行挖掘，得到反映其规律的函数表达式，再利用训练样本数据的自变量，根据挖掘出的函数表达式求出其目标值。对数据集重复50次挖掘实验，最后将实验结果与标准GEP算法和文献[17]中的DS-GEP算法进行对比。实验1的测试结果如表2所示。

Table 1 Parameter setting of experiments表1 实验中算法的运行参数

Table 2 Test results of experiment 1表2 实验1测试结果

从表2中可以看出，HSI-GEP算法的寻优率和平均收敛代数明显优于DS-GEP和GEP算法。为了验证选择算子的有效性，在满足其他条件都相同的情况下，本文做了两个对比实验：一个实验采用普通的锦标赛选择算子；另一个采用本文的选择算子。图2和图3分别为二者的进化曲线图，图中红色实线代表最优适应度值，蓝色虚线代表平均适应度值。

Fig.2 Evolution curve of experiment with tournament selection图2 带锦标赛选择的进化曲线图

Fig.3 Evolution curve of experiment with selection operator in this paper图3 本文选择算子的进化曲线图

从图2和图3中可以明显看出，由于该函数比较简单，二者都可以达到全局最优。但是在锦标赛选择之前加入克隆选择后，算法取得最优解的收敛代数明显减小。图3在不到20代时就已经达到最优，说明了引入克隆选择后能明显提高种群的收敛速度。

信息熵是衡量种群多样性的标志，信息熵与种群多样性成正比。从图4加镜像和重启机制前后信息熵对比曲线图可以看出，随着进化代数的不断加大，种群的信息熵逐渐减小，加入镜像和重启机制后，种群的信息熵明显提高。这说明引入镜像和重启机制能够明显提高种群的多样性，这也是HSI-GEP算法能够达到全局最优的原因。

Fig.4 Comparison of information entropy before and after using mirror and reset mechanism图4 加镜像和重启机制前后信息熵对比图

4.2 HSI-GEP算法的先进性实验

为了测试HSI-GEP算法的先进性，本文选取最新文献DS-GEP[17]、S-GEP[18]、MDC-GEP[19]、DG-GEP[20]中的算法进行对比测试。测试函数与文献[18-19]相同。具体函数表达式如式（6）～（15）所示。运行时参数设置见表1。实验测试结果见表3。

Table 3 Test results of experiment 2表3 实验2结果统计表

从表3中可以看出，与DS-GEP、MDC-GEP、SGEP、DG-GEP算法相比，HSI-GEP算法对于大多数函数，最大适应度、最小适应度和平均适应度都有明显的提高，说明了HSI-GEP算法的先进性和竞争力。对于较为简单的函数F2和F6，HSI-GEP算法能够达到最大适应度值1，但是F3、F5、F10函数的部分值却小于（非常接近）MDC-GEP算法。这是因为GEP算法本身是一种随机算法，且算法的运行代数、性能参数等都对实验有很大的影响，每个函数取得最优值所依赖的运行代数和性能参数都会不同，所以在算法的性能参数相同的条件下，少数函数取不到更优解的情况是存在的。

5 结束语

本文对标准GEP算法进行改进，提出了一种采用混合策略的改进基因表达式编程算法，并通过函数发现问题来验证该算法的有效性和竞争力。文中提出了两个改进点：首先，针对自然进化过程中由于种群多样性缺失导致的早熟收敛现象，通过镜像和重启机制替换掉部分较差个体，以增加种群的质量和多样性，提高算法的全局搜索能力。其次，在锦标赛选择之前引入了克隆选择，进一步在优质解的搜索区域中展开更精细的局部搜索，提高了对优质解的开采能力。通过与权威文献中改进的GEP算法关于函数发现问题的大量对比实验表明，改进后的HSI-GEP算法具有明显的竞争优势。

虽然HSI-GEP算法在本文的两次实验中均表现了优越的性能，但还是存在一定的问题，例如少数函数取不到更优解，算法参数的合理性选择，测试问题领域比较局限等。因此，优化算法的性能参数和扩大测试问题领域将是未来研究的重点。

[1]Ferreira C.Gene expression programming:a new adaptive algorithm for solving problems[J].Complex Systems,2001, 13(2):87-129.

[2]Ferreira C.Function finding and the creation of numerical constants in gene expression programming[M]//Advances in Soft Computing.London:Springer,2003:257-266.

[3]Kara I F.Empirical modeling of shear strength of steel fiber reinforced concrete beams by gene expression programming[J]. Neural Computing&Applications,2013,23(3/4):823-834.

[4]Traore S,Guven A.New algebraic formulations of evapo transpiration extracted from gene-expression programming in the tropical seasonally dry regions of west africa[J].Irrigation Science,2011,31(1):1-10.

[5]Lin Yishen,Peng Hong,Wei Jia.Function finding in niching gene expression programming[J].Journal of Chinese Computer Systems,2008,29(11):2111-2114.

[6]Jiang Yue,Tang Changjie,Zheng Xiuming,et al.Outbreeding strategy with dynamic fitness in gene expression programming[J].Journal of Sichuan University:Engineering Science Edition,2007,39(2):121-126.

[7]Mo Haifang,Kang Shun.Clonal selection algorithm with GEP code for function modeling[J].Pattern Recognition andArtificial Intelligence,2013,26(9):878-884.

[8]Zhang Yongqiang,Xiao Jing.Anew strategy for gene expression programming and its applications in function mining [J].Universal Journal of Computer Science&Engineering Technology,2010,1(2):122-126.

[9]Yuan Chang'an,Peng Yuzhong,Qin Xiao,et al.The principle and application of gene expression programming algorithm[M].Beijing:Science Press,2010:30-33.

[10]Zuo Jie.Gene expression programming core technology research[D].Chengdu:Sichuan University,2004.

[11]Shan Bing,Ni Shihong,Zha Xiang.GEP based on population diversity measure by variance of individuals’fitness[J]. Computer Engineering and Design,2013,34(9):3094-3098.

[12]Shen Huihui,Han Shenglian.A method to calculate the immune algorithm diversity and affinity[J].Journal of Chongqing Vocational&Technical Institute,2004,13(4):125-126.

[13]Li Taiyong,Tang Changjie,Wu Jiang,et al.Adaptive population diversity tuning algorithm for gene expression programming[J].Journal of University of Electronic Science and Technology of China,2010,39(2):279-283.

[14]Liu Y C,Hsieh J C.A hybrid selection algorithm for time series modeling[J].Soft Computing,2014,19:1-11.

[15]Yu Ying,Hou Chaozhen.Convergence analysis of clonal selection algorithm[J].Computer Application Research,2006, 23(6):96-98.

[16]Yuan Chang'an,Tang Changjie,Zuo Jie.Function mining based on gene expression programming—convergency analysis and remnant-guided evolution algorithm[J].Journal of Sichuan University:Engineering Science Edition,2004,36 (6):100-105.

[17]Wang Chaoxue,Zhang Kai,Dong Hui,et al.Double systemgene expression programming and its application in function finding[C]//Proceedings of the 2014 International Conference on Mechatronics,Control and Electronic Engineering,Shenyang,Aug 29-31,2014:357-361.

[18]Peng Yuzhong,Yuan Chang'an,Qin X,et al.An improved gene expression programming approach for symbolic regression problems[J].Neurocomputing,2014,137(15):293-301.

[19]Xuan Shibin,Liu Yiguang.GEP evolution algorithm based on control of mixed diversity degree[J].Pattern Recognition andArtificial Intelligence,2012,25(2):187-194.

[20]Liu Qihong,Tang Changjie,Hu Jian.Gene expression programming based on diversity-guided grading evolution[J]. Journal of Sichuan University:Engineering Science Edition,2006,38(6):108-113.

附中文参考文献：

[5]林毅申,彭宏,韦佳.小生境基因表达式编程在函数发现的研究[J].小型微型计算机系统,2008,29(11):2111-2114.

[6]姜玥,唐常杰,郑明秀,等.基因表达式编程中动态适应的远缘繁殖策略[J].四川大学学报:工程科学版,2007,39 (2):121-126.

[7]莫海芳,康顺.采用GEP编码的克隆选择算法实现函数建模[J].模式识别与人工智能,2013,26(9):878-884.

[9]元昌安,彭昱忠,覃孝,等.基因表达式编程算法原理与应用[M].北京:科学出版社,2010:30-33.

[10]左劼.基因表达式编程核心技术研究[D].成都:四川大学, 2004.

[11]单兵,倪世宏,查翔.基于适应度方差度量种群多样性的GEP算法[J].计算机工程与设计,2013,34(9):3094-3098.

[12]沈慧慧,韩生廉.免疫算法多样性及亲和性的一种计算方法[J].重庆职业技术学院学报,2004,13(4):125-126.

[13]李太勇,唐常杰,吴江,等.基因表达式编程种群多样性自适应调控算法[J].电子科技大学学报,2010,39(2):279-283.

[15]于瀛,侯朝桢.一种克隆选择算法的收敛性分析[J].计算机应用研究,2006,23(6):96-98.

[16]元昌安,唐常杰,左劼.基于基因表达式编程的函数挖掘——收敛性分析与残差制导进化算法[J].四川大学学报:工程科学版,2004,36(6):100-105.

[19]宣士斌,刘怡光.基于混合差异度控制的基因表达式编程[J].模式识别与人工智能,2012,25(2):187-194.

[20]刘齐宏,唐常杰,胡建.多样性制导分段进化的基因表达式编程[J].四川大学学报:工程科学版,2006,38(6):108-113.

WANG Chaoxue was born in 1967.He received the Ph.D.degree in computer science from Xi'an University of Technology.Now he is a professor at Xi’an University of Architecture and Technology,and the member of CCF.His research interests include artificial intelligence and data mining.

王超学（1967—），男，陕西西安人，西安理工大学计算机科学专业博士，现为西安建筑科技大学教授，CCF会员，主要研究领域为人工智能，数据挖掘。

ZHANG Jingjing was born in 1990.She is an M.S.candidate at Xi’an University of Architecture and Technology. Her research interest is intelligent software development.

张婧菁（1990—），女，山西运城人，西安建筑科技大学信息与控制工程学院硕士研究生，主要研究领域为智能软件开发。

WU Shuling was born in 1991.She is an M.S.candidate at Xi’an University of Architecture and Technology.Her research interest is intelligent modeling and forecasting.

吴书玲（1991—），女，河南驻马店人，西安建筑科技大学信息与控制工程学院硕士研究生，主要研究领域为智能建模及预测。

Improved Gene Expression ProgrammingAlgorithm Used by Hybrid Strategy*

WANG Chaoxue,ZHANG Jingjing+,WU Shuling
School of Information and Control Engineering,Xi’an University ofArchitecture and Technology,Xi'an 710055,China
+Corresponding author:E-mail:494945856@qq.com

Gene expression programming(GEP)is a new evolutionary algorithm,which has the very good applications in the field of function finding.In view of the insufficiency of traditional GEP,this paper puts forward an improved gene expression programming algorithm used by hybrid strategy(HSI-GEP).This paper has two improvements:(1)Using mirror and reset mechanism to replace the worst individuals of population,to improve the quality and diversity of population;(2)Introducing the clonal selection before tournament selection operator in order to improve the mining ability of algorithm about high qualities.A large number of experiments have been carried on the function finding problems,and the results show that the algorithm is of high quality,has fast convergence rate and obvious competitiveness compared with the improved GEP in authoritative literature.

gene expression programming(GEP);mirror replace;reset mechanism;clonal selection

A

：TP311

10.3778/j.issn.1673-9418.1509046

*The National Natural Science Foundation of China under Grant No.31170393(国家自然科学基金);the Natural Science Foundation of Shaanxi Province under Grant No.2012JM8023(陕西省自然科学基金).

Received 2015-09,Accepted 2016-02.

CNKI网络优先出版:2016-02-03,http://www.cnki.net/kcms/detail/11.5602.TP.20160203.1126.002.html