一種增強(qiáng)多樣性的改進(jìn)型NSGAⅡ算法*

程文旗，郭 華，謝承旺,2**，韋 偉，潘嘉敏，龍廣林

(1.南寧師范大學(xué)，計(jì)算機(jī)與信息工程學(xué)院，廣西南寧 530000；2.華南師范大學(xué)，數(shù)據(jù)科學(xué)與工程學(xué)院，廣東汕尾 516600)

0 引言

現(xiàn)實(shí)生活中涌現(xiàn)出越來(lái)越多的多目標(biāo)優(yōu)化問(wèn)題(Multi-objective Optimization Problem，MOP)，但是這些目標(biāo)之間通常是相互制約的，一個(gè)目標(biāo)在得到改善的同時(shí)會(huì)伴隨著其他目標(biāo)的效果變差，故MOP得到的解不能同時(shí)滿足全部目標(biāo)最優(yōu)，而是一組折衷的解，即Pareto解集或非劣解集[1]?；谌后w搜索的進(jìn)化算法(Evolutionary Algorithm，EA)是模擬生物進(jìn)化過(guò)程的自組織、自適應(yīng)的人工智能技術(shù)，主要通過(guò)選擇、交叉、變異、重組等遺傳操作求解問(wèn)題，其最大的優(yōu)勢(shì)就是不要求問(wèn)題滿足連續(xù)、可微等特定性質(zhì)?；贓A求解MOP問(wèn)題的優(yōu)勢(shì)，短短數(shù)年內(nèi)涌現(xiàn)出大量?jī)?yōu)秀的多目標(biāo)進(jìn)化算法(Multi-objective Evolutionary Algorithm，MOEA)。

1985年由Schaffer提出的矢量評(píng)價(jià)遺傳算法VEGA[2]是最早的進(jìn)化算法。在此后的時(shí)間里，學(xué)者針對(duì)不同的優(yōu)化問(wèn)題提出不同的MOEA，其中最具代表性的算法是以Pareto支配為基礎(chǔ)的MOEA，如NSGA[3]、NSGA-2[4]、強(qiáng)度Pareto進(jìn)化算法SPEA[5]、SPEA2[6]和PESA-Ⅱ[7]等。上述算法在求解較少數(shù)目標(biāo)優(yōu)化問(wèn)題上表現(xiàn)出良好的性能，其中以NSGAⅡ最具代表性。

多目標(biāo)優(yōu)化問(wèn)題在現(xiàn)實(shí)生活中的應(yīng)用比比皆是，例如：電力供應(yīng)[8]、 海水淡化[9]、護(hù)士排班問(wèn)題[10]、汽車控制器優(yōu)化問(wèn)題[11]以及疫情救災(zāi)點(diǎn)優(yōu)化[12]等。這些實(shí)際應(yīng)用問(wèn)題的目標(biāo)數(shù)通常是大于等于4 的，所以這些問(wèn)題又被稱為高維多目標(biāo)優(yōu)化問(wèn)題(Many-objective Optimization Problem，MaOP)。MaOP在傳統(tǒng)的優(yōu)化過(guò)程會(huì)面臨很多困難，如：①隨著目標(biāo)數(shù)的增加，種群中非支配個(gè)體所占的比例會(huì)急劇增大，嚴(yán)重削弱Pareto選擇壓力；②在目標(biāo)空間中可能會(huì)出現(xiàn)偏遠(yuǎn)的解，即支配抵觸解(Dominance Resistance Solution，DRS)[13]；③在高維空間中，因?yàn)閭€(gè)體可能相距太遠(yuǎn)，父代產(chǎn)生的子代有很大的差異，導(dǎo)致后代不穩(wěn)定且不具有代表性，通常會(huì)面臨雜交和變異算子失效的情況[14]；④Pareto前沿面表示困難。假設(shè)有m個(gè)目標(biāo)的優(yōu)化問(wèn)題，每個(gè)目標(biāo)上有b個(gè)解，則共需要mbm-1個(gè)解表示，這在現(xiàn)實(shí)應(yīng)用中十分困難。MaOP算法的提出一般基于上述幾個(gè)問(wèn)題，提出針對(duì)性的解決方案。

