懲罰策略輔助的快速非支配排序遺傳算法Ⅱ研究

王俊艷

(太原科技大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院， 太原 030024)

0 引言

多目標(biāo)優(yōu)化問題是指具有2～3個(gè)相互沖突的優(yōu)化問題。多目標(biāo)進(jìn)化算法是一種在解決多目標(biāo)優(yōu)化問題方面具有突出表現(xiàn)的一類算法。典型的多目標(biāo)算法包括快速非支配排序遺傳算法(NSGA-Ⅱ)[1]，多目標(biāo)微粒群算法(MOPSO)[2]等。 快速非支配排序遺傳算法Ⅱ由于其在解決多目標(biāo)優(yōu)化問題上的出色性能，在實(shí)際應(yīng)用中被廣泛采用。然而，其采用的錦標(biāo)賽策略由于存在重復(fù)選擇具有較高優(yōu)先級(jí)個(gè)體的缺陷而導(dǎo)致其多樣性交叉以及在某些多目標(biāo)優(yōu)化問題上性能表現(xiàn)一般。

針對(duì)此問題，許多學(xué)者做出了有效地改進(jìn)。張茂清等[3]提出了基于維度擾動(dòng)的快速非支配排序遺傳算法Ⅱ,即將采用錦標(biāo)賽策略選擇出的個(gè)體進(jìn)行局部擾動(dòng)操作，以此消除重復(fù)個(gè)體的現(xiàn)象。汪鐳等[4]提出引入多個(gè)交叉父代個(gè)體的策略，以降低重復(fù)選擇同一個(gè)父代個(gè)體的概率。呂琳[5]通過將正態(tài)分布引入交叉算子的方式設(shè)計(jì)了自適應(yīng)交叉算法，有效消除了重復(fù)選擇父代個(gè)體的現(xiàn)象。王青松等[6]提出混合交叉算子的方法擴(kuò)展搜索空間和減少重復(fù)選擇父代個(gè)體的概率。趙一霞[7]通過設(shè)計(jì)循環(huán)擁擠度距離的方式有效減少了重復(fù)父代的現(xiàn)象。田旭楊等[8]提出引入自適應(yīng)選擇與混合交叉算子，并進(jìn)一步應(yīng)用于列車運(yùn)行多目標(biāo)優(yōu)化問題中。趙珍珍等[9]則嘗試了將粒子群優(yōu)化算法的速度更新機(jī)制引入算法適應(yīng)值評(píng)價(jià)并將種群平均分為多個(gè)子種群，并從多個(gè)子種群中選擇代交叉?zhèn)€體，以此避免重復(fù)個(gè)體選擇問題。Li等[10]則設(shè)計(jì)了正態(tài)分布交叉算子和自適應(yīng)變異算子的方法消除重復(fù)個(gè)體，保證算法的多樣性。Yang等[11]則綜合了正態(tài)分布算子、自適應(yīng)變異算子，以及基于方差的擁擠度距離計(jì)算方法進(jìn)一步提升了算法多樣性。Kong等[12]提出3個(gè)交叉父代的策略以降低重復(fù)選擇父代的概率。

不同于上述討論的方法，本文通過設(shè)計(jì)一種懲罰機(jī)制，將每次通過錦標(biāo)賽策略選擇的個(gè)體以優(yōu)先級(jí)自適應(yīng)降低的方式降低個(gè)體下一輪中被選擇的概率?；趹土P策略提出了懲罰策略輔助的快速非支配排序遺傳算法Ⅱ (fast non-dominated sorting genetic algorithm Ⅱ assisted by penalty strategy,PNSGA-Ⅱ)。

1 基本概念

1.1 多目標(biāo)優(yōu)化問題定義

不失一般性，本文中所解決的多目標(biāo)優(yōu)化問題在數(shù)學(xué)上可表達(dá)如下[13]：

minF(X)=min(f1(X),f2(X),…,fm(X))

X=(x1,x2,…,xn)∈Rn

(1)

式中：fm(X)是第m個(gè)目標(biāo)函數(shù)，X是具有n維變量的解向量；Rn為決策變量空間。

1.2 基本NSGA-Ⅱ介紹

基本NSGA-Ⅱ算法主要包括錦標(biāo)賽策略、交叉操作、變異操作以及種群更新操作。主要運(yùn)行過程如圖1所示。

圖1 NSGA-Ⅱ算法說明

