一種確定目標域多目標優化算法NSGA/P

馬暢暢，汪 坤，鹿曉夢，陳未如

(1.沈陽化工大學 計算機科學與技術學院，遼寧 沈陽 110142；2.遼寧省化工過程工業智能化技術重點實驗室，遼寧 沈陽 110142)

0 引 言

在現實工程中，會遇到一些多目標優化問題。在這類問題中，需要同時滿足兩個或者更多的目標要求，但是極不可能出現每個目標同時都能達到最優的情況，一個目標的改善可能會引起另一個或者幾個目標指標的降低。因此，尋求絕對最優解是不現實的，但存在一個Pareto最優解集[1]。

由于進化算法能夠有效解決多目標優化問題，所以通過對多目標優化問題和進化算法相結合的多目標進化算法[2](multi-objective evolutionary algorithm，MOEA)成為當下熱門的研究方向。目前解決多目標問題的幾大方式主要有：基于Pareto支配關系的算法[3]、基于分解的算法[4]和基于評價指標的算法，其中最經典、最具影響力的算法是MOEA/D[5]和NSGA-II(nondominated sorting genetic algorithm II)。

NSGA-II是2002年Kalyanmoy Ded等人提出的基于支配關系的多目標進化算法。隨著進化算法[6]的不斷發展，通過對NSGA-II與其他多目標優化算法[7]進行比較和分析，發現NSGA-II算法容易早熟，算法運行效率不夠高，種群收斂性不夠好并且全局搜索能力一般，尤其是在超多目標優化問題的求解上更顯不足[8]。

因此一些研究人員在NSGA-II基礎上提出了一些改進算法，如NSGA-III[9]，其中NSGA-II中的快速非支配排序算子、擁擠度比較算子[10]以及精英保留策略保留了下來，NSGA-III算法在精英保留策略的基礎上采用參考基準的思想替換擁擠距離選取辦法，能夠在滿足解分布的條件下解決超多目標優化問題[11-12]。

針對NSGA-II的缺欠，該文借鑒基于投影面的多目標進化算法MOEA/P[13]的投影面思想，改進NSGA-II，從而提高該算法的計算效率、收斂性與解的分布性。

1 確定目標域的多目標問題概述

以最小化問題為例，一般情況下，確定目標域的多目標優化問題(MOP with definite object domains)是求一組決策變量,使其不僅滿足g、h約束條件,并且使m個目標函數在確定域內最優化，數學表達如下：

minimizeF(X)={f1(X),…,fm(X)}T

Subject toG(X)={g1(X),…,gj(X)}T,gj(X)≥0,j=1,…,J

H(X)={h1(X),…,hK(X)}T,hK(X)=0,k=1,…,K

X={x1,…,xn}T∈Ω

F∈Φ

(1)

對于確定目標域的多目標優化問題求解可以采用常規MOP算法，然后在解集中選取滿足目標域需求的解；也可以把目標域確定范圍作為約束條件，將問題轉為一般帶約束的MOP。前一種方法是在全局范圍內進行求解，求解效率和求解質量相對較低；第二種方法將目標與作為約束條件，大大降低了求解效率。然而，目標函數確定域作為一種特殊的約束，一定存在某種方法比常規算法有更好的性能。由于目標函數確定域的各目標函數的取值范圍是指定的，所以該文提出NSGA/P算法，它可以限定種群進化方向，進一步提高算法運行效率。

2 NSGA-II算法

NSGA-II算法是在NSGA基礎上做出了改進。首先父代種群Pt通過交叉變異操作生成子代種群Rt，利用快速非支配排序根據每個個體的非劣解水平對種群進行分層。先找出種群中的第一層非支配解集，并將這個解集從群體中刪掉，接著找出剩下群體中第二層非支配解集，不斷找出下一層非支配解集，重復這個過程，直到群體都被分層。分到同一層中的個體要根據個體擁擠距離進行排序。規模為N的父代種群和子代種群會組成一個規模為2N的新種群，根據快速非支配層及擁擠距離排序選擇出N個優秀個體成為新父代。這一過程如圖1所示。

圖1 NSGA-II算法過程圖

