一种面向动态约束多目标问题的时序图注意力网络辅助进化算法

《Knowledge-Based Systems》：A temporal graph attention network-assisted evolutionary algorithm for dynamic constrained multi-objective problems

　　

•针对 DCMOPs 提出了一种时间图注意力辅助进化算法。
•构建了一种基于时间图的预测模型来评估解的质量。
•设计了一种基于 Rényi 散度的更新触发指标。
•设计了一种预测驱动的环境响应策略。
•实验结果表明所提出的 T-DCMOEA 的有效性。

引言
动态约束多目标优化问题 (DCMOPs) 出现在许多工程应用中，包括调度 [1], [2]、路径规划 [3], [4] 和特征选择 [5]。一般的 DCMOP 可以表述如下：
最小化 F(x,t)=[f1(x,t),f2(x,t),…,fm(x,t)]^T
受限于 gi(x,t)≤0, i=1,2,…,p,
hj(x,t)=0, j=1,2,…,q,
x=(x1,x2,…,xD)^T∈Ω,
其中 x 是决策空间 Ω 中的 D 维决策向量，t 表示时间。目标向量 F(x,t) 包含 m 个时间相关目标，其中 fk(x,t) 表示时间 t 下的第 k 个目标，k=1,2,…,m。此外，gi(x,t) 和 hj(x,t) 分别表示时间 t 下的第 i 个不等式约束和第 j 个等式约束。解决 DCMOP 需要识别一组可行解，在变化的环境中保持好的收敛性和多样性。

在 DCMOPs 中，跟踪不同环境下的帕累托前沿 (PF) 是困难的，因为变化的目标和约束可以显著改变可行区域的拓扑结构 [6]。图 1 说明了在时间 t 时真实帕累托前沿 (TPF) 与无约束帕累托前沿 (UPF) 重合的情况。在时间 t+1，约束的变化缩小了可行区域，从而导致 TPF 发生偏移。这个例子展示了动态约束如何重塑搜索空间并影响最优解。

提出了多种动态约束多目标进化算法 (DCMOEAs) 以持续跟踪时变 PF 并为新环境提供高质量的初始解 [7]。这些算法可以分为三类：(1) 基于多样性的 DCMOEAs [8]，(2) 基于记忆的 DCMOEAs [9]，和 (3) 基于预测的 DCMOEAs [10]。

近年来，基于预测的 DCMOEAs 受到了越来越多的关注。然而，两个关键局限性阻碍了它们的性能。首先，这些算法通常关注帕累托最优集 (PSs) 或 PFs 的动态趋势，而忽视了同一环境中解之间的内在相关性。当环境变化频繁发生时，这一局限性可能阻碍为新环境生成高质量的初始解。糟糕的初始化使得在下一次变化之前识别出高质量的 PS 变得更加困难，从而造成性能恶化的循环 [11], [12]。其次，大多数基于预测的 DCMOEAs 在检测到环境变化后立即更新其预测模型。这种响应式策略在实际应用中可能是不必要的且计算效率低下。重用前一个环境的解是构建新环境初始种群的天然方法；然而，当环境变化频繁或解评估成本高昂时，重新评估这些解可能非常耗时。

在 DCMOEAs 中，搜索在种群层面操作，个体表现出内在的相互依赖性。静态图神经网络 (GNNs) 可以捕捉个体之间的结构依赖性，但无法明确表示连续环境之间的进化趋势。因为种群拓扑结构随环境变化，它可以自然地建模为动态图。基于长短期记忆 (LSTM) 的模型可以从历史解中学习进化模式，但无法明确保留个体之间的关系结构。同样，传统的预测模型通常基于个体或种群的向量化特征操作，因此无法有效表示随时间演化的种群拓扑。相比之下，时间图注意力网络 (TGAT) 在预测和分类任务中表现出了强大的性能 [13]。在 DCMOPs 中，邻居聚合可以捕捉个体之间的结构相关性，而时间编码可以表示种群随时间的演化。注意力机制进一步使模型能够自适应地地区分不同邻居个体和历史交互的贡献。因此，TGAT 能够刻画环境内种群结构跨环境进化依赖性，这使其特别适合 DCMOPs 的动态特性。

