基于分解和超平面擬合的進(jìn)化超多目標(biāo)優(yōu)化降維算法

劉海林 肖俊榮

(廣東工業(yè)大學(xué)應(yīng)用數(shù)學(xué)學(xué)院 廣州 510520)

1 引言

在自然科學(xué)和工程實(shí)際問題中，經(jīng)常會(huì)出現(xiàn)多目標(biāo)優(yōu)化問題。當(dāng)目標(biāo)個(gè)數(shù)大于3時(shí)，通常稱該問題為超多目標(biāo)優(yōu)化問題。隨著大數(shù)據(jù)的廣泛應(yīng)用，出現(xiàn)超多目標(biāo)優(yōu)化的情形將會(huì)越來越普遍[1-7]。目標(biāo)的增多可能會(huì)存在目標(biāo)之間不一定都是互相沖突的，其中可能存在一些目標(biāo)與其它目標(biāo)是正相關(guān)關(guān)系，這些目標(biāo)對(duì)求解該問題的前沿界面 (Pareto Front,PF)是不必要的，稱為冗余目標(biāo)。如果能找出這些冗余目標(biāo)，把它剔除，就可使求解的超多目標(biāo)優(yōu)化問題得到極大的簡化[1,8-11]。將冗余目標(biāo)從超多目標(biāo)優(yōu)化問題中剔除的過程稱為目標(biāo)降維[12,13]。在目標(biāo)降維研究領(lǐng)域，已有的算法主要分為下面兩種類型：

(1) 基于支配關(guān)系的算法。具有代表性的是[10]，該算法先用多目標(biāo)進(jìn)化優(yōu)化算法求得一組PF近似解，再利用這組解之間的支配關(guān)系，剔除那些對(duì)整體支配結(jié)構(gòu)影響較小的目標(biāo)。PCSEA[8](Pareto Corner Search Evolutionary Algorithm)是該類型另一個(gè)較知名的算法，與其它降維算法不同的是，PCSEA是先用多目標(biāo)進(jìn)化優(yōu)化算法找出所有的corner解，再利用這些corner解來判斷是否有冗余目標(biāo)。然而，PCSEA只能處理部分類型的目標(biāo)降維問題，有些情況無法處理，這點(diǎn)在該算法的論文中也有提到。

(2) 基于相關(guān)關(guān)系的算法。該類算法一般是先運(yùn)行多目標(biāo)進(jìn)化優(yōu)化算法求得問題的一組PF近似解，再根據(jù)這組解反映出的目標(biāo)之間的相關(guān)信息來找出冗余目標(biāo)。這類算法具有代表性的有文獻(xiàn)[14]提出的算法L-PCA, L-PCA可以處理PF為線性的目標(biāo)降維問題，但在處理一些PF為非線性的目標(biāo)降維問題時(shí)遇到了困難。為了解決該問題，Saxena等人[1]提出了算法MVU-PCA，MVU-PCA利用了流形學(xué)習(xí)中的算法MVU (Maximum Variance Unfolding)，把在幾何上非線性的PF轉(zhuǎn)化為線性的PF，再采用L-PCA的方法進(jìn)行目標(biāo)降維。MVUPCA在處理一些PF非線性的目標(biāo)降維問題時(shí)有了一定的效果。L-PCA和MVU-PCA可以較好地處理一些目標(biāo)與單個(gè)目標(biāo)正相關(guān)導(dǎo)致冗余的目標(biāo)降維問題，例如測(cè)試問題DTLZ5(I, m)[1]；對(duì)于目標(biāo)與多個(gè)目標(biāo)存在多元相關(guān)關(guān)系導(dǎo)致冗余的目標(biāo)降維問題則難以處理，例如測(cè)試問題MAOP(I, m)[9]。

