| 标题 | Deep Neural Crossover: A Multi-Parent Operator That Leverages Gene Correlations |
|---|---|
| 作者 | Eliad Shem-Tov,Achiya Elyasaf |
| 机构 | Ben-Gurion University of the Negev Beer-Sheva, Israel |
| 论文 | https://dl.acm.org/doi/pdf/10.1145/3638529.3654020 |
摘要
我们提出了一种新的遗传算法（GA）中的双亲交叉算子，称为“深度神经交叉”（DNC）。与依赖于随机选择亲本基因的传统遗传算法交叉算子不同，DNC利用深度强化学习（DRL）和编码器-解码器架构的能力来选择基因。具体来说，我们使用DRL来学习选择有前途基因的策略。该策略是随机的，以保持遗传算法的随机性，代表了一种选择适应度提高概率更高的基因的分布。我们的架构具有一个循环神经网络（RNN），用于将亲本基因组编码为潜在记忆状态，以及一个解码器RNN，它利用基于注意力的指向机制在后代中的下一个选定基因上生成分布。操作员的架构旨在找到基因之间的线性和非线性相关性，并将其转化为基因选择。为了降低计算成本，我们提出了一种迁移学习方法，其中架构最初在特定领域内的单个问题上进行训练，然后应用于解决同一领域的其他问题。我们将DNC与已知的算子在两个基准域上进行了比较，其表现优于所有基线。
简介
遗传算法（GA）是一种基于群体的元启发式优化算法，它对候选解决方案群体（称为个体）进行操作，迭代地提高几代个体的解质量。遗传算法采用选择、交叉和变异算子，根据适应度函数计算的适应度值生成新的个体。
多年来，人们提出了许多交叉算子来增强种群收敛。通常，这些运算符是针对特定的问题域量身定制的，例如旅行商问题（TSP）、特征选择、作业调度等。本文介绍了一种新的领域无关交叉算子，该算子利用深度强化学习（DRL）和递归神经网络（RNN）的能力进行基因选择。我们的目标是创建一个可以无缝适应不同问题领域的算子，而不需要对每个问题进行手工调整。我们提出的交叉算子——深度神经交叉（DNC）——使用在线学习算法动态优化当前领域的交叉过程，而不依赖于预定义的特定问题设置。具体来说，它利用深度学习来优化基因选择机制。DNC学习了一种随机策略，在给定一组两个或多个父母的情况下，该策略返回一个子代在所有可能的后代中的分布，这些后代可以使用统一的交叉生成。对于这项任务，我们使用两个递归神经网络（RNN）——一个编码器和一个解码器网络。编码器将父对象转换为潜在特征向量。给定这些载体，解码器通过指向父母之一，逐个基因迭代构建子代基因组。对每个基因重复这个过程，直到产生完整的后代。
均匀交叉和单点交叉之间有一个关键区别：单点交叉假设基因之间有一定的顺序，这表明更接近的基因更有可能一起传递。相比之下，均匀交叉消除了这一假设，假设没有相关性。我们的方法代表了这一思路的进步。DNC算子是第一个旨在学习基因之间相关性的交叉算子，避开了预先存在的、可能有偏见的假设。这些相关性可以是线性的，也可以是非线性的。
我们在文献中只发现了一项利用机器学习进行领域无关交叉的工作。Liu等人提出了NeuroCrossover，这是一种利用transformer模型结合强化学习（RL）方法来优化多个交叉点选择的算子。他们应用他们的神经交叉模型来确定交叉点的位置，通过将其应用于2点交叉场景来举例说明。我们的方法与这种方法相似，因为这两种方法都使用RL。然而，有一些显著的差异需要注意。我们的方法允许运行多父交叉，正如我们在下面演示的那样，它极大地改善了结果。此外，NeuroCrossover优化了两个交叉点的选择，因此只检测与顺序相关的相关性，如n点交叉。另一方面，DNC按顺序逐一选择每个基因，使我们能够利用非线性基因相关性。
与均匀交叉等标准交叉方法相比，使用深度学习算法进行交叉可能会增加时间和计算资源。值得注意的是，DNC算子的训练不需要额外的评估。相反，它利用在线学习，在进化过程中计算的适应度值用于训练操作员。然而，为了解决与时间相关的问题，我们为我们的算子提出了一种迁移学习方法。最初，我们针对特定领域内的单个问题（例如，单个装箱实例）训练架构，随后应用训练过的算子来解决同一领域内的其他问题。我们比较了这两种方法在时间和计算资源以及由此产生的后代质量方面的性能。
我们在两个优化域中评估了我们的方法，并与已知的交叉算子进行了比较分析。我们用整数向量表示来测试我们的方法，尽管我们的方法是通用的，也可以应用于二进制和实值表示。这项工作的主要贡献如下：
•我们提出了一种新的领域无关、通用的交叉算子。
•我们提出了第一个算子，旨在发现基因之间的线性和非线性相关性，并将其转化为基因选择，而不对相关性类型做出任何有偏见的假设。
深度神经交叉
我们的深度神经交叉（DNC）算子旨在将多个表示为整数序列的亲本个体组合在一起。为了简化解释和数学符号，我们假设只有两个父节点，尽管相同的程序可以用于更多的父节点。我们将使用提出的DRL的神经组合优化技术进行基因选择过程。
我们的算子通过合并父母的基因来生产一个孩子。它可以生成与均匀交叉完全相同的后代，每个后代的生成分布都有所不同。也就是说，与均匀交叉相比，它为评分高的后代分配了更高的概率，在均匀交叉中，所有后代都有相等的生成机会。我们将这种概率表示为𝑝（𝑐|p1，p2），其中p1，p2是父节点，c是可以使用统一交叉生成的子节点。
我们使用以下链式规则来分解后代的概率：
对于每个基因组指数𝑗，概率𝑝(𝑐𝑗 | 𝑐<𝑗 , 𝑝1，𝑝2）从父母双方的相应基因中确定将哪个基因传递给索引𝑗处的后代，有效地分配了指向两个基因中的每一个的概率。此外，在对索引𝑗处基因的概率分布进行建模时。通过考虑到目前为止之前选择的基因组，我们将后代的概率分解为一个迭代决策过程，在这个过程中，我们可以依次选择每个个体的基因。
为了学习方程中的概率并生成后代，我们使用Bello等人提出的序列到序列架构，该架构由两个递归神经网络（RNN）模块组成——编码器和解码器。编码器网络将两个父节点映射到一个嵌入式表示中，解码器学习概率𝑝(𝑐𝑗 | 𝑐<𝑗 , 𝑝1，𝑝2），并根据该概率从该表示中生成一个新的子对象。
编码器。编码器RNN（如图所示）结合了长短期记忆（LSTM）单元，其超参数潜在大小为维度𝑑。编码器的输出是两个父节点的二维嵌入式表示。
解码器（如图所示）也保持其潜在的记忆状态{𝑑𝑒𝑐𝑗 }。
指针网络。表示选择子基因的分布（𝑝(𝑐𝑗 | 𝑐<𝑗 , 𝑝1，𝑝2）），我们使用指针网络。该网络使用一组softmax模块，并注意产生从每个亲本中选择基因的概率。它被称为指针网络，因为它利用注意力和softmax模块的组合来有效地指向输入序列中的特定位置。
此外，为了在搜索和开发后代之间取得平衡，我们引入了贪婪搜索。在这种概率为ɛ的方法中，通过为采样的后代选择一个随机基因来执行随机操作。
学习DNC权重
我们使用基于策略的强化学习来学习运算符的权重，即嵌入式基因组、编码器和解码网络以及指针网络的权重。由于总体目标是使适应度得分最大化，我们将奖励信号定义为𝐿（𝑐|𝑝1， 𝑝2）=𝑓𝑖𝑡𝑛𝑒𝑠𝑠（𝑐）。我们的目标是提高从策略分布𝜋𝜃中采样的生成子代的预期适应度得分，其中𝜃由我们的架构可学习参数参数参数化。策略分布𝜋𝜃接收两个亲本基因组，并返回由我们的架构生成的ε贪婪诱导的基因选择分布。因此，我们的目标函数是：
我们使用随机梯度下降的策略梯度方法REINFORCE优化我们的网络：
我们通过从策略分布中提取后代，使用蒙特卡洛采样来近似方程中的梯度。在进化过程中，通过进化过程为操作员选择两个父母。该策略为下一代生成后代，以及指针网络产生的基因选择概率。我们计算孩子的适应度，并将其与基因选择概率和孩子一起缓存。因此，算子不会增加评估的次数。一旦缓存达到指定的批大小，我们就利用它来近似目标函数的梯度。然后将这些近似梯度传递给优化器进行梯度下降优化。
多亲代支持
指针网络不限于两个参考向量。因此，我们的DNC算子支持多父交叉。具体来说，当使用𝑚≥2个父节点时，编码器的输出是一个长度为𝑚×𝑑的嵌入式表示。
训练过程不受影响，因为在每一代中，都会从种群中随机选择一批父母，每批父母的长度为𝑚。为了保持种群规模的一致性，我们从策略分布中为每个多父母交叉生成两个后代。
降低计算成本
如前所述，适应度值被缓存，DNC运算符的训练不需要额外的适应度评估。然而，它的训练过程比标准交叉（例如均匀交叉）消耗了更多的时间和计算工作量。我们认为，考虑到下文所证明的结果，额外的时间是值得的。此外，进化收敛速度更快，导致适应度评估更少（在许多情况下非常昂贵）。
然而，认识到与我们的架构相关的计算需求和训练时间，我们提出了一种迁移学习方法，通过在特定领域内的单个问题（例如，单个装箱问题）上进行训练来学习算子的权重，然后将训练好的算子应用于解决同一领域的其他问题。具体来说，我们对单个问题运行完整的遗传算法来训练架构，然后在该领域其他问题的演化过程中使用它。如下所示，这种方法大大缩短了运行时间，有时甚至优于基本的DNC运算符，从而允许在同一域内的各种问题实例中更有效地使用。
评估
域
为了评估所提出的算子的性能，我们在两个问题域上进行了广泛的实验：
图着色：给给定的图着色，使用尽可能少的颜色，这样就不会有两个相邻的顶点具有相同的颜色。在几篇论文中，图着色已被用作遗传算法的基准域。对于基准图，我们使用DIMACS数据集进行图着色。
箱子包装问题（BPP）：BPP要求将一组𝐿物品装入具有指定容量的箱子中。目标是尽量减少用于包装物品的箱子数量。在几篇论文中，装箱也被用作遗传算法的基准域。对于基准实例，我们使用Schoenfield_Hard28数据集，其中每个实例有160到200个项目。
基线交叉算子
我们将我们的方法与以下交叉算子进行了比较：
（1） 单点：沿着父母双方的遗传表示选择一个随机交叉点。超过这一点的遗传物质在父母之间交换，产生两个后代。
（2） 等概率均匀：每个基因位置都是从父母中以相等的概率独立选择的。
（3） 自适应一致性：等概率均匀交叉的一种变体，其中根据父母适应度的比率动态调整从特定父母那里继承基因的概率。
（4） 多父母：涉及两个以上的父母。与等概率均匀交叉类似，对于后代中的每个基因位置，遗传物质以相等的概率从父母之一遗传。我们使用了三个亲本基因组进行比较。
（5） NeuroCrossover：一种2点交叉算子，采用RL和编码器-解码器-transformer架构来优化遗传位点选择。
实验细节
我们在两个数据集上使用相同的遗传算法超参数进行了实验，唯一的变化是交叉算子。我们每个实验进行20次重复，并通过运行10000轮置换测试来评估统计显著性，比较我们提出的方法和其他方法之间的平均得分。
结果
下表显示了图着色和装箱实验的结果，比较了不同交叉算子的性能。这些表格报告了使用不同运算符进行进化时，20次以上最佳个体的平均适应度
接下来，我们将与NeuroCrossover进行比较。
下图可视化了不同交叉算子对图着色域中每一代最大适应度值的影响。每条绘图线代表一个不同的交叉运算符，可以直接比较它们在连续几代中的性能。Multi-Parent DNC在解决方案质量和收敛速度方面明显优于所有其他交叉算子。这种趋势在其他问题实例中持续存在。
在下表中，我们比较了具有均匀交叉的标准遗传算法（GA）和我们提出的算法之间的每一代时间。很明显，我们的方法产生了更高的计算成本，与标准遗传算法相比，运行时间增加了约780%。标准偏差和最大生成时间的显著变化源于每隔几代为反向传播执行的优化步骤。运行时和解决方案质量之间的权衡是显而易见的。在特定的问题实例中，我们的方法比最佳基线算子有了实质性的改进。然而，为了解决这个问题，我们为迁移学习方法（DNC-TL）进行了时间比较，在这种方法中，架构在问题域内的特定实例上进行了预训练，然后应用于其他问题。
我们进行了运行时截止分析，以可视化运行时和实现的解决方案质量之间的权衡。截止时间如图所示。
结论
我们引入了一种新的领域无关交叉机制，该机制利用深度强化学习来捕捉基因之间的相关性，以进行基因选择。我们的算子学习了一种策略，在给定一对父母的情况下，该策略会在所有潜在的后代上生成一个分布，这些后代可以通过均匀交叉产生。
我们的研究结果表明，将遗传算法与强化学习相结合进行基因选择可以通过选择有前途的后代而不是依赖随机生成的后代来提高解决方案的质量。均匀交叉和两点交叉之间有一个关键区别。后者假设基因之间存在一定的顺序，这表明更接近的基因更有可能一起传递。相比之下，均匀交叉放弃了这一假设。我们的方法代表了这一思路的进步。深度神经交叉可以在任何位置自主学习基因组之间的线性或非线性相关性，避免预先存在的偏见假设。指针网络是我们模型不可或缺的一部分，擅长学习基因之间的非线性相关性，并将这些相关性转化为基因选择。
在未来的工作中，我们的目标是将我们的方法扩展到位和实向量表示以及进化计算的其他分支，特别是遗传编程（GP）。我们认为，由于GP编码的搜索空间比GA大得多，DNC可以大大提高GP交叉的性能。