为解决这些局限性，本文提出了一种时间图注意力网络辅助进化算法 (T-DCMOEA) 用于 DCMOPs。首先，使用改进的 TGAT 构建一个离线预测模型，将一组解表示为图。其次，引入了一种基于 Rényi 散度 (RD) 的更新触发指标 [14] 来检测种群分布的变化。当指标超过自适应阈值时，使用历史信息更新预测模型。最后，基于所得模型的环境响应策略为新环境提供高质量的初始种群。本文的主要贡献总结如下：
•将离线预测模型集成到 DCMOEA 中，以有效建模 DCMOPs 的解之间的关系和环境动态。
•提出了一种新的基于 RD 的更新触发指标来量化环境变化对种群分布的影响。通过避免不必要的预测模型更新，该指标提高了 T-DCMOEA 对频繁变化环境的适用性。
•一种新颖的环境响应策略使用预测模型来评估个体质量。通过整合个体特征、种群结构信息和时间信息，该策略指导为新环境生成高质量的初始种群。

本文的其余部分组织如下。第 2 节回顾相关工作。第 3 节详细描述所提出的算法。第 4 节介绍实验设置和参数配置。第 5 节分析实验结果。第 6 节总结本文并概述未来研究方向。

章节片段
DCMOEAs
已提出几种环境自适应响应机制来提高进化算法对 DCMOPs 的搜索能力和响应能力 [15], [16], [17]。基于它们的响应策略，现有的 DCMOEAs 可以大致分为三组：(1) 基于多样性的 DCMOEAs，(2) 基于记忆的 DCMOEAs，和 (3) 基于预测的 DCMOEAs。
基于多样性的 DCMOEAs 维持种群多样性，以提高在动态环境中的鲁棒性和适应性，其中以前

所提出的算法
本节详细描述所提出的 T-DCMOEA。该方法旨在通过预测新环境中个体的质量来增强在动态环境中的适应性。T-DCMOEA 对环境变化做出快速响应，保留高质量解，并平衡收敛性和多样性。为清晰起见，表 1 总结了本节中使用的主要符号和术语。第 3.1 节介绍整体框架（见图 3）。

对比算法
选择了七个代表性算法从不同方法论角度评估 T-DCMOEA：DCNSGAIIA [32], DC-MOEA [33], dCMOEA [23], mEDCMOA [20], FGSP [7], MOEAD-XGB [34], 和 LSTM-DMOEA [35]。根据第 2 节介绍的分类法，这些算法涵盖了 DCMOEA 研究中的三种主要环境响应范式：基于多样性的、基于记忆的和基于预测的方法。因为一些算法结合了多种响应操作，它们是

结果与讨论
本节在不同的实验设置下评估 T-DCMOEA。由于空间限制，补充材料在 A-E 节中展示了额外的实验和结果，包括 α 的敏感性分析、离线学习和在线更新策略的验证，以及剩余的 PF 比较。

结论
本文提出 T-DCMOEA 以改进对动态约束多目标优化中环境变化的响应。首先，从训练数据集中构建时间图以建模种群结构随时间的变化，并预训练一个离线预测模型。然后，更新触发指标仅当其值超过自适应阈值时才允许在线更新。所得模型被纳入环境响应策略中以预测个体

CRediT 作者贡献声明
Chunliang Zhao：资源，调查。Peng Ning：撰写 – 初稿，方法论，形式分析。Yiqin Zhang：资源，形式分析。Yuanyuan Hao：撰写 – 初稿，方法论。Zhong Li：方法论，调查。Yi Xiang：资源，调查。

未引用参考文献
表 2

利益冲突声明
作者声明他们没有任何已知的竞争财务利益或个人关系，这些可能会被认为影响了本论文报告的工作。

Chunliang Zhao|Peng Ning|Yiqin Zhang|Yuanyuan Hao|Zhong Li|Yi Xiang