對(duì)于第t代具有N個(gè)個(gè)體的父代種群Pt， 通過錦標(biāo)賽策略確定待交叉父代個(gè)體，然后通過模擬二進(jìn)制交叉和多項(xiàng)式變異操作產(chǎn)生子代種群Qt；接著，采用快速非支配排序策略對(duì)合并的種群Pt∪Qt進(jìn)行支配分級(jí)F1,F2,…。然后，將第1級(jí)到第l級(jí)內(nèi)的個(gè)體歸入子代種群Pt+1=F1∪F2…∪Fl；若此時(shí)|Pt+1|=N,則進(jìn)入下一代循環(huán)；若存在|F1∪F2…Fl∪Fl+1|>N和|F1∪F2…Fl|

NSGA-Ⅱ中錦標(biāo)賽策略可表述如下：

1) 確定選擇對(duì)比個(gè)體數(shù)，文獻(xiàn)[1]中設(shè)置為2，交叉池規(guī)模為N;

2) 對(duì)比選擇的2個(gè)父代個(gè)體所在非支配等級(jí)，具有較優(yōu)前沿面的個(gè)體進(jìn)入交叉池；若兩父代個(gè)體具有相同非支配等級(jí)，對(duì)比兩個(gè)體擁擠度距離，選擇擁擠度距離較大的個(gè)體進(jìn)入交叉池;

3) 重復(fù)上述1)和2)，直到滿足交叉池規(guī)模。

從錦標(biāo)賽執(zhí)行過程可以看出，在第一層非支配前沿面中具有較大擁擠度距離的個(gè)體具有更高的優(yōu)先級(jí)。在多次重復(fù)執(zhí)行的過程中，此類個(gè)體會(huì)被多次選中進(jìn)入交叉池。雖然這樣選擇策略有利于保留較優(yōu)個(gè)體的基因，但是不可避免導(dǎo)致后代多樣性受到影響。圖2統(tǒng)計(jì)了錦標(biāo)賽策略在ZDT1函數(shù)上運(yùn)行一次后個(gè)體被重復(fù)選擇的統(tǒng)計(jì)信息，種群個(gè)體數(shù)為100，實(shí)驗(yàn)其他參數(shù)設(shè)置見實(shí)驗(yàn)部分。從圖2可以看出，有些個(gè)體被多次重復(fù)選擇3次，5次甚至6次，有6個(gè)個(gè)體最多被重復(fù)選擇了6次，說明重復(fù)選擇同一個(gè)個(gè)體的現(xiàn)象非常普遍。

圖2 重復(fù)個(gè)體頻次統(tǒng)計(jì)

2 懲罰策略輔助的快速非支配排序遺傳算法Ⅱ

針對(duì)錦標(biāo)賽策略存在的重復(fù)個(gè)體多次被選擇缺陷，提出懲罰策略輔助的個(gè)體選擇機(jī)制。主要思想如下：對(duì)于父代種群Pt，根據(jù)快速非支配排序方法生成多個(gè)非支配等級(jí)F1,F2,…,Fn。對(duì)于個(gè)體S∈Fl，其優(yōu)先級(jí)定義為：

Os=l+rs/rmax

(2)

式中：l為個(gè)體S所處非支配等級(jí)順序；rs為Fl中個(gè)體擁擠度距離按照降序排列的順序；rmax為最大順序。

在錦標(biāo)賽選擇過程中，若個(gè)體S被選中一次，則其優(yōu)先級(jí)更新為：

Os=Os×er

(3)

式中：r為參數(shù)，具體設(shè)置將在后續(xù)實(shí)驗(yàn)中討論。

通過此方式可有效降低個(gè)體S在下一輪中被選中的概率。注意，此處個(gè)體優(yōu)先級(jí)值越大說明其優(yōu)先級(jí)越低。為清楚表示上述過程，懲罰策略輔助的錦標(biāo)賽選擇策略偽代碼如算法1所示，優(yōu)先級(jí)越小的個(gè)體對(duì)應(yīng)的Qs越小。

算法1：懲罰策略輔助的錦標(biāo)賽選擇策略偽代碼

輸入：非支配等級(jí)F1,F2,…,Fn,每個(gè)個(gè)體擁擠度距離

輸出：交叉池L

1: ForFi∈{F1,F2,…,Fn}

2: 對(duì)Fi中個(gè)體按照擁擠度距離大小降序排列

3： 按照式(1)計(jì)算每個(gè)個(gè)體優(yōu)先級(jí)

4： end

5: while |L|

6: 隨機(jī)選擇2個(gè)個(gè)體S1,S2

