基于表现型的基因表达式编程解空间模型研究-郭勇.pdf

《基于表现型的基因表达式编程解空间模型研究-郭勇.pdf》由会员分享，可在线阅读，更多相关《基于表现型的基因表达式编程解空间模型研究-郭勇.pdf（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第49卷第5期2017年9月工程科学与技术ADVANCED ENGINEERING SCIENCESV0149No5Sept2017信息工程 DOI：1015961jjsuese201601393基于表现型的基因表达式编程解空间模型研究郭 勇1，何 锫23+，张国锋1，郭顺超1，司永洁1(1黔南民族师范学院计算机与信息学院，贵州都匀558000；2广州大学计算机科学与教育软件学院，广东广州510006；3武汉大学软件工程国家重点实验室，湖北武汉430072)摘要：基因表达式编程(gene expression programming，GEP)解空间模型理论对算法性能的改进有现实指导意义。公开文

2、献对GEP解空间模型的研究较少，鲜见针对GEP表现型的理论研究。基于此，提出一种基于表现型的GEP解空间模型。首先，通过定义GEP染色体表现型高度，给出单基因染色体和多基因染色体表现型高度确定上界的定理及证明，利用GEP算法自身函数发现的能力，探索出操作符集最小目数为l或2的GEP染色体表现型高度上界计算的通项公式，以保证GEP表现型解空间模型的确定有界性与可计算性。其次，以GEP表现型高度的确定上界定理为基础，构建基于表现型的GEP解空间模型，总结GEP表现型解空间模型的性质和定理。通过进一步定义GEP表现型的完全解空间概念，对最优解在GEP表现型解空间和完全解空间中的分布特征进行探索研究，

3、获知在完全解空间中最优解随子空间序号的增长呈大比例增加的分布特征。基于表现型空间模型知识，提出限制GEP种群搜索空间的基本思想与控制策略，利用模型知识合理地解释公开文献中多种GEP改进算法的有效性。关键词：基因表达式编程；表现型；符号回归；空间模型中图分类号：TP301 文献标志码：A 文章编号：20963246(2017)05011710Gene Expression Programming Solution Space Model Based on PhenotypeGUO Yon91，HE Pei2p，ZHANG Guofen91，GUO Shuncha01，&Yongjiel(1Sch

4、ool ofComputer andInforQiannanNormalUnivforNationalities，Duyun 558000，Chma；2School ofComputer SciandEducationalSoftware，Guangzhou Universi够，Guangzhou 510006，China；3State Key LabofSoftware Eng，Wuhan Univ，Wuhan 430072，Chma)Abstract：The theory of solution space model has practical significance to impro

5、ve the performance of Gene Expression Programming(GEP)al-gorithmsThere are few studies on the GEP solution space model，and the theoretical research on GEP phenotype is also SCarceTo address thisproblem，a GEP solution space model based on phenotype was proposedFirstly，by defining the height ofGEP clr

6、omosome phenotype，a theoremand the proofofthe upper bound ofsingle gene chfomosome and polygene c11romosome manifestation were givenTo ensure the boundedness andcalculability ofthe GEP phenotype solution space model，the general formula ofheight upper bound ofGEP cllromosome phenotype with the minimu

7、m number ofoperators 1 or 2 was calculated，by using the ability ofGEP algorithm to find out the functionSecondly,on basis ofthe definitionfor upper bound theorem of GEP phenotype height，the GEP solution space model based on phenotype was constructed，and the properties and the-orems ofGEP phenotype s

8、olution space model were summarizedBy further defining the concept ofthe complete so!ution space ofthe GEP phenotype，the distribution of the optimal solution in the GEP phenotype solution space and the complete solution space were exploredIt was foundthat the optimal solution ofthe subspace in the c

9、omplete solution space largely increased in proportion to the order number of subspaceBased onthe knowledge ofphenotypic spatial model，the basic idea and control strategy oflimiting the GEP population search space were put forward，andtlle effectiveness ofvarious GEP improvement algorithms in the lit

