基于目標相對重要性的模糊多目標進化算法

易高明 蔣 艷(上海理工大學管理學院 上海 200082)

0 引 言

在優化中，由于決策變量的隱含條件限制，各個子目標是相互制約的，這和單目標優化問題有著本質的區別，即一般情況下，多目標優化最優解不是唯一的[1]。近十年來，進化算法和群體智能算法等啟發式算法已經被成功證明在求解融入偏好的多目標優化問題中具有較高的效率和極大的優越性[2-4]。然而，涌現的多目標進化算法都被設計成旨在尋找一組有著良好分布性和延展性的Pareto最優解集，但在實際工程中，不管是個體還是群體決策者并不需要這么一組眾多Pareto最優解，相反決策人只對Pareto前沿面上的若干少數解甚至某一個解有興趣[5-6]，此時傳統框架下用于求解融入決策者偏好的多目標進化方法將不再實用。因為考慮到在眾多的Pareto解中二次尋找符合自身偏好的若干少數解不僅會增加求解的復雜度，更會增加決策人的評價負擔[7-8]。決策者對進化多目標優化求解的期望已經不僅僅是得到盡可能多的分布性良好的Pareto最優解[9]，而且決策人希望在優化過程中，通過與多目標進化算法時時交互以不斷嵌入自身偏好，引導進化個體向特定偏好區域快速逼近來尋求決策人感興趣的少數實踐解[10]。

依據決策人在求解多目標問題時偏好嵌入方式的不同，進化多目標方法分成如下三類[12]：偏好先驗嵌入法、偏好后驗嵌入法、交互式偏好嵌入法。其中偏好先驗嵌入法是決策者在求解之前給出一個偏好向量，然后將多目標優化問題轉化為單目標問題求解。關于偏好后驗嵌入法，各項研究都是基于開發或者改進一類智能進化算法以更高效率的得到分布均勻、拓展良好的一組Pareto最優解。對于第三種交互方法，文獻[13]提出一種雙極偏好占優機制的進化個體排序規則，通過設置一個理想解和負理想解，定義遠離負理想解且更靠近理想解的進化個體更優的全新錦標賽選擇算子。文獻[14]提出一種全新的Pareto占優范式r-占優，能夠在種群進化當中給出個體的全序關系，以引導種群不斷向用戶偏好內逼近，其中采用期望水平向量定量刻畫決策者的偏好水平和強度并輔以NSGA-II方法尋求決策人滿意解。文獻[15]提出g-占優的基于參考點的多目標優化算法，主要根據決策者確定的某個參考點，規定位于偏好域的解優于非偏好區域的解，從而使進化個體不斷逼近參考點附近的偏好區域。

本文提出的基于目標間相對重要性的交互式進化算法RPT-NSGA-II的創新點：定量刻畫決策人的模糊偏好，采用更加符合決策人情感認知的倆倆目標間語義重要性的九級范式表達模糊偏好，并遵循決策人認知規律的模糊性和漸進性，分階段地刻畫更加細致清晰的目標相對重要的表達范式。通過映射到目標空間形成決策者新的偏好區域，最后構建目標相對重要的數學模型，在NSGA-II框架下給出同一非劣層下的個體優劣排序，最終使整個進化種群朝著Pareto最優前沿面上的偏好域內逼近。

1 多目標優化問題

1.1 多目標的數學模型

設最小化多目標優化問題MOP(Multi-objective Optimization Problem)由n個決策變量，k個目標函數和m個約束條件組成，其中x表示決策向量，y表示目標向量，X表示決策向量x形成的決策空間，Y表示目標向量y形成的目標空間[1]。形式如下：

miny=F(x)=(f1(x),f2(x),…,fk(x))T

s.te(x)=(e1(x),e2(x),…,em(x))≥0

x=(x1,x2,…,xn)∈X

y=(y1,y2,…,yk)∈Y

(1)

