摘要：傳統(tǒng)的 NSGA-Ⅱ（Non-dominated Sorting Genetic Algorithm Ⅱ） 算法使用擁擠度作為 精英選擇的第二指標，該方法在處理高維多目標優(yōu)化問題時，常常由于選擇壓力不足，以及不 同目標間優(yōu)化沖突加劇等原因，很難維持種群收斂性和多樣性的平衡。針對上述問題，提出一 種基于外部存檔更新及截斷機制的 NSGA-Ⅱ改進算法 NSGA-Ⅱ-UTEA（NSGA-Ⅱ algorithm based on Update and Truncation of External Archive）。該算法首先在精英選擇中引入基于權重 向量分解的外部存檔機制，然后根據個體與所在權重向量及超平面距離之和更新外部存檔，并 基于個體間角度計算實現(xiàn)外部存檔截斷，進一步提升了算法在高維多目標優(yōu)化問題中種群的收 斂性和多樣性。與 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） 系列測試函數上，各項性能 指標整體優(yōu)于其他算法，在解集的分布性和多樣性方面具有顯著優(yōu)勢。特別是在大部分高維 WFG4～WFG7 凹問題上都能取得最佳的性能指標值。與傳統(tǒng)的 NSGA-Ⅱ算法相比，NSGA-Ⅱ- UTEA 算法在 10 目標以上的高維 DTLZ 系列測試函數上，反世代距離（IGD）性能平均提升了 50.6%；在 15 目標以上的高維 WFG 系列測試函數上，超體積（HV）性能平均提升了 60.7%。實 驗結果驗證了 NSGA-Ⅱ-UTEA 算法改進的有效性。

關鍵詞：多目標優(yōu)化；精英選擇；NSGA-Ⅱ；權重向量；外部存檔

中圖分類號：TP301.6

文獻標志碼：A

隨著云計算、大數據和人工智能等技術的迅猛發(fā) 展，高維多目標優(yōu)化問題 （Many-objective Optimization Problems， MaOPs） 開始普遍出現(xiàn)于科學研究和工程 應用領域，例如無人機路徑規(guī)劃[1]、云資源調度優(yōu) 化[2]、混合動力汽車控制[3] 等。因此，研究和設計針 對 MaOPs 的高效優(yōu)化算法具有重要的理論價值和現(xiàn) 實意義。

傳 統(tǒng) 的 多 目 標 進 化 算 法 ， 如 NSGA-Ⅱ[4]、 MOEA/D[5] 和 IBEA（Indicator-Based" multi-objective Evolutionary Algorithm）[6] 等，在求解低維多目標優(yōu)化 問題時通常能夠表現(xiàn)出很好的性能，但在處理高維 多目標優(yōu)化問題時，一方面，由于目標空間維數增 大，種群中大部分的個體是非支配的，導致選擇壓力 不足；另一方面，目標空間維數的增大加劇了目標間 的優(yōu)化沖突，無法兼顧種群的收斂性和多樣性，算法 的優(yōu)化效果顯著下降。

為了增強算法目標變量維數的可擴展性，國內 外學者通常從以下兩個角度進行相關改進。第 1 個角度是修改傳統(tǒng)的 Pareto 優(yōu)勢關系定義，以增加向帕 累托前沿的選擇壓力。Wu 等 [7] 提出的一種基于 ε- domination 的 ε-Two_Arch2 算 法 ， 分 配 ε-domination 更新多樣性歸檔中的個體以增加算法的選擇壓力。

Gu 等 [8] 提出了一種新的基于參考點的增強優(yōu)勢關 系的 RPS-NSGA-Ⅱ（Reference point-based Strengthened NSGA-Ⅱ）算法，通過參考點集和收斂度量 Cov 來區(qū) 分 Pareto 解集，并進一步對其進行分層。第 2 個角度 是引入新的多樣性選擇指標，使用新的機制來促進 種群的多樣性。Wang 等 [9] 提出了一種基于解決方 案和參考方向之間基于懲罰的自適應矩形區(qū)域 （APA） 的新型聚類指標，以協(xié)助非支配級別排序來解 決傳統(tǒng)基于支配的多目標進化算法在高維多目標中 失效的問題。然而，上述兩種方法都存在一些問 題。其中，過度修改傳統(tǒng)的 Pareto 優(yōu)勢關系定義，可 能會導致算法復雜度升高和計算性能下降，最終導 致 Pareto 前沿不包括真正的優(yōu)秀解。引入新的多樣 性選擇指標，需要經過特定的設計才能更好地反映 問題的本質，這就需要更多的計算和存儲資源，算法 的效率降低。

