華一村，劉奇奇，郝礦榮，金耀初,

(1.東華大學 信息科學與技術學院，上海 201620； 2.薩里大學 計算機科學系，英國 薩里 GU2 7XH)

0 引言

現(xiàn)實中多目標優(yōu)化問題[1]的Pareto前沿面往往是不連續(xù)的[2]、退化的[3]、倒置的[4]等非規(guī)則的形式，這類問題也被稱為具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題[5]。多目標進化算法[1](multi-objective evolutionary algorithms，MOEAs)已被證明是解決多目標優(yōu)化問題的有效途徑，但現(xiàn)有算法大都假設問題的Pareto面是連續(xù)均勻地分布在目標空間的，在具有非規(guī)則Pareto前沿面的問題上表現(xiàn)不佳。這是由于，首先，基于指標的MOEAs[6]中，針對規(guī)則Pareto前沿面設計的指標不一定適用非規(guī)則Pareto前沿面，非規(guī)則Pareto前沿面問題中無效區(qū)域的個體可能使指標更好；其次，基于支配關系的MOEAs[5]針對規(guī)則Pareto前沿面設計的多樣性保持機制無法保持非規(guī)則Pareto前沿面的多樣性；第三，分解類的MOEAs[7]中預先設置的均勻分布的權值向量不能很好匹配非規(guī)則Pareto前沿面的分布，導致有效區(qū)域計算資源不足；最后，基于協(xié)同進化的MOEAs[8]中，基于決策變量分解的協(xié)同進化算法難以解決具有復雜依賴關系的問題，而使用目標函數(shù)分解的協(xié)同進化算法保持群體多樣性比較困難。

近年來，研究者們針對非規(guī)則Pareto前沿面多目標優(yōu)化問題設計了新的進化算法。本文將這些進化算法根據(jù)其實現(xiàn)方法分為調(diào)整參考向量類、固定參考向量加輔助方法類、參考點類、聚類和分區(qū)類，并進行分類綜述。

1 基礎概念及典型問題

1.1 相關概念

目前較通用的多目標優(yōu)化問題的數(shù)學描述如式(1)所示[1]：

MinF(x)=(f1(x),f2(x),…,fm(x))T，

(1)

x=(x1,x2,…,xn)T∈D。

式中：x為含n個決策變量的決策向量；D?n稱為決策空間；F(x)∈m是m個目標函數(shù)fi(x)組成的目標向量，i=1,2,…,m，目標向量構成目標空間。

定義1：支配解和非支配解。設xA、xB∈D是式(1)的兩個可行解，稱xA支配xB，記作xAxB，當且僅當：

(2)

對于這兩個可行解，稱xA為非支配解，xB為被支配解?？尚薪饧械姆侵浣獗环Q為Pareto最優(yōu)解，其在目標空間的映射構成Pareto前沿面。

定義2：退化的Pareto前沿面。一般來說，一個m目標的多目標優(yōu)化問題有一個m-1維的Pareto前沿面，當其Pareto前沿面的維數(shù)小于m-1時，稱該前沿面為一個退化的Pareto前沿面[3]。有冗余的目標、有約束等原因會造成退化的Pareto前沿面。

定義4：理想點、最底點和最壞點。種群中每個目標的最小值構成的點稱為最小值點，整個可行目標空間中的最小值點叫作理想點；種群中的非支配個體的每個目標的最大值構成的點稱為最底點；整個可行目標空間中的最大值構成的點稱最壞點[10]。

1.2 典型非規(guī)則Pareto前沿面測試問題

在DTLZ[11]系列可擴展的測試問題中，三目標及以上的DTLZ5，DTLZ6問題具有退化的Pareto前沿面，兩目標及以上的DTLZ7問題具有不連續(xù)的Pareto前沿面。IDTLZ1、IDTLZ2[12]有倒置的Pareto前沿面。圖1為三目標Pareto前沿面，其中三目標DTLZ1為規(guī)則的Pareto前沿面。

