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

1154 软件学报 2026 年第 37 卷第 3 期

15. end if
16. end if
17. return CA, DA
表 1 展示了 2 目标问题上档案库间个体迁移情况的示例. 针对档案库中的最小边界解, 在目标 1 上 f 1 (x 1 ) < f 1 (x 2 ),
这意味着 x 1 在目标 1 上具有更优的表现, 因此将其移动到 DA, 以其在收敛性方面的优势引导 DA 进化. 而在目
标 2 上 f 2 (x 3 ) > f 2 (x 4 ), 因此不做任何处理. 针对最大边界解, 在目标 1 上 f 1 (y 1 ) > f 1 (y 2 ), 不做任何处理. 在目标 2 上
y 4 移动到 CA, 利用具有更大边界值的个体引导 CA 进化. 通过一系列的个体迁移操作, 旨在
f 2 (y 3 ) < f 2 (y 4 ), 因此将
优化档案库间的信息交流, 确保 CA 和 DA 分别发挥其优势的同时, 能够互相引导进化.

表 1 2 目标问题上的 Two-Arch/IS 中个体迁移情况示例

最小边界解 最大边界解
处理内容
目标1 目标2 目标1 目标2
收敛性档案 min ( min ( max ( max (
f 2 x 3 ) = 0.13
f 2 y 3 ) = 0.87
f 1 y 1 ) = 0.90
f 1 x 1 ) = 0.10
多样性档案 min ( min ( max ( max (
f 1 x 2 ) = 0.12
f 2 x 4 ) = 0.11
f 2 y 4 ) = 0.92
f 1 y 2 ) = 0.89
操作 将 x 1 移动到DA 不做处理 不做处理 将 y 4 移动到CA

2.6 复杂度分析
在 Two-Arch/IS 中, 算法的复杂度主要来自档案库的更新、截断操作以及档案库间的信息补偿. 对于具有 M
个目标的多目标优化问题, 算法设置种群规模为 N, 子种群的大小为 N S . 档案库更新过程中, 首先需要获取子代中
2
2
O(MN ), 随后划分档案库和非支配解集需要的时间复杂度为 O(MN ), 在子种群
非支配解, 需要的时间复杂度为
内部局部更新档案库的时间复杂度参考 Two-Arch 2 N S < N, 因此档案库
O(MN ). 由于在任何条件下满足
算法, 为
S
2
更新过程的时间复杂度可表示为 O(MN ). 截断过程首先计算种群中两两个体间夹角并找到夹角最小的两个个体,
2
需要的复杂度为 O(MN ), 随后通过转移密度估计值删除两个个体中综合性能较差的个体, 计算两个个体的转移
O(MN ) 可忽略. 由于截断过程需要不断执行上述操作, 直至档案库大小满足条件, 因此截断过
2
密度估计值相比于
3 O(MN) 的
程需要的时间复杂度可估计为 O(MN ). 为进行档案库间的信息补偿, 获取各个目标上的边界解需消耗
时间复杂度, 随后进行边界解目标值的比较以及个体交换, 其复杂度可忽略. 综上分析, Two-Arch/IS 算法的复杂度
3
主要来自档案库的截断过程, 表示为 O(MN ).
3 实验结果与分析
在本节, 我们首先验证了 Two-Arch/IS 在高维问题上的卓越性能, 通过对比几种流行的 Two-Arch 变体算法以
及现有高维多目标进化算法, 全面深入地评估其在 MaOP 上的表现. 紧接着, 在低维问题上进一步证明了 Two-
Arch/IS 的有效性. 随后, 为验证 Two-Arch/IS 各部分的有效性, 本文针对 Two-Arch/IS 提出的几种策略进行消融实
验. 在此基础上, 通过对比几种高维多目标进化算法, 验证 Two-Arch/IS 的收敛速度优势; 最后, 对比多种不同类型
的算法衡量 Two-Arch/IS 的计算复杂度. 实验在具有 3.10 GHz Intel(R) Core(TM) i5-11300H 处理器和 Windows 10
64 bit 操作系统的设备上进行.
3.1 实验设置

(1) 测试问题
实验中采用了多样化的测试问题, 具体包括多目标优化的基准测试问题集 DTLZ 和 ZDT, 以及面向组合优化
的多目标背包问题 (multi-objective knapsack problem, MOKP) 和多线段距离最小化问题 (multi-line distance minimi-
zation problem, MLDMP).
[37]
DTLZ 测试问题集是 MaOP 领域经典的测试实例, 包含了具有不同 PF 的多种测试问题, 包括平面 PF (DTLZ1)、