鄭金華，喻　果，賈　月

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

?

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

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

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

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

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

1　引言

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

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

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

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

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

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

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

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

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

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

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

1.1基本概念

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

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

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

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

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

2　相關(guān)工作

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

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

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

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

MOEA/D將多目標(biāo)優(yōu)化問題分解為一組單目標(biāo)子問題并為每個子問題分配一個個體，由各子問題上的個體組成初始種群，通過并行進(jìn)化種群來優(yōu)化所有子問題.由于相鄰子問題之間存在對彼此進(jìn)化有利的信息，MOEA/D基于權(quán)重向量間的歐式距離建立子問題的鄰域，MOEA/D通過鄰域內(nèi)交叉變異產(chǎn)生新的個體.基于鄰域的進(jìn)化是MOEA/D的有效搜索機(jī)制之一.在進(jìn)化過程中，優(yōu)勢基因一旦被某個子問題搜索到，就會在鄰域內(nèi)擴(kuò)散，因此通過相鄰子問題的信息搜索到優(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方法，該方法是以參考點作為偏好信息的載體，將Pareto支配關(guān)系重新定義，放松了Pareto支配關(guān)系的定義，從而提出了一個更加簡便、靈活的支配關(guān)系，有利于偏好信息的提取以及獲取偏好區(qū)域.

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

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

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

Flagv(w)的定義如下:

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

通過定義可以知道，當(dāng)PM給定的參考點在可行域或不可行域時，G-dominance收斂性能是較好的.但是當(dāng)參考點落在Pareto面上或者離Pareto面非常近的時候，此時整個種群聚集在一起，因為進(jìn)化算法為隨機(jī)算法，只有基于一定的概率產(chǎn)生和參考點相同或非常近的個體時，算法才會收斂，相反算法就會不收斂.整個種群一直在參考點和最優(yōu)點之間不斷的進(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，參考點g，權(quán)重向量w，x，y∈RP滿足以下條件之一，稱個體x R-dominance y，記為x＜ry:

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

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

其中:

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

g為參考點，δ∈［0，1］為臨界值.

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

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

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

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

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

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

第一步:求參考點對應(yīng)的映射點.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中ε'∈［0，1］.

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

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

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

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

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

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

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

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

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

4　算法框架

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

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

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

5　實驗結(jié)果與分析

5.1實驗參數(shù)設(shè)置

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

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

5.2對比實驗

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

表1　參考點設(shè)置

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

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

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

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

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

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

而采用本文通過權(quán)重迭代映射偏好區(qū)域的方法，可以避免參考點位置信息的影響，因為基于原點和參考點的向量是不會因為參考點而改變的.

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

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

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

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

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

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

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

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

6　總結(jié)

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

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

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

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

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

盡管在處理高維多目標(biāo)優(yōu)化問題之上，存在很多優(yōu)秀算法［19，20］，能比較好的解決許多高維問題.但是，隨著目標(biāo)維數(shù)的增加，非支配解的數(shù)目成指數(shù)級增加，收斂壓力減小，從而不利于算法的收斂.因此，加入有效的偏好信息，將利于算法性能的進(jì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)算法解集分布廣度評價方法［J］.計算機(jī)學(xué)報，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é)報，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年生于湖南邵陽，現(xiàn)為湘潭大學(xué)信息工程學(xué)院教授、博士生導(dǎo)師、CCF高級會員.主要研究方向為進(jìn)化計算、智能科學(xué).

E-mail: jhzheng@ xtu.edu.cn

喻果男.1987年8月出生，湖南寧鄉(xiāng)人.就讀于湘潭大學(xué)信息工程學(xué)院.主要研究方向為偏好多目標(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

作者簡介

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

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

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

中圖分類號：TP18

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

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