在WFG[13]系列可擴展的測試問題中，兩目標及以上的WFG2問題具有分段的Pareto前沿面，三目標及以上的WFG3問題具有退化的前沿面。在MaF[14]系列可擴展的測試問題中，三目標及以上的MaF6、MaF8、MaF9、MaF13有退化的Pareto前沿面，MaF7、MaF11有不連續(xù)的Pareto前沿面，MaF1和MaF4有倒置的Pareto前沿面。在UF[15]系列測試問題中兩目標的UF5、UF6和三目標的UF9都有不連續(xù)的Pareto前沿面。有些文獻認為具有凹的、凸的或者有凹有凸的連續(xù)均勻Pareto前沿面問題也屬于非規(guī)則Pareto前沿面問題，但本文所指的非規(guī)則Pareto前沿面問題并不包括連續(xù)均勻分布的這類問題。

另外，現(xiàn)實生活中也存在較多具有非規(guī)則Pareto前沿面的問題：例如，選礦問題具有不連續(xù)的Pareto前沿面[16]；汽車設計中的碰撞可靠性問題是一個三目標的具有不連續(xù)的Pareto前沿面的問題；汽車側(cè)面碰撞問題的Pareto前沿面只分布在目標空間的部分區(qū)域[4]；多速齒輪箱設計問題和暴雨排水系統(tǒng)問題具有退化的Pareto前沿面[17]；碳纖維形成過程中的六級牽伸參數(shù)優(yōu)化問題具有不連續(xù)的Pareto前沿面[5]。

2 非規(guī)則前沿面多目標進化算法

目前，進化算法處理具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題的思路主要可分為4種： ①根據(jù)種群分布調(diào)整參考向量分布；②固定參考向量結合輔助方法；③參考點；④聚類和分區(qū)，另外還有少數(shù)的其他方法。不同類型的、用于解決具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題的MOEAs算法如表1所示。

圖1 三目標Pareto前沿面Figure 1 The Pareto fronts of three-objective optimization problems

表1 用于解決具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題的MOEAs分類Table 1 MOEAs for solving multi-objective optimization problems with irregular Pareto fronts

2.1 根據(jù)種群分布調(diào)整參考向量的方法

預先設置的固定參考向量體系無法很好地匹配不規(guī)則前沿面的形狀，造成計算資源的浪費。常用的解決方法就是調(diào)整參考向量的分布，使之更加適配不規(guī)則前沿面的分布。

在這類算法中，一些算法根據(jù)參考向量關聯(lián)的個體數(shù)量來評價目標空間的個體擁擠度情況，并據(jù)此調(diào)整原有參考向量。比如，A-NSGA-III[4]和A2-NSGA-III[12]的每一代在擁擠的區(qū)域增加參考向量，刪除沒有個體關聯(lián)的參考向量。這兩個算法的區(qū)別在于增加參考向量的方法:A-NSGA-III是以原始的參考點為中心做單純型格增加新的參考點以構成參考向量；而A2-NSGA-III是以原始的參考點為一個角點做單純型格增加新的參考點以構成參考向量。然而該算法增加參考向量的效率低，且刪除程序的啟動條件在某些問題中可能很難滿足，越來越多的參考向量會浪費很多不必要的計算資源。

