基于社区的方法来加速多目标优化中的收敛速度

《Swarm and Evolutionary Computation》：A neighborhood-based momentum approach to accelerate convergence in multi-objective optimization

　　陈龙灿|庞立蒙|张清富|石渕宏包 香港城市大学计算机科学系，中国香港 摘要 提高进化多目标优化算法（EMOAs）的收敛速度是计算智能中的一个关键挑战。在某些实际应用中，由于评估每个解决方案的成本较高和/或耗时较长，只能检查少量的解决方案。动量技术通过累积过去迭代的信息来加速优化过程。动量技术已广泛应用于单目标优化中。最近，动量技术也被用于进化多目标优化（EMO）的算法设计中。一些初步算法已经提出，表明使用动量可以提高EMOAs的收敛能力。在本文中，我们提出了一种基于邻域的动量方法，作为一种模块化的后处理步骤来加速EMOAs的收敛能力。通过采用模块化设计，所提出的方法可以嵌入到各种EMOAs中，作为附加增强而不改变其底层搜索策略。通过对人工测试问题和实际问题进行广泛的计算实验，我们证明了所提出的方法大大加快了EMOAs的收敛速度，并在不同算法框架中显示出有效性。

引言 在单目标优化中，目标是找到相对于单一目标函数的最佳解决方案。然而，在许多实际场景中，需要同时考虑多个相互冲突的目标[1],[2],[3],[4],[5]，这意味着改善一个目标会导致另一个目标的退化。这类问题被称为多目标优化问题（MOPs）。不失一般性，一个m目标最小化问题可以表示为：Minimize f(x) = (f1(x), f2(x),…, fm(x))T，受限于 x ∈ Ω，其中 x = (x1,x2,…, xd)T 是一个d维决策向量，Ω是决策空间，f: Ω → Rm 包含m个目标函数，Rm是目标空间，fi(x)是要最小化的第i个目标（i=1,2,…,m）。对于一个多目标优化问题，通常不存在同时优化所有目标的解决方案，因为这些目标是相互冲突的[6],[7],[8]。为了比较目标空间中的解决方案，经常使用帕累托优势关系。我们有以下定义：帕累托优势。给定Ω中的两个解决方案x和x′，如果对于所有k∈{1,2,…,m}都有fk(x)≤fk(x′)并且对于某些j∈{1,2,…,m}有fj(x)
背景 动量的概念最初是在[12]中为单目标优化提出的，它将过去的更新纳入当前更新步骤中。这个概念类似于经典物理学中的动量，其中一个物体在运动中积累惯性并倾向于保持运动状态。动量在单目标优化中得到了广泛的应用[13],[14]。动量最著名的应用是在神经网络的损失函数最小化的反向传播算法中[15]。

基于em的emo的通用框架 在算法1中概述了基于em的emo的通用框架。首先，我们初始化种群和候选解决方案集。然后，while循环的每次迭代对应于一代。在while循环内，第3行和第4行遵循标准的emoa程序。在第t代中，使用标准遗传操作生成后代解决方案集ot。后代解决方案集ot与当前种群pt合并，以选择下一个候选解决方案。

实验设置 本节解释了本文中使用的测试问题、参数设置和底层emos。为了确保严格和公平的比较，本研究的实验设计和设置与emo文献中的代表性工作[20],[24],[25],[26],[27],[28],[29],[30],[31]一致。

实验结果 为了验证所提出的em框架，我们的计算研究分为四个部分。在第一部分，我们通过将其集成到三个代表性的emos（nsga-ii、moea/d和sms-emoa）中，研究了我们提出的em框架的通用有效性和兼容性。在第二部分，为了理解我们框架的核心组件的行为，我们进行了两项分析：对步长参数η的敏感性分析，为其设置提供指导；以及消融研究。

结论与未来工作 本文介绍了一种新的基于动量的策略，旨在通过利用历史搜索信息生成有希望的候选解决方案来加速emos的收敛。通过广泛的计算实验，我们证明了em可以显著加快三种代表性emos（即nsga-ii、moea/d和sms-emoa）的收敛速度。此外，我们还展示了其可扩展性，证明了其能够改进三种最先进的大规模emos。

