鄭金華，喻　果，賈　月

(1.湘潭大學(xué)信息工程學(xué)院，湖南湘潭411105; 2.湘潭大學(xué)“智能計(jì)算與信息處理”教育部重點(diǎn)實(shí)驗(yàn)室，湖南湘潭411105)

?

基于權(quán)重迭代的偏好多目標(biāo)分解算法解決參考點(diǎn)對(duì)算法影響的研究

鄭金華1，2，喻果1，2，賈月1，2

(1.湘潭大學(xué)信息工程學(xué)院，湖南湘潭411105; 2.湘潭大學(xué)“智能計(jì)算與信息處理”教育部重點(diǎn)實(shí)驗(yàn)室，湖南湘潭411105)

摘要：在傳統(tǒng)偏好多目標(biāo)進(jìn)化算法中，參考點(diǎn)是表達(dá)決策者的偏好信息最常用的方式，但是參考點(diǎn)所處位置信息有時(shí)嚴(yán)重影響算法的性能.針對(duì)以上問(wèn)題，本文提出了一種基于權(quán)重迭代的偏好多目標(biāo)分解算法(MOEA/DPRE)，主要利用權(quán)重迭代方法獲取一組均勻的權(quán)重向量，并對(duì)偏好區(qū)域進(jìn)行映射，使得算法在進(jìn)化過(guò)程中，不用考慮參考點(diǎn)所處位置信息對(duì)算法性能的影響，另外提出了一種穩(wěn)定可控的偏好區(qū)域模型，能響應(yīng)決策者設(shè)置任意大小的偏好區(qū)域.通過(guò)對(duì)比實(shí)驗(yàn)表明該算法具有較好的收斂性和分布性，同時(shí)給出了滿足決策者不同要求的算法模型，并且能夠很好的解決參考點(diǎn)的位置信息對(duì)算法的影響.

關(guān)鍵詞：多目標(biāo)分解算法;進(jìn)化算法;偏好;權(quán)重迭代;決策者

1　引言

多目標(biāo)進(jìn)化算法(Multi-Objective Evolutionary Algorithms，MOEAs)是一種模擬生物進(jìn)化來(lái)解決多目標(biāo)優(yōu)化問(wèn)題(Multi-Objective Optimization Problems，MOPs)的全局搜索算法.

近年來(lái)，MOEAs的研究焦點(diǎn)主要集中于適應(yīng)值分配策略的設(shè)計(jì)［1］，保持Pareto最優(yōu)解的分布性［2］及提高算法收斂性［3］等.現(xiàn)實(shí)生活中，設(shè)計(jì)者也只需要把篩選好的方案提供給決策者.因?yàn)閷?shí)際問(wèn)題中，往往由于個(gè)人的偏好或問(wèn)題的需求，決策者通常只對(duì)某些區(qū)域內(nèi)的Pareto折中解感興趣［4］，從而多目標(biāo)優(yōu)化與決策者偏好信息相結(jié)合成為了一個(gè)新興的熱點(diǎn)問(wèn)題［5］.通過(guò)引入偏好信息，算法將全部計(jì)算資源用來(lái)獲取偏好區(qū)域的Pareto解集，從而提高算法的求解效率，同時(shí)便于決策者高效做出最終決策.

目前，在這方面產(chǎn)生了許多的經(jīng)典算法，能有效地將偏好信息與多目標(biāo)進(jìn)化算法結(jié)合起來(lái).Fonseca和Fleming［6］最早將DM的偏好信息納入進(jìn)化算法中，定義了“Preferability”的關(guān)系算子; Cvetkovic和Parmee［7，8］通過(guò)模糊偏好矩陣把決策者對(duì)各目標(biāo)的偏好信息定量轉(zhuǎn)化為目標(biāo)的權(quán)重值，并建立基于權(quán)重值的“Pareto支配”關(guān)系;崔遜學(xué)等［4］提出多準(zhǔn)則中“ELECTRE”法構(gòu)造的“級(jí)別不劣于”關(guān)系; Molina等［9］通過(guò)放松“Pareto關(guān)系”，提出一種G-dominance的支配關(guān)系; Lamjed Ben Said等［10］在“Pareto關(guān)系”的基礎(chǔ)上，提出一種嚴(yán)格的偏序關(guān)系，稱之為R-dominance的支配關(guān)系等.

然而，目前基于參考點(diǎn)的偏好的多目標(biāo)進(jìn)化算法存在以下兩點(diǎn)不足之處:

第一，當(dāng)DM給定參考點(diǎn)離Pareto面很近、在Pareto面上或者在可行域里時(shí)，尤其當(dāng)參考點(diǎn)在Pareto面上時(shí)，算法性能表現(xiàn)尤其不穩(wěn)定，很有可能導(dǎo)致算法的不收斂、性能不穩(wěn)定.當(dāng)算法逼近參考點(diǎn)時(shí)，種群落在參考點(diǎn)附近狹窄的局部區(qū)域時(shí)，由于進(jìn)化算法為隨機(jī)算法，只有基于一定的概率產(chǎn)生與參考點(diǎn)相同或非常近的個(gè)體時(shí)，算法才會(huì)收斂，也正因?yàn)檫@樣，算法也很有可能往相反的方向進(jìn)化，當(dāng)部分個(gè)體基于一定的概率跳出偏好區(qū)域，帶領(lǐng)整個(gè)種群脫離了偏好區(qū)域，從而導(dǎo)致算法的不收斂.當(dāng)參考點(diǎn)在可行區(qū)域時(shí)，算法在參考點(diǎn)和Pareto面上對(duì)應(yīng)偏好區(qū)域之間往返進(jìn)化，導(dǎo)致消耗算法計(jì)算資源.例如: G-dominance當(dāng)參考點(diǎn)在Pareto面上時(shí)，算法會(huì)退化，甚至不收斂.R-dominance，當(dāng)參考點(diǎn)在可行域內(nèi)時(shí)，算法將不收斂.