傳統(tǒng)的NSGAⅡ算法在高維(目標(biāo)數(shù)大于等于4)目標(biāo)空間優(yōu)化時(shí)，算法性能急劇下降，且算法的多樣性表現(xiàn)較差，不適用于現(xiàn)在的多目標(biāo)優(yōu)化問(wèn)題。受Elarbri等[15]所提出的RPD-NSGAⅡ啟發(fā)，本研究采用d2距離來(lái)增強(qiáng)算法在高維空間的多樣性，提出算法d2-NSGAⅡ。新算法擬在保證NSGAⅡ原有精英策略等優(yōu)點(diǎn)的同時(shí)，顯著改善算法的分布性。

1 多目標(biāo)優(yōu)化問(wèn)題及相關(guān)概念

統(tǒng)一以最小化問(wèn)題為例，將m個(gè)目標(biāo)函數(shù)和n個(gè)決策變量，(p+q) 個(gè)約束的MOP描述為

(1)

式中x∈X?Rn，y∈Y?Rm，n是決策變量的個(gè)數(shù)，m是目標(biāo)向量的個(gè)數(shù)，x表示決策向量，X是由決策向量x形成的決策空間；y表示目標(biāo)向量，Y是由目標(biāo)向量形成的目標(biāo)空間；F(x)定義了由決策空間X向目標(biāo)空間Y映射的函數(shù)，g(x)定義了p個(gè)不等式約束，h(x)定義了q個(gè)不等式約束。

定義1(可行解集)滿足式(1)中約束函數(shù)的決策向量的集合，用Xl表示，Xl={x∈X|g(x)≥0∧h(x)=0}。

定義2(Pareto支配)存在x1,x2∈Xl是問(wèn)題的解，當(dāng)滿足?i∈(1,…M):fi(x1)≤fi(x2)∧?j∈(1,…M):fi(x1)

定義3(Pareto最優(yōu)解)當(dāng)不存在其他解x∈Xl，使得xxl，稱xl為最優(yōu)解，最優(yōu)解也叫做非支配解。

定義4(Pareto最優(yōu)解集)滿足定義3的解的集合稱為Pareto最優(yōu)解集(Pareto optimal set，PS)，表示為PS={xl}={x∈Xl|-?x′∈Xl:x′x}。

定義5(Pareto前沿) PS在目標(biāo)空間的投影叫做Pareto前沿(Pareto optimal front，PF)，表示為PF={F(x)∈Rm|x∈PS}。

多目標(biāo)進(jìn)化算法按照不同優(yōu)化標(biāo)準(zhǔn)可以分為3類：基于支配的MOEA、基于指標(biāo)的MOEA以及基于分解的MOEA。其中，基于支配的MOEA算法代表有NSGAⅡ和SPEA2，基于分解的MOEA算法代表有MOEA/D[16]、MOEA/D-URAW[17]以及MOEA/D-DRA[18]，基于指標(biāo)的MOEA算法代表有超體積評(píng)價(jià)指標(biāo)(Hypervolume，HV)[19]、MOEA-HV[20]以及基于R2指標(biāo)的R2-HVC[21]。在基于分解的MOEA算法中，Zhang與Li[16]于2007年提出了一種優(yōu)秀的PBI分解方法，該方法因?yàn)榭梢暂^好地控制種群的收斂性和分布性而廣受關(guān)注。PBI在應(yīng)用時(shí)需要度量?jī)蓚€(gè)距離d1和d2，d1代表解在參考向量方向投影距離原點(diǎn)的歐式距離，d2代表解距離參考向量的歐式距離，具體度量如圖1所示。通過(guò)圖示不難看出，一個(gè)較小的d1代表解距離PF近，個(gè)體的收斂性更好；同樣較小的d2代表解具有更好的多樣性，當(dāng)d2=0時(shí)，意味著解在參考向量的方向上。

