基于外部存档更新及截断的 NSGA-Ⅱ改进算法

摘要：传统的 NSGA-Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ） 算法使用拥挤度作为 精英选择的第二指标，该方法在处理高维多目标优化问题时，常常由于选择压力不足，以及不 同目标间优化冲突加剧等原因，很难维持种群收敛性和多样性的平衡。针对上述问题，提出一 种基于外部存档更新及截断机制的 NSGA-Ⅱ改进算法 NSGA-Ⅱ-UTEA（NSGA-Ⅱ algorithm based on Update and Truncation of External Archive）。该算法首先在精英选择中引入基于权重 向量分解的外部存档机制，然后根据个体与所在权重向量及超平面距离之和更新外部存档，并 基于个体间角度计算实现外部存档截断，进一步提升了算法在高维多目标优化问题中种群的收 敛性和多样性。与 NSGA-Ⅱ、NSGA-Ⅲ、MOEA/D（Multi-Objective Evolutionary Algorithm based" on" Decomposition）、 NSGA-Ⅱ-ARSBX（NSGA-Ⅱ with" Adaptive" Rotation" based Simulated" Binary" crossover） 和 RPD-NSGA-Ⅱ（Reference" Point" Dominance-based" NSGA- Ⅱ） 这 5 种先进的进化算法的对比实验结果表明，NSGA-Ⅱ-UTEA 算法在 10 目标以上的高维 DTLZ（Deb Thiele Laumanns Zitzler） 和 WFG（Walking Fish Group） 系列测试函数上，各项性能 指标整体优于其他算法，在解集的分布性和多样性方面具有显著优势。特别是在大部分高维 WFG4～WFG7 凹问题上都能取得最佳的性能指标值。与传统的 NSGA-Ⅱ算法相比，NSGA-Ⅱ- UTEA 算法在 10 目标以上的高维 DTLZ 系列测试函数上，反世代距离（IGD）性能平均提升了 50.6%；在 15 目标以上的高维 WFG 系列测试函数上，超体积（HV）性能平均提升了 60.7%。实 验结果验证了 NSGA-Ⅱ-UTEA 算法改进的有效性。

关键词：多目标优化；精英选择；NSGA-Ⅱ；权重向量；外部存档

中图分类号：TP301.6

文献标志码：A

随着云计算、大数据和人工智能等技术的迅猛发 展，高维多目标优化问题 （Many-objective Optimization Problems， MaOPs） 开始普遍出现于科学研究和工程 应用领域，例如无人机路径规划[1]、云资源调度优 化[2]、混合动力汽车控制[3] 等。因此，研究和设计针 对 MaOPs 的高效优化算法具有重要的理论价值和现 实意义。

传 统 的 多 目 标 进 化 算 法 ， 如 NSGA-Ⅱ[4]、 MOEA/D[5] 和 IBEA（Indicator-Based" multi-objective Evolutionary Algorithm）[6] 等，在求解低维多目标优化 问题时通常能够表现出很好的性能，但在处理高维 多目标优化问题时，一方面，由于目标空间维数增 大，种群中大部分的个体是非支配的，导致选择压力 不足；另一方面，目标空间维数的增大加剧了目标间 的优化冲突，无法兼顾种群的收敛性和多样性，算法 的优化效果显著下降。

为了增强算法目标变量维数的可扩展性，国内 外学者通常从以下两个角度进行相关改进。第 1 个角度是修改传统的 Pareto 优势关系定义，以增加向帕 累托前沿的选择压力。Wu 等 [7] 提出的一种基于 ε- domination 的 ε-Two_Arch2 算 法 ， 分 配 ε-domination 更新多样性归档中的个体以增加算法的选择压力。

Gu 等 [8] 提出了一种新的基于参考点的增强优势关 系的 RPS-NSGA-Ⅱ（Reference point-based Strengthened NSGA-Ⅱ）算法，通过参考点集和收敛度量 Cov 来区 分 Pareto 解集，并进一步对其进行分层。第 2 个角度 是引入新的多样性选择指标，使用新的机制来促进 种群的多样性。Wang 等 [9] 提出了一种基于解决方 案和参考方向之间基于惩罚的自适应矩形区域 （APA） 的新型聚类指标，以协助非支配级别排序来解 决传统基于支配的多目标进化算法在高维多目标中 失效的问题。然而，上述两种方法都存在一些问 题。其中，过度修改传统的 Pareto 优势关系定义，可 能会导致算法复杂度升高和计算性能下降，最终导 致 Pareto 前沿不包括真正的优秀解。引入新的多样 性选择指标，需要经过特定的设计才能更好地反映 问题的本质，这就需要更多的计算和存储资源，算法 的效率降低。

