考慮全局和局部帕累托前沿的多模態多目標優化算法

李文樺 明夢君 張 濤,2 王 銳,2 黃生俊,2 王 凌

多目標優化問題 (Multi-objective optimization problems,MOPs) 在現實世界中廣泛存在[1].對于該類優化問題,往往需要考慮存在互斥關系的多個優化目標,并且不存在一個解能夠最優化所有優化目標.因此該類問題的最優解通常為一組互不支配的Pareto 最優解集.在工業應用和現實工程問題中,決策者經常遇到多個不同的最優解其目標函數值相同的一類問題,例如腦功能成像[2]、柴油機設計問題[3]、游戲地圖生成問題[4]等.對于Pareto 前沿上的某個目標向量,在決策空間中可以找到多個對應的決策向量.這類問題通常稱為多模態多目標優化問題[5](Multimodal multi-objective optimization problems,MMOPs).圖1 展示了一個兩目標兩決策變量的MMOP,從中可以看到,A點和B點都對應于Pareto 前沿上的P點.對于決策者來說,如果能夠獲得待優化問題的全部最優解,一方面可以更深入地了解該問題,對于刻畫問題屬性、提出改進方向、尋找最優解等具有重要作用;另一方面,一旦其中一個最優解因環境變化等因素導致不可用,決策者可以方便快速地轉變到另一個最優解.對于工業生產來說,多個最優解意味著有更多的生產方案可供選擇.在某些情況下,決策者甚至會接受目標值稍劣的解[6].例如某個解決方案要達到的加工條件較為苛刻,或者對加工精度要求極高,那么決策者將偏向于選擇對條件要求不苛刻的解而接受其目標函數值上的劣勢.因此,如何獲得MMOPs的全部最優解成為亟待解決的問題之一.

圖1 兩目標兩決策變量多模態問題示意圖 (左圖和右圖分別表示問題的決策空間和目標空間)Fig.1 Diagram of a two-objective two-decision-variable MMOP (the left figure and right figure are decision space and objective space respectively)

多目標進化算法 (Multi-objective evolutionary algorithms,MOEAs) 在求解非線性、決策類型多樣、決策空間復雜的MOPs 上的有效性已經得到了廣泛的驗證[7-8].鑒于MOEAs 在MOPs 的標準測試問題和實際工程問題上的優異性能,多種MOEAs 被拓展以用于解決MMOPs.研究者將種群多樣性保持機制與現有MOEAs 結合,以獲得問題的全部最優解集,這類算法統稱為多模態多目標進化算法 (Multimodal multi-objective evolutionary algorithms,MMEAs).但由于MMOPs 比傳統的MOPs 具有更復雜的決策空間和映射關系,目前所提出的MMEAs 在求解MMOPs 時仍存在許多困難[9],例如,如何平衡決策空間的多樣性和目標空間的收斂性,如何保留目標向量相似而決策向量相差較大的個體.

前期圍繞MMOPs 的大部分工作是獲得此類問題的多個全局最優解集,不考慮問題的局部最優解集.在火箭任務規劃問題[6]中,對于相距較遠的兩個火箭發射窗口,其空間飛行時間和有效載荷相差非常小,因此對于決策者來說,獲得這兩個不同的解具有重要意義.最新的研究也指出,在現實問題中,存在多個全局最優Pareto 區域較為罕見.更普遍的情況是,多個全局最優與局部最優區域同時存在.從另一個角度來說,多個全局最優是存在局部最優的一種特殊情況,因此,同時獲得問題的全局最優和局部最優區域更為重要[10].遺憾的是,針對此類問題的研究目前還比較少,仍處于初期階段.為了進一步提升MMEAs 在具有局部最優解集的MMOPs 上的性能,本文進行了積極的探索,創新性體現在以下幾個方面:

1) 提出了一種局部收斂性指標 (ILC).具體來說,區別于全局收斂性指標,局部收斂性指標只要求個體與它附近的個體進行對比.在進化過程中,基于局部收斂性指標可以保留問題的局部最優解.另外,該指標可以方便地嵌入到已有的MOEAs 中,從而使算法具有搜索問題局部最優Pareto 區域的能力.