MOEA/D-AWA[7]在一定代數(shù)后，根據(jù)外部庫評估的擁擠度對參考向量進行調(diào)整，刪除擁擠區(qū)域的參考向量，增加稀疏區(qū)域的參考向量。這個算法的問題在于，擁擠度評價在目標高維情況下計算量大，且算法對某些參數(shù)敏感。A-IM-MOEA[18]早期用一個隨機向量代替一個關聯(lián)個體數(shù)最多的向量，后期用一個隨機向量代替一個關聯(lián)個體數(shù)最少的向量。RVEA*[19]中，如果一個參考向量沒有任何個體與之關聯(lián)，該參考向量就會被一個隨機產(chǎn)生的參考向量替代。然而隨機產(chǎn)生的參考向量無法保證種群的均勻分布。iRVEA[26]在RVEA的框架下設置了兩組方向向量，一組是固定的，一組不固定，不固定的參考向量中每代用與其他個體夾角最大的個體去構造新的方向向量，代替一個無效的方向向量。另外RVEA的APD選擇可能會漏掉很多好解，所以又采用了第二準則去選擇。MaOEA/D-2ADV[21]一開始用目標軸向量引導種群收斂；當檢測到種群不再收斂時，以有個體關聯(lián)的向量為有效向量，按有效向量之間的夾角從大到小排序，兩兩之間產(chǎn)生中點向量為新的參考向量，直到達到種群規(guī)模。這個方法在具有凹型前沿面的問題上表現(xiàn)一般，且只使用目標軸向量作為方向向量搜索區(qū)域太窄，很難引導收斂。MOEA/D-TPN[22]把整個進化進程分為兩個階段，把種群分為中間種群和邊緣種群，根據(jù)第一階段檢測到的兩個種群的擁擠度對比情況決定是否進入第二階段——更新參考向量；同時，改進的差分進化[47]算子用于產(chǎn)生不重復的新個體。一些算法隨機產(chǎn)生新的參考向量，再與原有參考向量共同進行對比調(diào)整。如PICEA-w[24]的每一代都隨機產(chǎn)生新的參考向量，然后根據(jù)兩個準則篩選參考向量：①該參考向量使候選解的適應度更高；②如果有兩個適應度一樣的參考向量，則選擇與候選解向量角度大的，以此來保證收斂性和多樣性。然而，每一代都產(chǎn)生新參考向量集并重新計算適應度需要大量的計算資源，比較低效。一些算法先估計Pareto前沿面的分布情況，再生成匹配的參考向量。DMOEA/D[25]每隔一定代數(shù)，用當前種群估計PF面，再在估計的PF面上以個體在每個子目標的投影等距插值取點，再將這些點分組計算平均值以生成參考向量。MOEA/D-ABD[2]是針對不連續(xù)非規(guī)則面的一種算法。該算法每隔一定代數(shù)通過計算權重向量與其關聯(lián)的個體之間的偏差來檢測Pareto前沿的不連續(xù)部分，并根據(jù)每個連續(xù)部分的長度調(diào)整權重向量的數(shù)量。該算法只適用于兩目標問題，而且算法中的一些參數(shù)的閾值比較難確定。MOEA-HD[20]將子問題分為不同的層次，并根據(jù)高層次搜索結果自適應調(diào)整低層次子問題的搜索方向，缺點是只能處理2個或3個目標的優(yōu)化問題。一些算法用個體本身產(chǎn)生參考向量。MOEA/D-AM2M[27]是一種根據(jù)當前個體自適應產(chǎn)生參考向量的方法，該算法在處理退化的Pareto前沿面問題上表現(xiàn)較好。DDR[28]用個體和原點構造向量，以已選個體為聚類中心進行聚類，選擇當前個體為聚類中心的類中適應度最好的個體。它每次只產(chǎn)生一個參考向量，并相應選擇一個個體。SRV-TSL[23]通過特定的中心向量來縮放參考向量，用以處理凹或凸面的問題，TSL用多樣性較好的候選解及其兩兩的中點設置為新的參考向量用以處理退化的或不連續(xù)面的問題。這兩個方法可以協(xié)同工作，并嵌入基于參考向量的高維多目標進化優(yōu)化算法。然而SRV的縮放方法不適合反向的Pareto前沿面。

