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

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

在得出档案库中所有个体在归一化目标空间中两两之间的夹角后, 反复执行以下步骤: 在每次迭代中, 首先识
别出夹角 θ 最小的两个个体 X i 和 X j , 随后, 依据文献 [12] 中所述的 SDE 策略及第 k 近邻密度估计器 (the k-th
nearest neighbor density estimator) [36] , 估算这两个个体在归一化目标空间中的转移密度值 SDE(X i ) 和 SDE(X j ). 基于
转移密度估计值, 删除档案库中性能较差的个体. 过程持续进行, 直到档案库的大小不再超过预设上限 N. 具体计
算方式如下.
SDE X i 的密度时, 会根据种群 P X i 的收敛性表现转移位置, 表示如下:
策略在估计个体 中其他个体相对于
′
′
SDE(X i ,P) = D(dist(X i , p ),dist(X i , p ),...,dist(X i , p ′ )) (7)
1 2 N−1

 f m (X i ), ∃ f m (X i ) < f m (p )
′
 j
′  , m = 1,2,..., M (8)
j  ′
f m (p ) = 
 f m (p ), otherwise
j
′
′
其中, N 表示 P 的大小, p 表示转移之后的个体 ( p i , X i ), 转移方式按照公式 (8) 定义, dist(X i , p ) 表
p i p i ∈ P 并且
i i
′
示个体 X i 和 p 间的相似程度, 此处使用欧几里得距离作为衡量标准. 函数 D 计算目标个体与种群中其他个体的
i
相似度, 通过引入的 k 近邻密度估计器实现, 具体表示为:

1
D(X) = (9)
φ (X)+2
K
√
K
其中, φ (X) 是个体 X i 与其他个体转移目标向量距离的集合 X 中的第 K 小值, 通常 K = |N|.
为了更明确地展示档案库截断的计算过程, 精准描述具体操作, 我们在算法 4 中详细阐述了其计算步骤.
算法 4. 档案库截断 Delete_Redundant_Individuals.
输入: 收敛性档案 CA, 多样性档案 DA, 种群大小 N;
输出: 收敛性档案 CA, 多样性档案 DA.
1. 在归一化空间中计算 CA 中任意两个个体间夹角;
2. while |CA| > N do
3. 找到 CA 中拥有最小夹角 θ i,j 的个体 x i 和x j ; //公式 (6)
4. 计算 SDE(x i ) 和 SDE(x j ); //公式 (7)
5. 删除 SDE 值更大的个体;
6. end while
7. 在归一化空间中计算 DA 中任意两个个体间夹角;
8. while |DA| > N do
9. 找到 DA 中拥有最小夹角 θ i,j 的个体 x i 和x j ; //公式 (6)
10. 计算 SDE(x i ) 和 SDE(x j ); //公式 (7)
11. 删除 SDE 值更大的个体;
12. end while
13. return CA, DA
为了展示 Two-Arch/IS 截断过程的有效性, 以二维目标空间为例, 图 4 对比了 Two-Arch/IS 和 SPEA-II+SDE [12]
的个体选择过程. 图 4(a) 中, Two-Arch/IS 首先筛选出夹角最小的两个个体 b、c, 接着利用公式 (7)–公式 (9) 计算
个体 b 和 c 的转移密度估计值, 剔除拥有更大 SDE 值的个体 c, 从而保留个体{a, b, d, e}进入下一次迭代. 图 4(b)
中, SPEA-II+SDE 则根据每个个体的转移密度估计值进行筛选, 此时个体 d 相较于其他个体在收敛性上并无明显
优势, 因此 SPEA-II+SDE 为其分配较高的密度值进而剔除, 选择个体{a, b, c, e}进入下一次迭代.
值得强调的是, 个体 a、e 在维护种群多样性方面发挥着关键作用, 因为它们位于相对稀疏的区域, 为种群提
供了更广泛的搜索空间. 相比之下, 个体 b、c 的搜索方向极为相似, 如果从中剔除其一, 则能够最大化种群的搜索
潜力. 因此结合角度选择与转移密度估计的方法能够引导种群从多个不同方向逼近 PF, 有效维护了种群多样性.