2) 為了增強算法保持種群多樣性的能力,提出了一種考慮目標空間和決策空間多樣性的指標,并以此為依據,設計了一種能夠同時獲得問題的全局和局部Pareto 最優解的環境選擇策略.

3) 結合局部收斂性指標和環境選擇策略,提出了一種多模態多目標優化算法用以獲得MMOPs的全局和局部Pareto 解集.通過對比其他代表性算法在測試問題上的表現,驗證了所提算法的有效性.

本文內容安排如下:第1 節介紹多模態多目標優化的相關概念以及該類問題的求解難點;第2 節詳細介紹本文所提的局部收斂性指標以及基于該指標的多模態多目標優化算法;第3 節通過實驗對所提算法的有效性進行驗證;第 4 節對本文研究進行總結,并提出未來可能的研究方向.

1 研究背景

1.1 多目標優化問題

現實世界中的許多工程應用問題,往往需要考慮多個優化目標.通常來說,不同的目標是互相制約的,只能通過權衡來獲得令決策者滿意的解.不失一般性,MOPs[11-12]可以表示如下

其中,Ω 為問題的可行域,fm(x) 為決策向量x的第m個目標函數值.與具有單個全局最優值的單目標優化問題不同,在多目標優化問題中,存在多個非支配解,稱為Pareto 最優解集.解xA支配解xB當且僅當

一般來說,MOEAs 會給出一組互不支配的解集,稱為Pareto 最優解集 (Pareto solution set,PS),并且不存在一個解能在所有目標函數上都優于其他解.而PS 在目標空間上的映射稱為Pareto 最優前沿 (Pareto front,PF).

1.2 多模態多目標優化問題

多模態多目標優化問題可以定義[5,9]如下:

定義 1.如果一個多目標優化問題滿足以下兩個條件之一,則稱該問題為多模態多目標優化問題.

1) 問題至少有一個局部Pareto 最優解集;

2) 問題至少有兩個等效全局Pareto 最優解集,它們對應相同的PF.

定義 2.對于解集SL中的任意解x,如果不存在x的鄰居解y,其中‖x-y‖≤δ,使得yPareto支配x,那么SL稱為局部最優解集.

定義 3.對于解集SG中的任意解x,如果不存在解y,使得yPareto 支配x,那么SG稱為全局最優解集.

從定義中可以看出,MMOPs 存在兩種情況.情況1 可由圖1 簡單表示,即在決策空間中存在多個相距較遠的PS 對應于相同的PF.換句話說,在目標空間Pareto 前沿上的一個目標向量,可以在決策空間上找到距離較遠的多個最優解.情況2 可由圖2 表示,其中B點對應目標空間中的P1點,A點對應局部PF 上的P2點.在情況1 的基礎上,問題還存在一個或多個局部PF.

圖2 具有局部帕累托前沿的兩目標多模態問題 (左圖和右圖分別表示問題的決策空間和目標空間)Fig.2 A two-objective MMOP with local Pareto front (the left figure and right figure are decision space and objective space respectively)

由上述定義可知,對于MMOPs,只存在一個全局PF,而局部PF 可能有多個,且全局PF和局部PF 對應至少一個PS.圖3 展示了MMF12 問題和MMF15 問題的PF和PS.從中可以直觀地看到,MMF12 存在一個全局PF 對應于4 個等效全局PS,一個局部PF 對應于4 個等效局部PS;而MMF15則只有一個全局PS和一個局部PS.

圖3 MMF12 (左)和MMF15 (右)問題的PF和PS 示意圖Fig.3 Diagram of PF and PS for MMF12 (left) and MMF15 (right)

傳統的MOEAs 的目標是獲得一組靠近Pareto最優前沿的均勻分布的解集.這一目標包含兩個重點:1) 解集具有良好的收斂性,其目標向量接近于Pareto 前沿;2) 解集在Pareto 前沿上均勻分布.為了達成這一目標,NSGA-II 算法先后使用了兩個評價指標,即快速非支配排序和目標空間的擁擠距離.類似于NSGA-II,其他MOEAs 總是以收斂性為第一準則,輔以目標空間的均勻性選擇策略,從而獲得性能較好的解集.以圖1 為例,在利用MOEAs求解MMOPs 問題時,假設算法已經通過搜索獲得解A(對應于目標空間的點P),在新的迭代搜索中,算法得到解B′(對應于目標空間的點P′).那么,對于傳統的MOEAs 來說,P與P′在目標空間將變得 “擁擠”.由于目標空間均勻性指標的存在,P′將不會在迭代過程中得到保留,因此算法難以同時獲得解A和解B.即傳統以收斂性為第一準則的算法難以求解多模態多目標優化問題.另外,對于存在多個局部PF 的MMOPs 來說,由于MOEAs以收斂性作為第一準則,在沒有其他種群多樣性策略的輔助下,算法將迅速收斂到問題的全局PF,因此不會保留該問題的局部PF.

