自適應memetic算法求解集合覆蓋問題

林　耿， 關　健

(1.閩江學院 數(shù)學系，福建 福州 350108； 2. 閩江學院 現(xiàn)代教育技術中心, 福建 福州 350108)

?

自適應memetic算法求解集合覆蓋問題

林耿1， 關健2

(1.閩江學院 數(shù)學系，福建 福州 350108； 2. 閩江學院 現(xiàn)代教育技術中心, 福建 福州 350108)

摘要：集合覆蓋問題是一個經(jīng)典的NP困難的組合優(yōu)化問題，有著廣泛的應用背景.首先，采用動態(tài)罰函數(shù)法將集合覆蓋問題等價轉(zhuǎn)化為無約束的0-1規(guī)劃問題.然后，基于集合覆蓋問題的結構特征，設計了初始種群構造方法、局部搜索方法、交叉算子、動態(tài)變異算子和路徑重連策略，提出了一個高效求解該0-1規(guī)劃問題的自適應memetic算法.該算法有效平衡了集中搜索和多樣化搜索.通過45個標準例子測試該算法，并將其結果與現(xiàn)有遺傳算法進行了比較，表明該算法能夠在可接受的時間內(nèi)找到高質(zhì)量的解，能夠有效求解大規(guī)模集合覆蓋問題.

關鍵詞：集合覆蓋問題；memetic算法；罰函數(shù)；局部搜索；路徑重連

LIN Geng1, GUAN Jian2

(1.DepartmentofMathematics,MinjiangUniversity,Fuzhou350108,China; 2.ModernEducationalTechnologyCenter,MinjiangUniversity,Fuzhou350108,China)

0引言

集合覆蓋問題(set covering problem)是一個經(jīng)典的組合優(yōu)化問題.它是NP困難問題[1]，并且在通訊工業(yè)、后勤保障、市場銷售、計算生物學等領域應用廣泛.

集合覆蓋問題理論的重要性和應用的廣泛性，引起了學者們的廣泛關注,其算法大致可以分為精確算法、近似算法和啟發(fā)式算法.精確算法主要基于branch-and-bound算法和branch-and-cut算法[2-3].雖然精確算法能夠找到集合覆蓋問題的最優(yōu)解，近似算法[4-5]能夠找到有質(zhì)量保證的解，但是它們的求解速度都比較慢，只能求解較小規(guī)模的實例[6].

啟發(fā)式算法因其能夠較快地找到問題的高質(zhì)量解，成為學者們研究的熱點[6-11].BEASLEY等[7]提出了求解集合覆蓋問題的遺傳算法.吳志勇等[8]提出了一個二階段遺傳算法，該算法首先對實例進行有效約簡，縮小問題的規(guī)模，然后，通過遺傳算法求得一個高質(zhì)量的近似解.45個標準試例的測試結果表明，該算法的求解效率和求解質(zhì)量高于其他遺傳算法.蔣建林等[9]提出了一種改進的遺傳算法.這些遺傳算法求解質(zhì)量較高，但由于集中搜索能力(intensification)較弱，當種群數(shù)量較大時，算法的收斂速度較慢，求解消耗的時間較長.

Memetic算法是基于種群的全局搜索和基于個體的局部搜索的結合體，已被成功應用于求解各種高難度的優(yōu)化問題.本文根據(jù)集合覆蓋問題的特點，提出了一種自適應的memetic算法.該memetic算法通過迭代改進的局部搜索算法和路徑重連策略，有效提高了算法搜索的集中能力；通過動態(tài)變異算子，提高了算法搜索的多樣性.這些策略有效平衡了算法的集中搜索和多樣性搜索能力.采用45個國際標準測試例子測試本文算法，并與現(xiàn)有遺傳算法進行比較，以證明本算法的高效性.

1問題描述

給定一個m行n列的0-1矩陣A=(aij)m×n和列的費用cj，其中aij=1表示第i行被第j列覆蓋，aij=0表示第i行未被第j列覆蓋，集合覆蓋問題尋找一個費用總和最小的列的集合D，使得所有行都至少被D中的一列覆蓋.引入n維0-1向量x=(x1,…,xn)，如果第j列被選入集合D，則xj=1；否則，xj=0.則集合覆蓋問題可以描述為以下0-1規(guī)劃問題[6,8,10](P)：