外部存档技术是一种能够在不增加算法框架本 身计算复杂度的前提下，实现非支配解的维护，增强 可行解之间的选择压力，缓解种群收敛性和多样性 冲突的有效手段[10]。通过设置外部档案保存进化过 程中所搜索到的所有非支配解，以避免因为随机因素 而引起的优质解丢失[11]。本文以 NSGA-Ⅱ算法框架 为主体，结合 MOEA/D 分解思想的优势，在精英选择 策略中引入基于权重向量分解的外部存档机制，提 出了一种基于外部存档更新及截断的 NSGA-Ⅱ改进 算 法 NSGA-Ⅱ-UTEA（NSGA-Ⅱ algorithm" based" on Update and Truncation of External Archive）。该算法首 先引入权重向量，加速种群的收敛速度；然后根据个 体与权重向量和超平面距离制定外部存档更新策 略，并基于个体间角度计算实现外部存档截断机制， 得到符合条件的外部存档，并保留下来，直接参与下 一代种群的精英选择，从而提高了种群的多样性和 分布性。

1""" NSGA-Ⅱ算法和外部存档

经典 NSGA-Ⅱ算法的主要缺陷是在高维多目标 优化问题中，种群的非支配个体占比很高，甚至可能 达到 100%，这将导致基于支配的选择压力不足，种 群收敛速度降低。针对 NSGA-Ⅱ算法存在的以上问 题，研究人员一般从以下两个角度进行优化。

第 1 类技术的主要思想是修改传统的 Pareto 优 势关系定义，以增加向帕累托前沿的选择压力。这 种类型的思想已被广泛用于解决 MaOPs。如具有代 表性的支配关系 ϵ-dominance[12-13] 划分整个目标空间 为一个个网格，并将解分布在不同的网格中。除此 之外，还有很多其他可选的偏好关系在处理高维多 目标优化问题中也非常有前景，如 θ-dominance[14]、 Angle-dominance[15]、L-optimality[16]、fuzzy-dominance[17] 和偏好顺序排序[18]。与使用传统 Pareto 优势关系的 多目标进化算法相比，尽管这些策略很可能收敛到 Pareto 前沿的一个子区域，但是它们已经被证明能够 显著地提高多目标进化算法求解 MaOPs 的性能。

第 2 类技术的主要思想是引入新的多样性选择 指标，使用新的机制来促进种群的多样性。基于支 配的选择机制在高维目标空间中提供的选择压力不 足以区分不同的解，这将导致搜索偏离 Pareto 前沿 面。为了避免上述现象的发生，在高维多目标优化 问题中保持种群的多样性所采取的选择策略显得尤 为重要。Adra 等[19] 提出了两种管理多样性的机制且 研究了它们在高维多目标优化中对算法总体收敛性 的影响。Deb 等[20] 提出的 NSGA-Ⅲ算法，使用参考 点代替拥挤度来选择个体。Li 等[21] 对基于 Pareto 优 势的多目标进化算法的多样性标准进行了一般性修 改，即基于移位的密度估计 （SDE） 策略，涵盖了个体 的分布和收敛信息。Köppen 等[22]提出了一些替代距 离，这些替代距离基于一个解决方案几乎被任何其 他解决方案支配的程度。在文献 [23] 中，一个二进 制 "ϵ 将基于指标的偏好与优势相结合 ，以加 快 NSGA-Ⅱ算法在求解 MaOPs 时的收敛速度。Yang 等[24] 还定义了一个基于网格优势的度量标准，并在 此基础上提出了一个用于 MaOPs 的有效 MOEA，称 为 GrEA。此外还有拐点驱动的进化算法 （KnEA）[25] 等，这些算法将传统优势与额外的收敛相关度量结 合起来，提高了种群的多样性。

外部存档的目的主要是保留父代中的优良遗传 特性。为了避免搜索过程中优秀个体的流失，近年 来许多学者针对在进化算法中使用外部存档机制进 行了相关的研究，提升了种群的收敛性。Michalak[26] 引进一个外部种群存储每一代的非支配解，并将其 部分或者全部重新引入到主种群中，丰富了种群多 样性。张涛等[27] 提出了一种新的能量差计算方式， 使用外部存档技术提升了模拟退火算法的性能。刘 鑫平等[28] 设定了一个外部归档集，在每次迭代时对 子代种群执行归档操作并淘汰适应度较差的个体， 使归档集保持较好的分布性。王李进等[29] 将外部存档机制应用到布谷鸟搜索算法中，极大地提高了算 法的收敛速度。此外 ，还有引入了外部存档 的 PAES[30] （Pareto 文档进化策略）、带有可选择外部存 档的自适应差分进化算法 JADE[31] 等。

2""" NSGA-Ⅱ-UTEA 算法