NSGA-II算法通過增加精英保留策略、計算擁擠度距離和快速非支配排序策略[14]，解決了NSGA算法計算復雜度高，運行效率低，多樣性和收斂性不夠好等缺點。然而，由于NSGA-II算法的核心是根據支配關系進行個體的排序，在超多目標優化問題中，這種排序策略對個體的優先次序分辨度明顯不足。

3 基于投影面的多目標進化算法MOEA/P

基于投影面的多目標進化算法MOEA/P可以面向目標決策支持，在指定方向上進行專門有效的求解。MOEA/P本質上采用的是基于分解的多目標進化算法思想，該算法與其他基于分解的多目標進化算法的不同之處是以降維方式將多維目標進行分解處理。它將目標空間劃分為兩部分：投影面和自由維，并且把投影面分割成多個投影格，然后在各個投影格上求解自由維的最優值，在求解最優值過程中，采用合適的適應度函數和空間壓縮的進化算法，將種群個體壓縮到投影目標空間內，從而得到多目標優化問題的最優解。這種方式既能夠保證求解的精度，還能大大提高算法求解效率，又能夠滿足用戶決策支持需求。

該文提出的確定目標域多目標優化算法NSGA/P是將NSGA-II算法與MOEA/P算法思想結合在一起。MOEA/P算法目的是對多目標優化問題進行降維處理，把目標空間分解成自由維和投影面兩部分，以確定目標域為投影面，根據設置的目標域求解范圍來求解最優值，采用NSGA-II算法在投影面目標域求解范圍內對自由維進行相應的優化求解。這種求解方式不僅緩解了全局計算的壓力，在保證求解效率的同時還保證了解集質量，又滿足了用戶的決策需求，從而逐步得到目標域限定下多目標優化問題的最優解。

投影面設置是NSGA/P算法主體的第一步，它將確定目標域作為一個投影面。例如在三目標優化問題上，決策者可以在第一個決策目標和第二個決策目標有期望范圍，即選取前兩維作為投影面，采用固定的投影格邊長對投影面進行均勻分割。投影格是由相應的投影格標識向量表示，在投影格中確立求解方向，采用空間壓縮進化方法，將種群進化中的個體向投影目標空間壓縮，進而求出多目標優化問題的Pareto最優解。

4 NSGA/P算法框架

該文重點研究確定目標域的多目標優化算法NSGA/P。

(1)首先生成一組個體數量為N的隨機種群，確定好目標域。

(2)將目標域所在的目標維組成投影面，其余維作為自由維。

(3)對投影面的根據目標域范圍進行投影格分割，如圖2所示。

(4)在各個投影格上，分別通過NSGA-II算法求解自由維的解集。

此處，NSGA/P算法與NSGAII算法的區別就在個體的排序上。NSGAII完全是根據個體的Pareto支配關系對個體進行排序分層，而NSGA/P同時考慮個體與投影格間的距離及個體間的支配關系。

圖2 目標域投影格

為此，NSGA/P算法設置兩個隊列。第一隊列是按個體與投影格距離排序的隊列。所有沒有落到投影格范圍內的個體在此排隊；第二隊列是根據Pareto支配關系及擁擠距離按NSGAII的方法進行分層排序的隊列。所有落入相應投影格內的個體在此排隊。進化過程中個體在這兩個隊列間轉換，從最初的大多在第一隊列逐步轉移到第二隊列。

(5)根據精英保留策略，每個隊列都選取排序前N的個體。

(6)達到進化終止條件，整個進化過程結束，輸出第二隊列中當前Pareto等級最高的所有個體，即為問題求解的最優解集。

NSGA/P算法框架

輸入:

·確定目標域的多目標問題MOP；

·DS:目標決策空間(投影面)設定；

·E:最大進化代數；

·N:初始種群大小。

輸出:目標解集RS

過程：

步驟1：目標空間歸一化。

步驟2：在投影面上求非支配解。

步驟2.1 初始化種群：

初始化大小為N的種群G，構造種群中個體并初始個體基因序列，對種群G每個個體進行初始計算，得到相應的目標函數值。保證所有個體滿足MOP約束條件：如果不滿足MOP，重新生成，直到G.size=N。