外部存檔技術是一種能夠在不增加算法框架本 身計算復雜度的前提下，實現(xiàn)非支配解的維護，增強 可行解之間的選擇壓力，緩解種群收斂性和多樣性 沖突的有效手段[10]。通過設置外部檔案保存進化過 程中所搜索到的所有非支配解，以避免因為隨機因素 而引起的優(yōu)質解丟失[11]。本文以 NSGA-Ⅱ算法框架 為主體，結合 MOEA/D 分解思想的優(yōu)勢，在精英選擇 策略中引入基于權重向量分解的外部存檔機制，提 出了一種基于外部存檔更新及截斷的 NSGA-Ⅱ改進 算 法 NSGA-Ⅱ-UTEA（NSGA-Ⅱ algorithm" based" on Update and Truncation of External Archive）。該算法首 先引入權重向量，加速種群的收斂速度；然后根據個 體與權重向量和超平面距離制定外部存檔更新策 略，并基于個體間角度計算實現(xiàn)外部存檔截斷機制， 得到符合條件的外部存檔，并保留下來，直接參與下 一代種群的精英選擇，從而提高了種群的多樣性和 分布性。

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

經典 NSGA-Ⅱ算法的主要缺陷是在高維多目標 優(yōu)化問題中，種群的非支配個體占比很高，甚至可能 達到 100%，這將導致基于支配的選擇壓力不足，種 群收斂速度降低。針對 NSGA-Ⅱ算法存在的以上問 題，研究人員一般從以下兩個角度進行優(yōu)化。

第 1 類技術的主要思想是修改傳統(tǒng)的 Pareto 優(yōu) 勢關系定義，以增加向帕累托前沿的選擇壓力。這 種類型的思想已被廣泛用于解決 MaOPs。如具有代 表性的支配關系 ?-dominance[12-13] 劃分整個目標空間 為一個個網格，并將解分布在不同的網格中。除此 之外，還有很多其他可選的偏好關系在處理高維多 目標優(yōu)化問題中也非常有前景，如 θ-dominance[14]、 Angle-dominance[15]、L-optimality[16]、fuzzy-dominance[17] 和偏好順序排序[18]。與使用傳統(tǒng) Pareto 優(yōu)勢關系的 多目標進化算法相比，盡管這些策略很可能收斂到 Pareto 前沿的一個子區(qū)域，但是它們已經被證明能夠 顯著地提高多目標進化算法求解 MaOPs 的性能。

第 2 類技術的主要思想是引入新的多樣性選擇 指標，使用新的機制來促進種群的多樣性?；谥?配的選擇機制在高維目標空間中提供的選擇壓力不 足以區(qū)分不同的解，這將導致搜索偏離 Pareto 前沿 面。為了避免上述現(xiàn)象的發(fā)生，在高維多目標優(yōu)化 問題中保持種群的多樣性所采取的選擇策略顯得尤 為重要。Adra 等[19] 提出了兩種管理多樣性的機制且 研究了它們在高維多目標優(yōu)化中對算法總體收斂性 的影響。Deb 等[20] 提出的 NSGA-Ⅲ算法，使用參考 點代替擁擠度來選擇個體。Li 等[21] 對基于 Pareto 優(yōu) 勢的多目標進化算法的多樣性標準進行了一般性修 改，即基于移位的密度估計 （SDE） 策略，涵蓋了個體 的分布和收斂信息。K?ppen 等[22]提出了一些替代距 離，這些替代距離基于一個解決方案幾乎被任何其 他解決方案支配的程度。在文獻 [23] 中，一個二進 制 "? 將基于指標的偏好與優(yōu)勢相結合 ，以加 快 NSGA-Ⅱ算法在求解 MaOPs 時的收斂速度。Yang 等[24] 還定義了一個基于網格優(yōu)勢的度量標準，并在 此基礎上提出了一個用于 MaOPs 的有效 MOEA，稱 為 GrEA。此外還有拐點驅動的進化算法 （KnEA）[25] 等，這些算法將傳統(tǒng)優(yōu)勢與額外的收斂相關度量結 合起來，提高了種群的多樣性。

