Page 192 - 《软件学报》2026年第3期

丁炜超 等: 基于信息共享的改进双归档高维多目标进化算法 1155

凹曲面 PF (DTLZ2–4)、退化 PF (DTLZ5–6) 以及断开 PF (DTLZ7), 能够全面评估多目标进化算法的性能. 另外,
其重要特点是目标数量的可扩展性, 通过调整问题的目标数量, 从而同时检测算法在高维和低维目标下的性能表
现. 实验在不同的测试问题上进行, 设置目标数量包括{2, 3, 4, 6, 8, 10, 15, 20}, 总的测试实例数目为 56.
ZDT [38] 测试问题集是经典的 2 目标测试实例, 其不同测试问题的 PF 具有不同的难度特征, 包括基本的曲面
PF (ZDT1–2)、不连续 PF (ZDT3)、混合 PF (ZDT4) 以及复杂的非均匀分布 PF (ZDT6), 这种多样性使得 ZDT 测
试问题集能够很好地检测算法在低维目标上逼近真实 PF 的能力. 实验在 ZDT1–4 以及 ZDT6 问题上进行了测试,
总测试实例数目为 5.
多目标背包问题 (MOKP) [39] 和多线段距离最小化问题 (MLDMP) [40] 是两种常见的组合优化问题. MOKP 是一
种涉及多个背包的优化问题, 目标是同时最大化多个存在冲突的目标函数 (收益、重量等), 在给定的容量约束下,
选择物品的最优组合. MLDMP 旨在最小化多个线段之间的距离, 通常应用于空间布局和路径规划等领域. 该问题
的特性在于寻找多个解的过程中需要平衡不同线段之间的距离最小化. 这两类问题具有多样性和挑战性, 有助于
测试算法在不同情况下的表现. 实验设置目标数量为{4, 6, 8, 10}, 总的测试实例数量为 8.
(2) 对比算法
为测试 Two-Arch/IS 算法的有效性, 本文选取了 14 种有代表性的多目标进化算法作为对比算法以检验 Two-
Arch/IS 性能, 具体包括经典的 Two-Arch [17] 算法, 代表性的 Two-Arch 改进算法 Two_Arch2 [26] 、C-TAEA [41] 、
TriMOEATAR [33] 、TwoArchM [28] 和 TwoArchA [29] , 优异的高维多目标进化算法 NSGA-III [42] 、IBEA [43] 、KnEA [15] 、
[44] [45] [46] [47] [13]
MOEA/D 、SMS-EMOA 、HEA 、TSNSGA-II , 以及面向低维问题的基于网格的进化算法 GREA . 选择
上述算法的原因主要有以下几方面.
1) Two-Arch 是一个经典的算法框架, 在进化过程中将解集分为两个档案库以分别维护种群收敛性和多样性,
缓解高维下收敛性和多样性之间的冲突, 未引入额外参数. Two-Arch/IS 在此基础上优化改进, 对比 Two-Arch 以
检验 Two-Arch/IS 性能的提升.
2) Two_Arch2 是典型的 Two-Arch 变体算法, 为档案库设计了不同的选择原则, 并集成多种优势关系, 缓解了
算法难以收敛的问题, 而 Two-Arch/IS 在档案库维护和更新上重新设计, 两种算法改进思想较为类似.
3) C-TAEA 在 Two-Arch 算法基础上引入了协同进化的概念, 在环境选择过程中利用存档间的交互协作, 进
一步促进存档收敛性和多样性, 亦未引入额外参数, 算法中部分思想与 Two-Arch/IS 中的信息补偿机制较为相似.

4) TriMOEATAR 能够处理具有多个冲突目标的优化问题, 在 Two-Arch 框架中融入了一组参考向量集用于
增强种群多样性, 该思想与 Two-Arch/IS 中的子种群互映更新策略有一定相似度.
5) TwoArchM 分离优化收敛性与多样性, 基于多搜索策略平衡局部开发和全局搜索能力, 促进种群收敛; 设计
了新的基于范数的多样性保持机制维持种群多样性, 未引入额外参数.
6) TwoArchA 在 Two-Arch 方法中引入了聚合框架, 并为 CA 和 DA 重新设计了环境选择策略, 强化其在收敛
性和多样性方面的作用.
7) NSGA-III 是高维多目标进化算法领域的经典算法, 核心在于使用一组参考集 (可以根据目标空间自动生
成) 引导种群向 PF 进化, 并在环境选择中采取了高效的非支配排序方法, 未引入额外参数.
8) IBEA 是一种代表性的基于指标的高维多目标进化算法, 基于二元指标定义优化目标, 并在环境选择过程
中以该指标进行度量, 具备较强的可扩展性, 并且不需要引入额外的多样性保持机制.
9) KnEA 是一种基于帕累托关系改进的多目标进化算法, 主要思想是通过挖掘邻域内的 knee points, 在保证
多样性的同时强调种群的收敛性.
10) MOEA/D 是一种基于分解的多目标进化算法, 能够将多目标问题分解为一组单目标子问题, 通过优化子
问题的解逼近整个 PF, 具有较好的性能和灵活性.
11) SMS-EMOA 基于非支配排序评判个体等级, 利用 HV 指标作为选择标准丢弃对多样性贡献较差的个体,
以此指导进化过程, 重点关注解的分布和收敛性, 未引入额外参数.