面向高維多目標優(yōu)化的雙階段雙種群進化算法

曹嘉樂，楊 磊，田井林，李華德，李康順

華南農(nóng)業(yè)大學數(shù)學與信息學院，廣州 510642

高維多目標優(yōu)化問題在現(xiàn)實世界中廣泛存在，如樓宇負荷優(yōu)化調度[1]、汽車碰撞安全設計[2]和配送中心揀貨系統(tǒng)作業(yè)[3]等。這類問題通常涉及三個或三個以上相互沖突的目標，提升其中一個目標的性能往往會導致其他目標的性能下降，因此需盡可能地優(yōu)化這些沖突的目標使得總目標達到最優(yōu)。近年來，進化算法作為一種啟發(fā)式優(yōu)化算法，因其能夠模擬自然進化過程來解決各種復雜的優(yōu)化問題而在多目標優(yōu)化領域中得到了廣泛應用。如今的高維多目標進化算法大致分為如下四類：

第一類為基于帕累托支配關系的高維多目標優(yōu)化算法。這類算法一般基于兩種策略來選擇個體：第一種策略是通過改進帕累托支配關系來選擇個體，該策略通常通過放寬帕累托支配關系，使得不可比較的解能夠進行比較，從而增強環(huán)境選擇壓力。如CSDR-Dominance[4]、GPO-Dominance[5]等。這些算法雖然能提高高維多目標優(yōu)化算法的選擇壓力，但是對參數(shù)依賴性很強，往往很難找到合適的參數(shù)。第二種策略則是通過新型的多樣性選擇標準來選擇個體，如Zhou等人[6]采用一種基于全局和局部多樣性的多樣性維護機制來管理種群的多樣性，Chen等人[7]通過多樣性排序的方法來提高種群在不同類型帕累托前沿上的多樣性。這些算法雖然在增加選擇壓力方面有效，但在平衡多樣性和收斂性方面稍有不足。

基于指標的高維多目標進化算法屬于第二類，如HyPE[8]、MaOEA-IGD[9]等。這些算法使用超體積（hypervolume，HV）[10]、反向世代距離（inverted generational distance，IGD）[11]等準確指標或估計的指標值來進行環(huán)境選擇。然而，這些算法的計算成本是非常昂貴的，并且生成的解很難保證分布的均勻性。

第三類是采用新型自定義進化框架的高維多目標優(yōu)化算法。如基于決策變量分類的DVC-MOEA[12]采用一種新型的決策變量分類方法來生成有前景的解，但是決策變量貢獻的變化可能會導致錯誤的分類，從而影響算法效能?；趦呻A段代理輔助進化算法TS-SAEA[13]通過將進化過程劃分為收斂性階段和多樣性階段，以分別提高種群的收斂性和多樣性，但是對收斂性和多樣性分別進行處理，可能無法保持收斂性與多樣性的平衡。而Two_Arch2[14]則使用收斂性種群檔案及多樣性種群檔案來指導種群的進化，該方法能夠有效地維持收斂性和多樣性的平衡，其缺點是在高維空間多樣性檔案難以更新，會導致解集的多樣性變差。

第四類則為基于分解的高維多目標進化算法，該類算法通常采用均勻分布的權重向量將一個高維多目標優(yōu)化問題分解成多個單目標子問題，然后同時對它們進行優(yōu)化。其中，MOEA/D[15]、RVEA[16]是這類算法中的一些代表性算法。相較于其他三種類型的算法，該類算法具有計算復雜度低、能夠提供良好的選擇壓力和維持多樣性簡單等優(yōu)點。然而，當處理具有不規(guī)則形狀的帕累托前沿時（例如斷開、退化、反向、約束、嚴重縮放和復雜的帕累托前沿），使用預定義均勻分布的權重向量的算法性能會受到影響[17]，無法挑選出分布均勻的解，同時還會導致權重向量的浪費。

為了有效地處理具有不規(guī)則帕累托前沿的高維多目標優(yōu)化問題，一種有效的方法是在進化過程中自適應地調整權重向量。例如，Liu等人[18]通過改進的k-均值聚類方法從種群中提取符合帕累托前沿形狀的權重向量。Zhao 等人[19]采用雙重調整策略對權重向量進行調整。Zhang 等人[20]周期性地將權重向量分組為多個子集，并將每個子集中的權重向量數(shù)量與邊界個體形成的范圍成比例，從而挑選出覆蓋范圍良好的解。

即使上述權重向量調整方法能夠一定程度上處理具有不規(guī)則帕累托前沿的高維多目標優(yōu)化問題，但是這些方法大多都只能處理具有不規(guī)則帕累托前沿的高維多目標優(yōu)化問題，在具有規(guī)則帕累托前沿的高維多目標優(yōu)化問題上表現(xiàn)較差。此外，在高維多目標優(yōu)化問題中，保持種群的收斂性是相當具有挑戰(zhàn)性的。而這些方法大多都是在預定義的權重向量的基礎上進行權重向量的調整，需要多次對權重向量進行調整，雖然能夠提高種群的多樣性，但也會導致種群的收斂性變差。最后，這些方法在對權重向量調整時所需的參數(shù)較多，在不同的問題上使用固定的參數(shù)可能難以處理具有極端不規(guī)則帕累托前沿的高維多目標優(yōu)化問題。

