一種基于PBI指標支配的多目標優化算法

南寧師范大學計算機與信息工程學院 郭華

利用支配和指標度量結合的方式提出一種新的支配關系，通過該支配關系構造出新的多目標優化算法MOEA-PBI，該算法對多目標優化問題進行有效優化，從而得出一組可供選擇的折中解。新算法與其他三種代表性的多目標進化算法一同在3，5和8目標的DTLZ基準測試問題上進行測試，結果表明MOEA-PBI算法具有較為優秀的收斂性和多樣性。因此得出結論，MOEA-PBI算法是一種可以選擇的多目標進化算法。

現實中存在著很多需要同時優化多個目標的優化問題，這類問題統稱為多目標優化問題（Multiobjective Optimization Problems，MOPs），MOPs的解方案通常并非單個解，而是一組折中解。為解決這些MOP問題，研究者們提出了一些有效的多目標進化算法（Multi-objective Evolutionary Algorithms，MOEAs）。目前常見的MOEAs主要分為三大類：(1)基于分解的多目標進化算法，張青富等人在2007年提出的MOEA/D算法開創了分解策略應用于解決MOP問題的先河，該算法通過在目標空間生成均勻分布的權重向量來引導解個體的收斂。(2)基于支配關系的多目標進化算法，Deb等人提出的NSGA-II算法在NSGA算法的基礎上增加了快速非支配排序策略，使得基于Pareto的NSGA-II算法在解決MOP問題時不僅具有良好的收斂性和分布性，而且大大降低了時間復雜度。(3)基于指標的多目標進化算法，Bader等人基于超體積（Hypervolume，HV）指標提出HypE算法，通過HV指標將不可直接進行比較的解個體向量，轉化為可以直接比較大小的標量，從而進行個體篩選和優化。

但隨著優化問題的目標個數增多，傳統的MOEAs已經不能很好地解決四個及以上的高維多目標優化問題（Many-objective Optimization Problems，MaOPs），本文通過將基于支配的方法與基于指標的方法結合，利用支配關系的收斂性優勢和指標方法的多樣性優勢，從而解決高維多目標優化問題。

1 預備知識

1.1 MOP問題的基本概念

一般而言，最小化問題可表示如下：

其中，x=(x,x,...x)∈X?R是n維決策向量，X為n維決策空間；y=(y,y,...y)∈Y?R為m維的目標空間；目標函數F(x)定義了由決策空間X向目標。空間Y映射的函數，g(x)定義了p個不等式約束，h(x)定義了q個等式約束。約束函數g(x)和h(x)共同確定了決策向量x的可行域。一般當目標數m≥4時，式(1)中的MOP問題又被稱為MaOP問題。下面是MOP問題中一個重要的概念。

1.2 基于懲罰的邊界相交法PBI的概念

PBI方法來源于MOEA/D算法的效用函數。在MOEA/D算法中，PBI作為一個可選擇的函數，在度量解個體的優劣上體現出了它的優越性。PBI方法由可以度量個體收斂性和個體分布性的兩個指標構成，它們分別是d距離和d距離。d距離代表的是個體在權重向量上的投影到原點的距離，所以d距離可以直觀地表現出個體的收斂性。d距離代表的是個體到權重向量的垂直距離。而權重向量在初始設置中，是一組從原點出發、均勻分布的向量，所以個體越靠近權重向量，個體分布也就越均勻。即d距離可以直觀地刻畫出個體的分布性。具體地，PBI方法采用式（2）的方式計算，PBI值總體越小，則表示個體的收斂性和分布性越好，即個體越優秀。其中變量θ的作用是均衡種群的收斂性和分布性，當種群收斂過快而分布性較差時，就需要將θ值放大來強調收斂性，反之亦然。

求解MOP需預先在目標空間生成一組均勻分布的權重向量，權重向量從原點出發，沿著各自的方向延伸并與可達目標空間的最左下邊界（即規范化的PF）相交。通常，如果權值向量的數目設置合理，那么在PBI方法的引導下，可以產生一組較為優秀的解個體。圖1為PBI方法在雙目標優化問題上的形象描述。其中，F(x)為目標空間的任意一點,λ為一個權重向量，則d表示F(x)的投影點y與原點之間的距離，d表示F(x)與權重向量λ之間的垂直距離。

