郭曉彤，李玲燕+，朱春陽(yáng)

1.西安建筑科技大學(xué) 管理學(xué)院，西安 710055

2.南京航空航天大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，南京 211106

1 引言

含有多個(gè)目標(biāo)的最優(yōu)化問題被稱為多目標(biāo)優(yōu)化問題，多目標(biāo)優(yōu)化問題中當(dāng)需要被優(yōu)化的目標(biāo)數(shù)在4個(gè)及其以上時(shí)被稱為高維多目標(biāo)優(yōu)化問題，在現(xiàn)實(shí)世界中高維多目標(biāo)優(yōu)化問題廣泛存在，例如工程設(shè)計(jì)問題、機(jī)場(chǎng)調(diào)度問題、護(hù)士排班問題、車輛控制優(yōu)化、自來水供應(yīng)規(guī)劃等[1]。另外，一些單目標(biāo)優(yōu)化問題可以將多個(gè)約束轉(zhuǎn)化為優(yōu)化的目標(biāo)，變成一個(gè)高維多目標(biāo)無約束的優(yōu)化問題。例如，文獻(xiàn)[2]提出了一個(gè)汽車安全性優(yōu)化設(shè)計(jì)的問題，具有一個(gè)優(yōu)化目標(biāo)和多個(gè)約束，文獻(xiàn)[3]將其一些約束轉(zhuǎn)化為需要優(yōu)化的目標(biāo)，將問題轉(zhuǎn)化為具有9個(gè)目標(biāo)的高維多目標(biāo)優(yōu)化問題。不同于傳統(tǒng)的單目標(biāo)優(yōu)化問題和具有2～3個(gè)目標(biāo)的多目標(biāo)優(yōu)化問題，這些優(yōu)化問題的主要特點(diǎn)是需要優(yōu)化的目標(biāo)數(shù)非常多。

不失一般性，以最小化問題為例，一個(gè)具有n個(gè)決策變量，m個(gè)目標(biāo)函數(shù)的多目標(biāo)優(yōu)化問題（multiobjective optimization problems，MOPs）可表述為：

其中，x∈Ω是決策向量；Ω是決策空間；F:Ω→Rm由m個(gè)實(shí)值目標(biāo)函數(shù)組成，Rm是目標(biāo)空間，可行目標(biāo)集被定義為集合{F(x)|x∈Ω}。

使u,v∈Rm，對(duì)于任意的i∈{1,2,…,m}，滿足ui≤vi，并且在至少一個(gè)目標(biāo)上滿足uj＜vj,j∈{1,2,…,m}，稱u支配v。給定Rm中的一個(gè)集合S，S中的一個(gè)解如果被稱為非支配解，那就表示在集合S中當(dāng)沒有其他解可以支配它。如果x*∈Ω，在相應(yīng)的目標(biāo)集上F(x*)是非支配的。那像x*這樣的解組成的集合被稱為Pareto最優(yōu)解集（Pareto solution，PS），相應(yīng)的F(x*)組成的集合稱為Pareto前沿（Pareto front，PF）。

定義1（理想點(diǎn)Z*）

定義2（Pareto極值點(diǎn)B）

定義3（邊界解PCS）對(duì)于一個(gè)具有m個(gè)目標(biāo)的多目標(biāo)優(yōu)化問題，對(duì)于Pareto最優(yōu)解集而言，如果一個(gè)解能夠滿足最小化k個(gè)目標(biāo)(k＜m)，并且最大化其他目標(biāo)，那么，這樣的解被稱為邊界解。

演化算法作為一個(gè)經(jīng)典的基于種群的啟發(fā)式算法，能夠在一次運(yùn)行就得到一組解，具有解決多目標(biāo)優(yōu)化問題的先天優(yōu)勢(shì)。由于這一特性，最近二十年以來多目標(biāo)演化算法（multi-objective optimization evolutionary algorithm，MOEA）取得了長(zhǎng)足的發(fā)展[4]。然而，對(duì)于目標(biāo)數(shù)量超過3個(gè)的高維多目標(biāo)優(yōu)化問題（many-objective optimization problems，MaOPs），多目標(biāo)優(yōu)化算法的性能往往會(huì)急劇下降，因此，高維多目標(biāo)優(yōu)化問題近些年受到了廣泛關(guān)注[5]。

傳統(tǒng)多目標(biāo)優(yōu)化算法在高維多目標(biāo)優(yōu)化問題中存在的困難可以從收斂性和多樣性方面總結(jié)為以下兩點(diǎn)：