步驟2.2 確定目標域及投影面，并進行參考點[15-16]的選取：

根據DS確定投影面和目標域，均勻分割目標域并設置參考向量[17]。

步驟2.3 種群進化：

如果已經進化E代，或達到其他結束條件，轉步驟2.4；

分別對種群G中的個體進化操作；

父子代合并后，計算個體與在最近的參考向量的距離，將該距離與個體間的支配關系組合，據此進行快速排序；

選取排序前N的個體，組成新的G。

重復步驟2.3。

步驟2.4 提交進化結果：

將G中所有非支配個體提交到RS，并保證不與RS中任何現有個體相互Pareto支配。若存在Pareto支配關系對，從RS中刪去被支配的個體。

步驟3：輸出RS。

5 NSGA/P算法過程圖

NSGA/P算法過程圖如圖3所示。

6 實驗及討論

6.1 測試用例

該文選取了廣泛應用的ZDT系列和DTLZ系列[18]作為測試函數，主要是ZDT1-ZDT4、ZDT6及DTLZ1-DTZL4對該算法進行測試。

通過實際最優解與真實的Pareto前沿進行對比，可以驗證出NSGA/P算法的收斂性與分布性。采用Java語言，在Intel Core i5-10210U CPU @1.60 GHz環境下運行。為了簡潔方便，本實驗全部采用最后一維作為自由維，其余目標維構成投影面。

圖3 NSGA/P算法過程圖

對于ZDT的二目標問題，采用投影的思想將第一維設置為投影維，在確定目標域內進行實際的求解。第一維函數f1的取值設置在[0.2，0.8]這個區間，對第二維函數f2取值不約束。將實驗種群大小設置為N=60，最大進化代數E=250。算法運行結果如圖4所示。

圖4 NSGA/P算法對ZDT1、ZDT2、ZDT3、ZDT4、ZDT6的求解結果

通過對ZDT測試案例上的實驗結果進行比較分析，得出基于投影的NSGA/P算法在確定目標域的范圍內所求的最優解與真實的Pareto前沿逼近，算法收斂性效果較好，求得的最優解分布性也較好。

針對DTLZ問題，先求取三目標問題，將第一維和第二維設置為投影維，將第三維設置為自由維，接下來在投影面上進行求解。將第一維f1和第二維f2取值設置在[0.2,0.8]區間，對第三維f3取值不做約束。將實驗種群大小設置為N=100，進化代數設置為E=250，運行結果如圖5所示。

圖5 NSGA/P算法對DTLZ1、DTLZ2的求解結果

通過對DTLZ測試案例上的實驗結果進行比較分析，得出本算法在三維目標上也滿足了求解的精度，分布性和收斂性都表現良好。

6.2 性能評價指標

為了驗證算法性能，選用了CPU運行時間作為考察依據。并且選擇了反向迭代距離IGD指標[19]作為評價算法的分布性和收斂性的重要依據。其中P*代表真實的PF解集，P是近似解的集合。IGD計算P*到P的平均距離公式如下：

(2)

在超多目標問題中，并且無真實Pareto前沿的情況下，NSGA/P算法借鑒了MOEA/P算法中特有的評價指標自由維誤差和投影誤差，使NSGA/P算法性能分析更有意義。相關指標如下：

自由維誤差δd：算法求得近似解集ND中的非支配解的自由值與理想值距離的算術平均值：

(3)

其中，f和r分別表示解對應自由值和相應的理想值對應的自由維向量值，D是自由維向量數。算法所求的解與理想解越近越好。

投影誤差δp：目標個體與其投影點附近所有理想值之間的平均距離：

(4)

其中，Dp是投影維個數。投影誤差δp可以同時反映算法的多樣性和收斂性。

6.3 算法測試結果

6.3.1 種群大小對算法性能的影響

在進化代數E=250，種群大小N在20～100范圍內，目標域f1[0.2，0.8]，測試算法運行時間以及IGD評價指標結果，如表1所示。

表1 種群大小對CPU時間(秒)、反向迭代距離的影響值