綜上所述，在高維多目標優(yōu)化問題上獲得具有良好收斂性與多樣性的種群是一項充滿挑戰(zhàn)性的任務，雖然基于分解的高維多目標優(yōu)化算法在該問題上表現(xiàn)出色，但是其所生成的權重向量往往會與一些帕累托前沿的形狀不匹配，從而無法有效兼顧處理具有規(guī)則和不規(guī)則帕累托前沿的高維多目標優(yōu)化問題，最終導致算法的性能下降，甚至失效。

為了有效地處理具有規(guī)則和不規(guī)則帕累托前沿的高維多目標優(yōu)化問題。本文提出了一種面向高維多目標優(yōu)化的雙階段雙種群進化算法（dual-stage dualpopulation evolutionary algorithm for many-objective optimization，MaOEA-DD）。與以往采用雙階段或雙種群挑選個體以分別提高種群的收斂性和多樣性的算法有所不同，MaOEA-DD 算法主要是通過雙階段雙種群策略對權重向量進行調整，以同時提高種群的收斂性和多樣性。具體而言，該算法將進化過程劃分為兩個階段并且使用兩個種群進行進化。在第一階段，兩個種群同時進化，其中一個種群作為輔種群，根據(jù)能量平衡的關系收集多樣性較好的個體，另一個種群作為主種群，采用基于分解的方法進行進化，當主種群達到一定穩(wěn)定狀態(tài)后，根據(jù)權重向量與其對應的主種群個體之間的夾角，判斷帕累托前沿是否規(guī)則。在第二階段，根據(jù)第一階段得到的帕累托前沿的形狀，選擇是否對權重向量進行調整，若帕累托前沿規(guī)則，則不進行調整，否則將輔種群作為主種群的權重向量指導主種群進化。其主要貢獻有如下三點：

（1）提出了一種雙階段的進化過程。在第一階段，通過權重向量與種群個體之間的角度關系判斷帕累托前沿形狀是否規(guī)則。在第二階段，根據(jù)帕累托前沿的形狀，選擇是否對權重向量進行調整，以兼顧處理具有規(guī)則和不規(guī)則帕累托前沿的高維多目標優(yōu)化問題。

（2）設計了一種雙種群權重向量調整方法。其中一個主種群由預定義權重向量指導進化，另一個輔種群則負責收集多樣性良好的個體。當需要調整權重向量時，將輔種群作為權重向量指導另一個種群的進化。該方法不依賴預定義的權重向量，僅調整一次權重向量，能夠提高種群的多樣性，同時保持種群的收斂性。

（3）本文根據(jù)自然界中多體和相互作用的物理系統(tǒng)趨向于均勻有序狀態(tài)的特性，提出了一種收集均勻分布的種群作為權重向量的方法。該挑選過程無需額外參數(shù)，挑選的權重向量能夠有效處理具有不規(guī)則帕累托前沿的多目標優(yōu)化問題。

1 相關背景

定義1（高維多目標優(yōu)化問題）以最小化高維多目標優(yōu)化問題為例，其數(shù)學模型使用如下公式描述：

其中x=(x1,x2,…,xn)T是決策空間Ω中一個n維的決策向量，m≥3 是目標數(shù)量，F(xiàn)(x)是m維的目標向量。

定義2（帕累托支配關系）給定兩個決策向量xa和xb，如果xa帕累托支配xb(xa?xb)，則其對應的目標值必有：f(xa)i≤f(xb)i,?i∈{}1,2,…,m ,且f(xa)i ＜f(xb)i,?i∈{1,2,…,m}。

定義3（帕累托最優(yōu)解）當一個解不被任何一個解支配時，則稱這個解為非支配解或帕累托最優(yōu)解。

定義4（帕累托最優(yōu)集Pareto optimal set，PS）指的是一個包含所有非支配解或帕累托最優(yōu)解的集合。

定義5（帕累托最優(yōu)前沿Pareto optimal front，PF）指的是在目標空間中由PS映射而成的圖形。

定義6（權重向量）一組用于衡量不同目標之間重要性的向量，通常預定義權重向量由如下公式產(chǎn)生：

其中，n是權重向量個數(shù)，m是目標數(shù)，C 是組合數(shù)，p是每一個坐標軸的分區(qū)數(shù)，λ是權重向量的集合。

2 MaOEA-DD算法

2.1 雙階段進化過程

采用一組預定義均勻分布權重向量的基于分解的高維多目標進化算法可以有效地處理具有規(guī)則PF的高維多目標優(yōu)化問題，而無法處理具有不規(guī)則PF 的問題。采用動態(tài)調整權重向量的基于分解的高維多目標進化算法則相反。為兼顧兩者，本文將進化過程分為兩階段：

第一階段確定PF形狀：在初始狀態(tài)下，種群呈現(xiàn)混亂無序的特征，無法準確判斷PF的形狀，因此本文首先采用預定義均勻分布的權重向量指導種群進化，直至種群處于穩(wěn)定有序的狀態(tài)。而在本文中判斷種群是否達到穩(wěn)定有序狀態(tài)的計算公式如下：

其中，f(xi)k是種群中第i個體的第k個目標值，MD代表種群中所有個體到坐標原點的曼哈頓距離。在最小化問題中，較小的MD值意味著個體離坐標原點越近，即個體越接近PF，收斂性越好[21]。因此，MD值能夠一定程度上代表種群的狀態(tài)。在本文中，如果相鄰幾代種群的MD值變化小于10-6即Δ ＜10-6，則認為該種群的收斂性已經(jīng)不再變化，即達到種群達到穩(wěn)定狀態(tài)。

