一种用于多目标进化算法的自适应双种群与密度差异调和距离

《Swarm and Evolutionary Computation》：An adaptive Bi-population and harmonic distance of density differences for multi-objective evolutionary algorithm

　　

**摘要**

在多目标优化问题中，保持收敛性与多样性之间的平衡被认为是算法设计中的关键挑战。因为两者之间固有的矛盾往往导致算法性能的退化。因此，本文提出了一种基于超支配度评估的自适应双种群划分和多目标进化算法密度差调和距离（ABP-HDD）方法。在ABP-HDD中，提出了一种基于超支配度评估的自适应双种群划分策略。种群被自适应地划分为两个交互组件：一个以精英为导向的子种群，负责开发高质量区域并确保收敛；另一个是潜在探索子种群，负责探索稀疏或未发现的区域以维持多样性。这两个子种群在进化过程中动态共享信息，个体根据其当前的超支配度被持续重新评估和重新分配。这种协作机制增强了个体分配和全局探索的合理性，同时防止种群过早收敛到局部最优解。此外，提出了一种新的环境选择策略，即密度差调和平均距离（HDD）策略，以防止潜在探索子种群中的过早收敛。HDD策略通过计算个体之间的密度差来评估种群多样性。它能够有效地区分高维空间中来自不同分布区域的解，从而在环境选择中更好地平衡探索和开发。最后，实验结果表明，ABP-HDD在48个测试函数上能取得更好的结果，并具有一定的竞争力。

**引言**

随着复杂系统所涉及的决策问题日益复杂化，例如最优控制[1]、工业设计[2]和能源调度[3]，决策者在优化建模过程中通常需要同时解决多个相互冲突的目标。典型的权衡包括性能提升与成本控制、减排需求与供电可靠性，以及其他相互竞争的准则。涉及两个或多个相互冲突目标的优化问题正式称为多目标优化问题（MOPs）[4]。数学上，一个MOP表述如下：

min F(x) = (f?(x), f?(x), ?, f_M(x))?
s.t. x ∈ Ω

其中 x = (x?, x?, ?, x_D)? 是有界搜索空间 Ω 中的 D 维决策变量，M 是目标函数的数量。

为求解 MOPs，传统数学规划方法[5]（如加权求和方法[6]和 ε-约束方法[7]）需要依赖对问题的先验知识。此外，这些方法在处理非凸、高维或离散的帕累托前沿（PF）问题时能力有限，严重限制了其实际应用性。相比之下，进化算法（EAs）由于其种群搜索特性，能够并行探索解空间并有效近似帕累托前沿，已成为多目标优化的主流方法。然而，随着问题复杂度的增加，经典多目标进化算法（MOEAs）仍面临一些挑战，例如收敛性与多样性之间的矛盾、高维目标空间中选择压力的维持以及高计算成本[8]。这些局限性凸显了对更高级策略以提升算法性能的持续需求。认识到这些挑战，多目标优化在顶级人工智能和机器学习社区中日益受到关注。认识到这些挑战，多目标优化在人工智能和机器学习社区中日益受到关注。例如，最近提出的利用基于学习的空间划分的新方法[9]、用于进化分解的先进标量化方法[10]，以及 Metropolis 算法的多目标变体[11]，旨在更好地平衡探索和开发。此外，多目标问题的先进启发式搜索[12]和期望超体积（HV）改进等指标驱动的评估[13]也得到了广泛探索，以解决高维空间中的可扩展性和性能评估问题。当代 MOEAs 主要采用三种基本框架。当代 MOEAs 主要采用三种基本框架。

第一类框架基于帕累托支配关系。这些算法通过非支配排序筛选最优解，并通过拥挤距离等指标维持解集的分布。Wang 等人[14]提出了基于参考向量的帕累托支配关系，以获得具有良好收敛性和多样性的解。Zitzler 等人[15]通过精细化适应度分配、密度差和高级存档截断方法的巧妙集成增强了帕累托优化。Molina 等人[16]引入了 g-支配，Said 等人[17]开发了 r-支配，两者都基于参考点方法建立了新的支配关系。Deb 等人[18]提出了一种基于网格系统的 ε-支配方法，实现了种群分布的显式管理。He 等人[19]引入模糊逻辑开发了一种新的模糊帕累托支配准则，具有增强的适应度评估。

第二类由基于分解的算法组成，采用聚合函数引导方法。在这些方法中，MOPs 被分解为多个单目标子问题，从而实现通过协调解的并行优化[20]。Zhang 等人[21]开创了将 MOPs 分解为多个标量优化子问题，利用邻居信息进行协同进化。Wang 等人[22]开发了一种偏好启发的协同进化算法，采用自适应权向量，在优化过程中动态引导解向帕累托前沿移动。Cheng 等人[23]提出了一种参考向量引导的进化算法，将 MOPs 分解为单目标子问题，同时结合用户偏好。Cai 等人[24]通过新颖的排序确保收敛性，通过基于角度的选择机制维持种群多样性，增强了 MOEA/D 框架。

第三类由基于指标的算法组成，采用特定的质量指标评估候选解并引导进化过程。这些方法直接根据超体积和反向世代距离（IGD）等性能指标优化种群，为解的质量提供显式控制[25, 26, 27, 28, 29]。Bader 等人[25]使用蒙特卡罗采样方法通过近似 HV 计算其值，降低了计算复杂度。Gomez 等人[26]创新性地结合 R2 指标和 Goldberg 的非支配排序方法。Jiang 等人[27]提出了一种计算高效的 MOEA 框架，利用快速 HV 贡献更新。Lopez 等人[28]参考集合技术进行解质量评估，比精确 HV 计算具有更低的计算开销。Tian 等人[29]通过基于候选解贡献的自适应参考点调整机制增强了 IGD 指标。

