基于MOEA/D算法求解最小加權(quán)頂點覆蓋問題

馬洪玲，馬 璐

(天津工業(yè)大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院，天津 300387)

組合優(yōu)化問題是指在某些約束條件下，尋找目標(biāo)函數(shù)的最優(yōu)解.典型的組合優(yōu)化問題有旅行商問題、生產(chǎn)調(diào)度問題、頂點覆蓋問題等[1].

近年來，很多學(xué)者對頂點覆蓋問題進(jìn)行大量的研究，其中研究比較多的是單目標(biāo)最小加權(quán)頂點覆蓋(Minimum Weighted Vertex Cover, MWVC)問題.針對解決單目標(biāo)MWVC問題的方法主要分為兩類：1)集中優(yōu)化方法，該方法根據(jù)全局信息控制算法進(jìn)化過程，具有代表性的有IH-R、QIPSO-R算法[2]、ACO算法[3]、PBIG算法[4]等.集中優(yōu)化需要用到全局信息，隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大，集中優(yōu)化算法往往需要花費很長的時間.2)分布式優(yōu)化方法，該方法只利用局部信息，依賴鄰居找到最優(yōu)解, 具有代表性的有FastWVC算法[5]、NuMWVC算法[6]、RGMA算法[7]、FBR算法[8]等，相比于集中優(yōu)化方法，分布式優(yōu)化方法在MWVC問題尋找解的速度上有了很大的提高.MWVC問題在調(diào)度問題、集成電路[9]等領(lǐng)域都有著重要作用.

但是在實際問題中，通常存在多個目標(biāo)、指標(biāo)相關(guān)聯(lián)的問題，這時需要將多個目標(biāo)函數(shù)同時優(yōu)化.經(jīng)典的多目標(biāo)優(yōu)化算法有NSGA2[10]、MOEA/D[11].目前求解多目標(biāo)最小加權(quán)頂點覆蓋(Multi-objective Minimum Weighted Vertex Cover，MMWVC)問題的研究還比較少.文獻(xiàn)[12]提出求解MMWVC問題的MOSND算法,該算法是在MOEA/D的基礎(chǔ)上利用分解技術(shù)和迭代領(lǐng)域搜索尋找最優(yōu)解.MMWVC問題是MWVC問題的一個重要變形.

針對MMWVC問題，本文提出一種基于分解的多目標(biāo)進(jìn)化算法.該算法首先利用雪堆博弈的優(yōu)勢初始化種群形成初始解，然后在局部搜索階段設(shè)計一種自適應(yīng)搜索策略與三種操作算子結(jié)合改進(jìn)初始解，最后將其應(yīng)用在基準(zhǔn)實例上，驗證算法的有效性.

1 問題模型

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

多目標(biāo)優(yōu)化問題(Multi-objective Optimization Problem, MOP)[13]是在給定的決策空間內(nèi)，盡可能找到滿足約束條件的最優(yōu)解集，為解決MOP的決策者提供數(shù)據(jù).MOP的數(shù)學(xué)模型如公式(1)所示.

(1)

其中：x=(x1,x2,…,xn)T表示n維決策空間的一個向量，m表示目標(biāo)函數(shù)的個數(shù)，Ω表示決策空間，fi(x)表示多目標(biāo)優(yōu)化問題的目標(biāo)函數(shù).

1.2 多目標(biāo)最小加權(quán)頂點覆蓋問題

給定一個無向加權(quán)圖G=(V,E,W),其中頂點集合表示為V={1,2,…,N}，邊集合表示為E={eij}，每條邊e={(i,j),?i,j∈V}是V的2元組，且i和j都稱為e的端點，權(quán)重集合表示為W={w1,w2,…,wN}(其中wi是頂點的權(quán)重).下面給出一些相關(guān)定義：

定義1(頂點覆蓋)：頂點覆蓋是頂點VVC∈V的子集，對于任何的邊eij∈E，都有i∈VVC或j∈VVc，換句話說，eij的至少一個端點(i或j)包含在VVC中.