（1）選擇壓力的丟失。選擇壓力是指種群向真實(shí)PF收斂的壓力。由于在高維目標(biāo)空間中，大部分的解互相之間都是非支配的，因此使用解之間的支配關(guān)系來選擇解的策略將會(huì)面臨選擇壓力丟失的困難。圖1給出了隨著目標(biāo)數(shù)量的增多隨機(jī)產(chǎn)生的解為非支配的比例，從圖中可以看出在目標(biāo)數(shù)量增加時(shí)，絕大部分的解都成為非支配的[1]。

Fig.1 Schematic diagram of nondominant solution in initial solution under different number of objectives圖1 不同目標(biāo)數(shù)下初始解中的非支配解比例示意圖

（2）多樣性保持困難。一般來說，大多數(shù)多目標(biāo)連續(xù)優(yōu)化問題的PF是分段連續(xù)的[6-7]，因此不可能得到所有的Pareto最優(yōu)解。實(shí)際的算法設(shè)計(jì)中通常得到一組均勻分布的具有代表性的解集，以此來模擬PF。當(dāng)目標(biāo)數(shù)量是2或者3時(shí)，問題的PF是一維的曲線或者2維的曲面，保持其多樣性較為直觀。隨著目標(biāo)空間維度增加，種群中有限個(gè)解之間分布較為稀疏，這使得在低維空間中常使用的多樣性保持策略在高維多目標(biāo)優(yōu)化算法中失效[8-9]，例如在經(jīng)典的多目標(biāo)優(yōu)化算法NSGA-II[10]中使用的擁擠度距離排序。

為了提高傳統(tǒng)多目標(biāo)演化算法在高維多目標(biāo)優(yōu)化問題中的性能，學(xué)者們提出了大量的改進(jìn)方法[11-12]。這些方法大體可以分為3類。

第一類方法通過改進(jìn)支配關(guān)系提高算法在高維多目標(biāo)優(yōu)化問題上的收斂性能。由于支配關(guān)系在高維上將失去選擇壓力，最直觀的改進(jìn)方法就是修改原有的支配關(guān)系以提高收斂性能。這類修改支配關(guān)系的方法包括?-支配[13]、L-最優(yōu)化[14]、混合支配[15]等。文獻(xiàn)[16]提出了一種基于格子的高維多目標(biāo)優(yōu)化算法GrEA，利用格子支配來改善基于支配算法的收斂性能。

第二類方法是基于分解的方法。這類方法將一個(gè)復(fù)雜的多目標(biāo)優(yōu)化問題分解成為多個(gè)單目標(biāo)優(yōu)化問題，并分別解決這些單目標(biāo)問題實(shí)現(xiàn)對(duì)多目標(biāo)優(yōu)化問題的求解[17-18]。這類算法首先生成一組在目標(biāo)空間均勻分布的參考向量，每個(gè)向量對(duì)應(yīng)著一個(gè)子問題且每個(gè)子問題維護(hù)著一個(gè)最優(yōu)解。對(duì)每個(gè)子問題，通過聚合函數(shù)值選擇最優(yōu)解。由于聚合函數(shù)值比支配關(guān)系對(duì)解的選擇壓力要大，因此基于分解算法的收斂性能往往好于基于支配的算法。此外，此類算法的多樣性可以通過其在目標(biāo)空間均勻生成的一組參考向量得到保持。

第三類方法是基于指標(biāo)的方法。這類方法通過一個(gè)指標(biāo)值來評(píng)價(jià)一個(gè)解，而不是多個(gè)目標(biāo)值。具有代表性的算法例如IBEA（indicator-based evolutionary algorithm）[19]、SMS-EMOA（SMS-evolutionary multiobjective optimization algorithms）[20]、HypE（hypervolumebased search algorithm）[21]等。

本文組織結(jié)構(gòu)如下：第2章首先對(duì)多目標(biāo)優(yōu)化問題進(jìn)行分析，并基于此提出本文算法的設(shè)計(jì)動(dòng)機(jī)；第3章對(duì)基于Pareto支配關(guān)系的兩階段進(jìn)化高維多目標(biāo)優(yōu)化算法進(jìn)行了介紹；第4章對(duì)文中使用的基準(zhǔn)測(cè)試問題集、評(píng)價(jià)算法性能指標(biāo)以及相關(guān)實(shí)驗(yàn)參數(shù)的設(shè)置細(xì)節(jié)進(jìn)行說明，并將改進(jìn)后的算法與當(dāng)前領(lǐng)域主流算法在標(biāo)準(zhǔn)測(cè)試問題集上進(jìn)行算法比較實(shí)驗(yàn)，并對(duì)算法的各個(gè)功能模塊的有效性進(jìn)行實(shí)驗(yàn)論證；第5章總結(jié)全文。