第二，很多偏好多目標(biāo)進(jìn)化算法都沒(méi)有考慮DM對(duì)偏好區(qū)域大小的要求，所得到的偏好區(qū)域大小隨著參考點(diǎn)地移動(dòng)而變化，從而得不到穩(wěn)定的偏好區(qū)域，實(shí)驗(yàn)表明R-dominance存在這樣的缺陷.

針對(duì)以上的問(wèn)題，本文提出了算法MOEA/D-PRE，其主要的貢獻(xiàn)如下:

(1)針對(duì)于決策者的不同的偏好信息，分析G-dominance和R-dominance的理論原理，給出了兩種具體的模型，參考點(diǎn)不動(dòng)和運(yùn)動(dòng)的偏好模型以及偏好區(qū)域大小變化的偏好模型.

(2)通過(guò)分析標(biāo)準(zhǔn)邊界交叉的方法，給出了一個(gè)獲取權(quán)重向量的新模型和映射方法.

(3)通過(guò)實(shí)驗(yàn)證明了參考點(diǎn)的位置關(guān)系嚴(yán)重影響G-dominance與R-dominance的性能.

(4)實(shí)驗(yàn)驗(yàn)證了本文算法的性能，并對(duì)算法進(jìn)行了評(píng)估，與算法G-dominance和R-dominance進(jìn)行性能比較，驗(yàn)證了本文算法具有較好的優(yōu)越性.

1.1基本概念

不失一般性，下面給出無(wú)約束的連續(xù)多目標(biāo)優(yōu)化問(wèn)題:

其中x∈Ω，Ω為決策空間，F(xiàn):Ω→Rm的m維目標(biāo)函數(shù).Rm為目標(biāo)空間.

定義1(個(gè)體的Pareto支配關(guān)系)有兩個(gè)體x，y∈Rm，稱x支配y，記為x＞y，當(dāng)

(1)x的所有目標(biāo)不比y差，即xi≤yi，i∈{ 1，2，…，m} ;

(2)x至少存在一個(gè)子目標(biāo)比y好，即?j∈{ 1，2，…，m}，stxj＜yj.

2　相關(guān)工作

2.1偏好關(guān)系模型

Jaszkiewicz等［12］提出一種復(fù)雜的局部偏好關(guān)系模型.模型中，需要決策者給出起始點(diǎn)、終止點(diǎn)、無(wú)差別閾值向量、偏好閾值向量、否決閾值向量.本文采用簡(jiǎn)化的局部偏好關(guān)系模型［13］，如圖1所示:

2.2基于分解的多目標(biāo)進(jìn)化算法(MOEA/D)

將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題是用數(shù)學(xué)規(guī)劃方法求解多目標(biāo)問(wèn)題的基本策略.Zhang和Li等［11］將用數(shù)學(xué)規(guī)劃方法和進(jìn)化算法相結(jié)合，提出了基于分解的多目標(biāo)進(jìn)化算法(MOEA/D).該算法利用數(shù)學(xué)規(guī)劃方法求解多目標(biāo)問(wèn)題的基本策略將多目標(biāo)優(yōu)化問(wèn)題轉(zhuǎn)化為單目標(biāo)優(yōu)化問(wèn)題.

MOEA/D將多目標(biāo)優(yōu)化問(wèn)題分解為一組單目標(biāo)子問(wèn)題并為每個(gè)子問(wèn)題分配一個(gè)個(gè)體，由各子問(wèn)題上的個(gè)體組成初始種群，通過(guò)并行進(jìn)化種群來(lái)優(yōu)化所有子問(wèn)題.由于相鄰子問(wèn)題之間存在對(duì)彼此進(jìn)化有利的信息，MOEA/D基于權(quán)重向量間的歐式距離建立子問(wèn)題的鄰域，MOEA/D通過(guò)鄰域內(nèi)交叉變異產(chǎn)生新的個(gè)體.基于鄰域的進(jìn)化是MOEA/D的有效搜索機(jī)制之一.在進(jìn)化過(guò)程中，優(yōu)勢(shì)基因一旦被某個(gè)子問(wèn)題搜索到，就會(huì)在鄰域內(nèi)擴(kuò)散，因此通過(guò)相鄰子問(wèn)題的信息搜索到優(yōu)秀解的可能性更高.

其中常用的分解方法總結(jié)為以下三種:權(quán)重聚合(Weighted Sum)、切比雪夫(Tchebycheff)和基于懲罰的邊界交叉(Penalty-based Boundary Intersection，PBI).

(1)Weighted Sum分解方法:

(2)Tchebycheff分解方法:

(3)PBI分解方法:

其中，θ＞0為預(yù)設(shè)參數(shù).

2.3G支配關(guān)系

Molina等［9］提出的G-dominance方法，該方法是以參考點(diǎn)作為偏好信息的載體，將Pareto支配關(guān)系重新定義，放松了Pareto支配關(guān)系的定義，從而提出了一個(gè)更加簡(jiǎn)便、靈活的支配關(guān)系，有利于偏好信息的提取以及獲取偏好區(qū)域.

定義2(G-dominance)已知兩個(gè)點(diǎn)A，B∈RP，如果滿足下列條件之一，即稱A G-dominance B，記為A＜gB:

(1)Flagg(A)＞Flagg(B);

(2)對(duì)于?i =1，2，…，p，Ai≤Bi，滿足Flagg(A)＞Flagg(B)，那么至少存在一個(gè)j使得Aj＜Bj.

Flagv(w)的定義如下:

其中，v∈RP為參考點(diǎn)，w∈RP是目標(biāo)空間中的任意點(diǎn)，P為目標(biāo)個(gè)數(shù).上述定義將目標(biāo)空間劃分為兩部分Flag = 1和Flag = 0.算法的優(yōu)點(diǎn)在于，當(dāng)參考點(diǎn)在可行域或在不可行域，都不影響算法的收斂性效果.如圖2所示.

通過(guò)定義可以知道，當(dāng)PM給定的參考點(diǎn)在可行域或不可行域時(shí)，G-dominance收斂性能是較好的.但是當(dāng)參考點(diǎn)落在Pareto面上或者離Pareto面非常近的時(shí)候，此時(shí)整個(gè)種群聚集在一起，因?yàn)檫M(jìn)化算法為隨機(jī)算法，只有基于一定的概率產(chǎn)生和參考點(diǎn)相同或非常近的個(gè)體時(shí)，算法才會(huì)收斂，相反算法就會(huì)不收斂.整個(gè)種群一直在參考點(diǎn)和最優(yōu)點(diǎn)之間不斷的進(jìn)化和退化，這就是G-dominance存在的缺陷和不足，如圖3所示.

2.4R支配關(guān)系

Lamjed Ben Said等［10］提出的R-dominance方法，能將Pareto非支配集轉(zhuǎn)化為一組嚴(yán)格的偏序集，這種支配關(guān)系能引導(dǎo)算法快速的搜索到?jīng)Q策者喜歡的偏好區(qū)域.

定義3(R-dominance)已知種群P，參考點(diǎn)g，權(quán)重向量w，x，y∈RP滿足以下條件之一，稱個(gè)體x R-dominance y，記為x＜ry:

(1)x Pareto支配y，x＜y;

(2)x和y Pareto互不支配時(shí)，D(x，y，g)＜-δ，δ∈［0，1］

其中:

距離公式采用Deb采用的加權(quán)歐式距離［14］:

g為參考點(diǎn)，δ∈［0，1］為臨界值.

R-dominance存在一個(gè)缺點(diǎn)，在于當(dāng)參考點(diǎn)落在可行域時(shí)，將嚴(yán)重影響算法的收斂性能.由式(5)可知，當(dāng)參考點(diǎn)落在可行域，算法將引導(dǎo)種群向參考點(diǎn)進(jìn)行搜索，其偏離了算法的搜索方向，從而達(dá)不到最終的偏好區(qū)域，也就是說(shuō)算法性能對(duì)參考點(diǎn)的位置信息比較的敏感，將嚴(yán)重的影響決策者的最終決策，如圖4所示.

3　基于偏好信息的MOEA/D模型

模型首先將參考點(diǎn)的位置關(guān)系轉(zhuǎn)化為方向向量，然后通過(guò)邊界點(diǎn)來(lái)獲取偏好區(qū)域的大小，從而避免了參考點(diǎn)位置信息對(duì)算法的影響，而且提供了個(gè)體進(jìn)化的方向.針對(duì)于決策者的不同的偏好信息，下面給出了兩種具體的模型，參考點(diǎn)不動(dòng)和運(yùn)動(dòng)的偏好模型以及偏好區(qū)域大小變化的偏好模型.

3.1參考點(diǎn)不動(dòng)和運(yùn)動(dòng)的偏好MOEA/D模型

對(duì)于基于分解的多目標(biāo)進(jìn)化算法，怎么給子問(wèn)題指定相關(guān)權(quán)重是MOEA/D的關(guān)鍵問(wèn)題，因?yàn)榛诜纸獾亩嗄繕?biāo)進(jìn)化算法就是將多目標(biāo)優(yōu)化問(wèn)題通過(guò)子問(wèn)題分解，將其轉(zhuǎn)化為單目標(biāo)問(wèn)題.本文通過(guò)PM給定的參考點(diǎn)與原點(diǎn)O(0，0，…，0)的連線確定偏好區(qū)域方向，連線經(jīng)過(guò)面S: f1+ f2+…+ fm= 1，交點(diǎn)為A*在面S的映射點(diǎn).通過(guò)決策者給定的偏好區(qū)域大小半徑ε以及映射到偏好區(qū)域內(nèi)的權(quán)重向量，該模型將參考點(diǎn)的位置信息成功轉(zhuǎn)化為權(quán)重向量，因此此時(shí)參考點(diǎn)所在位置與算法無(wú)關(guān)了，因?yàn)樗跈?quán)重向量的線上.如圖5、圖6所示.

