張 峰，顧一凡

(南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211100)

0 引 言

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

1 概 述

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

一個連續(xù)的最小化超多目標(biāo)優(yōu)化問題(MaOP)的數(shù)學(xué)表達(dá)式如下：

(1)

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

1.2 相關(guān)定義簡介

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

理想點z*的定義如下：

(2)

極值點znad的定義如下：

(3)

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

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

收斂性和多樣性是衡量多目標(biāo)優(yōu)化算法性能的準(zhǔn)則。收斂性是指算法近似出來的PF距離真實PF的遠(yuǎn)近，多樣性是指算法近似的PF能否很好地覆蓋和表示整個PF。

1.3 多目標(biāo)優(yōu)化算法研究綜述

在過去的幾十年中，許多經(jīng)典的多目標(biāo)優(yōu)化算法被提出來求解MOP，而多目標(biāo)進(jìn)化算法能夠通過進(jìn)行大量目標(biāo)函數(shù)評估來有效求解MOP。下面簡單介紹一些多目標(biāo)進(jìn)化算法。

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

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

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

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

(4)

1.5 研究動機(jī)

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

2 算法設(shè)計

2.1 算法框架

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

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

輸入：N：種群數(shù)；

算法的終止條件。

輸出：最終種群P。

1.隨機(jī)生成規(guī)模為N的初始種群P；

2.while 沒達(dá)到終止條件 do

3.對P使用SBX算子產(chǎn)生子代Q；

4.PU=P∪Q；

5.使用PU近似z*；

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

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

8.end

9.returnP

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

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

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

(5)

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

(3)更新種群：根據(jù)PU非支配解的數(shù)量與種群數(shù)的相應(yīng)情況來更新當(dāng)前種群P。

2.2 更新種群

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

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

算法2：UpdatePop。

輸入：N:種群數(shù);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.根據(jù)PE中的解到z*的歐氏距離挑選N-|P'|個解補充到P'；

8.end

9.else

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

11.end

12.returnP'

2.3 層次聚類選解

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

在層詞聚類前先對每個解x∈P'的目標(biāo)向量進(jìn)行歸一化，歸一化的公式如下：

(6)

(7)

算法3：HCselection。

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

輸出：新種群P。

1.P=?；

2.P=P∪SC；

6.foreach idx∈Ido

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

11.P=P∪xB;

12.end

13.returnP

3 實驗設(shè)計

3.1 實驗參數(shù)設(shè)置

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

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

3.2 實驗結(jié)果

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

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

4 結(jié)束語

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