外部存檔的目的主要是保留父代中的優(yōu)良遺傳 特性。為了避免搜索過程中優(yōu)秀個體的流失，近年 來許多學者針對在進化算法中使用外部存檔機制進 行了相關的研究，提升了種群的收斂性。Michalak[26] 引進一個外部種群存儲每一代的非支配解，并將其 部分或者全部重新引入到主種群中，豐富了種群多 樣性。張濤等[27] 提出了一種新的能量差計算方式， 使用外部存檔技術提升了模擬退火算法的性能。劉 鑫平等[28] 設定了一個外部歸檔集，在每次迭代時對 子代種群執(zhí)行歸檔操作并淘汰適應度較差的個體， 使歸檔集保持較好的分布性。王李進等[29] 將外部存檔機制應用到布谷鳥搜索算法中，極大地提高了算 法的收斂速度。此外 ，還有引入了外部存檔 的 PAES[30] （Pareto 文檔進化策略）、帶有可選擇外部存 檔的自適應差分進化算法 JADE[31] 等。

2""" NSGA-Ⅱ-UTEA 算法

NSGA-Ⅱ-UTEA 算法是在 NSGA-Ⅱ算法基礎上 引入基于權重向量分解的外部存檔機制。首先將種 群空間分解為均勻的權重向量，為每個子問題分配 權重向量；然后根據個體與權重向量和超平面距離 制定外部存檔更新策略，并基于個體間角度計算實 現(xiàn)外部存檔截斷機制，得到符合條件的外部存檔，并 保留下來，直接參與下一代種群的精英選擇，提高了 種群的多樣性和分布性。

綜上，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 算法在精英選擇 環(huán)節(jié)中引入了一種基于權重向量分解的外部存檔機 制。首先外部存檔記錄優(yōu)秀的解，可以防止這些解 在進化過程中被淘汰，從而保證了種群進化的收斂 性。其次，在精英選擇中，同時考慮個體的適應度函 數值和它與所在權重向量及超平面的距離之和。這 種方法能夠更好地估計個體的品質，并使得個體與 外部存檔中的解進行更精確的比較，從而更好地維 護外部存檔中的多樣性，進而避免算法早熟并提高 算法的搜索能力。此外，NSGA-Ⅱ-UTEA算法還引入 了外部存檔截斷機制，通過計算不同解之間的角度 來保持外部存檔中的多樣性。這種機制使得算法能 夠在不降低搜索能力的情況下，控制外部存檔的大 小 ， 從 而 更 高 效 地 處 理 高 維 多 目 標 優(yōu) 化 問 題 。

2.1 外部存檔更新策略

外部存檔的目的主要是保留父代中的優(yōu)良遺傳 特性。為了避免搜索過程中優(yōu)秀非支配解的流失， 將其保存到外部存檔中，作為父代參與到下一代的 進化過程中。因此，外部存檔在算法的進化過程中 需要不斷進行迭代更新。

本文提出的外部存檔更新策略基本流程：首先， 保留上一次進化得到的外部存檔 EA，然后將非支配 集 F（k） 中的個體 Xi 歸到權重向量 λj 上。如果 Xi 不 能被屬 于 λj 的其他個體所支配 ，則 將 Xi 加 入 到 EA 中。如果 Xi 與 EA 中屬于 λj 的其他個體互不支 配，則刪除相比 Xi 到 λj 距離和 Xi 到超平面距離之和 大的第 1 個個體，否則刪除被 Xi 支配的其他個體。 直到最后 EA 的大小滿足條件，此時算法運行結束。

本文提出的個體與權重向量的距離代表解集中 的個體之間的差異程度，體現(xiàn)了解集的分布性和個 體的多樣性。為了評價個體與參考點的接近程度， Zhang 等 [31] 提出了一個拐點（knee point）概念。拐點 是指在多目標問題中，所有目標函數的值均可以被 優(yōu)化的非支配解集合中最接近參考點 （ reference point）的解。Zou 等 [32] 提出了一種使用加權子種群 拐點的多目標優(yōu)化算法。該算法的核心是通過種群 的拐點來引導種群的搜索方向，計算解和超平面之 間的距離，距離最短的點被認為是拐點，每一個拐點 代表了其子種群的最優(yōu)解，用于引導群體向 PF 方向 的搜索。本文中個體到超平面的距離代表了個體與 拐點的近似程度，偏向非支配解中的拐點被證明是 偏向大超體積的近似，從而增強了多目標優(yōu)化中的 收斂性能。此外，由于至多一個解將被識別為非支 配前沿中每個解的鄰域內的拐點，因此在所提出的 算法中不需要引入額外的多樣性維護機制，與用于 多目標優(yōu)化的許多現(xiàn)有多目標進化算法相比，顯著 降低了計算復雜度。

2.2 外部存檔截斷機制

外部存檔的更新策略將會導致優(yōu)秀的非支配解 不斷加入外部存檔，最終導致外部存檔個體數越來 越多。但是每一代所需要的外部存檔個體數是由種 群大小和前 k?1 層非支配集所共同決定的。因此，對于超出所需數量的外部存檔，必須采取相應的截斷 機制 ，以保證種群數量在進化過程中保持不變。

本文提出的外部存檔截斷機制基本流程為：首 先，保留上一次進化得到的外部存檔 EA，然后根據 第一層非支配集 F（1） 的個體數是否大于 N 分成兩種 情況。第 1 種情況：若 F（1） 的個體數大于 N，則在 EA 的個體間進行角度計算，循環(huán)刪除角度最小的個 體，直到 EA 的大小等于 N，算法運行結束；第 2 種情 況：若 F（1） 的個體數小于 N，則判斷前 k?1 層非支配 集和 EA 的個體數之和是否等于 N，如果不等于則將 EA 的個體與前 k?1 層的個體進行角度計算，循環(huán)刪 除角度最小的個體，直到等于 N，算法運行結束。

從時間復雜度上來看，表 1 中 NSGA-Ⅱ-UTEA 算法執(zhí)行步驟 4、5 需要的時間復雜度最大，同時 NSGA-Ⅱ-UTEA 算法沒有在原算法的基礎上增加額 外的時間復雜度，因此時間復雜度和原算法保持一 致，為 O（MN2 ），其中 M 表示目標維數。從空間復雜 度上來看，NSGA-Ⅱ-UTEA算法中盡管增加了外部存 檔，但是并沒有增加空間復雜度，執(zhí)行步驟最大的空 間復雜度仍為 O（N）。

3""" 實驗與結果分析