圖1 d1與d2距離的度量Fig.1 Measure of the distance of d1 and d2

具體數(shù)學(xué)表示如公式(2)：

(2)

2 基于d2距離的改進(jìn)型NSGAⅡ

傳統(tǒng)的NSGAⅡ算法在保持種群多樣性方面采用的是度量擁擠距離，該方法存在一定缺陷，即歐氏距離的度量在高維空間中不再適用[22]。個(gè)體的擁擠距離存在不能準(zhǔn)確度量個(gè)體擁擠度的問(wèn)題,在種群迭代的時(shí)候，該問(wèn)題會(huì)導(dǎo)致分布性差的個(gè)體反而被保留，進(jìn)而導(dǎo)致種群多樣性較差。如圖2所示，圖中個(gè)體為最后非支配層的個(gè)體，個(gè)體B、C的擁擠距離較大且相等，在迭代的時(shí)候這兩個(gè)個(gè)體會(huì)被保留下來(lái)。但是，由圖2可以看出這兩個(gè)個(gè)體實(shí)際距離較為接近，不應(yīng)該全部被保留；此時(shí)根據(jù)擁擠距離不能確定個(gè)體，可以度量?jī)蓚€(gè)個(gè)體距離相應(yīng)權(quán)重向量的d2距離，選擇距離小的個(gè)體保留(保留個(gè)體B)。

圖2 種群個(gè)體分布圖Fig.2 Distribution of population individuals

設(shè)置對(duì)照實(shí)驗(yàn)，增加統(tǒng)一數(shù)據(jù)集的維數(shù)，計(jì)算出目標(biāo)空間中最近與最遠(yuǎn)個(gè)體之間的差值dmax-dmin，實(shí)驗(yàn)參數(shù)設(shè)置如下：目標(biāo)數(shù)M=30，決策變量數(shù)目D=30，種群數(shù)N=100，評(píng)價(jià)次數(shù)Evaluation=10 000，p分別取值2.0，1.0，0.5，0.1。通過(guò)實(shí)驗(yàn)數(shù)據(jù)(圖3)可以看出，當(dāng)p=2.0(歐氏距離)以及p=1.0(曼哈頓距離)時(shí)，在高維空間dmax與dmin差值不是很明顯;當(dāng)p=0.5以及p=0.1時(shí)，隨維數(shù)的增加，dmax與dmin差值明顯變大，有利于在高維空間中選擇分布性較好的個(gè)體保留。因此，歐式距離降低了在高維空間中多樣性的選擇能力，其在高維空間中意義不大。相反地，其他p范式距離(p<1) 在高維空間上表現(xiàn)更好。

圖3 不同p取值下dmax與dmin差值變化情況Fig.3 Variation between dmaxand dmin under different values of p

Pareto支配能更好地提高算法的收斂性，而PBI效用函數(shù)的d2距離可以提高種群的多樣性分布。為將二者結(jié)合并求解高維目標(biāo)優(yōu)化問(wèn)題，本研究將d2距離的度量應(yīng)用到NSGAⅡ框架中。同樣采用NSGAⅡ非支配排序的方法選擇優(yōu)秀個(gè)體，保留F1,F2…Fl-1非支配層個(gè)體，刪除Fl層以后的個(gè)體，在第Fl非支配層利用個(gè)體距離相應(yīng)參考向量的d2距離，選擇出剩余優(yōu)秀個(gè)體，使得種群規(guī)模保持不變。這樣在保證種群收斂性的同時(shí)，促進(jìn)種群的多樣性。由此，產(chǎn)生一種基于d2距離的新算法d2_NSGAⅡ，算法的示意如圖4所示。

算法中使用的Pareto支配滿足反自反、反對(duì)稱和傳遞性質(zhì)。

①反自反性：種群中任一個(gè)體x，滿足反自反性，即x-x。

證明：如果xy，則至少存在一個(gè)分量i=1,2,…,m:滿足fi(x)

②反對(duì)稱性：種群中任意兩個(gè)體x，y如果滿足xy，則y-x。

