馬暢暢，汪 坤，鹿曉夢(mèng)，陳未如

(1.沈陽(yáng)化工大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，遼寧 沈陽(yáng) 110142；2.遼寧省化工過(guò)程工業(yè)智能化技術(shù)重點(diǎn)實(shí)驗(yàn)室，遼寧 沈陽(yáng) 110142)

0 引 言

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

由于進(jìn)化算法能夠有效解決多目標(biāo)優(yōu)化問題，所以通過(guò)對(duì)多目標(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]和基于評(píng)價(jià)指標(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ā)展，通過(guò)對(duì)NSGA-II與其他多目標(biāo)優(yōu)化算法[7]進(jìn)行比較和分析，發(fā)現(xiàn)NSGA-II算法容易早熟，算法運(yùn)行效率不夠高，種群收斂性不夠好并且全局搜索能力一般，尤其是在超多目標(biāo)優(yōu)化問題的求解上更顯不足[8]。

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

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

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

以最小化問題為例，一般情況下，確定目標(biāo)域的多目標(biāo)優(yōu)化問題(MOP with definite object domains)是求一組決策變量,使其不僅滿足g、h約束條件,并且使m個(gè)目標(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)

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

2 NSGA-II算法

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

圖1 NSGA-II算法過(guò)程圖

NSGA-II算法通過(guò)增加精英保留策略、計(jì)算擁擠度距離和快速非支配排序策略[14]，解決了NSGA算法計(jì)算復(fù)雜度高，運(yùn)行效率低，多樣性和收斂性不夠好等缺點(diǎn)。然而，由于NSGA-II算法的核心是根據(jù)支配關(guān)系進(jìn)行個(gè)體的排序，在超多目標(biāo)優(yōu)化問題中，這種排序策略對(duì)個(gè)體的優(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)空間劃分為兩部分：投影面和自由維，并且把投影面分割成多個(gè)投影格，然后在各個(gè)投影格上求解自由維的最優(yōu)值，在求解最優(yōu)值過(guò)程中，采用合適的適應(yīng)度函數(shù)和空間壓縮的進(jìn)化算法，將種群個(gè)體壓縮到投影目標(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算法目的是對(duì)多目標(biāo)優(yōu)化問題進(jìn)行降維處理，把目標(biāo)空間分解成自由維和投影面兩部分，以確定目標(biāo)域?yàn)橥队懊?，根?jù)設(shè)置的目標(biāo)域求解范圍來(lái)求解最優(yōu)值，采用NSGA-II算法在投影面目標(biāo)域求解范圍內(nèi)對(duì)自由維進(jìn)行相應(yīng)的優(yōu)化求解。這種求解方式不僅緩解了全局計(jì)算的壓力，在保證求解效率的同時(shí)還保證了解集質(zhì)量，又滿足了用戶的決策需求，從而逐步得到目標(biāo)域限定下多目標(biāo)優(yōu)化問題的最優(yōu)解。

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

4 NSGA/P算法框架

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

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

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

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

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

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

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

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

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

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

NSGA/P算法框架

輸入:

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

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

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

·N:初始種群大小。

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

過(guò)程：

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

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

步驟2.1 初始化種群：

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

步驟2.2 確定目標(biāo)域及投影面，并進(jìn)行參考點(diǎ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；

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

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

選取排序前N的個(gè)體，組成新的G。

重復(fù)步驟2.3。

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

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

步驟3：輸出RS。

5 NSGA/P算法過(guò)程圖

NSGA/P算法過(guò)程圖如圖3所示。

6 實(shí)驗(yàn)及討論

6.1 測(cè)試用例

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

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

圖3 NSGA/P算法過(guò)程圖

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

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

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

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

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

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

6.2 性能評(píng)價(jià)指標(biāo)

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

(2)

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

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

(3)

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

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

(4)

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

6.3 算法測(cè)試結(jié)果

6.3.1 種群大小對(duì)算法性能的影響

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

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

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

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

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

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

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

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

在種群大小N=100，進(jìn)化代數(shù)E=250，不同目標(biāo)域范圍內(nèi)進(jìn)行實(shí)驗(yàn)。本次測(cè)試三目標(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)行測(cè)試，結(jié)果如表3所示。

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

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

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

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

6.3.4 實(shí)驗(yàn)對(duì)比

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

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

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

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

7 結(jié)束語(yǔ)

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

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

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