近年來，機器學習被用于更準確地調(diào)整參考向量。CLIA[30]將每一代的參考向量標記為有效的和無效的，再用增量支持向量機進行學習，用學習的結果判斷哪些是有效的參考向量，并刪掉無效的參考向量，用A-NSGA-III的方法增加參考向量,接著用基于向量的PDM指標篩選適應度更好的個體。這里的PDM指標類似于MOEA/D的PBI和RVEA的APD指標，由收斂性項(個體每個目標的平均值)和多樣性項(個體到關聯(lián)的參考向量的距離)構成。這個算法中嵌套學習模型的做法本身比較占用資源，并且沒有考慮到種群分布的變化性，早期個體的分布往往不能準確反映Pareto前沿面的真實情況。DEA-GNG[29]用增長型神經(jīng)氣網(wǎng)絡(GNG)學習權重向量的拓撲結構，再用學習到的信息調(diào)整參考向量分布。PF的拓撲結構是由一個改進的GNG模型學習的，篩選已知的解作為信號輸入。參考向量通過結合GNG網(wǎng)絡中的節(jié)點和一組均勻分布的參考向量來進行調(diào)整。每個參考向量的標量函數(shù)都是根據(jù)相應節(jié)點和從其發(fā)出的邊之間的角度來調(diào)整的。這兩種適應機制增強了進化算法的搜索能力。

總體來說，根據(jù)種群分布調(diào)整參考向量分布的方法是有效的，不論是根據(jù)當前種群分布情況還是綜合考慮若干代種群分布變化去調(diào)整參考向量分布，都能一定程度上彌補固定參考向量的不足。但是，由于遠離Pareto前沿面時，種群中存在大量被支配個體，這些個體的分布并不能反映真實Pareto前沿面的分布情況，對于參考向量的調(diào)整有誤導作用。如何辨別真正有效的收斂方向是這類算法的一個關鍵。

2.2 固定參考向量合并其他輔助方法

雖然根據(jù)種群調(diào)整參考向量的方法達到了一定效果，但也有一些算法仍然是基于固定的參考向量體系，另外增加了其他適應非規(guī)則Pareto前沿面的輔助加強收斂性或多樣性的方法。

比如，BCE-MOEA/D[32]設置了兩個種群，一個基于非支配排序法，另一個沿用MOEA/D，這兩個種群同時產(chǎn)生新個體，同時進化，用非支配排序方法篩選兩個種群的最終個體。MOEA/D-SAS[33]的每個參考向量找距離自己夾角最近的若干個個體按適應度排序，再在最后一個選擇層，依次選擇與其他個體的夾角最大的個體。ASEA[34]首先把每個個體關聯(lián)給與自己夾角最小的向量，有效向量關聯(lián)的當代的未被選擇的個體中，先用收斂性排序，再以其與子問題及相鄰子問題中已選個體的最小夾角排序，夾角大的優(yōu)先選擇，這個過程循環(huán)直到達到種群規(guī)模。MOEA/D-AED[31]在算法中建立了一個外部庫，用于儲存分解的方法篩選出的適應度高(切比雪夫函數(shù)值小)的非支配個體，用一個基于自適應ε非支配排序的方法來控制外部庫的規(guī)模，這樣來彌補固定參考向量的方法在處理非規(guī)則Pareto前沿面問題時每一代得到的個體數(shù)太少的缺陷。

這類方法大都用一些輔助的手段來彌補固定參考向量方法在處理非規(guī)則Pareto前沿面時選出的個體數(shù)目不足的缺陷。然而當有個體關聯(lián)的參考向量數(shù)量非常少時，輔助的收斂或多樣性保持手段會對算法性能起決定性作用，而基于分解的算子則失去了應有的功能。

2.3 參考點的方法

參考點的思想也被用于處理非規(guī)則Pareto前沿面問題，這其中有一個參考點對應選擇種群中一個個體的方法，也有用最小值點或最底點作為全局參考點的方法。