為了獲得MMOPs 的全部最優解集,近年來學者們提出了許多MMEAs.Omni-optimizer[13]可能是最具代表性的MMEA,它基于NSGA-II[14]引入了保持決策空間解的多樣性的策略,包括基于拉丁超立方體采樣的種群初始化方法、限制交配選擇策略和替代擁擠距離.其中,替代擁擠距離旨在評估目標空間和決策空間中解的多樣性.受此啟發,基于niching 的協方差矩陣自適應 (Covariance matrix adaptation,CMA) 方法[15]在目標和決策空間中引入了聚合距離度量,可以將解集劃分為多個niches.另外,雙niches 進化算法 (Double-niched evolutionary algorithm,DNEA)[16]和基于決策空間的niching NSGA-II (Decision space-based niching NSGA-II,DN-NSGAII)[17]是兩種基于Omnioptimizer 的增強算法,經實驗證明,這兩個算法在MMF 測試問題上表現優異.與傳統采用模擬二元交叉算子 (Simulated binary crossover,SBX) 不同,MO_PSO_MM[18]和MO_Ring_PSO_SCD[19]使用粒子群優化 (Particle swarm optimization,PSO) 算子[20]來生成新的解并在傳統MMOPs 上獲得了良好的性能.此外,差分進化 (Differential evolution,DE) 算子[21]也被用來促進決策空間的多樣性,例如MMODE[22]、DE-RLFR[23]等.然而,前期的工作為了更直觀地展示算法獲得不同PS 的能力,測試問題的決策變量通常被設計為2～3 個,并且問題的搜索難度較小,通常能夠在10～50 代內找到最優解.

最近,Liu 等[24]考慮到現有的測試問題中,搜索不同PS 時難度一樣,而在現實問題中,獲得不同區域的解集難度往往是不同的.基于此,作者提出了一種新的測試問題集IDMP (Imbalanced distance minimization benchmark problems).這個測試集的主要特點是,搜索不同的區域需要的解的評價次數不同.經過實驗,已有的算法在這類問題上表現較差,往往只能找到一個Pareto 解集.因此,該測試問題能夠更加準確地衡量算法保持多樣性和搜索不同PS 的能力.為了解決這類問題,Liu 等提出了一種基于距離的收斂性懲罰方法,并選擇每次只更新一個解的steady 策略對種群進行更新,形成了CPDEA 算法.受基于指標的進化算法 (Indicatorbased evolutionary algorithm,IBEA) 啟發,Li 等[25]提出了一種加權指標,可以衡量個體的局部收斂性.Fan 等提出了一種自適應分區搜索 (Zoning search with adaptive resource allocating,ZS-ARA)[26]策略,將整個搜索空間分成幾個子區域進行搜索,從而提高算法保持多樣性的能力.經過驗證,這些算法在IDMP 問題上表現良好.

總體來說,MMEAs 的有效性得到了廣泛的實驗驗證,但是目前的MMEAs 更多地關注于找到MMOPs 的全局最優解.在現實問題中,存在多個等效全局最優Pareto 區域往往是比較少的情況,更普遍的情況是,全局最優與局部最優同時存在.因此研究同時獲得問題的全局最優和局部最優區域更為重要.遺憾的是,針對此類問題的研究目前還比較少.其中,PQ,?-MOEA[6]是專門針對空間任務設計問題而設計的算法,其使用?-dominance[27]進行后代選擇;MMOPIO[28]基于Pareto 支配關系設計,能在一定程度上獲得局部最優解;eMOEA/D-ADA[29]是基于分解方法的算法,通過給不同參考向量分配多個個體,也具有一定的局部最優搜索和保留能力;DIOP[30]則給出一種多樣性的指標,并使用基于集合的多目標優化算法框架對問題進行求解,能夠獲得問題的局部最優解集;DNEA-L[10]則通過使用一種多前沿檔案集更新方法來獲取局部PS.但是,由于沒有系統地討論這類問題,因此在性能上仍有提升的空間.