定義2(最小加權(quán)頂點覆蓋)：MWVC是找到子集VVC∈V，使得VVC中頂點權(quán)重之和最小.

定義3(多目標(biāo)最小加權(quán)頂點覆蓋)： MMWVC定義如公式(2)所示.

(2)

如果v在頂點覆蓋集中，則Sv=1，否則Sv=0.對于MMWVC問題，每個頂點對應(yīng)m個權(quán)重，有m個目標(biāo)需要優(yōu)化.本文m=2，即研究雙目標(biāo)MWVC問題，雙目標(biāo)MWVC問題是MMWVC問題的一個特例.

2 本文提出的算法

2.1算法框架

本文提出一種求解雙目標(biāo)MWVC問題的B0-MWVC(Bio-objective Minimum Weighted Vertex Cover)算法，該算法包括2個階段：初始化和局部搜索.BO-MWVC算法的總體描述如下.

輸入：

G:加權(quán)網(wǎng)絡(luò)圖；Pop:種群大小;Itermax:最大迭代次數(shù)

輸出：

Pset：非支配解

Step1 初始化：

Step1.1)生成初始權(quán)重向量λ={λ1,λ2,…,λm}.

Step1.2)通過雪堆博弈產(chǎn)生初始解S,然后生成初始種群P={S1,S2,…,SPop}.

Step2 局部搜索：

Step2.1)計算頂點的Eedge,Weight,EWscore值.

Step2.2)通過自適應(yīng)搜索對頂點進(jìn)行刪除、交換、添加.

Step2.3)更新解：如果g(S′|λS′)>g(S|λS)，則S′←S.

Step2.4)更新Pset.

Step3 停止條件：

如果達(dá)到Itermax，則停止并輸出Pset.否則，執(zhí)行Step2.

2.2 多目標(biāo)分解策略

在給定參考點信息或者權(quán)重偏好的情況下，分解方法通過非線性或者線性方式將原多目標(biāo)問題進(jìn)行分解，得到單目標(biāo)優(yōu)化問題，進(jìn)而求Pareto最優(yōu)解[14].本文使用權(quán)重聚合方法[10]將MOP分解為單目標(biāo)優(yōu)化問題，目標(biāo)函數(shù)聚合形式如式(3)所示.

(3)

2.3 初始化種群