通過(guò)二維和三維的圖形，總結(jié)可以得到高維的模型.

第一步:求參考點(diǎn)對(duì)應(yīng)的映射點(diǎn).

由式(9)可求得參考點(diǎn)對(duì)應(yīng)的映射點(diǎn)A'為:

第二步:設(shè)定偏好區(qū)域.

如上圖6所示，由PM給定一個(gè)偏好區(qū)域大小半徑ε∈［0，1］，通過(guò)每維邊界點(diǎn)B'、C'、D'和映射點(diǎn)A'，確定偏好區(qū)域大小，可以依據(jù)參考者的意愿，任意設(shè)定，如式(11)所示:

第三步:在偏好區(qū)域獲取權(quán)重.

由第二步設(shè)定好偏好區(qū)域的范圍之后，可以通過(guò)任意的確定性算法確定好權(quán)重值，即在映射點(diǎn)的周圍產(chǎn)生所需的點(diǎn)集.

Indraneel Das［15］等人提出的標(biāo)準(zhǔn)邊界交叉文章中，有一種求解權(quán)重的方法.通過(guò)設(shè)定每維的步長(zhǎng)和節(jié)點(diǎn)個(gè)數(shù)，循環(huán)迭代獲取一組均勻的權(quán)重.如圖7所示.

但是，該方法存在一個(gè)缺點(diǎn)，當(dāng)映射點(diǎn)在空間的邊界點(diǎn)時(shí)，產(chǎn)生的點(diǎn)落在了偏好區(qū)域之外，因此增加了大量的邏輯判斷，從而增加了算法的復(fù)雜度和運(yùn)算開(kāi)銷，尤其在高維多目標(biāo)算法中，更加的顯著.

第四步:由MOEA/D算法求解多目標(biāo)優(yōu)化問(wèn)題.

基于參考點(diǎn)運(yùn)動(dòng)的偏好多目標(biāo)分解進(jìn)化算法模型，在此基礎(chǔ)上通過(guò)修改參考點(diǎn)對(duì)應(yīng)的映射點(diǎn)來(lái)改變權(quán)重向量以實(shí)現(xiàn)該模型.

3.2偏好區(qū)域大小變化的模型

當(dāng)DM對(duì)偏好區(qū)域大小有一定的要求的時(shí)候，很多的算法都沒(méi)有考慮到這一點(diǎn)，得到的偏好區(qū)域大小隨著參考點(diǎn)地移動(dòng)而顯著變化，而得不到穩(wěn)定的偏好區(qū)域.基于此本文給出了一個(gè)簡(jiǎn)單穩(wěn)定可控的偏好區(qū)域模型，如圖8所示.

由于不動(dòng)參考點(diǎn)的MOEA/D模型可知，當(dāng)確定偏好區(qū)域后，在區(qū)域中設(shè)定均勻的權(quán)重向量，算法可以得到相應(yīng)的偏好區(qū)域.因此模型轉(zhuǎn)化為求偏好區(qū)域的邊界點(diǎn).

通過(guò)參考點(diǎn)Q、原點(diǎn)O、邊界點(diǎn)B，獲取偏好區(qū)域邊界B'的坐標(biāo).

由式(9)(10)可以得到參考點(diǎn)Q對(duì)應(yīng)的在面S上的映射點(diǎn)A的坐標(biāo).易知:

可得偏好區(qū)域邊界點(diǎn)B'的坐標(biāo).由向量變換可得:

其中ε'∈［0，1］.

針對(duì)于DM要求的不同偏好區(qū)域，得到的偏好區(qū)域如下圖9所示.

該模型可以通過(guò)動(dòng)態(tài)設(shè)置偏好區(qū)域參數(shù)ε來(lái)調(diào)整權(quán)重向量，從而獲取不同大小的偏好區(qū)域，有利于決策者選擇.

3.3權(quán)重獲取方法—權(quán)重迭代法

通過(guò)對(duì)標(biāo)準(zhǔn)邊界交叉算法的分析，本文給出了一種權(quán)重迭代獲取權(quán)重的迭代方法.

第1步:計(jì)算參考點(diǎn)A(f1，f2，…，fm)在面S: f1+ f2+…+ fm=1上的映射點(diǎn)A'.

第2步:獲取面f1+ f2+…+ fm= 1上的每維邊界點(diǎn)點(diǎn)集F，如圖10三維情況下邊界點(diǎn)為B(1，0，0)， C(0，1，0)，D(0，0，1).

第3步:由PM給定一個(gè)偏好區(qū)域大小半徑ε，將每維邊界點(diǎn)點(diǎn)集F和映射點(diǎn)A'合并為點(diǎn)集F'，由F'和ε確定偏好區(qū)域大小.得到偏好區(qū)域的邊界點(diǎn)集.三維情況下如上圖可得到B'，C'，D'.由向量可得B'點(diǎn)的坐標(biāo)，以此可知B'，C'，D'點(diǎn)的坐標(biāo)值.