xj∈{0,1},j=1,2,…,n.

2集合覆蓋問題的動態(tài)罰函數(shù)及性質(zhì)

2.1動態(tài)罰函數(shù)的構造

采用精確罰函數(shù)法，問題(P)可以轉(zhuǎn)化為如下的無約束0-1規(guī)劃問題(EUP)：

minf(x)+λα(x),

s.t. xj∈{0,1},j=1,2,…,n,

其中λ>0為罰參數(shù).精確罰函數(shù)法形式簡單，但是罰參數(shù)λ比較敏感，并且難以選擇合適的值.

為了解決罰參數(shù)難以選擇的問題，近年來，學者們提出了無參數(shù)罰函數(shù)法、自適應罰函數(shù)法等.針對帶約束的連續(xù)優(yōu)化問題，ALI等[12]提出了自適應動態(tài)罰函數(shù)法，此方法有效降低了罰參數(shù)對實例的敏感程度.基于集合覆蓋問題的特點，構造如下動態(tài)罰函數(shù)：

其中，μ>0是罰參數(shù)，U是問題(P)的上界.U的初始值可以通過貪心算法等求得.在搜索過程中，如果找到更好的可行解，則更新U.

基于以上的動態(tài)罰函數(shù)，構造如下無約束0-1規(guī)劃問題(DUP)：

minφ(x)，s.t. xj∈{0,1}, j=1,2,…,n.

2.2動態(tài)罰函數(shù)的性質(zhì)

定理1當μ>cmax=max{cj,j∈{1,2，…,n}}時，問題(P)和(DUP)具有相同的全局最優(yōu)解.

證明假設x*是問題(P)的全局最優(yōu)解，則對?x∈S，有f(x)≥f(x*).對于?x∈{0,1}n，考慮以下2種情況：x∈S和x?S.當x∈S時，有

φ(x)=f(x)≥f(x*)=φ(x*)；

(1)

當x?S時，無論f(x)≤U或是f(x)>U，由φ(x)的定義都有φ(x)>f(x)，所以

φ(x)>f(x)≥f(x*)=φ(x*).

(2)

由式(1)與(2)得x*是問題(DUP)的全局最優(yōu)解.

假設x*是問題(DUP)的全局最優(yōu)解，則對?x∈{0,1}n，有φ(x)≥φ(x*).由于μ>cmax，則必有x*∈S.由φ(x)的定義得：對于?x∈S，f(x)=φ(x)≥φ(x*)=f(x*)，即x*也是問題(P)的全局最優(yōu)解.

由定理1可知，可以通過求解無約束的問題(DUP)來找到原問題的全局最優(yōu)解.本文的基本思想是通過memetic算法求解問題(DUP)，以期找到原問題高質(zhì)量的解.該memetic算法采用如下的1變換鄰域結構：

(3)

定理2當μ>cmax時，問題(DUP)的局部最優(yōu)解必然是問題(P)的可行解.

證明假設y是問題(DUP)的局部最優(yōu)解，則對?x∈N(y)，有

φ(x)≥φ(y).

(4)

如果y?S，則α(y)>0.故至少存在一個未選的列j，使得將該列選入后，未覆蓋的行數(shù)會減少，即令yj=1后，得到新的解y′滿足α(y)>α(y′).顯然，y′∈N(y).又由于μ>cmax，有φ(y)>φ(y′)，與式(4)矛盾.故y∈S.

3自適應memetic算法

本文的基本思想是通過自適應memetic算法求解無約束問題(DUP)來得到問題(P)的高質(zhì)量的解.下面首先介紹memetic算法的幾個主要組成部分，然后給出算法的詳細步驟.

3.1初始種群的生成

初始種群P={x1,x2,…,xp}的構造對memetic算法的性能有很大的影響.本文采用隨機貪心自適應方法來構造質(zhì)量高、多樣性好的初始種群.設D表示選中的列的集合，M表示未被選中的列的集合，算法的具體步驟如下：