Liang 等[31]提出了具有局部PF 的MMOPs 測試問題,并舉辦了相關的競賽.在這之后,Lin 等[32]提出了使用基于DBSCAN 的雙重聚類的方法來維持種群的多樣性,能夠獲得問題的局部最優解集.然而,由于基于密度的聚類方法在對不同的解集區域進行聚類時存在誤差,因此容易出現性能不穩定的情況.Li 等[33]則提出了一種基于分層選擇的多目標優化算法 (Hierarchy ranking method based evolutionary algorithm,HREA) 來獲取問題的全局和局部Pareto 解集.Tanabe 等[9]和岳彩通等[5]針對多模態多目標優化進行了較為詳細的綜述總結,總的來說,雖然獲取MMOPs 的全局和局部最優解具有重要意義,但是相關的算法設計仍然處于起步階段,設計一種魯棒性高、性能好的考慮局部PS 的MMEA 成為MMOPs 研究領域的前沿問題.

2 基于局部收斂性指標的多模態多目標優化

2.1 局部收斂性指標

傳統的MOEAs 更多地關注解集的收斂性,因此絕大多數算法都選擇收斂性作為第一準則進行后代個體的選擇[14].基于傳統MOEAs 設計的多模態多目標優化算法考慮了決策空間的多樣性,因此能夠獲得更多的等效PS.然而,傳統算法往往只關注獲得全局PS,從而舍棄局部PS 的搜索.為了加強算法對局部PS 的搜索能力,參考SPEA2 算法[34]中所提的元適應度值,本文提出一種局部收斂性指標,對于解xi,其局部收斂性指標計算如下

圖4 為本文所提的局部收斂性指標計算示意圖.與SPEA2 算法所提的元適應度值需要跟種群中所有的個體進行比較不同,在局部收斂性指標的計算中,個體只跟自己的鄰居解進行比較,從而提高局部最優解的收斂能力.具體來說,對于決策空間中的解A來說,其處于局部PS (圓圈區域)中.在傳統的MOEAs 中,由于全局PS (C點所在線條)的收斂性更好,因此解A和解B被解C支配,在進化過程中不會被保留.在局部收斂性指標的計算中,解A在計算支配關系時,只跟自身的鄰居解(在當前示意圖中,鄰居只有解B) 進行比較,此時解A屬于非支配解,能夠保留并順利進入下一次的進化.局部收斂性指標的計算中使用了鄰居的概念,而決策空間中鄰居解的定義是偏主觀的,需要引入參數[4].不失一般性,在本文中,稱兩個解xi和xj為鄰居,當且僅當它們的歐幾里得距離小于V,計算如下

圖4 局部收斂性指標示意圖Fig.4 Diagram of local convergence indicator

其中,D表示決策變量的個數;分別代表第d個決策變量的最大值和最小值.

2.2 算法框架

前面具體介紹了局部收斂性指標的思想以及計算過程,基于該指標,本文提出了一種基于局部收斂性指標的多模態多目標優化算法 (MMEA based on local convergence indicator,ILC-MMEA).ILC-MMEA 的算法框架由算法1 表示.與大多數MOEAs一樣,ILC-MMEA 由以下步驟組成:種群初始化,交配選擇,后代生成,環境選擇.本文引入了局部收斂性指標來搜索全局和局部的PS.并且在挑選父代個體時 (步驟 3)),使用了局部收斂性指標作為二元競爭的準則,從而加快算法的收斂速度和提升局部探索能力.具體來說,首先從當前種群Pop里隨機挑選兩個解并比較它們的局部收斂性指標值,較好的個體將被選擇;如果它們的局部收斂性指標值一致,則擁擠距離小的個體被選擇;這一過程將被重復執行,直到挑選出N個個體.之后,被挑選的父代個體將使用SBX和多項式變異 (Polynomial mutation,PM) 產生后代個體 (步驟 4)).另外,針對局部PS 的搜索問題,本文設計了一種新的環境選擇策略.