作者贡献声明 陈龙灿：撰写 – 审稿与编辑，撰写 – 原始草稿，验证，项目管理，方法论，调查，形式分析，数据整理，概念化。庞立蒙：撰写 – 审稿与编辑，监督。张清富：撰写 – 审稿与编辑，监督。石渕宏包：撰写 – 审稿与编辑，监督。

利益冲突声明 作者声明他们没有已知的可能会影响本文报告工作的财务利益或个人关系。

致谢 本研究得到了中国国家自然科学基金（项目编号62376115）和广东省重点实验室（项目编号2020b121201001）的支持。 或耗时较长，只能检查少量的解决方案。emo算法需要快速找到良好的权衡解决方案。因此，需要进一步提高收敛能力，以便在仅检查少量解决方案后找到良好的权衡解决方案。在提高emoas收敛能力的各种技术中，动量是有效的方法之一[9],[10]。在文献中，一些研究人员已经尝试为emoas设计动量方法[9]。在[9]中，提出了一种基于动量的moea d变体。moea d将mop分解为许多单目标子问题[11]。在使用标准遗传操作生成子问题的后代时，也将该子问题的动量移动添加到后代中。实验结果表明，动量技术显著提高了moea d的收敛能力。然而，由于动量移动是基于子问题定义的，这种方法只能用于基于分解的emoas。最近，[10]引入了一种通用动量方法，旨在与现有的emoas兼容。通过基于帕累托优势或解决方案替换等关系定义动量移动，该方法可以集成到几乎任何emoas中。初步结果证实了这种方法对于加速收敛是有希望的。在[10]的工作基础上，本文介绍了一种改进的动量（em）方法，解决了原始方法的两个关键限制。首先，我们解决了步长控制问题。原始方法直接将动量向量添加到后代解决方案中。与适当的步长相比，过大的（或过小的）步长可能会使算法不稳定（或效率低下）。为了缓解这个问题，我们的em包含了一个比例参数来调整动量步长。其次，我们探索了一种更有效的分配动量移动的策略。原始方法仅将动量应用于后代。假设邻近解决方案可以从类似的方向指导中受益，我们引入了一种机制，也将动量移动应用于当前种群中的后代邻居。这种新方法旨在更好地利用有希望的搜索区域，并更有效地引导种群朝向帕累托最优前沿。所提出的基于邻域的动量方法被设计为一个模块化的后处理步骤，以加速emoas的收敛能力。通过采用模块化设计，所提出的方法可以嵌入到各种算法框架中，而不干扰其基本的搜索逻辑。通过对人工基准测试和实际应用进行广泛的实证评估，我们证明了这种方法可以加速多种算法架构的收敛速度。需要注意的是，所提出的em是专门设计作为一种收敛加速器。多样性保持由底层的emoa负责。本研究还探讨了所提出的em是否可以有效地平衡收敛加速和多样性保持。本文的其余部分组织如下。第2节回顾了em中动量移动的定义。第3节介绍了我们提出的em并解释了基于em的emos的实现。第4节描述了实验设置，包括基准问题、用于比较的算法和性能指标。第5节展示了人工问题和实际问题的计算结果和分析。最后，第6节总结了本文并讨论了有希望的未来研究方向。 背景 动量的概念最初是在[12]中为单目标优化提出的，它将过去的更新纳入当前更新步骤中。这个概念类似于经典物理学中的动量，其中一个物体在运动中积累惯性并倾向于保持运动状态。动量在单目标优化中得到了广泛的应用[13],[14]。动量最著名的应用是在神经网络的损失函数最小化的反向传播算法中[15]。 基于em的emo的通用框架 在算法1中概述了基于em的emo的通用框架。首先，我们初始化种群和候选解决方案集。然后，while循环的每次迭代对应于一代。在while循环内，第3行和第4行遵循标准的emoa程序。在第t代中，使用标准遗传操作生成后代解决方案集ot。后代解决方案集ot与当前种群pt合并，以选择下一个候选解决方案。 实验设置 本节解释了本文中使用的测试问题、参数设置和底层emos。为了确保严格和公平的比较，本研究的实验设计和设置与emo文献中的代表性工作[20],[24],[25],[26],[27],[28],[29],[30],[31]一致。 实验结果 为了验证所提出的em框架，我们的计算研究分为四个部分。在第一部分，我们通过将其集成到三个代表性的emos（nsga-ii、moea d和sms-emoa）中，研究了我们提出的em框架的通用有效性和兼容性。在第二部分，为了理解我们框架的核心组件的行为，我们进行了两项分析：对步长参数η的敏感性分析，为其设置提供指导；以及消融研究。 结论与未来工作 本文介绍了一种新的基于动量的策略，旨在通过利用历史搜索信息生成有希望的候选解决方案来加速emos的收敛。通过广泛的计算实验，我们证明了em可以显著加快三种代表性emos（即nsga-ii、moea d和sms-emoa）的收敛速度。此外，我们还展示了其可扩展性，证明了其能够改进三种最先进的大规模emos。 作者贡献声明 陈龙灿：撰写 – 审稿与编辑，撰写 – 原始草稿，验证，项目管理，方法论，调查，形式分析，数据整理，概念化。庞立蒙：撰写 – 审稿与编辑，监督。张清富：撰写 – 审稿与编辑，监督。石渕宏包：撰写 – 审稿与编辑，监督。 利益冲突声明 作者声明他们没有已知的可能会影响本文报告工作的财务利益或个人关系。 致谢>
背景 动量的概念最初是在[12]中为单目标优化提出的，它将过去的更新纳入当前更新步骤中。这个概念类似于经典物理学中的动量，其中一个物体在运动中积累惯性并倾向于保持运动状态。动量在单目标优化中得到了广泛的应用[13],[14]。动量最著名的应用是在神经网络的损失函数最小化的反向传播算法中[15]。

