采用放松支配關系的高維多目標微分進化算法

申曉寧，孫 毅，薛云勇

南京信息工程大學 信息控制學院，南京 210044

1 引言

近年來，多目標進化算法[1]（Multi-Objective Evolutionary Algorithms，MOEA）已經取得了飛速的發展，在許多方面都已有廣泛的應用。但現有的多目標進化算法一般是針對2到3個目標問題而設計。在現實生活中，隨著研究問題的復雜度越來越高，優化目標的個數也不僅僅局限于2到3個，有時往往會達到4個甚至更多。當優化問題的目標個數達到4個及以上時，稱這類優化問題為高維多目標優化問題[2]（Many-Objective Optimization Problems，MaOPs）。隨著目標維數的增加，傳統多目標進化算法（MOEAs）的優化效果大大降低。主要原因有：（1）隨著目標維數的增加，傳統的Pareto支配關系難以區分出不同解之間的優劣，導致基于Pareto支配關系的多目標進化算法收斂性能下降；（2）隨著目標維數的增加，傳統多目標進化算法為了保證算法所得解集的多樣性，采用的多樣性保持機制通常偏好極端個體，這將進一步影響算法在高維多目標優化問題上的搜索能力。因此，如何針對高維多目標優化問題，設計出一種在收斂性能和多樣性之間達到較好平衡的進化算法，成為進化計算領域的一個難點和熱點問題。

目前所提出的高維多目標進化算法主要分為如下幾類：（1）采用基于Pareto支配的方法，在該方法基礎上結合其他有效方法以縮小搜索空間或降低目標維數。如在搜索過程中加入決策者的偏好信息以縮小Pareto前沿區域[3]，Deb等人提出了基于主成分分析的目標縮減方法[4]，并將其結合到NSGA_II[5]算法中。然而，該類方法只適用于能夠預知偏好信息或目標主次的問題。與該方法類似，學者袁家偉提出了一種基于Simplex支配的方法[6]。該方法相比于Pareto支配的方法，其優點是遠遠提高了解的選擇壓力，缺點是缺少高效的機制用于維持群體的多樣性。（2）采用放松的Pareto支配方法，使得原先無法兩兩比較優劣的非支配個體之間能夠進行比較與選擇。如優勝關系[7]，改進的α-支配[8]等，該方法在一定程度上放寬了非支配個體之間的比較準則，增加了解的選擇壓力，但同時也降低了支配結果的合理性與可信性。（3）采用非Pareto的支配方法，該類方法采用新的評價準則對個體進行比較。目前該方法主要有兩類，一類是基于聚合函數的方法，該方法使用聚合函數，將一個高維多目標優化問題分解成一系列單目標優化問題，典型的算法是MOEA/D[9]。另一類是基于評價指標的方法，該方法采用一個指標作為個體的適應度來評價個體，典型的算法是IBEA[10]。該方法能夠解決基于Pareto支配所帶來的問題，然而其合理性有待進一步驗證，且在實際應用中還存在著計算復雜度高等問題。

微分進化算法是一種簡單、高效和快速的演化算法，具有結構簡單，易實現，精確度高、收斂速度快、魯棒性強等優點[11]。它的控制參數少、便于學習、空間復雜度低、便于擴展，可以處理更大范圍、更加重要的優化問題。因此，現在越來越多的學者開始將微分進化算法運用到高維優化問題中。王旭提出了一種解決高維優化問題的差分進化算法[12]，將協同進化思想引入到差分進化領域，采用一種由狀態觀測器和隨機分組策略組成的協同進化方案。該方案有效地增強了算法解決高維優化問題的搜索速度和能力。

為了進一步提高進化算法在求解MaOPs時的收斂性能和多樣性，本文提出采用放松支配關系的高維多目標微分進化算法，簡稱RDMODE（differential evolution algorithm for many-objective using relaxed dominance relation）。在12組標準測試函數中的仿真對比結果表明了所提算法的有效性。

2 高維多目標優化問題的難點

假設求解具有m個目標的最小化問題，則多目標優化問題的數學模型可以描述如下：

