偏好MOEA/D算法的研究與實現

萬旭光+毛樟根

摘 要： 在科研和工程實踐中存在著很多需要同時優化的兩個或多個相互沖突的多目標優化問題。多數情況下，人們使用多目標優化是為了尋求某一特定方向的Pareto解，但傳統的優化方法只能得出分散的全部解集，不利于輔助決策。為此，提出一種帶偏好的多目標優化算法（即偏好MOEA/D算法），該算法的核心思想是將一個多目標優化問題分解成多個單目標優化問題并同時優化，在子問題通過相鄰子問題信息優化的過程中加入使用者偏好，最終得到方向明確的Pareto解集。經仿真驗證，該算法具有突出的求解性能，便于輔助決策，且有較高的有效性和可拓展性。

關鍵詞： 多目標優化； MOEA/D算法； Pareto解； 信息優化； 輔助決策； 權向量

中圖分類號： TN911.1?34 文獻標識碼： A 文章編號： 1004?373X（2018）01?0133?06

Abstract： The multi?objective problem that two or more objectives conflicted with each other should be optimized exists in scientific research and engineering practice. The multi?objective optimization is usually used to get the Pareto solution in a certain direction， but the traditional optimization method can only get the dispersive whole solution set and isn′t conducive to the assistant decision. A preference?based multi?objective optimization algorithm （preference MOEA/D algorithm） is proposed. The core thought of this algorithm is to decompose a multi?objective optimization problem into several single?objective optimization problems， and optimize the single?objective optimization problems. The user preference is added into the sub problem in the information optimization process of the adjacent sub problem to get the Pareto solution set with explicit direction. The simulation results show that the proposed algorithm has outstanding solving performance， high efficiency and strong expansibility， and is convenient for assistant decision?making.

Keywords： multi?objective optimization； MOEA/D algorithm； Pareto solution； information optimization； assistant decision?making； weight vector

0 引 言

在科學技術、經濟管理和工程設計等領域的實踐中，常會遇到要求多個目標在指定方向上或限定區域內進行最優化處理的問題，也就是多目標優化問題（Multi?objective Optimization Problems，MOPs）[1]。

在單目標優化中最優解通常是惟一確定的，而多目標優化問題所研究的多個目標經常是相互矛盾，相互沖突的，因此沒有單一的全局最優解，而是一系列互不支配的解，稱為Pareto解或非支配解集，通常均勻分布在解空間內[2]。

而在實際問題的應用中，決策者往往只對目標空間的某一區域感興趣，因此，這就需要在這一特定區域能夠得到比較稠密的Pareto解。本文優化了MOEA/D算法，在該算法的基礎上加入偏好關系模型，改善了傳統算法解集均勻分布的缺點，成功使解集向使用者偏好方向聚集，所得解集對解決問題更有針對性，輔助決策的意義更強，效果更好。

1 偏好MOEA/D算法的描述

1.1 算法的提出

目前有很多求解多目標優化的算法，如強度Pareto遺傳算法（SPEA，SPEA?Ⅱ）、Pareto存檔進化算法（PAES）[3]、非劣排序遺傳算法（NSGA，NSGA?Ⅱ）[4]等，這些算法的核心目的是在盡量少的計算量的情況下，尋求較均勻的Pareto近似解。

本文要改進的是最近提出的MOEA/D算法，運用在第一象限均勻地分配權向量的方法將多目標優化問題分解成一系列單目標優化問題，每個子問題又有其鄰域子問題，為了構造一個新解，每個子問題需要組合其鄰域子問題的當前解的信息，同時每個新產生的解不僅要更新自身的解還要更新其鄰域子問題的解[5]。選擇該方法作為優化對象的原因是：該算法原理簡單，易于與具體問題結合并且容易與本文提出的偏好模型相結合，是一種簡單有效的進化算法。

目前對MOEA/D算法的改進和優化多集中于算法本身的功能上，很少有將偏好考慮其中的。算法本身在進行優化時，是對全目標空間進行尋優的，這樣最終得到的Pareto解也是均勻分布的。若在算法尋優的過程中加入使用者的個人偏好，使尋優方向向偏好方向靠攏并最終保持一致，便可在使用者所需要的區域內產生特定需求的Pareto解。endprint

采用先驗方法來處理偏好問題，在算法開始之前，由用戶提供一個目標空間的偏好區域，該偏好區域首先用權向量[λi]代表用戶偏好的方向，然后用偏好比率范圍來表示偏好區域的大小。在算法的運行過程中，通過權向量不斷調整達到Pareto解集不斷收斂到偏好區域的目的。

