基于進化角度比較方法的高維多目標進化算法

劉中鋒，李浩君

（1.寧波廣播電視大學網絡傳播學院，寧波315016；2.浙江工業大學教育科學與技術學院，杭州310023）

0 引言

高維多目標優化問題（MaOPs）具有三個以上沖突目標，廣泛存在于現實應用中，例如工程設計[1]、空中交通控制[2]、地下水管理[3]和分子設計[4]等。被用于解決多目標優化問題（MOPs）的多目標進化算法不能很好地優化MaOPs問題[5-9]，主要原因包括兩個，第一個原因是收斂壓力的損失，在許多MaOPs問題中大多數候選解變得互不支配，從而導致傳統多目標進化算法中基于支配的選擇策略失效；第二個原因是多樣性管理困難，在許多MaOPs問題中，候選解在高維目標空間中分布稀疏，導致多目標進化算法的多樣性管理策略失效。為了更好求解MaOPs問題，一些改進方法[10-11]被提出，基本可以分為四類。第一類是基于收斂增強的方法，包括ε支配[12-13]，L最優[14]、模糊支配[15]、偏好次序排序[16]和θ支配[17]等。第二類采用性能指標取代Pareto支配作為選擇非支配解的標準[18-21]，相關算法有基于指標的進化算法[22]、基于S度量選擇的多目標進化算法[23]和基于超體積的進化算法[24]。第三類是基于分解的方法將MaOPs問題分解為一組簡單子問題，然后以協同優化的方式求解。例如，基于穩定匹配模型的MOEA/D[25]和帶有自適應權重向量調整方法的MOEA/D[26]。第四類將MaOPs問題轉換為一個多目標優化問題，利用已有的多目標進化算法進行求解。例如，基于支配關系保存算法[27-28]。

盡管多目標進化算法已經對MaOPs問題進行了大量研究，但對于多目標優化問題中的大規模決策變量研究較少[29]。Ma等人[30]提出了基于決策變量分析的多目標進化算法（MOEA/DVA），用于求解大規模MOPs問題。該算法中提出了一種基于支配關系的決策變量分析方法，將決策變量分為三類：收斂性相關變量、多樣性相關變量和同時與收斂性和多樣性相關的變量。這種決策變量分析方法能夠有效優化具有兩個或三個目標的大規模MOPs問題，但對MaOPs問題沒有探究。支配關系并不是區分決策變量進化狀態的唯一度量，例如，Cheng等人[31]的研究表明，候選解中決策變量與收斂方向之間的角度同樣可以用于測量決策變量的收斂性與多樣性。Zhang等人[32]在MOEA/DVA算法基礎之上提出了基于決策變量聚類方法的高維多目標進化算法（MLEA），用于求解大規模MaOPs問題。MLEA算法采用K均值方法對樣本解中決策變量和收斂方向的夾角進行聚類，具有較小夾角平均值的簇表示對收斂性貢獻更大，具有較大夾角平均值的簇對多樣性貢獻更大，通過這種聚類思路將決策變量分為兩類，即收斂性相關變量和多樣性相關變量。實驗表明MLEA算法在大規模MaOPs問題中具有一定的優勢，但是簇的夾角平均值不能直接反映進化狀態，因此，并不能有力促進種群的進化過程。

本文針對大規模MaOPs問題，在LMEA算法基礎上提出了基于進化角度比較方法的高維多目標進化算法（EACLMEA）。在進化角度比較方法中，首先從種群中隨機選擇若干樣本解，通過比較當前樣本解與另外三個隨機選擇樣本解的決策變量與收斂方向形成夾角大小，判斷決策變量的多樣性和收斂性；如果當前樣本解的決策變量夾角小于其中兩個或以上，則該決策變量夾角具有屬于全部決策變量夾角中較小值高概率，判斷該決策變量具有較小夾角值，否則該決策變量具較大夾角值的高概率；較小夾角表示對多樣性貢獻更大，被判斷為多樣性相關變量，較大夾角表示對收斂性貢獻更大，為收斂性相關變量。

1 LMEA算法