算法1：

步驟1初始化D=φ，M={1,2，…,n}，xj=0,j=1,2，…,n.

步驟2記hj表示將第j列加入D后，新覆蓋的行的數(shù)量.M中列j的性價比Q(j)定義為：

(5)

按照式(5)計算出M中列j的性價比Q(j).

步驟3構造候選列的集合RCL={j∈M:Qmax≥Q(j)≥δ Qmax}，其中1>δ>0為參數(shù)，用于平衡隨機性和貪婪性.

步驟4從RCL中隨機選擇一列j′放入D，令M=M-{j′}，xj′=1.

步驟5如果α(x)=0，停止，輸出x；否則，轉(zhuǎn)步驟2.

重復運行以上算法p次得到初始種群.

3.2局部搜索算法

文獻[7-8]中的遺傳算法由于缺乏局部搜索，使得算法的收斂速度較慢.針對劃分問題，F(xiàn)IDUCCIA等[13]提出了一種高效的迭代改進搜索算法(FM)，該算法的變形已經(jīng)應用于求解許多劃分問題.本文采用改進的FM算法作為局部搜索算法(記為SCPFM)，有效提高了算法的搜索效率.

該局部搜索算法SCPFM由一系列pass組成.假設x0為初始解.在每個pass的初始階段，所有變量都能夠自由翻轉(zhuǎn)(即由xj變?yōu)?-xj).假設gain(j)表示翻轉(zhuǎn)變量xj后的增益，即：

gain(j)=φ(x)-φ(x′)，

(6)

其中x′=(x1,x2,…,xj-1,1-xj,xj+1,…,xn).SCPFM根據(jù)式(6)計算出所有能夠自由翻轉(zhuǎn)的變量的增益，并找出增益最大的變量(最大增益可能大于0，也可能小于0).為了增加局部搜索的多樣性，SCPFM以0.8的概率翻轉(zhuǎn)增益最大的變量.變量被翻轉(zhuǎn)后，就鎖定該變量，即在當前的pass中禁止該變量再翻轉(zhuǎn).更新自由變量的增益.記xb是該pass中到目前為止找到的最好的解.重復以上步驟，直到φ(x)-φ(xb)>ξ時，該pass停止，其中φ(x)為當前解的目標函數(shù)值，ξ>0為參數(shù).因為當ξ比較大時，在該pass中，繼續(xù)翻轉(zhuǎn)自由變量，將無法找到比xb更好的解.接下來的pass以xb作為初始解.重復以上迭代，直到無法得到改進解為止．設F表示自由變量的集合，SCPFM算法的具體步驟如下：

算法2：

步驟1初始化x=x0，xb=x0，F(xiàn)={1,2，…,n}.

步驟2根據(jù)式(6)計算所有自由變量的增益．令F′=F.

步驟3令xj=argmax{gain(i),i∈F′}，隨機產(chǎn)生σ∈(0,1)，若σ≤0.8，概率將xj翻轉(zhuǎn)，即令xj=1-xj；否則，F(xiàn)′=F′-{j}，重復步驟3.

步驟4鎖定xj，即F=F-{j}.如果φ(x)<φ(xb)，令xb=x.

步驟5如果φ(x)-φ(xb)>ξ，轉(zhuǎn)步驟6；否則，轉(zhuǎn)步驟2.

步驟6如果φ(xb)<φ(x0)，令x0=xb，轉(zhuǎn)步驟1；否則局部搜索算法停止，輸出xb.

局部搜索算法SCPFM主要有2個操作：計算自由變量的增益和尋找具有最大增益的自由變量.在每個pass的初始階段，由式(6)計算增益，需要算出f(x)和α(x).計算f(x)和α(x)分別需要O(n)、O(mn)時間.故計算所有自由變量的增益需要O(mn)時間.本文采用桶的數(shù)據(jù)結構[13]能夠在O(1)時間內(nèi)找到具有最大增益的自由變量.在一個pass中，每個變量至多翻轉(zhuǎn)一次，所以一個pass的時間復雜度為O(mn2).