算法 1.ILC-MMEA 算法框架

2.3 環境選擇策略

在這一節中,將詳細討論基于ILC的環境選擇策略,其基本思路由算法2 表示.

算法2.環境選擇策略

首先,將種群與新生成的后代個體進行合并,并計算合并后種群的局部收斂性指標ILC(步驟 1)、步驟 2)).根據式 (3),當=0 時,表明解xi不被它的任何鄰居解支配.因此本文設計了一種二次選擇策略,具體為:當局部非支配解的個數小于種群大小N時,按照ILC的值對種群進行排序,隨后選擇前N個個體進入下一代 (步驟 4));否則,算法將首先挑選出局部非支配解,然后計算它們的擁擠距離,隨后刪除擁擠距離較大的解,從而保持新種群的大小為N(步驟 5)、步驟 6)).

ILC-MMEA 使用擁擠距離作為第二準則對種群中的個體進行挑選.一般來說,傳統的MOEAs更多地關注目標空間中解集分布的均勻性,而MMEAs 則更多地關注決策空間的均勻性[5,9],這一點可以通過圖5 對目標空間和決策空間的分布性進行說明.圖5 中左邊表示解在決策空間的分布性很好,但是在目標空間的分布性較差,對應于傳統的MMEAs;圖5 中間表示解在決策空間的分布性很差,但是在目標空間的分布性很好,對應于傳統的MOEAs;理想狀態的解分布應該如圖5 中右邊所示,即解在決策空間和目標空間的分布性都很好.為了實現這一目標,本文提出了一種改進的種群擁擠距離計算方法,具體如下

圖5 目標空間和決策空間的分布均勻性Fig.5 Distribution uniformity in the objective space and the decision space

其中,‖xj -xi‖表示xi和xj的歐氏距離,f(xi) 則代表解xi對應的目標向量歸一化之后的值.值得注意的是,在計算之前,需要對xi和xj的值進行歸一化.

新提出的擁擠距離充分考慮了解集在目標空間和決策空間的相對位置,因此可以獲得在兩個空間中分布更加均勻的解集.另外,為了更好地平衡兩個空間的差異,算法對兩個空間的向量使用了統一的歸一化策略.

2.4 算法計算復雜度分析

本節將討論ILC-MMEA 在最壞情況下的計算運行時間復雜度.對于每一代,主要執行三個步驟:交配選擇,個體交叉變異,環境選擇.假設種群大小、問題的目標數量和決策變量的數量分別為N,M,D.對于每一代,交配選擇需要 O (MN2) 的時間復雜度.采用SBX 來執行交叉操作,需要的運行時間為 O (DN). 另外,對于環境選擇,算法需要計算ILC,其時間復雜度為 O (MN2/2);而二次選擇的時間復雜度為 O (D2);因此環境選擇的總復雜度為max{O(MN2/2),O(D2)}. 那么,ILC-MMEA 算法的最終時間復雜度為 m ax{O(GMN2/2),O(GD2)},其中G表示迭代次數.通常有N＞D,因此,可以確定ILC-MMEA 的運行時間復雜度為 O (GMN2).作為比較,Two_Arch2、IBEA和NSGA-III 的運行時間復雜度分別為 m ax{O(),O(MN2)},O(N2),O(MN2)}[35].從理論分析來看,ILC-MMEA 的計算效率很高.此外,在后續實驗部分,算法的運行時間將與其他代表性MMEAs 進行比較.

3 實驗

3.1 實驗設置

3.1.1 測試問題和對比算法

為了測試ILC-MMEA 在求解傳統MMOPs和具有局部PS 的MMOPs 時的性能,本節將使用IDMP 測試集[24]和IEEE CEC 2019 MMOP 測試集[31].相比于其他的MMOPs 測試集,IDMP 測試集在搜索不同的PS 時搜索難度不同,在某種程度上來說,此類問題更能顯示出算法保持種群多樣性的能力;另外,IEEE CEC 2019 MMOP 測試集中的部分測試問題 (MMF10～MMF13,MMF15) 具有局部PS,因此被選擇用來測試所提算法獲得局部PS 的能力.

