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

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

进一步研究与探索.
(2) 基于分解的 MOEA. 基于分解的方法通过聚合函数将多目标优化问题分解为多个单目标子问题, 使用进化
算法以协作的方式对子问题进行优化, 最终得到一组近似的最优解集合, 近年来提出的代表性算法有 MOEA/D-
ROD [22] 、IM-MOEA/D [23] . 这类方法有效避免了算法的选择压力在高维下失效的难题, 并且子问题数量不会呈指
数级增长, 但算法的性能在极大程度上依赖于权重向量在解空间中的分布情况. 对于具有不规则 PF 的问题, 生成
有效划分 PF 的权重向量集是一个巨大的挑战. 此外, PF 的形状复杂多变, 传统的权重向量生成方法难以适用所有
的情况, 因此主要的研究难点在于设计能够适应多种 PF 形态的权重向量集生成方法.
(3) 基于指标的 MOEA. 该类方法通过定义一系列指标衡量解集优劣, 基于指标推进演化过程, 有效应对高维
空间中的搜索难题, 实现有效且均衡的搜索. 经典的评价指标包括超体积 (hypervolume, HV)、逆世代距离
(inverted generational distance, IGD) 等, 因其良好的理论支撑被广泛应用于多种算法中 [24,25] . 然而, 这些指标的计算
复杂度通常较高, 在处理高维或大规模问题时, 算法耗时很长. 其次, 基于指标推进种群演化, 这意味着算法性能过
度依赖于指标的设计. 尽管存在一些指标能够同时兼顾收敛性与多样性, 但在不同问题中的表现可能存在差异, 无
法在所有场景下均有效. 此外, 为特定问题选取合适的指标也是一大难题.
针对 MaOP, Two-Arch 算法因其计算复杂度低、收敛性与多样性独立优化的优势, 为该问题提供了新的求解
思路. 然而, Two-Arch 框架本质上属于基于帕累托支配关系的 MOEA, 在求解 MaOP 时, 常面临帕累托优势关系
失效的困境, 因此造成算法选择压力不足. 为应对这一问题, 本文提出了一种改进的双归档进化算法, 旨在通过多
种策略缓解该难题, 提高算法在高维优化问题中的综合性能.
1.2 Two-Arch 算法
Two-Arch 算法是一种低复杂度的多目标进化算法, 算法将非支配解集划分为两个档案库: 收敛性档案 CA 和
多样性档案 DA, 分别促进算法的两个目标——收敛性和多样性.
算法流程图如后文图 1 所示, 基本框架类似于一般的 MOEA, 即种群的复制和迭代. 在繁殖过程, CA 和 DA
的并集将作为 MOEA 框架中的父种群, 而 Two-Arch 并未设置特殊的父种群选择机制. 在通过交叉和突变操作获
得新一代个体后, Two-Arch 根据非支配解集对 CA 和 DA 进行更新, 由于 CA 和 DA 的目标不同, Two-Arch 为其
制定了不同的选择原则. 针对获得的非支配解集, 支配 CA 或 DA 中任意个体的解将被加入 CA (具备支配地位的
后代), 而未能支配两者的解则加入 DA (无支配地位的后代). 在种群迭代过程中, CA 和 DA 中的任何支配个体都
将被移除. 在 Two-Arch 中, CA 和 DA 被视为整体解集, 总规模固定 (假设为 N), 但各自大小灵活调整. Two-Arch
根据 DA 中个体与 CA 的距离来移除 DA 中额外个体, 而 CA 中个体保持不变. 由于 CA 的大小不会超过上限 N,
当 CA 达到最大规模时, DA 将被清空, 此时加入 CA 的解均具备支配地位, 并至少替代一个被支配的 CA 个体.
Two-Arch 算法作为首个实现收敛性与多样性独立优化的算法, 在未增加额外算法复杂度的前提下, 展现出了
其独特的优势. 实验数据充分证明, Two-Arch 算法取得了较为显著的研究成果. 然而, 随着目标维数的增加, Two-
Arch 算法的优异性能逐渐下降, 这主要归因于两点: (1) 鉴于 Two-Arch 算法本质上是一种基于帕累托的多目标进
化算法, 传统的帕累托占优是一种严格的支配关系, 因此在求解具有大量目标的多目标问题时, 种群中非支配解的
比例急剧增加导致种群选择压力不足, 难以收敛至 PF, 算法的优化效果受到影响; (2) 档案更新机制尚存不足. 尽
管 CA 的作用是促进收敛, 但由于缺乏对 CA 多样性的维护, 可能导致算法被迫停滞. 当 CA 中的所有解都在 PF
上并且 CA 的大小已经达到最大 (上限 N) 时, DA 将被丢弃. 此时如果新的非支配解不能支配档案库中的个体, 本
应将其添加到 DA, 但此时 CA 和 DA 的总大小已经达到上限, 并且无法删除 CA 中的任何解, 因此算法将被迫停
滞, 不再更新 CA 和 DA, 算法最终得到的结果是多样性严重缺失的 CA.
1.3 Two-Arch 变体算法
鉴于 Two-Arch 算法在解决多目标优化问题时所表现出的潜力, 近年来, 研究人员从档案更新机制、种群搜
索策略等角度对其进行了优化改进, 并将其应用到不同类型的多目标优化问题中, 包括: 高维多目标优化问题、约
束多目标优化问题 (constrained multi-objective optimization problem, CMOP) 和多模态多目标优化问题 (multi-