基于外部存檔更新及截?cái)嗟?NSGA-Ⅱ改進(jìn)算法

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

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

中圖分類號：TP301.6

文獻(xiàn)標(biāo)志碼：A

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

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

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

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

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

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

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

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

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

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

2""" NSGA-Ⅱ-UTEA 算法

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

綜上，NSGA-Ⅱ-UTEA 算法的總體流程如圖 1 所示。首先 ，初始化種群 P（t） 和外部存檔 EA，對 P（t） 進(jìn)行交叉、變異生成第 1 代子種群 Q（t），將父代 種群 P（t） 與子代種群 Q（t） 合并，形成新種群 R（t），并 對其進(jìn)行非支配排序，產(chǎn)生一系列非支配集 F（t）。然 后，不斷將等級小的非支配集加入到新的父代種群 P（t） 中，一直加到第 k 層非支配集 F（k），種群的大小 超出 N。接著，使用非支配集 F（k） 更新外部存檔，如 果此時(shí)外部存檔的大小加上前 k?1 層非支配集正好 為種群大小 N，則將外部存檔與前 k?1 層非支配集合 并，生成新的父代種群 P（t），否則使用前 k?1 層非支 配集 F（1）～F（k?1） 進(jìn)行外部存檔截?cái)嗖僮鳎钡酵獠?存檔大小加上前 k?1 層非支配集等于種群大小 N，此 時(shí)算法運(yùn)行結(jié)束。

表 1 所示是 NSGA-Ⅱ-UTEA 算法的偽代碼。在 算法 1 中，外部存檔更新的流程如表 2 的算法 2 所 示。首先進(jìn)行權(quán)重向量的劃分，然后根據(jù)個(gè)體的支 配關(guān)系決定是否加入外部存檔，最后根據(jù)個(gè)體到權(quán) 重向量距離和到超平面距離之和的大小，刪除多余的個(gè)體。外部存檔截?cái)鄼C(jī)制的流程如表 3 的算法 3 所示，首先判斷第 1 層非支配集的個(gè)體數(shù)是否超過 種群數(shù)量，然后判斷外部存檔的大小是否符合要求， 最后根據(jù)個(gè)體間的角度，刪除外部存檔中的多余個(gè)體。

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

2.1 外部存檔更新策略

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

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

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

2.2 外部存檔截?cái)鄼C(jī)制

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

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

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

3""" 實(shí)驗(yàn)與結(jié)果分析

3.1 測試函數(shù)

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

3.3 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

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

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

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

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

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

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

為 了 進(jìn) 一 步 直 觀 地 反 映 NSGA-Ⅱ-UTEA、 NSGA-Ⅱ、NSGA-Ⅲ、MOEA/D、NSGA-Ⅱ-ARSBX 和 RPD-NSGA-Ⅱ 6 種算法在高維目標(biāo)空間中得到的最 終解集的分布情況，本文采用平行坐標(biāo)圖來可視化 高維數(shù)據(jù)。由于本文篇幅的限制，只提供了上述 6 種 算法在 30 維目標(biāo) WFG4 上最終解集的平行坐標(biāo)圖， 如圖 2 所示。在高維目標(biāo)空間中的一個(gè)點(diǎn)被表示為 一條拐點(diǎn)在 M 條平行于坐標(biāo)軸的折線，在第 k 個(gè)坐 標(biāo)軸上的位置就表示這個(gè)點(diǎn)在第 k 維的目標(biāo)函數(shù)值， 其中 WFG4 問題的第 k 維目標(biāo)函數(shù)值在 [0，2k] 之間。

從圖 2 可以看出，NSGA-Ⅱ-UTEA 算法在種群 分布性和多樣性方面都獲得了很好的效果；NSGA-Ⅱ 和 NSGA-Ⅱ-ARSBX 算法能滿足種群多樣性的要 求 ， 但 收 斂 性 較 差 ； NSGA-Ⅲ 、 MOEA/D 和 RPD[1]NSGA-Ⅱ算法在高維目標(biāo)空間中存在目標(biāo)解丟失的 情況，導(dǎo)致分布性差于 NSGA-Ⅱ-UTEA 算法。綜上 所述，NSGA-Ⅱ-UTEA 算法得到的解集分布更加均 勻，提升了種群的分布性和多樣性，在解決高維多目 標(biāo)優(yōu)化問題時(shí)有很大的優(yōu)勢。

4""" 結(jié)束語

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

參考文獻(xiàn)：

鄒蒲， 鄧吉秋， 劉立， 等. 地質(zhì)災(zāi)害應(yīng)急中無人機(jī)運(yù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.

秦大同， 隗寒冰， 段志輝， 等. 重度混合動(dòng)力汽車油耗和排 放多目標(biāo)實(shí)時(shí)最優(yōu)控制[J]. 機(jī)械工程學(xué)報(bào)， 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.

王超學(xué)， 田利波. 一種改進(jìn)的多目標(biāo)合作型協(xié)同進(jìn)化遺傳 算法[J]. 計(jì)算機(jī)工程與應(yīng)用， 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ìn)的模擬退火算法求解多目標(biāo)規(guī)劃問題[J]. 武漢工業(yè)學(xué)院學(xué)報(bào)， 2013， 32（2）： 74- 76.

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

王李進(jìn)， 鐘一文， 尹義龍. 帶外部存檔的正交交叉布谷鳥 搜索算法[J]. 計(jì)算機(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.