LMEA算法被設計用于求解大規模MaOPs問題，采用決策變量聚類方法將決策變量分為收斂性相關變量和多樣性相關變量。收斂性相關變量根據交互分析方法可以進一步劃分為若干收斂性相關變量子組，然后利用收斂性優化策略優化收斂性相關變量子組；多樣性相關變量則采用多樣性優化策略進行優化。

1.1 決策變量聚類方法

通過一個具有四個決策變量x1,x2,x3和x4的兩目標最小化問題來說明決策變量聚類方法。為了說明決策變量與收斂性相關還是與多樣性相關，首先從種群中隨機選擇nSel（本例中nSel為2）個候選解，所選擇候選解的每個決策變量都被執行nPer（本例中nPer為8）次擾動。

將擾動每個決策變量產生的樣本解歸一化，擬合歸一化樣本解以生成一條線L。所有樣本解組成超平面的法線與擬合線L的之間的角度被計算為f1+…+fm=1，其中M是目標數，法線代表了收斂方向。每一個決策變量都關聯了一些角度，角度的數量取決于用于決策變量聚類所選擇候選解的數量。因為本例中有兩個候選解被選擇用于決策變量聚類，因此每個決策變量xi，1≤i≤4，與兩個角度相關聯。決策變量聚類方法中，與決策變量關聯的角度用于測量決策變量對于收斂性和多樣性的貢獻，即較大的角度意味著該決策變量對多樣性貢獻更大，一個更小的角度對收斂性貢獻更大，更多的解被用于決策變量聚類，則會有更多的角度與每一個決策變量關聯，則對于決策變量的度量更加準確。

采用k均值聚類方法將決策變量分為兩簇，其中較小夾角平均值簇中的決策變量為收斂性相關變量，在另一個簇中的決策變量為多樣性相關變量。

1.2 交互分析方法

算法1用于說明決策變量交互分析過程。首先初始化交互作用的變量子組的空集合subCVs，然后根據決策變量之間的交互作用，將收斂性相關變量集合CV中的變量分配給不同的收斂性相關變量子組，其中交互關系被定義如下：給定一個MOP問題，min f=min(f1,f2,…,fm)，如果存在x,a1,a2,b1,b2和至少一個 fk,1≤k≤m，滿 足 fk(x)|xi=a2,xj=b1fk(x)|xi=a1,xj=b2，其中fk(x)|xi=a2,xj=b1=fk(x1,…,xi-1,a2,…,xj-1,b1,…,xn)，則決策變量xi和xj存在交互作用。具體來說就是，如果一個變量與subCVs中至少一個現有變量交互，那么這兩個變量被分配到同一個子組，否則，該變量被分配到一個新的子組。重復此操作，直到每個與收斂性相關的變量都分配給一個子組。因此在極端情況下，最多會有|CV|個子群，即收斂性相關變量是完全分離的，相反，如果收斂性相關變量是完全不可分的，則只有一個子群。

算法1：InteractionAnalysis（P，CV，nCor）

輸入：P（當前種群），CV（收斂性相關變量集合），nCor（被選取用于決策變量交互分析的解的數量）

輸出：subCVs（CV中的交互決策變量子組集合）

1:subCVs←?;

2:forall th ev∈CVdo;

3:CorSet←?;

4:forall th e Group∈subCVsdo

5: forall th eu∈Groupdo

6: flag←false;

7: for i=1tonCor do

8: Randomly selecta solution p from P;

9:if v isinteracted with u in p then

10: flag←true;

11:CorSet←CorSet∪{Group};

12:break;

13:if flagthen

14: break;

15:if CorSet==?th en

16: subCVs←subCVs∪{{v}};

17:else

18: subCVs←subCVs/CorSet;

19:Group←all var iablesin CorSet and v;

20:subCVs←subCVs∪{Group};

1.3 基于樹快速非支配排序方法（T-ENS）