一個參考點對應選擇種群中一個個體的方法有：RPEA[36]每隔一定代數(shù)，用當前非支配個體中擁擠距離較大(不擁擠)的個體通過在每個目標軸上的平移產(chǎn)生參考點，再選擇種群中距離這些參考點加權歐氏距離最小的個體。AR-MOEA[37]算法提出一個改進的IGD指標——IGD-NS，在初始的均勻分布的參考點的基礎上，根據(jù)種群的分布，找距離參考點最近的個體和非支配個體建立外部庫，選有個體關聯(lián)的參考點和與這些參考點向量夾角最大的外部庫個體作為新的參考點，刪除無效的參考點。然后，進行非支配排序，在最后一個待選擇的非支配面，根據(jù)新的參考點集，刪除使整個種群的IGD-NS指標更小的個體，直到達到所需種群規(guī)模。F-DEA[35]首先用傳統(tǒng)的Das and Dennis方法產(chǎn)生均勻分布的參考點，然后選擇有個體關聯(lián)的參考點中擁擠距離較大的參考點作為聚類中心，對合并的父子種群進行聚類，選擇每個類中模糊適應度值最好的個體。CA-MOEA[5]先對當前種群進行非支配排序，再在臨界非支配面用基于分層聚類方法將個體聚為所需數(shù)目的類，然后計算每個類的聚類中心作為參考點，依次選擇距離參考點最近的、擁擠區(qū)域的、稀疏區(qū)域的個體。

用最小值點、最底點或最大值點作為全局參考點的算法有：MOEA/D-MR[39]將種群分為兩個子種群，其中一個種群以當前的最小值點作為參考點，另一個種群以當前非支配種群的最大值點作為參考點。用這樣雙參考點的方法避免前沿面的凹和凸帶來的參考向量分布不均勻的問題。PAEA[40]中，一個父代會產(chǎn)生兩個子代，在這3個個體中分別選擇以最小值點為參考點和以最大值點為參考點的情況下適應度最高的兩個個體。再在剩下的種群中依次選擇夾角最小的兩個個體，留下其中距離原點更近的那一個。然而，算法默認子代的收斂性比父代好，而這種情況并不總是成立。PaRP/EA[41]先用非支配排序，如果第一非支配面?zhèn)€體數(shù)超過種群數(shù)目，則用歸一化后距離向量最近的幾個非支配個體到超平面的平均距離和原點到超平面的平均距離做對比。如果更近，則判斷為凸面，用最底點作為參考點，距離參考點近的個體適應度高；如果更遠，則判斷為凹面，用最小值點作為參考點。距離參考點更遠的，適應度更高，如果距離一樣，則判斷為線性，個體每個目標值的和越小適應度越高。另外，算法用個體向量之間的夾角度量多樣性，與其他個體夾角越大，適應度越高。這個算法只檢測了Pareto前沿面的凹凸性，對其他非規(guī)則形狀沒有特別處理。MaOEA-CS[38]先用軸向量尋找與之夾角最小的邊界個體，并用邊界個體的每個目標的最大值構造最底點，將目標值小于最底點的和大于最底點的分為兩個子集。如果目標值小于最底點的個體數(shù)大于所需種群規(guī)模，則依次選擇與其他個體最小夾角最大的個體；若目標值小于最底點的個體數(shù)不足，則從目標值大于最底點的個體中依次選與最小值點距離最近的個體。

基于參考點的方法中，參考點的設置對于算法的性能有決定性的影響。因此，如何設置更有效的參考點，從而引導種群高效地收斂并保持多樣性，是這類算法的關鍵。

2.4 聚類和分區(qū)的方法

由于非規(guī)則Pareto前沿面的分布不可預知，將當前種群通過聚類或者分區(qū)的方法分為若干個子問題，找尋子問題的最優(yōu)解從而構成最終的解集也是一個比較好的途徑。

