汪 欣，夏 超

(南京航空航天大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，江蘇 南京 211100)

0 引 言

實際中大部分的優(yōu)化問題都是組合優(yōu)化問題，在很多情況下各個目標(biāo)之間都是相互沖突的，即對于一個目標(biāo)上的改善很有可能會導(dǎo)致其余一個或幾個目標(biāo)性能的降低。因此多目標(biāo)優(yōu)化的目的是對多個目標(biāo)上進(jìn)行權(quán)衡，使得優(yōu)化結(jié)果能夠在各個目標(biāo)上都盡可能達(dá)到最優(yōu)。進(jìn)化算法是一種基于種群的多點搜索方法，已經(jīng)在很多多目標(biāo)優(yōu)化問題[1]中得到了應(yīng)用[2]。當(dāng)前已經(jīng)有很多算法在2～3個目標(biāo)的組合多目標(biāo)優(yōu)化問題中取得了良好的效果，但是在超多目標(biāo)(3個以上目標(biāo))上的表現(xiàn)不佳。針對超多目標(biāo)的問題的特性，提出了一種基于雙種群的Pareto局部搜索算法(DPPLS)。DPPLS在分解的框架下，分別維持著兩個種群，一個種群來保持解的收斂性，另一個用于貢獻(xiàn)多樣性。

1 概 述

1.1 多目標(biāo)優(yōu)化問題定義

一個多目標(biāo)優(yōu)化問題(MOP)的定義如下：

(1)

其中，Ω是決策空間；F:Ω→Rm是由m個實值目標(biāo)函數(shù)組成的目標(biāo)空間。可行目標(biāo)域為{F(x)|x∈Ω}。當(dāng)Ω為離散集合時，式1被稱作一個多目標(biāo)組合優(yōu)化問題。

1.2 支配關(guān)系描述

令u,v∈Rm，當(dāng)且僅當(dāng)對于所有的i∈{1,2,…,m}均有ui≤vi，且至少存在一個j∈{1,2,…,m}使得uj

1.3 多目標(biāo)組合優(yōu)化問題

在實際的多目標(biāo)組合優(yōu)化問題中，獲得其PF通常是一個NP難問題。在過去的探索中，多目標(biāo)啟發(fā)式算法(如Pareto局部搜索[4-5]、多目標(biāo)模擬退火等算法[6])、多目標(biāo)元啟發(fā)式算法(如多目標(biāo)進(jìn)化算法(MOEAs[7-13])以及多目標(biāo)蟻群算法(MOACO[14]))被廣泛應(yīng)用于近似真實問題的PF。

1.4 進(jìn)化算法背景

在進(jìn)化算法中，選擇解的過程對算法效果及其重要。通常，算法的目的是獲得收斂性和多樣性取得權(quán)衡條件下的卓越的近似Pareto最優(yōu)解集[15-16]。收斂性可以用來度量最終解解集合和真實PF的距離，其結(jié)果越小越好。多樣性可以用來度量解集合在PF上分布的效果，其越均勻越好。基于上述兩種選擇解的需求，當(dāng)前的進(jìn)化算法可以分為基于指標(biāo)的、基于分解的以及基于支配關(guān)系的算法[17-20]。一個基于分解的多目標(biāo)進(jìn)化算法的典型代表是MOEA/D[21]，MOEA/D的核心思想是將一個多目標(biāo)優(yōu)化算法分解為多個子問題，然后同時優(yōu)化這些子問題。這些子問題的目標(biāo)函數(shù)可以是多目標(biāo)優(yōu)化問題線性或非線性的聚合函數(shù)。在MOEA/D中，每一個解都被綁定至一個子問題，并且如果兩個子問題對應(yīng)的權(quán)重向量之間的歐氏距離相近，則稱這兩個子問題為鄰居。MOEA/D通過相鄰子問題之間的相關(guān)關(guān)系來加速其搜索，通過在目標(biāo)空間內(nèi)進(jìn)行多個方向的搜索來實現(xiàn)其多樣性。

