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

0 引 言

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

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

本文提出的基于目標(biāo)間相對(duì)重要性的交互式進(jìn)化算法RPT-NSGA-II的創(chuàng)新點(diǎn)：定量刻畫(huà)決策人的模糊偏好，采用更加符合決策人情感認(rèn)知的倆倆目標(biāo)間語(yǔ)義重要性的九級(jí)范式表達(dá)模糊偏好，并遵循決策人認(rèn)知規(guī)律的模糊性和漸進(jìn)性，分階段地刻畫(huà)更加細(xì)致清晰的目標(biāo)相對(duì)重要的表達(dá)范式。通過(guò)映射到目標(biāo)空間形成決策者新的偏好區(qū)域，最后構(gòu)建目標(biāo)相對(duì)重要的數(shù)學(xué)模型，在NSGA-II框架下給出同一非劣層下的個(gè)體優(yōu)劣排序，最終使整個(gè)進(jìn)化種群朝著Pareto最優(yōu)前沿面上的偏好域內(nèi)逼近。

1 多目標(biāo)優(yōu)化問(wèn)題

1.1 多目標(biāo)的數(shù)學(xué)模型

設(shè)最小化多目標(biāo)優(yōu)化問(wèn)題MOP(Multi-objective Optimization Problem)由n個(gè)決策變量，k個(gè)目標(biāo)函數(shù)和m個(gè)約束條件組成，其中x表示決策向量，y表示目標(biāo)向量，X表示決策向量x形成的決策空間，Y表示目標(biāo)向量y形成的目標(biāo)空間[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當(dāng)且僅當(dāng)?i=1,2,…,k，fi(xv)≥fi(xu) 且?j=1,2,…,k，有fj(xv)>fj(xu)。

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

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

1.2 偏好多目標(biāo)求解方法

從實(shí)踐的立場(chǎng)來(lái)看，多目標(biāo)的最優(yōu)解集的基數(shù)雖然不唯一，但是決策者僅需要少數(shù)甚至一個(gè)實(shí)踐解。經(jīng)典的進(jìn)化多目標(biāo)即偏好后驗(yàn)嵌入法的求解思路是借助于進(jìn)化算法的并行計(jì)算優(yōu)勢(shì)，經(jīng)過(guò)一定代數(shù)的種群進(jìn)化，旨在得到一組逼近前沿端的分布性和延展性良好的Pareto解集。然后用戶(hù)基于個(gè)人經(jīng)驗(yàn)、偏好等其他高層次信息進(jìn)一步評(píng)價(jià)這些解的優(yōu)劣，從中挑選一個(gè)滿(mǎn)意解。圖1給出倆目標(biāo)最小化優(yōu)化問(wèn)題的基本步驟[16]。

步驟1通過(guò)進(jìn)化優(yōu)化算法找到一組分布性延展性較好的若干非劣解。

步驟2從上面非劣解中挑選一個(gè)滿(mǎn)意解。

圖1 經(jīng)典后驗(yàn)偏好法求解多目標(biāo)問(wèn)題思路

相比較偏好后驗(yàn)嵌入法，偏好先驗(yàn)嵌入法在一開(kāi)始便由決策者給出一個(gè)偏好向量w，偏好向量用于構(gòu)建一個(gè)復(fù)合單目標(biāo)函數(shù)，從而將一個(gè)多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化成一個(gè)單目標(biāo)優(yōu)化問(wèn)題求解。然而在實(shí)踐中，特別是對(duì)于模糊偏好多目標(biāo)優(yōu)化問(wèn)題的求解，決策者事先給出一組偏好向量是困難的。同時(shí)合成的目標(biāo)函數(shù)對(duì)偏好向量的微調(diào)非常敏感，因此偏好先驗(yàn)嵌入法對(duì)決策者而言是較為主觀(guān)的，圖2是先驗(yàn)法思路[16]。

圖2 先驗(yàn)偏好法求解多目標(biāo)問(wèn)題思路

1.3 TOPSIS法的改進(jìn)

圖3 TOPSIS法

其中目標(biāo)方案Fi的TOPSIS綜合評(píng)價(jià)指數(shù)Ci即排隊(duì)值由大到小依次排列目標(biāo)方案的優(yōu)劣次序。

(2)

文獻(xiàn)[13]選取的正負(fù)理想解是由決策者根據(jù)自身偏好而給出,并沒(méi)有考慮給出兩個(gè)正負(fù)偏好點(diǎn)的可行性，在改進(jìn)的TOPSIS法里，本文采用基于移動(dòng)理想點(diǎn)法的正負(fù)偏好點(diǎn)更新策略，每一次進(jìn)化個(gè)體的迭代和位置的更新，使TOPSIS法中的理想點(diǎn)和厭惡點(diǎn)也都到自動(dòng)修正。

2 偏好區(qū)域的構(gòu)建

2.1 目標(biāo)相對(duì)重要性的語(yǔ)義范式

在融入模糊偏好的多目標(biāo)進(jìn)化優(yōu)化過(guò)程中，問(wèn)題的首要任務(wù)在于定量動(dòng)態(tài)刻畫(huà)決策者的偏好?？紤]到?jīng)Q策人對(duì)目標(biāo)問(wèn)題偏好認(rèn)知的模糊性與漸進(jìn)性，交互式的重構(gòu)決策者的偏好表達(dá)是求解多目標(biāo)進(jìn)化優(yōu)化問(wèn)題的關(guān)鍵所在。本文根據(jù)Thomas L.Saaty創(chuàng)建的屬性間相對(duì)重要性等級(jí)表[18]，考慮決策人對(duì)一般事物認(rèn)知的規(guī)律特點(diǎn)，對(duì)倆倆目標(biāo)進(jìn)行重要性比較，并且采用符合人的一般認(rèn)知習(xí)慣與判斷能力的更加細(xì)分的語(yǔ)義描述范式來(lái)表達(dá)目標(biāo)之間的相對(duì)重要性，在這種范式表達(dá)下，決策者可以容易且自然地表達(dá)對(duì)目標(biāo)間偏好強(qiáng)度。語(yǔ)義范式如表1所示。