定義1(Pareto支配) 決策向量xu=(u1,u2,…,un)Pareto支配決策向量xv=(v1,v2,…,vn)：xu?xv當且僅當?i=1,2,…,k，fi(xv)≥fi(xu) 且?j=1,2,…,k，有fj(xv)>fj(xu)。

定義2(Pareto最優解集) 若P*∈{x∈X|?x*∈X,x*?x}，則集合P*是Pareto最優解集。

定義3(Pareto前沿) Pareto解映射到目標空間的集合即為Pareto前沿，記為PF*={F(x)|x∈P*}。

1.2 偏好多目標求解方法

從實踐的立場來看，多目標的最優解集的基數雖然不唯一，但是決策者僅需要少數甚至一個實踐解。經典的進化多目標即偏好后驗嵌入法的求解思路是借助于進化算法的并行計算優勢，經過一定代數的種群進化，旨在得到一組逼近前沿端的分布性和延展性良好的Pareto解集。然后用戶基于個人經驗、偏好等其他高層次信息進一步評價這些解的優劣，從中挑選一個滿意解。圖1給出倆目標最小化優化問題的基本步驟[16]。

步驟1通過進化優化算法找到一組分布性延展性較好的若干非劣解。

步驟2從上面非劣解中挑選一個滿意解。

圖1 經典后驗偏好法求解多目標問題思路

相比較偏好后驗嵌入法，偏好先驗嵌入法在一開始便由決策者給出一個偏好向量w，偏好向量用于構建一個復合單目標函數，從而將一個多目標優化問題轉化成一個單目標優化問題求解。然而在實踐中，特別是對于模糊偏好多目標優化問題的求解，決策者事先給出一組偏好向量是困難的。同時合成的目標函數對偏好向量的微調非常敏感，因此偏好先驗嵌入法對決策者而言是較為主觀的，圖2是先驗法思路[16]。

圖2 先驗偏好法求解多目標問題思路

1.3 TOPSIS法的改進

圖3 TOPSIS法

其中目標方案Fi的TOPSIS綜合評價指數Ci即排隊值由大到小依次排列目標方案的優劣次序。

(2)

文獻[13]選取的正負理想解是由決策者根據自身偏好而給出,并沒有考慮給出兩個正負偏好點的可行性，在改進的TOPSIS法里，本文采用基于移動理想點法的正負偏好點更新策略，每一次進化個體的迭代和位置的更新，使TOPSIS法中的理想點和厭惡點也都到自動修正。

2 偏好區域的構建

2.1 目標相對重要性的語義范式

在融入模糊偏好的多目標進化優化過程中，問題的首要任務在于定量動態刻畫決策者的偏好。考慮到決策人對目標問題偏好認知的模糊性與漸進性，交互式的重構決策者的偏好表達是求解多目標進化優化問題的關鍵所在。本文根據Thomas L.Saaty創建的屬性間相對重要性等級表[18]，考慮決策人對一般事物認知的規律特點，對倆倆目標進行重要性比較，并且采用符合人的一般認知習慣與判斷能力的更加細分的語義描述范式來表達目標之間的相對重要性，在這種范式表達下，決策者可以容易且自然地表達對目標間偏好強度。語義范式如表1所示。

表1 目標間語義感知范式

定義4對于多目標問題中的任意兩個目標fi、fj，兩者之間相對重要性有：

fi?wfj(w=1,2,…,9)

當且僅當決策人在偏好程度w下感知目標fi和fj的重要比范式。有代表性的重要范式有：

1) 決策人給出的偏好是fi比fj同等重要，則有fi～fj。

2) 決策者給出的偏好是fi比fj略微重要，則有fi?3fj。

3) 決策者給出的偏好是fi比fj相當重要，則有fi?5fj。

4) 決策者給出的偏好是fi比fj明顯重要，則有fi?7fj。

5) 決策者給出的偏好是fi比fj絕對重要，則有fi?9fj。