3.1 測試函數

為了便于與以往文獻中的實驗結果進行對比分 析，本文設置了相同的種群規(guī)模、實驗重復次數和函 數評估次數等條件，并選擇了 DTLZ[33] 和 WFG[34] 系列 函數作為測試問題。DTLZ1～DTLZ4 和 WFG4～WFG7 測試函數的屬性如表 4 所示。

3.3 實驗結果與分析

多 目 標 優(yōu) 化 算 法 性 能 評 估 標 準 主 要 包 括 Pareto 最優(yōu)解集的空間分布性和收斂性。Pareto 最優(yōu) 解集空間分布性用以衡量 Pareto 最優(yōu)解的質量，收斂 性用以測試算法尋優(yōu)能力。本文采用帶精英策略的非支配排序的遺傳算法 NSGA-Ⅱ、基于參考點的非 支配遺傳算法 NSGA-Ⅲ、基于分解的多目標進化算 法 MOEA/D、基于旋轉的模擬二元交叉的 NSGA-Ⅱ- ARSBX 算法 、基于分解支配關系 的 RPD-NSGA- Ⅱ算法以及本文改進算法 NSGA-Ⅱ-UTEA 對 DTLZ 測試集（ DTLZ1～DTLZ4）與 WFG 測試集（WFG4～ WFG7）進行測試，通過實驗驗證 NSGA-Ⅱ-UTEA 算 法在 IGD 和 HV 兩個性能評估標準方面相比其他算 法具有優(yōu)勢，結果如表 5 和表 6 所示。

所有實驗都基于 PlatEMO v3.5 平臺；編程語言： Matlab；編程環(huán)境：MatlabR2021a；內存：16GB；操作系 統(tǒng)：Windows10。設置初始種群規(guī)模為 100，重復計 算 30 次，表中深灰色背景表示最優(yōu)值，淺灰色背景表 示次優(yōu)值。為了進行結果比較 ，采用了 Wilcoxon 秩和檢驗，其顯著性水平設置為 0.05，表中的“+”、 “=”和“?”分別表示比較的算法是否顯著優(yōu)于、顯著 劣于和沒有顯著差異于本文提出的 NSGA-Ⅱ-UTEA 算法。

3.3.1"" DTLZ 測試函數實驗結果分析 表 5 示出了 6 種算法在 DTLZ 測試函數不同維度上的 IGD 平均 值與標準差。從實驗結果可知，在 DTLZ 測試函數 中，NSGA-Ⅱ-UTEA 算法在分布性和多樣性方面優(yōu) 于其他對比算法，只有在少量 DTLZ 測試函數上，略 次 于 MOEAD 算 法 、 NSGA-Ⅲ 算 法 和 RPD-NSGA- Ⅱ算法，但結果相差不大。

