当前位置: 主页 > 学术动态 >

面向符号回归的泰勒遗传编程算法

点击数:   更新日期: 2022-08-23

中文题目面向符号回归的泰勒遗传编程算法

论文题目Taylor Genetic Programming for Symbolic Regression

录用时间2022-3-24

录用会议Genetic and Evolutionary Computation Conference (CCF:C类)

原文DOI10.1145/3512290.3528757

作者列表

1)何柏河,中国石油大学(北京),信息科学与工程学院,2020级硕士

2)鲁强,中国石油大学(北京),信息科学与工程学院,硕士导师

3)杨青云,中国石油大学(北京),信息科学与工程学院,2020级硕士

4) Jake Luo, University of Wisconsin, Milwaukee, College of Health Sciences, Associate Professor

5)王智广,中国石油大学(北京),信息科学与工程学院,硕士导师

背景与动机:

符号回归是指从数学表达式空间中找到一个拟合到给定数据集。遗传编程和机器学习是解决符号回归问题的常用方法。遗传编程专注于在搜索空间中搜索解决方案,但它通常在不考虑数据集特征的情况下将个体随机转换为搜索结果。因此,遗传算法的搜索过程通常效率低下。在求解符号回归问题时,虽然机器学习方法可以快速找到一些最优符号方程,但结果通常依赖于预定义的回归模型,因此机器学习方法不适用于求解大规模数据集。例如,在最近使用大规模基准对SR问题的算法进行的评估中,结果表明,有四分之三的帕累托前沿是基于遗传编程的方法。为了克服遗传编程和M机器学习的缺点,我们提出了泰勒遗传编程算法(TaylorGP):首先使用泰勒展开式拟合数据集并从展开式中捕获数据集特征;然后使用根据数据集特征指导的遗传编程来搜索结果。



1 TaylorGP 算法框架

设计与实现:

TaylorGP算法主要包括三个步骤:计算泰勒多项式,提取泰勒特征和指导遗传编程。首先,通过求解k元一次方程组的方式计算出近似拟合数据集的k阶泰勒多项式。泰勒特征是指从拟合数据集的泰勒多项式中提取的,能够表征数据集所具有的特殊规律的统称,比如可分性、有界性、单调性、奇偶性等,我们可以利用泰勒特征改进遗传编程,目的是削减种群的探索空间,更多地在有效空间中探索。

l 计算泰勒多项式

通过求解k元一次方程组的方式计算出近似拟合数据集的k阶泰勒多项式。



l 提取泰勒特征

(1)第一个特征是变量可分性。该可分性的性质可以将一个复杂的多元函数分解为多个简单的函数,从而通过分治法达到降维求解目的。

(2)第二个特征是低阶多项式判别,它可以帮助我们判别是否存在能够表征数据集的低阶多项式。比如“x62x4+x2”,它在任何展开点的泰勒多项式也是其本身;而如果函数是非线性表达式,例如sin(x),log(1+x)等,它们的泰勒多项式是一个无限阶多项式。低阶泰勒多项式无法逼近它们。

(3)第三个特征是函数特征,我们可以从泰勒多项式中计算出有界性、奇偶性和单调性,函数特征可以指导GP进行启发式搜索。

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

通讯作者简介:

鲁强:副教授,硕士导师。目前主要从事演化计算与符号回归、知识图谱与智能问答、以及轨迹分析与挖掘等方面的研究工作。