7: ifOS1

8:L←L∪{S1}

9:OS1←OS1×er

10: elseOS1≥OS2

11:L←L∪{S2}

12:OS2←OS2×er

13: end

14: end

為了算法完整性，仍然將完整懲罰策略輔助的快速非支配排序遺傳算法Ⅱ偽代碼呈現(xiàn)，如算法2所示。

算法2：懲罰策略輔助的快速非支配排序遺傳算法Ⅱ偽代碼

輸入：種群規(guī)模N

輸出：最終種群P

1:P←初始化種群

2: {F1,F2,…,Fn}←執(zhí)行快速非支配排序策略

3: 計(jì)算每個(gè)個(gè)體擁擠度距離

4: while(滿足結(jié)束條件？)

5：L←懲罰策略輔助的錦標(biāo)賽選擇方法%如算法1所示

6： 模擬二進(jìn)制交叉和多項(xiàng)式變異

7： {F1,F2,…,Fn}←執(zhí)行快速非支配排序策略

8： 計(jì)算每個(gè)個(gè)體擁擠度距離

9：P←環(huán)境更新

10: end

3 實(shí)驗(yàn)結(jié)果以及分析

3.1 實(shí)驗(yàn)設(shè)置

為測(cè)試PNSGA-Ⅱ的綜合性能，采用ZDT和DTLZ[14]測(cè)試函數(shù)集作為測(cè)試用例。所用ZDT測(cè)試函數(shù)集包括ZDT1、ZDT2、ZDT3、ZDT4和ZDT6。DTLZ測(cè)試函數(shù)集包括DTLZ1,DTLZ2,DTLZ3,DTLZ4,DTLZ5以及DTLZ6。ZDT測(cè)試函數(shù)集合中所有函數(shù)目標(biāo)均為2個(gè)，DTLZ測(cè)試函數(shù)集合中所有目標(biāo)均為3個(gè)。ZDT1—ZDT3函數(shù)對(duì)應(yīng)的決策變量數(shù)目為30，ZDT4以及ZDT6對(duì)應(yīng)決策變量數(shù)目為10。DTLZ1函數(shù)有7個(gè)決策變量，DTLZ2—DTLZ6有12個(gè)決策變量。性能指標(biāo)采用IGD和Spread[15]指標(biāo)。IGD指標(biāo)為一類綜合指標(biāo)，不僅可以衡量收斂性，而且可以衡量解集多樣性。IGD指標(biāo)值越小，表明相應(yīng)算法越優(yōu)秀。Spread指標(biāo)用于衡量所求種群多樣性。對(duì)比算法采用NSGA-Ⅱ[1]、MOPSO[16]、HypE[17]以及NMPSO[18]。對(duì)于PNSGA-Ⅱ以及NSGA-Ⅱ,交叉概率設(shè)置為1，變異概率設(shè)置為1/D,D為決策變量維度。對(duì)于MOPSO,每個(gè)目標(biāo)分割數(shù)為10。其他參數(shù)按照開發(fā)者建議設(shè)置。PNSGA-Ⅱ中的參數(shù)r設(shè)置為0.5，具體參數(shù)敏感性分析將在實(shí)驗(yàn)部分驗(yàn)證。以上所有算法評(píng)價(jià)次數(shù)為10 000次，種群規(guī)模為100，每個(gè)算法運(yùn)行20次,并采用Friedman檢驗(yàn)方法統(tǒng)計(jì)對(duì)比實(shí)驗(yàn)結(jié)果。

3.2 算法分析

表1和表2列出了算法在測(cè)試函數(shù)上的IGD和Spread指標(biāo)數(shù)據(jù)，其中最優(yōu)值用黑體顯示,M表示目標(biāo)函數(shù)維度。最后一行為采用Friedman方法統(tǒng)計(jì)出的算法對(duì)比結(jié)果。從表1可以看出，在所有測(cè)試函數(shù)上，PNSGA-Ⅱ在8個(gè)函數(shù)上表現(xiàn)最優(yōu)。在ZDT4和ZDT6函數(shù)上，PNSGA-Ⅱ比NSGA-Ⅱ略差; 在DTLZ3上，PNSGA-Ⅱ整體性能比HypE差。對(duì)比標(biāo)準(zhǔn)NSGA-Ⅱ,可以看出PNSGA-Ⅱ在綜合性能提升方面較為明顯。從表1最后一行Friedman檢驗(yàn)結(jié)果可以看出，PNSGA-Ⅱ在統(tǒng)計(jì)意義上具有最優(yōu)表現(xiàn)。從表2數(shù)據(jù)可以看出，PNSGA-Ⅱ在所有算法中仍然表現(xiàn)最優(yōu)，在7個(gè)函數(shù)上獲得最優(yōu)值。在ZDT2和ZDT6上，PNSGA-Ⅱ多樣性比NSGA-Ⅱ差; 在ZDT6上，NMPSO多樣性表現(xiàn)優(yōu)于PNSGA-Ⅱ；在DTLZ6上，MOPSO多樣性表現(xiàn)最好，但是PNSGA-Ⅱ 仍然優(yōu)于NSGA-Ⅱ。從表2最后一行Friedman統(tǒng)計(jì)結(jié)果可以看出，在所有對(duì)比算法中，PNSGA-Ⅱ整體表現(xiàn)最優(yōu)。