其中，x為決策向量，y為目標向量，X為決策向量x形成的決策空間，Y為目標向量y形成的目標空間。gi(x)≤0,i=1,2,…,h為 x需滿足的h個約束條件。當目標維數m≥4時，即為高維多目標優化問題MaOPs。

求解多目標優化問題時，最常采用的是基于Pareto支配關系的比較方法。設Xf為多目標優化的可行解集，F(x)=(f1(x),f2(x),…,fm(x))為目標向量，x1∈Xf，x2∈Xf。稱 x1Pareto支配 x2（簡稱支配，記作 x1?x2）當且僅當

在MaOPs的求解中存在如下難點：（1）隨著目標維數的增加，如果仍采用常規的Pareto支配關系，將導致群體中非支配個體所占的比例迅速上升，個體間難以區分優劣，算法的選擇壓力過小，進化選擇近似為隨機選擇而失去優勝劣汰的作用。（2）當優化目標大于3個時，算法得到的解集無法在傳統的直角坐標系中表示出來，因而增加了可視化的難度，為決策者的最終選擇制造了障礙。（3）目標維數的增加使得近似Pareto最優前沿解的個數劇增，不利于決策者在如此龐大的集合中，找出滿足其需要的解。（4）當使用大規模的進化種群時，能夠在一定程度上緩解因目標維數增加而導致的進化算法收斂性能的下降，也可能得到近似分布在整個最優前沿的解集，但隨之而來的是空間復雜度和時間復雜度的劇增。

3 基于放松支配關系的高維多目標微分進化算法

3.1 rel-支配的放松Pareto支配關系

本文提出一種稱為rel-支配的放松Pareto支配關系。假設求解高維多目標最小化問題，設x1和x2為MaOPs可行解集 Xf上兩個不同的解，F(x)=(f1(x),f2(x),…,fm(x))為目標向量，稱x1rel-支配x2當且僅當

其中，m為MaOPs中的目標個數。如果一個解x∈Xf不受Xf中任何其他解rel-支配，則稱x為該問題中的rel非支配解。

由于目標維數越高，解之間越難進行比較，因此，所提rel-支配關系對Pareto支配關系的放松程度依據目標維數m的不同取值而作自適應調整，具體見圖1所示。圖1的縱坐標表示放松程度，該取值越小，說明rel-支配關系對Pareto支配關系的放松程度越大。當給定問題的目標維數m≤4時，此時兩兩解之間容易比較優劣，故縱坐標的取值接近于1，即rel-支配關系的放松程度很小；當m＞4時，此時比較出兩兩解之間優劣的難度逐漸加大，故rel-支配關系的放松程度隨m的增大而逐漸增大。由式（3）也可以看出，隨著m的增大，(1-e-20/m)取值減小，即rel-Pareto的放松尺度增大。此外，式（3）未引入額外的參數，避免了ε-支配關系[13]中，參數ε需要事先手工確定的不足。

圖1 rel-支配關系中解的放松程度隨著目標個數變化的曲線

圖2 給出了基于rel-支配關系比較兩個解x1和x2的示意圖。由圖可見，如果基于Pareto支配關系，x1和x2互不支配，但如果采用放松后的rel-支配關系，使得解x1相對于解x2在目標 f1上的值由原來的大于關系變成小于，在目標 f2的值比原來更小，即經過rel-支配關系后，解x1由圖中所看到的位置變成了解x′1在圖中的位置，則此時解x1顯然能夠rel-支配解x2。

圖2 基于rel-支配關系比較兩個解x1和x2

綜上所述，本文采用rel-支配關系能夠更加有效地區分出個體之間的優劣，增加選擇壓力，以改進常規Pareto支配關系帶來的群體中非支配解過多的不足，將其運用到高維多目標微分進化算法中，能夠更加有效地引導算法的搜索方向，從而提高算法的搜索效率。

3.2 群體與外部存儲器的協同進化