NSGA-Ⅱ-UTEA 算法是在 NSGA-Ⅱ算法基础上 引入基于权重向量分解的外部存档机制。首先将种 群空间分解为均匀的权重向量，为每个子问题分配 权重向量；然后根据个体与权重向量和超平面距离 制定外部存档更新策略，并基于个体间角度计算实 现外部存档截断机制，得到符合条件的外部存档，并 保留下来，直接参与下一代种群的精英选择，提高了 种群的多样性和分布性。

综上，NSGA-Ⅱ-UTEA 算法的总体流程如图 1 所示。首先 ，初始化种群 P（t） 和外部存档 EA，对 P（t） 进行交叉、变异生成第 1 代子种群 Q（t），将父代 种群 P（t） 与子代种群 Q（t） 合并，形成新种群 R（t），并 对其进行非支配排序，产生一系列非支配集 F（t）。然 后，不断将等级小的非支配集加入到新的父代种群 P（t） 中，一直加到第 k 层非支配集 F（k），种群的大小 超出 N。接着，使用非支配集 F（k） 更新外部存档，如 果此时外部存档的大小加上前 k−1 层非支配集正好 为种群大小 N，则将外部存档与前 k−1 层非支配集合 并，生成新的父代种群 P（t），否则使用前 k−1 层非支 配集 F（1）～F（k−1） 进行外部存档截断操作，直到外部 存档大小加上前 k−1 层非支配集等于种群大小 N，此 时算法运行结束。

表 1 所示是 NSGA-Ⅱ-UTEA 算法的伪代码。在 算法 1 中，外部存档更新的流程如表 2 的算法 2 所 示。首先进行权重向量的划分，然后根据个体的支 配关系决定是否加入外部存档，最后根据个体到权 重向量距离和到超平面距离之和的大小，删除多余的个体。外部存档截断机制的流程如表 3 的算法 3 所示，首先判断第 1 层非支配集的个体数是否超过 种群数量，然后判断外部存档的大小是否符合要求， 最后根据个体间的角度，删除外部存档中的多余个体。

本文提出的 NSGA-Ⅱ-UTEA 算法在精英选择 环节中引入了一种基于权重向量分解的外部存档机 制。首先外部存档记录优秀的解，可以防止这些解 在进化过程中被淘汰，从而保证了种群进化的收敛 性。其次，在精英选择中，同时考虑个体的适应度函 数值和它与所在权重向量及超平面的距离之和。这 种方法能够更好地估计个体的品质，并使得个体与 外部存档中的解进行更精确的比较，从而更好地维 护外部存档中的多样性，进而避免算法早熟并提高 算法的搜索能力。此外，NSGA-Ⅱ-UTEA算法还引入 了外部存档截断机制，通过计算不同解之间的角度 来保持外部存档中的多样性。这种机制使得算法能 够在不降低搜索能力的情况下，控制外部存档的大 小 ， 从 而 更 高 效 地 处 理 高 维 多 目 标 优 化 问 题 。

2.1 外部存档更新策略

外部存档的目的主要是保留父代中的优良遗传 特性。为了避免搜索过程中优秀非支配解的流失， 将其保存到外部存档中，作为父代参与到下一代的 进化过程中。因此，外部存档在算法的进化过程中 需要不断进行迭代更新。

本文提出的外部存档更新策略基本流程：首先， 保留上一次进化得到的外部存档 EA，然后将非支配 集 F（k） 中的个体 Xi 归到权重向量 λj 上。如果 Xi 不 能被属 于 λj 的其他个体所支配 ，则 将 Xi 加 入 到 EA 中。如果 Xi 与 EA 中属于 λj 的其他个体互不支 配，则删除相比 Xi 到 λj 距离和 Xi 到超平面距离之和 大的第 1 个个体，否则删除被 Xi 支配的其他个体。 直到最后 EA 的大小满足条件，此时算法运行结束。

