Ferreira于2001年提出基因表达式编程（gene expression programming，GEP）^[1–2]，GEP对未知系统及知识具有较强的探索能力。在GEP理论方面已有一定的研究成果：GEP概念的形式化描述^[3]、GEP基因结构完备性定理证明^[3]、GEP最小残差平方和依概率收敛定理^[4]、GEP马尔可夫收敛性定理^[4]、GEP模式定理^[5]、GEP依条件完全收敛、几乎必然收敛且依均值收敛至全局最优解定理^[6]。同许多进化算法一样，GEP的理论基础仍较薄弱，达不到严谨的理论体系支持GEP算法的寻优。由于缺乏基础理论的支持，GEP性能的改进有一定的盲目性，改进方法的有效性主要依赖推断猜想和实验进行探索及佐证。

在GEP解空间研究方面，文献[7]对特定GEP问题，采用条件云模型和问题数据集构建GEP搜索空间模型，通过控制、引导GEP演化过程中保持一定种群的多样性和搜索区域的限制，提高了整体进化效率和求解质量。文献[8]基于线性编码空间，在种群初始化时，按基因头部和尾部编码的均匀分布策略生成多样性优势种群，实验证实比随机初始化种群的计算效率高；文献[9–10]将“小生境”等思想应用到GEP中，通过GEP种群多样性和演化搜索方向的控制，实现对GEP演化效能的改进；文献[11]给出了特定GEP染色体基因型与表现型表达空间大小的算法与证明，提出基于最佳genemap的初始化种群和演化控制的拓展算法AMGEP。上述文献涉及到不同视角和意义的GEP解空间模型雏形，虽然没有形成较完整的模型理论体系，但印证了基于一定的GEP解空间模型理论与认知，引导GEP演化过程的控制，以期获得GEP效能提升的可行性。本文针对符号回归问题，通过对GEP表现型的研究，获得GEP表现型的关键知识，构建基于表现型的GEP解空间理论体系，利用GEP表现型解空间模型揭示的知识，指引GEP演化效能改进策略的探索。

1 GEP简介 1.1 GEP个体的表示

GEP中个体为染色体（chromosome），染色体由基因（gene）构成，分为单基因染色体和多基因染色体；多基因染色体的多个基因由连接运算符按“广度优先”进行连接解释。GEP基因编码取自操作符集（F）和终结符集（T），基因编码分为头部（head）和尾部（tail）两部分，头部编码取自F∪U，尾部编码取自T，尾部长度t与头部长度h满足关系式（1）：

$t = h \times (M - 1) + 1$

(1)

式中，M为F中操作符最大参数目数。

例1：F={+，–， $* $ ，/}，T={a，b}，h=6，则“ $ +　* $ –aa/baabbab”为合法的基因编码。

1.2 GEP个体的基因型和表现型

GEP单基因染色体的线性编码称为基因型，线性编码按“广度优先”构建的表达式树（expression tree，ET）称为表现型。例1基因的表达式树如图1所示。多基因染色体的表现型，由固定连接符将各基因表达式树依“广度优先”连接而得。

1.3 GEP基因的解释

GEP基因的解释指基因所表达的数学意义，标准GEP基因的解释通过对基因的表达式树“后序遍历”得到其数学函数表达式。如图1表达式树“后序遍历”所得的数学表达式为：

$f(a,b) = {a^2} - b + 1{\text{。}}$

1.4 GEP个体适应度及遗传算子

GEP个体的适应度指将给定训练样本集所有样本变量值代入个体解释所得数学表达式，计算所得数学表达式值与样本整体差异的统计函数值，在符号回归问题中，一般使用绝对误差式、相对误差等^[1]作为适应度函数。GEP遗传算子主要包括选择、突变、重组、转座等，GEP通过选择算子和适应度函数控制种群的进化方向。

2 GEP表现型解空间 2.1 关于“确定GEP问题”

确定GEP问题求解包含以下3个确定内容：

1）确定的操作符集F和终结符集T。

