点击数: 更新日期: 2022-12-06
中文题目：AB-GEP：用于符号回归的对抗赌臂机基因表达式编程
论文题目：AB-GEP: Adversarial bandit gene expression programming for symbolic regression
录用期刊：Swarm and Evolutionary Computation（JCR Q1，Top）
原文DOI：https://10.1016/j.swevo.2022.101197
录用时间：2022-10-27
作者列表：
1）鲁强，中国石油大学（北京），信息科学与工程学院
2）徐聪文，中国石油大学（北京），人工智能学院 硕士19级
3）Jake Luo, University of Wisconsin, Milwaukee, College of Health Sciences, Associate Professor
4）王智广，中国石油大学（北京），信息科学与工程学院
背景与动机:
基因表达式编程 (GEP) 是解决符号回归 (SR) 问题的常用方法。然而，GEP 经常陷入局部最优。 GEP 是随机搜索结果，并可能重新访问低价值搜索空间，这会影响其性能。为了克服这两个问题，我们提出了一种使用对抗赌臂机来增强 GEP 的新算法--AB-GEP。 AB-GEP 将数学表达式空间分割成许多子空间。然后，它利用一种新的搜索空间选择方法 AvgExp3 来增强子空间之间选择与跳跃，这可以防止算法陷入局部最优。 AvgExp3 通过搜索空间中产生的奖励来动态估计子空间。动态奖励估计使 AB-GEP 更能适应奖励变化，也为AB-GEP 选择可以包含正确结果的子空间提供了方向的指导。
本研究证明 AvgExp3 是对子空间平均奖励的无偏估计，其方差低于标准 Exp3 方法。在两个基准数据集的评估表明，与GEP、SL-GEP 和 SPJ-GEP 三种传统 GEP算法相比， AB-GEP可以保持更好的种群多样性，并获得更好的结果。 AB-GEP 在 32 个基准测试中的 50% 中排名第一，而传统 GEPs 仅获得不超过 20% 的最佳结果。
图1 AB-GEP 框架
设计与实现：
AB-GEP将整个数学空间划分为多个子空间进行探索。这可以防止搜索过程陷入局部最优。原因是该算法可以通过个体跳跃过程逃离局部最优，因为个体在子空间之间跳跃可以给个体的基因型带来重大变化，并鼓励探索。此外，这些划分的子空间允许AB-GEP获取关于每个个体近似位置的信息，因为每个个体必须属于子空间。
2.1 AB-GEP
在AB-GEP中，数学表达式空间被划分为许多子空间。从这些子空间中，符号回归 (SR) 发现适合给定数据集的最佳数学表达式。在这种情况下，SR 面临与对抗多臂赌博机相同的问题——如何在不假设赌臂（子空间）奖励值分布的情况下估计每个赌臂（子空间）的期望奖励值，以及如何在子空间探索和利用之间取得平衡并最大化奖励（最好的数学表达式）。因此，对抗多臂赌博机问题和SR子空间评估问题的相似性，我们提出将对抗多臂赌博机方法与基因表达编程（GEP）相结合来解决SR问题，因此将该算法命名为 AB-GEP。
AB-GEP 遵循以下总体步骤：（1）它将数学表达式空间划分为k个子空间； (2) 初始化每个子空间的平均奖励； (3) 计算学习率； (4) AB-GEP在每一代中都利用修改后的Exp3-AvgExp3来选择一个子空间进行探索； (5) AB-GEP 使种群从当前子空间跳转到子空间ωi； (6) AB-GEP利用交叉和变异在子空间ωi中搜索（利用）； (7) AB-GEP 更新每个子空间的平均估计奖励。
2.2 选择子空间
AB-GEP根据在子空间ωi中个体的适应度值，来评估子空间ωi被选中的概率Pt。
公式（1）
由于以下两个原因，AB-GEP利用AvgExp3而不是Exp3来选择子空间。一个是Exp3基于中的所有历史奖励来选择子空间ωi。与Exp3不同，GEP是一种进化算法，在一轮（生成）中多次利用群体，而它只使用群体中最好的个体作为轮次奖励rt。rt根据以下的公式计算得到。
公式（2）
而公式（1）中的是学习率，其计算公式为
公式（3）
2.3 空间跳跃
在AB-GEP使用AvgExp3选择子空间后，它需要使种群从当前子空间ωj跳到ωi。为了实现从一个子空间跳到另一个子空间，AB-GEP将ωi中个体的编码替换种群中每个单独代码的头部编码。
2.4 空间利用
在种群跳到选定的子空间后，AB-GEP利用交叉和变异操作对子空间ωi进行搜索（利用）。
2.4.1 交叉
为了利用ωi，这些跳跃的个体通过交叉与ωi中最好的个体重组。尽管一个子空间中的许多连续组合可能会暂时使种群相似，但这种情况很快就会被跳出子空间的种群打破。当种群再次跳入时，种群与原始种群大不相同。因此，子空间之间的跳跃有助于算法避免陷入局部最优，并保持种群多样性。
2.4.2 变异
AB-GEP中的突变与原始GEP中的突变相似。突变可以发生在个体的头部和尾部。在头部，子空间编码之外的符号可以转换为另一个函数或终端。在尾部，符号只能更改为终端。
2.4.3 子空间评估
AB-GEP对子空间探索和利用后会对子空间进行评估，在AB-GEP中利用平均估计回报对子空间进行评估。的计算公式如下：
公式（4）
实验与结果:
3.1 数据集
我们使用两个数据集、SR 基准和实际基准来评估 AB-GEP 的性能。SR 基准由来自四个规范符号回归基准的 24 个 SR 问题组成：Nguyen、Korns、Keijzer 和 Vladislavleva。
现实世界的基准包括八个现实世界的问题。与 SR 基准测试不同，现实世界的基准测试涉及更多功能。这有助于研究 AB-GEP 在高维 SR 问题中的性能。
实验所使用的数据集基准和数据集的函数及常量如表1、表2和表3所示。
表1 符号回归基准
表2 候选函数及其常数
表3 实际基准数据集
3.2 实验结果
如图2和图3所示为所有基准的适应度比较结果。
图2 所有基准的适应度比较
图3 适应度比较
下图4所示为不同方法的种群多样性比较结果。
图 4 种群多样性比较
如图5所示为AB-GEP 和 SPJ-GEP 在选择子空间上的比较结果。
图5 AB-GEP 和 SPJ-GEP 在选择子空间上的比较
如图6所示为不同方法的收敛结果的比较。
图6 收敛比较
作者简介:
鲁强，副教授，硕士导师。目前主要从事演化计算和符号回归、知识图谱与智能问答、以及轨迹分析与挖掘等方面的研究工作。