基于近似邊界和層次聚類的超多目標進化算法

張 峰，顧一凡

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211100)

0 引 言

在實際工程優化問題中，往往需要同時優化多個沖突的目標，這類問題就被稱為多目標優化問題[1-2](multiobjective optimization problem，MOP)。目標數大于3的多目標優化問題，就被稱為超多目標優化問題(many-objective optimization problem，MaOP)。許多工程優化問題都屬于超多目標優化問題，高效地求解超多目標優化問題有著十分重要的理論意義和實際價值。

1 概 述

1.1 超多目標優化問題定義

一個連續的最小化超多目標優化問題(MaOP)的數學表達式如下：

(1)

其中，Ω∈Rn和F:Ω→Rm分別表示決策空間和m個實值目標函數組成的目標空間，x=(x1,x2,…,xn)T∈Ω稱為MaOP中的一個解。

1.2 相關定義簡介

假設兩個解u,v∈Ω，定義u支配v并簡記為uv，成立的條件是當且僅當對?j∈{1,2,…,m}都有fj(u)≤fj(v)，并且至少?i∈{1,2,…,m}使得fi(u)

理想點z*的定義如下：

(2)

極值點znad的定義如下：

(3)

其中，P'表示一個解集P的非支配解集。

決策者可以根據實際需要從算法近似的PF中挑選一個解進行決策。

收斂性和多樣性是衡量多目標優化算法性能的準則。收斂性是指算法近似出來的PF距離真實PF的遠近，多樣性是指算法近似的PF能否很好地覆蓋和表示整個PF。

1.3 多目標優化算法研究綜述

在過去的幾十年中，許多經典的多目標優化算法被提出來求解MOP，而多目標進化算法能夠通過進行大量目標函數評估來有效求解MOP。下面簡單介紹一些多目標進化算法。

NSGA-II[4]能夠通過快速非支配排序和計算擁擠距離來有效求解2到3目標的MOP，但在求解MaOP上，會出現許多非支配解，導致算法性能難以達到理想的效果。MOEA/D-DE[5]通過結合基于一組權重向量分解的方法和差分進化來有效求解一些具有復雜PS形狀的MOP，但由于算法中的權重向量是固定的，這不一定能很好地適應PF形狀，在求解一些PF形狀特殊的MaOP，MOEA/D-DE效果欠佳。為了更好地平衡算法在高維目標空間上的收斂性和多樣性，RVEA[6]通過一種角度懲罰距離的度量方法來自適應地調整權重向量分布，因此，RVEA能夠較好地求解MaOP問題。在一種被廣泛使用的評價指標Inverted Generational Distance[7](IGD)上，MaOEA/IGD[8]設計了一種高效計算支配比較的方法和提出了一種基于分解的高效近似極值點的方法，來更好地求解MaOP。盡管上述的多目標進化算法能夠從基于支配、分解和指標的角度來較好地求解MaOP問題，但由于MaOP目標空間過于龐大，算法使用的種群數量有限，如何在求解MaOP時更好地考慮算法的收斂性和多樣性一直是一個嚴峻的挑戰。

1.4 使用角點解近似理想點和極值點

Singh和Isaacs等人定義了角點解并提出一種求出角點解的方法[9]。角點解可能出現在以下這兩種極端的情況。(1)角點解位于一個只有某個目標最小的超平面上；(2)角點解位于軸坐標上，原點在理想點上。

角點解可以用來有效近似極值點。假設SC是一個角點解集，極值點的近似公式如下所示：

(4)

1.5 研究動機

在求解MOP時，平衡多樣性和收斂性是提升算法性能的關鍵。但在求解MaOP時，由于目標空間過大，并且算法往往只能使用數量較少的種群來近似問題的PF，這使得許多算法更難以較好地保持多樣性和收斂性。此外，大多數算法忽略了使用近似的極值點來固定近似的PF邊界，這會影響MaOP的求解速度。為了充分利用極值點的有效信息，該文使用一種求角點解的方法[9]來近似極值點，和使用極值點固定近似的PF邊界來排除比較差的解，借此來加速算法收斂，然后進一步提出使用層序聚類的方法來將種群劃分成多個聚類，并根據每個聚類中心自適應地產生一個權重向量，最后根據每個聚類中的解在對應權重向量的聚合函數來挑選下一代種群。通過上述方法使得算法能夠保持較好的收斂性和多樣性并有效地求解MaOP。

2 算法設計

2.1 算法框架

本節主要介紹提出的基于層次聚類和邊界近似的超多目標進化算法(MaOEA-ABHC)的實現細節，其中MaOEA表示超多目標進化算法，ABHC表示邊界近似和層次聚類。MaOEA-ABHC的算法框架如算法1所示：

算法1：MaOEA-ABHC算法框架。

輸入：N：種群數；

算法的終止條件。

輸出：最終種群P。

1.隨機生成規模為N的初始種群P；

2.while 沒達到終止條件 do

3.對P使用SBX算子產生子代Q；

4.PU=P∪Q；

5.使用PU近似z*；

6.根據PU求出角點解集SC并近似znad；

7.P=UpdatePop(N,PU,SC,z*,znad)；

8.end

9.returnP