2 多目標(biāo)優(yōu)化問題分析

多目標(biāo)優(yōu)化問題的復(fù)雜性體現(xiàn)在決策空間中不存在唯一的解能使所有的目標(biāo)同時(shí)達(dá)到最優(yōu)，求解多目標(biāo)優(yōu)化問題是要找到一組表示目標(biāo)間權(quán)衡關(guān)系的Pareto最優(yōu)解。因此，通常希望能夠得到具有以下性質(zhì)的一組解集。

（1）收斂性：所得到的解集在目標(biāo)空間上能夠盡可能地靠近PF。

（2）多樣性：所得到的解集在目標(biāo)空間上能夠盡可能均勻地分布在整個(gè)PF上。

對(duì)于現(xiàn)存的多目標(biāo)優(yōu)化算法，雖然基于支配的算法能夠在一定程度上改善基于支配的算法的收斂性能，但由于支配關(guān)系先天的劣勢(shì)，對(duì)于目標(biāo)數(shù)量較多的問題（如10個(gè)和10個(gè)以上目標(biāo)的優(yōu)化問題），這類算法的性能仍有待提高。對(duì)于基于支配的算法，由于參考向量是在整個(gè)目標(biāo)空間生成，其假設(shè)高維多目標(biāo)優(yōu)化問題的PF是完整的流形（各個(gè)目標(biāo)之間是完全沖突的）。然而，許多問題特別是實(shí)際工程問題的PF是不規(guī)則的。例如，DTLZ[22]測(cè)試集中的DTLZ5和DTLZ6問題的PF是退化的，其只有兩個(gè)目標(biāo)是完全沖突的，在高維上其PF仍然是一個(gè)一維的曲線。DTLZ7問題的前沿是不連續(xù)的，PF含有2m-1個(gè)不連續(xù)的部分（m是目標(biāo)數(shù)量）。由于PF的不完整，很多參考向量將不能與PF相交，位于前沿外部的參考向量通常會(huì)引導(dǎo)演化算法搜索到位于PF邊界上的點(diǎn)，這大大損害了算法的多樣性，浪費(fèi)了計(jì)算資源。雖然基于支配的多目標(biāo)優(yōu)化算法在一些問題上取得了極好的性能，例如MOEA/DD[23]和NSGA-III[24]在DTLZ1～DTLZ4上均取得了極好的性能，但是這種性能依賴于問題PF的形狀，魯棒性較差[25]?；谥笜?biāo)的算法往往需要耗費(fèi)大量的時(shí)間來計(jì)算每個(gè)解的指標(biāo)值，使得這類算法的時(shí)間復(fù)雜度較高[26]。

基于對(duì)現(xiàn)有算法的分析，提出了一種基于Pareto支配關(guān)系的兩階段高維多目標(biāo)優(yōu)化算法。第一階段集中計(jì)算資源搜索邊界解，并通過邊界解確定極值點(diǎn)。此后，可以依據(jù)極值點(diǎn)將高維的目標(biāo)空間縮小。在第二階段可以根據(jù)極值點(diǎn)和支配關(guān)系共同選擇精英解，并通過本文提出的動(dòng)態(tài)最小距離選擇多樣性較好的解。

支配關(guān)系在高維上會(huì)喪失選擇壓力，通過搜索到極值點(diǎn)并縮小目標(biāo)空間的方式來提高算法的收斂性能，同時(shí)發(fā)揮了基于支配的算法在多樣性保持方面的靈活性。基于分解的多目標(biāo)優(yōu)化算法由于需要產(chǎn)生一組均勻分布的參考向量，難以較好地處理具有不規(guī)則PF的高維多目標(biāo)優(yōu)化問題。本文提出的算法在第二階段使用了動(dòng)態(tài)最小距離的方法保持解集的多樣性，使得算法能夠很好地處理PF不規(guī)則的高維多目標(biāo)優(yōu)化問題。

3 算法設(shè)計(jì)

3.1 算法總體框架

在本節(jié)將介紹提出的基于Pareto支配關(guān)系的兩階段進(jìn)化高維多目標(biāo)優(yōu)化算法（MOEA/PT），其中MOEA表示多目標(biāo)進(jìn)化算法；P表示Pareto支配關(guān)系；T表示two phase。