證明：假設(shè)xy，根據(jù)定義3，則任意fi(x),fi(y),i=1,2,…,m:存在fi(x)≤fi(y)。所以不存在fi(x)>fi(y)，故y不能Pareto支配x，即y-x，滿足反對(duì)稱性質(zhì)。

③傳遞性：x,y,z是種群中3個(gè)個(gè)體，如果xy且yz,則xz。

證明：因?yàn)閤y，則滿足?i=1,2,…,m:fi(x)≤fi(y)∧?j=1,2,…,m:fj(x)

除非支配排序外，文章還涉及參考點(diǎn)的產(chǎn)生。因文章算法針對(duì)高維多目標(biāo)優(yōu)化問(wèn)題，因此采用Deb和Jain的雙層參考點(diǎn)產(chǎn)生方法，產(chǎn)生兩層參考點(diǎn)，每層參考點(diǎn)數(shù)量計(jì)算公式相同，具體如下所示：

(3)

其中，C代表參考點(diǎn)數(shù)量，M代表目標(biāo)數(shù)量，H代表超平面上沿著每個(gè)目標(biāo)考慮的劃分?jǐn)?shù)量。

表1 不同目標(biāo)情況下參考點(diǎn)數(shù)目Table 1 Number of reference points for different reference vector

圖5 參考向量的產(chǎn)生以及參考點(diǎn)的分布Fig.5 Generation of reference vectors and distribution of reference points

d2_NSGAⅡ具有以下特點(diǎn)：①利用NSGAⅡ經(jīng)典框架，保留精英策略，同時(shí)采用非支配排序，算法時(shí)間復(fù)雜度低；②算法最后的非支配層采用d2距離度量，可以在收斂性的基礎(chǔ)之上最大化地提高多樣性。以下給出算法的具體流程。

算法：d2_NSGAⅡ算法

輸入：種群規(guī)模N，決策變量數(shù)目D，MaOP問(wèn)題的目標(biāo)數(shù)目M，最大迭代次數(shù)Tmaxgen，沿目標(biāo)方向劃分H份

輸出：最末代種群Pmaxgen

1.初始化

1.1初始化迭代計(jì)數(shù)器t=0；

1.2在MaOP問(wèn)題的可行決策空間內(nèi)隨機(jī)產(chǎn)生N個(gè)初始點(diǎn)，形成初始化種群P0；

1.3計(jì)算P0中所有解的目標(biāo)值向量F1(0),…,FN(0)；

1.4產(chǎn)生參考點(diǎn)(M,H)→Set；

2.WHILE(t

6.合并子種群和父種群：Rt=Pt∪Qt；

7.計(jì)算最小向量值→Fmin；

8.計(jì)算最大向量值→Fmax；

9.歸一化處理(Rt,Fmin,Fmax)→Rt；

10.保留Rt中邊界解；

11.對(duì)Rt集合中的個(gè)體進(jìn)行非支配排序；

12.確定最小的k值，使其滿足|F1∪F2∪…∪Fk|≥N;//Fi表示第i層非Pareto支配層；

13.計(jì)算非支配層(Fk)個(gè)體的d2距離d2(Fk,Set)；

14.關(guān)聯(lián)Fk中個(gè)體與Set集合中的點(diǎn)；

15.IF |F1∪F2∪…∪Fk|>NTHEN

16.根據(jù)距離從非Pareto支配層Fk中刪除(|F1∪F2∪…∪Fk|-N)個(gè)具有較大d2距離的個(gè)體；

17.END IF

18.Pt+1=|F1∪F2∪…∪Fk|；//獲得規(guī)模為N的下一代種群;

19.更新迭代計(jì)數(shù)器t=t+1；

20.END WHILE.

21.輸出最末代種群Pmaxgen。

(4)

算法第13步通過(guò)公式(2)計(jì)算Fk層個(gè)體距離參考向量的d2距離，找到距離個(gè)體最近的參考向量進(jìn)行關(guān)聯(lián)。如圖6所示，度量個(gè)體a、b、c、e所有權(quán)重向量的d2距離，不難發(fā)現(xiàn)，個(gè)體b距離參考向量λ1最近，個(gè)體c距離參考向量λ2最近，將Fk層個(gè)體與相應(yīng)權(quán)重向量關(guān)聯(lián)。算法中，先進(jìn)性非支配排序獲得若干非支配層后，再對(duì)Fk非支配個(gè)體進(jìn)行關(guān)聯(lián)參考點(diǎn)，這樣可以避免計(jì)算所有個(gè)體的d2距離，減少計(jì)算復(fù)雜度。

圖6 個(gè)體關(guān)聯(lián)參考點(diǎn)Fig.6 Individuals associated with reference points

同時(shí)，保留目標(biāo)空間中的邊界值，將在每個(gè)目標(biāo)上的最大值與最小值的個(gè)體保留下來(lái)(邊界值)。將邊界個(gè)體的d2值設(shè)置為0，在迭代的時(shí)候?qū)2值為0的個(gè)體保留下來(lái)。與NSAGⅡ同樣地進(jìn)行非支配排序，確定最后的非支配層使得種群規(guī)模保持N，并在最后非支配層根據(jù)d2值由小到大篩選優(yōu)秀的個(gè)體，使種群的規(guī)模保持為N，進(jìn)入下一代迭代。

