林　耿， 關(guān)　健

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

?

自適應(yīng)memetic算法求解集合覆蓋問題

林耿1， 關(guān)健2

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

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

關(guān)鍵詞：集合覆蓋問題；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è)、后勤保障、市場銷售、計算生物學(xué)等領(lǐng)域應(yīng)用廣泛.

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

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

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

1問題描述

給定一個m行n列的0-1矩陣A=(aij)m×n和列的費(fèi)用cj，其中aij=1表示第i行被第j列覆蓋，aij=0表示第i行未被第j列覆蓋，集合覆蓋問題尋找一個費(fèi)用總和最小的列的集合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ù)的構(gòu)造

采用精確罰函數(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ù)難以選擇的問題，近年來，學(xué)者們提出了無參數(shù)罰函數(shù)法、自適應(yīng)罰函數(shù)法等.針對帶約束的連續(xù)優(yōu)化問題，ALI等[12]提出了自適應(yīng)動態(tài)罰函數(shù)法，此方法有效降低了罰參數(shù)對實例的敏感程度.基于集合覆蓋問題的特點，構(gòu)造如下動態(tài)罰函數(shù)：

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

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

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

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

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

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

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

(1)

當(dāng)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)解.

假設(shè)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變換鄰域結(jié)構(gòu)：

(3)

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

證明假設(shè)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自適應(yīng)memetic算法

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

3.1初始種群的生成

初始種群P={x1,x2,…,xp}的構(gòu)造對memetic算法的性能有很大的影響.本文采用隨機(jī)貪心自適應(yīng)方法來構(gòu)造質(zhì)量高、多樣性好的初始種群.設(shè)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構(gòu)造候選列的集合RCL={j∈M:Qmax≥Q(j)≥δ Qmax}，其中1>δ>0為參數(shù)，用于平衡隨機(jī)性和貪婪性.

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

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

重復(fù)運(yùn)行以上算法p次得到初始種群.

3.2局部搜索算法

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

該局部搜索算法SCPFM由一系列pass組成.假設(shè)x0為初始解.在每個pass的初始階段，所有變量都能夠自由翻轉(zhuǎn)(即由xj變?yōu)?-xj).假設(shè)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)后，就鎖定該變量，即在當(dāng)前的pass中禁止該變量再翻轉(zhuǎn).更新自由變量的增益.記xb是該pass中到目前為止找到的最好的解.重復(fù)以上步驟，直到φ(x)-φ(xb)>ξ時，該pass停止，其中φ(x)為當(dāng)前解的目標(biāo)函數(shù)值，ξ>0為參數(shù).因為當(dāng)ξ比較大時，在該pass中，繼續(xù)翻轉(zhuǎn)自由變量，將無法找到比xb更好的解.接下來的pass以xb作為初始解.重復(fù)以上迭代，直到無法得到改進(jìn)解為止．設(shè)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′}，隨機(jī)產(chǎn)生σ∈(0,1)，若σ≤0.8，概率將xj翻轉(zhuǎn)，即令xj=1-xj；否則，F(xiàn)′=F′-{j}，重復(fù)步驟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ù)結(jié)構(gòu)[13]能夠在O(1)時間內(nèi)找到具有最大增益的自由變量.在一個pass中，每個變量至多翻轉(zhuǎn)一次，所以一個pass的時間復(fù)雜度為O(mn2).

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

3.3交叉算子與變異算子

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

3.4路徑重連策略

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

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

(7)

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

算法3：

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

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

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

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

3.5自適應(yīng)memetic算法的步驟

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

圖1　自適應(yīng)memetic算法流程圖Fig.1　Flowchart of the adaptive memetic algorithm

mu是變異算子中控制變異程度的參數(shù).在搜索的早期，為了快速提高種群解的質(zhì)量，mu的取值應(yīng)該較小.隨著搜索的深入，種群的多樣性變差，應(yīng)當(dāng)增加mu，開拓新的搜索空間.記xi∈P,i=1,2，…,p的變異參數(shù)分別為mu(i),i=1,2,…,p.設(shè)最小變異值為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è)算法的最大迭代次數(shù)為G，自適應(yīng)memetic算法的步驟如下：

算法4:

步驟1算法1運(yùn)行p次，構(gòu)造初始種群P={x1,x2,…,xp}.運(yùn)用SCPFM算法(算法2)分別對種群P中的解進(jìn)行優(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實驗結(jié)果及分析

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

采用OR-Library中的45個國際標(biāo)準(zhǔn)測試?yán)訙y試本文提出的算法.這些例子已廣泛用于對集合覆蓋問題相關(guān)算法的測試.

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

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

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

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

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

表1　3種算法的計算結(jié)果

5結(jié)束語

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

參考文獻(xiàn)(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].小型微型計算機(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ìn)遺傳算法的集合覆蓋問題[J].數(shù)學(xué)的實踐與認(rèn)識，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

文獻(xiàn)標(biāo)志碼：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.

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

收稿日期：2015-06-03.