尽管上述方法取得了显著进展，但仍存在以下瓶颈。例如，基于拥挤距离[30]和参考向量[31]的环境选择策略需要预设分布参数，无法适应复杂的帕累托几何形状。这容易导致种群陷入局部最优或分布不均匀，从而导致多样性与收敛性之间的矛盾[32]。此外，当目标数量增加时，传统的帕累托支配关系变得无效，多样性保持机制的计算开销呈指数增长，严重影响算法的可扩展性，导致高维算法的计算效率下降。最近，为应对这些可扩展性和复杂优化瓶颈，提出了空间离散化进化搜索[33]和大规模多目标问题的缩放变换矩阵[34]等新方法，以及对大规模进化优化的综合研究[35]。尽管取得了这些进展，大多数算法仍然具有单一的搜索模式并依赖固定的种群结构。这很难动态平衡全局探索和局部开发，容易陷入过早收敛或冗余搜索。

为了更好地平衡全局探索和局部搜索，本文提出了一种基于超支配度的自适应双种群和多目标优化密度差调和距离算法（ABP-HDD）。在 ABP-HDD 中，提出了一种基于超支配度进化的自适应双种群划分策略，将种群分为精英导向子种群和潜在探索子种群。这种划分旨在提高个体分配和全局探索的合理性。对于精英导向子种群，通过阈值控制多样性与收敛性之间的平衡以获得更高质量的解。因此，使用了一种容忍度控制策略，通过控制容忍度来平衡精英导向子种群的收敛性和多样性。此外，潜在探索子种群负责探索解空间中未探索的区域。因此，提出了一种基于密度差调和平均距离（HDD）的新型环境选择策略。该 HDD 策略通过精确计算个体之间局部密度差的调和平均值来实现种群多样性的评估和维护，增强了 ABP-HDD 的可扩展性，同时保持种群多样性。本文的主要贡献如下：

(1) 基于超支配度，提出了一种自适应双种群划分策略。为提高个体分配的合理性，该方法通过协同进化有效平衡全局探索和局部开发。这种平衡有助于防止因过度收敛而导致的多样性过早丧失。

(2) 提出了一种具有 HDD 策略的新型环境选择方法。为了维持种群多样性并提高解的质量，将 k 近邻和密度差集成到距离计算中，从而在环境选择中更好地平衡探索和开发。

(3) 设计了一种多样性保持策略和精英保留的再选择机制，以扩展种群的搜索范围并利用精英解引导收敛方向。

(4) 实验结果表明，与大多数现有算法相比，所提出的 ABP-HDD 在 48 个测试函数上取得了更好的性能。此外，它在进一步求解可分离性和多峰值的多目标问题方面也具有进一步的研究价值。

本文的其余部分如下。第 2 节主要介绍相关工作。第 3 节介绍所提出的 ABP-HDD 的原理。第 4 节介绍实验设置。第 5 节分析和比较实验结果。第 6 节总结本文工作。

**各节摘要**

**帕累托支配**

假设 x? 和 x? 是 MOPs 的两个解。解 x? 帕累托支配 x?，记为 x? ? x?，当且仅当满足公式(2)中指定的条件时成立[36]。

?i ∈ (1, 2, ?, M): f_i(x?) ≤ f_i(x?)
?i ∈ (1, 2, ?, M): f_i(x?) < f_i(x?)

图 1 提供了目标空间中支配关系的示例。如图 1 所示，x? 在两个目标上的值都小于 x? 对应的目标值，因此 x? ? x?。类似地，x? ? x?，因为 f?(x?) = f?(x?)，而 f?(x?) < f?(x?)。在

**提出的算法**

本节将详细介绍所提出的 ABP-HDD 的整体框架。描述了超支配度评估机制、基于超支配度的自适应双种群划分策略、多样性保持策略、精英保留再选择机制和 HDD。最后，分析了 ABP-HDD 的计算复杂度。

**基准测试问题**

本文在一套标准基准测试函数上进行了全面的实验评估，具体包括 DTLZ 和 WFG 系列。这些基准在 MOPs 社区中被广泛认可，它们能够评估优化算法在各种问题特性下的性能。每个受调查的算法在不同的条件下进行测试。决策变量维度 D 分别设置为 10、30 和 50，以及

**实验结果与讨论**

本节使用 IGD 和 HV 指标全面分析了所提出的 ABP-HDD 和对比算法的性能。以下数据表中，统计结果以 30 次独立运行所得到的均值和标准差呈现。为了直观展示统计比较，Wilcoxon 秩和检验的结果总结在表中。具体而言，符号"-"表示 ABP-HDD 显著优于

**结论**

在本工作中，我们从三个方面讨论了求解 MOPs 的方向。其中，求解 MOPs 的主要思想基于支配和分解的思想。在本文中，从基于支配的角度求解 MOP。在 ABP-HDD 中，基于超支配度，提出了一种自适应双种群划分策略，采用多层次支配评估将种群分为精英导向子种群和潜在

**CRediT 作者贡献声明**

Baihao Qiao（乔百豪）：可视化、监督、方法论、资金获取。
Ziru Feng（冯子如）：写作 – 初稿、软件、方法论。
Rongrong Bai（白榕榕）：写作 – 初稿、方法论。
Li Yan（严丽）：写作 – 初稿、监督、资金获取。
Boyang Qu（屈伯洋）：写作 – 初稿、可视化、监督。

乔百豪 | 冯子如 | 白榕榕 | 严丽 | 屈伯洋