文獻(xiàn)[15]提出了一種不同于上述類型的目標(biāo)降維算法，該文設(shè)計(jì)了一種用超平面擬合的算法，提出了算法LHA和NLHA[15]。該方法利用多目標(biāo)進(jìn)化優(yōu)化算法求得PF的一組近似解，再用一個(gè)超平面去擬合這組近似解，從而判斷出哪些目標(biāo)是冗余的。該方法簡單、高效，不僅可以處理冗余目標(biāo)與單個(gè)目標(biāo)正相關(guān)，還能處理冗余目標(biāo)與多個(gè)目標(biāo)線性組合正相關(guān)的目標(biāo)降維問題。遺憾的是，LHA在處理PF為非線性的降維問題時(shí)易出錯(cuò)，這點(diǎn)在LHA處理測(cè)試問題集MAOP(I, m)中有反映出來；而NLHA是通過一種目標(biāo)的冪變換，來使非線性的PF映射到新的目標(biāo)空間中靠近某個(gè)線性超平面，再用超平面擬合的方法進(jìn)行降維。遺憾的是，NLHA的處理方法只能把少部分類型的PF線性化，在復(fù)雜形狀的PF情況下，仍難以達(dá)到有效的降維效果。由于在實(shí)際問題中，非線性的PF更加常見，因此，在基于超平面擬合方法的基礎(chǔ)上，找到一種新的技術(shù)來處理PF為非線性的目標(biāo)降維問題具有重要的意義。

本文提出了一種基于分解和超平面擬合的目標(biāo)降維算法(Decomposition and Hyperplane Approximation, DHA)。該方法利用“以直代曲”的思想將幾何上非線性的PF近似解集分解為多個(gè)近似線性的PF近似解子集，通過構(gòu)建的帶擾動(dòng)項(xiàng)的稀疏超平面擬合的數(shù)學(xué)模型，找到一個(gè)最優(yōu)的綜合超平面去擬合這些子集，最后根據(jù)該超平面提取出原問題的本質(zhì)目標(biāo)集。相比于LHA, DHA可以更好地處理PF為非線性的目標(biāo)降維問題；相比于NLHA,DHA在處理非線性的PF時(shí)注重的是局部，通過放大局部特征，可以更好地把握目標(biāo)間的沖突關(guān)系，具有更好的穩(wěn)定性。

本文第2節(jié)簡單地引入目標(biāo)降維問題的一些相關(guān)概念；第3節(jié)將詳細(xì)介紹本文提出的目標(biāo)降維方法DHA；第4節(jié)將對(duì)本文提出的算法DHA進(jìn)行實(shí)驗(yàn)，并與其它有代表性的目標(biāo)降維算法進(jìn)行對(duì)比；第5節(jié)是對(duì)本文所做工作的總結(jié)。

2 目標(biāo)降維問題的相關(guān)概念與基于超平面擬合的目標(biāo)降維算法簡介

2.1 目標(biāo)降維問題的相關(guān)概念

一個(gè)多目標(biāo)優(yōu)化問題可以表示為下面的式子：

2.2 基于超平面擬合的目標(biāo)降維算法介紹

3 基于分解和超平面擬合的目標(biāo)降維算法

3.1 基本思想與模型的構(gòu)建