1.2 算法的數學描述

MOEA/D的數學描述為：

[（MOP）minF（x）=f1（x），f2（x），…，fq（x）s.t. x∈Ω Ω?Rn] （1）

式中：[Ω]是變量空間；[F（x）]為向量值函數，[F（x）∈Rq；]min表示向量極小化，即向量目標[F（x）=][f1（x）， f2（x），…， fq（x）]中的各個子目標函數都盡可能極小化。

大多數情況下，多目標優化問題（MOP）的最優Pareto解位于目標空間邊界。圖1給出了一個二目標最小化目標函數，[xa]和[xb]點分別為問題的兩個Pareto最優解，當從[xa]點移動到[xb]點時，在函數[f2]上的性能變優，在[f1]上的性能卻變差。[xb]點Pareto支配[xc]點。

文獻[6]提出復雜的局部偏好關系模型，該模型中，需要決策者給出起始點、終止點、無差別閾值向量、否決閾值向量，規避了僅為每個單目標分配0或1的某個權重，即全部否定或全部肯定的決策輔助情況。

本算法的提出受到了局部偏好關系模型的啟發，但是本算法只需要用戶給出偏好方向上的權向量和偏好比率范圍（如圖2所示），簡化了偏好關系模型的復雜度。偏好方向權向量選定以0點為向量起始點，終止點選取起始點后的任何點，這里采用最大值作為終止點，限定偏好權向量只有一個，偏好比率范圍用以限定偏好區間，假設Pareto前沿為1，那么偏好區間以偏好方向為基點占Pareto前沿長度的比率作為偏好范圍比率（即偏好比率范圍為0～1以內的任意值），偏好比率越大則代表偏好范圍越大。

1.3 算法框架

目前有許多方法可以將一個多目標優化問題分解為一系列單目標優化問題，本文所采用的分解方法是Tchebycheff分解法[7]。

Tchebycheff分解方法：將多目標問題分解后，其中一個單目標優化問題可以表示成如下形式：

[Minimize gtexλ，z*=Max1≤i≤mλifi（x）-z*is.t. x∈Ω] （2）

式中：[λ1，λ2，…，λN]是一套均勻分布的權重向量，其中[λi≥0，i=1，2，…，m，]并且[i=1mλi=1]。這里[z*=（z*1，z*2，…，z*m）T]是一個參考點，也就是說，對每一個[i=1，2，…，m，]存在[z*=minfi（x）x∈Ω3]對式（1）中每一個Pareto占優解[x*]存在一個權值向量[λ]使得[x*]是式（2）的最優解；而且每一個式（2）的最優解都是式（1）的Pareto占優解，所以能夠通過解一系列由Tchebycheff分解方法定義的不同權向量的單目標優化問題來獲得不同的Pareto占優解。

以下是基于偏好的MOEA/D算法的主要流程：

輸入：

1.多目標優化問題（MOP）

2.終止條件

3.N：MOEA/D分解過程中所考慮子問題的數目

4.均勻分布的N個權重向量：[λ1，λ2，…，λN]

5.T：權重向量的個數

輸出：EP（外部種群）

Step1初始化：

1.1 令Pareto解集 EP=[?；]

1.2 計算任何兩個向量間的歐氏距離，然后對每個權重用與其距離最近的T個權重組成其相鄰集合；即對每一個i=1，2，…N，有[B（i）={i1，i2，…，iT}]，其中[λi1，λi2，…，λiT]就是[λi]的T個最近的權重向量；

1.3 隨機或根據集體問題產生一個初始化種群[x1，x2，…，xN，]并計算[FVi=F（xi）]；

1.4 根據具體問題設置初始化，令[z=（z1，z2，…，zm）T]。

Step2 更新：對每個i=1，2，…，N，做如下操作：

2.1 繁殖：從[B（i）]中隨機選擇兩個序號[k，l，]然后對[xk]和[xl]進行遺傳操作，產生一個新的解[y；]

2.2 更新改進：根據具體問題對接進行調整/修補，由[y]變成[y；]

