基于權(quán)重學(xué)習(xí)的高維多目標(biāo)進(jìn)化算法

李杭涓，崔志華，謝麗萍

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

0 引 言

隨著社會(huì)對(duì)生產(chǎn)需求的增長(zhǎng)，現(xiàn)實(shí)生活中的多目標(biāo)優(yōu)化問(wèn)題[1-2]變得越來(lái)越復(fù)雜，需要考慮的目標(biāo)問(wèn)題也越來(lái)越多。因此，當(dāng)前現(xiàn)有的進(jìn)化算法[3]在求解多目標(biāo)優(yōu)化問(wèn)題時(shí)面臨著許多挑戰(zhàn)[4-6]。例如，種群進(jìn)化方向的盲目性，支配關(guān)系的無(wú)效性，收斂性和多樣性不平衡性，真實(shí)解決方案集的可視化難度等。

隨著目標(biāo)數(shù)量的增多，種群中的非支配解在可行解中的比例會(huì)爆炸性地增加[7]，促使種群進(jìn)化的選擇壓力下降[8-9]，導(dǎo)致了支配關(guān)系無(wú)效。針對(duì)這一問(wèn)題，一些學(xué)者試圖通過(guò)改變支配關(guān)系來(lái)增加選擇壓力，這意味著使用新的支配關(guān)系來(lái)增加進(jìn)化種群的選擇壓力。例如，r支配[10]、ε支配[11]等支配關(guān)系。雖然在特定的情況下這些支配關(guān)系可以選出收斂性強(qiáng)的個(gè)體以維持種群的多樣性和收斂性，但在此類方法中涉及到參數(shù)的取值，具有很大的不確定性。

由于支配關(guān)系的無(wú)效性，基于密度的多樣性維護(hù)策略[12]是維持種群進(jìn)化選擇壓力的另一方法。例如Deb等[13]提出的NSGA-III，該方法基于參考點(diǎn)選擇個(gè)體以保持種群的良好分布。但是，該算法在環(huán)境選擇階段過(guò)于依賴多樣性保護(hù)機(jī)制，收斂信息沒有得到充分利用。同時(shí)，由于進(jìn)化算法中進(jìn)化策略的隨機(jī)性，使得種群個(gè)體進(jìn)化方向存在盲目性。

針對(duì)以上兩個(gè)問(wèn)題，該文提出了WL-NSGAIII算法，即分別從產(chǎn)生候選解和選擇候選解兩個(gè)角度對(duì)NSGAIII算法進(jìn)行改進(jìn)。在WL-NSGAIII算法的匹配選擇階段，設(shè)計(jì)了一種基于權(quán)重的個(gè)體學(xué)習(xí)策略，為種群個(gè)體提供進(jìn)化方向并增強(qiáng)候選解集的收斂性。同時(shí)，在WL-NSGAIII算法的環(huán)境選擇階段，利用權(quán)重信息對(duì)小生境選擇策略進(jìn)行改進(jìn)，在維持種群多樣性的同時(shí)提高其收斂性。

1 概 述

1.1 多目標(biāo)優(yōu)化問(wèn)題相關(guān)定義

定義1(多目標(biāo)優(yōu)化問(wèn)題)：

MinF(x)=(f1(x),f2(x),…,fm(x))T,x∈Ω

(1)

其中，F(xiàn)(x)是m維目標(biāo)空間中的目標(biāo)函數(shù)，x=(x1,x2,…,xn)T是n維決策空間Ω中的決策變量。

定義2(Pareto支配)：

x支配y,記為xy，當(dāng)且僅當(dāng)?i∈{1,2,…,m}，fi(x)≤fi(y)，?i∈{1,2,…,m},且?j∈{1,2,…,m},s.t.fi(x)

定義3(Pareto最優(yōu)解)：

當(dāng)且僅當(dāng)一個(gè)解x*∈Ω在Ω中x*不會(huì)被其他解x所Pareto支配時(shí)，x*被稱為Pareto最優(yōu)解。

定義4(Pareto最優(yōu)解集，PS)：

在決策空間Ω中，對(duì)于一組給定的最優(yōu)解集，如果這個(gè)集合中的所有解都是Pareto最優(yōu)解，那么稱這個(gè)解集為Pareto最優(yōu)解集。

定義5(Pareto最優(yōu)前沿，PF)：

Pareto最優(yōu)解集中每個(gè)Pareto最優(yōu)解在目標(biāo)空間中對(duì)應(yīng)的目標(biāo)函數(shù)值向量組成的集合，被稱為Pareto最優(yōu)前沿。

定義6(理想點(diǎn))：

1.2 NSGAIII算法

NSGAIII算法步驟描述如下：

步驟1：初始化操作。

(2)生成初始種群X={x1,x2,…,xN}T，計(jì)算個(gè)體pi的目標(biāo)函數(shù)值Fi，i∈{1,2,…,N}，N為種群數(shù)量；

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

