用于算法性能预测的 GNN 框架

抽象。

数值黑盒优化中的自动算法性能预测通常依赖于问题特征，例如探索性景观分析特征。这些特征通常用作机器学习模型的输入，并以表格格式表示。然而，这种方法往往忽略了算法配置，而算法配置是影响性能的关键因素。算法运算符、参数、问题特征和性能结果之间的关系形成了一个复杂的结构，最好用图表表示。

这项工作探索了异构图数据结构和图神经网络的使用，通过捕获问题、算法配置和性能结果之间的复杂依赖关系来预测优化算法的性能。我们重点介绍两个模块化框架 modCMA-ES 和 modDE，它们分解了两种广泛使用的无导数优化算法：协方差矩阵适应进化策略 （CMA-ES） 和差分进化 （DE）。我们在 6 个运行预算和 2 个问题维度上评估了 24 个 BBOB 问题的 324 个 modCMA-ES 和 576 个 modDE 变体。

在M⁢S⁢E与传统的基于表格的方法相比，这项工作突出了几何学习在黑盒优化中的潜力。

数值黑盒优化长期以来一直是一个活跃的研究领域，导致开发了许多优化算法。因此，自动算法性能预测等元学习任务（Trajanov 等人，2021)、算法配置（Schede 等人，2022)和算法选择（Kerschke 等人，2019)对于确定最适合给定问题的算法变得越来越重要。

多年来，已经引入了许多新颖的算法思想，以及对众所周知的无导数优化算法的逐步改进，例如协方差矩阵适应进化策略 （CMA-ES）（Hansen 和 Ostermeier，1996)和差分进化 （DE）（斯托恩和普莱斯，1997).这些进步进一步使优化算法的前景多样化，使得系统地比较和选择它们更具挑战性。

为了解决这个问题，模块化优化框架（如 modCMA-ES（de Nobel 等人，2021)和 modDE（Vermetten 等人，2023)将 CMA-ES 和 DE 分解为模块化组件，使研究人员能够分析不同的配置和参数设置如何影响性能。通过捕获有关算法结构和交互的详细信息，这些框架为算法分析提供了丰富的资源。然而，尽管它们具有潜力，但它们在元学习任务中仍然没有得到充分利用。

传统的算法性能预测方法通常依赖于问题特征的表格表示，例如探索性景观分析 （ELA）（Mersmann 等人，2011).虽然有效，但这些方法无法捕捉问题、算法、配置和性能结果之间复杂的相互依赖关系。将这些实体表示为图形中的节点，边缘捕获它们的关系，自然地反映了数据的关系结构，并支持更丰富的建模。

几何学习，机器学习的一个分支，用于处理非欧几里得域（如图和流形）中的数据（Bronstein 等人，2017)为这项任务提供了合适的框架。它的方法范围从浅节点嵌入到更高级的图形神经网络 （GNN），所有这些都利用数据中的关系和拓扑信息。

此概念的早期演示涉及将性能预测建模为链接预测任务。具体来说，在我们之前的工作中（Kostovska 等人，2023b)，我们采用浅节点嵌入来推断模块化优化算法和黑盒问题之间的“缺失”性能链接，如果算法在固定的函数评估预算内达到预定义的精度阈值，则将链接标记为已解决。虽然有效，但这种方法将性能预测视为二元分类任务，而不是更具表现力的回归问题。此外，浅层嵌入将框架限制在转导学习上，将泛化限制在看不见的问题上。

GNN 通过捕获高阶依赖关系和实现归纳学习来解决这些限制。虽然尚未应用于模块化优化算法，但 GNN 已成功应用于相关领域。例如，Lukasik 等人。（Lukasik 等人，2021)使用 GNN 预测 NAS-Bench-101 上的神经架构性能（Ying 等人，2019 年b)和 Singh 等人。（Singh 等人，2021)将深度网络建模为图形以改进运行时预测。Chai 等人。（Chai 等人，2023)提出了 PerfSAGE，这是一种基于 GNN 的模型，用于预测边缘设备上神经网络的推理延迟、能耗和内存占用。

我们的贡献：在这项研究中，我们应用 GNN 来预测模块化优化算法的性能。首先，我们提出了一种异构图表示，对来自 modCMA-ES 和 modDE 的数据进行编码，在统一的图结构中捕获问题、算法组件、参数和性能。其次，基于这种表示形式，我们引入了一个消息传递 GNN 框架，该框架旨在对异构图进行作，在性能节点上执行节点回归，以预测算法在给定问题上的性能。最后，我们提出了实验，表明与传统的表格方法相比，通过基于图形的模型合并关系结构可以提高预测性能。

