基于投影面的多目標優化問題進化算法MOEA/P

楊 爽, 陳未如

(沈陽化工大學 計算機科學與技術學院, 遼寧 沈陽 110142)

在實際工程應用中,存在很多目標優化問題(multi-objective optimization problems,MOP).這些目標通常都是相互矛盾、相互制約的,基本上不可能在所有目標上都求得最優解,但存在一個Pareto最優解集[1].Pareto最優解的含義是沒有任何其他解在各個目標上都比這個最優解更好.多目標優化算法的目標就是求解Pareto最優解集.由于可能存在無窮解,保證求解完整的Pareto最優解集是費時且幾乎不可能的,所以多目標優化算法都是求解Pareto最優解集的近似子集,即在已得到的所有可行解中求解非支配解集——不被已知其他解所支配的解的集合.

進化算法由于基于種群的特點而十分適合多目標優化問題的求解,在近幾十年的時間里成為國內外學者研究的熱點,尤其是在近20年的時間內有著突飛猛進的研究成果.在最初的多目標遺傳算法研究基礎上,學者們提出了許多典型的算法:以精英保護策略為主要特征的算法NSGAII[2],利用Pareto支配信息指導解集的選擇;基于分解的多目標進化算法(MOEA/D)[3],將一個多目標優化問題分解為一組單目標的子問題進行求解;基于指標評價的算法IBEA[4],通過評價指標指引算法的搜索方向,指導進化過程中新種群的選擇;還有一些研究專門研究如何確定多目標權重系數以達到更強尋優能力的目的[5].

近年來,面向超多目標優化問題的算法研究也取得了一定進展,在Google學術搜索上超多目標優化相關論文多達19 700條(2020年3月19日以“many objective optimization”為關鍵詞進行搜索).與多目標優化算法分類相同,面向超多目標優化問題的算法包括:(1)基于Pareto支配關系的超多目標進化算法,如GFM-MOEA[6];(2)基于改進支配關系的超多目標進化算法,如GPO[7];(3)將目標空間劃分為若干網格并利用網格坐標作為目標值來判斷Pareto支配關系的算法,如grid支配[8];(4)利用模糊邏輯提升某個解支配其他解概率的算法,如fuzzy支配[9];(5)利用小生境技術來判斷支配關系的算法,如SDR[10];(6)基于分解的超多目標進化算法,如MOEA/D-AWA[11];(7)基于性能指標的超多目標進化算法,如基于改進的IGD的AR-MOEA[12].

多目標優化所面臨的最大問題是存在大量、分散的解,影響算法的求解效率和求解質量.大多數算法都是面向整個解空間研究如何提高求解效率和求解質量,如果能夠在較小的范圍內求解,如重點關注某幾個目標,或選擇某些目標值范圍內的最優解等,將會大大提高求解效率和求解質量.當面向整個解空間求解時會得到大量的解,而過多的解會使用戶無從抉擇,因此有側重地去求所需要的解集,會使決策者在較小的范圍內得到自己所關心、期望的結果.這個問題在超多目標優化問題中也尤為突出.

筆者提出一種全新的求解多目標優化問題的思想——基于投影面的多目標優化問題進化算法(multi-objective optimization evolutionary algorithm based on projection plane,MOEA/P).借鑒基于分解的多目標進化算法思想,根據決策需求將目標空間分成投影面和自由維,再把投影面分割成多個投影格,由各個投影格決定求解方向,在各個投影格上求解自由維的最優值,從而得到多目標優化問題的最優解.在求解過程中,利用空間壓縮的進化方法,選擇適當的適應度函數,由大到小將種群個體壓縮向投影目標空間,逐步得到最終解.

投影面的劃分將高維多目標優化問題簡化成求解低維多目標優化問題,即僅在投影面上求解自由維目標的優化;投影格的分割將求解確定在由決策者指定的目標值具體范圍,提高了求解精度和效率.在本算法應用中,可以根據用戶的決策方向,有指導地選擇相應的投影格進行最優求解,既能夠保證求解的精度,又能夠保證所得解滿足用戶決策支持需求.

1 相關工作

以最小化問題為例,多目標優化問題可以描述為:

最小化:F(X)={f1(X),…,fm(X)}T.

約束到:gj(X)≥0,j=1,…,J,

hk(X)=0,k=1,…,K,

X∈Ω.

(1)

{F(X)|X∈Ω,gj(X)≥0,hk(X)=0}.

其中:j=1,…,J;k=1,…,K.

對于任意兩個決策向量u,v∈Ω,稱u支配v(記作uv).當且僅當 ?i∈{1,2,…,m}時有fi(u)≤fi(v);當?i∈{1,2,…,m}時有fi(u)