本文提出的个体与权重向量的距离代表解集中 的个体之间的差异程度，体现了解集的分布性和个 体的多样性。为了评价个体与参考点的接近程度， Zhang 等 [31] 提出了一个拐点（knee point）概念。拐点 是指在多目标问题中，所有目标函数的值均可以被 优化的非支配解集合中最接近参考点 （ reference point）的解。Zou 等 [32] 提出了一种使用加权子种群 拐点的多目标优化算法。该算法的核心是通过种群 的拐点来引导种群的搜索方向，计算解和超平面之 间的距离，距离最短的点被认为是拐点，每一个拐点 代表了其子种群的最优解，用于引导群体向 PF 方向 的搜索。本文中个体到超平面的距离代表了个体与 拐点的近似程度，偏向非支配解中的拐点被证明是 偏向大超体积的近似，从而增强了多目标优化中的 收敛性能。此外，由于至多一个解将被识别为非支 配前沿中每个解的邻域内的拐点，因此在所提出的 算法中不需要引入额外的多样性维护机制，与用于 多目标优化的许多现有多目标进化算法相比，显著 降低了计算复杂度。

2.2 外部存档截断机制

外部存档的更新策略将会导致优秀的非支配解 不断加入外部存档，最终导致外部存档个体数越来 越多。但是每一代所需要的外部存档个体数是由种 群大小和前 k−1 层非支配集所共同决定的。因此，对于超出所需数量的外部存档，必须采取相应的截断 机制 ，以保证种群数量在进化过程中保持不变。

本文提出的外部存档截断机制基本流程为：首 先，保留上一次进化得到的外部存档 EA，然后根据 第一层非支配集 F（1） 的个体数是否大于 N 分成两种 情况。第 1 种情况：若 F（1） 的个体数大于 N，则在 EA 的个体间进行角度计算，循环删除角度最小的个 体，直到 EA 的大小等于 N，算法运行结束；第 2 种情 况：若 F（1） 的个体数小于 N，则判断前 k−1 层非支配 集和 EA 的个体数之和是否等于 N，如果不等于则将 EA 的个体与前 k−1 层的个体进行角度计算，循环删 除角度最小的个体，直到等于 N，算法运行结束。

从时间复杂度上来看，表 1 中 NSGA-Ⅱ-UTEA 算法执行步骤 4、5 需要的时间复杂度最大，同时 NSGA-Ⅱ-UTEA 算法没有在原算法的基础上增加额 外的时间复杂度，因此时间复杂度和原算法保持一 致，为 O（MN2 ），其中 M 表示目标维数。从空间复杂 度上来看，NSGA-Ⅱ-UTEA算法中尽管增加了外部存 档，但是并没有增加空间复杂度，执行步骤最大的空 间复杂度仍为 O（N）。