從表 5 還可以看出，相比 NSGA-Ⅱ、NSGA-Ⅲ、 MOEA/D、NSGA-Ⅱ-ARSBX 和RPD-NSGA-Ⅱ，NSGA- Ⅱ-UTEA 表現(xiàn)更優(yōu)的測試實例比例分別為 12/20， 8/20，7/20，12/20，9/20，而 NSGA-Ⅱ-UTEA 表現(xiàn)較差 的比例分別為 6/20，6/20，7/20，7/20，6/20。由比例結 果可以看出，相比于其他算法，NSGA-Ⅱ-UTEA 算法 整體表現(xiàn)最好，能夠有效處理 DTLZ1～DTLZ4 測試 函數集。

在 DTLZ1 函數問題上，NSGA-Ⅱ-UTEA 算法只 在 5 維和 15 維目標空間中獲得的 IGD 值優(yōu)于其他 算法，但在 10 維目標空間中僅次于 MOEA/D 算法。 DTLZ1 是一個具有線性 Pareto 最優(yōu)面的較簡單的 M 個目標的測試問題，高維目標空間問題的搜索空 間較大，算法不容易收斂。另外，高維目標空間問題 增加了算法的復雜度，導致算法產生較低的分布性 能。因此，NSGA-Ⅱ-UTEA 算法在 DTLZ1 函數問題 上很難達到最優(yōu)效果。

此外 ， NSGA-Ⅱ-UTEA 算法在 DTLZ3、 DTLZ4 函數問題上整體優(yōu)于其他對比算法 ，這是因 為 DTLZ3 測試的是一個 MOEA 收斂到全局 Pareto 最 優(yōu)的能力，DTLZ4 函數問題側重于測試 MOEA 算法 的解的分布性，而 NSGA-Ⅱ-UTEA 算法中使用了個 體與權重向量及超平面距離之和來更新外部存檔。 個體到超平面的距離代表了個體與拐點的近似程 度，偏向非支配解中的拐點被證明是偏向大超體積 的近似，從而增強了多目標優(yōu)化中的收斂性能。個 體與權重向量的距離代表解集中個體之間的差異程 度，因此解集的分布性更好。

綜上所述，在解決 DTLZ1～DTLZ4 函數問題時， NSGA-Ⅱ-UTEA 算法能夠保證種群較好的收斂性和 多樣性，特別是在高維目標空間中算法的優(yōu)勢更加 明顯。

3.3.2"" WFG 測 試 函 數 實 驗 結 果 分 析 ""相 比 于 DTLZ 測試函數 ，WFG 考察的數學特征更多更全 面，比如不可分、欺騙性等。表 6 示出了 6 種算法在 WFG 測試函數不同維度上的 HV 平均值與標準差。 從實驗結果可知，在 WFG 測試函數問題上，NSGA- Ⅱ-UTEA 算法在高維多目標空間中的分布性和多樣 性優(yōu)于其他對比算法，在低維多目標空間中略次于 NSGA-Ⅲ算法 和 RPD-NSGA-Ⅱ算法 ，但結果相差 不大。

從 表 6 中 數 據 可 以 看 出 ， 相 比 于 NSGA-Ⅱ 、 NSGA-Ⅲ、MOEA/D、NSGA-Ⅱ-ARSBX 和RPD-NSGA- Ⅱ，NSGA-Ⅱ-UTEA 表現(xiàn)出更優(yōu)的測試實例比例分 別為 18/32， 15/32， 14/32， 15/32， 11/32，而 NSGA-Ⅱ- UTEA 表現(xiàn)較差的比例分別為 5/32，9/32，7/32，7/32， 8/32。由比例結果可以看出 ，相比于其他算法 ， NSGA-Ⅱ-UTEA算法整體表現(xiàn)最好，能夠有效處理 WFG4～WFG7測試函數集。