MOEA/PT由兩個(gè)子算法構(gòu)成，在算法開始的第一階段，通過極值點(diǎn)搜索技術(shù)搜索到優(yōu)化問題的近似極值點(diǎn)，此后算法進(jìn)入第二階段，此階段通過基于Pareto支配關(guān)系的進(jìn)化算法輸出一組精英解。值得注意的是，為了提高算法的魯棒性，第一階段通過自適應(yīng)終止條件根據(jù)優(yōu)化問題極值點(diǎn)搜索的難易而自適應(yīng)終止。接下來的幾節(jié)將對(duì)算法的各個(gè)模塊進(jìn)行詳細(xì)介紹。

3.2 算法的第一階段及其終止條件

在此階段，通過極值點(diǎn)搜索算法搜索到優(yōu)化問題的近似極值點(diǎn)，然后通過極值點(diǎn)縮小算法在高維多目標(biāo)優(yōu)化問題的搜索空間。值得注意的是Pareto極值點(diǎn)向量是由Pareto前沿上的各個(gè)目標(biāo)的最大值所組成的，而且極值點(diǎn)只存在于目標(biāo)空間。因此不能直接在決策空間中搜索，現(xiàn)有的幾種極值點(diǎn)搜索算法[27-29]也是通過邊界解來間接地搜索優(yōu)化問題的極值點(diǎn)，本文采用近期研究工作[30]中第一階段自適應(yīng)極值點(diǎn)搜索技術(shù)來搜索優(yōu)化問題的極值點(diǎn)。該方法的主要思想是在迭代過程中，通過最小化式（4）找到每個(gè)坐標(biāo)軸上的邊界解。

式中，ei代表第i個(gè)坐標(biāo)軸的方向向量；vertdist(F(x),ei)表示F(x)到軸ei的垂直距離。在確定當(dāng)前種群中的邊界點(diǎn)之后，對(duì)這些邊界點(diǎn)進(jìn)行變異操作產(chǎn)生新解，并通過帕里托支配關(guān)系進(jìn)行選擇。迭代進(jìn)行以上的操作，直到達(dá)到該階段的終止條件。設(shè)所有的邊界解所組成的集合為Pb，則可由該集合，根據(jù)式（5）近似當(dāng)前解集P的極值點(diǎn)。

在搜索極值點(diǎn)的過程中，計(jì)算每第t代與之前t-200代的邊界解最大變化率。由于需要給極值點(diǎn)搜索一定的搜索次數(shù)，因此設(shè)置檢測(cè)變化的迭代次數(shù)為200，即極值點(diǎn)搜索最少將進(jìn)行200代1）在搜索極值點(diǎn)的過程中，需要給極值點(diǎn)一定的搜索次數(shù)，計(jì)算最大變化率的頻率過高可能會(huì)導(dǎo)致極值點(diǎn)還沒有被搜索到就切換到了第二階段。反之，如果最大變化率的頻率過低，會(huì)導(dǎo)致算法有可能一直停留在第一階段從而失去了切換機(jī)制的應(yīng)有的作用。通過在不同的測(cè)試問題上的實(shí)驗(yàn)表明在整個(gè)演化過程中判斷5至10次比較合適。在實(shí)驗(yàn)階段，選取的是30萬次的函數(shù)評(píng)估，結(jié)合不同目標(biāo)數(shù)時(shí)的種群規(guī)模，基本上每個(gè)目標(biāo)數(shù)的問題都需要迭代1 000多次，在這種情況下，將計(jì)算最大變化率的頻率統(tǒng)一設(shè)定為200代，從而確保每個(gè)問題基本上都能進(jìn)行5～10次的最大變化率判斷。。如果由式（6）所得的最大變化率小于預(yù)定的閥值0.001，則說明極值點(diǎn)已經(jīng)在200代之內(nèi)變化極少，當(dāng)前階段繼續(xù)進(jìn)行極值點(diǎn)搜索將很難使種群得到更大的改善，因此應(yīng)終止此階段，進(jìn)行下一步的搜索操作。

3.3 算法的第二階段

此階段中，輸入為第一階段極值點(diǎn)搜索所得的種群，輸出是通過基于Pareto支配關(guān)系和動(dòng)態(tài)最小距離法的演化算法所得到的一組精英解。關(guān)于該階段的更多細(xì)節(jié)將在后續(xù)詳細(xì)介紹。