基于上述定義以及決策者對目標間重要性認知的漸進性，本文提出將帶偏好的進化優化過程劃分成三個子階段來表達決策者偏好。第一階段稱為廣義目標相對重要性優化(w=1，5，9)；第二階段稱為一般目標相對重要性優化(w=1，3，5，7，9)；第三階段稱為精準目標相對重要性優化(w=1，2，3，4，5，6，7，8，9)。特別的，第一階段與第二階段以a1T為分割點，第二階段與第三階段以a2T為分割點。其中T為決策者給點的終止進化代數，且有a1+a2=1，a1,a2∈(0,1)由決策者給定具體數值。在進化過程中決策者可以實時交互式的修正對目標函數的偏好,從而在目標決策空間形成新的偏好域以引導進化個體向偏好域上不斷逼近。

2.2 偏好域的等角度劃分

將感性的語言范式描述轉化為定量的數學模型表達，是衡量多目標進化優化中嵌入決策者偏好意志成功與否的關鍵所在[19]，因此將上文中的目標相對重要性語言描述以恰當的方式轉化為數學模型投射到目標空間的區域是非常必要的。本文對整個目標空間進行等角度偏好域劃分，其他具體角度劃分由決策者權衡給出。在此基礎上建立偏好區域的數學模型。這里示例給出倆目標空間下廣義目標相對重要性表達偏好的角度劃分，見圖4。

圖4 廣義目標相對重要性對min(fi,fj)等角度劃分

考慮圖4的廣義目標相對重要性劃分圖,當目標空間被等角度劃分五個區域后，根據上述區域劃分的數學不等式模型并結合給定的決策者的偏好區域，可以進一步判斷進化個體所在區域和決策者偏好區域的位置關系，從而給出同一非支配層中進化個體的優劣比較即處于偏好域內的個體占優偏好域外個體。各個區域的數學不等式分別有：

fi?9fj?0.32fi>fj
fi?5fj?0.32fi≤fj<0.73fi
fi～fj?0.73fi≤fj<1.38fj
fj?5fi?1.38fi≤fj≤3.03fi
fj?9fi?fj>3.03fi

(3)

3 進化個體適應值評價

本文給出一種全新的基于目標相對重要性的偏好區域劃分排序法。該排序策略分為三個層次：基于分級的快速非劣解排序，同一非劣級別下偏好域占優排序，同一非劣級別下基于雙極偏好占優的偏好域外進化個體排序。

定義5(RPT-Dominance) 決策目標空間中任意的兩個決策向量X、Y，有XRPT-DominanceY，當且僅當滿足如下條件之一(其中Q是決策者修正的偏好區域，Xd、Yd是決策向量X、Y的擁擠度，CX、CY是決策向量X、Y綜合評價指數)。

1)XPareto支配Y。

2)X、Y互不支配且X,Y∈Q,Xd>Yd。

3)X、Y互不支配且X∈Q、Y?Q。

4)X、Y互不支配且X,Y?Q、CX>CY。

第一個條件解決了兩個解位于不同非劣層的情況，即屬于更靠前的非支配解集合中的解X優于屬于靠后的非支配解集合中的解Y。后面三個條件解決了屬于同一層非支配解集合下的解個體優劣問題，即若X、Y均位于決策者偏好域內，則根據它們的擁擠距離進行判別，擁擠距離較大的個體(位于較稀疏區域的個體)優于擁擠距離小的解個體；偏好域內的進化個體優于偏好域內的個體；兩個解均位于偏好域外，則根據TOPSIS綜合評價指數比較優劣，綜合評價指數大的個體優于評價指數較小的個體。

4 基于目標相對重要性與雙極偏好融合的RPT-NSGA-II算法