MOEA/D[3]是基于分解的多目標進化算法的代表,這類算法的核心思想是將一個多目標優化問題按照目標空間個數分為若干個單目標優化問題,同時求解這些子問題并將它們進行組合.在MOEA/D的基礎上改進的超多目標優化算法中,大多側重研究聚集函數的設計、權值向量的分配方式以及自適應方法.基于分解的多目標進化算法基本上采用參考點、參考向量以及權重向量等分解目標空間.由于目標解集可能存在解量大且不均勻的情況,因此,為了減少所得解的數量,得到有一定代表性的較小的解集,Yang等[8]將目標空間劃分為若干網格,并利用網格坐標作為目標值進行Pareto支配關系的判斷,從而將相近的解歸并成一個解.

2 投影面及投影支配

與其他基于分解的多目標進化算法不同,筆者將目標空間按目標維分解為兩部分:投影面和自由維.

定義1. 投影面:根據目標決策需求選取部分主要目標維構成投影面(projection plane),投影面上的各目標維稱為投影維(projection dimension).投影面P是多目標函數集F的純子集,即P?F.不失一般性,選取前m-1維目標作為投影面進行算法實驗分析.這樣,對于二目標優化問題,投影面就是f1坐標軸;對于三目標優化問題,投影面是f1、f2構成的一個坐標面.

定義2. 自由維:除投影面外的目標空間其他維稱為自由維(free dimension),由所有自由維所組成的集合稱為自由維集(free dimension set).自由維集D=F-P.

對于給定目標解向量f在投影面上的投影記為fp,在自由維集上的投影記為fd.

實驗中將最后一目標維fm作為自由維.圖1給出的是一個三維目標的投影面劃分.

圖1 三維目標空間劃分成投影面和自由維

定義3. 投影點和自由值:目標向量在投影面上的分量稱為投影點,在自由維上的分量稱為自由值.

定義4. 投影格:將投影面分割成一個個子面,稱為投影格(projection grid,PG).用其核心點作為標識向量,該標識向量稱為投影格向量(projection grid vector,Vg).Vg由組成投影面的各維度值構成.在不影響理解的情況下,以下簡稱投影格向量為投影格.

按照本文給出的算法求得落在指定投影面上的目標向量后,以該投影面所限定的子空間(投影格)為目標求解范圍,進化求解自由維最優解.

定義5. Pareto投影支配:設多目標優化問題F的投影面P和自由維集D.對于任意兩個決策向量u,v∈Ω,稱uPareto投影支配v(記作u?v).當且僅當?fp∈P時有fp(u)≤fp(v);當?fd∈D時有fd(u)≤fd(v);當?fd∈P時有fd(u)

定義6. 非Pareto投影支配解:非Pareto投影支配解是不被任何其他解Pareto投影支配的解.相應地,非Pareto投影支配解集NDP為所有非Pareto投影支配解的集合.以下簡稱非Pareto投影支配解為非投影支配解.

3 MOEA/P算法

筆者提出基于投影面的多目標優化問題進化算法MOEA/P.它不是求解多目標優化問題的所有Pareto前沿,而是根據目標決策需要將目標空間劃分成投影面P和自由維D,同時將投影面分割成投影格,求解非Pareto投影格支配解,進而得到Pareto投影前沿,并在此基礎上得到其中的全局非支配目標解.

宏觀上看,MOEA/P是一種基于分解的多目標進化算法.但與其他類MOEA/D算法不同,MOEA/P不是分解成若干個參考向量,而是將目標空間分解成兩部分:投影面和自由維.MOEA/P也進行網格分割,但分割對象不是整個目標空間,而是投影面,其目的是求各投影格上的最優解.

3.1 MOEA/P算法框架

MOEA/P算法框架

輸入:

多目標問題MOP;

結束條件;

DS:目標決策空間(投影面)設定;

ω:投影格邊長;

S:初始種群大小.

輸出:最優解集PS

過程:

步驟(1) 目標空間劃分

根據DS確定MOP投影面及投影范圍,并將之分割成邊長為ω的多個投影格PGs;

設目標解集PS為空.

步驟(2) 在每個投影格上求非投影支配解

對于PGs的每一個投影格,執行步驟①～③.

步驟① 初始化種群

初始化長度為S的種群G,構造種群中個體并初始個體基因序列,保證所有個體滿足MOP約束條件;

對種群G每個個體進行初始計算,得到相應的目標函數值;

設置投影格內個體非支配解個體列表GridList.

步驟② 種群進化

如果滿足結束條件,轉步驟③;