圖1 PBI示意圖Fig.1 Schematic diagram of PBI

2 MOEA-PBI算法

受MOMBI算法的啟發，通過計算個體基于懲罰的邊界相交法(Penalty-based Boundary Intersection，PBI)的值來度量解的優劣性。每一個個體對于任意一個權重向量都有唯一的PBI值，在支配關系中應用該值平衡收斂性和分布性，則能對種群個體進行一個合理的支配分層。算法的具體步驟：(1)首先生成具有N個個體的初始種群，同時在目標空間生成與個體數目相同的N個均勻分布的權重向量；(2)在每一代中，計算每個個體到每個權重向量的PBI值；(3)在同一個權重向量下，根據PBI值大小對每個個體進行升序排序，并賦予個體序號值；(4)循環步驟(3)，對全部N個權重向量進行上述操作；(5)對于任意個體而言，它將具有N個針對不同權重向量的序號值，存儲其中最小的序號值作為該個體在全部個體中所處的非支配層數，非支配層數越小，則表示個體越優秀，也就越容易進入下一代進化中。至此，不同個體所在非支配層之間的支配關系構建完成。

傳統的多目標進化算法在保持種群多樣性方面，一般采用擁擠距離的度量，該方法存在一定缺陷，即在高維空間中歐氏距離的度量不再適用。個體的擁擠距離存在不能準確度量個體擁擠度的問題，在種群迭代的時候，該問題會導致分布性差的個體反而被保留，進而導致種群多樣性較差。如公式(3)所示，本文采用PBI指標值度量個體多樣性適應度，即利用公式(2)計算最后一層非支配層中個體對于各個權重向量的PBI指標值（一般θ取值為5），選擇最小的PBI值作為該個體的多樣性適應度。P表示個體i的多樣性適應度，PBIj∈{1，...，N}表示個體i與每一個權重向量j都進行PBI計算，最終保留最小值。圖2以MOEA-PBI算法的第t代為例說明算法的運行機制。

圖2 MOEA-PBI算法運行機制Fig.2 Operating mechanism of MOEA-PBI

3 實驗與分析

一般針對MOP問題的MOEAs大多利用Das等提出的方法產生權重向量，但對于MaOPs問題來說，其目標數通常≥4，如果仍然使用該策略，則會使得產生的種群數目過于龐大。為此，本文利用雙層參考向量生成方法。

為驗證MOEA-PBI的算法性能，本文將其與三種經典的多目標算法進行實驗對比，分別是RPDNSGA-II、NSGA-II、MOEA/D。四種算法一同在3-、5-和8-目標的DTLZ系列測試問題集上進行實驗，通過IGD性能指標以檢驗算法的收斂性和多樣性。實驗中對各目標數的種群規模分別設為92、212和156，評估次數為50000。表1列出了四種算法在DTLZ系列測試問題上獲得的IGD均值和方差。表內各行最佳的結果加粗表示。其中MOEA-PBI、MOEA/D、RPD-NSGA-II、NSGA-II算法在這些測試實例上獲得最佳IGD均值的個數分別為9、3、2、1。另外，從表1的檢驗結果來看，MOEA-PBI相對于MOEA/D、RPD-NSGA-II、NSGA-II的凈勝得分(得“-”數目減去得“+”的數目)分別為5，11，11。綜上，MOEA-PBI算法在求解DTLZ系列問題時具有顯著較優的性能。

表1 四種算法在DTLZ系列問題上獲得IGD值Tab.1 The IGD values of the 4 algorithms on the DTLZ test function

4 結論

未來將面臨更多有關高維多目標問題的挑戰，研究者們應當提出更高效的算法來解決這些問題。本文通過支配與指標相結合的原則，利用支配策略偏向強調收斂性，指標策略偏向強調多樣性的特征，共同促進解個體向真實Pareto前沿收斂。實驗結果表明，MOEA-PBI在面對高維多目標問題時，總體具有較好的性能。在解決日后的MaOPs時，MOEA-PBI也不失為一種較優的選擇。