大纲：本文的其余部分结构如下：第 2 节详细介绍了我们研究中采用的方法，包括图形构造和 GNN 设计。第 3 节概述了实验设置。第 4 节介绍了研究的结果，第 5 节总结了对未来工作的见解和方向。

代码和数据：本研究中使用的所有相关代码和数据均可在以下网址获得：https://github.com/KostovskaAna/GNN4PerformancePrediction。

本节概述了我们在模块化优化框架的基准测试数据上使用 GNN 预测算法性能的方法。我们描述了异构图表示，然后是 GNN 模型架构。

我们使用异构图来捕获黑盒优化问题、模块化优化算法、它们的配置和相应的性能分数。

异构图 （HG） 定义为图形H⁢G={𝒱,ℰ,ℛ,𝒯}哪里𝒱表示节点集，ℰ表示边集，ℛ表示关系类型的集合，并且𝒯表示节点类型的集合。每个节点v∈𝒱通过映射函数与节点类型关联T⁢(v):𝒱→𝒯和每条边e∈ℰ通过映射函数与关系类型关联R⁢(e):ℰ→ℛ.要使图形被视为异构图形，不同节点和关系类型的和必须大于 2，即|𝒯|+|ℛ|>2.除了类型映射之外，每个节点v∈𝒱与特征向量关联𝐱v∈ℝd哪里d表示特征空间的维数。这些节点功能对节点的属性进行编码。

在图 1 中，我们说明了我们提出的异构图的元图。这个元图是我们的H⁢G代表𝒯（节点类型集）作为节点，将ℛ（关系类型的集合）作为它们之间的边。它包括参数、参数类、算法执行部分、算法、性能、黑盒优化问题六种节点类型，以及五种边（关系）类型：has-parameter、has-parameter-class、controls-algorithm-execution-part、has-algorithm 和 has-problem。

在图 2 中，我们说明了𝒱和ℰ，提供相应异构图的快照。它显示了两个黑盒问题、两个算法变体及其关联的性能节点和参数。这些参数属于 local_restart、 base_sampler 和 elitism 类，影响算法执行的不同部分。我们根据问题维度、运行时间预算和算法类型的独特组合构建一个图，从而产生多个图实例。

我们采用异构消息传递 GNN 架构来处理图中的多个节点和关系类型。从本质上讲，GNN 中的消息传递涉及每个节点从其邻居那里收集“消息”，并对其进行转换和组合以更新自己的表示形式。在异构设置中，不同的节点和边缘类型需要不同的消息传递函数或聚合过程，这是文献中公认的方法（Zhang 等人，2019).因此，每种关系类型r指示消息如何从tu到类型为tv.在聚合每个关系的消息后，我们整合所有相关关系类型的输出，以形成更新的节点嵌入。在多个层上重复此过程使节点能够从图形中越来越远的部分捕获信息。

我们的架构支持堆叠多个消息传递层（参见图 3）。我们使用 GraphSAGE（Hamilton 等人，2017)的归纳功能，尽管其他消息传递层也兼容。每一层都执行特定于关系的聚合，然后执行交叉关系聚合，通过激活函数引入非线性，并应用随机失活以防止过拟合。

学习任务是节点回归，其目标是预测算法在特定问题实例上的性能。每个性能节点都与一个数字分数相关联，GNN 通过利用异构图的结构和特征来学习预测它。最终的 GNN 嵌入通过线性层来预测性能值y^.

请注意，这种经过训练的模型能够跨不同的算法变体进行泛化，预测给定运行时预算和问题维度下所有模块化算法变体的性能。此外，尽管输入图（图 2）是有向的，但我们添加了反向边缘，有效地将图视为无向图。这实现了双向信息流并改进了表示学习。

我们使用了 COCO 环境中 BBOB 基准测试套件中的 24 个单目标、无噪声、连续黑盒问题（Hansen 等人，2020).每个问题都包含通过转换（如 offsets 和 scalings）生成的多个实例。我们为维度D=5和D=30.为了表示问题态势，我们使用了 OPTION KB 中提供的 46 个 ELA 功能 （Kostovska 等人，2023 年一).