3""" 实验与结果分析

3.1 测试函数

为了便于与以往文献中的实验结果进行对比分 析，本文设置了相同的种群规模、实验重复次数和函 数评估次数等条件，并选择了 DTLZ[33] 和 WFG[34] 系列 函数作为测试问题。DTLZ1～DTLZ4 和 WFG4～WFG7 测试函数的属性如表 4 所示。

3.3 实验结果与分析

多 目 标 优 化 算 法 性 能 评 估 标 准 主 要 包 括 Pareto 最优解集的空间分布性和收敛性。Pareto 最优 解集空间分布性用以衡量 Pareto 最优解的质量，收敛 性用以测试算法寻优能力。本文采用带精英策略的非支配排序的遗传算法 NSGA-Ⅱ、基于参考点的非 支配遗传算法 NSGA-Ⅲ、基于分解的多目标进化算 法 MOEA/D、基于旋转的模拟二元交叉的 NSGA-Ⅱ- ARSBX 算法 、基于分解支配关系 的 RPD-NSGA- Ⅱ算法以及本文改进算法 NSGA-Ⅱ-UTEA 对 DTLZ 测试集（ DTLZ1～DTLZ4）与 WFG 测试集（WFG4～ WFG7）进行测试，通过实验验证 NSGA-Ⅱ-UTEA 算 法在 IGD 和 HV 两个性能评估标准方面相比其他算 法具有优势，结果如表 5 和表 6 所示。

所有实验都基于 PlatEMO v3.5 平台；编程语言： Matlab；编程环境：MatlabR2021a；内存：16GB；操作系 统：Windows10。设置初始种群规模为 100，重复计 算 30 次，表中深灰色背景表示最优值，浅灰色背景表 示次优值。为了进行结果比较 ，采用了 Wilcoxon 秩和检验，其显著性水平设置为 0.05，表中的“+”、 “=”和“−”分别表示比较的算法是否显著优于、显著 劣于和没有显著差异于本文提出的 NSGA-Ⅱ-UTEA 算法。

3.3.1"" DTLZ 测试函数实验结果分析 表 5 示出了 6 种算法在 DTLZ 测试函数不同维度上的 IGD 平均 值与标准差。从实验结果可知，在 DTLZ 测试函数 中，NSGA-Ⅱ-UTEA 算法在分布性和多样性方面优 于其他对比算法，只有在少量 DTLZ 测试函数上，略 次 于 MOEAD 算 法 、 NSGA-Ⅲ 算 法 和 RPD-NSGA- Ⅱ算法，但结果相差不大。

从表 5 还可以看出，相比 NSGA-Ⅱ、NSGA-Ⅲ、 MOEA/D、NSGA-Ⅱ-ARSBX 和RPD-NSGA-Ⅱ，NSGA- Ⅱ-UTEA 表现更优的测试实例比例分别为 12/20， 8/20，7/20，12/20，9/20，而 NSGA-Ⅱ-UTEA 表现较差 的比例分别为 6/20，6/20，7/20，7/20，6/20。由比例结 果可以看出，相比于其他算法，NSGA-Ⅱ-UTEA 算法 整体表现最好，能够有效处理 DTLZ1～DTLZ4 测试 函数集。

在 DTLZ1 函数问题上，NSGA-Ⅱ-UTEA 算法只 在 5 维和 15 维目标空间中获得的 IGD 值优于其他 算法，但在 10 维目标空间中仅次于 MOEA/D 算法。 DTLZ1 是一个具有线性 Pareto 最优面的较简单的 M 个目标的测试问题，高维目标空间问题的搜索空 间较大，算法不容易收敛。另外，高维目标空间问题 增加了算法的复杂度，导致算法产生较低的分布性 能。因此，NSGA-Ⅱ-UTEA 算法在 DTLZ1 函数问题 上很难达到最优效果。

此外 ， NSGA-Ⅱ-UTEA 算法在 DTLZ3、 DTLZ4 函数问题上整体优于其他对比算法 ，这是因 为 DTLZ3 测试的是一个 MOEA 收敛到全局 Pareto 最 优的能力，DTLZ4 函数问题侧重于测试 MOEA 算法 的解的分布性，而 NSGA-Ⅱ-UTEA 算法中使用了个 体与权重向量及超平面距离之和来更新外部存档。 个体到超平面的距离代表了个体与拐点的近似程 度，偏向非支配解中的拐点被证明是偏向大超体积 的近似，从而增强了多目标优化中的收敛性能。个 体与权重向量的距离代表解集中个体之间的差异程 度，因此解集的分布性更好。

综上所述，在解决 DTLZ1～DTLZ4 函数问题时， NSGA-Ⅱ-UTEA 算法能够保证种群较好的收敛性和 多样性，特别是在高维目标空间中算法的优势更加 明显。

3.3.2"" WFG 测 试 函 数 实 验 结 果 分 析 ""相 比 于 DTLZ 测试函数 ，WFG 考察的数学特征更多更全 面，比如不可分、欺骗性等。表 6 示出了 6 种算法在 WFG 测试函数不同维度上的 HV 平均值与标准差。 从实验结果可知，在 WFG 测试函数问题上，NSGA- Ⅱ-UTEA 算法在高维多目标空间中的分布性和多样 性优于其他对比算法，在低维多目标空间中略次于 NSGA-Ⅲ算法 和 RPD-NSGA-Ⅱ算法 ，但结果相差 不大。

从 表 6 中 数 据 可 以 看 出 ， 相 比 于 NSGA-Ⅱ 、 NSGA-Ⅲ、MOEA/D、NSGA-Ⅱ-ARSBX 和RPD-NSGA- Ⅱ，NSGA-Ⅱ-UTEA 表现出更优的测试实例比例分 别为 18/32， 15/32， 14/32， 15/32， 11/32，而 NSGA-Ⅱ- UTEA 表现较差的比例分别为 5/32，9/32，7/32，7/32， 8/32。由比例结果可以看出 ，相比于其他算法 ， NSGA-Ⅱ-UTEA算法整体表现最好，能够有效处理 WFG4～WFG7测试函数集。

由表 6 数据可知 ，除了在测试函数 WFG6 的 3 维、8 维、10 维和 15 维上，NSGA-Ⅱ-UTEA 算法表 现不如 NSGA-Ⅱ算法外 ，其他情况均优于 NSGA- Ⅱ算法，说明了本文算法改进的有效性。 NSGA-Ⅱ-UTEA 算 法 在 15～30 维 的 WFG4 和 WFG5 测试函数上的表现优于其他算法，在 3～10 维 的 HV 值略差于 NSGA-Ⅲ算法。这是由于 NSGA- Ⅱ-UTEA 在高维多目标问题中能很好地兼顾局部搜 索和全局搜索的能力，而 WFG4 测试函数存在大量 的局部最优解，主要考察算法在缩放的情况下，算法 的全局搜索能力。WFG5 测试函数具有欺骗的特性， 主要考察算法是否能够避免陷入局部收敛，进行有 效搜索。而 NSGA-Ⅱ-UTEA 在精英选择中引入个体 到所在权重向量及超平面距离之和来更新外部存 档，避免算法早熟并提高算法的搜索能力。

NSGA-Ⅱ-UTEA 算 法 在 20～30 维 的 WFG6 和WFG7 测试函数上获得的 HV 值均大于其他对比算 法，在 3～15 维的 WFG6 和 WFG7 测试函数上表现不 佳。这是因为 WFG6 侧重于决策变量的不可分离， WFG7 侧重于有偏特性，主要考察算法能否处理大量 最优解集中在某一处的问题。NSGA-Ⅲ算法引入参 考点的概念，在搜索过程中能更好地避免局部最优 解。但是随着问题维度的增加，搜索空间的大小呈 指数级增长，NSGA-Ⅲ算法表现不佳，而 NSGA-Ⅱ- UTEA 算法通过外部存档更新策略增强了算法搜索 能力，避免算法陷入局部最优解。

综上所述，NSGA-Ⅱ-UTEA 算法在解决 WFG4～ WFG7 4 个测试函数问题时，在 20～30 的高维目标空 间中均能够获得最优的 HV 值，这也表明了相较于其 他算法，NSGA-Ⅱ-UTEA 算法所获得的解集是在分 布性和多样性方面更加接近真实 PF 的非占优解集。

为 了 进 一 步 直 观 地 反 映 NSGA-Ⅱ-UTEA、 NSGA-Ⅱ、NSGA-Ⅲ、MOEA/D、NSGA-Ⅱ-ARSBX 和 RPD-NSGA-Ⅱ 6 种算法在高维目标空间中得到的最 终解集的分布情况，本文采用平行坐标图来可视化 高维数据。由于本文篇幅的限制，只提供了上述 6 种 算法在 30 维目标 WFG4 上最终解集的平行坐标图， 如图 2 所示。在高维目标空间中的一个点被表示为 一条拐点在 M 条平行于坐标轴的折线，在第 k 个坐 标轴上的位置就表示这个点在第 k 维的目标函数值， 其中 WFG4 问题的第 k 维目标函数值在 [0，2k] 之间。

从图 2 可以看出，NSGA-Ⅱ-UTEA 算法在种群 分布性和多样性方面都获得了很好的效果；NSGA-Ⅱ 和 NSGA-Ⅱ-ARSBX 算法能满足种群多样性的要 求 ， 但 收 敛 性 较 差 ； NSGA-Ⅲ 、 MOEA/D 和 RPD[1]NSGA-Ⅱ算法在高维目标空间中存在目标解丢失的 情况，导致分布性差于 NSGA-Ⅱ-UTEA 算法。综上 所述，NSGA-Ⅱ-UTEA 算法得到的解集分布更加均 匀，提升了种群的分布性和多样性，在解决高维多目 标优化问题时有很大的优势。

4""" 结束语