由于SCPFM通過調(diào)整參數(shù)ξ的值來提前停止pass，在一個pass中只有少數(shù)變量能夠翻轉(zhuǎn)，即一個pass的復雜度降低為O(mn).并且實驗表明，SCPFM一般都只含有很少的pass.所以在實際求解中，SCPFM的搜索速度非?？?

3.3交叉算子與變異算子

為了提高搜索的多樣性，根據(jù)集合覆蓋問題的特點，引入動態(tài)變異算子，對解進行變異.假設解x選中列的集合為D，變異算子隨機從D中選擇mu個列刪除.mu是控制變異程度的參數(shù)，在搜索過程中，隨當前解的質(zhì)量動態(tài)變化，詳細情況將在3.5節(jié)中介紹.

3.4路徑重連策略

路徑重連是通過建立當前解與導向解之間的連接路徑，從中獲得新解的一種有效的啟發(fā)式搜索策略.本文采用路徑重連來加強memetic算法的搜索能力.

本文的路徑重連以當前最好的解x*作為導向解.首先建立當前解x與x*之間的差異集合

(7)

以往的路徑重連策略按照某種規(guī)則，每次從Δ中選擇1個變量進行翻轉(zhuǎn)，直到發(fā)現(xiàn)更好的解或到達導向解(Δ=?).為了更加有效地對x*附近的解進行搜索，本文的路徑重連首先考慮從{1,2，…,n}中找出增益最大的變量xj，如果翻轉(zhuǎn)xj，能夠得到比x*更好的解，則翻轉(zhuǎn)xj；否則，從Δ中選擇增益最大的變量xt進行翻轉(zhuǎn).路徑重連策略的具體步驟如下：

算法3：

步驟1根據(jù)式(7)得到差異集Δ.

步驟2由式(6)算出所有變量的增益.設xj=argmax{gain(i),i∈{1,2，…，n}}，z=(x1,x2,…,xj-1,1-xj,xj+1,…,xn)，如果φ(z)<φ(x*)，停止，輸出z；否則，設

xt=argmax{gain(i),i∈Δ}，令xt=1-xt.

步驟3令Δ=Δ-{t}，如果Δ≠φ，轉(zhuǎn)步驟2；否則，停止，輸出x*.

3.5自適應memetic算法的步驟

求解集合覆蓋問題的自適應memetic算法的流程如圖1所示，其基本思想如下：首先通過算法1構造具有良好多樣性的初始種群P={x1,x2,…,xp}，并用SCPFM算法對種群中的解進一步優(yōu)化.種群P中質(zhì)量最好的解記為x*，令U=f(x*).其次，memetic算法通過2種方式產(chǎn)生新解.第1種，從P中任意選擇2個解xs,xt，應用交叉算子產(chǎn)生解z，再通過變異，得到的解仍記為z；第2種，從P中任意選擇1個解xs進行變異,得到新解z.最后，利用SCPFM算法對z進行優(yōu)化，采用算法3將優(yōu)化得到的解與x*做路徑重連，如果找到比x*更好的解，則更新x*和U.重復以上步驟，至達到最大迭代步數(shù)，輸出x*.

圖1　自適應memetic算法流程圖Fig.1　Flowchart of the adaptive memetic algorithm

mu是變異算子中控制變異程度的參數(shù).在搜索的早期，為了快速提高種群解的質(zhì)量，mu的取值應該較小.隨著搜索的深入，種群的多樣性變差，應當增加mu，開拓新的搜索空間.記xi∈P,i=1,2，…,p的變異參數(shù)分別為mu(i),i=1,2,…,p.設最小變異值為min_mu，最大變異值為max_mu，即min_mu≤mu(i)≤max_mu.初始化mu(i)=min_mu，如果通過變異和局部搜索后，得到的解比xi差，則需要增大變異參數(shù)，令mu(i)=mu(i)+1.如果在搜索的過程中，mu(i)超過所允許的最大變異值max_mu，則令mu(i)=min_mu.

假設算法的最大迭代次數(shù)為G，自適應memetic算法的步驟如下：

算法4:

步驟1算法1運行p次，構造初始種群P={x1,x2,…,xp}.運用SCPFM算法(算法2)分別對種群P中的解進行優(yōu)化，所得解仍記為xi,i=1,2,…,p.令x*=argmin{f(xi), xi∈P}, U=f(x*)，generation=1.初始化mu(i)=min_mu，i=1,2,…,p，P′=φ.

步驟2令k=1.

步驟4如果0.5ma_mu，令mu′(k)=min_mu.

步驟5如果φ(z)<φ(x*)且α(z)=0，則x*=z，U=f(z)，mu′(k)=min_mu.

步驟6P′=P′∪{z}，采用算法3將z與x*做路徑重連，如果找到比x*好的解，更新x*和U.

步驟7如果k=p，mu(i)=mu′(i)，i=1,2,…,p，P=P′,P′=φ,轉(zhuǎn)步驟8；否則，k=k+1，轉(zhuǎn)步驟3.

步驟8令generation=generation+1，如果generation

4實驗結果及分析

為了檢驗自適應memetic算法的性能，用c語言對自適應memetic算法進行編程.本算法的運行環(huán)境為Windows7，CPU3.4GHz，內(nèi)存4GB.

采用OR-Library中的45個國際標準測試例子測試本文提出的算法.這些例子已廣泛用于對集合覆蓋問題相關算法的測試.

根據(jù)前期實驗，算法的參數(shù)設置如下：種群規(guī)模p=10，μ的值為x*中選中列的權總和的平均值，δ=0.8，ξ=3，min_mu=3，min_mu的值為x*中選中列的數(shù)量的3/4，G=800.

利用本文提出的自適應memetic算法求解45個標準測試例子，每個例子求解10次.表1展示了10次實驗獲得的最好解(Best)、平均解(Avg)以及找到最好解時所用的平均時間(Time)(單位：s).為便于結果的比較分析，將遺傳算法[7]、二階段遺傳算法[8]的計算結果(目標函數(shù)值C和運行時間Time)也列于表1中.遺傳算法、二階段遺傳算法的計算結果引自文獻[8].

對比表1的結果可以看出：(1)在45個測試例子中，遺傳算法、二階段遺傳算法和本文算法分別在6，44，44個例子中找到了最優(yōu)解.在34個例子中，本文得到的平均解優(yōu)于遺傳算法.(2)從算法的求解時間看，全部例子均表明本文算法的求解時間明顯低于遺傳算法和二階段遺傳算法.遺傳算法、二階段遺傳算法和本文算法求解的平均時間分別為1332.492，194.561和64.886 s.遺傳算法、二階段遺傳算法是在CPU 3.4 GHz,2 GB內(nèi)存的電腦上運行的，運行的環(huán)境與本文算法相當.

以上結果表明，本文算法優(yōu)于遺傳算法，能夠在較短時間內(nèi)找到與二階段遺傳算法可比擬的結果，大大提高了求解速度.

采用例子4.1，4.2，4.3，4.4，4.5，B1、B2、B3、B4、B5、D1、D2、D3、D4、D5、cyc06、cyc07測試改進遺傳算法[9]的性能，實驗結果表明，除4.1外，該算法均能夠找到最優(yōu)解．應用本文算法時，這17個測試例子都能找到最優(yōu)解．可見本文的memetic算法比改進遺傳算法更為有效．

表1　3種算法的計算結果

5結束語

集合覆蓋問題本質(zhì)上是一個帶約束的0-1規(guī)劃問題，本文通過動態(tài)罰函數(shù)法將集合覆蓋問題等價轉(zhuǎn)化為無約束的0-1規(guī)劃問題，并提出了高效的自適應memetic算法以求解該無約束0-1規(guī)劃問題.自適應memetic算法首先通過貪心自適應算法構造了具有良好多樣性的初始種群，采用局部搜索算法和路徑重連策略加強了其局部搜索能力，并通過動態(tài)變異算子來避免早熟收斂，提高了種群多樣性．實驗結果表明，所提算法較于其他算法更高效，求值速度更快.

參考文獻(References)：

[1]GAREY M R, JOHNSON D S. Computers and Intractability: A Guide to the Theory of NP-Completeness[M]. San Francisco：Freeman,1979.