第4步:由點(diǎn)集F'個(gè)體兩兩交叉求中點(diǎn)，獲取新的點(diǎn)集K，F(xiàn)'與K兩兩交叉獲取中點(diǎn)解集K'，將F'與K合并更替F'，即F'= F'∪K，F(xiàn)'再與K'產(chǎn)生中點(diǎn)集K″，更新K'= K″，交替更新直到K'點(diǎn)集大小達(dá)到種群大小.如圖10，由點(diǎn)集F'=(A'，B'，C'，D')兩兩交叉得到中點(diǎn)集K =(1，2，3，4，5，6)，再由F'與K兩兩交叉得到中點(diǎn)集K'，F(xiàn)'= F'∪K，K = K'，再進(jìn)行F'與K兩兩交叉，不斷交替更新.最終得到一組均勻的權(quán)重向量.

權(quán)重迭代法簡(jiǎn)單容易實(shí)現(xiàn)，所有的點(diǎn)都在偏好區(qū)域內(nèi)，且所有的點(diǎn)都落在凸多邊形中，滿足權(quán)重要求.同時(shí)還可以獲取一組比較均勻的權(quán)重向量.如圖11所示.

4　算法框架

算法的時(shí)間復(fù)雜度主要在于求解邊界和迭代更替，時(shí)間復(fù)雜度為O(m2)，m為目標(biāo)個(gè)數(shù)，迭代更替的時(shí)間復(fù)雜度為O(n·m)，m為目標(biāo)維數(shù)，n為種群大小.

本文首先結(jié)合決策者的偏好信息(參考點(diǎn)信息)，利用權(quán)重迭代方法初始化一組均勻權(quán)重向量，對(duì)偏好區(qū)域進(jìn)行映射，從每個(gè)權(quán)重對(duì)應(yīng)的子問(wèn)題鄰域中進(jìn)行個(gè)體之間的交叉變異，當(dāng)產(chǎn)生優(yōu)秀的個(gè)體時(shí)替換當(dāng)前個(gè)體，依次重復(fù)直到滿足終止條件，輸出最優(yōu)解.具體算法如下所示:

算法中交叉變異算子終止條件可以自由設(shè)定，不影響算法的框架.其中算法的主要的時(shí)間復(fù)雜度在于Step1和Step2.Step1的時(shí)間復(fù)雜度在于權(quán)重迭代，復(fù)雜度為O(n·m)，而Step2的時(shí)間復(fù)雜度為O(n2).所以總的時(shí)間復(fù)雜度為O((n·m + n)·n).

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

5.1實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)考慮參考點(diǎn)在Pareto面上和在可行域兩種情況，算法MOEA/D-PRE采用MOEA/D中的邊界交叉(Penalty-based Boundary Intersection，PBI)分解方法，參數(shù)θ= 5.本文選擇常用的測(cè)試函數(shù): ZDT系列測(cè)試函數(shù)［16］，DTLZ系列測(cè)試函數(shù)［17］.

其中ZDT系列測(cè)試函數(shù)設(shè)置種群大小為100，變量維數(shù)為30，交叉概率為0.99，變異概率為0.1，最大運(yùn)行代數(shù)為500(其中ZDT4為1500代，ZDT6為1200 代).DTLZ系列測(cè)試函數(shù)設(shè)置種群大小為200，變量維數(shù)為12，交叉概率為0.99，變異概率為0.1，最大運(yùn)行代數(shù)為500.每一維的偏好區(qū)域大小都統(tǒng)一設(shè)定為ε= 0.1，參考點(diǎn)的設(shè)置如下表1所示.

5.2對(duì)比實(shí)驗(yàn)

算法對(duì)每個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行30次，結(jié)果取平均值.所有試驗(yàn)為了證明算法的收斂性能，本文采用GD［18］指標(biāo)來(lái)估計(jì)算法的最終邊界和全局Pareto最優(yōu)面的趨近距離.

表1　參考點(diǎn)設(shè)置

其中，n為解集中的個(gè)體數(shù)，di為每個(gè)個(gè)體到全局最優(yōu)面的最小歐幾里得距離.GD值越小，解集越靠近Pareto最優(yōu)面，從而表明算法的收斂性越好.

針對(duì)ZDT系列測(cè)試函數(shù)，本文設(shè)計(jì)了10組對(duì)比實(shí)驗(yàn)，考慮參考點(diǎn)設(shè)置在Pareto面上以及可行域內(nèi)兩種情況，將MOEA/D-PRE和G-dominance、R-dominance進(jìn)行實(shí)驗(yàn)比較，表2和表3給出ZDT系列測(cè)試函數(shù)的GD實(shí)驗(yàn)指標(biāo)值.

通過(guò)表2和表3給出的GD指標(biāo)對(duì)應(yīng)的均值和方差可知，MOEA/D-PRE、G-dominance以及R-dominance在測(cè)試問(wèn)題ZDT1、ZDT2、ZDT3上都收斂得比較好，都找到了參考點(diǎn)所對(duì)應(yīng)的的偏好區(qū)域.但是從表2還可以知道，當(dāng)參考點(diǎn)在Pareto面上時(shí)，R-dominance在這三個(gè)測(cè)試問(wèn)題上沒(méi)有G-dominance和MOEA/D-PRE好，同時(shí)MOEA/DPRE又要比G-dominance要好.可知對(duì)于相對(duì)簡(jiǎn)單的測(cè)試問(wèn)題上，參考點(diǎn)的位置信息影響了R-dominance和G-dominance的收斂性能.這是由于支配關(guān)系存在的缺陷所導(dǎo)致的，即以參考點(diǎn)作為信息引導(dǎo)，采用加權(quán)歐式距離或者放松Pareto支配關(guān)系都會(huì)影響算法的收斂.而采用本文通過(guò)權(quán)重迭代映射偏好區(qū)域的方法，可以避免參考點(diǎn)位置信息的影響，因?yàn)榛谠c(diǎn)和參考點(diǎn)的向量是不會(huì)因?yàn)閰⒖键c(diǎn)而改變的.