10、erature was explained by the theories ofspace model，Key words：gene expression programming；phenotype；symbolic regression；space modelFerreira：J：2001年提出基因表达式编程(gene expression programming，GEP)1一纠，GEP对未知系统及知识具有较强的探索能力。在GEP理论方面已有一定的研究成果：GEP概念的形式化描述【31、GEP基因收稿日期：20161224基金项目：国家自然科学基金资助项目(61170199)；贵州省科技厅联

11、合基金项目资助(20157727；2013GZl2215)作者简介：郭勇(1970)，男，副教授研究方向：演化计算；数据挖掘E-maih gzgy5555foxmailcom+通信联系人Etrnail：bk_he126eomhttp：jsueseijournals，cn http：jSuesesfueducn万方数据118 工程科学与技术 第49卷结构完备性定理证明p J、GEP最小残差平方和依概率收敛定理【4J、GEP马尔可夫收敛性定理一J、GEP模式定理睁j、GEP依条件完全收敛、几乎必然收敛且依均值收敛至全局最优解定理【6J。同许多进化算法一样，GEP的理论基础仍较薄弱，达不到严谨的理论

12、体系支持GEP算法的寻优。由于缺乏基础理论的支持，GEP性能的改进有一定的盲目性，改进方法的有效性主要依赖推断猜想和实验进行探索及佐证。在GEP解空间研究方面，文献7对特定GEP问题，采用条件云模型和问题数据集构建GEP搜索空间模型，通过控制、引导GEP演化过程中保持一定种群的多样性和搜索区域的限制，提高了整体进化效率和求解质量。文献8基于线性编码空间，在种群初始化时，按基因头部和尾部编码的均匀分布策略生成多样性优势种群，实验证实比随机初始化种群的计算效率高；文献9-10将“小生境”等思想应用到GEP中，通过GEP种群多样性和演化搜索方向的控制，实现对GEP演化效能的改进；文献11给出了特定G

13、EP染色体基因型与表现型表达空间大小的算法与证明，提出基于最佳genemap的初始化种群和演化控制的拓展算法AMGEP。上述文献涉及到不同视角和意义的GEP解空间模型雏形，虽然没有形成较完整的模型理论体系，但印证了基于一定的GEP解空间模型理论与认知，引导GEP演化过程的控制，以期获得GEP效能提升的可行性。本文针对符号回归问题，通过对GEP表现型的研究，获得GEP表现型的关键知识，构建基于表现型的GEP解空间理论体系，利用GEP表现型解空间模型揭示的知识，指引GEP演化效能改进策略的探索。1 GEP简介11 GEP个体的表示GEP中个体为染色体(chromosome)，染色体由基因(gene

14、)构成，分为单基因染色体和多基因染色体；多基因染色体的多个基因由连接运算符按“广度优先”进行连接解释。GEP基因编码取自操作符集(F)和终结符集(T)，基因编码分为头部(head)和尾部(tail)两部分，头部编码取自FU U，尾部编码取自兀尾部长度t与头部长度h满足关系式(1)：t=hx(M一1)+1 (1)式中，M黄tJF中操作符最大参数目数。例l：F=+，一，)，r=a，b)，h=6，贝0“+一aabaabbab”为合法的基因编码。12 GEP个体的基因型和表现型GEP单基因染色体的线性编码称为基因型，线性编码按“广度优先”构建的表达式树(expression tree，ET)称为表现型

15、。例1基因的表达式树如图1所示。多基因染色体的表现型，由固定连接符将各基因表达式树依“广度优先”连接而得。图1例1表达式树Fig1 Expression tree of example 113 GEP基因的解释GEP基因的解释指基因所表达的数学意义，标准GEP基因的解释通过对基因的表达式树“后序遍历”得到其数学函数表达式。如图l表达式树“后序遍历”所得的数学表达式为：f(a，6)=a26+1。14 GEP个体适应度及遗传算子GEP个体的适应度指将给定训练样本集所有样本变量值代入个体解释所得数学表达式，计算所得数学表达式值与样本整体差异的统计函数值，在符号回归问题中，一般使用绝对误差式、相对误差