測試結果表明種群大小直接影響算法效率和解的質量，算法運行時間與種群大小成正比，與IGD評價指標成反比。尤其在ZDT3和ZDT4測試問題上，隨著種群的增大，IGD表現得越優秀，解的分布性和收斂性越好。

6.3.2 進化代數對算法性能的影響

在進化代數E分別為50～300，種群大小N=60，目標域f1[0.2，0.8]的情況下，通過實驗進行相應比較分析，測試結果如表2所示。

表2 進化代數對CPU時間(秒)、反向迭代距離的影響值

測試結果顯示算法運行時間基本上與進化代數呈線性關系，IGD值隨種群增大而減小，最后趨于一定值，并在進化到大概150代的時候，基本實現最優解的求取。

6.3.3 確定目標域范圍對算法性能的影響

在種群大小N=100，進化代數E=250，不同目標域范圍內進行實驗。本次測試三目標問題，在f1、f2上設置同等的決策空間，分別為S1[0，1]、S2[0.1，0.9]、S3[0.2，0.8]、S4[0.3，0.7]，S5[0.4，0.6]五種范圍進行測試，結果如表3所示。

表3 目標域范圍對CPU時間(秒)、反向迭代距離的影響值

實驗結果表明，相同種群大小在越小的目標域內所得的最優解集質量越高(計算IGD時，在真實解集上同樣選取目標域范圍內的解進行計算，由于DTLZ1測試問題在S4和S5范圍內取不到真實解，因此不做這兩個實驗)。

接下來使用測試函數DTLZ(1～4)進行超多目標實驗，實驗初始種群N=500，最大進化代數E=500，目標域為[0,1]。依次測試目標個數M為4到8時的最優化求解情況，每組實驗均將前兩維f1、f2作為投影面，剩下各維設為自由維，實驗主要考察求解質量、求解效率和投影誤差，全部運行10次取均值作為實驗結果。實驗表明隨著目標個數的增加，投影誤差值逐漸增大，但投影誤差仍在一個較小的范圍內，同時隨著目標個數的增加求解時間也有所增長，這是超多目標問題下難以避免的情況。CPU時間與誤差δd的運行結果如表4所示。

表4 超多目標優化問題解的投影誤差δd值、CPU時間

6.3.4 實驗對比

對比現有的一些求解超多目標算法MOEA/P，NSGA-III和MOEA/D進行超多目標問題實驗，每種算法種群大小N=500，最大進化代數E=500，在目標域為[0,1]進行測試，對比實驗求解的IGD值和CPU運行時間結果如表5所示。

表5 超多目標算法求解IGD值、CPU時間

實驗結果顯示NSGA/P的求解質量普遍優于其他算法，在時間效率上也優于NSGA-III和MOEA/D，但在某些測試問題上時間效率稍微落后于MOEA/P。

通過以上實驗對比發現，NSGA/P算法總體效果表現良好，具有很好的魯棒性，適用于解決多目標優化問題，也證明了NSGA/P在求解超多目標問題的有效性。

7 結束語

通過分析并改進多目標進化算法，在NSGA-II和MOEA/P算法基礎上提出了確定目標域的NSGA/P投影算法。通過對目標空間進行劃分，利用降維的思想成功將高維多目標問題轉化為單目標問題，再根據決策者限定的范圍進行求取最優。

通過在大量的測試函數上運行算法，對實驗數據進行驗證及分析，所設計的NSGA/P算法有很好的收斂性和分布性，運行效率也較高，可以有效求解各種多目標優化問題，并且在求解超多目標問題上也存在一定的優勢。

但NSGA/P算法同樣存在不足，以后的研究方向從以下幾個方面進行展開：在某些測試函數上NSGA/P的性能稍微落后于MOEA/D以及MOEA/P算法，還需要不斷完善；投影后參考點的選取可能導致解的選取有很大的不同，后期應該注重參考點的選取數量以及如何設置參考點；該文根據常規的ZDT和DTLZ函數來測試NSGA/P算法，沒有考慮到實際的應用問題，后期可以將該算法應用到實際的生產生活中。