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

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

S i 中. 这种划分方式仅需一次遍历种群即可完成, 虽然时间复杂度相对较低, 但在种群进化过程中我
对应子种群
们发现子种群大小存在较大差异, 甚至部分子种群为空, 这种非均衡状态极有可能导致算法过早地陷入局部最优
解, 进而削弱种群的多样性.

{ }

S i = x ∈ Pi = argmin
F(x)−w j
(3)
j 2
图 3 以二维目标空间为例, 直观地展示了两种种群划分方法得到的不同结果. 其中, 图 3(a) 是本文采取的划分
方法, 在首次遍历权重向量集后, 个体{b, c, e}被分配至相应的子种群中, 完成第 2 次遍历后, 子种群划分结束, 得
到的是 3 个大小均为 2 的均衡子种群. 而图 3(b) 则展示了另一种划分方法, 该方法只需一次遍历种群, 但得到的
结果是 3 个大小分别为 3、0 和 3 的子种群, 其中第 2 个子种群为空, 这种不均衡的划分在后续的档案库更新过程
中严重阻碍了种群多样性的维持.

f 1 f 1
w 1 w 1
a a
w 2
w 2
b b
c c
d w 3 d w 3
e e
f f
f 2 f 2
(a) 遍历权重向量集的方法 (b) 遍历种群个体的方法
图 3 种群划分示意图 (以 2 目标为例)

在子种群划分完成后, Two-Arch/IS 利用 R i 更新 CA i 和 DA i , 更新规则主要参照 Two-Arch 算法的更新方式.
具体地, 首先移除 R i 中被 CA i 和 DA i 支配的个体, 其次将非支配解集 R i 中的个体与 CA i 和 DA i 中的个体进行比较,
如果存在个体可以支配 CA i 或 DA i 中的个体, 则将其加入 CA i , 并移除 CA i 中被支配的个体, 否则将其加入 DA i .
当所有子种群更新完成后, 算法合并 CA i 作为新的 CA, 合并 DA i 作为新的 DA. 算法 3 展示了 Two-Arch/IS 基于空
间划分的子种群互映更新策略实现档案库维护的过程.
2.4 基于角度选择与转移密度估计的截断策略
在档案库更新完成后, Two-Arch/IS 采用基于角度选择与转移密度估计的方法移除档案库中超过种群数量限
制的冗余解. 在档案库维护过程中, Two-Arch/IS 为 CA 和 DA 设置了独立的阈值 N, 避免 Two-Arch 可能导致的多
样性丧失问题. 该策略通过识别目标空间中夹角最小的一组个体, 即搜索方向最为相似的个体, 并剔除其一, 从而
最大限度地保留了种群个体的多样性. 文献 [12] 中提出的 SDE (shift-based density estimation) 策略能够兼顾收敛
性和多样性, 有效评估个体的综合性能, 因此截断过程中采取 SDE 作为核心评估指标, 确保种群在保持收敛性的
同时, 尽可能维持多样性. 该策略能够有效维护种群收敛性和多样性的平衡, 同时有效降低了在高维问题下的计算
成本.
min
min
min
假设档案库中的理想点 (ideal point) 为 Z min = (z ,z ,...,z ), 极点 (nadir point) 为 Z max = (z max ,z max ,...,z max ).
1 2 M 1 2 M
为便于进行后续的分析和操作, 首先将个体转移至归一化之后的目标空间, 档案库中的个体 X i 的目标向量可以表示为:

′
′
′
′
F (X i ) = ( f (X i ), f (X i ),..., f (X i )) (4)
1 2 M
f m (X i )−z min
′
f (X i ) = m , m = 1,2,..., M (5)
m max min
z m −z m
′
其中, f (X i ) 表示个体 X i 在第 m 个目标上的值. 随后, 计算档案库中任意两个个体 X i 和 X j 在归一化目标空间中的
m
夹角, 具体计算方式为:

′ ′
F (X i )· F (X j )

θ i,j = arccos

(6)

′

′

F (X i )
·
F (X j )