16、等J作为适应度函数。GEP遗传算子主要包括选择、突变、重组、转座等，GEP通过选择算子和适应度函数控制种群的进化方向。2 GEP表现型解空间21关于“确定GEP问题”确定GEP问题求解包含以下3个确定内容：1)确定的操作符集F和终结符集死2)确定的基因头部长度h及尾部长度t，且满足11节的关系式(1)，对于多基因GEP还包括组成染色体的基因数及连接符。3)确定的适应度函数和控制阈值。确定GEP问题的求解及本文论述建立在以下2个假设下：假设1确定GEP问题个体的表达空间包含满足适应度控制阈值的解。假设2最小符号集的限定，To，数值型GEP中+，一，)F，逻辑型GEP中A，D，N)_oF。22 G

17、EP表现型解空间基本概念与性质定义1(表现型解空间) 确定的GEP问题所有可能个体的不同表现型集合称为GEP问题的表现型解空间，记为S。万方数据第5期 郭 勇，等：基于表现型的基因表达式编程解空间模型研究 119尽管基因的中性编码区域具有特殊的遗传意义，但最终个体的数学意义仍只由有效区域编码确定。具有相同有效编码区域的个体由于中性区域编码的差异，存在多个基因型不同的个体对应同一个表现型的情况，所以基因型的表达空间元素远多于表现型表达空间的元素。GEP依表现型的解释判断其是否作为问题解，基于GEP表现型解空间视角探索GEP改进的策略更接近其数学本质。定义2(最优解) 适应度达到演化控制阈值的个体

18、称为确定GEP问题的最优解，记为厂。表现型不同、数学意义上约简后具有相同数学表达式函数的最优解称为等价解。表现型和所解释的数学表达式函数都不相同，但适应度达到控制阈值的最优解称为非等价解。适应度未达到适应度控制阈值的解称为候选解，确定GEP问题的所有个体统称为可能解。定义3(最优解空间) 确定GEP问题的所有最优解的不同表现型集合，称为确定GEP问题的最优解空间，记为s 7。定义4(表现型高度) 个体表现型的节点从上向下按层级分布在表达式树的“树枝”上，表达式树的总层级数称为表达式树的高度，也称为个体的表现型高度，记为日。如图1表达式树的最上层为0层，即根节点层，最下面层为第4层，其高度H=5

19、。定义5(最简解) 确定GEP问题的表现型高度最小的最优解称为该GEP问题的最简解。根据GEP基因结构的完备性定理p J，满足11节式(1)的基因都能生成合法的表达式树，得GEP的表达式树具有以下性质：性质1 GEP表达式树最底层全部是叶节点。性质2在构建GEP表达式树时只有运算操作符节点才会产生下一级的表达式树层。性质3除根节点外，其他层级节点都是上一层级中某个操作符节点的子节点。定理1头部长度为h的单基因染色体的GEP表现型高度月r1)个基因构成多基因染色体的表现型高度然而+行。证明：1)当n=l时，即为单基因染色体，根据定理1，命题成立。2)假设n=k时，命题成立，即日h+k。将每个基因

20、视为一个整体，由于多基因染色体使用连接符按“广度优先”进行多基因的解释，得到1个“复合”单基因染色体的编码为：+G1G2G女 (2)式(2)中，共有肛1个连接运算符“+”，可视为1个头部长度为牲1的单基因染色体G，根据定理1，其表现型高度上界为：H(G)(七一1)+1。即日(G)k。3)当n=k+l时，染色体结构Ltn=k时增加了1个基因和1个连接运算符，即有k个连接符和斛1个基因，同样将每个基因视为整体所得“复合”单基因染色体G7的编码形如：+GlG2GGk+l (3)式(3)中，有阶连接运算符“+”，比假设2中的染色体增加1个连接运算符，G7的表达式树最多再增加1个表达式树层，所以单基因染

21、色体G7的表现型高度上界为：H(G)日(G)+1 (4)将假设2中的结果H(G)足代入式(4)得：H(G)k+1。由于标准GEP多基因染色体中的多个基因按“广度优先”连接，在G中无论有多少个基因，据定理1其高度H I：界：H(h7+1) (5)式(5)中，7等于“复合”基因的头部长度k，即H(1c+1)。原多基因染色体的表现型是把各基因G，的表达式树替换“复合”基因G7表达式树中的G，的位置而得，只有最底层某个基因的表达式树高度达到最大值(h+1)，所得G7的表达式树高度最大，如图2所示。一一j 一一一。j G 6一孓图2 多基因染色体表达式树Fig2 Multigene chromosome