本文以多目标优化问题为研究对象，提出一种 基于外部存档更新及截断机制的 NSGA-Ⅱ改进算 法NSGA-Ⅱ-UTEA，并与NSGA-Ⅱ、NSGA-Ⅲ、MOEA/ D、 NSGA-Ⅱ-ARSBX 和 RPD-NSGA-Ⅱ 5 种典型的 进化算法进行对比。经过 IGD 和 HV 两项测试标准 的比较，证实了本文 NSGA-Ⅱ-UTEA 算法在种群多 样性和分布性方面改进的有效性，特别是高维多目 标优化问题的优势更加明显。其中，在种群分布性 的优势也说明了 NSGA-Ⅱ-UTEA 算法能够平衡每个 子目标函数，以得到更好的 Pareto 非支配最优解集。 由于未考虑循环结构的矢量化编程和并行计算，导 致本文算法在收敛效率方面尚存在一定的改进空 间。因此，在未来的工作中，我们将进一步探索算法 搜索质量和收敛效率的权衡兼顾策略。

参考文献：

邹蒲， 邓吉秋， 刘立， 等. 地质灾害应急中无人机运输与飞 行路径规划[J]. 测绘与空间地理信息， 2017， 40（10）： 15- 17.

SINGH S， CHANA I. A survey on resource scheduling in cloud computing： Issues and challenges[J]. Journal of Grid Computing， 2016， 14（2）： 217-264.