基于em的emo的通用框架 在算法1中概述了基于em的emo的通用框架。首先，我们初始化种群和候选解决方案集。然后，while循环的每次迭代对应于一代。在while循环内，第3行和第4行遵循标准的emoa程序。在第t代中，使用标准遗传操作生成后代解决方案集ot。后代解决方案集ot与当前种群pt合并，以选择下一个候选解决方案。

实验设置 本节解释了本文中使用的测试问题、参数设置和底层emos。为了确保严格和公平的比较，本研究的实验设计和设置与emo文献中的代表性工作[20],[24],[25],[26],[27],[28],[29],[30],[31]一致。

实验结果 为了验证所提出的em框架，我们的计算研究分为四个部分。在第一部分，我们通过将其集成到三个代表性的emos（nsga-ii、moea/d和sms-emoa）中，研究了我们提出的em框架的通用有效性和兼容性。在第二部分，为了理解我们框架的核心组件的行为，我们进行了两项分析：对步长参数η的敏感性分析，为其设置提供指导；以及消融研究。

结论与未来工作 本文介绍了一种新的基于动量的策略，旨在通过利用历史搜索信息生成有希望的候选解决方案来加速emos的收敛。通过广泛的计算实验，我们证明了em可以显著加快三种代表性emos（即nsga-ii、moea/d和sms-emoa）的收敛速度。此外，我们还展示了其可扩展性，证明了其能够改进三种最先进的大规模emos。

作者贡献声明 陈龙灿：撰写 – 审稿与编辑，撰写 – 原始草稿，验证，项目管理，方法论，调查，形式分析，数据整理，概念化。庞立蒙：撰写 – 审稿与编辑，监督。张清富：撰写 – 审稿与编辑，监督。石渕宏包：撰写 – 审稿与编辑，监督。

利益冲突声明 作者声明他们没有已知的可能会影响本文报告工作的财务利益或个人关系。

致谢 本研究得到了中国国家自然科学基金（项目编号62376115）和广东省重点实验室（项目编号2020b121201001）的支持。>