2）确定的基因头部长度h及尾部长度t，且满足1.1节的关系式（1），对于多基因GEP还包括组成染色体的基因数及连接符。

3）确定的适应度函数和控制阈值。

确定GEP问题的求解及本文论述建立在以下2个假设下：

假设1　确定GEP问题个体的表达空间包含满足适应度控制阈值的解。

假设2　最小符号集的限定， $T \ne \varnothing $ ，数值型GEP中 $\{ + , - ,*,/\} \subseteq F$ ，逻辑型GEP中 ${\rm{\{ }}A,O,N{\rm{\} \subseteq }}F$ 。

2.2 GEP表现型解空间基本概念与性质

定义1（表现型解空间）　确定的GEP问题所有可能个体的不同表现型集合称为GEP问题的表现型解空间，记为S。

尽管基因的中性编码区域具有特殊的遗传意义，但最终个体的数学意义仍只由有效区域编码确定。具有相同有效编码区域的个体由于中性区域编码的差异，存在多个基因型不同的个体对应同一个表现型的情况，所以基因型的表达空间元素远多于表现型表达空间的元素。GEP依表现型的解释判断其是否作为问题解，基于GEP表现型解空间视角探索GEP改进的策略更接近其数学本质。

定义2（最优解）　适应度达到演化控制阈值的个体称为确定GEP问题的最优解，记为f。表现型不同、数学意义上约简后具有相同数学表达式函数的最优解称为等价解。表现型和所解释的数学表达式函数都不相同，但适应度达到控制阈值的最优解称为非等价解。适应度未达到适应度控制阈值的解称为候选解，确定GEP问题的所有个体统称为可能解。

定义3（最优解空间）　确定GEP问题的所有最优解的不同表现型集合，称为确定GEP问题的最优解空间，记为 $S'$ 。

定义4（表现型高度）　个体表现型的节点从上向下按层级分布在表达式树的“树枝”上，表达式树的总层级数称为表达式树的高度，也称为个体的表现型高度，记为H。

如图1表达式树的最上层为0层，即根节点层，最下面层为第4层，其高度H=5。

定义5（最简解）　确定GEP问题的表现型高度最小的最优解称为该GEP问题的最简解。

根据GEP基因结构的完备性定理^[3]，满足1.1节式（1）的基因都能生成合法的表达式树，得GEP的表达式树具有以下性质：

性质1　GEP表达式树最底层全部是叶节点。

性质2　在构建GEP表达式树时只有运算操作符节点才会产生下一级的表达式树层。

性质3　除根节点外，其他层级节点都是上一层级中某个操作符节点的子节点。

定理1　头部长度为h的单基因染色体的GEP表现型高度H≤h+1。

由于h∈N，可使用数学归纳法证明^[12]。

定理2　由头部长度为h，连接符为“+”（或“O”）的n（n≥1）个基因构成多基因染色体的表现型高度H≤h+n。

证明：1）当n=1时，即为单基因染色体，根据定理1，命题成立。

2）假设n=k时，命题成立，即 $H \le h + k \text{。} $

将每个基因视为一个整体，由于多基因染色体使用连接符按“广度优先”进行多基因的解释，得到1个“复合”单基因染色体的编码为：

$ + + \cdots {\rm{ + }}{G_1}{G_2} \cdots {G_{{k}}}$

(2)

式（2）中，共有k–1个连接运算符“+”，可视为1个头部长度为k–1的单基因染色体G，根据定理1，其表现型高度上界为：

$H{\rm{(}}G{\rm{)}} \le {\rm{(}}k{\rm{ - 1) + 1}}\text{。}$

即 $H(G) \le k\text{。}$

3）当n=k+1时，染色体结构比n=k时增加了1个基因和1个连接运算符，即有k个连接符和k+1个基因，同样将每个基因视为整体所得“复合”单基因染色体 $G'$ 的编码形如：

$+ + \cdots {\rm{ + }}{G_1}{G_2} \cdots {G_{{k}}}{G_{{{k + 1}}}}$

(3)