從圖2中不難發(fā)現(xiàn)，如果邊界解確定得不夠準(zhǔn)確，空間劃分選解策略將會(huì)出現(xiàn)偏差，如：在PF上的解x1、x近似出的極值點(diǎn)B1是正確的，而x2、x3近似出的極值點(diǎn)B2則由于過小，而導(dǎo)致空間劃分出現(xiàn)嚴(yán)重的偏差，導(dǎo)致很多的非支配解也在外部空間被刪去?；诖?，為了提高算法的魯棒性以及處理高維多目標(biāo)優(yōu)化問題的效率，本文只在混合種群中發(fā)現(xiàn)非支配解，如果非支配解的數(shù)量大于規(guī)定尺寸，基于近似極值點(diǎn)的空間劃分選解策略將作為算法選解的一個(gè)補(bǔ)充機(jī)制，在非支配解中進(jìn)一步通過空間劃分完成選解。

Fig.2 Schematic diagram for nadir point B圖2 極值點(diǎn)B的示意圖

Fig.3 Illustration of diversity maintenance based on dynamic minimum distances圖3 動(dòng)態(tài)最小距離多樣性保持機(jī)制示意圖

設(shè)當(dāng)前內(nèi)部空間的非支配解集為S，其中S為當(dāng)前內(nèi)部空間中的非支配個(gè)體的數(shù)目，若S大于預(yù)先設(shè)置的種群上限N，需要通過一個(gè)準(zhǔn)則在S個(gè)非支配個(gè)體中選擇N個(gè)個(gè)體，并盡量保證保留下來的非支配個(gè)體分布的多樣性。就多樣性保持而言，在算法設(shè)計(jì)動(dòng)機(jī)部分已經(jīng)進(jìn)行了討論，一次計(jì)算的擁擠度距離策略不能很好地考慮每個(gè)解對(duì)于種群整體的多樣性貢獻(xiàn)，基于此，本文提出了基于動(dòng)態(tài)最小距離的多樣性保持機(jī)制，首先將m個(gè)邊界解保存進(jìn)精英解集中，然后從剩余的S-m個(gè)個(gè)體中選擇N-m個(gè)精英個(gè)體。首先計(jì)算S-m個(gè)解中每個(gè)解到其他解的距離，將距離最小的一對(duì)解中的任意一解刪除，然后重復(fù)以上步驟，直至S-N個(gè)劣解被刪除。如圖3所示，以從6個(gè)解中選擇4個(gè)解為例，邊界解x1和x6首先被保存下來，然后距離最近的一對(duì)x3和x4中的任意一個(gè)解被刪除。更新每個(gè)解的最近解距離，此時(shí)，距離最近的一對(duì)解為x1和x2，由于x1已經(jīng)被優(yōu)先加入到種群中，因此x2將被刪除。最終保留下來的解將會(huì)是x1、x3、x5和x6或者x1、x4、x5和x6。這與理想的選解方式十分相符。然而，當(dāng)使用傳統(tǒng)的擁擠度距離排序的方式選擇解時(shí)，擁擠度最小的兩個(gè)解為x3和x4，因此，x3和x4都將被刪除，最終保留下來的解將會(huì)是x1、x2、x5和x6，種群的多樣性較差。

應(yīng)用動(dòng)態(tài)最小距離的多樣性保持策略，MOEA/PT的第二階段的算法流程如下。

輸入：

（1）第一階段的極值點(diǎn)搜索算法所保留的種群P。

（2）近似的極值點(diǎn)B。

步驟1生成新解。

從輸入種群P中隨機(jī)選擇兩個(gè)解，然后對(duì)這兩個(gè)解進(jìn)行模擬二進(jìn)制交叉（SBX）和多項(xiàng)式變異（polynomial mutation）操作生成新解y，重復(fù)以上步驟直至N個(gè)新解全部生成，并與父代解組成混合種群Q。

步驟2選擇解。

（1）首先將混合種群Q中的非支配解集Q1和支配解集Q2進(jìn)行分離。

（2）如果|Q1|≤N，Q1將全部保留進(jìn)P，在Q2中距離理想點(diǎn)Z*歐幾里德距離最近的N-|Q1|個(gè)解將會(huì)保留進(jìn)P。

（3）如果|Q1|≥N，利用近似的極值點(diǎn)B對(duì)目標(biāo)空間進(jìn)行空間劃分，即x,x∈Q1，如果 ?i,i∈{1,2,…,m}，滿足fi(x)≤Bi，這類解所組成的解集被標(biāo)記為內(nèi)部空間解集對(duì)于x,x∈Q1，如果 ?i,i∈{1,2,…,m}，使得fi(x)＞Bi，那這類解所組成的解集被標(biāo)記為外部空間解集

步驟3終止條件。