我们考虑两种模块化算法： CMA-ES 和 DE。对于 CMA-ES，我们使用 modCMA-ES 框架（de Nobel 等人，2021)，其中包括采样分布、加权方案和重启策略的变化。对于 DE，我们使用 modDE 软件包（Vermetten 等人，2023)，它支持一系列突变运算符、碱基选择选项、交叉策略和受最先进的 DE 变体启发的更新机制。有关模块和参数空间的完整详细信息，请参阅（Kostovska 等人，2023b)，此数据已从中重复使用。

我们总共分析了 324 个 modCMA-ES 和 576 个 modDE 变体。每个都根据六个功能评估预算进行评估，B∈{50⁢D,100⁢D,300⁢D,500⁢D,1000⁢D,1500⁢D}哪里D∈{5,30}.记录在每个预算下实现的最佳精度（即与最佳精度的距离）。

本研究中使用的所有数据均重复使用自 Kostovska 等人。（Kostovska 等人，2023b)并通过 OPTION KB 访问（Kostovska 等人，2023 年一).

我们使用深度图库 （DGL） 实现 GNN 架构（王，2019)预测模块化优化算法的性能。该模型使用基于 GraphSAGE 算法的 SageConv 层（Hamilton 等人，2017)，用于按关系消息聚合。然后使用 HeteroConv 层将这些嵌入进行组合以进行交叉关系聚合。均值聚合应用于关系内，而求和则用于关系。

我们使用 4 层 GNN 来捕获所有相关的算法信息。问题节点由 46 个 ELA 特征表示，而其他节点类型的特征使用 Kaim 均匀分布进行初始化。我们使用 GELU（Hendrycks 和 Gimpel，2016)to 引入非线性。

我们执行嵌套交叉验证以调整辍学率 （0.1、0.2、0.3） 和嵌入大小 （32、64、128），每个实验重复 10 次。使用 L1 损失训练模型 200 个 epoch，并使用 Adam 进行优化（Kingma 和 Ba，2014)（学习率 0.1，每 20 个停滞 epoch 减半）。我们采用与之前工作相同的 leave-instance-out 嵌套交叉验证协议（Kostovska 等人，2024)，我们在其中训练 46 个 ELA 特征的随机森林 （RF） 回归器。这些是评估我们的 GNN 模型的基线。

在上述设置的基础上，我们进行了实验来预测模块化算法的性能。表 1 显示了两个维度和六个预算的 MSE 分数，仅使用 Kostovska 等人的表格 ELA 特征将 GraphSAGE 模型与射频基线进行了比较。（Kostovska 等人，2024).

GNN 在所有设置下通常都优于 RF。对于 modCMA 和5⁢D问题维度，GNN 将 MSE 提高0.03–0.06对于较低的预算 （50⁢D,100⁢D），而对于较大的预算（例如5.19→4.57在1500⁢D).在30⁢D问题维度，中高预算的收益更为明显，例如，在100⁢D，MSE 从0.27自0.19和1000⁢D，则相对改进达到36.6%.

对于 modDE 在5⁢D，对于大多数预算，GNN 的 MSE 低于 RF，其中改善最大，为300⁢D和500⁢D.在30⁢D，GNN 的性能始终优于 RF。最佳增益在100⁢D，其中 MSE 从0.25自0.19，则相对提高24%.在500⁢D，则增益为15.8%.

在这项研究中，我们探讨了 GNN 在数值黑盒优化中预测模块化优化算法的性能。我们的结果表明，GNN 通过捕获问题、算法配置和性能结果之间的关系，优于表格 RF 模型。据我们所知，这是第一个将异构图结构和 GNN 应用于该领域性能预测的工作，为增强算法配置和选择等元学习任务提供了一个有前途的方向。

未来研究的有前途的方向包括探索 GraphSAGE 之外的替代 GNN 架构，例如图注意力网络（Velickovic 等人，2017)或 Graph Transformers（Yun 等人，2019)，这可能会进一步增强预测性能。GNNExplainer 等可解释性方法（Ying 等人，2019 年a)可以提供有关哪些节点、关系和特征对预测影响最大的见解。通过对异构图进行微调来利用预训练的 GNN 也可以提高泛化性。摆在面前的一个关键挑战是将这种方法扩展到非模块化算法，这需要算法组件及其配置的标准化词汇表——这项任务需要更广泛的社区合作。