[2]BALAS E, CARRERA M C. A dynamic subgradient-based branch-and-bound procedure for set covering[J]. Operations Research,1996,44(6):875-890.

[3]FISHER M R, KEDIA P. Optimal solution of set covering/partitioning problems using dual heuristics[J]. Management Science,1990,36(6):674-688.

[4]HOCHBAUM D S. Approximation algorithms for the set covering and vertex cover problems[J]. SIAM Journal on Computing,1982,11(3):555-556.

[5]GROSSMAN T, WOOL A. Computational experience with approximation algorithms for the set covering problem[J]. European Journal of Operational Research,1997,101(1):81-92.

[6]REN Z G, FENG Z R, KE L J, et al. New ideas for applying ant colony optimization to the set covering problem[J]. Computers & Industrial Engineering,2010,58(4):774-784.

[7]BEASLEY J E, CHU P C. A genetic algorithm for the set covering problem[J]. European Journal of Operational Research,1996,94(2):392-404.

[8]吳志勇，陳韜，王紅川，等.一個解決集合覆蓋問題的二階段遺傳算法[J].小型微型計算機系統(tǒng)，2011,32(4)：732-737.

WU Zhiyong, CHEN Tao, WANG Hongchuan, et al. Two stage genetic algorithm for set covering problem [J]. Journal of Chinese Computer Systems,2011,32(4):732-737

[9]蔣建林，程坤，王璨璨，等.基于改進遺傳算法的集合覆蓋問題[J].數(shù)學的實踐與認識，2012,42(5)：120-126.

JIANG Jianlin, CHENG Kun, WANG Cancan, et al. Improved genetic algorithm for set covering problem [J]. Mathematics in Practice and Theory,2012,42(5):120-126.

[10]NAJI-AZIMI Z, TOTH P, GALLI L. An electromagnetism metaheuristic for the unicost set covering problem[J]. European Journal of Operational Research, 2010, 205(2): 290-300.

[11]SUNDAR S, SINGH A. A hybrid heuristic for the set covering problem[J]. Operational Research,2012,12(3):345-365.

[12]ALI M M, ZHU W X. A penalty function-based differential evolution algorithm for constrained global optimization[J]. Computational Optimization and Applications,2013,54(3):707-739.

[13]FIDUCCIA C M，MATTHEYSES R M. A linear time heuristic for improving network partitions[C]// Proceedings of 19thACM/IEEE Design Automation Conference. New Jersey: IEEE Press,1982：175-181.

An adaptive memetic algorithm for solving the set covering problem. Journal of Zhejiang University(Science Edition), 2016,43(2):168-174

Abstract:Set covering problem is an NP-hard and classical combinatorial optimization problem that has a wide range of real world applications. Firstly, the set covering problem is converted into an equivalent unconstrained 0-1 programming problem by the adaptive penalty function method. Then, an efficient adaptive memetic algorithm is proposed to solve the resulting unconstrained 0-1 programming problem. It integrates an initial population construction method, a local search method, a crossover operator, an adaptive mutation operator and a path relinking strategy, which are based on the characteristics of the set covering problem. These strategies achieve a good balance between intensification and diversification. The proposed algorithm has been tested on 45 benchmarks from the literatures. Computational results and comparisons with the existing genetic algorithms indicate that the proposed algorithm can find solutions with high quality in a reasonable time, and it is an efficient algorithm for solving the large scale set covering problems.

Key Words:set covering problem; memetic algorithm; penalty function; local search; path relinking

中圖分類號：O 224.1；TP 18

文獻標志碼：A

文章編號：1008-9497(2016)02-168-07

DOI:10.3785/j.issn.1008-9497.2016.02.008

作者簡介：林耿(1981-),ORCID:http://orcid.org/0000-0002-1643-6859,男，副教授，博士，主要從事優(yōu)化理論與算法、智能計算等研究，E-mail: lingeng413@163.com.

基金項目：國家自然科學基金資助項目(11301255)；福建省自然科學基金資助項目(2015J01589,2016J01025).

收稿日期：2015-06-03.