Pareto支配關系下兩階段進化高維多目標優(yōu)化算法*

郭曉彤，李玲燕+，朱春陽

1.西安建筑科技大學 管理學院，西安 710055

2.南京航空航天大學 計算機科學與技術學院，南京 211106

1 引言

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

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

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

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

定義1（理想點Z*）

定義2（Pareto極值點B）

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 算法設計

3.1 算法總體框架

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

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

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

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

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

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

3.3 算法的第二階段

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

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

Fig.2 Schematic diagram for nadir point B圖2 極值點B的示意圖

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

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

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

輸入：

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

（2）近似的極值點B。

步驟1生成新解。

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

步驟2選擇解。

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

（2）如果|Q1|≤N，Q1將全部保留進P，在Q2中距離理想點Z*歐幾里德距離最近的N-|Q1|個解將會保留進P。

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

步驟3終止條件。

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

3.4 MOEA/PT的討論

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

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

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

4 實驗分析

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

4.1 基準測試問題

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

4.2 性能指標

在本文實驗中，實驗結果的性能度量指標采用演化計算領域主流的反向迭代距離（inverted generational distance，IGD）[17]。IGD是指計算真實Pareto前沿上的點到求出的近似Pareto前沿的最小距離的平均值。式（7）中P*是真實Pareto前沿，P是算法近似的Pareto前沿，IGD定義為：

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

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

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

算法對比實驗采用領域主流的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算法進行對比。

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

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

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

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

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

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

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

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

4.4 MOEA/PT算法各個功能模塊的有效性驗證

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

Table 2 Comparison results of algorithms in 8-objectives表2 8個目標的算法對比結果

4.5 MOEA/PT算法整體性能驗證

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

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

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

Table 3 Comparison results of algorithms表3 算法對比實驗結果

5 結束語

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