偏好MOEA/D算法的研究與實現(xiàn)

萬旭光+毛樟根

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

關(guān)鍵詞： 多目標優(yōu)化； MOEA/D算法； Pareto解； 信息優(yōu)化； 輔助決策； 權(quán)向量

中圖分類號： 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 引 言

在科學技術(shù)、經(jīng)濟管理和工程設(shè)計等領(lǐng)域的實踐中，常會遇到要求多個目標在指定方向上或限定區(qū)域內(nèi)進行最優(yōu)化處理的問題，也就是多目標優(yōu)化問題（Multi?objective Optimization Problems，MOPs）[1]。

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

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

1 偏好MOEA/D算法的描述

1.1 算法的提出

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

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

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

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

1.2 算法的數(shù)學描述

MOEA/D的數(shù)學描述為：

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

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

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

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

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

1.3 算法框架

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

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

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

式中：[λ1，λ2，…，λN]是一套均勻分布的權(quá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占優(yōu)解[x*]存在一個權(quán)值向量[λ]使得[x*]是式（2）的最優(yōu)解；而且每一個式（2）的最優(yōu)解都是式（1）的Pareto占優(yōu)解，所以能夠通過解一系列由Tchebycheff分解方法定義的不同權(quán)向量的單目標優(yōu)化問題來獲得不同的Pareto占優(yōu)解。

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

輸入：

1.多目標優(yōu)化問題（MOP）

2.終止條件

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

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

5.T：權(quán)重向量的個數(shù)

輸出：EP（外部種群）

Step1初始化：

1.1 令Pareto解集 EP=[?；]

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

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

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

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

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

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

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

2.4 更新相鄰集合中的解：對每一個指數(shù)[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 偏好權(quán)向量的調(diào)整：根據(jù)偏好信息對解進行調(diào)整，在偏好區(qū)域內(nèi)在解集最稀疏的地方增加一個權(quán)向量，在偏好區(qū)域外權(quán)向量最密集的地方刪除一個權(quán)向量。

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

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

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

2 算法仿真及實驗結(jié)果分析

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

2.1 測試函數(shù)的選取

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

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

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

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

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

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

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

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

[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函數(shù)，變量數(shù)：[k+x-1，]取值范圍：[0，1]，目標函數(shù)：

[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 實驗設(shè)置

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

2.3 實驗結(jié)果分析

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

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

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

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

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

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

3 結(jié) 論

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

參考文獻

[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] 肖曉偉，肖迪，林錦國，等.多目標優(yōu)化問題的研究概述[J].計算機應(yīng)用研究，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的優(yōu)化技術(shù)及其在天線優(yōu)化設(shè)計中的應(yīng)用[D].合肥：中國科學技術(shù)大學，2015.

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

[9] 張冬梅，龔小勝，戴光明，等.求解復雜多目標優(yōu)化問題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覆蓋優(yōu)化方法[J].計算機應(yīng)用研究，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熵的多目標粒子群優(yōu)化算法[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