表1 目標(biāo)間語(yǔ)義感知范式

定義4對(duì)于多目標(biāo)問(wèn)題中的任意兩個(gè)目標(biāo)fi、fj，兩者之間相對(duì)重要性有：

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

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

1) 決策人給出的偏好是fi比f(wàn)j同等重要，則有fi～fj。

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

3) 決策者給出的偏好是fi比f(wàn)j相當(dāng)重要，則有fi?5fj。

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

5) 決策者給出的偏好是fi比f(wàn)j絕對(duì)重要，則有fi?9fj。

基于上述定義以及決策者對(duì)目標(biāo)間重要性認(rèn)知的漸進(jìn)性，本文提出將帶偏好的進(jìn)化優(yōu)化過(guò)程劃分成三個(gè)子階段來(lái)表達(dá)決策者偏好。第一階段稱(chēng)為廣義目標(biāo)相對(duì)重要性?xún)?yōu)化(w=1，5，9)；第二階段稱(chēng)為一般目標(biāo)相對(duì)重要性?xún)?yōu)化(w=1，3，5，7，9)；第三階段稱(chēng)為精準(zhǔn)目標(biāo)相對(duì)重要性?xún)?yōu)化(w=1，2，3，4，5，6，7，8，9)。特別的，第一階段與第二階段以a1T為分割點(diǎn)，第二階段與第三階段以a2T為分割點(diǎn)。其中T為決策者給點(diǎn)的終止進(jìn)化代數(shù)，且有a1+a2=1，a1,a2∈(0,1)由決策者給定具體數(shù)值。在進(jìn)化過(guò)程中決策者可以實(shí)時(shí)交互式的修正對(duì)目標(biāo)函數(shù)的偏好,從而在目標(biāo)決策空間形成新的偏好域以引導(dǎo)進(jìn)化個(gè)體向偏好域上不斷逼近。

2.2 偏好域的等角度劃分

