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

(1.東華大學(xué) 信息科學(xué)與技術(shù)學(xué)院，上海 201620； 2.薩里大學(xué) 計(jì)算機(jī)科學(xué)系，英國(guó) 薩里 GU2 7XH)

0 引言

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

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

1 基礎(chǔ)概念及典型問題

1.1 相關(guān)概念

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

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

(1)

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

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

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

(2)

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

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

定義4：理想點(diǎn)、最底點(diǎn)和最壞點(diǎn)。種群中每個(gè)目標(biāo)的最小值構(gòu)成的點(diǎn)稱為最小值點(diǎn)，整個(gè)可行目標(biāo)空間中的最小值點(diǎn)叫作理想點(diǎn)；種群中的非支配個(gè)體的每個(gè)目標(biāo)的最大值構(gòu)成的點(diǎn)稱為最底點(diǎn)；整個(gè)可行目標(biāo)空間中的最大值構(gòu)成的點(diǎn)稱最壞點(diǎn)[10]。

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

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

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

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

2 非規(guī)則前沿面多目標(biāo)進(jìn)化算法

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

圖1 三目標(biāo)Pareto前沿面Figure 1 The Pareto fronts of three-objective optimization problems

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

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

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

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

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

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

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

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

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

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

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

2.3 參考點(diǎn)的方法

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

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

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

基于參考點(diǎn)的方法中，參考點(diǎn)的設(shè)置對(duì)于算法的性能有決定性的影響。因此，如何設(shè)置更有效的參考點(diǎn)，從而引導(dǎo)種群高效地收斂并保持多樣性，是這類算法的關(guān)鍵。

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

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

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

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

3 結(jié)論和展望

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

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

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