所提算法RDMODE采用一個群體POP和一個外部存儲器Archive協同進化的策略。Archive中保存由歷代群體搜索到的rel非支配解。在Archive中精英個體染色體信息的指導下，對POP分別采用兩種變異方式，生成子代群體。利用生成的子代群體，采用基于指標的方法更新POP使得POP能夠較快地向問題真實的Pareto前沿收斂；將子代群體搜索到的rel非支配解對Archive更新，并采用基于Lp-范數距離的多樣性維護策略裁剪Archive，使得Archive的規模不超過預先設定的大小，并保持良好的多樣性。POP和Archive相互輔助、相互促進，共同推動算法在收斂性和多樣性之間維持平衡。

在子代群體生成的過程中，首先對POP采用DE/rand/2變異策略和二項式交叉策略，生成子代群體NPOP1。因為該策略采用隨機搜索方式，有利于算法探索到更多的解，提高算法的多樣性。DE/rand/2變異策略和二項式交叉策略的表達式分別如式（4）和式（5）所示：

其中，變異策略DE/rand/2中的3個隨機個體 xr1、xr3、xr5取自POP，另兩個 xr4、xr2取自Archive，，以充分利用Archive中個體的優良遺傳特性，并且增強所生成子代個體的多樣性。變異因子F是區間[0.8，0.9]內均勻產生的隨機數，Vi是經過變異后得到的中間個體，randj[ ]0,1 為[0，1]之間滿足均勻分布的隨機數。當randj[ ]0,1小于等于給定的交叉概率CR或 j=jrand（Vi,j為中間個體Vi的第 j維，j=1,2,…,n,n為決策變量的維數，jrand為從{ }1,2,…,n中均勻隨機產生的整數）時，將變異得到的中間個體Vi的第 j維作為子代個體Ui的第 j維，否則，將原來的父代個體xi第 j維作為子代個體Ui的第 j維。

對POP再采用DE/current-to-best/1變異策略和二項式交叉策略，生成子代群體NPOP2。該策略將群體POP中的當前個體作為初始個體，將外部存儲器中的精英個體作為指導個體進行變異操作，有利于增加算法的收斂速度，避免陷入局部最優。式（6）給出了DE/current-to-best/1變異策略的表達式，二項式交叉策略表達式同式（5）。

其中，變異策略DE/current-to-best/1中的兩個隨機個體xr2、xr3和當前個體xi取自POP，xbest個體隨機取自Archive，，變異因子 F1、F2是區間[0.8，0.9]內均勻產生的隨機數，該策略生成子代群體的方式同上。

為了加強算法的收斂性能，采用基于指標的方法計算POP∪NPOP(NPOP=NPOP1∪NPOP2)中每個個體的適應度，并對群體進行更新，生成新一代群體POP。令Iε+表示一個指標，該指標描述了在目標空間中，一個解支配另一個解所需要的最小距離[10]。

根據這個指標為個體分配相應的適應值，式（8）給出了個體x1的適應值計算方法[14]：

對群體進行更新時，將適應值小的個體依次從群體中移除，直到滿足規定的群體規模為止。

在生成新的外部存儲器的過程中，采用了基于Lp-范數（0

其中，d表示數據空間的維數，Lp(x,y)表示在d維數據空間中，向量(x1,x2,…,xd)與向量(y1,y2,…,yd)之間的Lp-范數距離。

當Archive中的個體數量超出規定的容量時，首先將Archive中在每個目標上具有最大/最小目標值的個體加入一個空的外部存儲器Archive′中，然后每次從Archive中，選擇距離Archive′中現有個體最短Lp-范數距離值最大的個體加入Archive′，如此反復直到Archive′中解的個數滿足規定的容量為止。該策略能夠有效地維護外部存儲器中個體的多樣性。

3.3 算法步驟

所提算法RDMODE詳細步驟如下：

步驟1初始化。設置算法的最大目標評價次數為nmb_obj_max。隨機產生一個規模為N的初始群體POP并計算其目標值，令目標評價次數計數器nmb_obj=N，規定nArchive為外部存儲器最大保留個數，求出POP中的rel非支配解并將其存于Archive中。

步驟2繁殖操作。分別對POP利用不同的變異、交叉策略生成子代群體NPOP1和NPOP2。累計目標評價次數為表示集合中元素個數）。