將感性的語(yǔ)言范式描述轉(zhuǎn)化為定量的數(shù)學(xué)模型表達(dá)，是衡量多目標(biāo)進(jìn)化優(yōu)化中嵌入決策者偏好意志成功與否的關(guān)鍵所在[19]，因此將上文中的目標(biāo)相對(duì)重要性語(yǔ)言描述以恰當(dāng)?shù)姆绞睫D(zhuǎn)化為數(shù)學(xué)模型投射到目標(biāo)空間的區(qū)域是非常必要的。本文對(duì)整個(gè)目標(biāo)空間進(jìn)行等角度偏好域劃分，其他具體角度劃分由決策者權(quán)衡給出。在此基礎(chǔ)上建立偏好區(qū)域的數(shù)學(xué)模型。這里示例給出倆目標(biāo)空間下廣義目標(biāo)相對(duì)重要性表達(dá)偏好的角度劃分，見(jiàn)圖4。

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

考慮圖4的廣義目標(biāo)相對(duì)重要性劃分圖,當(dāng)目標(biāo)空間被等角度劃分五個(gè)區(qū)域后，根據(jù)上述區(qū)域劃分的數(shù)學(xué)不等式模型并結(jié)合給定的決策者的偏好區(qū)域，可以進(jìn)一步判斷進(jìn)化個(gè)體所在區(qū)域和決策者偏好區(qū)域的位置關(guān)系，從而給出同一非支配層中進(jìn)化個(gè)體的優(yōu)劣比較即處于偏好域內(nèi)的個(gè)體占優(yōu)偏好域外個(gè)體。各個(gè)區(qū)域的數(shù)學(xué)不等式分別有：

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 進(jìn)化個(gè)體適應(yīng)值評(píng)價(jià)

本文給出一種全新的基于目標(biāo)相對(duì)重要性的偏好區(qū)域劃分排序法。該排序策略分為三個(gè)層次：基于分級(jí)的快速非劣解排序，同一非劣級(jí)別下偏好域占優(yōu)排序，同一非劣級(jí)別下基于雙極偏好占優(yōu)的偏好域外進(jìn)化個(gè)體排序。

定義5(RPT-Dominance) 決策目標(biāo)空間中任意的兩個(gè)決策向量X、Y，有XRPT-DominanceY，當(dāng)且僅當(dāng)滿(mǎn)足如下條件之一(其中Q是決策者修正的偏好區(qū)域，Xd、Yd是決策向量X、Y的擁擠度，CX、CY是決策向量X、Y綜合評(píng)價(jià)指數(shù))。

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。

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

4 基于目標(biāo)相對(duì)重要性與雙極偏好融合的RPT-NSGA-II算法

算法思想：融入決策者模糊偏好信息的多目標(biāo)優(yōu)化問(wèn)題，采用目標(biāo)相對(duì)重要的全新語(yǔ)義范式，依據(jù)人認(rèn)知的漸進(jìn)性，分階段地讓決策者與算法不斷交互，允許決策者改變自己的偏好。將優(yōu)化過(guò)程劃分為廣義目標(biāo)相對(duì)重要性?xún)?yōu)化，一般目標(biāo)相對(duì)重要性?xún)?yōu)化和精準(zhǔn)目標(biāo)相對(duì)重要性?xún)?yōu)化表述三個(gè)階段。決策適時(shí)給出目標(biāo)間偏好并在目標(biāo)空間形成相應(yīng)的偏好域數(shù)學(xué)模型，在NSGA-II優(yōu)化框架下進(jìn)行種群優(yōu)化，并根據(jù)RPT-Dominance排序算子比較兩兩個(gè)體間優(yōu)劣，從而引導(dǎo)進(jìn)化個(gè)體不斷朝著決策者感興趣的區(qū)域搜索，步驟如下：

Step1隨機(jī)初始化產(chǎn)生一個(gè)規(guī)模為N的群體P(t),進(jìn)化代數(shù)t=0。

Step2對(duì)進(jìn)化種群個(gè)體進(jìn)行快速非支配排序，并在不同進(jìn)化階段采用2.1節(jié)中語(yǔ)義范式來(lái)刻畫(huà)決策者偏好的表達(dá)。

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