如果滿足終止代數(shù)條件，則終止算法并輸出P；否則，返回步驟1。

3.4 MOEA/PT的討論

高維多目標(biāo)優(yōu)化算法中，由于維度災(zāi)難，目標(biāo)空間的大小將隨著目標(biāo)數(shù)量呈指數(shù)增加。MOEA/PT在第一階段集中計(jì)算資源搜索邊界點(diǎn)，雖然在高維空間上Pareto支配的選擇壓力喪失，但是在邊界點(diǎn)的局部空間內(nèi)，Pareto支配關(guān)系仍然具有較強(qiáng)的選擇壓力，第一階段使種群快速收斂到PF附近。邊界點(diǎn)可以確定極值點(diǎn)，通過極值點(diǎn)可以確定內(nèi)部目標(biāo)空間和外部目標(biāo)空間。內(nèi)部空間的解被認(rèn)為是精英解，需要優(yōu)先選擇；外部空間的解由于已經(jīng)超過了極值點(diǎn)，說明其不在PF附近，將作為補(bǔ)充選擇加入到種群中。極值點(diǎn)搜索和劃分內(nèi)部外部空間有效提高了基于支配關(guān)系多目標(biāo)優(yōu)化算法的收斂性能。

當(dāng)內(nèi)部空間的非支配解的數(shù)量大于最大種群數(shù)量N，則說明此時(shí)演化算法已經(jīng)得到了足夠多收斂性較好的解，在第二階段使用動(dòng)態(tài)最小距離來選擇多樣性較好的解，由于內(nèi)部空間已經(jīng)被初步確定，在使用動(dòng)態(tài)最小距離選擇解時(shí)，比使用預(yù)設(shè)參考向量保持解集多樣性具有更大的靈活性，因此在具有不規(guī)則PF的高維多目標(biāo)優(yōu)化算法上將具有較好的性能。

在算法中，快速非支配排序需要O(mN2)的時(shí)間復(fù)雜度[10]，在動(dòng)態(tài)最小距離法中，計(jì)算距離每個(gè)解最近的解的距離d需要O(mN2)的時(shí)間復(fù)雜度，為每個(gè)解更新d的值最壞需要O(mN)的時(shí)間復(fù)雜度，因此，MOEA/PT的最壞時(shí)間復(fù)雜度為O(mN2)。

4 實(shí)驗(yàn)分析

本章在前三節(jié)介紹實(shí)驗(yàn)所采用的基準(zhǔn)測(cè)試問題、算法性能度量指標(biāo)以及算法的參數(shù)設(shè)置，在后兩節(jié)將通過兩組算法對(duì)比實(shí)驗(yàn)分別驗(yàn)證算法各個(gè)功能模塊的有效性以及算法的整體性能。

4.1 基準(zhǔn)測(cè)試問題

在本文實(shí)驗(yàn)中采用目前演化計(jì)算領(lǐng)域流行的高維多目標(biāo)測(cè)試問題集DTLZ[16]，該測(cè)試問題集是實(shí)際工程問題的高度抽象，包含實(shí)際工程高維多目標(biāo)優(yōu)化問題中多峰、偏倚、退化、不連續(xù)等各種特性，能夠測(cè)試所設(shè)計(jì)算法的各種性能，且可以根據(jù)需求拓展不同的優(yōu)化目標(biāo)數(shù)，一直是高維多目標(biāo)優(yōu)化算法設(shè)計(jì)所使用的主流測(cè)試問題。本文實(shí)驗(yàn)中將目標(biāo)數(shù)設(shè)置為4、5、6、8。對(duì)于決策變量數(shù)n，按照文獻(xiàn)[14]中n=m+r-1的形式進(jìn)行設(shè)置，其中m∈{4,5,6,8}，對(duì)于DTLZ1將r設(shè)置為5，對(duì)于DTLZ2～DTLZ6將r設(shè)置為10，對(duì)于DTLZ7將r設(shè)置為20。

4.2 性能指標(biāo)

在本文實(shí)驗(yàn)中，實(shí)驗(yàn)結(jié)果的性能度量指標(biāo)采用演化計(jì)算領(lǐng)域主流的反向迭代距離（inverted generational distance，IGD）[17]。IGD是指計(jì)算真實(shí)Pareto前沿上的點(diǎn)到求出的近似Pareto前沿的最小距離的平均值。式（7）中P*是真實(shí)Pareto前沿，P是算法近似的Pareto前沿，IGD定義為：

其中，dist(v,P)表示v到P中最近點(diǎn)的歐幾里德距離。