MaOEA-ABHC主要分為3個階段：

(1)初始化：主要隨機生成一個規模為N的初始種群P。

(2)近似邊界：首先對當前種群P使用SBX算子來產生子代Q，然后根據式(5)來近似理想點z*：

(5)

根據Singh和Isaacs等人的工作[9]求出當前PU的角點解集SC，最后根據式(4)使用SC來近似極值點znad。

(3)更新種群：根據PU非支配解的數量與種群數的相應情況來更新當前種群P。

2.2 更新種群

更新種群相對比較復雜，首先獲取PU的非支配解集P'和剩余解集PR。

接下來進行第一次判斷，如果P'的數量|P'|大于種群數N，則先去除P'在znad外的解，并得到剩余解集P'和去除解集PE，再進行第二次判斷，如果P'的數量|P'|仍然大于種群數N，則使用層次聚類方法來挑選下一代種群。第二次判斷中，如果P'的數量|P'|小于種群數N，則根據PE中的解到z*的最短歐氏距離來挑選N-|P'|個解補充到P'。第一次判斷中，如果P'的數量|P'|小于種群數N，則根據PR中的解到z*的最短歐氏距離來挑選N-|P'|個解補充到P'。最后返回一個新種群P'，具體的實現細節可以參考算法2。

算法2：UpdatePop。

輸入：N:種群數;PU:父代和子代的合并種群;SC:PU的角點解集;z*:近似的理想點;znad:近似的極值點。

輸出：新種群P'。

1.獲取PU的非支配解集P'和剩余解集PR；

2.if |P'|>Nthen

3.去除P'在znad外的解，得剩余解集P'和去除解集PE；

4.if |P'|>Nthen

5.P'=HCSelection(N,P',SC)；

6.else

7.根據PE中的解到z*的歐氏距離挑選N-|P'|個解補充到P'；

8.end

9.else

10.根據PR中的解到z*的歐氏距離挑N-|P'|個解補充到P'；

11.end

12.returnP'

2.3 層次聚類選解

首先把PU的角點解集SC加入到新種群P，接下來使用層次聚類的方法挑選出剩下的N-|SC|個解加入到P中，|SC|表示角點解集的數量。

在層詞聚類前先對每個解x∈P'的目標向量進行歸一化，歸一化的公式如下：

(6)

(7)

算法3：HCselection。

輸入：N:種群數;P':候選種群;SC:PU的角點解集。

輸出：新種群P。

1.P=?；

2.P=P∪SC；

6.foreach idx∈Ido

8.按式(7)來計算聚類中心權重向量λidx;

11.P=P∪xB;

12.end

13.returnP

3 實驗設計

3.1 實驗參數設置

MaF系列測試問題[11]是一組流行的超多目標優化問題。該文主要選擇了MaF系列中前11個測試問題來檢驗MaOEA-ABHC與4個流行超多目標優化對比算法的性能，這些對比算法主要包括NSGA-II、MOEA/D-DE、RVEA和MaOEA/IGD。每個算法都獨立地運行目標變量數m為5和10的MaF1-MaF11測試問題30次。在5目標的MaF中，除了MaF7的決策變量數n為24和MaF8-9的n為2外，其他問題的n都為14；在10目標的MaF中，除了MaF7的決策變量數n為29和MaF8-9的n為2外，其他問題的n都為19。所有算法的種群數都設為200，并且每個測試問題的最大目標函數評估次數都設為100 000次。

除了上文提到的IGD指標外，還有Hypervolume Indicator[12](HV)、IGD+[13]和R2[14]等評價指標。該文主要使用一種考慮收斂性和多樣性的綜合指標HV來評價所有算法的性能，以上算法都在PlatEMO[15]上實現，并使用PlatEMO自帶的HV計算方法來計算所有算法的HV值。此外，還使用了置信度為0.05的Wilcoxon秩和檢驗來度量MaOEA-ABHC與其他對比算法的顯著性，其中符號=表示MaOEA-ABHC和其他對比算法沒有顯著性區別，符號+和-分別表示MaOEA-ABHC明顯地比其他對比算法好和差。

3.2 實驗結果

正如表1所示，MaOEA-ABHC在大多數測試問題上都取得了最佳的HV值，并且在大多數測試問題上，MaOEA-ABHC的算法性能都顯著地優于其他對比算法。由于HV是一種考慮多樣性和收斂性的綜合指標，這表明MaOEA-ABHC在解決各類型的MaOP上都能保持較好的多樣性和收斂性，并能有效地求解各類型的MaOP。

表1 所有算法在全部測試問題上的HV均值和顯著性符號(每個問題的最佳指標值加粗顯示)

4 結束語

許多工程優化問題都屬于超多目標優化問題。由于目標空間過于龐大，并且算法往往只能使用規模較少的種群來近似問題的PF，這使得多數算法難以保持較好的收斂性和多樣性。此外，許多算法往往忽視使用極值點的有用信息來幫助算法加速收斂并提升優化性能。在一個求角點解集方法的基礎上，該文使用角點解集近似邊界(極值點)并加速算法收斂，然后使用層次聚類進行選解來保證算法的收斂性和多樣性。在未來，將進一步拓展算法來研究并求解一些實際應用問題。