秦大同， 隗寒冰， 段志辉， 等. 重度混合动力汽车油耗和排 放多目标实时最优控制[J]. 机械工程学报， 2012， 48（6）： 83-89.

DEB K， PRATAP A， AGARWAL S， et al. A fast and eli[1]tist" multiobjective" genetic" algorithm：" NSGA-Ⅱ[J]. IEEE Transactions" on" Evolutionary" Computation，" 2002，" 6（2）： 182-197.

ZHANG Q，" LI" H." MOEA/D：" A" multiobjective"" evolution[1]ary" algorithm" based" on" decomposition[J]. IEEE" Transac[1]tions on Evolutionary Computation， 2007， 11（6）： 712-731.

ZITZLER E， KÜNZLI S. Indicator-based selection in mul[1]tiobjective" search[C]//International "Conference" on" Parallel Problem Solving from Nature. Berlin， Heidelberg： Springer， 2004： 832-842.

WU" T，" AN" S，" HAN" J， et al." An ε-domination" based" two[1]archive" 2" algorithm" for" many-objective" optimization[J]. Journal" of" Systems "Engineering" and" Electronics，" 2022， 33（1）： 156-169.

GU Q， CHEN H， CHEN L， et al. A many-objective evolu[1]tionary algorithm with reference points-based strengthened dominance" relation[J]. Information" Sciences，" 2021，" 554： 236-255.

WANG" X，" XIE" Z，" ZHOU" X， et al." A" two-stage" adaptive reference" direction" guided" evolutionary" algorithm" with modified dominance" relation" for" many-objective"" optimiza[1]tion[J]. Swarm" and" Evolutionary" Computation，" 2023，" 78： 101272.

LI" B，" LI" J，" TANG" K， et al. An" improved" two" archive"" al[1]gorithm" for" many-objective" optimization[C]//2014" IEEE Congress" on" Evolutionary" Computation" （CEC）." Berlin， Heidelberg： Springer， 2014： 2869-2876.

王超学， 田利波. 一种改进的多目标合作型协同进化遗传 算法[J]. 计算机工程与应用， 2016， 52（2）： 18-23.

LAUMANNS" M，" THIELE" L，" DEB" K， et al." Combining convergence" and" diversity" in" evolutionary" multiobjective optimization[J]. Evolutionary" Computation，" 2002，" 10（3）： 263-282.

HADKA" D，" REED" P." BORG：" An" auto-adaptive" many[1]objective evolutionary computing framework[J]. Evolution[1]ary Computation， 2013， 21（2）： 231-259.

YUAN" Y，" XU" H，" WANG" B， et al." A" new" dominance relation-based" evolutionary" algorithm" for "many-objective optimization[J]." IEEE" Transactions" on" Evolutionary Computation， 2015， 20（1）： 16-37.

LIU Y， ZHU N， LI K， et al. An angle dominance criterion for" evolutionary" many-objective" optimization[J]. Informa[1]tion Sciences， 2020， 509： 376-399.

ZOU" X，" CHEN" Y，" LIU" M， et al." A" new" evolutionary algorithm for" solving" many-objective" optimization"" prob[1]lems[J]. IEEE" Transactions" on" Systems，" Man，" and Cybernetics： Part B （Cybernetics）， 2008， 38（5）： 1402-1412.