22、 expression tree设最底层有基因G瑚表达式树达最大值h+l，占位替换G。后，可使G将所有基因的子表达式树替换后所得表达式树增加(h+1)一1层，即H(G7)(七+1)+(忍+1)一1。即得：H(G)h+(k+1)。命题对n=k+1成立，据假设12，命题对染色体基因数咒取任何自然数均成立，证毕。抖g朴010llllH(S。)，所以最优解仅分布在根据22节性质1及GEP的基因结构完备性可得 S的部分子空间中。万方数据第5期 郭勇，等：基于表现型的基因表达式编程解空间模型研究 121定理5若，为单基因染色体GEP问题的最简解，表现型高度扣风in，则在形中存在表现型高度为斛2或斛3的多个

23、等价解。根据第21节的假设2，定理5可通过在，表现型最底层叶节点上实施“嫁接术”进行例证。据性质4，设肭最底层的一个叶节点终结符为“a”，其表现型表达式树如图4所示。如图5(a)为数值型GEP问题在最底层的1个叶节点“a”上“嫁接”出表现型高度为斛2的多个等价解，考虑到“+、*”等运算符满足交换律，类似的等价解可卜图4表现型高度为k的表达式树示意图Fig4 An expression tree with a phenotype height of k达6个。图5(b)为逻辑型GEP问题“嫁接”出表现型高度为斛2和斛3的多个等价解，由于“AND”与“OR”满足交换律，类似的等价解可达7个。(a)

24、数值型等价解图5定理5例证示意图Fig5 Schematic diagram of Theorem 5定理5的推广可得：引 理若厂为单基因染色体GEP问题的最优解，表现型高度为Ht=k，则在矽中存在表现型高度为抖2或斛3的多个等价解。一方面，表达式树的最底层常不止1个叶节点，“嫁接”出的等价解更多。另一方面，表达式树倒数第2层可能存在多个叶节点，如图6N示，类似方法可“嫁接”出高度为胁1的多个等价解。同时对于数值型GEP问题，从图5(a)可观察到，“嫁接”所得表达式树最底层的叶节点会倍增，这种倍增情况从巩j。+2开始，即最优解具有在吁空间中以2的几何级数“倍增”的趋势。结合定理4、5及引理，递

25、推可得最优解在形子空间中的分布特征：ak+26a“1+a。考虑到顺高子空间中可能出现新的非等价解，也以相同方式增长，所以最优解在盱空间中会以加速“倍增”趋势随子空间序号的增长而剧增，称这种递增速度为“大比例”增长方式。最优解在S与中的分布如图7所示，图7中40Hmi。，日代表定N300的m，gm=Hm。，实线表示中最优解数量变化，虚线代表s中最优解数量的变化。图6“嫁接”示意图Fig6 Sketch of grafting1)总体上最优解随野空间表现型高度的增高而大幅增加。2)在区间凰，日，上，实线与虚线重合，表示在此区间上s与形的子空间相同，最优解的分布无差异，且遵循大比例增长趋势。脏此区间

26、各子空间中个体的基因有效编码区相对较短，解码用时少，又包含了大量最优解，有币IJGEP搜索到最优解，称此区间为最佳搜索区间，其上的所有子空间称为最佳搜索空间，简记为。3)在区间日，砜上，由于受基因头部长度限制，笏G劾万方数据122 工程科学与技术 第49卷yf最优J 晖数量)J 一，W0、 Sx(表现 高度)Ho H1 H。图7最优解分布示意图Fig7 Schematic diagram of optimal solution distribution无法表达定理4与定理5中的大量等价解，而嗍大比例的增加，s子空间中最优解明显少于形的子空间，同时还可能由于具体GEP问题的特殊性和无头部运算符使