當(dāng)多目標(biāo)優(yōu)化問題的PF呈非線性時(shí)，采用基于超平面擬合的降維方法可能難以達(dá)到去冗余效果。例如，一個(gè)3個(gè)目標(biāo)的多目標(biāo)優(yōu)化問題，種群進(jìn)化到后期呈現(xiàn)如圖3所示情形。從圖中可以看出目標(biāo)f1和 目標(biāo)f2是 相互沖突的，f2與f3呈正相關(guān)關(guān)系，因此f3和f2中之一可作為冗余目標(biāo)去除。按照基于超平面擬合的降維算法，則需擬合出平行于f3或f2的平面，才可達(dá)到去冗余效果。而當(dāng)種群處于圖3的情形時(shí)，它的最優(yōu)擬合超平面很可能是圖3中的藍(lán)色平面，該平面的截距均大于0，依此超平面無法發(fā)現(xiàn)冗余目標(biāo)f3。 實(shí)際上，由于f3是冗余的，因此它對(duì)于種群中的每一部分來說都是冗余的。假設(shè)將圖3所示的種群分解為3個(gè)子種群，如圖4的紅色、綠色、藍(lán)色實(shí)心圓所示，去除f3對(duì)每個(gè)子種群內(nèi)個(gè)體的支配關(guān)系都不影響，即f3對(duì)于每個(gè)子種群來說都是冗余的。由于子種群的分布相對(duì)于整個(gè)種群通常更接近于線性的，因此從子種群更容易擬合出平行于冗余目標(biāo)的平面，達(dá)到去冗余的效果。

圖1 目標(biāo)均非冗余時(shí)超平面擬和種群示意圖

圖2 存在冗余目標(biāo)時(shí)超平面擬合種群示意圖

圖3 用超平面擬合非線性的種群分布的示意圖

圖4 多個(gè)平面擬合非線性種群分布示意圖

另一方面，應(yīng)該考慮的是分解后對(duì)子種群采用超平面擬合的方法會(huì)不會(huì)把本質(zhì)目標(biāo)錯(cuò)當(dāng)冗余目標(biāo)去除。實(shí)際上，由于子種群跟整個(gè)種群的沖突關(guān)系是不一定等價(jià)的，因此存在一些情況可能會(huì)導(dǎo)致過度降維。該情況是：當(dāng)某個(gè)目標(biāo)對(duì)于整個(gè)種群來說是不可或缺的，但它對(duì)于每個(gè)子種群來說又是冗余的。我們認(rèn)為出現(xiàn)這種情況是比較少的。對(duì)于大多數(shù)情況來說，本質(zhì)目標(biāo)至少對(duì)PF的某個(gè)部分來說是不可或缺的，一旦缺失會(huì)改變相應(yīng)部分個(gè)體之間的支配關(guān)系。

因此，針對(duì)非線性的PF，本文將種群分解為多個(gè)子種群，用基于超平面擬合的方法從子種群中提取冗余目標(biāo)，達(dá)到更好的去冗余效果。為避免從不同子種群提取出不同的本質(zhì)目標(biāo)集，本文采用單一超平面加一些細(xì)微的系數(shù)擾動(dòng)來擬合所有子種群，最后用該超平面反映的沖突關(guān)系作為提取結(jié)果。

根據(jù)上面的討論，本文提出了DHA的數(shù)學(xué)模型：

3.2 一種基于角度的分解策略

該分解方法既考慮了子種群中心的分布性又考慮了子種群內(nèi)個(gè)體的聚集性，既反映種群總體的特征，也反映它的局部特征。因此，該分解方法可以較好地保留種群攜帶的信息。

3.3 目標(biāo)降維算法框架

本節(jié)提出兩個(gè)算法框架，分別是在線的(表1)和離線的(表2)進(jìn)化目標(biāo)降維算法DHA框架。

在表1的步驟2中調(diào)整MOEA/D-M2M的權(quán)重向量是因?yàn)榛诜纸獾乃惴ㄔ讷@取初始權(quán)重向量時(shí)是在單位超立方里布點(diǎn)的，對(duì)于PF取值范圍差距很大的問題，若不調(diào)整權(quán)重向量的尺度，將導(dǎo)致后續(xù)再次進(jìn)化時(shí)獲取的解集的分布性較差，該策略在文獻(xiàn)[15]有詳細(xì)介紹。在表1的步驟3和步驟5分別是對(duì)問題的第1、第2次目標(biāo)降維。將相應(yīng)的種群輸入到離線的DHA中(表2)，DHA根據(jù)3.1節(jié)所述的原理和數(shù)學(xué)模型進(jìn)行降維，具體步驟在表2中。在第2次降維后若沒有目標(biāo)減少，則認(rèn)為已找不到冗余目標(biāo)并