為了驗證ILC-MMEA 在解決MMOPs 中的有效性,本文選擇Omni-optimizer[13]、DN-NSGAII[16]、MO_Ring_PSO_SCD[19]、MMEA-WI[25]、CPDEA[24]、DNEA-L[10]和MMOEA/DC[32]作為對比算法.具體來說,Omni-optimizer、DN-NSGAII和MO_Ring_PSO_SCD 都是求解MMOPs 的代表性算法,其性能已經得到了廣泛驗證;MMEAWI和CPDEA 是專門為解決不平衡MMOPs 提出的算法;DNEA-L和MMOEA/DC 則是最新關注于獲得全局和局部PS 的算法.

為了保證對比的公平性,對于所有算法,設置種群大小N=100D,函數評估的最大次數設置為NF E=5 000D,其中D是決策變量的數量.此外,除了MO_Ring_PSO_SCD 采用PSO 算子,其他算法均使用SBX和PM 算子用于生成后代,其中交叉概率和變異概率分別為1和 1 /D,ηc=ηm=20.對比算法中的具體參數均按照原論文設置.所有實驗均基于PlatEMO v1.6[36],計算機配置為Intel i9-9900X @ 3.50 GHz,64 GB RAM.為方便多模態多目標相關領域研究人員的后續研究工作,本文開放了ILC-MMEA 的源代碼,相關代碼可從以下網站獲取:https://gitee.com/wenhua-li/ilcmmea.

3.1.2 性能評價指標

針對MOEAs 性能的評價指標包括超體積 (Hypervolume,HV)[37]、世代距離 (Generation distance,GD)[38]和反世代距離 (Inverted generation distance,IGD)[38]等.它們中的大多數是用來衡量解集在目標空間中接近真實Pareto 前沿的程度和解集分布的均勻程度.由于MMEAs 旨在獲得所有PS,因此還應衡量解集在決策空間中的性能.因此,在本文中采用IGDX[39]作為評價指標,以評價獲得的解集與真實PF和真實PS 的近似程度.對于一個解集X,IGDX 的計算過程可以表示如下

其中,ED(x,y) 表示解x和解y的歐氏距離,X*代表真實Pareto 集合中的均勻采樣,|X*|表示集合X*中解的總個數.IGDX 的值越小,表示解集的收斂性和均勻性越好,當IGDX 值為0 時,表示獲得的解集能完全覆蓋參考解集.

3.2 傳統MMEAs 性能對比

為了測試ILC-MMEA 在求解傳統MMOPs 時的性能,本文使用了IDMP 測試集.具體來說,相比較前期提出的MMOPs 測試問題,獲得IDMP 測試問題的全部Pareto 最優解集更加困難,因此更能夠體現出MMEAs 保持種群多樣性和獲取不同PS的能力.表1 列出了所有算法31 次獨立運行的IGDX 的平均值和方差.另外,本文使用Wilcoxon 秩和檢驗來比較ILC-MMEA 與每個對比算法的性能差異,其中顯著性水平p設置為0.05.在表1 的最后一列中,符號 “+”和 “–” 表示當前算法與ILC-MMEA 相比,能獲得更好和更差的性能的測試問題數量.此外,符號 “=” 表示該對比算法與ILC-MMEA 之間沒有顯著差異的測試問題數量.

從表1 中可以觀察到,ILC-MMEA 在所選測試問題上表現出比其他代表性算法更好的性能.具體來說,12 個測試問題中,ILC-MMEA 在8 個問題上表現出了最佳性能.此外,MMOEA/DC、MMEA-WI和CPDEA 分別在2 個、1 個和1 個測試問題上獲得了最好的IGDX 值.從表1 中可以看出,ILC-MMEA、MMOEA/DC、MMEA-WI和CPDEA 相較于其他對比算法性能更強,其在IGDX指標值上有跨越量級的領先.這是因為,CPDEA和MMEA-WI 是專門為了解決IDMP 問題提出的,考慮了搜索不同PS 時的不平衡性問題;ILC-MMEA和MMOEA/DC 則是考慮到了決策空間中存在局部PS 的情況,因此在求解PS 不平衡問題時依然能夠獲得問題的全部PS.但是,隨著目標個數的提升,只有ILC-MMEA和MMOEA/DC 能夠獲得較好的結果,其他算法均不能夠獲得問題的全部PS.雖然DN-NSGAII和Omni-optimizer 是為多模態多目標優化設計的,但似乎它們在所選基準問題上表現不佳.IDMP 測試問題在搜索不同PS 時存在不平衡,因此一般的MMEAs 很難獲得所有PS.DN-NSGAII和Omni-optimizer 是MMOPs 早期研究中的兩個代表性算法,其思想啟發了眾多針對MMOPs 的算法和相關工作,但是在IDMP 測試問題上表現較差.