在確定種群達到穩(wěn)定狀態(tài)后，本文通過判斷預定義權重向量與其指導的個體之間是否存在夾角來確定當前PF的形狀。由于在不規(guī)則的PF上，預定義的權重向量沒有考慮到PF 的形狀，只考慮了兩兩權重向量之間的等距離關系。因此，由這些權重向量指導進化的個體無法完全分布在這些權重向量上，只能盡可能靠近它們，并與它們成一定角度。圖1（a）展示了這種情況，在圖中，權重向量w3與斷開的PF 并沒有交點，這使得由其指導進化的個體x3無法與由邊界附近權重向量w4指導的個體x4保持均勻的間隙，只能分布在盡可能接近w3的PF邊界上，即x3與w3會存在一定的角度。而在規(guī)則的PF 上，每個個體都能均勻分布在指導其進化的權重向量上。如圖1（b）所示，每個權重向量與PF 都有交點，與其指導的個體之間不存在夾角，每個個體都分布在對應的權重向量上，即均勻地分布在PF 上。因此，在本文中，將權重向量與其指導的個體存在角度的PF判定為不規(guī)則PF，否則為規(guī)則PF。

圖1 在不同形狀的PF上個體與權重向量的關系Fig.1 Relationship between individuals and weight vector on PF of different shapes

需要注意的是，在本文中是通過計算權重向量與其夾角最小的個體來粗略確定當前權重向量指導的個體，因為通常情況下，由當前權重向量指導的個體是與該權重向量距離最近的個體。然而，在進化過程中，即使在規(guī)則PF 上，個體與權重向量之間的角度也可能不為零度，而是存在微小角度。因此，本文以10-6作為邊界值，當兩者角度差小于10-6時，說明兩者無夾角，否則存在夾角。此外，文中權重向量指導的個體與該權重向量之間的夾角指的是被指導個體和坐標原點構成的向量與對應權重向量之間的角度，如x3與坐標原點構成的向量v1與w3的角度θ1。

第二階段調整權重向量：在第一階段確定PF 形狀后，在第二階段則根據(jù)PF 的形狀進行權重向量的調整。如果PF是不規(guī)則的，則進行權重向量調整，以確保種群在不規(guī)則PF上均勻分布。而如果PF是規(guī)則的，則不調整權重向量，以保持預定義權重向量在規(guī)則PF 上的優(yōu)勢。

具體而言，MaOEA-DD 雙階段進化過程的主要目的是通過第一階段判斷PF 的形狀，然后在第二階段選擇是否對權重向量進行調整，以綜合應對處理具有規(guī)則PF 和不規(guī)則PF 的高維多目標優(yōu)化問題，與以往的雙階段多目標進化算法在不同階段分別側重于收集收斂性與多樣性良好的個體的目的有所不同。同時在MaOEA-DD中階段轉換是依據(jù)種群收斂性的穩(wěn)定性和權重向量與種群之間的關系這兩個條件進行的，并不是依據(jù)種群的收斂性與多樣性之間的關系進行的。此外，在MaOEA-DD的第一階段中提出了一種根據(jù)權重向量指導的個體與PF 的夾角判斷PF 形狀的方法，在第二階段對具有規(guī)則PF的問題和具有不規(guī)則PF的問題進行了不同的處理。

2.2 雙種群權重向量調整

目前已有的權重向量調整方法大多數(shù)是權重向量的調整與種群進化同時進行，每次調整權重向量后，種群需根據(jù)新的權重向量重新進化。雖然提高了種群的分布但也嚴重降低了種群收斂速度，使得種群的收斂性變差。為解決此問題，本研究提出了一種使用雙種群調整權重向量的方法。其中，一個種群稱為主種群，使用預定義權重向量指導進化；另一個種群稱為輔種群，其在進化過程中收集多樣性良好的個體。這兩個種群相互獨立且無關。輔種群主要收集的是多樣性良好的種群個體，并不受PF形狀的影響，而主種群是通過權重向量指導進化的，多樣性受PF形狀影響，但是能夠保持良好的收斂性，因此其收斂性優(yōu)于輔種群但多樣性差于輔種群。當種群收斂性穩(wěn)定后將輔種群作為主種群的權重向量，此后便不再調整權重向量，這不僅提升了主種群在不規(guī)則PF上的多樣性而且也能夠保持主種群的收斂性。將輔種群轉化為權重向量的具體公式如下：

其中，λi表示第i個參考向量，f(xi)m是種群中第i個體的第m個目標值，max(f(xi))表示第i個體的最大目標值。通過該公式能夠將輔種群的目標值范圍限定在0到1，以符合權重向量的規(guī)范。

總而言之，MaOEA-DD 雙種群策略的目的是收集一個多樣性良好的輔種群作為權重向量，以提高主種群的多樣性。而大多數(shù)已有的雙種群多目標進化算法的目的是使用一個種群收集收斂性良好的個體，另一個種群收集多樣性良好的個體，然后綜合挑選收斂性與多樣性良好的個體。此外，MaOEA-DD 的兩個種群采用了不同的進化框架進行進化，結合了不同進化框架的優(yōu)點，主種群采用了基于分解的進化框架，而輔種群采用基于帕累托支配的進化框架進行，接下來的章節(jié)將會對此進行詳細介紹。最后，通常權重向量是通過公式（2）計算獲得的，而在MaOEA-DD中則是通過公式（4）將輔種群轉化成權重向量獲得的。