WANG G， JIANG H. Fuzzy-dominance and its application in evolutionary many objective optimization[C]//2007 Inter[1]national" Conference" on" Computational" Intelligence" and Security" Workshops" （CISW" 2007）." Berlin，" Heidelberg： Springer， 2007： 195-198.

DI P F， KHU S T， SAVIC D A. An investigation on prefer[1]ence order ranking scheme for multiobjective evolutionary optimization[J]. IEEE Transactions" on" Evolutionary" Com[1]putation， 2007， 11（1）： 17-45.

ADRA" S" F，" FLEMING" P" J." Diversity" management" in evolutionary" many-objective" optimization[J]." IEEE Transactions" on" Evolutionary" Computation，" 2010，" 15（2）： 183-195.

DEB K， JAIN H. An evolutionary many-objective optimi[1]zation algorithm" using" reference-point-based"" nondomin[1]ated" sorting" approach：" Part" I." Solving" problems" with" box constraints[J]. IEEE Transactions on Evolutionary Compu[1]tation， 2013， 18（4）： 577-601.

LI M， YANG S， LIU X. Shift-based density estimation for Pareto-based algorithms in many-objective optimization[J]. IEEE" Transactions" on" Evolutionary" Computation，" 2013， 18（3）： 348-365.

KÖPPEN M，" YOSHIDA" K." Substitute" distance"" assign[1]ments in NSGA-Ⅱ for handling many-objective optimiza[1]tion problems[C]//International" Conference" on"" Evolution[1]ary" Multi-Criterion" Optimization." Berlin，" Heidelberg： Springer， 2007： 727-741.

LÓPEZ A， COELLO C A C， OYAMA A， et al. An alterna[1]tive preference relation to deal with many-objective optimi[1]zation problems[C]//International Conference on Evolution[1]ary" Multi-Criterion" Optimization." Berlin，" Heidelberg： Springer， 2013： 291-306.

YANG" S，" LI" M，" LIU" X， et al." A" grid-based" evolutionary algorithm for many-objective optimization[J]. IEEE Trans[1]actions" on" Evolutionary" Computation，" 2013，" 17（5）：" 721- 736.

ZHANG X，" TIAN" Y，" JIN" Y." A" knee" point-driven"" evolu[1]tionary algorithm for many-objective optimization[J]. IEEE Transactions" on" Evolutionary" Computation，" 2014，" 19（6）： 761-776.

MICHALAK" K." Improving" the" NSGA-Ⅱ Performance with an external population[C]//International Conference on Intelligent" Data" Engineering" and" Automated" Learning. Berlin， Heidelberg： Springer， 2015： 273-280.

张涛， 陈忠， 吕一兵. 利用一种改进的模拟退火算法求解多目标规划问题[J]. 武汉工业学院学报， 2013， 32（2）： 74- 76.

刘鑫平， 顾春华， 罗飞， 等. 基于败者组与混合编码策略的 NSGA-Ⅱ 改进算法[J]. 计算机科学， 2019， 46（10）： 222- 228.

王李进， 钟一文， 尹义龙. 带外部存档的正交交叉布谷鸟 搜索算法[J]. 计算机研究与发展，" 2015，" 52（11）：" 2496- 2507.

KNOWLES J" D，" CORNE" D" W." Approximating" the"" non[1]dominated" front" using" the" Pareto" archived" evolution strategy[J]. Evolutionary" Computation，" 2000，" 8（2）：" 149- 172.

ZHANG J， SANDERSON A C. JADE： Adaptive differen[1]tial evolution with optional external archive[J]. IEEE Trans- actions" on" Evolutionary" Computation，" 2009，" 13（5）：" 945- 958.

ZOU J， JI C， YANG S， et al. A knee-point-based evolution[1]ary" algorithm" using" weighted" subpopulation" for" many[1]objective optimization[J]. Swarm and Evolutionary Compu[1]tation， 2019， 47： 33-43.

KHARE V， YAO X， DEB K. Performance scaling of multi[1]objective evolutionary algorithms[C]//International Confer[1]ence on Evolutionary Multi-Criterion Optimization. Berlin， Heidelberg： Springer， 2003： 376-390.

HUBAND" S，" BARONE" L，" WHILE" L， et al." A" scalable multi-objective test" problem" toolkit[C]//International"" Con[1]ference on Evolutionary Multi-Criterion Optimization. Ber[1]lin， Heidelberg： Springer， 2005： 280-295.