表1 不同算法在IDMP 測試問題上31 次獨立運行的IGDX 平均值和方差Table 1 Mean and variance of 31 independent runs of IGDX for different algorithms on IDMP test problems

圖6 展示了所有算法在IDMPM3T4 問題上獲得的PS和PF (挑選出每個算法最接近平均IGDX值的運行結果進行展示).從圖中可以看出,ILC-MMEA和MMOEA/DC 能夠獲得所有的PS,而DNEA-L、CPDEA、MMEA-WI和MO_Ring_PSO_SCD 只能獲得其中的部分PS;DN-NSGAII和Omni-optimizer 只能獲得其中一個PS.另外,圖7展示了所有算法在具有4 個決策變量的IDMPM4T3問題上獲得的PS.可以看到,僅有考慮了局部PS的DNEA-L、ILC-MMEA和MMOEA/DC 能夠獲得全部的PS,并且ILC-MMEA和MMOEA/DC獲得的解集分布均勻性明顯更好.此外,可以明顯地看到,ILC-MMEA和MMOEA/DC 最終獲得的解集中包含了非支配解.這是因為這兩個算法都考慮了獲得問題的局部PS,因此還有少量的個體繼續在決策空間進行探索.

圖6 不同算法在IDMPM3T4 問題上獲得的PS和PFFig.6 PS and PF obtained by different algorithms on IDMPM3T4 problem

圖7 不同算法在IDMPM4T3 問題上獲得的PS (藍色實線)和真實PS (紅色虛線)Fig.7 True PS (red dotted lines) and obtained PS (blue solid lines) by different algorithms on IDMPM4T3 problem

總體來說,在IDMP 測試問題上,ILC-MMEA、MMOEA/DC、MMEA-WI和CPDEA 表現良好,而隨著目標個數和決策數量的增加,ILC-MMEA和MMOEA/DC 的性能優勢更加凸顯,且ILC-MMEA性能更佳.

3.3 考慮局部最優算法性能對比

本節展示了ILC-MMEA和對比算法在具有局部PS 的MMOPs 上的性能.具體來說,實驗挑選了IEEE CEC 2019 MMOP 中的部分測試問題,包括MMF10、MMF11、MMF12、MMF13和MMF15.為了降低隨機性帶來的影響,所有實驗均獨立執行31 次.與上一節相同,使用Wilcoxon 秩和檢驗來表示不同算法相比于ILC-MMEA 的性能好壞.

表2 列出了所有對比算法在測試問題上獲得的IGDX 的平均值和方差.從表中可以看出,在全部5 個測試問題中,ILC-MMEA 在4 個測試問題上表現出最好的性能,MMOEA/DC 在1 個測試問題上表現最好.DNEA-L、MMOEA/DC和ILC-MMEA 相比于其他算法表現更加出色 (IGDX 值更小).這是因為,這三個算法均采取了一定的策略對局部PS 進行搜索并保留.對于本節選擇的測試問題,這三個算法都能找到并保留局部PS,因此其性能表現優異.

表2 不同算法在具有局部PS 測試問題上31 次獨立運行的IGDX 平均值和方差Table 2 Mean and variance of 31 independent runs of IGDX for different algorithms on MMOPs with local PS