2.3 多樣性良好的輔種群獲取

高維多目標優(yōu)化問題中的PF 是一個高維超曲面，這使得收集均勻分布的種群成為了一項艱巨的任務。為此本文使用了一種稱為Riesz s-Energy[22]的勢能在不規(guī)則PF上收集多樣性良好的種群。其原理是自然界中多體和相互作用的物理系統(tǒng)最終會趨向于最小總勢能的均勻有序狀態(tài)。由于物體間勢能與距離成反比，因此系統(tǒng)總勢能較大時，系統(tǒng)中的物體會迅速擴散以降低勢能。當系統(tǒng)中的物體間距離相等時，系統(tǒng)總勢能達到最小值，此時系統(tǒng)中的物體停止運動。具體地，Riesz s-energy數(shù)學定義如下：

其中，E代表所有點的能量總和，這里的能量用兩點之間的歐式距離表示，距離越大，能量越小則點越均勻?！?·‖表示歐式距離，n是點的數(shù)量，yi和yj分別代表點集R的第i、j個點，m是目標數(shù)。

由于歐式距離在高維空間中不適用[23]，所以文中兩個個體之間的距離是通過計算它們對應的目標值之間的曼哈頓距離獲得的。因此，在本文中的Riesz s-energy被定義為如下所示：

其中，xk表示第k個個體的決策向量，fi(xk)表示第k個個體的第i目標值，|·| 表示兩者之間的絕對值。

盡管Riesz s-energy在保持點集均勻性方面表現(xiàn)良好，但在多目標優(yōu)化中，種群分布需要同時滿足均勻性和符合PF 形狀（帕累托支配關系）。因此，本文在帕累托支配關系下使用Riesz s-energy。具體挑選過程如下：假設輔種群大小為N，在每次進化過程中，使用輔種群生成N個子代。從該子代和輔種群組成的2N個體集合中，選擇符合帕累托支配關系且具有最小Riesz s-energy 的N個個體作為下一代輔種群。然而，從2N個個體中挑選N個符合要求的個體的時間復雜度很高。因此，在文中首先對子代和輔種群共2N個個體進行非支配排序。然后，從排名前N的個體中選取N個個體。如果有多個個體排名相同且導致前N名個體數(shù)量超過N，則從這些個體中選擇與當前已選個體構成的種群的Riesz s-energy 最小的個體，直到選擇的個體數(shù)達到N為止。這種選擇方法類似于貪心算法，但可能不夠準確。為了提高選擇結果的準確性，完成上述選擇后，逐一使用排名前N且未被選擇的個體替換與其排名相同且已被選擇的個體。如果種群的Riesz s-energy變小，則同意替換。重復此步驟，直到所有排名相同且未被選擇的個體都被操作。此外，計算Riesz s-energy需重復計算兩點距離。為降低計算時間復雜度，本文使用矩陣記錄已計算的距離。

以上方法挑選的種群符合PF形狀且均勻分布。雖然該種群的收斂性可能不佳，但將其用作主種群的權重向量指導主種群在不規(guī)則PF 上的進化方向，能夠提升主種群的多樣性。

2.4 算法主流程

MaOEA-DD算法處理高維多目標優(yōu)化問題的主要流程與基于分解的高維多目標進化算法類似。然而MaOEA-DD 將進化過程劃分為了兩個階段，并采用了兩個種群進行進化，同時還對權重向量進行了調整。其算法流程圖如圖2所示，具體步驟如下：

圖2 MaOEA-DD算法主流程Fig.2 Main process of MaOEA-DD algorithm

輸入：

步驟1一個高維多目標優(yōu)化問題，種群規(guī)模N，最大迭代次數(shù)tmax。

初始化：

步驟2生成大小為N的主種群和輔種群，并創(chuàng)建N個預定義的權重向量。

第一階段：

步驟3對主種群進行交叉變異，產(chǎn)生N個子代。

步驟4對輔種群進行交叉變異，產(chǎn)生N個子代。

步驟5由權重向量的指導下從主種群及其子代中挑選N個個體作為下一代主種群。

步驟6對輔種群及其子代共2N個個體進行非支配排序，挑選排名靠前且具有最小Riesz s-energy 的N個個體作為下一代輔種群。

步驟7判斷是否達到最大迭代次數(shù)tmax，是則執(zhí)行步驟12，否則繼續(xù)進行下一步。

步驟8判斷當前是否處于第一階段，是則進行下一步，否則依次執(zhí)行步驟3、5、7。

步驟9判斷主種群是否達到穩(wěn)定狀態(tài)，如果未達到穩(wěn)定狀態(tài)，則返回步驟3。否則，通過權重向量與其指導的個體之間的夾角來判斷PF的形狀。

第二階段：

步驟10如果第一階段判斷的PF形狀是規(guī)則的，則不對權重向量進行調整，否則使用輔種群作為主種群的權重向量。

步驟11依次執(zhí)行步驟3、5、7。

輸出：

步驟12輸出大小為N的主種群。

2.5 算法時間復雜度

針對具有m個目標的高維多目標優(yōu)化問題，主種群采用了基于分解的高維多目標進化框架進行進化。其時間復雜度為O(mNT)，其中N是種群大小，T是相鄰權重向量的數(shù)量，且T ＜N。對于輔種群，比較父代與子代的支配關系以及Riesz s-energy大小的時間復雜度為O(N3m)，而計算Riesz s-energy 的時間復雜度為O(N2m)。因此，輔種群每一代進化所需時間復雜度為O(N3m)。綜上，MaOEA-DD 的總體時間復雜度為O(mNT+N3m)=O(N3m)。

