论文题目：Adversarial Bandit Gene Expression Programming for Symbolic Regression

会议名称：Genetic and Evolutionary Computation Conference (2021 CCF：C类）

作者列表：

（1） 徐聪文 中国石油大学（北京）信息科学与工程学院2019级硕士

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

（3） Jake Luo，University of Wisconsin, Milwaukee, College of Health Sciences  Associate Professor

（4） 王智广 中国石油大学（北京 ）信息科学与工程学院 硕士导师

原文DOI：10.1145/3449726.3459499

背景与动机

符号回归(SR)指的是根据一组数据集 , 寻找能够描述数据集间关系的数据表达式f,使得Y=f(X)。基因表达式编程（GEP）是解决符号回归问题的常用方法。然而，由于种群多样性的下降，GEP容易陷入过早收敛，并且只能达到局部最优解。为了解决过早收敛问题，我们提出了一种基于对抗性赌臂机技术的符号回归算法（AB-GEP）。AB-GEP 将整个数学表达式空间分割成许多子空间，通过种群在子空间之间的跳转保持种群多样性。为了选择合适的子空间进行探索，AB-GEP利用基于对抗式赌臂机模型Exp3的改进方法AvgExp3进行子空间的选择。AvgExp3放弃了有关于子空间奖励值分布的任何假设，而是根据子空间动态产生的奖励值对其进行评估，使得评估结果更准确的反映时间变化特征。实验结果表明， AB-GEP相较于其它的基准GEP算法能够发现更准确的数学公式。

图 1 AB-GEP 算法框架

设计与实现

AB-GEP算法主要包括两个步骤：子空间选择和个体跳转。子空间的选择为GEP在整个搜索空间指定探索的区域，从而能够更准确的找到适合数据集的公式。子空间的选择基于子空间奖励值的动态评估，根据当前子空间奖励值的反馈，指导下一个步骤可能被探索的子空间，此过程结合改进的对抗式赌臂机方法AvgExp3实现对于子空间的探索和利用的平衡。在选择合适的子空间基础上，利用个体跳转使得当前种群跳入该子空间，并与该子空间中的历史最优个体进行重组以达到快速探索该子空间的目的。

l 子空间选择

AB-GEP通过概率分布 来获得每一代（t）选择各个子空间（）的概率。其中 根据指数加权方式进行计算，

        （1）

公式（1）中是子空间在前t-1代的平均估计奖励值，是学习率。由公式（2）进行计算，

 （2）

其中表示子空间 中最佳个体的适应度。

l 个体跳转

个体跳转通过特定的交叉方式实现，给定一个属于子空间的个体，当通过交叉方式将该个体编码头部替换为 后，它会跳转到子空间。之后，它将与中的历史最优个体重组来探索。个体（种群）在子空间之间的跳转保持了种群多样性，避免搜索陷入局部最优。

实验结果

在12个标准问题测试集上，将以下四个算法：GEP、SPJ-GEP、SL-GEP和AB-GEP，分别运行了10次，所获得的数据误差和获得正确答案准确率如下表所示。

标准测试集如下图所示：

数据误差和获得正确答案准确率如下图所示：

子空间选择对比如下图所示：

关于作者

鲁强，副教授

中国石油大学（北京），信息科学与工程学院智能中心，硕士生导师。目前主要从事演化计算与符号回归、知识图谱与智能问答、以及轨迹分析与挖掘等方面的研究工作。先后主持或参与国家自然科学基金、国家重大专项以及企业横向课题10余项。在教学方面主要教授操作系统、分布式系统和语义Web等本科和研究生课程，并主编或参编图书两部。联系方式：Email：luqiang@cup.edu.cn