本文利用異步更新規(guī)則下雪堆博弈形成初始種群[15].雪堆博弈描述如下：雪堆博弈是指在一個下雪的晚上,兩輛車被困在一個雪堆的兩側(cè).假設(shè)道路通暢則每個司機(jī)的收益為b，道路不通暢鏟除雪堆需要的代價為c，每個司機(jī)都有兩種可選擇的策略1)合作(C)、2)背叛(D);鏟雪代表司機(jī)選擇合作策略，不鏟雪代表司機(jī)選擇背叛策略.如果兩個司機(jī)都選擇合作,則他們的收益為b-c/2；如果一個司機(jī)選擇合作，另一個選擇背叛，則選擇合作的司機(jī)收益為b-c，選擇背叛的司機(jī)收益為b；如果兩司機(jī)都選擇背叛，則他們的收益為0.在不失一般性的情況下，b-c/2將標(biāo)準(zhǔn)化為1，則雪堆博弈收益比r=c/(2b-c)(0

CDC11-rD1+r0

異步更新規(guī)則是指網(wǎng)絡(luò)中所有頂點按順序依次進(jìn)行博弈并更新自身策略[16].納什均衡是指博弈參與者都不能通過改變當(dāng)前的策略使得自身收益增加所達(dá)到的平衡狀態(tài).文獻(xiàn)[17]提出當(dāng)r·Kmax<1(Kmax是頂點的最大度值)時，網(wǎng)絡(luò)進(jìn)行異步更新規(guī)則下雪堆博弈一定能達(dá)到納什均衡狀態(tài)，并且納什均衡狀態(tài)是一個頂點覆蓋集合.

2.4 局部搜索

2.4.1 評分函數(shù)

邊函數(shù)Eedge用來評估頂點覆蓋邊的變化.當(dāng)頂點在解中時，number1為刪除該頂點未覆蓋邊的數(shù)量；當(dāng)頂點未在解中時，number2為添加該頂點未覆蓋邊的數(shù)量.Eedge定義如式(4)所示.

(4)

權(quán)重函數(shù)Weight用來計算頂點權(quán)重值，當(dāng)λ固定時，頂點的權(quán)重就是確定值.在局部搜索階段，選擇Weight值小的頂點添加到解中，選擇Weight值大的頂點從解中刪除.Weight定義如式(5)所示.

(5)

邊函數(shù)側(cè)重用更少的頂點優(yōu)化解，權(quán)重函數(shù)側(cè)重用更小的權(quán)重優(yōu)化解，基于這兩個函數(shù)的特點，本文定義一種同時考慮邊和權(quán)重的評分函數(shù)EWscore優(yōu)化解.為了更好的優(yōu)化目標(biāo)值，選擇EWscore值大的頂點添加到解中，選擇EWscore值小的頂點從解中刪除.EWscore定義如式(6)所示.

(6)

2.4.2 操作算子

刪除操作(delete)：刪除操作是刪除解中多余的頂點，使得目標(biāo)值變小.根據(jù)之前的介紹，可以知道EWscore為0的頂點是多余頂點，如果存在多個EWscore為0的頂點，選擇Weight值較大的頂點刪除.

添加操作(add)：添加操作是從未在解中的頂點里選擇一個頂點添加到解中，目的是為了增加搜索的多樣性.

交換操作(swap)：交換操作是將在解中的頂點和未在解中的頂點進(jìn)行交換，即刪除一個頂點后再添加一個頂點，交換頂點后的解要保證仍然是一個可行解.交換的目的是讓目標(biāo)值變小，所以在選擇頂點時要滿足Weight(u)-Weight(z)>0，其中u是刪除的頂點，z是添加的頂點.

2.4.3 自適應(yīng)局部搜索

本文提出一種自適應(yīng)的方式進(jìn)行局部搜索.首先，計算每個頂點的三個評分函數(shù)值，然后對頂點進(jìn)行刪除、交換和添加操作，隨著迭代的增加，如果連續(xù)Nobettermax次找不到更好的解，則自適應(yīng)搜索次數(shù)Sa減1.自適應(yīng)局部搜索算法如算法1所示.

算法1 自適應(yīng)局部搜索

輸入 初始解S

輸出 最終解S′

1.For each vertex v do

2. CalculateEedge(v),Weight(v),EWscore(v)

3.S′←S,Nobetter=0

4.ForLocals=0 toLocalsmax

5. ifNobetter≥Nobettermax&&Sa≥2

6.Sa--1

7. else

8. for i=1 toSa

9. delete or swap or add

10. ifg(S′|λS′)>g(S|λS)

11.S′←S

12. else

13.Nobetter++

14. end for

15. end for

圖1展示了局部搜索的操作過程.實例為8個頂點和9條邊的無向圖，每個頂點對應(yīng)一個三元組(Eedge(v),Weight(v),EWscore(v))，圖1中黑色頂點表示在頂點覆蓋集合中，白色頂點表示不在頂點覆蓋集合中.圖1(A)為雪堆博弈生成的初始解；圖1(B)～(D)為依次進(jìn)行交換、添加和刪除操作，最后生成最終解f(S)=110.

圖1 局部搜索過程Figure 1 Local search process

3 性能評估

3.1 基準(zhǔn)實例

本文選用文獻(xiàn)[3]中的測試實例，該實例已被廣泛用于MWVC問題.每個實例有N個頂點和M條邊，每個頂點有兩個權(quán)重，權(quán)重在[1,120]之間隨機(jī)生成.BO-MWVC算法采用C++語言編寫，實驗是在具有 2.30 GHz CPU 的計算機(jī)上進(jìn)行.

3.2 參數(shù)設(shè)置

BO-MWVC算法參數(shù)設(shè)置如下：迭代次數(shù)Itermax=100；雪堆博弈收益比r=0.000 2，自適應(yīng)搜索次數(shù)Sa=4，種群規(guī)模Pop=50，局部搜索次數(shù)Localsmax=100.

3.3 對比算法

本文將提出的BO-MWVC算法與MONSD[12]、NSGA2[10]算法對比以驗證提出的BO-MWVC算法的有效性.MONSD算法是將迭代領(lǐng)域搜索與分解技術(shù)相結(jié)合的多目標(biāo)算法，為了更好的求解問題，設(shè)計了混合打分函數(shù)用于初始化和領(lǐng)域搜索.NSGA2算法是帶有精英保留策略的快速非支配多目標(biāo)優(yōu)化算法，該算法已廣泛用于求解多目標(biāo)問題.

3.4 評價指標(biāo)

本文采用超體積指標(biāo)(HV)[18]作為衡量指標(biāo)，該指標(biāo)可以同時評價算法的多樣性和收斂性.HV表示的是算法獲得的非支配解集和參考點圍成的區(qū)域體積，如果解集A比解集B好，那么解集A的HV大于解集B的HV.在計算HV之前首先要對非支配解集作歸一化處理，歸一化處理方式如式(7)所示，HV計算方法如式(8)所示.

(7)

(8)

其中:mPF表示非支配解集的個數(shù)，fii表示參考點與非支配解集里第i個解圍成的超體積，參考點取(1.2,1.2).

3.5 Pareto前沿面分布情況

Pareto前沿面可以直觀的反映出解的分布情況.本文從三種不同規(guī)模實例中各選兩個實例進(jìn)行展示，因本文求解的是最小化問題，所以分布曲線越靠近左下部分越好.從圖2可以看出兩個目標(biāo)權(quán)重和是互斥的，符合 MOP的特點，同時BO-MWVC要比MONSD和NSGA2獲得更好的Pareto前沿面.

圖2 Pareto前沿面分布曲線Figure 2 Pareto front distribution curve

3.6 綜合試驗結(jié)果

表1～3為3種算法在不同規(guī)模的基準(zhǔn)實例上HV指標(biāo)的對比結(jié)果，粗體為較好的解.可以看出，B0-MWVC算法在所有實例中都得到了比另外兩種算法好的HV值.HV指標(biāo)可以同時評價算法的多樣性和收斂性，因此，B0-MWVC算法的多樣性和收斂性要優(yōu)于MONSD算法和NSGA2算法.

表1 在小規(guī)模實例上HV指標(biāo)的對比結(jié)果Table 1 Comparison of HV metrics on small-scale instances

續(xù)表1

表2 在中等規(guī)模實例上HV指標(biāo)的對比結(jié)果Table 2 Comparison of HV metrics on medium-scale instances

表3 在大規(guī)模實例上HV指標(biāo)的對比結(jié)果Table 3 Comparison of HV metrics on large-scale instances

4 結(jié) 語

本文以頂點的兩個權(quán)重為雙重優(yōu)化目標(biāo)，建立了最小加權(quán)頂點覆蓋問題多目標(biāo)優(yōu)化模型.針對多目標(biāo)最小加權(quán)頂點覆蓋問題，提出了B0-MWVC算法.該算法利用分解策略將多目標(biāo)問題分解為單目標(biāo)問題，采用雪堆博弈生成初始種群，并在局部搜索中引入自適應(yīng)策略和三個操作算子提高算法效率.實驗結(jié)果表明，B0-MWVC在Pareto前沿面、HV性能指標(biāo)上要優(yōu)于MONSD和NSGA2.