表1 在線的進(jìn)化目標(biāo)降維算法DHA

表2 離線的目標(biāo)降維算法DHA

4 實(shí)驗(yàn)設(shè)計(jì)與實(shí)驗(yàn)結(jié)果

4.1 評(píng)價(jià)指標(biāo)

評(píng)價(jià)算法的性能需要恰當(dāng)?shù)脑u(píng)價(jià)指標(biāo)。本文采用文獻(xiàn)[15]中使用的成功率指標(biāo)和σ?指標(biāo)。其中，成功率是指在某個(gè)問題中成功提取本質(zhì)目標(biāo)集的概率，在計(jì)算時(shí)用對(duì)問題成功提取本質(zhì)目標(biāo)集的次數(shù)除以總運(yùn)行次數(shù)。對(duì)于σ?指標(biāo)，它的定義式為

4.2 參數(shù)設(shè)計(jì)

為了展示本文所提算法的效果，本文選擇了幾個(gè)有代表性的降維算法作為對(duì)比算法：基于相關(guān)關(guān)系的L-PCA和NL-MVU-PCA；基于支配關(guān)系的greedyδ-MOSS和PCSEA；基于超平面擬合的LHA和NLHA。對(duì)比算法的參數(shù)大小均設(shè)置為原論文設(shè)置的大小，如表3所示。

表3 降維算法參數(shù)表

為了檢測(cè)算法的效果，測(cè)試函數(shù)是必不可少的；本文采用了3個(gè)常用的目標(biāo)降維算法測(cè)試函數(shù)集：

對(duì)于實(shí)驗(yàn)數(shù)據(jù)的獲取分為無噪聲和帶噪聲兩種情況，無噪聲指從問題的真實(shí)PF中獲取數(shù)據(jù)；帶噪聲指未從PF取點(diǎn)，用多目標(biāo)進(jìn)化優(yōu)化算法運(yùn)行一次代數(shù)后的PF近似解集。近似解集中可能含有一些未收斂到真實(shí)PF的點(diǎn)，這些點(diǎn)稱為噪聲點(diǎn)。由于DTLZ5(I,m)和MAOP(I,m)是相對(duì)容易收斂的測(cè)試函數(shù)，因此本文對(duì)其獲取帶噪聲時(shí)的數(shù)據(jù)；而WFG3(I,m)是一個(gè)難以收斂的測(cè)試函數(shù)集，本文只測(cè)試它們?cè)谡鎸?shí)PF取點(diǎn)(無噪聲)的情況。

4.3 實(shí)驗(yàn)結(jié)果與分析

對(duì)于測(cè)試問題DTLZ5(I,m)。從表4、表5可以看出，本文提出的算法DHA與其他算法相比，具有較高的穩(wěn)定性。對(duì)于LHA, PCSEA在個(gè)別問題上的表現(xiàn)不佳，從表5顯示它們存在個(gè)別σ?值為0的情況，這反映著它們對(duì)應(yīng)問題上沒有去冗余效果。LHA, NLHA它們?cè)贒TLZ5(2, 50)的成功率較低，而σ?值卻較高，這顯示了雖然它們有不錯(cuò)的去冗余效果，但很多時(shí)候不能完全去冗余。而本文DHA在該問題上的兩個(gè)指標(biāo)值都穩(wěn)定且較高，這反映著DHA在個(gè)別情況下優(yōu)于LHA, NLHA。

表4 各算法在DTLZ5(I, m), WFG(I, m), MAOP(I, m)問題上的降維成功率

表5 各算法在DTLZ5(I, m)、WFG(I , m)，MAOP(I, m)問題上的的平均σ ?值

