基于雙種群的Pareto局部搜索算法

汪 欣，夏 超

(南京航空航天大學 計算機科學與技術學院，江蘇 南京 211100)

0 引 言

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

1 概 述

1.1 多目標優化問題定義

一個多目標優化問題(MOP)的定義如下：

(1)

其中，Ω是決策空間；F:Ω→Rm是由m個實值目標函數組成的目標空間?？尚心繕擞驗閧F(x)|x∈Ω}。當Ω為離散集合時，式1被稱作一個多目標組合優化問題。

1.2 支配關系描述

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

1.3 多目標組合優化問題

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

1.4 進化算法背景

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

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

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

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

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

2 算 法

2.1 主要框架

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

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

(2)

每一個分解后的單目標優化描述如下：

(3)

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

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

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

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

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

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

算法1：主框架

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

輸出：一組有效解集

/*初始化所有參數*/

/*對EP進行局部搜索*/

/*通過WP產生新解*/

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

2.2 初始化

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

算法2：初始化

輸入：WP,EP,S,B

輸出：WP,EP,S,B

對每一個k=1,2,…,N，在子問題k上應用一個單目標啟發式方法來產生解xk，對應權重向量λk

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

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

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

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

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

算法3：Pareto局部搜索

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

輸出：WP,EP,S

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

ifsi==false，則

設置si=true

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

/*通過局部搜索產生新解*/

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

設置I=B(i)

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

ifx'已經被加入到外部集EP

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

end

end

end

end

算法4：生成子代

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

輸出：WP,EP,S；

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

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

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

ifyi可以被加入WP，則

令I={1,2,…,N}；

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

end

end

2.4 EP(外部集)的更新

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

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

算法5：更新外部集EP

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

輸出：EP,S；

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

ify被xi所支配，則

return

end

ify支配xi，則

使得xi=y且si=false

end

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

θ1=angle(y,λj)

θ2=angle(xj,λj)

ifθ1<θ2，則

設置使得xi=y且si=false

end

end

2.5 WP(工作集)的更新

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

算法6：更新工作集WP

輸入：y,WP,I

輸出：WP

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

設置xk=y

end

end

3 實 驗

為了驗證提出的算法，選擇經典的多目標旅行商問題(mTSP)進行對比分析。

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

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

(4)

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

3.2 測試問題

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

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

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

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

3.3 實驗參數設置和度量指標

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

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

3.4 算法設置

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

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

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

3.5 比較算法

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

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

3.6 實驗結果

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

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

4 結束語

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