3 實驗驗證

3.1 實驗設置

3.1.1 測試問題及對比算法

為了驗證本文所提出的算法在處理不同目標下的高維多目標優(yōu)化問題時的性能，本文選擇了在3、5、10 目標下的DTLZ2、DTLZ3、DTLZ5、DTLZ6、DTLZ7、W-FG4、WFG5、MAF1、MAF2、MAF3、MAF6、MAF7、IDTLZ1、IDTLZ2[24-27]共14 個測試問題來進行了實驗。這組測試問題覆蓋了多種高維多目標優(yōu)化問題類型，包括但不限于多模態(tài)、欺騙性、難以收斂、凹形、凸形、線性、退化、不連續(xù)以及具有嚴重擴展PF的問題。這些測試問題的具體介紹如表1 所示。同時，本文選取來自3種不同類型的4個算法作為對比算法，這些算法分別為基于帕累托支配關系的KnEA[28]，基于指標的MaOEAIGD[9]，基于分解且采用預定義權重向量的M-OEA/D[15]，基于分解且采用了權重向量調整的VaEA[29]。

表1 測試問題Table 1 Test problems

3.1.2 參數(shù)設置

交叉和變異算子：實驗中的所有算法使用的交叉算子和變異算子分別為模擬二元交叉（simulated binary crossover，SBX）[30]和多項式變異（polynomial mutation，PM）[31]。其中SBX 的交叉概率設置為1，分布指數(shù)設置為20。PM 的突變變量數(shù)量的期望值設置為1，分布指數(shù)設置為20。

種群大小、停機條件及運行次數(shù)：為了確保公平比較，在不同目標下種群的大小需要同參考點數(shù)量相同，表2展示了本文在不同目標下的種群大小。此外，在不同目標下每個算法運行的停機條件是達到對應的最大迭代次數(shù)，如表2 所示。為了確保實驗結果的可靠性，每個實驗算法在每個目標下的每個測試問題上都獨立運行30次后取其結果的平均值及方差。

表2 不同目標數(shù)下的種群大小與最大迭代次數(shù)Table 2 Population size and maximum number of iterations for different target numbers

顯著性檢驗：本文采用Wilcoxon 秩和檢驗[32]，顯著性水平為0.05，對實驗結果進行統(tǒng)計和分析。信號“+”“-”和“=”分別表示比較算法的結果顯著優(yōu)于、顯著低于或沒有顯著差異于MaOEA-DD的結果。

MaOEA-DD 參數(shù)設置：MaOEA-DD 采用了基于分解的進化框架，需要在分解時對相鄰的權重向量數(shù)T進行設置，T會對算法的收斂速度產(chǎn)生影響，由于本文在分解中采用的方法與MOEA/D 一致，因此按照MOEA/D的相關說明將T設為10。此外，MaOEA-DD在種群穩(wěn)定性判斷中，是通過判斷相鄰n代個體之間MD值不變來確定種群穩(wěn)定性的，這里的n文中設置為2。通常情況MD值一代未變，則能夠說明種群處于穩(wěn)定狀態(tài)，但是在一些具有欺騙性的問題上將n設置為1可能會出現(xiàn)局部最優(yōu)的情況，從而錯誤判斷種群的穩(wěn)定性，在實驗中發(fā)現(xiàn)設置為2 有助于避免這種情況的發(fā)生，且該值不宜設置過大，因為這會使得算法一直判斷種群處于不穩(wěn)定狀態(tài)。

3.1.3 評價指標

本文采用IGD[11]作為評估不同算法綜合性能的指標。該指標是通過計算真實PF上每個參考點到由高維多目標進化算法得出的近似PF上距離最近解的平均距離來近似評估最終解的收斂性和多樣性。IGD 的值越小，則說明算法的綜合性能越好，即收斂性與多樣性越好。IGD數(shù)學表達式如下：

其中，Ptrue代表從真實PF 中獲取的參考點，Pknow代表通過多目標進化算法得到的最終解集，p表示來自Ptrue的解，q表示來自Pknow的解。‖p-q‖表示p和q之間的歐氏距離，|Ptrue|表示真實PF參考點的數(shù)量。

此外，由于種群的多樣性包含種群的分布廣泛性及分布均勻性，因此，本文還采用了廣泛性（spread）[33]和間距（spacing）[33]來對這兩方面進行評估，從而評估不同算法獲得的種群的多樣性。具體說明如下：

Spread 是通過判斷極端解與非支配邊界解及非支配連續(xù)解之間的關系來評估種群分布的廣泛程度。其數(shù)學定義如下：

其中，n表示種群大小，m表示目標個數(shù)，di表示所獲得的非支配解中相鄰解的距離，是di的平均值，是極端解與第k個邊界解之間的距離。

Spacing是通過計算解之間的最小距離的標準差來確定種群的分布均勻性，該值越小種群分布越均勻。其數(shù)學定義如下：

其中，n表示種群大小，di表示第i個解到種群中其他解的最小距離，dˉ指的是所有di的均值。

由于在現(xiàn)實問題中，無法提前得知真實PF，從而無法使用與真實PF相關的指標來評估算法的性能，因此，本文采用HV[10]來評估不同算法在現(xiàn)實應用中的綜合性能。HV是通過計算非支配解集和參考點包圍的空間的超體積值來評估多目標優(yōu)化算法的性能。其值越大則表示算法性能越好。其計算公式如下：

