基于薄板样条的预测机制，用于动态约束多目标优化

《Swarm and Evolutionary Computation》：Thin plate spline-based prediction mechanism for dynamic constrained multi-objective optimization

　　摘要
动态约束多目标优化问题（DCMOPs）由于在现实世界中的广泛应用而受到了广泛关注。然而，许多动态约束多目标进化算法（DCMOEAs）在预测阶段难以捕捉动态约束的Pareto解集，且约束会导致响应延迟。为了解决这些问题，本文提出了一种基于薄板样条预测机制（TPSEA）的DCMOEA。具体而言，该算法建立了相邻但不同环境中找到的解集之间的映射关系，利用这一关系根据现有的历史种群来预测未知种群。在预测阶段，预测机制利用目标空间中的映射关系来确定下一个环境的合理初始种群。为了避免在种群维护过程中丢弃可能被过滤掉的良好预测解，应用基于薄板样条的拟合方法来尽可能保留流形的结构特征。此外，还设计了一种基于角度多样性的维护策略来保持种群多样性。这种策略确保了预测阶段种群匹配的合理性，并在拟合过程中保持了流形结构。在包含19个DCMOPs的两个基准测试套件上的比较实验表明，TPSEA与七种最先进的DCMOEAs具有竞争力。GitHub仓库：https://github.com/T-loobby/DCMOP_TPSEA

引言
动态约束多目标优化问题（DCMOPs）已广泛应用于实际场景，如流体催化裂化[1]、[2]、氧化镁颗粒制造[3]和废水处理过程[4]。DCMOPs具有挑战性，因为它们涉及多个相互冲突的目标和可能随时间变化的约束。因此，在约束条件下跟踪可行的Pareto最优解已成为一个关键问题。为了解决这个问题，已经提出了各种动态约束多目标进化算法（DCMOEAs）[2]、[5]、[6]。通常，大多数DCMOEAs包含三个模块[7]、[8]、[9]：一个用于检测环境是否发生变化的检测器，一个用于应对环境变化的响应机制，以及一个在新环境中促进种群进化的静态优化器。先前的研究表明，这三个核心模块主要解决了两个关键问题[7]、[9]、[10]：如何设计高效的动态机制来更好地利用历史信息，以及如何设计稳健的约束处理技术来辅助种群进化。为了更好地利用历史信息，已经提出了许多优秀的策略。Chen等人[2]设计了一种动态响应机制，不仅保留了历史上有价值的解，还通过随机生成新解来探索可行区域。Chen等人[11]提出了一种子空间知识转移策略，通过划分子空间并使用卡尔曼滤波器来估计Pareto解集的位置。然而，由约束引起的不可行区域仍然对探索构成了挑战。

约束的存在使得在DCMOPs中捕捉动态约束Pareto最优集（DCPS）变得困难。Wang等人[12]使用概率模型通过近似匹配来预测响应机制的变化。然而，约束的存在使得匹配变得困难，可能导致不合理的情况，从而影响DCPS预测的准确性。为了关注约束函数对种群进化的影响，Yang等人[13]提出了一种双种群进化算法，采用层次变分策略来指导收敛。他们引入了一种主导解修复策略，通过非支配解的高斯分布来修复单目标变量，以增强收敛性。尽管这种策略在一定程度上有助于跨越不可行区域，但仍然是一个极具挑战性的任务。

薄板样条插值（TPS）是表面重建和变形建模中的重要工具，它可以通过最小化弯曲能量来实现离散点数据的平滑插值[14]。TPS因其出色的全局平滑性和物理可解释性而被广泛使用[15]。TPS与图1中的动态解集预测问题具有类似的结构特征，因为两者都涉及在连续空间中对离散点集的平滑拟合和外推[16]。由于TPS可以根据历史解集构建平滑的响应表面，因此它有潜力模拟动态环境中Pareto前沿（PFs）的连续演变。通过将解集演变过程转化为连续表面的时间序列插值问题，可以有效地捕捉和预测DCPS流形的平滑变化趋势。图1中的类比是机制上的，但仅限于TPSEA的目标空间部分。从相邻PF近似中采样的两个离散点集在目标空间中进行匹配，然后TPS从早期的近似构建到后期的平滑变形，同时最小化弯曲能量。外推的变形估计了下一个PF的几何形状，并支持历史环境的选择。这个局部模型适用于相邻PF连续或适度平滑变化的情况。