式（3）中，有k个连接运算符“+”，比假设2中的染色体增加1个连接运算符， $G'$ 的表达式树最多再增加1个表达式树层，所以单基因染色体 $G'$ 的表现型高度上界为：

$H(G') \le H(G) + 1$

(4)

将假设2中的结果 $H\left( G \right) \le k$ 代入式（4）得：

$H(G') \le k + 1\text{。}$

由于标准GEP多基因染色体中的多个基因按“广度优先”连接，在 $G'$ 中无论有多少个基因，据定理1其高度H上界：

$H \le (h' + 1)$

(5)

式（5）中， $h'$ 等于“复合”基因的头部长度k，即

$H \le (k + 1)\text{。}$

原多基因染色体的表现型是把各基因G_i的表达式树替换“复合”基因 $G'$ 表达式树中的G_i的位置而得，只有最底层某个基因的表达式树高度达到最大值（h+1），所得 $G'$ 的表达式树高度最大，如图2所示。

设最底层有基因G_m表达式树达最大值h+1，占位替换G_m后，可使 $G'$ 将所有基因的子表达式树替换后所得表达式树增加（h+1）–1层，即

$H(G') \le (k + 1) + (h + 1) - 1\text{。}$

即得：

$H(G') \le h + (k + 1)\text{。}$

命题对n=k+1成立，据假设1～2，命题对染色体基因数n取任何自然数均成立，证毕。

2.3 GEP表现型解空间结构

据定理1和定理2，可将S按表现型高度从小到大划分为m个子空间S_i（1≤i≤m）。

对于单基因染色体的确定GEP问题有：

$m \le h + 1\text{。}$

对于n个基因组成多基因染色体的确定GEP问题有：

$m \le h + n\text{。}$

将GEP最优解表现型空间 $S'$ 按个体的表现型高度从小到大划分为多个子空间 $S\!_i'$ （1≤i≤n），子空间包含最优解个数记为 $\left| {S\!_i'} \right|$ ，最简解的高度记为H_min，据定理1和定理2知最优解表现型高度的最大值是有界的，记为H_max。

$\begin{aligned} &　{S\!_1'} \cup {S\!_2'} \cup \cdot \cdot \cdot \cdot \cdot \cdot \cup {S\!_n'} = S'\text{，}\\ & \quad 1 \le {H_{\min }} \le {H_{\max }} \le m\text{，}\\ & \quad \quad H({S\!_1'}) = {H_{\min }}\text{，}\\ & \quad \quad H({S\!_n'}) = {H_{\max }}\text{。}\end{aligned}$

2.4 GEP最优解的分布研究

定义6（完全解空间）　由确定GEP问题的操作符集F和终结符集T中的符号构成的所有合法表达式树的集合，称为该GEP问题的表现型完全解空间，简记为W。

显然完全解空间W中的元素有无限多个，表达式树高度范围为自然数集N。按照W中元素表达式树的高度将W分为无限个子空间W_i（i∈N）。

确定GEP问题的W、S及 $S'$ 间的关系有：

$\begin{array}{l}\quad\quad\quad S' \subset S \subset W\text{，}\\{S_i} \subseteq {W_i}\text{，}\;\;\;i = 1,2, \cdot \cdot \cdot \cdot \cdot \cdot ,m\text{。}\end{array}$

由于GEP基因的头部编码取自F∪U，与完全解空间W的字符集相同，可得定理：

定理3　单基因染色体确定GEP问题必存在自然数 $m'(m' < m,m = {H_{\max }})$ ，使得GEP表现型解空间S与完全解空间W的前 $m'$ 个子空间相等：

$\begin{aligned}& {S_i} = {W_i}\text{，}\;\;\;1 \le i \le m'\text{；}\\& {S_i} \subset {W_i}\text{，}\;\;\;m' < i < m\text{。}\end{aligned}$

显然定理3中当GEP的头部长度h越长 $m'$ 的值就越大。定理3揭示了在一定的表现型高度之上由于受到基因尾部编码只能取自终结符T的限制，使得GEP的表现型解空间S虽然能表达到较高的子空间中的部分元素，但无法表达完全解空间W在该子空间中的所有元素。

定理4　若f为单基因染色体确定GEP问题的最简解，表现型高度k=H_min（k≥2），则在W中存在表现型高度为k+1的多个等价解。

定理4可通过对f表现型的根节点实施“生根术”进行例证，如图3（a）所示，对于数值型GEP问题，基于2.1节的假设2，T至少包含1个终结符a，在f的表现型根节点上增加少量字符，即可构建出数学意义相同而表现型高度为k+1的多个等价解，由于加法与乘法满足交换律，这样的等价解可达6个。图3（b）为“生根术”构建的逻辑型GEP问题的部分等价解，由于“AND”和“OR”满足交换律，这样的等价解多达8个。

定理4的推广可得：

引　理　若f为单基因染色体确定GEP问题的最优解，其表现型高度为k，则在W中存在表现型高度为k+1的多个等价解。

根据2.2节性质1及GEP的基因结构完备性可得性质4：

性质4　GEP表达式树最底层至少有一叶节点。

对于较复杂的GEP问题，由于其最简解表现高度往往大于1，即 $H({S\!_1'}) > H({S_1})$ ，所以最优解仅分布在S的部分子空间中。

定理5　若f为单基因染色体GEP问题的最简解，表现型高度k=H_min，则在W中存在表现型高度为k+2或k+3的多个等价解。

根据第2.1节的假设2，定理5可通过在f表现型最底层叶节点上实施“嫁接术”进行例证。据性质4，设f的最底层的一个叶节点终结符为“a”，其表现型表达式树如图4所示。

图5（a）为数值型GEP问题在最底层的1个叶节点“a”上“嫁接”出表现型高度为k+2的多个等价解，考虑到“+、 $ * $ ”等运算符满足交换律，类似的等价解可达6个。图5（b）为逻辑型GEP问题“嫁接”出表现型高度为k+2和k+3的多个等价解，由于“AND”与“OR”满足交换律，类似的等价解可达7个。

定理5的推广可得：

引　理　若f为单基因染色体GEP问题的最优解，表现型高度为H_f=k，则在W中存在表现型高度为k+2或k+3的多个等价解。

一方面，表达式树的最底层常不止1个叶节点，“嫁接”出的等价解更多。另一方面，表达式树倒数第2层可能存在多个叶节点，如图6所示，类似方法可“嫁接”出高度为k+1的多个等价解。同时对于数值型GEP问题，从图5（a）可观察到，“嫁接”所得表达式树最底层的叶节点会倍增，这种倍增情况从H_min+2开始，即最优解具有在W子空间中以2的几何级数“倍增”的趋势。结合定理4、5及引理，递推可得最优解在W子空间中的分布特征：

${a_{k + 2}} \gg 6{a_{k + 1}} + {a_k}\text{。}$

考虑到W更高子空间中可能出现新的非等价解，也以相同方式增长，所以最优解在W子空间中会以加速“倍增”趋势随子空间序号的增长而剧增，称这种递增速度为“大比例”增长方式。

最优解在S与W中的分布如图7所示，图7中H₀=H_min， $ H $ ′代表定理3中的 $m'$ ，H_m=H_max，实线表示W中最优解数量变化，虚线代表S中最优解数量的变化。

1）总体上最优解随W子空间表现型高度的增高而大幅增加。

2）在区间 $\left[ {{H_0} , H'} \right]$ 上，实线与虚线重合，表示在此区间上S与W的子空间相同，最优解的分布无差异，且遵循大比例增长趋势。S在此区间各子空间中个体的基因有效编码区相对较短，解码用时少，又包含了大量最优解，有利GEP搜索到最优解，称此区间为最佳搜索区间，其上的所有子空间称为最佳搜索空间，简记为W_b。

3）在区间 $\left[ {H' , {H_{\rm m}}} \right]$ 上，由于受基因头部长度限制，无法表达定理4与定理5中的大量等价解，而W仍大比例的增加，S子空间中最优解明显少于W的子空间，同时还可能由于具体GEP问题的特殊性和无头部运算符使用而无法表达出任何最优解，从而使最优解数量骤减，甚至无最优解，此区间上虚线的走向有不确定性。

4）在区间 $\left[ {{H_{\rm m}}{\rm{ , }}\infty } \right]$ 上，由于S受染色体结构长度的限制，不能表达更高的子空间，故无虚线，而W实线仍可无限延伸，且最优解保持大比例速度剧增。

依定理3和定理4及引理可得以下结论和启示：

结论：单基因染色体确定GEP问题的基因头部长度h足够长时，如果最简解的高度H_min远小于定理3中的 $m'$ ，则在最佳区间 $\left[ {{H_{\min }},m'} \right]$ 上，最优解的分布依子空间S_i序号i（i≥H_min）的增大呈大比例增加，控制GEP种群在此区间上子空间中搜索效率相对较好。

启示1：对于单基因GEP问题，在无先验知识情况下，基因头部长度的选择是一个难点，选择过小可能导致解空间S不包含最优解，太大又会导致整体解码时间大幅增加，同时产生大头部降低随机演化命中最优解概率的想法，从而选择较小的头部长度尝试多次问题的求解，据结论，加大尝试的头部长度不一定有想象的哪样困难，相反可能较快尝试出包含问题最优解的基因头部长度，从而提高GEP解决实际应用问题的效率。

启示2：对于单基因GEP问题，根据结论和GEP表现型及解空间的特性，在区间 $\left[ {{H_{\min }},m'} \right]$ 上，更高子空间中的个体基因的有效编码区域更长，中性区域相对较短，子空间中表达的个体相对较少，最优解相对较多。在种群规模固定时，采取一定的演化策略和控制技术，使种群在更高表现型子空间中演化搜索，可期望提升GEP概率搜索到最优解的“命中率”。

基于2.4节的定理4和定理5，结合2.1节的假设1和假设2，可推定定理6。

定理6　确定GEP问题的完全解空间W中，当k≥H_min时，连续的两个子空间W_k与W_k+1中必定包含有该GEP问题的多个最优解。

3 探索实验 3.1 探索实验1

实验目的：分析GEP演化过程中种群所有个体表现型高度和最优解表现型高度的取值范围。

对下面的函数进行函数发现仿真实验：

$f(a) = \frac{{{a^2}}}{2}{\rm{ + 3}}a\text{。}$

使用单基因染色体，F={+，–， $ * $ ，/}，T={a}，基因头部长度为12，随机在[–10，10]生成训练样本20组，种群个体数为100，适应度函数取相对误差，适应度控制阈值精度为0.01%。运行GEP程序100次，利用Sqlite数据库记录每次每代演化所有个体表现型高度，由于函数相对简单，所得到最优解均为完全拟合的完美解，即最佳个体的数学解析表达式约简后都与目标函数相同，进行了以下两项数据统计：

1）统计实验所得最优解表现型高度范围区间为[5，8]。

2）对所有演化实例中每代所有个体的表现型高度进行统计，得到所有个体表现型高度范围为[1，8]，其中表现型高度小于5的个体占统计个体总数的30.405 7%。

分析1：依定理1此GEP问题的个体表现型高度范围应为[1，13]，统计项1）最优解个体表现型高度的范围为[5，8]，实验数据虽不能证明表现型高度不在此范围内就不存在最优解，但至少证实对稍复杂的GEP问题，其最优解仅分布在表现型解空间S的部分子空间中。

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

3.2 探索实验2

实验目的：探索单基因染色体的最大表现型高度计算的通项公式。

针对实验1中的第2项统计结果“个体表现型高度范围为[1，8]”，定理1揭示的是头部长度h≥1的基因表现型上界的普遍性性质，而实验1中操作符集F的最小操作符参数目数为2，实验数据中并没有出现表现型高度为h+1=13的个体，也没有出现表现型高度为9至12间的个体。定理1是对操作符集F最小目数没有限定的一个表现型高度“上限”的界定，其隐含的条件是操作符目数≥1，即定理1当操作符集最小目数为1时基因表现型高度才能达到最大值h+1，而本实验中操作符集F的最小操作符目数为2，提出以下猜想：

确定GEP问题F中操作符最小目数和头部长度h决定了基因表现型的最大高度Max（H）。

为找到常用于多项式函数发现的基本操作符集F={+，–， $ * $ ，/}这种操作符最小目数为2的基因表现型高度上界计算的通项公式，以实验1的函数发现为例，取不同头部长度h运行若干次演化程序，统计h不同取值时，演化得到的所有单基因染色体的最大表现型高度Max（H），统计得20组实测样本数据见表1。

分两种情况使用GEP程序来进行最大表现型高度Max（H）的通项式函数发现：

第1种情况：F={+，–， $ * $ ，/}，不考虑F最小目数n，将h按奇、偶数分2组训练集分别演化得一元函数式为：

${\rm Max}(H) = \left\{ \begin{array}{l}\displaystyle\frac{{h + 1}}{2} + 1\text{，}\; h{\text{为奇数；}}\\\displaystyle\frac{h}{2} + 2\text{，}\; h{\text{为偶数}}\end{array} \right.$

(6)

第2种情况：F={+，–， $ * $ ，/，I}，“I”表示截取整数运算INT（），将操作符最小目数n=2也作为变量值参与演化，演化所得二元函数式为：

${\rm Max}(H) = {\rm INT}(\frac{{{\rm{ }}h{\rm{ }}}}{n}) + n$

(7)

式中，当n=1时，可化简为 ${\rm Max}(H) = h + 1$ 。

与定理1结论相同，式（7）对操作符最小目数为1或2这两种最常用操作符集的情况都适用。基于2.1节假设2，在解决实际的GEP问题中，一般操作符集F的操作符最小目数为1或2，因此可将式（7）作为计算确定GEP问题单基因染色体最大表现型高度的通项公式。

对于使用“+”（或“OR”）作为连接符，k个基因构成的染色体表现型最大高度的计算，如定理2的证明方法，将k个基因视为整体G_i，各基因G_i构成终结符集 $T'$ ，操作符集 $F' = \{ + \} $ 得到的1个“复合”单基因染色体 $G'$ ，其结构头部长度为k–1，尾部长度为k。由于 ${{F}}$ ′的最小目数为2，可根据式（7）计算出“复合”单基因染色体 $G'$ 的表现型高度最大值 ${\rm Max}(H')$ ，再根据单个基因的操作符集F的最小目数利用式（7）求出单基因表现型的最大高度 ${\rm Max}({H_i})$ ，即可算出k 个基因构成的染色体个体表现型的最大高度：

${\rm Max}(H) = {\rm Max}(H') + {\rm Max}({H_i}) - 1$

(8)

4 GEP演化控制策略 4.1 表现型解空间搜索控制策略

GEP算法的有效性在理论上得到了一定论证，文献[13]证明了基于精英保留策略的GEP算法依概率收敛，文献[6]重构带精英保留策略GEP的Markov链模型转移矩阵，建立依概率收敛速度的精确表达式，证明了算法依均值收敛、几乎必然收敛甚至完全收敛至全局最优值。GEP的本质仍属群体搜索算法，在种群规模固定的情况下，通过控制种群个体在可能最优解子空间范围搜索，发挥种群每个个体的演化贡献，从而提高种群整体演化搜索效率，作为改进GEP计算效能的基本思想。

据第3.1节实验1的分析结合第2.4节的结论，演化控制宜在较高的表现型高度上进行，但表现型高度越大，往往基因型有效编码区域更长，遗传算子随机实施命中最优解的概率相对较小，同时由于实践中GEP问题的差异和无先验知识，盲目限制搜索在很高的表现型高度范围或更少的子空间上不一定能取得好的效果，因此策定宏观控制策略。宏观控制指采用一定的方法控制种群更多的个体在S的部分子空间中演化，主要通过排除不包含最优解高度较小的子空间或其他子空间，缩小种群个体搜索子空间的范围，提高整体演化的效能。

4.2 限制个体具有较高的表现型

通过控制尽量多的种群个体在较高表现型子空间中演化搜索，排除不包含最优解的“表现型高度”较小子空间的搜索。依2.4节的定理及分析结论，在更高完全解空间W的子空间中最优解呈大幅度增加趋势，可望提高种群搜索到最优解的概率。公开文献中符合此控制策略的有以下方法：

1）“头+身+尾”基因结构改造法^[14–15]；

2）加大头部操作符选择概率法^[16]；

3）基因多表达^[17–21]；

4）开放尾部的基因表达式程序编程^[22]。

4.2.1 “头+身+尾”基因结构改造法

文献[14–15]都提出“头+身+尾”的基因结构改造法，定义基因编码由头（head）、身（body）、尾（tail）组成，head的编码字符只能取自F，当head长度达到一定的值，则种群个体的表现型高度将维持在一定高度之上。文献[14]在“头+身+尾”基因结构改造的基础上，还采用“同源基因”的多基因染色体结构，又进一步提高了所有个体的表现型高度。“头+身+尾”基因结构改造法的不足之处也在于head的编码字符全部取自F，无法表达head包含终结符的解。其表现型的表达空间显然比标准GEP的表现型表达空间小许多，虽会为它求解GEP问题时带来一定的优势，但不排除对某些具体GEP问题求解的效果不佳。

4.2.2 加大头部操作符选择概率法

文献[16]在初始种群及突变算子时加大基因头部操作符选择的概率，据2.2节性质2，该方法使个体更容易进化到表现型更高的子空间中。事实上大量公开文献仿真实验的变量数都远小于F的操作符数，较多的文献中函数发现实验使用1个变量的示例函数，F包含4个或更多的操作符，头部操作符的选择概率≥80%，很难再进一步确定更加精细的操作符选择概率值。由于演化计算的“随机性”，该方法在符号回归仿真实验中的效果并不显著，概率值的选择无规律可循，文献中没有提出头部操作符选择概率值的方法。

4.2.3 基因多表达法

该方法类似多表达式编程（multi expression programming，MEP）^[17]，1个基因编码可解析出多个有效表达式，将某个表达式作为问题的候选解。该方法部分表达式由其他表达式复合而成，表现型高度通常较高，更有可能作为复杂GEP问题的最优解，弥补了较多个体游离于低子空间的不足，增加了较高表现型子空间上搜索的能力。对于单基因染色体GEP来说，这种方法的优势之一在于基因的多表达，使1个单基因染色体中包含了多个候选解，在种群规模大小不变的情况下增加了实际演化个体的相对数量，对算法的有效性有一定的贡献。基因多表达的另一优势是能实现较短的线性编码表达更高的表现型子空间，具有编码重用、解码复用、空间复杂度小、搜索能力强等潜质。由于要评估更多表达式，时间复杂度相对较高。公开文献中有多种GEP的拓展算法具有基因多表达的能力：

1）MEOE^[18]、UGEP^[19]

MEOE、UGEP使用无约束基因结构，基因编码不分头尾，所有编码取自F∪T，通过终结符复用、分段获取表达式及连接符得到多个表达式，其中所包含的复杂表达式的表现型高度通常较高。方法具有短编码表达高表现型子空间的能力，能完整表达W前面部分子空间，避免因标准GEP头部长度的限制，导致有效编码区超出头部长度，再也无法表达较高子空间中更多等价解的缺陷。

2）MGEP^[20]、EGEP^[21]

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

4.2.4 开放尾部基因表达式编程

文献[22]在标准GEP基因尾部编码的终结符集T中加入“？”，GEP演化时，将每代最优个体动态地保存到一个特定结构ExpandTail中，解码时随机从ExpandTail中获取1个历史最优个体替换“？”进行解释计算。显然基因表现型最底层存在“？”时，最终表达出的表达式树高度大大增高，该方法不仅能使用较短的基因编码获得较高表现型表达空间的探索能力，同时具有历史最优个体解码复用的优势。

4.3 综合控制法

综合控制法指解决生产实践中具体的GEP问题时，在GEP问题求解程序的设计中，实现用户对演化控制策略“多选”的交互功能，达到运用公开文献中多种控制策略及其他GEP改进策略的方法来尝试GEP问题的求解。对于毫无先验知识的GEP问题求解，实践中往往需要多次尝试才能得到较好的GEP问题解，单一演化控制策略不一定能够取得预期的效果，多种控制策略的综合应用对某些特殊GEP问题的求解可能效果更佳。

4.4 “贪婪”控制策略

“限制个体具有较高表现型”策略排除了种群个体在表现型高度较小的部分子空间的搜索，其搜索的子空间仍然很多，据定理4和定理5，提出让种群在更少的表现型子空间搜索的控制策略。

4.4.1 采用多基因染色体

标准GEP包含了多基因染色体结构的计算框架^[1–2]，大量文献实验及实践证实，面对稍微复杂的GEP问题，特别是多项式函数的发现问题，多基因染色体的效能明显优于单基因染色体。

定理7　操作符集F最小目数为1时，基因型长度相近的单基因染色体GEP在完全解空间W中搜索的子空间数大约是k个基因组成的多基因染色体GEP的k倍。

证明：设多基因染色体基因头部长度为n。

则基因型长度相近的单基因染色体的基因头部长度 $h' \approx kn$ 。据定理1、定理2得单基因染色体GEP在W中搜索的子空间数为 $h' + 1 \approx kn + 1$ 个，k个基因构成的多基因染色体在W中搜索的子空间数为n+k个。则两者之比：

$\begin{aligned}& \displaystyle\frac{{n + k}}{{h' + 1}} \approx \frac{{n + k}}{{kn + 1}}\text{，}\\& \mathop {\lim }\limits_{n \to \infty } (\frac{{n + k}}{{kn + 1}}) = \displaystyle\frac{1}{k}\text{。}\end{aligned}$

证毕。

例2：表2为染色体长度相近的单、多基因染色体结构，按3.2节式（3）与式（4）计算得表现型最大高度分别为42和13。单基因染色体搜索W子空间42个，而4基因染色体表现型高度H≥3，最终种群搜索W子空间仅有11个，接近于单基因染色体的1/4。

对于编码长度相近的染色体基因型来说，多基因染色体不但能有效排除表现型高度较小子空间的搜索，同时多基因染色体最大优势是避免在相近长度单基因染色体GEP较高表现型子空间的搜索，具有“斩头去尾”的能力，搜索范围更加接近最佳搜索空间W_b。

4.4.2 “贪婪”控制思想

据2.4节定理6可知，W中较高的几个连续子空间一定包含最优解，可采取适当措施使种群在更少的子空间中进化，增加探索到最优解的概率。这种“贪婪”控制思想有一定理论可行性，但由于遗传算子的随机性较强，具体控制方法不宜实施，还不能确定较好的控制措施，有待进一步研究。

5 结束语

传统GEP“建树解码”时空复杂度高，效率较低，导致GEP表现型的研究没有引起更多关注。本文从GEP的表现型视角，探索了GEP个体表现型表达空间的结构与知识，研究GEP符号回归问题的最优解在GEP表现型解空间和完全解空间中的分布规律，提出在GEP表现型解空间中改进种群搜索效能的基本思想与策略，利用GEP表现型解空间知识对公开文献中的多种GEP拓展算法的有效性进行解释。基于表现型的GEP解空间模型概念与理论体系，对GEP的研究具有一定的理论和实践意义。从GEP表现型的视角来研究与改善GEP计算效能仍有较丰富的想象空间。下一步将基于GEP表现型解空间知识，对GEP种群多样性、全局搜索能力的评估及GEP搜索空间“制导”等问题进行探索。