其中，λ表示勒貝格測度，vi代表由參考點與第i個非支配解構成的超體積，S代表非支配解集。

3.2 實驗結果與分析

3.2.1 MaOEA-DD的總體性能

為了驗證MaOEA-DD 在處理高維多目標優(yōu)化問題時的有效性，本小節(jié)采用IGD 作為評價指標，將MaOEA-DD 與一些著名的算法進行了實驗對比，實驗結果如表3所示。由表3中給出的所有實驗算法在不同測試問題上的IGD平均值及標準差可知，在絕大多數(shù)測試問題中，MaOEA-DD獲得了最佳IGD值，相比其他競爭算法具有明顯的優(yōu)勢。具體介紹如下：

表3 所有實驗算法在不同測試問題上的IGD值Table 3 IGD values of all experimental algorithms on different test problems

在處理DTLZ2、IDTLZ2、MAF1等難以維持種群多樣性的問題上，由于MaOEA-DD 在面對具有規(guī)則形狀及不規(guī)則形狀的PF問題上分別采用了均勻分布的權重向量及輔種群作為的權重向量，因此其IGD值取得了總體最優(yōu)的結果的，即使其IGD 在MAF1 的5 維、10 維稍遜于或等于KnEA和VaEA，但明顯優(yōu)于其他算法。

為了更直觀地展示這一結果，圖3 和圖4 分別展示了各個算法在3 維DTLZ2 和IDTLZ2 上獲得的最終種群的分布情況。

圖3 所有實驗算法在3維DTLZ2上獲得的最終種群的分布Fig.3 Distribution of final population obtained by all experimental algorithms on 3-dimensional DTLZ2 problem

圖4 所有實驗算法在3維IDTLZ2上獲得的最終種群的分布Fig.4 Distribution of final population obtained by all experimental algorithms on 3-dimensional IDTLZ2 problem

在圖3 具有規(guī)則PF 的DTLZ2 問題上，KnEA 和MaOEA-IGD獲得的種群分布在PF四周，中間位置分布稀疏，甚至沒有。由于MOEA/D 也是采用預定均勻分布的權重向量指導種群的進化，因此它與MaOEA-DD在DTLZ2問題上分布一致，都分布得非常均勻。VaEA在規(guī)則的PF 上對權重向量進行了調整，因此其獲得的種群在PF頂端分布的較為密集，均勻性略差于MaOEA-DD與MOEA/D。

而在圖4具有不規(guī)則PF的IDTLZ2上，MaOEA-DD獲得的種群分布在PF 上的各個位置，并且間隔較為均勻，而其他算法獲得的種群分布較為密集。

對于DTLZ3、MAF2、MAF3、IDTLZ1等難以收斂的問題，MaOEA-DD 表現(xiàn)最佳。這歸因于MaOEA-DD 采用了基于分解的進化策略，并且避免了選擇壓力的存在，從而能夠有效地收斂到PF。因此，同樣采用基于分解的進化策略的MOEA/D 和VaEA 也能夠有效地收斂到PF。然而，由于MOEA/D和VaEA的權重向量在不同層面上并不如MaOEA-DD 的均勻，它們的IGD 值差于MaOEA-DD。另一方面，對于基于帕累托支配策略的KnEA，其IGD 較差的原因是在高維空間中選擇壓力不足，因此難以收斂到PF。而對于基于指標的MaOEA-IGD雖然其能夠有效地收斂到PF，但是它也存在著基于指標的多目標進化算法的通病，即難以維持多樣性，因此其IGD值也較差。

在DTLZ5、DTLZ6、DTLZ7、MAF6、MAF7 等具有復雜PF 的高維多目標優(yōu)化問題上，MaOEA-DD 同樣展現(xiàn)出了最佳性能，這是因為MaOEA-DD 引入了自然界中能量平衡的概念，以此收集了多樣性良好的種群作為權重向量，從而能夠有效地維持種群的多樣性。

從圖5可以直觀觀察到在10維MAF6問題上，所有實驗算法得到的最終種群的分布情況。MaOEA-DD能夠有效地收斂到PF，同時種群個體分布均勻且符合PF形狀。相比之下，KnEA和VaEA無法收斂到PF，原因可能是KnEA 在高維空間失去了選擇壓力，而VaEA 則是因為過度調整權重向量，降低了算法的收斂性。而對于MaOEA-IGD 和MOEA/D 雖然能夠收斂到PF，但是由PF過于復雜無法維持種群的多樣性。

圖5 所有實驗算法在10維MAF6上獲得的最終種群的分布Fig.5 Distribution of final population obtained by all experimental algorithms on 10-dimensional MAF6 problem

最后，在具有多模態(tài)特性的WFG4和具有欺騙性特征的WFG5 上，MaOEA-DD 取得了最佳的IGD 值。如圖6 所示，MaOEA-DD 獲得了良好的種群多樣性，而KnEA和VaEA獲得的種群只是在分布的廣泛程度上表現(xiàn)較好，種群個體之間的間隔并不均勻，存在許多空白區(qū)域。相比之下，MaOEA-IGD與MOEA/D則是因為沒有有效處理具有多模態(tài)特性的問題方法，因此它們獲得的種群分布密集，容易匯聚到一點上。

圖6 所有實驗算法在10維WFG4上獲得的最終種群的分布Fig.6 Distribution of final population obtained by all experimental algorithms on 10-dimensional WFG4 problem

