一種確定目標(biāo)域多目標(biāo)優(yōu)化算法NSGA/P

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

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

0 引 言

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

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

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

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

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

1 確定目標(biāo)域的多目標(biāo)問題概述

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

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)

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

2 NSGA-II算法

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

圖1 NSGA-II算法過程圖

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

3 基于投影面的多目標(biāo)進(jìn)化算法MOEA/P

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

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

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

4 NSGA/P算法框架

該文重點研究確定目標(biāo)域的多目標(biāo)優(yōu)化算法NSGA/P。

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

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

(3)對投影面的根據(jù)目標(biāo)域范圍進(jìn)行投影格分割，如圖2所示。

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

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

圖2 目標(biāo)域投影格

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

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

(6)達(dá)到進(jìn)化終止條件，整個進(jìn)化過程結(jié)束，輸出第二隊列中當(dāng)前Pareto等級最高的所有個體，即為問題求解的最優(yōu)解集。

NSGA/P算法框架

輸入:

·確定目標(biāo)域的多目標(biāo)問題MOP；

·DS:目標(biāo)決策空間(投影面)設(shè)定；

·E:最大進(jìn)化代數(shù)；

·N:初始種群大小。

輸出:目標(biāo)解集RS

過程：

步驟1：目標(biāo)空間歸一化。

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

步驟2.1 初始化種群：

初始化大小為N的種群G，構(gòu)造種群中個體并初始個體基因序列，對種群G每個個體進(jìn)行初始計算，得到相應(yīng)的目標(biāo)函數(shù)值。保證所有個體滿足MOP約束條件：如果不滿足MOP，重新生成，直到G.size=N。

步驟2.2 確定目標(biāo)域及投影面，并進(jìn)行參考點[15-16]的選?。?/p>

根據(jù)DS確定投影面和目標(biāo)域，均勻分割目標(biāo)域并設(shè)置參考向量[17]。

步驟2.3 種群進(jìn)化：

如果已經(jīng)進(jìn)化E代，或達(dá)到其他結(jié)束條件，轉(zhuǎn)步驟2.4；

分別對種群G中的個體進(jìn)化操作；

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

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

重復(fù)步驟2.3。

步驟2.4 提交進(jìn)化結(jié)果：

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

步驟3：輸出RS。

5 NSGA/P算法過程圖

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

6 實驗及討論

6.1 測試用例

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

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

圖3 NSGA/P算法過程圖

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

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

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

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

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

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

6.2 性能評價指標(biāo)

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

(2)

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

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

(3)

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

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

(4)

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

6.3 算法測試結(jié)果

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

在進(jìn)化代數(shù)E=250，種群大小N在20～100范圍內(nèi)，目標(biāo)域f1[0.2，0.8]，測試算法運行時間以及IGD評價指標(biāo)結(jié)果，如表1所示。

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

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

6.3.2 進(jìn)化代數(shù)對算法性能的影響

在進(jìn)化代數(shù)E分別為50～300，種群大小N=60，目標(biāo)域f1[0.2，0.8]的情況下，通過實驗進(jìn)行相應(yīng)比較分析，測試結(jié)果如表2所示。

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

測試結(jié)果顯示算法運行時間基本上與進(jìn)化代數(shù)呈線性關(guān)系，IGD值隨種群增大而減小，最后趨于一定值，并在進(jìn)化到大概150代的時候，基本實現(xiàn)最優(yōu)解的求取。

6.3.3 確定目標(biāo)域范圍對算法性能的影響

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

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

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

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

表4 超多目標(biāo)優(yōu)化問題解的投影誤差δd值、CPU時間

6.3.4 實驗對比

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

表5 超多目標(biāo)算法求解IGD值、CPU時間

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

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

7 結(jié)束語

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

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

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