對(duì)于測(cè)試問題集WFG3(I,m)，它是一個(gè)PF為線性的測(cè)試問題集。從表4和表5可以看到，DHA對(duì)每個(gè)測(cè)試情況都能較好地處理，而對(duì)于算法LPCA, NLMVUPCA, PCSEA存在個(gè)別成功率和σ?值都為0的情況，即沒有降維效果。對(duì)于算法LHA,NLHA也能較穩(wěn)定地處理每種情況。對(duì)該測(cè)試問題，由于PF是線性的，DHA對(duì)于LHA和NLHA沒有明顯的優(yōu)勢(shì)，但也反映了DHA能較好處理PF為線性的帶冗余目標(biāo)的超多目標(biāo)優(yōu)化問題。

MAOP(I,m)中的冗余目標(biāo)不是跟單個(gè)目標(biāo)正相關(guān)，而是與多個(gè)目標(biāo)存在多元相關(guān)關(guān)系，這大大地增加了目標(biāo)降維的難度。從表4和表5可以看出，LPCA, NLMVUPCA對(duì)該問題的大部分測(cè)試情況的成功率和對(duì)應(yīng)的σ?值都較低，效果較差。PCSEA只能較好地處理前4種情況，對(duì)于后面4個(gè)測(cè)試情況效果較差。其它4個(gè)包括DHA可以較好地處理該問題。從greedy-δMOSS在MAOP2(3, 5)的測(cè)試結(jié)果看到，該算法也存在一些情況不穩(wěn)定的，受到了噪聲點(diǎn)的干擾。對(duì)于LHA和NLHA, DHA在MAOP4(4, 10)和MAOP6(6, 10)上有些許優(yōu)勢(shì)。LHA和NLHA在這兩個(gè)測(cè)試函數(shù)的成功率較低而σ?值卻較高，這是因?yàn)樗麄內(nèi)ト哂嘈Ч诲e(cuò)，但最終找出本質(zhì)目標(biāo)集的情況卻不多，而DHA在這兩方面都較好。

5 對(duì)DHA的進(jìn)一步探究

5.1 DHA對(duì)進(jìn)化算法的作用分析

為探究DHA在實(shí)際進(jìn)化過程中起到的效果，本文將施加DHA的MOEA/D-M2M記為DHAMOEA/D-M2M與未施加DHA的MOEA/D-M2M對(duì)超多目標(biāo)優(yōu)化問題求解效果進(jìn)行對(duì)比實(shí)驗(yàn)，用傳統(tǒng)的反轉(zhuǎn)世代距離[18](IGD)作為評(píng)價(jià)指標(biāo)。IGD的定義為

將DHA-MOEA/D-M2M與MOEA/D-M2M在測(cè)試問題DLTZ5(5, 10)，DLTZ5(2, 20)，DLTZ5(5, 20)進(jìn)行實(shí)驗(yàn)，兩個(gè)算法均運(yùn)行600代后停止，對(duì)于前者在進(jìn)化300代后調(diào)用DHA進(jìn)行1次目標(biāo)降維。對(duì)實(shí)驗(yàn)的其它參數(shù)設(shè)置同第4節(jié)。對(duì)每個(gè)問題獨(dú)立運(yùn)行20次，計(jì)算IGD值，實(shí)驗(yàn)結(jié)果如表6所示。

從表6可以看到，除了MAOP1(3, 5)，其它運(yùn)行結(jié)果均有明顯的提升。這反映了在進(jìn)化過程中使用DHA進(jìn)行目標(biāo)降維，可以有效提高所求解集的質(zhì)量。

表6 DHA-MOEA/D-M2M與MOEA/D-M2M在各個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行20次的平均IGD值與標(biāo)準(zhǔn)差

5.2 對(duì)DHA參數(shù)的敏感性分析