通過式（7）可以看出，優(yōu)化算法得到的近似Pareto前沿越接近真實(shí)Pareto前沿，并且在整個(gè)前沿上分布越均勻，那么計(jì)算出的IGD值就會(huì)越小。

4.3 比較算法和參數(shù)設(shè)置

算法對(duì)比實(shí)驗(yàn)采用領(lǐng)域主流的NSGA-II（a fast and elitist multiobjective genetic algorithm）[4]、GrEA（a grid-based evolutionary algorithm）[16]、NSGA-III（an evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach）[24]和 MOEA/DD（an evolutionary manyobjective optimization algorithm based on dominance and decomposition）[23]算法與本文提出的MOEA/PT算法進(jìn)行對(duì)比。

NSGA-II首先通過非支配排序?qū)⒋x擇的種群分層，隨后從第一層開始，依次將每一層所有的解加入到子代種群。當(dāng)種群數(shù)量將要超過事先設(shè)定的最大種群數(shù)量N時(shí)，應(yīng)用擁擠度距離排序?qū)⒕哂凶畲髶頂D度距離的解加入到種群。該算法是典型的基于支配的多目標(biāo)優(yōu)化算法，具有良好的魯棒性，但在處理高維問題上面臨收斂壓力喪失等缺點(diǎn)。

GrEA的第一步與NSGA-II相同，首先通過非支配排序?qū)⒎N群分層依次加入自帶種群。在最后一層的處理上，GrEA引入了格子支配關(guān)系和基于格子的多樣性保持策略，以此來提高算法的收斂性和多樣性。

NSGA-III同樣進(jìn)行非支配排序。在最后一層的選擇上，事先給定了一組參考點(diǎn)，通過將解與參考點(diǎn)綁定，在參考點(diǎn)的局部提高支配關(guān)系的效率，同時(shí)保持種群的多樣性。

MOEA/DD首先利用設(shè)定的參考向量將目標(biāo)空間分成一組子區(qū)域。在通過非支配關(guān)系確定待選擇種群的優(yōu)先級(jí)次序后，通過子區(qū)域中所有解的聚合函數(shù)值定義區(qū)域的擁擠程度和收斂程度。以此決定應(yīng)該從種群中刪除的解以最大化地保持精英種群。

對(duì)比算法參數(shù)均按照相應(yīng)的參考文獻(xiàn)進(jìn)行設(shè)置。算法在處理不同優(yōu)化目標(biāo)數(shù)時(shí)的種群規(guī)模如表1所示。

Table 1 Group size for algorithms表1 對(duì)比算法的種群規(guī)模

由于不同算法對(duì)種群有不同的要求，為了公平對(duì)比，在不同的目標(biāo)上設(shè)置不同的種群規(guī)模，并在相同的目標(biāo)上盡可能地采用相近的種群規(guī)模，所有算法都將進(jìn)行30萬次函數(shù)評(píng)估，并獨(dú)立運(yùn)行30次。對(duì)于MOEA/PT，交叉分布指數(shù)和多項(xiàng)式變異分布指數(shù)均為20，最大變異概率為0.1（n為決策變量個(gè)數(shù)）。

本文采用Wilcoxon秩和檢驗(yàn)對(duì)所得數(shù)據(jù)進(jìn)行顯著性測(cè)試。+和-分別表示在相應(yīng)測(cè)試問題上MOEA/PT顯著優(yōu)于或劣于該算法，如無則表示該算法與MOEA/PT相比無顯著性差異，粗體表示在相應(yīng)測(cè)試問題上該算法IGD均值最小。

4.4 MOEA/PT算法各個(gè)功能模塊的有效性驗(yàn)證

為了驗(yàn)證MOEA/PT算法中極值點(diǎn)搜索技術(shù)和基于動(dòng)態(tài)最小距離的多樣性保持機(jī)制這兩個(gè)功能模塊的有效性，設(shè)計(jì)了一組算法對(duì)比實(shí)驗(yàn)，將MOEA/PT算法與傳統(tǒng)的快速非支配排序算法（NSGA-II）以及MOEA/PT算法的修改版本MOEA/PT-1算法在8個(gè)目標(biāo)的DTLZ測(cè)試問題上進(jìn)行了對(duì)比，其中MOEA/PT-1算法與MOEA/PT算法的唯一區(qū)別在于多樣性保持策略上仍然采用了傳統(tǒng)的擁擠度距離策略。對(duì)比結(jié)果如表2所示，不難發(fā)現(xiàn)MOEA/PT和MOEA/PT-1相對(duì)于NSGA-II都取得了較小的IGD值，這說明兩種算法都取得了很好的收斂效果，這證明極值點(diǎn)搜索技術(shù)對(duì)于算法的收斂性是有效的。值得注意的是，相對(duì)于MOEA/PT-1算法而言，MOEA/PT算法在所有的測(cè)試問題上都取得了最優(yōu)的IGD值，這說明基于動(dòng)態(tài)最小距離的多樣性保持機(jī)制能夠有效地保持種群整體的多樣性。