27、用而无法表达出任何最优解，从而使最优解数量骤减，甚至无最优解，此区间上虚线的走向有不确定性。4)在区间【玩，oo】上，由于s受染色体结构长度的限制，不能表达更高的子空间，故元虚线，而陟实线仍可无限延伸，且最优解保持大比例速度剧增。依定理3和定理4及引理可得以下结论和启示：结论：单基因染色体确定GEP问题的基因头部长度h足够长时，如果最简解的高度耳。远小于定理3中的m，则在最佳区间。，m7上，最优解的分布依子空间sf序号i(f2巩i。)的增大呈大比例增加，控制GEP种群在此区间上子空间中搜索效率相对较好。启示1：对于单基因GEP问题，在无先验知识情况下，基因头部长度的选择是一个难点，选择过小可能

28、导致解空间S不包含最优解，太大又会导致整体解码时间大幅增加，同时产生大头部降低随机演化命中最优解概率的想法，从而选择较小的头部长度尝试多次问题的求解，据结论，加大尝试的头部长度不一定有想象的哪样困难，相反可能较快尝试出包含问题最优解的基因头部长度，从而提高GEP解决实际应用问题的效率。启示2：对于单基因GEP问题，根据结论和GEP表现型及解空间的特性，在区间【日血，m，上，更高子空间中的个体基因的有效编码区域更长，中性区域相对较短，子空间中表达的个体相对较少，最优解相对较多。在种群规模固定时，采取一定的演化策略和控制技术，使种群在更高表现型子空间中演化搜索，可期望提升GEP概率搜索到最优解的“

29、命中率”。基于24节的定理4和定理5，结合21节的假设1和假设2，可推定定理6。定理6确定GEP问题的完全解空间形中，当硷ami。时，连续的两个子空间与1中必定包含有该GEP问题的多个最优解。3探索实验31探索实验1实验目的：分析GEP演化过程中种群所有个体表现型高度和最优解表现型高度的取值范围。对下面的函数进行函数发现仿真实验：f(a)：嬖砌。使用单基因染色体，仁+，一，*，仁口)，基因头部长度为12，随机在-10，lo生成训练样本20组，种群个体数为100，适应度函数取相对误差，适应度控制阈值精度为001。运行GEP程序100次，利用Sqlite数据库记录每次每代演化所有个体表现型高度，由

30、于函数相对简单，所得到最优解均为完全拟合的完美解，即最佳个体的数学解析表达式约简后都与目标函数相同，进行了以下两项数据统计：1)统计实验所得最优解表现型高度范围区间为5，8。2)对所有演化实例中每代所有个体的表现型高度进行统计，得到所有个体表现型高度范围为1，8，其中表现型高度小于5的个体占统计个体总数的30405 7。分析1：依定理1此GEP问题的个体表现型高度范围应为1，13，统计项1)最优解个体表现型高度的范围为5，8】，实验数据虽不能证明表现型高度不在此范围内就不存在最优解，但至少证实对稍复杂的GEP问题，其最优解仅分布在表现型解空间S的部分子空间中。分析2：实验统计结果显示最优解表现

31、型高度最小值为5，说明此GEP问题表现型高度小于5的个体适应度很难达到适应度阈值；同时统计项2)说明演化过程中有近30的个体游离于最优解所在的子空间外，有如基因的中性区域，它们可能在某些遗传算子的作用下达到最优解或进入最优解所在子空间。但由于GEP遗传算子的“随机性”，表现型高度较小的个体基因型的中性区域相对更长，突变和重组算子的“突变点”和“重组点”落在中性区域的概率非常大；当突变点、重组点发生在中性区域，尽管其基因型有所改变，但个体的表现型不变，个体适应度值无变化，不但浪费大量计算资源，而且也降低了种群整体搜索的有效性，这30的个体一定程度上拖累了GEP种群进化的效率。32探索实验2实验目

32、的：探索单基因染色体的最大表现型高度计算的通项公式。万方数据第5期 郭勇，等：基于表现型的基因表达式编程解空间模型研究 123针对实验1中的第2项统计结果“个体表现型高度范围为【l，8】”，定理1揭示的是头部长度hl的基因表现型上界的普遍性性质，而实验1中操作符集F的最小操作符参数目数为2，实验数据中并没有出现表现型高度为h+l=13的个体，也没有出现表现型高度为9至12间的个体。定理1是对操作符集腹小目数没有限定的一个表现型高度“上限”的界定，其隐含的条件是操作符目数芝1，即定理1当操作符集最小目数为1时基因表现型高度才能达到最大值h+l，而本实验中操作符集肭最小操作符目数为2，提出以下猜想