Pareto局部搜索(PLS)可以看作是單目標(biāo)局部搜索的一個擴(kuò)展[5]，它通過一系列相互不支配的解來進(jìn)行工作。Pareto局部搜索在每一迭代中，通過搜索這些非支配解的部分或者全部的鄰居來進(jìn)一步更新這個解集。當(dāng)前，一個比較成功的PLS的變種是兩階段Pareto局部搜索(2PPLS)[5]。第一階段通過聚合方法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)，然后對這些單目標(biāo)問題利用現(xiàn)有的方法進(jìn)行求解，產(chǎn)生一組高質(zhì)量的非支配解集。第二階段再利用Pareto局部搜索對第一階段產(chǎn)生的解繼續(xù)進(jìn)行求解，往真實PF進(jìn)行推進(jìn)。最近，另外一種混合多目標(biāo)啟發(fā)式算法MOMAD[22]，其結(jié)合了Pareto局部搜索和MOEA/D分解的方法在一些多目標(biāo)組合優(yōu)化問題中取得了優(yōu)異的效果。

但是當(dāng)前的2PPLS和MOMAD以及其他現(xiàn)存的多目標(biāo)啟發(fā)式算法并不適合解決3-目標(biāo)或者3-目標(biāo)以上的超多目標(biāo)組合優(yōu)化問題(CMaOPs[23])。主要原因如下[23-24]：

(1)Pareto支配關(guān)系的效果急劇下降，這是因為隨著目標(biāo)個數(shù)的增加，解與解之間相互支配的概率會變得很低，大多數(shù)的解之間都是非支配關(guān)系。這也導(dǎo)致了一些常見的基于支配的算法在超過兩個目標(biāo)的組合優(yōu)化問題上表現(xiàn)不佳。

(2)在MOMAD中，用來近似PF的解的數(shù)量沒有很好的控制，因此極高的空間復(fù)雜度和時間復(fù)雜度限制了其在超過3個目標(biāo)上的擴(kuò)展。

2 算 法

2.1 主要框架

文中算法主要基于MOEA/D算法框架，將一個多目標(biāo)優(yōu)化問題分解為N個單目標(biāo)優(yōu)化問題，一些聚合方法(權(quán)重和法、切比雪夫方法等)可以達(dá)到這些目的。在該算法中采用權(quán)重求和方法，工作原理如下：

對于權(quán)重向量W，有W={λ1,λ2,…,λN}，其中

(2)

每一個分解后的單目標(biāo)優(yōu)化描述如下：

(3)

在權(quán)重向量W中，λl是λk的T個最近的權(quán)重向量之一，則稱λl是λk的鄰居。第l個子問題也稱為第k個子問題的鄰居。

經(jīng)過長期發(fā)展，Pareto局部搜索也有了很多的版本[22]。在這些版本和文中算法中，有一個重要的假設(shè)前提，就是在搜索空間里，通過定義正確的鄰域關(guān)系，鄰居可以通過從起始解集移動到鄰居解集迭代生成。Pareto最優(yōu)解集可以從鄰居解集中獲取。

每一次迭代中，在算法中保持兩個解集：

(1)工作集WP:WP={x1,x2,…,xN}，其中xk是迄今為止在子問題k中通過聚合方法找到的最優(yōu)解。

(2)外部集EP:外部集中的解都將進(jìn)行Pareto局部搜索。

兩個解集之間將一直進(jìn)行通信，新解可以通過基因算子從工作集中生成，也可以通過在外部集中進(jìn)行Pareto局部搜索生成。每一個新產(chǎn)生的解都有可能更新這兩個種群。用來進(jìn)行Pareto局部搜索的起始解集來自外部集，因為工作集通過基因算子生成的解可能會更新外部集，因此它可以幫助外部集跳出局部最優(yōu)點。

算法1：主框架

輸入：算法的終止條件；子問題的個數(shù)N；權(quán)重向量的集合W={λ1,λ2,…,λN}；每個子問題的鄰居大小T；一組標(biāo)記向量S={s1,s2,…,sN}

輸出：一組有效解集

/*初始化所有參數(shù)*/

/*對EP進(jìn)行局部搜索*/

/*通過WP產(chǎn)生新解*/

if滿足終止條件，停止并輸出外部集，否則轉(zhuǎn)到步驟2

2.2 初始化

在此階段，工作集和外部集被初始化。由于已經(jīng)將一個多目標(biāo)問題分解成N個子問題，對于每一個k∈{1,2,…,N}，都對應(yīng)一個λk，在每一個子問題上應(yīng)用一個單目標(biāo)啟發(fā)式方法來生成解xk，然后使用集合{x1,x2,…,xN}來初始化WP和EP。

算法2：初始化

輸入：WP,EP,S,B

輸出：WP,EP,S,B

對每一個k=1,2,…,N，在子問題k上應(yīng)用一個單目標(biāo)啟發(fā)式方法來產(chǎn)生解xk，對應(yīng)權(quán)重向量λk