(1)進(jìn)化操作。父代種群X通過(guò)進(jìn)化操作(錦標(biāo)賽選擇策略，模擬二項(xiàng)式交叉算子，多項(xiàng)式變異算子)產(chǎn)生子代種群Y，并與之合并得到個(gè)體數(shù)為2N的合并種群R=X∪Y；

(3)環(huán)境選擇。對(duì)種群R進(jìn)行快速非支配排序操作，并利用小生境選擇策略對(duì)個(gè)體進(jìn)行選擇，得到個(gè)體數(shù)為N的新種群。

步驟3：如果達(dá)到最大迭代次數(shù)則結(jié)束算法；否則執(zhí)行步驟2。

2 WL-NSGAIII算法

2.1 基于權(quán)重的個(gè)體學(xué)習(xí)策略

圖1 新個(gè)體的進(jìn)化方向示意圖

新的個(gè)體更新公式為：

(2)

(3)

基于權(quán)重的個(gè)體學(xué)習(xí)策略的流程如下所示：

第一步：根據(jù)式(3)，計(jì)算子代種群Q中所有個(gè)體的T(x)值，并按照T(x)值從小到大排序，排在前m位的個(gè)體組成最優(yōu)集合S={xs1,xs2,…,xsm}，排在最后一位的個(gè)體作為最差個(gè)體；

第三步：從最優(yōu)集合S中隨機(jī)選擇一個(gè)個(gè)體作為優(yōu)秀個(gè)體；

2.2 小生境選擇改進(jìn)策略

在環(huán)境選擇階段，NSGAIII算法中的小生境選擇策略主要依靠解的分布對(duì)個(gè)體進(jìn)行選擇，即確定具有最少小生境計(jì)數(shù)的參考點(diǎn)集，然后選擇具有最短d2距離的個(gè)體。在這種選擇策略下生成的解集雖然有良好的多樣性，但由于缺少收斂性，可能遠(yuǎn)離前沿面。

針對(duì)這一問(wèn)題，該文利用收斂性信息d1對(duì)小生境選擇策略進(jìn)行了改進(jìn)。其中，d1,d2如圖2所示，d1是F(x)-Z*在參考點(diǎn)向量w上的投影，被用來(lái)評(píng)價(jià)個(gè)體x的收斂性；d2是一種衡量種群多樣性的方法。

圖2 收斂性與多樣性關(guān)系示意圖

在原有的小生境選擇策略中，如果同時(shí)存在多個(gè)參考點(diǎn)集則隨機(jī)選擇一個(gè)參考點(diǎn)，然后依賴個(gè)體的多樣性信息進(jìn)行相關(guān)的選擇操作。在此過(guò)程中可考慮加入個(gè)體的收斂性信息，以平衡種群的多樣性和收斂性，即如果同時(shí)存在多個(gè)參考點(diǎn)集則根據(jù)個(gè)體的收斂性信息進(jìn)行選擇。

圖3 參考向量所關(guān)聯(lián)的個(gè)體

小生境選擇改進(jìn)策略的步驟如下所示：

第一步：將種群中所有個(gè)體與距離其最近的參考點(diǎn)進(jìn)行關(guān)聯(lián)；

第二步：利用式(3)計(jì)算最后一層上待選擇個(gè)體的適應(yīng)度值，根據(jù)適應(yīng)度值對(duì)個(gè)體進(jìn)行排序，并按順序記錄與個(gè)體相關(guān)聯(lián)的參考點(diǎn)；

第三步：判斷算法中已選擇的個(gè)體數(shù)是否小于或等于種群個(gè)數(shù)N。如果沒有達(dá)到迭代次數(shù)或不滿足終止條件已選擇的個(gè)體數(shù)小于或等于種群個(gè)數(shù)N，則進(jìn)行第四步；如果已選擇的個(gè)體數(shù)大于種群個(gè)數(shù)N，則輸出種群；

第四步：將關(guān)聯(lián)個(gè)體數(shù)最少的參考點(diǎn)作為一個(gè)集合；

第五步：按照第二步中所記錄參考點(diǎn)的順序在第四步中得到的參考點(diǎn)集合進(jìn)行匹配查找。只要找到一個(gè)則立即停止查找并轉(zhuǎn)到第七步；如果查找完畢時(shí)，沒有找到相對(duì)應(yīng)的參考點(diǎn)，則轉(zhuǎn)到第六步；

第六步：從第四步所得到的集合中隨機(jī)選取參考點(diǎn)，對(duì)其相關(guān)聯(lián)的個(gè)體進(jìn)行判斷，如果為待選擇個(gè)體，則轉(zhuǎn)到第七步；如果為已選擇個(gè)體，則進(jìn)行標(biāo)記并重復(fù)第六步；

第七步：選取該個(gè)體；轉(zhuǎn)到第三步。

2.3 基于權(quán)重學(xué)習(xí)的高維多目標(biāo)進(jìn)化算法流程

根據(jù)2.1和2.2所述操作對(duì)NSGAIII算法的改進(jìn)，WL-NSGAIII算法的基本步驟如下所示：

第一步：初始化操作：生成參考點(diǎn)和理想點(diǎn)、初始化種群；