在当前研究中，现有的DCMOEAs在可行PF的位置、形状或拓扑发生变化时仍难以转移有用的种群信息[2]、[7]、[9]、[10]。本文通过基于TPS的目标空间预测器和目标空间角度对应规则来解决这个问题。这种方法的动机是局部平滑或适度变化的PF轨迹，而不是理论上的保证。完整的算法不会丢弃约束，而是在多个组件中使用它们。TPS充分利用了种群信息。

本文的贡献总结如下：
1. 提出了一种基于薄板样条插值的种群预测机制，该机制可以模拟目标空间中的连续变化，以预测动态环境中的PF变形。由此获得的目标空间信息用于定位决策空间候选解，这些候选解随后会在当前约束下进行评估；因此，它提供的是间接指导，而不是对未指定约束功能的直接预测。
2. 提出了一种基于角度的种群多样性维护策略。对于被准确预测但可能被错误分类为噪声的个体，在预测阶段执行薄板样条插值。在最终的拟合结果中，进一步维持角度多样性，从而为后续环境提供更合理的初始种群。
3. 将提出的TPSEA与七种竞争性的DCMOEAs在两个测试套件上进行了比较。结果显示，在大多数测试设置中，TPSEA具有优越的整体性能，尽管该方法并不是在所有问题和指标上都表现最佳。

本文的其余部分组织如下。第2节介绍了动态约束多目标优化的基本定义和相关工作。第3节描述了所提出的TPSEA。第4节比较并进一步分析了所提出的TPSEA与七种最先进的DCMOEAs的实验结果。最后，第5节总结了本文并讨论了未来的工作。

动态约束多目标优化
一般而言，DCMOP可以表示为以下形式[17]：
minF(x,t) = (f1(x,t), f2(x,t), …, fM(x,t))T,
s.t.
hk(x,t) = 0,
k = 1,…,
ags(x,t) ≤ 0,
s = a + 1,…,
a + b
x ∈ Ω1,
t ∈ Ω2,
其中x = (x1,x2,…,xD)T是一个D维决策向量，t表示时间变量，Ω1和Ω2表示决策空间和时间域，fp(x,t)是第p个目标，F(x,t)是M维目标向量，hk(x,t)表示第k个等式约束，gs(x,t)表示第sth个不等式约束。

基于动态性的动机
动机分为三个步骤。首先，环境变化可以改变PF的几何形状和可行区域，使得前一环境的最终种群成为一个不完美的初始化器。其次，目标空间几何形状和决策空间可行性起着不同的作用：几何形状可以指导历史环境的检索，而可行性必须在新的约束下评估候选解之后进行判断。第三，DCMOP将目标空间与...

比较算法
为了评估所提出的TPSEA的有效性，选择了七种最先进的DCMOEAs进行比较，包括DCMOEA [6]、DCNSGAIIA [5]、DCNSGAIIB [5]、DCNSGAIII [44]、MP-DFR [8]、SKTEA [11]和HATC [9]。所比较的实现使用相同的种群大小和停止规则。每种方法都保留了其在源实现中描述的响应和约束处理机制。关于20%的解被随机解替换的说法仅适用于...

结论
本文提出了用于DCMOPs的TPSEA。TPS预测目标空间PF的变形，并支持历史环境的检索，同时分别外推匹配的决策向量来初始化候选解。这种分离避免了目标到决策的逆向映射。目标空间角度对应、受限和辅助种群、随机补充以及变化后的修复支持适应。在19个DCF和DCP问题中，TPSEA获得了具有竞争力的MIGDCRedI

作者贡献声明
Hongbiao Tian：写作 – 审稿与编辑、写作 – 原始草案、可视化、数据管理。
Baosheng Li：验证、项目管理、资金获取、概念构思。
Xiaochuan Gao：验证、资源管理、调查。
Qianlong Dang：写作 – 审稿与编辑、项目管理、资金获取、数据管理。
Zhiyang Zhang：监督、软件。

利益冲突声明
作者声明没有利益冲突。