設置新一代個體池GenPOOL;

分別對種群G中的個體進化操作;

計算每一個新生成個體并根據適應度優先關系將之按序加入GenPOOL中,并將落入到相應投影格內的個體按支配關系插入到GridList;

令G=GenPOOL,并將GridList中的個體插入到G的前端;

對G進行截斷操作;

重復本步驟.

步驟③ 提交進化結果

將GridList中所有非投影支配個體提交到PS,并保證不與PS中任何現有個體相互Pareto支配.若存在Pareto支配關系對,則從PS中刪去被支配的個體.

步驟(3) 輸出PS

3.2 投影面分割

在MOEA/P算法中,目標空間劃分是求解的第一步,也是最重要的一步,它包括目標決策空間設定和投影面劃分兩部分.

目標決策空間設定是要選定投影面及相應決策范圍.投影面由用戶重點關注和設定的目標維組成.投影維的決策范圍即各投影維的決策上下界,它可以采用參考文獻[13]的方法設置缺省值,也可以由用戶設定所關注的區間.投影維決策范圍設定后通過歸一化方法,將整個目標空間變換為歸一化空間.目標決策空間的設定將最優化求解空間設定到一個較小的范圍內,可以大大縮小計算時間并提高計算精度.

投影面選定之后,需要根據投影格邊長將投影面分割成投影格,并將各投影格按鄰接關系排序,以便進一步求解.投影格由相應的投影格標識向量所標定,對投影面進行分割就是要生成相應的投影格向量.

3.3 適應度函數及投影盒

在MOEA/P算法中,適應度包括兩部分:投影格適應度δ和自由維適應度λ.

投影格適應度又稱空間適應度,是目標向量f距離指定投影格Vg的距離.

(2)

自由維適應度λ是自由維向量各維同理想值偏差平方和的開方.

(3)

在δ和λ的基礎上,MOEA/P算法采用空間壓縮思想,設置一個投影盒box,其計算公式為

box=α·λ+β·δ.

(4)

其中:box表示了一個目標向量與投影格Vg在目標空間的距離,其值越小,表明目標向量距Vg越近,就越接近最優值;α、β是適應度強度,反映了自由維和投影面的權重組合.通過進化計算,MOEA/P算法將所有種群個體向投影格向量壓縮,使box值在最小范圍內的非Pareto投影支配解被最后選中.

4 實驗及討論

4.1 算法性能

由于公式(4)的引入,算法大部分過程通過box向投影格進行壓縮,實際上是將多目標問題簡化為單目標問題.在將各目標個體向量壓入投影格后再進行Pareto投影支配比較,而此時各目標向量已經很接近最終值了.所以算法每次進化迭代的效率可以表示為O(N·LOGN·S),其中:N是種群大小;S是投影格數量.S根據用戶需要進行選擇設定,而由于投影格的劃分,N可以設置得很小.

算法是在將目標向量壓入投影格的同時使自由值最優,單目標化的過程保證了算法的收斂性.

算法的多樣性通過兩種途徑實現:一是投影格的劃分,保證有解的情況下各個投影格都會求得相應的較優解;二是算法設置的目標間距ε,保證目標個體間不會因為局部太近而使整個區間分布不均.

由于本文研究的是基于投影面的多目標優化問題的求解,并不追求整個目標空間的求解,所以一般用于評價算法性能的方法并不適用于本算法.設ND為算法得到的非Pareto支配解集,以下為算法性能指標相關概念.

(1)目標間距ε:為保證目標個體間不會因為局部太近而使整個區間分布不均,設置目標間距ε,其含義是任何兩個目標個體之間至少在一個目標維度上的值不小于ε,否則將被認為是相同的目標.

(2)自由維誤差δd:在某指定投影格上,如果有解,算法所求的解與理想解越近越好.自由維誤差表示的是所有ND對應非支配解的自由值與理想值距離的算術平均值.

(5)

(3) 投影誤差δp:目標個體與其投影點附近所有理想值之間的平均距離.

(6)

其中Dp是投影維個數.投影誤差δd可以同時反映算法的多樣性指標和收斂性.

4.2 與NSGA-II和MOEA/D算法的對比實驗