33、：确定GEP问题F中操作符最小目数和头部长度|jl决定了基因表现型的最大高度Max(H)。为找到常用于多项式函数发现的基本操作符集乒+，一，木，)这种操作符最小目数为2的基因表现型高度上界计算的通项公式，以实验1的函数发现为例，取不同头部长度h运行若干次演化程序，统计h不同取值时，演化得到的所有单基因染色体的最大表现型高度Max(H)，统计得20组实测样本数据见表l。表1不同头部长度最大树高实验数据Tab1 Experimental data of maximum tree height for dif-ferent head lengths最小操作符目数n 头部长度 统计Max(劢分两种情况

34、使用GEP程序来进行最大表现型高度Max(H)的通项式函数发现：第1种情况：p+，一，s，)，不考虑F最小目数n，将矗按奇、偶数分2组训练集分别演化得一元函数式为：Max(H)=I+1枘奇数； (6)I芸+2，矗为偶数第2种情况：辟+，一，术，n，“，”表示截取整数运算INT()，将操作符最小目数n=2也作为变量值参与演化，演化所得二元函数式为：Ma)【(日)：矾T(皇)+，l (7)，z式中，当n=l时，可化简为Max(H)=h+1。与定理1结论相同，式(7)对操作符最小目数为1或2这两种最常用操作符集的情况都适用。基于21节假设2，在解决实际的GEP问题中，一般操作符集F的操作符最小目数为

35、1或2，因此可将式(7)作为计算确定GEP问题单基因染色体最大表现型高度的通项公式。对于使用“+”(或“OR”)作为连接符，是个基因构成的染色体表现型最大高度的计算，如定理2的证明方法，将露个基因视为整体G，各基因G；构成终结符集r，操作符集F7=+)得到的1个“复合”单基因染色体G，其结构头部长度为肛1，尾部长度为k。由于F7的最小目数为2，可根据式(7)计算出“复合”单基因染色体G7的表现型高度最大值Max(H)，再根据单个基因的操作符集F的最小目数利用式(7)求出单基因表现型的最大高度Max(H,)，即可算出k个基因构成的染色体个体表现型的最大高度：Max(H)=Max(H)+Max(H

36、_!)一1 (8)4 GEP演化控制策略41表现型解空间搜索控制策略GEP算法的有效性在理论上得到了一定论证，文献13】证明了基于精英保留策略的GEP算法依概率收敛，文献6重构带精英保留策略GEP的Markov链模型转移矩阵，建立依概率收敛速度的精确表达式，证明了算法依均值收敛、几乎必然收敛甚至完全收敛至全局最优值。GEP的本质仍属群体搜索算法，在种群规模固定的情况下，通过控制种群个体在可能最优解子空间范围搜索，发挥种群每个个体的演化贡献，从而提高种群整体演化搜索效率，作为改进GEP计算效能的基本思想。据第31节实验1的分析结合第24节的结论，演化控制宜在较高的表现型高度上进行，但表现型高度越

37、大，往往基因型有效编码区域更长，遗传算子随机实施命中最优解的概率相对较小，同时由于实践中GEP问题的差异和无先验知识，盲目限制搜索在很高的表现型高度范围或更少的子空间上不一定能取得好的效果，因此策定宏观控制策略。宏观控制指采用一定的方法控制种群更多的个体在s的部分子空间中演化，主要通过排除不包含最优解高度较小的子空间或其他子空间，缩小种群个体搜索子空间的范围，提高整体演化的效能。3445566778899mmnn也他n34，6709m屹BH：j2M捕捞加扒挖万方数据124 工程科学与技术 第49卷42限制个体具有较高的表现型通过控制尽量多的种群个体在较高表现型子空间中演化搜索，排除不包含最优解