算法思想：融入決策者模糊偏好信息的多目標優化問題，采用目標相對重要的全新語義范式，依據人認知的漸進性，分階段地讓決策者與算法不斷交互，允許決策者改變自己的偏好。將優化過程劃分為廣義目標相對重要性優化，一般目標相對重要性優化和精準目標相對重要性優化表述三個階段。決策適時給出目標間偏好并在目標空間形成相應的偏好域數學模型，在NSGA-II優化框架下進行種群優化，并根據RPT-Dominance排序算子比較兩兩個體間優劣，從而引導進化個體不斷朝著決策者感興趣的區域搜索，步驟如下：

Step1隨機初始化產生一個規模為N的群體P(t),進化代數t=0。

Step2對進化種群個體進行快速非支配排序，并在不同進化階段采用2.1節中語義范式來刻畫決策者偏好的表達。

Step3依據目標相對重要性建立數學模型，并且判斷進化個體與偏好域的位置關系，計算偏好域內個體的擁擠距離和偏好域外個體錦標賽選擇策略選擇適應值較優的個體組成交配池，并且依概率對其進行交叉變異等遺傳操作生成子代群體Q(t)。

Step4R(t)=P(t)∪Q(t)并依據RPT-Dominance錦標賽選擇算子選出R(t)中前N個優勢進化個體，令其為P(t+1)。

Step5給定算法終止條件，當滿足終止條件則輸出偏好域內滿意解；否則，令t=t+1,轉Step 2。

對于引入偏好的多目標遺傳算法，本文給出了一種全新的進化個體適應值排序策略，算法流程如圖5所示。

圖5 RPT-NSGA-II流程

5 實 驗

為了驗證本文提出的基于RPT-dominance的偏好多目標遺傳算法的有效性，將該方法與偏好先驗嵌入法和偏好后驗嵌入法作比較，三種方法均在NSGA-II框架下進行操作，對于每一個測試函數，三種方法均獨立運行30次，五個基準數值測試函數分別為ZDT1、ZDT2、ZDT3、SCH、DTLZ2。

5.1 算法參數設置

三種方法的種群規模均設置為30并采用單點交叉和均勻變異，概率分別為0.9和0.1，兩目標函數進化代數N為800，三目標函數的進化代數N為1 000。為表達決策者偏好的分割點設置為a1=0.3、a2=0.7，即在0～0.3N代時采用廣義目標相對重要性表達決策者的偏好，在0.3N～0.7N代時采用一般目標相對重要性表達決策者偏好，0.7N后采用精準目標相對重要性表達決策者偏好。決策者初始偏好經過三次修正到達最終偏好，初始偏好即為先驗法的決策者偏好，在迭代0.3N代時進行第一次偏好修正，迭代至0.5N代時進行第二次偏好修正，最后一次偏好修正的時間點是0.7N,即為最終偏好，最終偏好也是后驗法的決策者偏好，具體設置如表2所示示。

表2 偏好設置

5.2 性能評價指標

1)AD測度：求得的最優解集中X的所有進化個體x到決策者最終偏好域的平均距離，記為:

(4)

式中：AD測度表達的是決策者采用某種進化方式求得的Pareto最優解的滿意程度，AD測度值越小則表示決策者對解集X越滿意。當最終個體位于偏好域內時，該個體的D(x)為0。

2)T測度：算法求解耗時。T側度越小則表示對應算法求解的時間效率越高。

3)I測度：進化個體位于最終偏好域內的非劣解個數，I測度值越大，則表示該算法獲得決策者最終滿意解的能力越強。

5.3 實驗結果分析

