点击数: 更新日期: 2022-03-24
录用/见刊时间：2022-3-24
论文题目：Taylor Genetic Programming for Symbolic Regression
录用期刊/会议：Genetic and Evolutionary Computation Conference (CCF：C类）
原文DOI：10.1145/3512290.3528757
作者列表：
1）何柏河，中国石油大学（北京），信息科学与工程学院，2020级硕士
2）鲁强，中国石油大学（北京），信息科学与工程学院，硕士导师
3）杨青云，中国石油大学（北京），信息科学与工程学院，2020级硕士
4）ake Luo, University of Wisconsin, Milwaukee, College of Health Sciences, Associate Professor
5）王智广，中国石油大学（北京），信息科学与工程学院，硕士导师
背景与动机:
符号回归是指从数学表达式空间中找到一个拟合到给定数据集（,）的符号方程，即(X) = 。遗传编程和机器学习是解决符号回归问题的常用方法。遗传编程专注于在搜索空间中搜索解决方案，但它通常在不考虑数据集特征的情况下将个体随机转换为搜索结果。因此，遗传算法的搜索过程通常效率低下。在求解符号回归问题时，虽然机器学习方法可以快速找到一些最优符号方程，但结果通常依赖于预定义的回归模型，因此机器学习方法不适用于求解大规模数据集。例如，在最近使用大规模基准对SR问题的算法进行的评估中，结果表明，有四分之三的帕累托前沿是基于遗传编程的方法。为了克服遗传编程和M机器学习的缺点，我们提出了泰勒遗传编程算法（TaylorGP）：首先使用泰勒展开式拟合数据集并从展开式中捕获数据集特征；然后使用根据数据集特征指导的遗传编程来搜索结果。
图 1 TaylorGP 算法框架
设计与实现:
TaylorGP算法主要包括三个步骤：计算泰勒多项式，提取泰勒特征和指导遗传编程。首先，通过求解k元一次方程组的方式计算出近似拟合数据集的k阶泰勒多项式。泰勒特征是指从拟合数据集的泰勒多项式中提取的，能够表征数据集所具有的特殊规律的统称，比如可分性、有界性、单调性、奇偶性等，我们可以利用泰勒特征改进遗传编程，目的是削减种群的探索空间，更多地在有效空间中探索。
l 计算泰勒多项式
通过求解k元一次方程组的方式计算出近似拟合数据集的k阶泰勒多项式。
l 提取泰勒特征
（1）第一个特征是变量可分性。对于一个多变量函数(1,...,)，如果有一个操作符“◎”使得(1,...,)=1(,...,)◎2(,...,)，并且满足{,...,}∪{,...,}={1,...,}和{，...，}∩{，...，}=，则(1,...,)是具有变量可分性的。该可分性的性质可以将一个复杂的多元函数分解为多个简单的函数，从而通过分治法达到降维求解目的。
（2）第二个特征是低阶多项式判别，它可以帮助我们判别是否存在能够表征数据集的低阶多项式。比如“x6−2x4+x2”，它在任何展开点的泰勒多项式也是其本身；而如果函数是非线性表达式，例如sin(x)，log(1+x)等，它们的泰勒多项式是一个无限阶多项式。低阶泰勒多项式无法逼近它们。
（3）第三个特征是函数特征，我们可以从泰勒多项式中计算出有界性、奇偶性和单调性，函数特征可以指导GP进行启发式搜索：
①有界性:(Min(fTaylor(X)),Max(fTaylor(X))
②奇偶性:Odd→fTaylor(−X)=fTaylor(X);Even→fTaylor(−X)=fTaylor(X)
③单调性:Increasing→∀Xi≥Xj,fTaylor(Xi)≥fTaylor(Xj);
Decreasing→∀Xi≥Xj,fTaylor(Xi)≤fTaylor(Xj)
l 指导遗传编程
图 2 初始化过程
（1）使用上述特征来指导遗传编程的初始化。随机生成满足函数特征的个体的概率非常小。因此，如图2所示，我们首先根据树形个体对应的中缀表达式前两位来划分空间，也就是说，我们穷举公式符号以列出所有空间。其次，根据Hend Dawood提出的区间算法评估每个空间的边界。然后削减掉不能包含泰勒多项式上下边界的空间，因为这些空间必不包含目标公式。最后，在有效空间中对个体进行采样。例如，我们可以在底层的“++”空间中将星号填充为“xxx”，以获得个体“x+x+x”；在“+x”空间中用“sinxx”填充，得到个体“x+sin(x)”。
图 3 重组规则表
（2）指导遗传编程中的重组过程。为了确保重组产生的后代都具有相同的特征，我们给出了全新的重组规则表。如图3所示，假设我们的目标公式是一个奇函数。首先，我们随机选择两个奇函数个体“2x+2sin(x)”和”x+x3”。其次，我们从奇函数重组规则中选择运算符“+”。最后，我们将这两个个体重组为“3x+2sin(x)+x3”，它仍然是一个奇函数。因此，重组规则确保了种群后代特征的一致性。
实验结果及分析:
我们评估了TaylorGP在三类基准数据集上的性能：机器学习基准数据集（PMLB）、经典符号回归基准数据集（SRB）和Feynman符号回归基准数据集（FSRB）。按样本和特征划分的81个数据集分布如图4所示。图5展示了十种算法在所有基准数据集上运行30次的的标准化R2结果。由于标准化R2值越接近1表示越好的结果，因此TaylorGP可以找到比其他算法适应度更准确和更稳定的结果。
图 4数据集分布
图5
如图6所示，根据30次独立重复实验生成的15个收敛图中，我们可以看到蓝色的TaylorGP比GPLearn、GSGP和BSR收敛更快、更稳定。
图6
通讯作者简介:
鲁强：副教授，硕士导师。目前主要从事演化计算与符号回归、知识图谱与智能问答、以及轨迹分析与挖掘等方面的研究工作。