步驟3求出子代中的rel非支配解。令NPOP=NPOP1∪NPOP2，求出NPOP中的rel非支配解。

步驟4更新與裁減POP和Archive。令POP=，若，則采用基于指標 Iε+的方式更新POP。確定出中的rel非支配解，并賦給Archive，若，則采用基于Lp-范數距離的多樣性維護策略對Archive進行更新。

步驟5終止準則判斷。如果目標評價次數nmb_obj達到對應問題的nmb_obj_max，則終止算法，把當前外部存儲器Archive作為最終的滿意解集輸出，否則轉到步驟2。

3.4 算法的計算復雜度

在MaOPs中，隨著目標個數的不斷增多，算法的計算復雜度也越來越大。采用一個含有m個目標，群體規模為N的多目標優化問題作為例子。所提算法RDMODE的計算復雜度主要包括以下幾個方面：（1）從生成的子代群體中確定rel非支配解其復雜度為O(mN2)；（2）采用基于指標的方式更新POP，它的復雜度為O(N2)；（3）采用rel支配關系更新Archive，它在比較個體間支配關系時的復雜度為O(Nlg(m-2)N)，在計算個體間的Lp-范數距離以維護多樣性時的復雜度為O(mN2)。綜上，該算法總的復雜度為max{O(Nlg(m-2)N),O(mN2)}。

4 仿真實驗

4.1 優化問題描述

為了驗證所提算法RDMODE的有效性，將其用于DTLZ1和DTLZ2這兩類目標可擴展的測試問題上[16]。本實驗在DTLZ1和DTLZ2中，將目標個數m分別取為m=3，5，8，10，15，20。因此，實驗中一共包括了12個不同的高維多目標測試函數。

4.2 參數設置

Two_Arch2[14]是近年來涌現出的一種具有代表性的高維多目標進化算法。文獻[14]將Two_Arch2與其他已有的高維多目標進化算法Two_Arch[17]、IBEA、NSGA_III[18]、MOEA/D進行比較，以測度IGD[19]作為評判標準，實驗結果表明Two_Arch2在收斂性和分布性能方面均優于上述對比算法。NSGA_II[5]是一種經典的快速非支配排序多目標精英遺傳算法，已成功應用于多種實際多目標優化問題中。將所提算法RDMODE與Two_Arch2、NSGA_II在4.1節中的測試函數上進行對比實驗。所提算法的參數設置依據實驗結果調試得到，算法Two_Arch2的參數設置參照文獻[14]，算法NSGA_II的參數設置參照文獻[16]，各算法參數具體設置見表1。

表1 3種算法的參數設置

為了體現算法比較的公平性，3種算法的終止準則均采用目標向量評價次數達到給定的最大值，最大目標向量評價次數對不同的測試問題，以及不同的目標個數m，取不同的值，參數具體設置見表2。

4.3 實驗比較

使用測度IGD、測度C_Metric[20]以及作圖法，將RDMODE與Two_Arch2、NSGA_II進行比較。測度IGD描述了問題真實Pareto前沿中的個體到算法搜索到的解集中個體的平均最短距離，它的值越小，說明算法獲得的解集收斂性和分布性越好，即越接近于真實的Pareto前沿。測度C_Metric度量兩種算法搜索到的近似Pareto非支配解集間相互支配的程度，C(X1,X2)＞C(X2,X1)表明集合X1在C測度上的性能優于X2。

表2 3種算法在測試函數上取不同目標時的最大目標評價次數設置

圖3、圖4分別給出了各算法在DTLZ1和DTLZ2，取m=3時，由100個解構成的Pareto前沿。由圖4可以看出RDMODE和Two_Arch2均能收斂到真實的Pareto前沿，但所提算法RDMODE得到的解的分布性更好。從圖5中可以看出，RDMODE和Two_Arch2算法無論是在收斂性上還是在分布性上效果都遠比NSGA_II好。由此可見，在MaOPs中，僅靠Pareto支配排序已不能區分出個體的優劣。同時，個體選擇壓力的丟失也會導致分布性選擇策略的失效。Li等人[21]的實驗結果表明，NSGA_II中的擁擠距離策略甚至會在MaOPs上對群體的進化起到反作用。