至此，這些結果已經(jīng)證實了MaOEA-DD 對多種高維多目標優(yōu)化問題上的有效性。

3.2.2 權重向量調整方法的有效性驗證

為了評估本文提出的權重向量調整方法在規(guī)則和不規(guī)則PF 上是否能夠獲得分布性良好的解，本小節(jié)采用Spacing以及Spread作為評價指標，將MaOEA-DD與同樣采用權重向量調整方法的VaEA進行了實驗比較，實驗結果見表4。

表4 所有實驗算法在不同測試問題上的Spacing和Spread值Table 4 Spacing and Spread values of all experimental algorithms on different test problems

根據(jù)表4 中給出的所有實驗算法在不同測試問題上獲得的Spacing 和Spread 的平均值及標準差，可得出MaOEA-DD 在Spacing 以及Spread 指標上均表現(xiàn)出最佳結果。具體說明如下：

規(guī)則PF：在DTLZ2、DTLZ3、MAF3 等具有規(guī)則PF的測試問題中，MaOEA-DD 的Spacing和Spread值幾乎全優(yōu)于VaEA，這意味著MaOEA-DD獲得的種群在分布的均勻性與廣泛性幾乎全優(yōu)于VaEA，即MaOEA-DD獲得的種群多樣性更優(yōu)。這歸因于MaOEA-DD的雙階段進化過程，使其在第一階段中準確地判斷了PF 的形狀是規(guī)則的，因此其并未對權重向量進行調整，從而保持了預定均勻分布的權重向量能夠在處理具有規(guī)則PF的問題上獲得良好多樣性的優(yōu)點。而VaEA 在規(guī)則的PF上對權重向量進行了調整，因此導致了其在規(guī)則PF 上的獲得的解的多樣性要差于MaOEA-D。

不規(guī)則PF：在DTLZ6、DTLZ7、WFG4、WFG5、MA-F3、MAF2、MAF6、MAF7、IDTLZ1、IDTLZ2 等具有不規(guī)則PF的問題上，MaOEA-DD的Spacing和Spread值分別取得25 個和18 個最優(yōu)結果，而VaEA 的Spacing 和Spread值僅分別取得4個和12個最優(yōu)結果?？芍狹aOEA-DD的Spacing 最優(yōu)結果個數(shù)遠多于VaEA，即MaOEA-DD獲得的種群在分布均勻性上優(yōu)于VaEA獲得的種群。這是因為MaOEA-DD 采用Riesz s-Energy 收集的種群作為的權重向量，可以獲得分布更均勻的效果。而VaEA采用的是最大向量角原則收集的權重向量，該原則在凸問題等復雜問題中，存在著兩兩個體之間角度均勻并不代表它們之間的距離也均勻的問題，因此VaEA獲得的種群均勻性會較差。對于MaOEA-DD的Spread最優(yōu)結果個數(shù)僅比VaEA 的Spread 最優(yōu)結果個數(shù)多6 個，這是因為種群分布的廣泛程度會受種群收斂性的影響。如在圖5 的10 維MAF6 問題上，VaEA 獲得的種群并未收斂，因此其分布廣泛程度必然會遠優(yōu)于MaOEA-DD，但這并不能說明在收斂的情況下MaOEA-DD的廣泛程度不如VaEA。類似的情況也出現(xiàn)在DTLZ5 和DTLZ6上。即便不考慮這些情況，MaOEA-DD 獲得的種群的分布廣泛程度仍優(yōu)于VaEA。綜上所述，MaOEA-DD獲得的種群分布的均勻性及廣泛程度均優(yōu)于VaEA，即MaOEA-DD獲得的種群多樣性優(yōu)于VaEA。

MaOEA-DD獲得的種群不僅在具有規(guī)則PF的高維多目標優(yōu)化問題上多樣性優(yōu)于VaEA，并且在具有不規(guī)則PF的高維多目標優(yōu)化問題上多樣性也優(yōu)于VaEA，這說明了本文所提出的權重向量調整方法比VaEA所采用的權重向量調整方法更有效，能夠同時處理具有規(guī)則PF和不規(guī)則PF的高維多目標優(yōu)化問題。

3.2.3 收斂速度分析

為探究MaOEA-DD與其他對比算法在收斂速度方面的差異，本小節(jié)記錄了不同算法在不同測試問題下隨著迭代次數(shù)增加，其IGD 值的變化情況。

具體變化見圖7，說明如下：

圖7 5種算法在10維DTLZ2、DTLZ3、MAF6和IDTLZ2上IGD值的變化Fig.7 Variation of IGD values of 5 algorithms on 10-dimensional DTLZ2，DTLZ3，MAF6，and IDTLZ2

規(guī)則PF：如圖7（a）所示，在較易收斂且具有規(guī)則PF 的DTLZ2 問題上MaOEA-DD 與MOEA/D 均在迭代3 000次左右收斂，這是因為MaOEA-DD在雙階段進化過程中將DTLZ2問題識別為具有規(guī)則PF 的問題，采用了預定義的權重向量進化，因此MaOEA-DD與MOEA/D的收斂速度相同，同理在圖7（b）較難收斂且具有規(guī)則PF 的DTLZ3 問題上MaOEA-DD 與MOEA/D 的收斂速度也相同，在迭代1 000 次左右收斂。而KnEA 雖然在DTLZ3 中IGD 變化幅度較大，但其收斂速度在DTLZ2和DTLZ3 都是最快的。對于MaOEA-IGD 其收斂速度僅次于KnEA，無論在DTLZ2還是DTLZ3均在迭代500次左右收斂。由于VaEA在進化過程中頻繁調整權重向量因此其收斂速度最慢。因此在規(guī)則PF 上所有算法的收斂速度排名為KnEA>MaOEA-IGD>MaOEA-DD=MOEA/D>VaEA。