通過(guò)表2和表3給出的GD指標(biāo)對(duì)應(yīng)的均值和方差可知，MOEA/D-PRE、G-dominance和R-dominance在測(cè)試問(wèn)題ZDT1、ZDT2、ZDT3上都收斂得比較好，都找到了參考點(diǎn)所對(duì)應(yīng)的偏好區(qū)域.但從表2還可以知道，當(dāng)參考點(diǎn)在Pareto面上時(shí)，R-dominance在這三個(gè)測(cè)試問(wèn)題上沒(méi)有G-dominance和MOEA/D-PRE好，同時(shí)MOEA/D-PRE又要比G-dominance要好.可知對(duì)于相對(duì)簡(jiǎn)單的測(cè)試問(wèn)題上，參考點(diǎn)的位置信息影響了R-dominance和G-dominance的收斂性能，這是由于支配關(guān)系存在的缺陷所導(dǎo)致的，即以參考點(diǎn)作為信息引導(dǎo)，采用加權(quán)歐式距離或者放松Pareto支配關(guān)系都會(huì)影響算法的收斂.

表2　當(dāng)參考點(diǎn)在Pareto面時(shí)的GD指標(biāo)

表3　當(dāng)參考點(diǎn)在可行區(qū)域時(shí)的GD指標(biāo)

而采用本文通過(guò)權(quán)重迭代映射偏好區(qū)域的方法，可以避免參考點(diǎn)位置信息的影響，因?yàn)榛谠c(diǎn)和參考點(diǎn)的向量是不會(huì)因?yàn)閰⒖键c(diǎn)而改變的.

從表2、3和對(duì)比實(shí)驗(yàn)圖12可知，特別在ZDT4測(cè)試問(wèn)題上G-dominance和R-dominance，完全沒(méi)有收斂.對(duì)于比較復(fù)雜的測(cè)試問(wèn)題，放松支配關(guān)系和加權(quán)歐氏距離嚴(yán)重影響了算法的搜索性能，最終導(dǎo)致了算法的不收斂.在ZDT6測(cè)試問(wèn)題上，G-dominance也完全沒(méi)有收斂，R-dominance收斂比較好.但是當(dāng)參考點(diǎn)在可行域中時(shí)，由偏好關(guān)系模型可知，原點(diǎn)和參考點(diǎn)的射線沒(méi)有經(jīng)過(guò)R-dominance獲取到的偏好區(qū)域，因而不能提供滿足決策者所想要的信息.因此MOEA/D-PRE盡管沒(méi)有R-dominance收斂那么好，但是滿足的了決策者所需要的信息.

綜合表2和3可知，MOEA/D-PRE要比G-dominance 和R-dominance更能滿足決策者需要的信息.并且ZDT系列測(cè)試問(wèn)題算法都收斂了，因此MOEA/D-PRE的性能也比較的穩(wěn)定.

針對(duì)DTLZ系列測(cè)試問(wèn)題，本文進(jìn)行12組對(duì)比實(shí)驗(yàn)，同時(shí)考慮了參考點(diǎn)在Pareto面上和在可行域兩種情況.MOEA/D-PRE、G-dominance以及R-dominance的GD指標(biāo)對(duì)比試驗(yàn)如表4和表5所示.

由表4和表5可知，算法MOEA/D-PRE、G-dominance和R-dominance在DTLZ2和DTLZ4的測(cè)試問(wèn)題上都有較好的收斂效果.但是從表可知MOEA/D-PRE相比而言有更好的收斂效果.而在DTLZ1、DTLZ3、DTLZ6比較難以搜索到PF的測(cè)試問(wèn)題上，G-dominance完全沒(méi)有收斂，這是因?yàn)镚-dominance算法本身只提供了參考點(diǎn)的引導(dǎo)信息，受到參考點(diǎn)的位置關(guān)系的影響，導(dǎo)致算法向參考點(diǎn)進(jìn)化，但是當(dāng)參考點(diǎn)在可行域或在Pareto面上時(shí)，很容易讓算法進(jìn)入局部搜索，最終使得算法不收斂.

而R-dominance在DTLZ1和DTLZ3上都收斂了，而且當(dāng)參考點(diǎn)在可行區(qū)域時(shí)，收斂效果還要比MOEA/DPRE效果更好.但是通過(guò)實(shí)驗(yàn)圖12可知，R-dominance所獲得的偏好區(qū)域并不能滿足決策的要求，而算法R-dominance雖然收斂了但是所獲取的是整個(gè)PF.并不滿足偏好關(guān)系.當(dāng)參考點(diǎn)在可行域時(shí)，在DTLZ5和DTLZ6上，R-dominance沒(méi)有收斂.實(shí)驗(yàn)證明了R-dominance支配關(guān)系的不足，當(dāng)參考點(diǎn)在可行域時(shí)，加權(quán)歐式距離會(huì)引導(dǎo)種群往參考點(diǎn)靠近，進(jìn)而導(dǎo)致算法無(wú)法收斂.