表3給出了三種不同算法得到的AD測度的均值和方差，由表3可知，與偏好先驗嵌入法和偏好后驗嵌入法相比較，本文提出的RPT-NSGA-II算法得到的5個測試函數的AD測度最小，即得到的所有最終解到決策者偏好域的平均距離最短，說明本文提出的方法得到的最優解最能反映出決策者的偏好，且本文算法得到的最優解在反映決策者偏好方面顯著優于偏好先驗法和偏好后驗法。對于2目標測試函數ZDT1、ZDT2、ZDT3、SCH，采用先驗法得到的AD測度大于后驗法得到的AD測度，這表明在2目標測試函數上，后驗法得到的最優解在反映決策者偏好的上要優于先驗法，但不難發現，只有ZDT3的AD測度表現較為明顯的差異，ZDT1、ZDT2、SCH在先驗法和后驗法得出的AD測度均無顯著差異。此外在3目標測試函數DTLZ2問題上，采用先驗法得出的AD測度小于后驗法得出的AD測度，因此認為先驗法和后驗法在處理帶有模糊偏好的多目標優化問題上具有結果不確定性，在不同類型的優化問題表現出差異性，然而本文提出的交互式RPT-NSGA-II在處理此類模糊偏好優化問題上表現出較為顯著的優越性和穩定性。

表3 三種方法對五個測試函數的AD測度

如表4所示，與其他兩種方法對比，本文提出的RPT-NSGA-II算法的時間T測度略微大于先驗法得出的時間測度值，兩者的T測度的差值在3 s以內。但是與后驗法相比，本文的RPT-NSGA-II法的算法耗時顯著小于后驗法求解的耗時，后驗法對所有測試函數的求解耗時均是RPT-NSGA-II交互式算法求解耗時的1～2倍。由此可知后驗法求解此類問題是非常耗時的。對于本文算法耗時與先驗法求解耗時的差異，一方面是RPT-NSGA-II算法考慮了與決策者的交互需求，另一方面在先驗法中采用的是所有非劣進化個體的擁擠距離排序，而在本文提出的交互算法中，我們定義了偏好域內的個體采用擁擠距離的排序策略，而在偏好域外，則采用雙極偏好占優的排序策略。仿真結果表明，相對于算法的總耗時，先驗法和交互法的求解耗時差異是不顯著的。另外之所以交互法與后驗法的T測度的差異是顯著的，這是因為在后驗法求得的一組近似Pareto解后，決策者必須再次花費時間進行二次滿意解搜索，但是本文提出的算法則是交互式向決策的偏好域逼近，從而大大減少了滿意解搜索耗時。

從表5反映本文的RPT-NSGA-II算法在滿意解搜索上表現出更強的能力，最終解位于最終偏好域內的解個數，包括平均個數(四舍五入)和最大個數，均顯著多于先驗法和后驗法生成的偏好域內解個數。圖6至圖10是三種方法對五個測試函數滿意解數量分布仿真圖，矩形區域內的解是每種方法作用在一個測試函數上的最終偏好域內最大解分布，容易得出本文算法對五種測試函數下的滿意解搜索數量的分布都是最好的。

(a) RPT-NSGA-II交互法 (b) 先驗法 (c) 后驗法圖6 三種方法對ZDT1函數的滿意解分布

(a) RPT-NSGA-II交互法 (b) 先驗法 (c) 后驗法圖7 三種方法對ZDT2函數的滿意解分布

(a) RPT-NSGA-II交互法 (b) 先驗法 (c) 后驗法圖8 三種方法對ZDT3函數的滿意解分布

(a) RPT-NSGA-II交互法 (b) 先驗法 (c) 后驗法圖9 三種方法對SCH函數的滿意解分布

(a) RPT-NSGA-II交互法 (b) 先驗法 (c) 后驗法圖10 三種方法對DTLZ2函數的滿意解分布

6 結 語

針對帶模糊偏好的多目標進化優化問題，本文提出一種基于目標相對重要性的交互式多目標進化算法(RPT-NSGA-II)，引入偏好表達的九級自然語義范式，分廣義階段、一般階段和精準階段三個子階段來刻畫更加細致清晰的目標相對重要性式。決策者修正的偏好與算法不斷交互有效提高了實踐需求與算法有效資源分配的匹配度。仿真實驗表明，RPT-NSGA-II在五個不同的測試函數上取得較高的求解效率。