2.3 更新[z：]對每一個j=1，2，…，m，如果[zj

2.4 更新相鄰集合中的解：對每一個指數[j∈B（i）]的標號，如果有[gteyλj，z≤gtexjλj，z，]則令[xj=y]并且[FVj=F（y）]；

2.5 EP的更新：從EP中刪除被[F（y）]支配的所有向量，如果在EP中沒有向量支配[F（y）]那么則將[F（y）]加入EP中；

2.6 偏好權向量的調整：根據偏好信息對解進行調整，在偏好區域內在解集最稀疏的地方增加一個權向量，在偏好區域外權向量最密集的地方刪除一個權向量。

Step3終止條件：如果滿足終止條件那么就停止并輸出EP，若不滿足則轉向第2步。

從上述算法框架中，可以將其分為五大主要模塊：輸入、初始化、更新、判斷、輸出，本文的算法將偏好模型加在更新部分，通過不斷調整權向量使解集不斷收斂于偏好區域。

MOEA/D對多目標中每個分解的子問題建立對應的評價機制，能大大減少計算復雜度，加快群體的收斂速度。同時在MOEA/D算法中融入偏好模型可以將用戶的偏好信息加入算法的運行過程，經過每一代權向量的調整和篩選，使得最終結果趨近在用戶的偏好區域附近。

2 算法仿真及實驗結果分析

本文的算法代碼是在VC++ 6.0的平臺上運行，運行結束后將得出數據保存，再運用Matlab作為界面展示，結果形象并易于觀察變化。

2.1 測試函數的選取

本文的主要工作是為了體現優化后的偏好MOEA/D算法的解集聚攏效果，只與傳統MOEA/D算法的解集作比較，不與其他多目標優化算法作對比分析。所以測試對象選取了3個兩目標函數和2個可展為高維目標的函數[8]。這些測試函數被廣泛引用，能較全面地體現某多目標算法的性能。SCH是比較簡單的兩目標優化問題，其最優Pareto前沿是非連續的，常用于測試算法在非連續區域的穩定性；ZDT1和ZDT2問題是Zitzler等學者提出的較為復雜的兩目標優化問題。它們的Pareto前沿分別是凸的和非凸的，決策變量維數均為30；DTLZ2和DTLZ3問題由Deb等學者提出，可以擴展為不同目標的多目標優化問題，為了衡量算法的擴展性能，測試了高達8目標DTLZ2和DTLZ3問題。關于這些測試函數的Pareto最優前沿可以參看Coello等學者建立的相關方面網站及文獻[9]。這些測試函數的數學定義如下：

1） SCH函數，變量數：1，取值范圍：[-5，10]，目標函數：

[f1（x）=-x，x≤1-2+x，14f2（x）=（x-5）2]

2） ZDT1函數，變量數：30，取值范圍：[0，1]，目標函數：

[f1（x）=x1，f2（x）=g（x）1-x1g（x）g（x）=1+9i=2nxin-1]

3） ZDT2函數，變量數：30，取值范圍：[0，1]，目標函數：

[f1（x）=x1f2（x）=g（x）1-x1g（x）2g（x）=1+9i=2nxin-1]

4） DTLZ2函數，變量數：30，取值范圍：[0，1]，目標函數：

[f1=1+gxkcosx1π2cosx2π2…cosxk-2π2sinxk-1π2]

[?]

[fk-1（x）=1+gxkcosx1π2sinx2π2fk（x）=1+gxksinx1π2g（xk）=xi∈xkxi-0.52]

5） DTLZ3函數，變量數：[k+x-1，]取值范圍：[0，1]，目標函數：

[f1=1+gxkcosx1π2cosx2π2…cosxk-2π2cosxk-1π2f2=1+gxkcosx1π2cosx2π2…cosxk-2π2sinxk-1π2 ?]

[fM-1（x）=1+gxkcosx1π2sinx2π2fM（x）=1+gxksinx1π2g（xk）=100*xk+xi∈xkxi-0.52-cos20πxi-0.5]

2.2 實驗設置

本文在實驗中首先測試了兩目標函數問題SCH和ZDT函數系列，然后對目標維數較高的DTLZ2和DTLZ3問題[10]進行相關測試，均設計了不同的偏好方向以及偏好范圍參數，具體參數設置見表1。

2.3 實驗結果分析

上述函數的測試結果圖如圖3～圖5所示。每個函數給出四個測試圖，歸類為一組。每組的第一張圖為測試在傳統MOEA/D算法無偏好情況下被測函數所獲得的全部Pareto解集；第二張圖給出加上偏好后的解集對比試驗結果；第三張圖針對偏好，選擇當偏好方向相同而偏好區域不同時解集的對比結果；第四張圖為偏好區域相同但偏好方向不同時的解集對比結果。

每張圖中藍色的點是偏好MOEA/D方法得到的在偏好區域內的解集，黑色的線代表標準Pareto前沿。

從圖中可以清楚地看出，隨設定偏好范圍的增大則偏好解集范圍增大，改變偏好方向則偏好解集也隨之改變方向，從上述的兩目標函數中可以發現，無論函數的形狀如何或是否連續，偏好模型在MOEA/D算法中能夠有效地使解集收斂并約束在偏好區域以內均勻分布。同時，加入偏好之后函數的解集明顯收斂到了偏好區域范圍內，并且在Pareto前沿上分布較均勻。隨著在測試中改變偏好方向，解集明顯以新的偏好方向為中心分布，在測試中改變偏好大小，偏好解集的范圍也隨之改變。證明了該算法能夠根據使用者的決策預期引導算法朝著預先設定的偏好方向進行優化，并能調整偏好范圍的大小。

為了測試函數的可擴展性，繼續測試了8目標的DTLZ2和DTLZ3問題[11]，測試結果如圖6，圖7所示。

針對上述2個三維函數，通過改變函數的偏好方向和偏好范圍，可以看出函數可以均勻分布于偏好范圍內并隨著偏好范圍大小做出相應改變，驗證了算法的可擴展性。

從以上5個測試函數中可以看出，偏好MOEA/D算法能有效地將用戶的偏好信息加入算法的進化過程中，根據用戶的偏好方向和偏好范圍求出相應方向和范圍的解集，獲得更優的輔助使用者決策的效果。

3 結 論

本文優化了傳統的MOEA/D算法，在原有的基礎上結合偏好關系模型，產生偏好MOEA/D算法，并介紹了其算法框架，利用具有代表性的兩目標函數SCH及ZDT1，ZDT2驗證了其有效性，進一步使用八維函數DTLZ2和DTLZ3進行測試以驗證其可擴展性。實驗結果表明，新算法能夠根據用戶的偏好區域范圍搜索相應的解集，并且具有較快的收斂速度和較好的均勻性保持能力，輔助決策的意義更強，效果更好。

參考文獻

[1] PARETO V. Cours d′economies olitique [M]. Lausanne： Rouge， 1896.

[2] ZHANG Q， LI H. MOEA/D： a multiobjective evolutionary algorithm based on decomposition [J]. IEEE transactions on evolutionary computation， 2007， 6（11）： 712?731.

[3] BRANKE J， DEB K， MIETTINEN K， et al. Multiobjective optimization： interactive and evolutionary approaches [M]. New York： Springer， 2008： 405?433.

[4] MOLINA J， SANTANA L V， HERNANDEZ?DIAZ A G， et al. g?dominance： reference point based dominance for multiobjective metaheuristics [J]. European journal of operational research， 2009， 197（2）： 685?692.

[5] KIM J， HAN J， KIM Y， et al. Preference?based solution selection algorithm for evolutionary multiobjective optimization [J]. IEEE transactions on evolutionary computation， 2012， 16（1）： 20?34.

[6] JASZKIEWICZ A， SLOWINSKI R. The light beam search approach?an overview of methodology and applications [J]. European journal of operation research， 1999， 113（2）： 300?314.

[7] 肖曉偉，肖迪，林錦國，等.多目標優化問題的研究概述[J].計算機應用研究，2011，28（3）：805?808.

XIAO Xiaowei， XIAO Di， LIN Jinguo， et al. Research overview of multi target application research [J]. Computer optimization problems， 2011， 28（3）： 805?827.

[8] 丁大維.基于MOEA/D的優化技術及其在天線優化設計中的應用[D].合肥：中國科學技術大學，2015.

DING Dawei. MOEA/D based optimization technology and antenna optimization design application [D]. Hefei： University of Science & Technology China， 2015.

[9] 張冬梅，龔小勝，戴光明，等.求解復雜多目標優化問題MOEA/D?GEP算法[J].華中科技大學學報（自然科學版），2012，40（4）：33?36.

ZHANG Dongmei， GONG Victory， DAI Guangming. Solving complex multi?objective optimization problem MOEA/D?GEP algorithm [J]. Journal of Huazhong University of Science and Technology （natural science edition）， 2014， 40（4）： 33?36.

[10] 神顯豪，李軍，張祁.基于改進MOEA/D算法的WSN覆蓋優化方法[J].計算機應用研究，2016，33（4）：1203?1206.

SHEN Xianhao， LI Jun， ZHANG Qi. WSN overlay optimization method based on improved MOEA/D algorithm [J]. Computer application research， 2016， 33（4）： 1203?1206.

[11] 胡旺，Gary G.YEN，張鑫.基于Pareto熵的多目標粒子群優化算法[J].軟件學報，2014，25（5）：1025?1050.

HU Wang， YEN G G， ZHANG Xin. Multi objective particle swarm optimization algorithm based on Pareto entropy [J]. Journal of software， 2014， 25（5）： 1025?1050.endprint