第二步：判斷算法是否達(dá)到迭代次數(shù)并滿足終止條件。如果沒有達(dá)到迭代次數(shù)或不滿足終止條件，則進(jìn)行第三步；如果達(dá)到迭代次數(shù)并滿足終止條件，則終止算法，輸出種群；

第三步：通過(guò)錦標(biāo)賽選擇算子、模擬兩點(diǎn)交叉算子和多項(xiàng)式變異算子進(jìn)行進(jìn)化操作，在父代種群的基礎(chǔ)上產(chǎn)生子代種群；

第四步：匹配選擇階段，利用基于權(quán)重的個(gè)體學(xué)習(xí)策略在子代種群的基礎(chǔ)上產(chǎn)生學(xué)習(xí)種群，將子代種群和學(xué)習(xí)種群進(jìn)行個(gè)體比較和保留，得到候選種群；

第五步：合并父代種群和候選種群；

第六步：更新理想點(diǎn)；

第七步:環(huán)境選擇階段，利用小生境選擇改進(jìn)策略對(duì)合并后的種群進(jìn)行個(gè)體選擇得到新種群；轉(zhuǎn)到第二步。

3 實(shí)驗(yàn)與分析

該文選擇經(jīng)典的KnEA[14]、GrEA[15]、ANSGAIII[13]、MOEADDE[16]、NSGA-III等算法作為對(duì)比算法。

3.1 評(píng)價(jià)指標(biāo)

采用常用的綜合性指標(biāo)反世代距離[17](inverted generational distance，IGD)作為評(píng)價(jià)標(biāo)準(zhǔn)。它主要通過(guò)計(jì)算每個(gè)在真實(shí)Pareto前沿面上的點(diǎn)(個(gè)體)到算法獲取的個(gè)體集合之間的最小距離和，來(lái)評(píng)價(jià)算法的收斂性能和分布性能。值越小，算法的綜合性能包括收斂性和分布性能越好。

(4)

其中，P為均勻分布在真實(shí)Pareto面上的點(diǎn)集，|P|為分布在真實(shí)Pareto面上的點(diǎn)集的個(gè)體數(shù)。Q為算法獲取的最優(yōu)Pareto最優(yōu)解集。而d(v,Q)為P中個(gè)體v到種群Q的最小歐幾里得距離。

3.2 參數(shù)設(shè)置

文中所有算法的種群大小保持一致且不同目標(biāo)個(gè)數(shù)的目標(biāo)函數(shù)有各自對(duì)應(yīng)的種群數(shù)量，如表1所示。算法的交叉概率均設(shè)置為1，變異概率均設(shè)置為1/D(D為變量數(shù)量)；最大評(píng)估次數(shù)為30 000，算法獨(dú)立運(yùn)行30次。

表1 種群參數(shù)設(shè)置

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

在模擬實(shí)驗(yàn)中，基于3～20個(gè)目標(biāo)的DTLZ1-DTLZ4測(cè)試集[18]中的IGD值，將WL-NSGAIII與KnEA、GrEA、ANSGAIII、MOEADDE、NSGA-III進(jìn)行了比較。實(shí)驗(yàn)結(jié)果如表2所示，在表中，“+”表示比WL-NSGAIII更好的結(jié)果，“=”表示與WL-NSGAIII相似的結(jié)果，“-”表示比WL-NSGAIII差的結(jié)果。粗體數(shù)字表示同一問(wèn)題的最佳結(jié)果。

通過(guò)比較6種不同算法的IGD值，可以看出WL-NSGAIII算法在DTLZ1-4測(cè)試問(wèn)題上的整體性能表現(xiàn)良好，尤其是在DTLZ1和DTLZ3測(cè)試問(wèn)題上表現(xiàn)突出?？梢?，基于權(quán)重信息的個(gè)體學(xué)習(xí)策略和小生境選擇改進(jìn)策略，能夠在維持種群多樣性的基礎(chǔ)上，增強(qiáng)其收斂性。

表2 在DTLZ測(cè)試集上不同算法的IGD值

續(xù)表2

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

針對(duì)種群個(gè)體進(jìn)化的盲目性以及依賴多樣性保護(hù)機(jī)制這兩個(gè)問(wèn)題，提出了一種基于權(quán)重學(xué)習(xí)的高維多目標(biāo)進(jìn)化算法WL-NSGAIII，分別從產(chǎn)生候選解和選擇候選解兩個(gè)角度對(duì)NSGAIII算法進(jìn)行改進(jìn)。在算法的匹配選擇階段，通過(guò)基于權(quán)重的個(gè)體學(xué)習(xí)策略，為種群個(gè)體提供進(jìn)化方向并增強(qiáng)候選解集的收斂性。同時(shí)，在算法的環(huán)境選擇階段，利用權(quán)重信息對(duì)小生境選擇策略進(jìn)行改進(jìn)。最終，在維持種群多樣性的同時(shí)提高其收斂性。通過(guò)模擬實(shí)驗(yàn)結(jié)果可以看到，WL-NSGAIII算法在處理高維多目標(biāo)優(yōu)化問(wèn)題上性能表現(xiàn)良好。