本文的交互式進化優化算法將對包括工業和藝術產品的個性化創作設計、語言聲音圖像處理和快速檢索以及目擊人在海量人像庫中對嫌疑人畫像的再指認等尋優領域提供理論支持。

[1] 公茂果, 焦李成, 楊咚咚,等. 進化多目標優化算法研究[J]. 軟件學報, 2009, 20(2):271- 289．

[2] Deb K, Pratap A, Agarwal S, et al. A fast and elitist multiobjective genetic algorithm: NSGA-II[J]. IEEE Transactions Evolutionary Computation, 2002, 6(2):182- 197．

[3] Cheng R，Jin Y，Olhofer M．A Reference Vector Guided Evolutionary Algorithm for Many-Objective Optimization[J]．IEEE Transactions on Evolutionary Computation，2016，20(5)：773- 791．

[4] Singh H K, Isaacs A, Ray T. A Pareto Corner Search Evolutionary Algorithm and Dimensionality Reduction in Many-Objective Optimization Problems[J]. IEEE Transactions on Evolutionary Computation, 2011, 15(4):539- 556．

[5] Filatovas E, Kurasova O, Sindhya K. Synchronous R-NSGA-II: An Extended Preference-Based Evolutionary Algorithm for Multi-Objective Optimization[J]. Informatica, 2015, 26(1):33- 50．

[6] Wagner T, Trautmann H. Integration of Preferences in Hypervolume-Based Multiobjective Evolutionary Algorithms by Means of Desirability Functions[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(5):688- 701．

[7] 鄭金華, 謝諄志. 關于如何用角度信息引入決策者偏好的研究[J]. 電子學報, 2014, 42(11):2239- 2246．

[8] 張艷梅, 曹懷虎, 賈恒越,等. 考慮用戶偏好的多目標服務組合優化算法研究[J]. 小型微型計算機系統, 2016, 37(1):38- 42．

[9] 肖曉偉, 肖迪, 林錦國,等. 多目標優化問題的研究概述[J]. 計算機應用研究, 2011, 28(3):805- 808．

[10] 王麗萍，章鳴雷，邱飛岳，等．基于角度懲罰距離精英選擇策略的偏好高維目標優化算法[J]．計算機學報，2018，41(1)：236- 253．

[11] Deb K, Kumar A. Interactive evolutionary multi-objective optimization and decision-making using reference direction method[C]// Conference on Genetic and Evolutionary Computation. ACM, 2007:781- 788．

[12] 鞏敦衛, 王更星, 孫曉燕. 高維多目標優化問題融入決策者偏好的集合進化優化方法[J]. 電子學報, 2014, 42(5):933- 939．

[13] 邱飛岳, 吳裕市, 邱啟倉,等. 基于雙極偏好占優的高維目標進化算法[J]. 軟件學報, 2013,24(3):476- 489．

[14] Said L B, Bechikh S, Ghedira K. The r-Dominance: A New Dominance Relation for Interactive Evolutionary Multicriteria Decision Making[J]. IEEE Transactions on Evolutionary Computation, 2010, 14(5):801- 818．

[15] Molina J, Santana L V,Hernández-Díaz A G, et al. G-dominance: Reference point based dominance for multiobjective metaheuristics[J]. European Journal of Operational Research, 2009, 197(2):685- 692．

[16] Burke E K，Kendall G．搜索方法論-優化與決策支持技術入門教程[M]．北京：清華大學出版社，2014．

[17] 王應明，闕翠平，藍以信．基于前景理論的猶豫模糊TOPSIS多屬性決策方法[J]．控制與決策，2017，32(5)：864- 870．

[18] 岳超源．決策理論與方法[M]．北京:科學出版社，2003．

[19] Rachmawati L，Srinivasan D．Incorporating the notion of relative importance of objectives in evolutionary multi-objective optimiation[J]．IEEE Transactions on Evolutionary Computation，2010，14(4)：530- 546.