Table 2 Comparison results of algorithms in 8-objectives表2 8個(gè)目標(biāo)的算法對(duì)比結(jié)果

4.5 MOEA/PT算法整體性能驗(yàn)證

為了驗(yàn)證MOEA/PT算法的整體性能，與3個(gè)當(dāng)前主流的高維多目標(biāo)優(yōu)化算法進(jìn)行比較，這些算法涵蓋了基于非支配排序策略、基于格子支配的策略、基于非支配排序和分解混合的策略等。實(shí)驗(yàn)結(jié)果如表3所示。

通過實(shí)驗(yàn)發(fā)現(xiàn)MOEA/PT在10個(gè)測(cè)試問題上取得了最優(yōu)的IGD值，MOEA/DD在8個(gè)測(cè)試問題上取得了最優(yōu)的IGD值，NSGA-III在3個(gè)測(cè)試問題上取得了最優(yōu)的IGD值。

MOEA/DD作為一種基于分解框架并引入支配關(guān)系的高維多目標(biāo)優(yōu)化算法，具有良好的收斂性能。又由于DTLZ1問題的PF是在第一象限的一個(gè)完整的超平面，DTLZ2～DTLZ4的PF都是位于第一象限的完整的超球面。MOEA/DD事先設(shè)定的一組參考向量位均勻地分布在第一象限的超平面上，與DTLZ1～DTLZ4的PF形狀相吻合。因此，MOEA/DD在DTLZ1～DTLZ4上取得了較好的結(jié)果。雖然MOEA/PT可以通過極值點(diǎn)搜索和動(dòng)態(tài)最小距離較好地保持種群的收斂性和多樣性，但是在DTLZ1～DTLZ4問題上所得解的均勻性不及MOEA/DD。但是在PF形狀不規(guī)則的問題上，因?yàn)镸OEA/DD事先設(shè)定的參考向量不能夠很好地吻合問題的PF，所以MOEA/PT得到了較好的結(jié)果。已經(jīng)說明了DTLZ5、DTLZ6的PF是退化的，DTLZ7的PF是不連續(xù)的，MOEA/PT在不同目標(biāo)數(shù)量的這類問題上均取得了最好的IGD值。另外對(duì)于DTLZ1～DTLZ4問題，雖然MOEA/PT沒有都取得最好的結(jié)果，但是其指標(biāo)值與最好的結(jié)果相差較小，這些結(jié)果都表明MOEA/PT在不同類型的問題上有更好的魯棒性。

Table 3 Comparison results of algorithms表3 算法對(duì)比實(shí)驗(yàn)結(jié)果

5 結(jié)束語

針對(duì)現(xiàn)有算法難以較好地解決具有不規(guī)則PF的高維多目標(biāo)優(yōu)化問題，而實(shí)際工程問題中這類問題廣泛存在，本文提出了一種基于Pareto支配關(guān)系的兩階段進(jìn)化高維多目標(biāo)優(yōu)化算法MOEA/PT。通過第一階段的極值點(diǎn)搜索技術(shù)縮小了目標(biāo)搜索空間，提升了算法的收斂壓力，在算法的第二階段通過Pareto非支配關(guān)系以及動(dòng)態(tài)最小距離的多樣性度量策略獲得一組在Pareto前沿上均勻分布的精英解。在實(shí)驗(yàn)部分，首先通過對(duì)比驗(yàn)證了算法各個(gè)模塊的有效性。然后通過與其他最新高維多目標(biāo)優(yōu)化算法的對(duì)比，表明了MOEA/PT在PF形狀不規(guī)則的問題上性能顯著優(yōu)于其他算法，而在PF形狀規(guī)則的問題上也取得了較好的結(jié)果。因此MOEA/PT能夠很好地解決PF形狀不規(guī)則問題的同時(shí)具有較好的魯棒性。在接下來的工作中，將考慮對(duì)MOEA/PT進(jìn)行擴(kuò)展以探究其在處理房地產(chǎn)領(lǐng)域?qū)嶋H的工程優(yōu)化問題時(shí)的算法性能。