EMyO/C[43]把聚類思想應用于高維多目標優(yōu)化問題，將歐氏距離最近的個體聚為一個類，每個類中再選擇距離預先設定的全局參考點最近的個體。然而，基于種群計算出的理想點不能保證正確的收斂方向，而且簡單地根據(jù)歐氏距離聚類也不能對個體進行有效的劃分。MaOEA/C[42]用K-means聚類結合分層聚類，選擇方向軸為K-means聚類的聚類中心，將整個種群均分為m(m為目標數(shù)目)份。在m個子區(qū)域中，分別先用非支配排序，把前幾個面?zhèn)€體挑出來，再用基于角度的分層聚類，把整個目標空間分為所需種群規(guī)模數(shù)量的子問題，每個子問題依次選離軸最近的個體和收斂性最好的個體。RdEA[45]根據(jù)種群分布預測Pareto前沿面的幾何形狀，并提出一種區(qū)域劃分的方法將目標空間分區(qū)，在每個分區(qū)中選擇離參考點更近或離區(qū)域中心點更近的個體。然而判斷個體位于哪個區(qū)域比較困難，且算法中存在難以確定的參數(shù)。CDG-MOEA[46]對當前種群建立網(wǎng)絡，每個個體按網(wǎng)格中的位置編序，優(yōu)先選擇序號小的個體。MOEA-PPF[44]首先根據(jù)個體之間的擁擠距離判斷優(yōu)化問題的Pareto前沿面上的間斷點，并在考慮間斷點的基礎上將目標空間劃分為若干子空間，在每一子空間中采用MOEA/D得到一個外部保存集，再綜合所有外部保存集組成問題的最終Pareto解集。該算法比較適合有分段的Pareto前沿面的問題。

聚類和自適應分區(qū)的方法在處理非規(guī)則Pareto前沿面問題上有較好的表現(xiàn)。聚類的優(yōu)勢在于它是基于種群的分區(qū)，每一個子區(qū)域都有個體，不浪費計算資源，劣勢在于當分類不均勻時會導致種群的分布不均勻，而且聚類的方法計算復雜度較高。再者，聚類也無法辨別真正有Pareto前沿面的區(qū)域。而網(wǎng)格分區(qū)方法雖然分區(qū)更加均勻，卻容易造成計算資源的浪費，且算法性能對網(wǎng)格尺寸敏感。

3 結論和展望

近幾年來，隨著多目標進化優(yōu)化算法的發(fā)展，以往基于規(guī)則的Pareto前沿面設計的進化算法無法很好解決具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題，于是具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題逐漸受到關注，并涌現(xiàn)出許多針對性的算法。

本文首先簡要介紹了MOEAs的研究概況，將現(xiàn)有MOEAs分為指標類、支配關系類、分解類和協(xié)同進化類4個大類，分別簡要介紹這4類算法以及在處理具有非規(guī)則Pareto前沿面多目標優(yōu)化問題上的缺陷；接著，給出了非規(guī)則Pareto前沿面多目標進化優(yōu)化領域的一些概念，并整理了典型的非規(guī)則Pareto前沿面多目標優(yōu)化測試問題。在文章的主要部分，從調(diào)整參考向量、固定參考向量結合其他輔助策略、參考點、聚類和分區(qū)4個大方向?qū)ο鄳愋偷乃惴ㄟM行簡述，分析了每個類型算法的特點和設計關鍵。

盡管運用MOEAs處理具有非規(guī)則Pareto前沿面問題已經(jīng)取得了一定成效，但現(xiàn)有算法一般只在部分非規(guī)則Pareto前沿面問題上表現(xiàn)較好，適應所有種類的非規(guī)則Pareto前沿面問題的算法還有待開發(fā)，更加智能的、可以辨別和處理多類型非規(guī)則Pareto前沿面的MOEAs是未來的研究重點。這里給出一些可能的發(fā)展方向：首先，目前大都用單一的方法來處理非規(guī)則Pareto前沿面多目標優(yōu)化問題，用多種方法混合可能可以取長補短，提高算法性能；第二，機器學習的方法也可以與進化算法進行融合，比如遷移學習，多任務的方法等；第三，決策變量或目標數(shù)量的高維[48]給問題帶來更大的難度，這方面的研究還有很大空間；第四，動態(tài)的具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題的研究還是空白，有待開發(fā)；第五，數(shù)據(jù)驅(qū)動的、具有非規(guī)則Pareto前沿面的多目標優(yōu)化研究以及算法在實際具有非規(guī)則Pareto前沿面的多目標優(yōu)化問題上的應用研究也有待加強。