將3種算法分別在12個測試函數上獨立運行10次。表3給出了3種算法在測度C_Metric上的平均值和標準差。

從表3可以看出，所提算法RDMODE在12組測試函數中得到的C_Metric值，總體上顯著優于其他兩種算法得到的C_Metric值。在DTLZ1上，除了在目標個數為5時，算法Two_Arch2得到的C_Metric值較大外，其余情況下所提算法RDMODE均具有更大的C_Metric值，即有更高的支配比例；在DTLZ2中，當目標維數m取3或5時，Two_Arch2的C_Metric值更優于其余兩種算法，隨著目標維數的不斷增加，所提算法RDMODE有最好的C_Metric值，尤其當目標維數m≥10時，所提算法得到的解集，能夠支配Two_Arch2解集中解的比例較大，而Two_Arch2支配所提算法解集的比例為0；由于較差的收斂性，算法NSGA_II在所有測試函數中的C_Metric值最差。這也驗證了在高維多目標優化問題中，所提算法RDMODE的收斂性總體上較其余兩種算法的收斂性要好。

表4給出了3種算法在測度IGD上的平均值和標準差。

從表4可見，在DTLZ1中，當目標維數m取3、5、8時，所提算法RDMODE較Two_Arch2有更好的IGD平均值，其余情況下算法Two_Arch2的IGD平均值更好；在 DTLZ2中，當目標維數 m 取 3、5、8、10時，算法Two_Arch2優于RDMODE，有相對不錯的IGD平均值，當目標維數m＞10時，所提算法RDMODE得到的IGD平均值最好；由此可見，所提算法對于DTLZ1中目標個數相對較小的函數，能夠取得較好的IGD性能，而對于DTLZ2卻在目標個數較大時獲得更優的IGD性能。由于NSGA_II的進化機制不能適應MaOPs的高維環境，它得到的IGD平均值在12個測試函數上依然最差。此外，所提算法RDMODE在絕大部分測試函數上得到的標準差均最小，表明了所提算法具有較穩定的搜索性能，在不同運行次數中得到數據集的IGD值變化幅度較小。

圖3 3目標DTLZ1問題中Pareto前沿的比較

圖4 3目標DTLZ2問題中Pareto前沿的比較

表3 兩兩算法在DTLZ1、DTLZ2上的C_Metric值

表4 各算法在DTLZ1、DTLZ2上的IGD值

由上述結果可見，所提算法RDMOEA是一種高效的高維多目標進化算法。在大部分測試函數，尤其在目標維數較高的函數上，得到的解集較已有的代表性高維算法Two_Arch2具有更好的收斂性和多樣性。這主要歸因于所提算法RDMOEA采用了一種新的放松支配關系，有效地增加了群體的選擇壓力，提高了算法的收斂速度；同時，所提算法RDMOEA采用群體和外部存儲器協同進化的方式，由于外部存儲器能夠給群體的進化方向提供指導信息，而生成的子代群體采用基于指標的適應度評價機制更新進化群體和采用Lp-范數距離的多樣性維護策略更新外部存儲器，兩者相互合作，共同促進，使得所提算法RDMOEA能夠在收斂性和多樣性之間維持較好的平衡。

5 結束語

本文提出了采用放松支配的高維多目標微分進化算法RDMOEA，該算法設計了一種rel支配關系放寬解的比較準則，該關系能夠依據目標個數自適應地調整對Pareto支配的放松程度，且未引入額外的參數；采用群體和外部存儲器協同進化的方案增加了算法的搜索速度和搜索效率，并使用混合微分進化算子搜索解空間。將所提算法RDMOEA和其余兩種優秀的多目標進化算法在目標可擴展的標準測試函數集DTLZ1和DTLZ2上進行了對比，實驗結果表明所提算法RDMOEA在求解MaOPs時，能夠產生一組收斂性能和分布性能均較優的非支配解，從而表明算法所設計的策略是可行而有效的。今后的工作將進一步研究所提算法RDMOEA中參數的自適應控制方法，并將它應用于實際優化問題。