圖8 直觀地展示了所有算法在具有局部PS 問題上的表現.可以看到,MMOEA/DC和ILC-MMEA能夠找到問題的全局和局部PS.DNEA-L 在MMF11問題上能夠找到全局和局部PS,但是在MMF12上只能獲得部分PS,且解集分布的均勻性較差.對于早期提出的MMEAs 而言,由于算法沒有考慮局部PS 的搜索,因此無法對局部PS 進行保留.ILC-MMEA 獲得的PF 分布性更加均勻.這是因為,ILC-MMEA 引入了全新的種群擁擠度計算方式,能夠更好地平衡目標空間和決策空間分布的均勻性.在MMF12 問題上,MMOEA/DC 獲得的PF相比于ILC-MMEA 更加均勻,而PS 情況則相反.由于篇幅限制,算法在其他問題上的PF和PS 沒有全部畫出,感興趣的讀者可以在論文代碼開源地址獲得所有數據結果.總體來說,ILC-MMEA和MMOEA/DC 均能夠獲取問題的全局和局部PS,DNEA-L 能夠獲取問題的部分局部PS,且ILC-MMEA 獲得的解集分布性更好.

圖8 不同算法在MMF11 問題 (前兩行)和MMF12 問題 (后兩行) 上獲得的PS和PFFig.8 PS and PF obtained by different algorithms on MMF11 (first two rows) and MMF12 (last two rows) problems

3.4 算法運行時間對比

前文在理論上給出了ILC-MMEA 算法的計算時間復雜度,為了更加直觀地展示不同MMEAs 算法的計算耗時,本節將使用實驗的方法對時間復雜度進行分析.具體來說,將使用Multi-polygon 作為基準測試問題.該測試問題可以方便地擴展到高維,因此,設置目標函數個數M分別為3、4、8、10,D=4 ,并統一使用N=200 ,NF E=20 000 進行31 次獨立實驗,取結果的平均值進行比較.

圖9 展示了不同算法在目標個數不同的測試問題上的計算時間.可以看到,MMOEA/DC、MMEAWI和ILC-MMEA 的計算復雜度隨著目標個數的提升并沒有明顯的增大.對于DN-NSGAII和Omni-optimizer 來說,求解目標個數為4 時的優化問題所用時間甚至小于目標個數為3 時的求解時間.進一步分析可以知道,這兩個算法的計算復雜度與當前種群中非支配解占比息息相關.當目標個數增大時,算法運行前期種群中非支配解的占比較低,這導致了計算時間的下降.另外,CPDEA、DNEA-L和MO_Ring_PSO_SCD 的計算時間隨著目標個數的增大有微小增加.總體來說,ILC-MMEA 的計算時間在所有對比算法中處于中間位置,具備較好的計算效率.

圖9 不同算法在不同目標個數測試問題上的計算時間Fig.9 Computational time of different algorithms on test problems with different number of objectives

4 結論

獲得MMOPs 的全部PS 對于決策者具有重要意義.然而,由于目標空間多樣性與決策空間多樣性存在一定的沖突,因此,獲得全部PS 仍然是進化計算領域面臨的一個巨大挑戰.此外,搜索并保留決策者能接受的局部最優PS 可以認為是保留全部全局PS 的更普遍情況.這是因為,擁有多個全局最優PS 的問題是具有局部最優PS 的一個特例.研究具備搜索局部PS 能力的算法可以更好地解決MMOPs.在本文中,提出了局部收斂性指標和基于雙空間的擁擠距離,并通過實驗驗證了所提方法的有效性,說明關注問題的局部PS 可以更好地解決MMOPs.

目前,針對MMOPs 的研究大多聚焦在連續型優化上[5,9],且問題的決策空間較小 (決策變量個數較少),已有算法重點考慮了解集的分布性而沒有重視算法的搜索能力.然而實際問題的決策變量可能是多類型或大規模的.近期,CEC 會議舉辦了針對路徑規劃的多模態多目標競賽[40-41],公開了一系列測試集,研究了多模態多目標優化算法在離散型問題上的性能,取得了較多的關注.另一方面,針對多模態多目標優化算法的實際應用還比較少.這是因為,決策者難以確定待優化問題是否屬于多模態優化問題;并且,已有的MMEAs 在實際問題上的效果還有待檢驗.因此決策者更傾向于選擇傳統的MOEAs 對問題進行求解,這對理解問題的決策空間屬性造成了一定的障礙.因此,如何快速表征某個問題是否為多模態多目標優化問題是推廣此類算法的關鍵.另外,未來的研究方向將聚焦于提升多模態多目標優化算法在大規模決策變量問題上的性能以及推動多模態多目標優化算法的實際應用.