基于權重學習的高維多目標進化算法

李杭涓，崔志華，謝麗萍

(太原科技大學 計算機科學與技術學院，山西 太原 030024)

0 引 言

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

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

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

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

1 概 述

1.1 多目標優(yōu)化問題相關定義

定義1(多目標優(yōu)化問題)：

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

(1)

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

定義2(Pareto支配)：

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

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

當且僅當一個解x*∈Ω在Ω中x*不會被其他解x所Pareto支配時，x*被稱為Pareto最優(yōu)解。

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

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

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

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

定義6(理想點)：

1.2 NSGAIII算法

NSGAIII算法步驟描述如下：

步驟1：初始化操作。

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

步驟2：種群進化。

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

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

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

2 WL-NSGAIII算法

2.1 基于權重的個體學習策略

圖1 新個體的進化方向示意圖

新的個體更新公式為：

(2)

(3)

基于權重的個體學習策略的流程如下所示：

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

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

2.2 小生境選擇改進策略

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

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

圖2 收斂性與多樣性關系示意圖

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

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

小生境選擇改進策略的步驟如下所示：

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

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

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

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

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

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

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

2.3 基于權重學習的高維多目標進化算法流程

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

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

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

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

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

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

第六步：更新理想點；

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

3 實驗與分析

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

3.1 評價指標

采用常用的綜合性指標反世代距離[17](inverted generational distance，IGD)作為評價標準。它主要通過計算每個在真實Pareto前沿面上的點(個體)到算法獲取的個體集合之間的最小距離和，來評價算法的收斂性能和分布性能。值越小，算法的綜合性能包括收斂性和分布性能越好。

(4)

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

3.2 參數(shù)設置

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

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

3.3 實驗結果與分析

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

通過比較6種不同算法的IGD值，可以看出WL-NSGAIII算法在DTLZ1-4測試問題上的整體性能表現(xiàn)良好，尤其是在DTLZ1和DTLZ3測試問題上表現(xiàn)突出。可見，基于權重信息的個體學習策略和小生境選擇改進策略，能夠在維持種群多樣性的基礎上，增強其收斂性。

表2 在DTLZ測試集上不同算法的IGD值

續(xù)表2

4 結束語

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