表1 算法在測(cè)試集上的IGD值

表2 算法在測(cè)試函數(shù)上的Spread值

圖3列出了所有算法在DTLZ2上的帕累托前沿面，其中實(shí)線表示真實(shí)帕累托前沿面，灰色圓點(diǎn)表示算法所求帕累托最優(yōu)解。從圖3可看出，PNSGA-Ⅱ所求帕累托前沿面比較接近真實(shí)前沿面，而且分布相對(duì)均勻。和PNSGA-Ⅱ相比，NSGA-Ⅱ所求前沿面均勻性較差。如前面分析，從所獲得的解集分布性而言,MOPSO表現(xiàn)仍比PNSGA-Ⅱ差。從HypE所求帕累托前沿可以看出，HypE維持種群多樣性能力明顯比PNSGA-Ⅱ差。NMPSO在收斂性和多樣性方面超過了MOPSO和HypE,但是多樣性明顯比PNSGA-Ⅱ差。從以上分析可以看出，所提PNSGA-Ⅱ整體表現(xiàn)突出。相比于原始錦標(biāo)賽選擇策略，基于懲罰的錦標(biāo)賽選擇策略表現(xiàn)較優(yōu)。

圖3 算法在DTLZ2函數(shù)上所求前沿面

3.3 參數(shù)r分析

為對(duì)參數(shù)r敏感性做進(jìn)一步分析，將r分別設(shè)置為0、0.1、0.2、0.3、0.4、0.5、0.6、0.7，并在DTLZ和ZDT函數(shù)集上對(duì)比不同r值對(duì)應(yīng)的Friedman值。算法參數(shù)設(shè)置如3.1小節(jié)所示，結(jié)果如圖4所示。從圖4(a)可以看出，參數(shù)r為0～0.3時(shí)，有明顯下降趨勢(shì)；r=0.4時(shí)，算法性能逐步變差；當(dāng)r=0.5時(shí)，對(duì)應(yīng)算法取得最好性能；當(dāng)r為0.6～1.0時(shí)，對(duì)應(yīng)算法性能逐漸變差。從圖4(b)可以看出，當(dāng)r為0～0.1時(shí)，算法性能逐漸變好；當(dāng)r為0.1～0.3時(shí)，算法性能出現(xiàn)波動(dòng)；當(dāng)r=0.4時(shí)，算法性能明顯變差；當(dāng)r=0.5時(shí)，算法取得最好性能；然后隨著r增加，算法性能再次變差。從上述2個(gè)測(cè)試集上的參數(shù)r對(duì)算法性能影響可以看出，r=0.5時(shí)為最優(yōu)參數(shù)，因此選取0.5為最優(yōu)參數(shù)設(shè)置。

圖4 參數(shù)r敏感性分析曲線

4 結(jié)論

錦標(biāo)賽選擇策略是一種在進(jìn)化算法中被普遍接受的一種選擇策略。然而，由于其存在多次重復(fù)選擇某些優(yōu)勢(shì)個(gè)體的缺陷，導(dǎo)致算法分布性以及整體性能下降。為解決此問題，提出了懲罰策略輔助的錦標(biāo)賽選擇策略，即將每次所選的個(gè)體優(yōu)先級(jí)不斷地降低，以此保證在下一輪選擇中以較低的概率選擇。通過將懲罰策略輔助的錦標(biāo)賽方法融入NSGA-Ⅱ,提出了懲罰策略輔助的快速非支配排序遺傳算法Ⅱ。在ZDT和DTLZ經(jīng)典測(cè)試問題上，實(shí)驗(yàn)分析表明了本文中所提懲罰策略的有效性。