Step4R(t)=P(t)∪Q(t)并依據(jù)RPT-Dominance錦標(biāo)賽選擇算子選出R(t)中前N個(gè)優(yōu)勢(shì)進(jìn)化個(gè)體，令其為P(t+1)。

Step5給定算法終止條件，當(dāng)滿(mǎn)足終止條件則輸出偏好域內(nèi)滿(mǎn)意解；否則，令t=t+1,轉(zhuǎn)Step 2。

對(duì)于引入偏好的多目標(biāo)遺傳算法，本文給出了一種全新的進(jìn)化個(gè)體適應(yīng)值排序策略，算法流程如圖5所示。

圖5 RPT-NSGA-II流程

5 實(shí) 驗(yàn)

為了驗(yàn)證本文提出的基于RPT-dominance的偏好多目標(biāo)遺傳算法的有效性，將該方法與偏好先驗(yàn)嵌入法和偏好后驗(yàn)嵌入法作比較，三種方法均在NSGA-II框架下進(jìn)行操作，對(duì)于每一個(gè)測(cè)試函數(shù)，三種方法均獨(dú)立運(yùn)行30次，五個(gè)基準(zhǔn)數(shù)值測(cè)試函數(shù)分別為ZDT1、ZDT2、ZDT3、SCH、DTLZ2。

5.1 算法參數(shù)設(shè)置

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

表2 偏好設(shè)置

5.2 性能評(píng)價(jià)指標(biāo)

1)AD測(cè)度：求得的最優(yōu)解集中X的所有進(jìn)化個(gè)體x到?jīng)Q策者最終偏好域的平均距離，記為:

(4)

式中：AD測(cè)度表達(dá)的是決策者采用某種進(jìn)化方式求得的Pareto最優(yōu)解的滿(mǎn)意程度，AD測(cè)度值越小則表示決策者對(duì)解集X越滿(mǎn)意。當(dāng)最終個(gè)體位于偏好域內(nèi)時(shí)，該個(gè)體的D(x)為0。

2)T測(cè)度：算法求解耗時(shí)。T側(cè)度越小則表示對(duì)應(yīng)算法求解的時(shí)間效率越高。

3)I測(cè)度：進(jìn)化個(gè)體位于最終偏好域內(nèi)的非劣解個(gè)數(shù)，I測(cè)度值越大，則表示該算法獲得決策者最終滿(mǎn)意解的能力越強(qiáng)。

5.3 實(shí)驗(yàn)結(jié)果分析

表3給出了三種不同算法得到的AD測(cè)度的均值和方差，由表3可知，與偏好先驗(yàn)嵌入法和偏好后驗(yàn)嵌入法相比較，本文提出的RPT-NSGA-II算法得到的5個(gè)測(cè)試函數(shù)的AD測(cè)度最小，即得到的所有最終解到?jīng)Q策者偏好域的平均距離最短，說(shuō)明本文提出的方法得到的最優(yōu)解最能反映出決策者的偏好，且本文算法得到的最優(yōu)解在反映決策者偏好方面顯著優(yōu)于偏好先驗(yàn)法和偏好后驗(yàn)法。對(duì)于2目標(biāo)測(cè)試函數(shù)ZDT1、ZDT2、ZDT3、SCH，采用先驗(yàn)法得到的AD測(cè)度大于后驗(yàn)法得到的AD測(cè)度，這表明在2目標(biāo)測(cè)試函數(shù)上，后驗(yàn)法得到的最優(yōu)解在反映決策者偏好的上要優(yōu)于先驗(yàn)法，但不難發(fā)現(xiàn)，只有ZDT3的AD測(cè)度表現(xiàn)較為明顯的差異，ZDT1、ZDT2、SCH在先驗(yàn)法和后驗(yàn)法得出的AD測(cè)度均無(wú)顯著差異。此外在3目標(biāo)測(cè)試函數(shù)DTLZ2問(wèn)題上，采用先驗(yàn)法得出的AD測(cè)度小于后驗(yàn)法得出的AD測(cè)度，因此認(rèn)為先驗(yàn)法和后驗(yàn)法在處理帶有模糊偏好的多目標(biāo)優(yōu)化問(wèn)題上具有結(jié)果不確定性，在不同類(lèi)型的優(yōu)化問(wèn)題表現(xiàn)出差異性，然而本文提出的交互式RPT-NSGA-II在處理此類(lèi)模糊偏好優(yōu)化問(wèn)題上表現(xiàn)出較為顯著的優(yōu)越性和穩(wěn)定性。