表4　當(dāng)參考點(diǎn)在Pareto面時(shí)的GD指標(biāo)

表5　當(dāng)參考點(diǎn)在可行區(qū)域時(shí)的GD指標(biāo)

綜合表4和表5以及圖13可知，算法MOEA/D-PRE 在DTLZ系列測(cè)試問(wèn)題上有較好的收斂性，而且能夠很好地滿足決策者的要求，得到想要的偏好區(qū)域.算法性能比較穩(wěn)定，不因參考點(diǎn)的位置信息而改變.因此在DTLZ測(cè)試問(wèn)題上MOEA/D-PRE相比之下有更好的表現(xiàn).

6　總結(jié)

偏好多目標(biāo)進(jìn)化算法重點(diǎn)是要準(zhǔn)確的表達(dá)決策者的偏好信息，并最終獲得偏好區(qū)域內(nèi)的最優(yōu)解集，本文對(duì)此進(jìn)行了比較深入的研究，主要工作可以概括為以下3個(gè)方面:

(1)通過(guò)對(duì)偏好信息的深入分析，提出了一個(gè)偏好區(qū)域的變化模型，更簡(jiǎn)單準(zhǔn)確的表達(dá)決策者的偏好信息.

(2)通過(guò)實(shí)驗(yàn)證明了參考點(diǎn)所處位置信息嚴(yán)重影算法G-dominance和R-dominance的性能.

(3)采用權(quán)重迭代法引導(dǎo)搜索過(guò)程，避免了算法陷入局部最優(yōu)同時(shí)保證解集具有較好的分布性.本文算法與MOEA/D結(jié)合，能夠避免參考點(diǎn)的位置對(duì)算法性能的影響，保證了算法的收斂性與參考點(diǎn)的位置無(wú)關(guān).并與G-dominance、R-dominance方法對(duì)比，實(shí)驗(yàn)結(jié)果表明了該算法具有很好的收斂性.

本文提出了一種基于權(quán)重迭代的偏好多目標(biāo)分解算法(MOEAD-PRE)，主要利用權(quán)重迭代方法獲取一組均勻的權(quán)重向量，對(duì)偏好區(qū)域進(jìn)行映射，使得算法在進(jìn)化過(guò)程中，不用考慮參考點(diǎn)的位置對(duì)算法性能的影響，另外提出了一種穩(wěn)定可控的偏好區(qū)域模型，能響應(yīng)決策者設(shè)置任意大小的偏好區(qū)域.通過(guò)對(duì)比實(shí)驗(yàn)表明該算法具有較好的收斂性和分布性，同時(shí)給出了滿足決策者不同要求的算法模型.

盡管在處理高維多目標(biāo)優(yōu)化問(wèn)題之上，存在很多優(yōu)秀算法［19，20］，能比較好的解決許多高維問(wèn)題.但是，隨著目標(biāo)維數(shù)的增加，非支配解的數(shù)目成指數(shù)級(jí)增加，收斂壓力減小，從而不利于算法的收斂.因此，加入有效的偏好信息，將利于算法性能的進(jìn)一步提升.所以，把偏好信息融入高維問(wèn)題將是我們未來(lái)的研究重點(diǎn).

參考文獻(xiàn)

［1］Davarynejad M，Vrancken J，van den Berg J，et al.A fitness granulation approach for large-scale structural design optimization［A］.Variants of Evolutionary Algorithms for Real-World Applications［M］.Berlin Heidelberg: Springer，2012.245-280.

［2］李密青，鄭金華.一種多目標(biāo)算法解集分布廣度評(píng)價(jià)方法［J］.計(jì)算機(jī)學(xué)報(bào)，2011，34(4): 647-664.Li Miqing，Zheng Jinhua.An indicator for assessing the spread of solutions in multi-objective evolutionary algorithms［J］.Chinese Journal of Computers，2011，34(4): 647-664.(in Chinese)

［3］Sindhya K，Deb K，Miettinen K.Improving convergence of evolutionary multi-objective optimization with local search: a concurrent hybrid algorithm［J］.Natural Computing，2011，10(4): 1407 -1430.

［4］崔遜學(xué)，林闖.一種基于偏好的多目標(biāo)調(diào)和遺傳算法［J］.軟件學(xué)報(bào)，2005，16(5): 761 -770.Cui Xunxue，Lin Chuang.A preference-based multi-objective concordance genetic algorithm［J］.Journal of Software，2005，16(5): 761 -770.(in Chinese)

［5］Deb K，Sundar J，Rao N U B，et al.Reference point based multi-objective optimization using evolutionary algorithms［J］.International Journal of Computational Intelligence Research，2006，2(3): 273 - 286.

［6］Fonseca C M，F(xiàn)leming P J.Multi-objective genetic algorithms made easy: selection sharing and mating restriction［A］.Proc of the 1st IEEE International Conference on Genetic Algorithms in Engineering Systems: Innovations and Applications［C］.Sheffield，UK，1995.42 - 52.