T-ENS核心思想是利用一棵樹來表示每一個非支配前沿的解，樹中節點用于存儲解，同時也存儲決定解之間支配關系的目標信息，可以從分配給非支配前沿的解（即樹中的解）推斷出很多非支配關系，從而可以減少同一前沿解之間的比較次數，因此，提高了快速非支配排序的計算效率，該方法的具體過程如算法2所示。

算法2：T-ENS的主要步驟

輸入：P（種群），M（目標數）

輸出：F（前沿集合，每個前沿被一棵樹表示）

1:根據第一個目標升序排列P;

2:F←?;

3:k←0;

4:whilenot_empty(P) do;

5:k←k+1;

6:for all th ep∈Pdo

8:update_tree(p,F[]k,objSeq);

9:return F;

1.4 收斂性優化策略與多樣性優化策略

在算法1完成交互分析后，LMEA算法開始使用收斂性優化策略逐個優化每一個收斂性相關變量子組，過程如算法3。在收斂性優化策略中，利用T-ENS對父代種群進行非支配排序，計算出每一個候選解到理想點的歐氏距離。每個子組中的變量，使用二元競賽法則從種群P中隨機選擇兩個候選解，然后利用重組算子生成的變量替代同一子組中的決策變量值，保持剩余決策變量不變，以生成子代候選解。當且僅當子代候選解在非支配排序中具有較小的非支配前沿數，或者它具有與父代相同的非支配前沿數，但與理想點之間的歐氏距離較小時，子代候選解被認為具有比其父代解具有更好的收斂性。那么如果子代候選解比其父代具有更好的收斂性，則選擇將其作為下一代，否則子代候選解被丟棄，父代候選解作為下一代。

算法3：ConvergenceOptimization（P，subCVs）

輸入：P（當前種群），subCVs（收斂性相關變量子組的集合）

輸出：P（下代種群）

1:Front←Nondo min atedSort(P);

2:計算P中每個解和原始點在目標空間中的距離

3:forall th eGroup∈subCVsdo

4:nEvaluated←0;

5:whilenEvaluated< ||P do

6: S←?;

7: for i=1to ||P do

8: if rand()

9: S←S∪{i};

10:O←?

11:for s∈Sdo

12:通過二元競賽從P中選擇p1和p2，其中每個解的前沿數和距離被用于作為第一和第二標準;

s'(G roup)表示在組Group中決策變量以上的組成s'值的一個向量*/

14:s''←s;

15:s''(Group)←s'(Group);

16:O←O∪{s''}

17:nEvaluated←nEvaluated+|O|;

18:Front←Nondo min atedSort(P∪O);

19:計算目標空間中O中的所有解和原始點之間的距離;

20：根據前沿數和距離，用O中每個解替代P中相應的解;

在多樣性優化策略中，通過將所有多樣性相關變量作為一個整體進行優化，以從P種群中生成|P|子代；然后，子代與父代進行組合，組合種群通過兩階段進行環境選擇。首先，從k-1個前沿中選擇候選解，k是滿足|F1∪F2∪…∪Fk|>|P|的最小值；來自前沿Fk的最好多樣性的剩余候選解被一個一個地選擇直到種群規模|P|被達到，多樣性通過目標空間中候選解之間的角度進行測量。多樣性優化策略如算法4所示。重復算法3和算法4直到終止條件滿足。

算法4：DiversityOptimization（P，DV）

輸入：P（當前種群），DV（多樣性相關變量）輸出：Q（下代種群）

1:O←?;

2:forall thep∈Pdo

3:隨機從P中選擇p1和p2;

4: p'(DV)←recombination(p1(DV),p2(DV));

5: p''←p;

6: p''(DV)←p'(DV);

7:O←O∪{p''};

8:F←Nondo min ateSort(P∪O);

9:Q←F1∪F2∪…∪Fk-1，其 中 k是 滿 足|F1∪F2∪…∪Fk|>|P|的最小值;

10:if Q=?th en

11:Q←在Fk中的所有極值;

12:Fk←Fk/Q;

13:計算所有目標空間中Q∪Fk內任意兩個解之間的角度;

14:while ||Q< ||P do

15: p←argmaxx∈Fkminy∈QAngle[]x[y];

16:Q←Q∪{p};