由表 6 數據可知 ，除了在測試函數 WFG6 的 3 維、8 維、10 維和 15 維上，NSGA-Ⅱ-UTEA 算法表 現(xiàn)不如 NSGA-Ⅱ算法外 ，其他情況均優(yōu)于 NSGA- Ⅱ算法，說明了本文算法改進的有效性。 NSGA-Ⅱ-UTEA 算 法 在 15～30 維 的 WFG4 和 WFG5 測試函數上的表現(xiàn)優(yōu)于其他算法，在 3～10 維 的 HV 值略差于 NSGA-Ⅲ算法。這是由于 NSGA- Ⅱ-UTEA 在高維多目標問題中能很好地兼顧局部搜 索和全局搜索的能力，而 WFG4 測試函數存在大量 的局部最優(yōu)解，主要考察算法在縮放的情況下，算法 的全局搜索能力。WFG5 測試函數具有欺騙的特性， 主要考察算法是否能夠避免陷入局部收斂，進行有 效搜索。而 NSGA-Ⅱ-UTEA 在精英選擇中引入個體 到所在權重向量及超平面距離之和來更新外部存 檔，避免算法早熟并提高算法的搜索能力。

NSGA-Ⅱ-UTEA 算 法 在 20～30 維 的 WFG6 和WFG7 測試函數上獲得的 HV 值均大于其他對比算 法，在 3～15 維的 WFG6 和 WFG7 測試函數上表現(xiàn)不 佳。這是因為 WFG6 側重于決策變量的不可分離， WFG7 側重于有偏特性，主要考察算法能否處理大量 最優(yōu)解集中在某一處的問題。NSGA-Ⅲ算法引入參 考點的概念，在搜索過程中能更好地避免局部最優(yōu) 解。但是隨著問題維度的增加，搜索空間的大小呈 指數級增長，NSGA-Ⅲ算法表現(xiàn)不佳，而 NSGA-Ⅱ- UTEA 算法通過外部存檔更新策略增強了算法搜索 能力，避免算法陷入局部最優(yōu)解。

綜上所述，NSGA-Ⅱ-UTEA 算法在解決 WFG4～ WFG7 4 個測試函數問題時，在 20～30 的高維目標空 間中均能夠獲得最優(yōu)的 HV 值，這也表明了相較于其 他算法，NSGA-Ⅱ-UTEA 算法所獲得的解集是在分 布性和多樣性方面更加接近真實 PF 的非占優(yōu)解集。

為 了 進 一 步 直 觀 地 反 映 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 算法得到的解集分布更加均 勻，提升了種群的分布性和多樣性，在解決高維多目 標優(yōu)化問題時有很大的優(yōu)勢。

4""" 結束語

本文以多目標優(yōu)化問題為研究對象，提出一種 基于外部存檔更新及截斷機制的 NSGA-Ⅱ改進算 法NSGA-Ⅱ-UTEA，并與NSGA-Ⅱ、NSGA-Ⅲ、MOEA/ D、 NSGA-Ⅱ-ARSBX 和 RPD-NSGA-Ⅱ 5 種典型的 進化算法進行對比。經過 IGD 和 HV 兩項測試標準 的比較，證實了本文 NSGA-Ⅱ-UTEA 算法在種群多 樣性和分布性方面改進的有效性，特別是高維多目 標優(yōu)化問題的優(yōu)勢更加明顯。其中，在種群分布性 的優(yōu)勢也說明了 NSGA-Ⅱ-UTEA 算法能夠平衡每個 子目標函數，以得到更好的 Pareto 非支配最優(yōu)解集。 由于未考慮循環(huán)結構的矢量化編程和并行計算，導 致本文算法在收斂效率方面尚存在一定的改進空 間。因此，在未來的工作中，我們將進一步探索算法 搜索質量和收斂效率的權衡兼顧策略。

參考文獻：

鄒蒲， 鄧吉秋， 劉立， 等. 地質災害應急中無人機運輸與飛 行路徑規(guī)劃[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.

秦大同， 隗寒冰， 段志輝， 等. 重度混合動力汽車油耗和排 放多目標實時最優(yōu)控制[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.

王超學， 田利波. 一種改進的多目標合作型協(xié)同進化遺傳 算法[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.

張濤， 陳忠， 呂一兵. 利用一種改進的模擬退火算法求解多目標規(guī)劃問題[J]. 武漢工業(yè)學院學報， 2013， 32（2）： 74- 76.

劉鑫平， 顧春華， 羅飛， 等. 基于敗者組與混合編碼策略的 NSGA-Ⅱ 改進算法[J]. 計算機科學， 2019， 46（10）： 222- 228.

王李進， 鐘一文， 尹義龍. 帶外部存檔的正交交叉布谷鳥 搜索算法[J]. 計算機研究與發(fā)展，" 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.