38、的“表现型高度”较小子空间的搜索。依24节的定理及分析结论，在更高完全解空间嗍子空间中最优解呈大幅度增加趋势，可望提高种群搜索到最优解的概率。公开文献中符合此控制策略的有以下方法：1)“头+身+尾”基因结构改造法14-15；2)加大头部操作符选择概率法【161；3)基因多表达【l卜川1；4)开放尾部的基因表达式程序编程【2 2。421 “头+身+尾”基因结构改造法文献14_15】都提出“头+身+尾”的基因结构改造法，定义基因编码由头(head)、身(body)、尾(tail)组成，head的编码字符只能取自F，当head长度达到一定的值，则种群个体的表现型高度将维持在一定高度之上。文献141在

39、“头+身+尾”基因结构改造的基础上，还采用“同源基因”的多基因染色体结构，又进一步提高了所有个体的表现型高度。“头+身+尾”基因结构改造法的不足之处也在于head的编码字符全部取自F，无法表达head包含终结符的解。其表现型的表达空间显然比标准GEP的表现型表达空间小许多，虽会为它求解GEP问题时带来一定的优势，但不排除对某些具体GEP问题求解的效果不佳。422加大头部操作符选择概率法文献16在初始种群及突变算子时加大基因头部操作符选择的概率，据22节性质2，该方法使个体更容易进化到表现型更高的子空间中。事实上大量公开文献仿真实验的变量数都远小于F的操作符数，较多的文献中函数发现实验使用1个变

40、量的示例函数，跑含4个或更多的操作符，头部操作符的选择概率80，很难再进一步确定更加精细的操作符选择概率值。由于演化计算的“随机性”，该方法在符号回归仿真实验中的效果并不显著，概率值的选择无规律可循，文献中没有提出头部操作符选择概率值的方法。423基因多表这法该方法类似多表达式编程(multi expression programming，MEP)J，1个基因编码可解析出多个有效表达式，将某个表达式作为问题的候选解。该方法部分表达式由其他表达式复合而成，表现型高度通常较高，更有可能作为复杂GEP问题的最优解，弥补了较多个体游离于低子空间的不足，增加了较高表现型子空间上搜索的能力。对于单基因染色

41、体GEP来说，这种方法的优势之一在于基因的多表达，使1个单基因染色体中包含了多个候选解，在种群规模大小不变的情况下增加了实际演化个体的相对数量，对算法的有效性有一定的贡献。基因多表达的另一优势是能实现较短的线性编码表达更高的表现型子空间，具有编码重用、解码复用、空间复杂度小、搜索能力强等潜质。由于要评估更多表达式，时间复杂度相对较高。公开文献中有多种GEP的拓展算法具有基因多表达的能力：1)MEOErl 81、UGEP19MEOE、UGEP使用无约束基因结构，基因编码不分头尾，所有编码取自Fu丁，通过终结符复用、分段获取表达式及连接符得到多个表达式，其中所包含的复杂表达式的表现型高度通常较高。

42、方法具有短编码表达高表现型子空间的能力，能完整表达w前面部分子空间，避免因标准GEP头部长度的限制，导致有效编码区超出头部长度，再也无法表达较高子空间中更多等价解的缺陷。2)MGEP20】、EGEP21】在MGEP与EGEP中，基因结构与标准GEP相同，通过持续解码直到基因头部所有操作符用完，得到多个表达式，其中包含了较高表现型表达式。将MEP的多表达能力与GEP的“基因结构完备性”相结合。不仅具有表达更高解空间的优势，还可避免仅从头部首位解码，获得较短、适应度很差的表达式，忽略了后续编码更长、表现型更高、模式更好的编码段，导致在下一轮进化时，因轮盘赌等精英策略的概率选择失去进化到最优解的机会

43、。424开放尾部基因表达式编程文献22在标准GEP基因尾部编码的终结符集丁中加入“?”，GEP演化时，将每代最优个体动态地保存到一个特定结构ExpandTail中，解码时随机从ExpandTail中获取1个历史最优个体替换“?”进行解释计算。显然基因表现型最底层存在“?”时，最终表达出的表达式树高度大大增高，该方法不仅能使用较短的基因编码获得较高表现型表达空间的探索能力，同时具有历史最优个体解码复用的优势。43综合控制法综合控制法指解决生产实践中具体的GEP问题时，在GEP问题求解程序的设计中，实现用户对演化控制策略“多选”的交互功能，达到运用公开文献中多种控制策略及其他GEP改进策略的方法来