2 EACLMEA算法

EACLMEA算法采用了LMEA算法的基本結構，同時在EACLMEA算法中引入了進化角度比較方法替代LMEA算法中的決策變量聚類方法。

2.1 EACLMEA算法的主要框架

EACLMEA算法如算法5，由五部分組成。第一部分隨機初始化包括n個候選解的種群；第二部分采用進化角度比較方法將這些變量分為兩組，即收斂性相關變量和多樣性相關變量；第三部分依據交互分析方法，如算法1，將收斂性相關變量進一步劃分為若干收斂性相關變量子組，同一子組內變量間存在交互作用，不同子組間的變量不存在交互作用關系。第四部分采用收斂性優化策略，如算法3，優化收斂性相關變量子組；第五部分采用多樣性優化策略，如算法4，優化多樣性相關變量。

算法5：EACLMEA算法的主要框架

輸入：N（種群大小），nSel（被選取用于決策變量進化角度比較的解的數量），nPer（決策變量進化角度比較中每個解被擾動的數量），nCor（被選取用于決策變量交互分析的解的數量）

輸出：P（最終種群）

1:P?Initialize（N）;

2:[DV，CV]?VarialbleEvolutionAngleCompare（P，nSel，nPer）;

3:subCVs?InteractionAnalysis（P，CV，nCor）;4:while termination criterion not fulfilled do

5:P?ConvergenceOptimization（P，subCVs）;6:P?DiversityOptimization（P，DV）;

7:end while

2.2 進化角度比較方法

進化角度即決策變量與收斂方向之間的夾角，計算方法為從種群中選擇nSel個樣本解，每個樣本解的決策變量被擾動nPer次，以生成擾動樣本解，然后將擾動樣本解歸一化，生成歸一化樣本解。并通過線L擬合歸一化樣本解中的決策變量。線L與歸一化樣本解組成超平面的法線形成夾角，即為歸一化樣本解中決策變量的進化角度，法線代表收斂方向，因此進化角度也可以表述為決策變量與收斂方向之間的夾角。進化角度比較方法，如算法6所示，核心思想是通過進化角度大小判斷決策變量屬于收斂性相關變量還是多樣性相關變量。對于某一決策變量i，如步驟2，為了判斷決策變量i是多樣性相關還是收斂性相關，隨機從種群P選擇nSel個樣本解，如步驟3，通過比較當前樣本解，與另外三個隨機選擇樣本解中決策變量夾角的大小，得出決策變量是否具有所有決策變量中較小值的高概率，如果具有較小值高概率，判斷決策變量i為多樣性相關變量，否則為收斂性相關變量。

算 法6：VarialbleEvolutionAngleCompare（P，nSel，nPer）

輸入：P（當前種群），nSel（被選擇用于決策變量進化角度比較的解的數量），nPer（被選擇用于決策變量進化角度比較的每個解的擾動數）

輸出：DV（多樣性相關變量），CV（收斂性相關變量）

1:D←決策變量的長度;

2:for i=1 to Ddo

3:S←從P中隨機選擇nSel個解;

4: for j=1 nSel todo

5: 擾動S[]j的第i個決策變量nPer次以生成一個種群SP;

6: 歸一化SP;

7:為SP擬合一個線L;

8: Angle[i][j]←計算L和超平面的法線之間的角度，f1+…fM=1，M是目標數;

9:K←randsample(nSel,3);

10:if Angle[i][j]小于Angle[i][ K(1)]、Angle[i][ K(2)]和Angle[i][K (3)]中兩個或三個值

11:JudgeAngle[i][j]←0;

12:elseif Angle[i][j]小于Angle[i][ K(1)]、Angle[i][K (1)]和Angle[i][K (1)]中兩個或三個值

13:JudgeAngle[i][j]←1;

14: else JudgeAngle[i][j]←1

15:CV←{i=1,…,D|mean( MSE[i])<1e-2};

16: if any( JudgeAngle(C V)==1)≠?and any(JudgeAngle(C V)==0)≠?

17:if JudgeAngle(C V,:)==1