DHA需要設(shè)置兩個(gè)參數(shù)：子種群個(gè)數(shù)K和參數(shù)λ。在第4節(jié)的實(shí)驗(yàn)中K設(shè)為10，λ設(shè)為1。為檢驗(yàn)DHA的穩(wěn)定性，現(xiàn)將K取5個(gè)值：6, 8, 10, 12, 14，λ取5個(gè)值：0., 1, 1.5, 2, 2.5，兩個(gè)參數(shù)兩兩配對(duì)在測(cè)試問題MAOP5(6, 10)上進(jìn)行實(shí)驗(yàn)，計(jì)算各自降維成功率，將得到的25個(gè)實(shí)驗(yàn)結(jié)果作3維曲面圖，結(jié)果如圖5所示。從圖5可以看到，DHA對(duì)子種群數(shù)K和參數(shù)λ的取值在一定區(qū)域內(nèi)不敏感，通過合適的取值可以使DHA保持較高的成功率。

5.3 種群大小對(duì)DHA降維效果的影響分析

對(duì)于PF的真實(shí)維數(shù)較高的超多目標(biāo)優(yōu)化問題，若種群個(gè)體太少，則可能因難以刻畫真實(shí)PF的特征導(dǎo)致對(duì)問題過度降維的結(jié)果。由于DHA是基于種群分解，因此種群大小對(duì)DHA的影響會(huì)大于其他算法。為探究該影響，本文采用DTLZ5(2, 5),DTLZ5(5, 10), DTLZ5(7, 10)作為測(cè)試問題；將每次進(jìn)化代數(shù)G設(shè)為固定300；種群大小N分別設(shè)為20,30,50,100,200,300,400；其他參數(shù)同4.1節(jié)的設(shè)置。采用在線的DHA框架，對(duì)每個(gè)問題獨(dú)立運(yùn)行20次，實(shí)驗(yàn)結(jié)果如圖6所示。從圖中可以看到當(dāng)問題的PF真實(shí)維數(shù)不高時(shí)，如DTLZ5(3, 5)和DTLZ5(5, 10)，DHA對(duì)種群大小的要求不高，適當(dāng)?shù)娜≈稻色@得較高的成功率。而對(duì)于PF真實(shí)維數(shù)比較高的問題DTLZ5(7, 10)，此時(shí)種群不宜太小，太小則會(huì)影響效果。從圖6可以看到，當(dāng)種群大小設(shè)為200以上時(shí)，DHA對(duì)DTLZ5(7, 10)保持了較高的降維成功率。

圖 5 DHA對(duì)應(yīng)不同的K , λ 值在MAOP5(6,10)上的降維成功率曲面圖

圖 6 不同種群大小下，DHA在相應(yīng)問題的降維成功率變化圖

6 結(jié)束語

本文提出了一種基于分解和超平面擬合的目標(biāo)降維算法DHA。在該算法中，種群中的非劣解集基于角度被分解成多個(gè)非劣解子集，根據(jù)本文構(gòu)建的DHA的數(shù)學(xué)模型找到一個(gè)綜合的超平面結(jié)合擾動(dòng)項(xiàng)來擬合這些子集，進(jìn)而根據(jù)該超平面提取原問題的本質(zhì)目標(biāo)集。該算法既可以處理前沿界面分布為線性，也可以處理前沿界面分布為非線性的目標(biāo)降維問題。為了測(cè)試DHA的性能，采用3個(gè)常用的目標(biāo)降維測(cè)試問題DTLZ5(I,m), WFG3(I,m)和MAOP(I,m)，并與當(dāng)前具有代表性的目標(biāo)降維算法進(jìn)行對(duì)比。計(jì)算機(jī)仿真結(jié)果表明提出的算法無論前沿界面是線性或非線性的情形都具有優(yōu)異的性能。當(dāng)前的目標(biāo)降維算法大都是以進(jìn)化到一定代數(shù)的非劣解集作為近似的PF來找出冗余目標(biāo)，是否存在一個(gè)更好的判斷冗余目標(biāo)的方法，還有待進(jìn)一步研究。