基于符号图遗传编程的符号回归方法

中文题目：基于符号图遗传编程的符号回归方法

论文题目：Symbol Graph Genetic Programming for Symbolic Regression

录用期刊/会议：Parallel Problem Solving From Nature PPSN 2024 (CCF B)

作者列表：

1）宋晶璐 中国石油大学（北京）人工智能学院 计算机科学与技术 硕22

2）鲁 强 中国石油大学（北京）人工智能学院 智能科学与技术系 副教授

3）田博舟 中国石油大学（北京）人工智能学院 计算机技术 硕22

4）张经文 中国石油大学（北京）人工智能学院 计算机科学与技术 硕22

5）Jake Luo University of Wisconsin Milwaukee Department of Health Informatics and Administration Associate Professor

6）王智广 中国石油大学（北京）人工智能学院 计算机系 教授

摘要:

符号回归的数学表达式空间是巨大的，所以解决该问题的主要难点在于如何精准地识别更可能包含正确表达式的子空间。本文深入探讨这一难点，提出名为符号图遗传编程（SGGP）的创新方法。SGGP首先构建一个符号图来有效地表示表达式空间。然后，它采用基于语义相似度的广义帕累托分布来评估该图中每条边（子空间）产生优秀个体的概率。根据这些概率，SGGP策略性采样新个体来发现准确的表达式。在109个数据集上的对比实验表明，SGGP显著优于21种现有的符号回归方法，其生成的表达式不仅准确性更高，而且更简洁。

背景与动机:

符号回归（SR）指从表达式空间中发现与给定数据集拟合的表达式。由于SR是NP难问题，演化计算特别是遗传编程方法，通常用于寻找SR的近似解。这些方法虽然有效，但它们在搜索表达式的过程中往往忽略数据集的特征。而机器学习/深度学习算法往往受到预定义的回归模型和所使用的训练数据集的影响。在大规模的基准实验中发现，最优的三种SR方法仍是基于遗传编程的，所以我们提出一种结合数据集特征的遗传编程方法来解决SR问题。

设计与实现:

符号图遗传编程(SGGP)方法总体框架如图1所示。首先，SGGP构建一个符号图，并在该图中初始化种群（如图1a所示）。然后，它利用语义算子生成新种群，具体操作如下：（1）计算极值分布：语义算子通过估计个体的语义相似度（如图1b所示）来计算每条边上的极值分布（如图1c所示）；（2）采样新个体：根据计算出的极值分布，语义算子对新个体采样（如图1d所示）。

图1 符号图遗传编程(SGGP)

实验结果及分析:

在FSRB、Strogatz和PMLB数据集上的对比实验表明，SGGP在、恢复率和模型大小方面都明显优于其他算法。

图2 FSRB和Strogatz的实验结果

（a） Test （b）Model Size

图3 PMLB的实验结果

（a）FSRB和Strogatz （b）PMLB

图4 和模型大小的帕累托前沿图

SGGP的突出性能主要归功于语义算子。该算子能够利用个体语义相似度和极值分布来指导SGGP搜索。这种方法能够提高搜索效率，使SGGP能够更快地找到最优解。

图5 数据集“”收敛性比较。虚线表示每种算法运行10次的平均适应度。蓝色实线是SGGP运行的结果之一。桑基图a、b和c表示符号图中边的概率。

结论:

本文设计了一种新的符号图，用来描述符号回归的表达式空间。在符号图的基础上，我们提出了一种新的遗传编程方法——符号图遗传编程（SGGP）。SGGP采用极值分布以及语义相似度来计算符号图中每条边的概率。然后，它基于这些概率对新个体进行采样来有效搜索正确的表达式。实验表明，SGGP优于21种符号回归方法，其中包括最新的机器学习/深度学习方法和演化计算方法。

通讯作者简介:

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

联系方式：luqiang@cup.edu.cn