18: CV=CV&JudgeAngle==1

19:else CV=CV&JudgeAngle==0

20:DV←{j=1,…,D|j?CV};

3 實驗與分析

為了驗證EACLMEA算法在大規模MaOPs問題中的性能，對比了三種最新的多目標進化算法，即MOEA/DVA算法[30]、NSGA-III[33]算法和LMEA算法[32]。

使用被廣泛使用的測試集LSMOP[34]作為實驗問題，LSMOP測試集用于研究者開發多變量和高維多目標問題，允許創建帶有任何數量決策變量和目標數的函數。LSMOP包括9個測試問題，LSMOP1-LSMOP9，在本研究中所有測試問題的目標數均為5個，決策變量分別考慮100個和1000個，所有測試問題均為大規模MaOPs問題。

3.1 實驗設置

為了進行公正比較，用于比較的算法參數均采用原文獻推薦值以獲得最佳性能，其他公用參數具體設置如下：

（1）種群規模、最大評估次數和運行次數：所有算法種群規模均為10，最大評估次數為1000，在每個測試問題上，每個算法獨立執行20次，以獲得統計結果；

（2）本文提出的EACLMEA算法相關參數：進化角度比較方法中，種群中被選擇用于進化角度比較的樣本解的數量nSel=5，每個樣本解被擾動數為nPer=50，用于交互分析方法中的解的數量為nCor=5。

（3）性能指標：采用被廣泛使用性能指標，翻轉世代距離（IGD）作為評價算法的性能指標，IGD值越小，解集質量越好。

3.2 結果與討論

表1給出了四種算法在具有100和1000個決策變量的9個測試問題LSMOP1-LSMOP9上，20次獨立運行獲得的IGD值的統計結果，最佳結果顯示為灰色背景。其中符號“+”、“-”和“≈”分別表示在0.05顯著水平的Wilcoxon軼和檢驗上，相比EACLMEA算法的IGD值，顯著更好、更差和統計學沒有差異。

表1四種算法在測試問題LSMOP1-LSMOP9上獲得的IGD值

從表1中可以得出兩個觀察結果，首先LMEA和EACLMEA總體獲得更好的IGD值，且EACLMEA獲得更多的最優IGD值。EACLMEA在LSMOP5-LSMOP9和具有100個決策變量的LSMOP3上具有更好的結果；LMEA在LSMOP1、具有100個決策變量的LSMOP2、具有1000個決策變量的LSMOP3和具有100個決策變量的LSMOP4上具有更好的IGD值。在Wilcoxon軼和檢驗結果中，在LSMOP9、具有100個決策變量的LSMOP2、具有1000個決策變量的LSMOP4和具有1000個決策變量的LSMOP6上，LMEA和EA?CLMEA在統計學上沒有差異。EACLMEA算法獲得更多最優IGD值原因是，進化角度比較方法能夠將決策變量準確區分為多樣性相關變量和收斂性相關變量，通過相關優化策略獲得較好的IGD值；EACLMEA算法整體上比LMEA算法具有更優的性能，原因是EA?CLMEA算法將具有較小夾角的決策變量判斷為多樣性相關變量，從而使更加偏向收斂方向決策變量的多樣性得到充分利用。其次，隨著決策變量從100變為1000，EACLMEA算法都能獲得較好的IGD值，說明該算法能夠適應高維度多目標優化問題中，大規模決策變量的優化需求。

4 結語

本文提出基于進化角度比較方法的高維多目標進化算法（EACLMEA），進化角度比較方法根據當前樣本解與隨機選擇樣本解的決策變量與收斂方向形成夾角的大小比較，判斷當前樣本解的決策變量為收斂性相關變量或多樣性相關變量，如果當前樣本解的決策變量小于大多數隨機選擇樣本解決策變量夾角，則判斷決策變量為多樣性相關變量，采用多樣性優化策略進行優化；否則采用收斂性優化策略優化該決策變量。結果表明EACLMEA算法在大多數LSMOP問題中取得更好的IGD值，即進化角度比較方法能夠有效解決大規模高維多目標優化問題。