d2_NSGAⅡ的時(shí)間復(fù)雜度主要由兩部分組成：非支配排序、d2距離度量。假設(shè)MOP有M個(gè)目標(biāo)，種群規(guī)模N。非支配排序中，種群中所有個(gè)體之間相互比較，確定所有個(gè)體計(jì)數(shù)Sq(被個(gè)體q支配的個(gè)體數(shù)目) 和個(gè)體q支配的個(gè)體數(shù)目nq，需要兩兩個(gè)體比較，時(shí)間復(fù)雜度為O(MN2)。在找到第一非支配層個(gè)體后，剩余個(gè)體的nq計(jì)數(shù)最多為N-1，故剩余個(gè)體最多需要遍歷(N-1)次才會(huì)找到所在非支配層。因?yàn)槌サ谝环侵鋵又庾疃嗍Ｓ鄠€(gè)體為(N-1)，故此過(guò)程時(shí)間復(fù)雜度為O(N2)。因此，非支配排序的時(shí)間復(fù)雜度為O(MN2)。在最差情況下，即第一非支配層即為最后非支配層，需度量所有個(gè)體距離參考向量的距離，時(shí)間復(fù)雜度為O(N2)。綜上兩部分時(shí)間復(fù)雜度比較，取最高次冪，故d2_NSGAⅡ的時(shí)間復(fù)雜度為O(MN2)。

3 測(cè)試實(shí)驗(yàn)與數(shù)據(jù)分析

為驗(yàn)證所提出的d2_NSGAⅡ算法的有效性，采用3組對(duì)比算法在DTLZ系列測(cè)試函數(shù)上進(jìn)行實(shí)驗(yàn)數(shù)據(jù)的對(duì)照以及分析，所采用的算法依次是NSGAⅡ、NSGA、VaEA[23]、MOEAD以及MOEADFFRMAB[24]。

3.1 測(cè)試問(wèn)題

研究采用的是DTLZ系列測(cè)試函數(shù)，具體為DTLZ1-DTLZ7。DTLZ測(cè)試函數(shù)的前沿面具有多樣性，具備不同的特征，可以從多個(gè)角度檢驗(yàn)算法在高維多目標(biāo)情況下優(yōu)化問(wèn)題的能力，而且采用的測(cè)試函數(shù)在目標(biāo)空間和決策空間上均具有可擴(kuò)展性。DTLZ系列測(cè)試函數(shù)的具體特征描述如表2所示。

表2 測(cè)試函數(shù)特征Table 2 Characteristics of the test function

3.2 性能指標(biāo)