由于NSGA-II和MOEA/D是兩種影響非常廣的多目標優化問題進化算法,因此選擇與它們進行對比.參照參考文獻[3]的相關實驗,選擇雙目標測試用例ZDT1、ZDT2、ZDT3、ZDT4和ZDT6和三目標測試用例DTLZ1-DTLZ2進行對比實驗.原文采用種群大小N=100用于二目標測試,N=300用于三目標測試,進化250代.MOEA/P算法對二目標測試劃分4個投影格,對三目標測試劃分25個投影格,所有測試種群大小都設置為70,同樣進化250代.由于MOEA/P劃分了投影格,為公平起見,對MOEA/P算法在滿足足夠進化精度的種群大小情況下,通過調整目標間距ε使所得目標解個數分別在100和300左右.選擇相同環境(Intel CPU @3.2GHz)下運行,每組測試獨立運行30次.表1與表2中有關NSGA-II和MOEA/D的數據均來自參考文獻[3].

表1為算法NSGA-II、MOEA/D和MOEA/P求解部分多目標優化問題時相應的平均運行時間.表1結果顯示:MOEA/P算法除了在ZDT6用例上較MOEA/D相當之外,在其他用例上都有很大的優勢.

表1 NSGA-II、MOEA/D和MOEA/P平均運行時間

為了測試算法的收斂性和多樣性,參考文獻[3]使用了D-matric指標.設P*是一組在真實Pareto前沿上均勻采樣的解集,A為多目標進化算法求得的近似解集,d(v,A)是v與A中各點的最小歐式距離,則從P*到A的平均距離[3]定義為

(7)

與參考文獻[3]相同,選用均勻分布的500點和990點的P*進行D-matric計算.表2為算法NSGA-II、MOEA/D和MOEA/P求解部分多目標優化問題時相應的D-matric值(括號內為標準差).表2結果顯示:MOEA/P算法除了在ZDT3用例上較NSGA-II相當之外,在其他用例上都有明顯優勢,且具有更好的穩定性.

表2 NSGA-II、MOEA/D和MOEA/P D-matirc值

表3是MOEA/P算法求解部分問題所得解的投影誤差δp與D-matric計算結果(括號內為標準差).由表3可知:除在ZDT6上因個別點抖動(標準差增大)影響外,其他結果顯示投影誤差δp與D-matric基本在同一量級,可以用于MOEA/P算法在不同測試用例中進行收斂性和多樣性的評價.

表3 投影誤差δp與D-matirc值

4.3 超多目標優化實驗

對于4個目標以上的超多目標優化問題,往往很難用P*進行D-matric計算,大多數采用超體積指標進行算法的收斂性和多樣性測試.筆者利用投影誤差δp的概念對算法求解超多目標優化問題的性能進行評價.

選用DTLZ系列測試案例[14]進行超多目標測試.整體采用N=80大小的種群,進化200代.目標間距ε=0.05,分別對 3、4、5、6、7個目標的問題進行求解,每組實驗獨立運行10次,表4是相關測試結果(括號內為標準差).表4測試結果表明MOEA/P算法在求解超多目標問題時有較好的收斂性、多樣性和穩定性.

圖2是MOEA/P算法求解部分超多目標問題相應的運行時間與投影格個數的關系.圖2表明算法的運行時間與目標個數關聯不大,每次迭代運行時間基本上與投影格數目成正比關系.

表4 超多目標優化問題解的投影誤差δp值、算法運行時間t和解數目s

圖2 超多目標問題求解算法運行時間與投影格個數的關系

5 結論與展望

實驗表明基于投影面的多目標優化問題進化算法(MOEA/P)可以有效求解多目標優化問題甚至超多目標優化問題.筆者還進行了大量的相關實驗,包括求解質量與種群大小、進化代數的關系,不同投影面的選擇、目標值求解范圍的設定等,由于篇幅限制,本文不能充分展示.總體結論是:

(1) 由于投影面的設置,將原本復雜的高維多目標問題簡化成在投影面上的低維多目標問題,甚至是單目標問題,因而該算法很適用于求解超多目標問題.

(2) 由于可以選擇求解范圍,不必面向整個求解空間,可以選擇很小的種群進行進化,部分問題可以在種群大小為10的情況下進化求解,極大地提高了算法效率和求解精度.

(3) 可以針對不同目標空間范圍進行求精計算,從而對整個空間的整體高精度求解.

(4) 投影面可以根據用戶決策需求進行設置,也可以針對同一問題選擇不同的投影面進行求解,再將各解合并,得到分布更加合理的高精度解集.

MOEA/P還存在部分問題.由于投影面被均勻分割成多個投影格,而解的分布不一定是均勻的,所以存在所求解分布不均的情況,需要根據求解過程中解的分布自適應地進行局部投影格分割.如何充分結合現有其他算法有效求解自由維最優解,更是需要認真研究的.

目前,多目標優化問題以及超多目標優化問題的研究顯得尤為重要和迫切,尤其是對于超多目標優化問題這一難題.將MOEA/P進一步改進,并在適當的領域應用是我們下一步的工作目標.