基于近似邊界和層次聚類的超多目標(biāo)進(jìn)化算法

張 峰，顧一凡

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

0 引 言

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

1 概 述

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

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

(1)

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

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

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

理想點(diǎn)z*的定義如下：

(2)

極值點(diǎn)znad的定義如下：

(3)

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

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

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

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

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

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

1.4 使用角點(diǎn)解近似理想點(diǎn)和極值點(diǎn)

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

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

(4)

1.5 研究動(dòng)機(jī)

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

2 算法設(shè)計(jì)

2.1 算法框架

本節(jié)主要介紹提出的基于層次聚類和邊界近似的超多目標(biāo)進(jìn)化算法(MaOEA-ABHC)的實(shí)現(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.對(duì)P使用SBX算子產(chǎn)生子代Q；

4.PU=P∪Q；

5.使用PU近似z*；

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

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

8.end

9.returnP

MaOEA-ABHC主要分為3個(gè)階段：

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

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

(5)

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

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

2.2 更新種群

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

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

算法2：UpdatePop。

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

輸出：新種群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'|個(gè)解補(bǔ)充到P'；

8.end

9.else

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

11.end

12.returnP'

2.3 層次聚類選解

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

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

(6)

(7)

算法3：HCselection。

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

輸出：新種群P。

1.P=?；

2.P=P∪SC；

6.foreach idx∈Ido

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

11.P=P∪xB;

12.end

13.returnP

3 實(shí)驗(yàn)設(shè)計(jì)

3.1 實(shí)驗(yàn)參數(shù)設(shè)置

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

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

3.2 實(shí)驗(yàn)結(jié)果

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

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

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

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