采用IGD指標(biāo)測(cè)試新算法的性能。該指標(biāo)反映了真實(shí)的Pareto前沿到近似Pareto前沿之間的距離，可以綜合度量算法的收斂性與多樣性。IGD指標(biāo)具體工作機(jī)制如下：在真實(shí)的Pareto前沿上采用一組分布較為均勻的點(diǎn)，并計(jì)算他們到近似Pareto解之間的距離。IGD指標(biāo)的值越小表明算法收斂性與多樣性越好。具體的計(jì)算公式如下：

(5)

(6)

3.3 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)對(duì)比了6種算法在DTLZ6測(cè)試函數(shù)上，目標(biāo)數(shù)為8的IGD值變化情況(圖7)。從圖7可以看出，隨著評(píng)估次數(shù)的增大，6種算法的IGD值整體在變小。評(píng)估次數(shù)在3 000之前，d2_NSGAⅡ的下降速度遠(yuǎn)遠(yuǎn)大于NSGAⅡ、VaEA、NSGAⅢ，但是稍微小于MOEAD和MOEADFRRMAB；評(píng)估次數(shù)在3 000之后，d2_NSGAⅡ的下降速度僅僅略遜色于MOEADFRRMAB，但是遠(yuǎn)遠(yuǎn)超過(guò)其他4種算法。圖7算法的IGD變化情況印證了d2_NSGAⅡ算法在算法多樣性與收斂性方面的效果。

圖7 6種算法在DTLZ6測(cè)試函數(shù)上(目標(biāo)數(shù)為8)的IGD值變化Fig.7 Change of IGD values of 6 algorithms on DTLZ6 test function (target number 8)

表3給出d2_NSGAⅡ與NSGAⅡ、NSGAⅢ、VaEA、MOEAD、MOEADFRRMAB 6種算法在測(cè)試函數(shù)上的IGD值，以及他們的優(yōu)劣對(duì)比，表現(xiàn)優(yōu)秀的IGD值用加粗字體標(biāo)注。將目標(biāo)數(shù)分別設(shè)置為3,5,8,10 (表3)，在28組測(cè)試函數(shù)中，d2_NSGAⅡ共取得7個(gè)最佳IGD值，NSGAⅡ共獲得1個(gè)最佳IGD值，VaEA 取得1個(gè)最佳值，NSGAⅢ共取得4個(gè)最佳IGD值，MOEAD共取得11個(gè)最佳IGD值，MOEADFRRMAB取得4個(gè)最佳IGD值。從表中的Wilcoxon秩和檢驗(yàn)結(jié)果看，相比于MOEAD、MOEADFRRMAB、VaEA、NSGAⅢ、NSGAⅡ，d2_NSGAⅡ凈勝得分(數(shù)據(jù)優(yōu)于對(duì)比算法的個(gè)數(shù)減去差于對(duì)比算法的個(gè)數(shù))為-2,0,6,1,16。由此可見(jiàn)，除算法性能稍微劣于MOEAD、MOEADFRRMAB，d2_NSGAⅡ均優(yōu)于其他幾種算法，故認(rèn)為d2_NSGAⅡ算法在求解DTLZ系列測(cè)試函數(shù)具有較為優(yōu)秀的性能。

表3 6種算法在DTLZ測(cè)試函數(shù)上的IGD值Table 3 IGD values of 6 algorithms on the DTLZ test function

續(xù)表3Continued table 3

4 結(jié)論

為解決NSGAⅡ在高維空間中效果不佳的問(wèn)題，研究提出基于d2距離的NSGAⅡ算法，在保證算法收斂性的同時(shí)增加其多樣性。通過(guò)實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證，該算法在MaOP上取得了不錯(cuò)的效果，但是隨著目標(biāo)數(shù)目的增加，算法性能下降。究其原因，隨著目標(biāo)數(shù)目的增加，個(gè)體之間變得相互非支配，這是傳統(tǒng)非支配方法面臨的統(tǒng)一問(wèn)題。未來(lái)可從支配關(guān)系以及距離度量方面進(jìn)一步改進(jìn)與探索，同時(shí)可以設(shè)計(jì)一些更加復(fù)雜的MaOP問(wèn)題檢驗(yàn)算法的有效性，使其效果更加優(yōu)秀。