不規(guī)則PF：如圖7所示不論是在難收斂且具有不規(guī)則PF的MAF6問題上還是在較易收斂且具有不規(guī)則PF的IDTLZ2 問題上MaOEA-IGD 的收斂速度都是最快的。如圖7（c）所示，MOEA/D收斂速度僅次于MaOEAIGD，而KnEA 雖然IGD 變化幅度較大，但是其值在迭代200 次左右在固定的范圍擺動，其收斂速度快于MaOEA-DD。MaOEA-DD 在迭代350 次左右收斂，速度優(yōu)于VaEA，但是因為MaOEA-DD對權重向量進行了調整因此收斂速度慢于MOEA/D。對于VaEA，其收斂速度最慢，在迭代4 000 次時才取得最小值。而在圖7（d）較易收斂且具有不規(guī)則PF 的IDTLZ2 問題上VaEA收斂速度僅次于MaOEA-IGD。雖然KnEA 在迭代100次后IGD 值在浮動，但是其浮動幅度較小，因此KnEA收斂速度在IDTLZ2 上排名第三。即便MOEA/D 與MaOEA-DD都在迭代4 000次后取得最小IGD值，但是MOEA/D的IGD值變化幅度較小，所以其收斂速度快于MaOEA-DD。因此，在不規(guī)則PF 上算法收斂速度排名為MaOEA-IGD>MOEA/D=KnEA>VaEA>MaOEA-DD。

綜上所述，所有實驗算法在具有規(guī)則及不規(guī)則PF的問題上綜合收斂速度排名為MaOEA-IGD≥KnEA>MOEA/D>VaEA≥MaOEA-DD。需要注意的是，這只是對所有實驗算法的收斂速度粗略的排名，具體每個算法的收斂速度需要根據(jù)實際問題進行判斷。雖然MaOEA-DD 的收斂速度較慢，但其收斂性最優(yōu)。因此其在解決高維多目標優(yōu)化問題中仍有著競爭優(yōu)勢。

3.2.4 汽車碰撞安全設計優(yōu)化

為了驗證MaOEA-DD在現(xiàn)實世界優(yōu)化問題中的實用性，本小節(jié)將MaOEA-DD 與其他對比算法分別應用在汽車碰撞安全設計優(yōu)化問題[34]上。該問題的主要目的是通過對汽車結構進行優(yōu)化，以滿足碰撞安全性標準。為確保汽車滿足碰撞安全性標準，需要對汽車結構的重量、加速度特性和腳板侵入這三個目標進行優(yōu)化，其中這三個目標相互沖突并且需要同時最小化，是一個高維多目標優(yōu)化問題。在對該問題應用實驗算法進行優(yōu)化時，種群大小統(tǒng)一設置為91，迭代次數(shù)設置為1 500，并且每個算法在該問題上獨立運行30 次取平均HV 值作為實驗結果。實驗結果如表5 所示。在汽車碰撞安全設計優(yōu)化中，MaOEA-DD 獲得了最優(yōu)的HV 值，雖然VaEA 獲得的HV 值與MaOEA-DD 相近，但是隨著目標數(shù)的增加，PF 越來越復雜，MaOEA-DD 與VaEA 的差距可能會逐漸增大。KnEA 的性能雖然不如MaOEA-DD和VaEA，但優(yōu)于其他算法。對于MOEA/D，由于其采用了固定的權重向量進行進化，因此其性能遠不如MaOEA-DD，這也驗證了本文權重向量調整方法的有效性。由于MaOEA-IGD難以保持種群的多樣性，其性能最差。由此可得，MaOEA-DD 在現(xiàn)實優(yōu)化問題中具有一定的實用性。

表5 所有算法在汽車碰撞安全設計優(yōu)化中獲得的HV值Table 5 HV values obtained from all algorithms in optimization of crash safety design for vehicles

4 結束語

為了在具有規(guī)則和不規(guī)則帕累托前沿的高維多目標優(yōu)化問題中獲得收斂性和多樣性良好的種群，本文提出了一種面向高維多目標優(yōu)化的雙階段雙種群進化算法。該算法將進化過程劃分為兩個階段，以同時考慮種群在具有規(guī)則和不規(guī)則帕累托前沿的問題上的多樣性。在處理具有不規(guī)則帕累托前沿的問題時，該算法使用了一個輔種群收集多樣性良好的個體作為權重向量，一個主種群正常進化，避免了在權重向量調整時主種群的收斂性下降。此外，該算法還借鑒自然界中能量平衡的概念來選擇多樣性良好的輔種群作為權重向量。為了驗證該算法的性能，將該算法與其他4個著名的算法進行了實驗對比，實驗結果表明，本文算法能夠有效地處理不同類型的高維多目標優(yōu)化問題。此外，本文提出的權重向量調整方法在與其他權重向量調整方法進行的實驗對比中也被證實是有效的。然而，本文算法獲得的種群在不連續(xù)的帕累托前沿上的分布廣泛性并沒有達到最優(yōu)。針對該問題，下一步將設計一種保護邊界解的方法以提高種群的分布廣泛性。