44、尝试GEP问题的求解。对于毫无先验知识的GEP问题求解，实践中往往需要多次尝试才能得到较好的GEP问题解，单一演化控制策略不一定能够取得预期的效果，多种控制策略的综合应用对某些特殊GEP问题的求解可能效果更佳。44“贪婪”控制策略“限制个体具有较高表现型”策略排除了种群个万方数据第5期 郭 勇，等：基于表现型的基因表达式编程缌空间模型研究 125体在表现型高度较小的部分子空问的搜索，其搜索的子空间仍然很多，据定理4和定理5，提出让种群在更少的表现型子空间搜索的控制策略。441采用多基因染色体标准GE咆含了多基因染色体结构的计算框架1-2，大量文献实验及实践证实，面对稍微复杂的GEP问题，特别是

45、多项式函数的发现问题，多基因染色体的效能明显优于单基因染色体。定理7操作符集聩小目数为1时，基因型长度相近的单基因染色体GEP在完全解空间形中搜索的子空间数大约是阶基因组成的多基因染色体GEP的艚。证明：设多基因染色体基因头部长度为刀。则基因型长度相近的单基因染色体的基因头部长度hkn。据定理1、定理2得单基因染色体GEP在砷搜索的子空间数为h7+1kn+】个，衿基因构成的多基因染色体在形中搜索的子空间数为n+阶。则两者之比：n+k n+k元雨12kn玎1庇，+ +lim(筹可111-，oo Ion +l 庀证毕。例2：表2为染色体长度相近的单、多基因染色体结构，按32节式(3)与式(4)计算

46、得表现型最大高度分别为42和13。单基因染色体搜索盱空间42个，而4基因染色体表现型高度-_3，最终种群搜索野空间仅有1 1个，接近于单基因染色体的14。表2染色体结构Tab2 Chromosome structure对于编码长度相近的染色体基因型来说，多基因染色体不但能有效排除表现型高度较小子空间的搜索，同时多基因染色体最大优势是避免在相近长度单基因染色体GEP较高表现型子空间的搜索，具有“斩头去尾”的能力，搜索范围更加接近最佳搜索空间既。442“贪婪”控制思想据24节定理6可知，形中较高的几个连续子空间一定包含最优解，可采取适当措施使种群在更少的子空间中进化，增加探索到最优解的概率。这种“

47、贪婪”控制思想有一定理论可行性，但由于遗传算子的随机性较强，具体控制方法不宜实施，还不能确定较好的控制措施，有待进一步研究。5结束语传统GEP“建树解码”时空复杂度高，效率较低，导致GEP表现型的研究没有引起更多关注。本文从GEP的表现型视角，探索了GEP个体表现型表达空间的结构与知识，研究GEP符号回归问题的最优解在GEP表现型解空间和完全解空间中的分布规律，提出在GEP表现型解空间中改进种群搜索效能的基本思想与策略，利用GEP表现型解空间知识对公开文献中的多种GEP拓展算法的有效性进行解释。基于表现型的GEP解空间模型概念与理论体系，对GEP的研究具有一定的理论和实践意义。从GEP表现型的

48、视角来研究与改善GEP计算效能仍有较丰富的想象空间。下一步将基于GEP表现型解空间知识，对GEP种群多样性、全局搜索能力的评估及GEP搜索空间“制导”等问题进行探索。参考文献：1】Ferreira CGene expression programming：A new adaptivealgorithm for solving problemsJComplex Systems，200l，13(2)：87-1292Ferreira CGene expression programmingMPortugal：An-gora do Heroismo，200231 Zuo JieResearch on kernel technology of gene expressionprogrammingDCengdu：Sichuan University，2004左劫基因表达式编程核心技术研究D成都：四川大学，2004】4Yuan Changan，Tang Changjie，Zuo Jie，et a1Function min-ing based on gene expression programming-Convergencyanalysis and remnantguided evolution algorithm