表3 三種方法對(duì)五個(gè)測(cè)試函數(shù)的AD測(cè)度

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

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

(a) RPT-NSGA-II交互法 (b) 先驗(yàn)法 (c) 后驗(yàn)法圖6 三種方法對(duì)ZDT1函數(shù)的滿(mǎn)意解分布

(a) RPT-NSGA-II交互法 (b) 先驗(yàn)法 (c) 后驗(yàn)法圖7 三種方法對(duì)ZDT2函數(shù)的滿(mǎn)意解分布

(a) RPT-NSGA-II交互法 (b) 先驗(yàn)法 (c) 后驗(yàn)法圖8 三種方法對(duì)ZDT3函數(shù)的滿(mǎn)意解分布

(a) RPT-NSGA-II交互法 (b) 先驗(yàn)法 (c) 后驗(yàn)法圖9 三種方法對(duì)SCH函數(shù)的滿(mǎn)意解分布

(a) RPT-NSGA-II交互法 (b) 先驗(yàn)法 (c) 后驗(yàn)法圖10 三種方法對(duì)DTLZ2函數(shù)的滿(mǎn)意解分布

6 結(jié) 語(yǔ)

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

本文的交互式進(jìn)化優(yōu)化算法將對(duì)包括工業(yè)和藝術(shù)產(chǎn)品的個(gè)性化創(chuàng)作設(shè)計(jì)、語(yǔ)言聲音圖像處理和快速檢索以及目擊人在海量人像庫(kù)中對(duì)嫌疑人畫(huà)像的再指認(rèn)等尋優(yōu)領(lǐng)域提供理論支持。

[1] 公茂果, 焦李成, 楊咚咚,等. 進(jìn)化多目標(biāo)優(yōu)化算法研究[J]. 軟件學(xué)報(bào), 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] 鄭金華, 謝諄志. 關(guān)于如何用角度信息引入決策者偏好的研究[J]. 電子學(xué)報(bào), 2014, 42(11):2239- 2246．

[8] 張艷梅, 曹懷虎, 賈恒越,等. 考慮用戶(hù)偏好的多目標(biāo)服務(wù)組合優(yōu)化算法研究[J]. 小型微型計(jì)算機(jī)系統(tǒng), 2016, 37(1):38- 42．

[9] 肖曉偉, 肖迪, 林錦國(guó),等. 多目標(biāo)優(yōu)化問(wèn)題的研究概述[J]. 計(jì)算機(jī)應(yīng)用研究, 2011, 28(3):805- 808．

[10] 王麗萍，章鳴雷，邱飛岳，等．基于角度懲罰距離精英選擇策略的偏好高維目標(biāo)優(yōu)化算法[J]．計(jì)算機(jī)學(xué)報(bào)，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] 鞏敦衛(wèi), 王更星, 孫曉燕. 高維多目標(biāo)優(yōu)化問(wèn)題融入決策者偏好的集合進(jìn)化優(yōu)化方法[J]. 電子學(xué)報(bào), 2014, 42(5):933- 939．

[13] 邱飛岳, 吳裕市, 邱啟倉(cāng),等. 基于雙極偏好占優(yōu)的高維目標(biāo)進(jìn)化算法[J]. 軟件學(xué)報(bào), 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．搜索方法論-優(yōu)化與決策支持技術(shù)入門(mén)教程[M]．北京：清華大學(xué)出版社，2014．

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

[18] 岳超源．決策理論與方法[M]．北京:科學(xué)出版社，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.