［7］Cvetkovic D，Parmee I C.Genetic algorithm based multi-objective optimization and conceptual engineering design［A］.Proc of the Congress on Evolutionary Computation［C］.Washington，USA，1999.I:29 -36.

［8］Cvetkovic D，Parmee I C.Preferences and their application in evolutionary multi-objective optimization［J］.IEEE Trans on Evolutionary Computation，2002，6(1): 42 -57.

［9］Molina J，Santana L V，Coello C A C，et al.G-dominance: reference point based dominance for multi-objective metaheuristics［J］.European Journal of Operational Research，2009，197(2): 685 -692.

［10］Ben Said L，Bechikh S，Ghédira 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.

［11］Zhang Q，Li H.MOEA/D: A multiobjective evolutionary algorithm based on decomposition［J］.IEEE Transactions on Evolutionary Computation，2007，11(6): 712 -731.

［12］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.

［13］K Deb，A Kumar.Light beam search based multi-objective optimization using evolutionary algorithms［A］.Proc of the IEEE Congress on Evolutionary Computation［C］.Singapore，2007.2125 -2132.

［14］Deb K，Sundar J，Udaya Bhaskara Rao N，et al.Reference point based multi-objective optimization using evolutionary algorithms［J］.International Journal of Computational Intelligence Research，2006，2(3): 273-286.

［15］Das I，Dennis J E.Normal-boundary intersection: a new method for generating the Pareto surface in nonlinear multicriteria optimization problems［J］.SIAM Journal on Optimization，1998，8(3): 631 -657.

［16］Zitzler E，Deb K，Thiele L.Comparison of multi-objective evolutionary algorithms: empirical results［J］.Evolutionary Computation，2000，8(2): 173 -195.

［17］Deb K，Thiele L，Laumanns M，Zitzler E.Scalable multiobjective optimization test problems［A］.Proceedings of the Congress on Evolutionary Computation 2002［C］.Piscataway，New Jersey，2002.825 -830.

［18］Van Veldhuizen D A，Lamont G B.Evolutionary computation and convergence to a Pareto front［A］.Proc of the Late Breaking Papers at the Genetic Programming Conference［C］.Madison，USA，1998.221 -228.

［19］Gacto M J，Galende M，Alcalá R，et al.METSK-HD e: a multiobjective evolutionary algorithm to learn accurate TSK-fuzzy systems in high-dimensional and large-scale regression problems［J］.Information Sciences，2014，276: 63 -79.

［20］Miqing Li，Shengxiang Yang，Xiaohui Liu.Shift-based density estimation for Pareto-based algorithms in manyobjective optimization［J］.IEEE Transactions on Evolutionary Computation，2014，22(2): 189 -230.

鄭金華男.1963年生于湖南邵陽(yáng)，現(xiàn)為湘潭大學(xué)信息工程學(xué)院教授、博士生導(dǎo)師、CCF高級(jí)會(huì)員.主要研究方向?yàn)檫M(jìn)化計(jì)算、智能科學(xué).

E-mail: jhzheng@ xtu.edu.cn

喻果男.1987年8月出生，湖南寧鄉(xiāng)人.就讀于湘潭大學(xué)信息工程學(xué)院.主要研究方向?yàn)槠枚嗄繕?biāo)進(jìn)化算法.

E-mail: yuguo0801@126.com

Research on MOEA/D Based on User-Preference and Alternate Weight to Solve the Effect of Reference Point on Multi-Objective Algorithms

ZHENG Jin-hua1，2，YU Guo1，2，JIA Yue1，2
(1.Department of Information Engineering，Xiangtan University，Xiangtan，Hunan 411105，China; 2.Key Laboratory of Intelligent Computing and Information Processing(Ministry of Education)，Xiangtan，Hunan 411105，China)

Abstract:In MOEAs based on user-preference，reference point is most commonly used to express the preference information，but the position of reference point has detrimental effect on the performance of algorithms.According to this issue，this paper proposes MOEA/D-PRE that combines MOEA/D with preference information and alternate weight method.This algorithm applies the alternate weight method to map the region of interest of the decision maker，which can avoid the influence of the reference point，and the model is easy for the decision maker to adjust the size of preference region.Experimental results show that this approach has much better performance.Moreover，this paper proposes different models to satisfy different demands of the decision maker，which has provided a new way to solve MOPs based on preference information and especially to tackle the effect of reference point.

Key words:MOEA/D(multi-objective evolutionary algorithm based on decomposition); evolution algorithm; preference; alternate weight; decision maker

作者簡(jiǎn)介

基金項(xiàng)目:國(guó)家自然科學(xué)基金(No.61379062);湖南省自然科學(xué)基金(No.14JJ2072);湖南省科技廳項(xiàng)目(No.2013SK3136);湖南省科技計(jì)劃(No.2014GK3027);湖南省教育廳重點(diǎn)科研項(xiàng)目(No.12A135);湖南省研究生創(chuàng)新基金(No.CX2013A011)

收稿日期:2014-04-08;修回日期: 2014-12-19;責(zé)任編輯:李勇鋒

DOI:電子學(xué)報(bào)URL：http: / /www.ejournal.org.cn10.3969/j.issn.0372-2112.2016.01.011

中圖分類號(hào)：TP18

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：0372-2112(2016)01-0067-10