初始化WP={x1,x2,…,xN}，EP=WP

對于每一個si∈S,i=1,2,…,N，將si=false

計算每兩個權(quán)重向量之間的歐氏距離，并獲得每個權(quán)重向量最近的T個權(quán)重向量。對每一個i=1,2,…,N，設(shè)置B(i)={i1,i2,…,iT}

2.3 EP(外部集)的Pareto局部搜索

對于EP中的有效解，它的鄰居也可能是有效的?；谶@種假設(shè)，對EP中解x進(jìn)行Pareto局部搜索來產(chǎn)生它的鄰居集N(x)，然后再使用N(x)來更新EP和WP。只有新加入的解才會被用來進(jìn)行下一次的搜索。

算法3：Pareto局部搜索

輸入：WP,EP,W,S,B

輸出：WP,EP,S

對每一個xi∈EP以及si∈S,i=1,2,…,N，執(zhí)行以下操作

ifsi==false，則

設(shè)置si=true

/*N(x)：解x的鄰居*/

/*通過局部搜索產(chǎn)生新解*/

對于每一個x'∈N(xi)，執(zhí)行：

設(shè)置I=B(i)

更新外部集EP(x'↓,EP,S,W↓,I↓)

ifx'已經(jīng)被加入到外部集EP

更新工作集WP(x'↓,WP,I↓)；

end

end

end

end

算法4：生成子代

輸入：WP,EP,W,S,B

輸出：WP,EP,S；

對每一個i=1,2,…,N，執(zhí)行以下操作

從B(i)中任意選擇兩個下標(biāo)k,l，然后通過基因算子從xk和xl產(chǎn)生新解yi；

令I(lǐng)=B(i)，更新外部集EP(yi↓,WP,I↓)

ifyi可以被加入WP，則

令I(lǐng)={1,2,…,N}；

更新外部集EP(yi↓,WP,S,W↓,I↓)

end

end

2.4 EP(外部集)的更新

在更新外部集EP時，輸入的解y將會有兩次比較。在第一階段，y將比較EP中的一些解，并且替換掉被y支配掉的解。如果y被其中任意一個解所支配，該過程將結(jié)束。如果y沒有被任何所選的解支配，則進(jìn)入第二階段。第二階段通過一種新的方法比較之前的解。對所有j∈I，第j個子問題對應(yīng)解xj和參考線λj。計算解y與λj之間的角度θ1以及xj與λj之間的角度θ2，如果θ1<θ2，則解y替換解xj。

外部集的更新在算法的第三步和第四步都會更新。對外部集EP中的解進(jìn)行Pareto局部搜索，每一個通過基因算子新產(chǎn)生的解x的鄰居如果能夠加入工作集WP則更新外部集EP。假設(shè)Pareto局部搜索產(chǎn)生的鄰居距離原始解很近，因此可以僅更新EP中該解的鄰居。如果解是通過基因算子產(chǎn)生的，應(yīng)該更新整個外部集。

算法5：更新外部集EP

輸入：y,EP,S,W,I；

輸出：EP,S；

對每一個xi∈EP并且i∈I，執(zhí)行以下操作

ify被xi所支配，則

return

end

ify支配xi，則

使得xi=y且si=false

end

對于每一個xj∈EP并且j∈I，執(zhí)行以下操作

θ1=angle(y,λj)

θ2=angle(xj,λj)

ifθ1<θ2，則

設(shè)置使得xi=y且si=false

end

end

2.5 WP(工作集)的更新

當(dāng)一個新解通過基因算子或者Pareto局部搜索產(chǎn)生時，也會更新工作集WP。在算法4中，解y是子問題i產(chǎn)生的新解，I是子問題i所有鄰居的索引集合。對I中的每一個k，如果解y的聚合函數(shù)值更優(yōu)，則y將會替換解xk。

算法6：更新工作集WP

輸入：y,WP,I

輸出：WP

對每一個xk∈WP(k∈I)，執(zhí)行以下：ifgws(y|λk)≤gws(xk|λk)，則

設(shè)置xk=y

end

end

3 實 驗

為了驗證提出的算法，選擇經(jīng)典的多目標(biāo)旅行商問題(mTSP)進(jìn)行對比分析。

3.1 多目標(biāo)旅行商問題(mTSP)簡介

多目標(biāo)旅行商問題(mTSP)是一個經(jīng)典的NP-難的多目標(biāo)組合優(yōu)化問題。對于一個無向圖G=(V,E)，其中V={1,2,…,N}是城市集，E={e=(i,j)|i,j∈V}是邊集。對于每一條邊e有m個距離度量指標(biāo)de,1,de,2,…,de,m。一個可行解是一個所有V元素的全排列組合，同時也是一個所有邊E的哈密頓回路。對于mTSP的第i個目標(biāo)，算法的目的是最小化以下函數(shù)：

(4)

其中，x為E的子集形成的解。

3.2 測試問題

生成了5～10目標(biāo)的測試實例，并且考慮以下三種類型的實例：

(1)歐氏距離測試集(Euclidean)：假設(shè)所有的節(jié)點分布在一個平面上，兩個城市之間的邊的成本是對應(yīng)均勻分布的；

(2)隨機(jī)測試集(random)：每條邊的成本是通過均勻分布隨機(jī)生成的；

(3)混合測試集(mixed)：這種實例是(1)和(2)的混合，一部分是歐氏實例，另一部分是隨機(jī)實例。

3.3 實驗參數(shù)設(shè)置和度量指標(biāo)

算法中工作集WP和外部集EP(N)的大小是相同的。過大的種群將會導(dǎo)致每一代都有很高的計算復(fù)雜度，過小的種群又會導(dǎo)致搜索丟失PF的一部分。基于這些考慮，N的設(shè)置如下：3目標(biāo)時設(shè)置N=300，5目標(biāo)時設(shè)置N=210，8目標(biāo)時設(shè)置N=156，10目標(biāo)時設(shè)置N=275。每一個子問題的鄰居集大小設(shè)置為20，且所有測試用例獨立運行30次。

采用最常使用的性能評估指標(biāo)：HyperVolume(IH)[25]，其值越大表示結(jié)果越好。

3.4 算法設(shè)置

(1)第一步中的工作集WP和外部集EP：因為將多目標(biāo)優(yōu)化問題分解成N個子問題，利用隨機(jī)方法來生成解xk。設(shè)置WP={x1,x2,…,xN}，以及EP=WP。

(2)解x產(chǎn)生的鄰居解集N(x)(算法3的第4行)：Pareto局部搜索的重要步驟是如何通過解x產(chǎn)生它的鄰居解集N(x)。算法中的鄰居使用了文獻(xiàn)[22]中提供的2-opt方法。

(3)工作集WP交叉變異算子：文中使用GoldBerg和Linge提出的PMX交叉和單交換變異來產(chǎn)生新解。因為在很多問題上PMX交叉算子[26]比其他交叉算子的效果更好。

3.5 比較算法

由于在目標(biāo)個數(shù)上升到3或者更多的時候，現(xiàn)有算法如MOMAD等無法解決該類超多目標(biāo)問題。因此，在3～10個目標(biāo)的mTSP問題中，使用MOEA/D算法進(jìn)行比較。對于這兩種算法，同樣的PMX交叉和單交換變異策略被用來產(chǎn)生新解。由于這兩種算法只保持一個種群并且使用基因算子來產(chǎn)生新解，因此添加了Pareto局部搜索到原始的MOEA/D算法中作為一個補充，來實現(xiàn)公平的比較，命名為MOEA/D(PLS)。

實驗中，這些算法都是基于C++編碼，并且使用了同樣的CPU時間，所有的實驗都是基于一臺Intel 2.6 GHz，8 GB內(nèi)存的PC實現(xiàn)。

3.6 實驗結(jié)果

實驗比較了在相同運行時間下HyperVolume在不同問題實例下的值。從表1可以看出，DPPLS的性能要好于其余兩種比較算法。DPPLS作為MOEA/D算法框架的一個拓展，其在超多目標(biāo)上的效果要好于MOEA/D本身。此外，使用Pareto局部搜索策略的MOEA/D算法效果也要優(yōu)于通過普通的交叉變異生成解的方式。

表1 MOEA/D-PLS和MOEA/D在測試問題上HyperVolume的比較

4 結(jié)束語

針對現(xiàn)有的多目標(biāo)組合優(yōu)化算法無法較好地解決目標(biāo)數(shù)大于3的超多目標(biāo)組合優(yōu)化問題，提出了一種多目標(biāo)組合優(yōu)化算法。在基于MOEA/D算法的框架下，利用兩個種群，其中一個作為工作集來運作MOEA/D，另一個用于進(jìn)行Pareto局部搜索。實驗結(jié)果表明，該算法相比較MOEA/D而言，在超多目標(biāo)問題上具有很好的效果。