一種求解厭惡型p-中位問題的混合進(jìn)化算法

林耿(閩江學(xué)院 數(shù)學(xué)系， 福建 福州 350108)

一種求解厭惡型p-中位問題的混合進(jìn)化算法

林耿
(閩江學(xué)院 數(shù)學(xué)系， 福建 福州 350108)

厭惡型p-中位問題是一個(gè)NP-困難問題.提出了一種求解厭惡型p-中位問題的混合進(jìn)化算法.首先，通過貪心隨機(jī)自適應(yīng)搜索方法和隨機(jī)構(gòu)造方法產(chǎn)生初始種群.然后，利用搜索過程中收集到的全局信息和局部信息構(gòu)造新解，期間注意提高搜索的多樣性，避免早熟.最后，針對厭惡型p-中位問題的特點(diǎn)，構(gòu)造基于約束交換鄰域的局部搜索算法，提高了算法的局部搜索能力.通過求解72個(gè)標(biāo)準(zhǔn)測試?yán)右詸z驗(yàn)算法的性能，發(fā)現(xiàn)該算法在較短時(shí)間內(nèi)得到了高質(zhì)量解，優(yōu)于現(xiàn)有算法.

厭惡型p-中位問題；進(jìn)化算法；分布估計(jì)算法；局部搜索；啟發(fā)式算法

0 引 言

選址問題(facility location problem)是運(yùn)籌學(xué)研究的重要內(nèi)容之一，在運(yùn)輸、教育、通信網(wǎng)絡(luò)、管理等學(xué)科中有廣泛應(yīng)用.近年來，隨著工業(yè)化的發(fā)展，環(huán)境污染已成為嚴(yán)峻的社會(huì)問題；同時(shí)，人們的環(huán)保意識越來越強(qiáng)，政府對厭惡型設(shè)施選址問題越來越重視.所謂厭惡型設(shè)施是指污染環(huán)境、危害或具有潛在危害人們身心健康可能性的設(shè)施，比如核電站、垃圾處理站、化工廠、手機(jī)基站發(fā)射塔等.這些厭惡型設(shè)施大多是社會(huì)必需的公共設(shè)施，但人們期望盡量遠(yuǎn)離這些設(shè)施.厭惡型設(shè)施選址問題已經(jīng)成為學(xué)者們廣泛關(guān)注的熱點(diǎn)之一.

根據(jù)不同的問題背景，可以建立不同的厭惡型設(shè)施選址模型[1-5].目前，很多模型是基于某一類特殊情況或者特殊圖的.2007年，根據(jù)厭惡型設(shè)施的選址應(yīng)盡可能遠(yuǎn)離顧客的要求，BELOTTI等[5]建立了一般圖的厭惡型p-中位問題(obnoxiousp-median problem).厭惡型p-中位問題是指在一般圖的頂點(diǎn)上確定p個(gè)點(diǎn)來布置厭惡型設(shè)施，使所有顧客到達(dá)這些厭惡型設(shè)施的最小距離總和最大.因此，求解一般圖上的厭惡型p-中位問題具有重要的理論和現(xiàn)實(shí)意義.

厭惡型p-中位問題是一個(gè)NP-困難問題，可用0-1線性規(guī)劃建立數(shù)學(xué)模型.BELOTTI等[5]提出了基于分支-切割的精確算法(branch-and-cut method，B&C).為了提高算法的效率，B&C法先通過禁忌搜索算法(exploring tabu search，XTS)獲得下界，然后再進(jìn)行分支割算法.數(shù)值實(shí)驗(yàn)結(jié)果表明，B&C法能夠在可接受的時(shí)間內(nèi)求解小規(guī)模厭惡型p-中位問題，但隨著問題規(guī)模的增大，求解時(shí)間迅速增加，無法在短時(shí)間內(nèi)求解較大規(guī)模的問題.故學(xué)者們設(shè)計(jì)了啟發(fā)式算法來求解大規(guī)模厭惡型p-中位問題.COLMENAR等[6]提出了一種求解厭惡型p-中位問題的貪心隨機(jī)自適應(yīng)算法(greedy randomized adaptive search procedure，GRASP).該算法首先通過貪心構(gòu)造算法構(gòu)造初始解.然后，通過過濾機(jī)制找出具有潛力的初始解.最后，通過局部搜索算法進(jìn)一步提高了具有潛力的解的質(zhì)量.重復(fù)以上步驟，直到算法停止，滿足準(zhǔn)則.通過72個(gè)標(biāo)準(zhǔn)例子測試GRASP，與B&C、XTS相比，GRASP能夠較快地找到高質(zhì)量的解.

雖然，XTS和GRASP在求解速度上有了較大提高，但其求解時(shí)間依然會(huì)隨著問題規(guī)模的增大而快速增加.導(dǎo)致算法求解速度慢的主要原因有： 1)沒有充分利用先前搜索獲得的全局信息和局部信息來構(gòu)造新解；2)為了保證解的可行性，XTS和GRASP采用基于交換鄰域的局部搜索算法.由于交換鄰域中解的個(gè)數(shù)為p(n-p)，其中n為設(shè)施的數(shù)量，隨著n的增大，算法的搜索速度急劇下降.

進(jìn)化算法已經(jīng)成功應(yīng)用于求解許多大規(guī)模優(yōu)化問題[7-8].針對現(xiàn)存算法求解速度慢的問題，提出了一種混合進(jìn)化算法(hybrid evolutionary algorithm,HEA)求解厭惡型p-中位問題.HEA法基于厭惡型p-中位問題的特點(diǎn)，首先利用分布估計(jì)算法收集到的全局信息，結(jié)合當(dāng)前精英解集中解的局部信息生成新一代的解向量，使得新產(chǎn)生的解具有較高的質(zhì)量，以及多樣性.然后，采用基于約束交換鄰域的局部搜索算法進(jìn)一步提高求解速度和解的質(zhì)量.采用72個(gè)標(biāo)準(zhǔn)測試?yán)訙y試本文算法，并與B&C、XTS和GRASP法進(jìn)行比較，以證明本文算法的高效性.

1 問題的描述和數(shù)學(xué)模型

給定一個(gè)顧客集合I={1,2，…,m}和設(shè)施集合J={1,2，…,n}，假設(shè)dij表示第i個(gè)顧客和第j個(gè)設(shè)施之間的距離，厭惡型p-中位問題需要尋找一個(gè)含有p個(gè)設(shè)施的子集S?J，使得每一個(gè)顧客i∈I與選中的p個(gè)設(shè)施的最小距離的總和最大.引入n維0-1向量x=(x1,x2，…,xn)，如果第j個(gè)設(shè)施被選中，那么xj=1；否則xj=0.則厭惡型p-中位問題可以用以下0-1規(guī)劃建立數(shù)學(xué)模型：

厭惡型p-中位問題是一個(gè)NP-困難問題[9].

2 混合進(jìn)化算法

混合進(jìn)化算法[10-11]能夠克服單種進(jìn)化算法的缺點(diǎn)，提高搜索效率，已經(jīng)成功應(yīng)用于求解許多大規(guī)模優(yōu)化問題.ZHANG等[12]和CHAURASIA等[13]提出了一類將全局信息和局部信息相結(jié)合的混合進(jìn)化算法，能夠有效提高算法的搜索效率.受此啟發(fā)，針對現(xiàn)有算法求解速度慢的問題，根據(jù)厭惡型p-中位問題的特點(diǎn)，提出了一種將統(tǒng)計(jì)學(xué)習(xí)方法與進(jìn)化算法有機(jī)結(jié)合，能夠快速求解厭惡型p-中位問題的混合進(jìn)化算法(HEA)，也稱種群算法.算法主要包含4個(gè)基本子模塊： 1) 初始種群生成方法；2) 概率模型；3) 新解的產(chǎn)生方法；4) 基于約束交換鄰域的局部搜索算法.

2.1 初始種群的生成方法

為了更好地介紹改進(jìn)的COLMENAR等[6]的初始解構(gòu)造方法(improved constructive algorithm,ICA)，先給出一些下文要用到的記號.

(1)

假設(shè)S為選中的設(shè)施的集合，|S|為選中的設(shè)施的數(shù)量.ICA初始化S=?，首先從初始候選集合CL={j∈J：φ(j)≥φmin+λ*(φmax-φmin)}中隨機(jī)選擇一個(gè)設(shè)施k加入S，其中λ∈(0,1).向S中增加設(shè)施，使得目標(biāo)函數(shù)值下降.記g(S,j)為向S中增加設(shè)施j后目標(biāo)函數(shù)值的改變量，即

(2)

然后，ICA構(gòu)造隨機(jī)候選集合：

RCL={j∈J-S：g(S,j)≥

gmax-λ*(gmax-gmin)}.

(3)

從RCL中隨機(jī)選擇一個(gè)設(shè)施加入S.ICA重復(fù)以上步驟，直到|S|=p.

初始種群生成法的步驟如下：

算法1

步驟1初始化t=1，P=?.

步驟4由式(2)計(jì)算g(S,j)，?j∈J-S，并根據(jù)式(3)構(gòu)造RCL.

步驟6如果|S|

步驟10如果|S|

2.2 概率模型

已有研究[14-15]表明： 大規(guī)模組合優(yōu)化問題的高質(zhì)量解之間具有很高的相似度.HEA通過概率模型記錄先前搜索的高質(zhì)量解的空間分布情況.引入n維概率向量v=(v1,v2，…,vn)，其中vj表示xj=1的概率，即設(shè)施j被選中的概率.

(4)

更新概率向量，其中0≤κ≤1表示學(xué)習(xí)速率.由于優(yōu)勢解集解的結(jié)構(gòu)比較接近，為避免早熟，對概率向量進(jìn)行以下修正：

(5)

2.3 新解的產(chǎn)生方法

分布估計(jì)算法通過概率模型記錄解空間的分布情況，利用概率向量產(chǎn)生下一代的解向量.該方法雖然有效地利用了全局信息.但缺乏對搜索過程中收集到的局部信息的利用，導(dǎo)致算法的局部搜索能力不足.

遺傳算法通過對種群中的解進(jìn)行交叉和變異操作來構(gòu)造下一代解向量.有效利用了局部信息，但沒有充分利用搜索過程中的全局信息，導(dǎo)致算法容易陷入局部最優(yōu).

HEA結(jié)合2種算法的優(yōu)點(diǎn)構(gòu)造新的解向量.假設(shè)E={z1,z2，…,zμ}是μ個(gè)解組成的精英解集，新產(chǎn)生的解向量記為x=(x1,x2，…,xn).首先，HEA從精英解集E中隨機(jī)選擇一個(gè)解z=(z1,z2,…,zn).然后，對于新解x的每一維分量xj，HEA可以通過概率模型產(chǎn)生，或直接繼承zj的值.最后，由于通過以上方法得到的可能不是可行解，HEA可通過以下方法對解進(jìn)行修復(fù)： 1)如果選中的設(shè)施超過p個(gè)，則從S中隨機(jī)刪除|S|-p個(gè)設(shè)施；2)如果選中的設(shè)施少于p個(gè)，則從J-S中隨機(jī)選擇p-|S|個(gè)設(shè)施加入S.

新解的產(chǎn)生方法及步驟如下：

算法2

步驟1從E中隨機(jī)選擇一個(gè)解z.初始化t=1.

步驟2產(chǎn)生一個(gè)隨機(jī)數(shù)θ∈[0,1].

步驟3如果θ≤0.7，則轉(zhuǎn)步驟4；否則，令xt=zt.

步驟4產(chǎn)生一個(gè)隨機(jī)數(shù)θ∈[0,1].如果θ≤vt，則令xt=1；否則，令xt=0.

步驟5令t=t+1，如果t≤n，則轉(zhuǎn)步驟2；否則，轉(zhuǎn)步驟6.

步驟6假設(shè)解向量x對應(yīng)的選中的設(shè)施集合為S.如果|S|>p，則從S中隨機(jī)刪除|S|-p個(gè)設(shè)施.如果|S|

步驟7停止，并將S所對應(yīng)的解x輸出.

2.4 基于約束交換鄰域的局部搜索算法

局部搜索算法能夠有效提高進(jìn)化算法的局部搜索能力.研究結(jié)果表明，進(jìn)化算法的大部分時(shí)間消耗在局部搜索中[16].因此，設(shè)計(jì)高效的局部搜索算法是進(jìn)化算法的重要步驟之一.

KERNIGHAN等[17]提出了一種高效的迭代改進(jìn)局部搜索算法(Kernighan and Lin algorithm， KL)以求解圖的劃分問題.該算法已被應(yīng)用于求解各類大規(guī)模優(yōu)化問題[18].為了提升局部搜索算法的速度，根據(jù)厭惡型p-中位問題的特點(diǎn)，HEA提出了一種基于約束交換鄰域的KL算法(constrained swap neighborhood based KL algorithm,CENKLA).該局部搜索算法能夠在搜索過程中保持解的可行性.

d(S,j)=f(S-{j})-f(S)，

(6)

其中f(S)表示選中的設(shè)施集合為S時(shí)的目標(biāo)函數(shù)值.CENKLA分別構(gòu)造了S和J-S中有潛力且可以自由改變狀態(tài)的子集Nd?S∩Fd和Na?(J-S)∩Fa.即

Nd={j∈S∩Fd：d(S,j)≥dmin+
α*(dmax-dmin)}，

(7)

Na={j∈(J-S)∩Fa：g(S,j)≥gmin+
α*(gmax-gmin)}，

(8)

α∈(0,1).令

(9)

輸入可行解x0，CENKLA的具體步驟如下：

算法3

步驟1初始化x=x0，xb=x0.

步驟2初始化Fd=S，F(xiàn)a=J-S，其中S為當(dāng)前解x選中的設(shè)施集合.

步驟3由式(7)和(8)分別構(gòu)造Nd和Na.

步驟6如果f(x)>f(xb)，令xb=x.

步驟7如果Fd=?或Fa=?，轉(zhuǎn)步驟8；否則，轉(zhuǎn)步驟3.

步驟8如果f(xb)>f(x0)，令x0=xb，x=x0，轉(zhuǎn)步驟2；否則，停止，輸出xb.

2.5 HEA算法步驟

假設(shè)算法的最大迭代次數(shù)為G，本文提出的混合進(jìn)化算法HEA的詳細(xì)步驟如下：

算法4

步驟2從P中選擇μ個(gè)最好的解構(gòu)成精英解集E.

步驟3令x*=argmax{f(x),x∈P}，xw為E中最差的解，即xw=argmin{f(x),x∈E}.

步驟4令iter=iter+1.從P中選擇ρ個(gè)最優(yōu)解，用式(4)和(5)更新概率向量v.初始化t=1，P′=?.

步驟5采用新解的產(chǎn)生方法(算法2)產(chǎn)生新的解xt，并用局部搜索算法(算法3)進(jìn)一步優(yōu)化.令P′=P′∪{xt}.

步驟6如果f(xt)>f(xw)，令E=E∪{xt}-{xw}，xw=argmin{f(x),x∈E}.

步驟7如果f(xt)>f(x*)，令x*=xt.

步驟10如果iter

3 實(shí)驗(yàn)結(jié)果與分析

為了檢測HEA算法的性能，本文用C語言對混合進(jìn)化算法進(jìn)行編程.算法的運(yùn)行環(huán)境為Windows 7，CPU 3.4 GHz，內(nèi)存4 GB.

3.1 標(biāo)準(zhǔn)測試?yán)?/h3>

COLMENAR等[6]將OR-library[19]中的24個(gè)p-中位問題的測試?yán)?從pmed17到pmed40)轉(zhuǎn)換為72個(gè)厭惡型p-中位問題的測試?yán)?這72個(gè)例子已被應(yīng)用于測試B&C、XTS和GRASP.本文也將利用這些例子來測試HEA.

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

3.3 結(jié)果與比較

利用本文提出的混合進(jìn)化算法求解72個(gè)標(biāo)準(zhǔn)例子.為了避免算法的隨機(jī)性，在同一臺電腦上對每個(gè)例子進(jìn)行20次測試.運(yùn)行過程中分別記錄每個(gè)例子在20次測試中得到的最優(yōu)解、平均解和標(biāo)準(zhǔn)差，以及運(yùn)行20次需要的平均時(shí)間.測試結(jié)果如表1所示.表1還給出了現(xiàn)存算法(包括B&C、XTS和GRASP)在每個(gè)例子上找到的當(dāng)前最優(yōu)解.HEA新找到的最優(yōu)解在表1中用黑體顯示.

從表1的結(jié)果可以看出：

1)HEA在17個(gè)例子上找到了比當(dāng)前最優(yōu)解更好的解.另外，HEA在30個(gè)例子上能夠找到當(dāng)前最優(yōu)解.

2)HEA的標(biāo)準(zhǔn)差變化范圍為[0,12.14]，平均標(biāo)準(zhǔn)差為3.09.此外，HEA在20個(gè)例子中每次都能找到一樣的解(即標(biāo)準(zhǔn)差為0).可見，HEA是比較穩(wěn)健的進(jìn)化算法.

3)HEA算法的求解時(shí)間隨著問題規(guī)模的增大而增加.72個(gè)例子的平均求解時(shí)間為50.182 s.

表1 HEA的實(shí)驗(yàn)結(jié)果Table 1 Experimental results of HEA

(續(xù)表1)

為進(jìn)一步檢驗(yàn)本文提出的HEA性能，將HEA與現(xiàn)存算法B&C、XTS、GRASP做比較，其中GRASP算法使用2種停止準(zhǔn)則.第1種GRASP(1 000)迭代1 000次停止，第2種GRASP(5 000)迭代5 000次停止.表2給出了5種算法在72個(gè)例子中運(yùn)行得到的平均解和平均求解時(shí)間.表2中B&C、XTS、GRASP(1 000)和GRASP(5 000)的結(jié)果均引自文獻(xiàn)[6].

表2 HEA在測試集上的情況比較Table 1 Comparison of HEA over the whole set of instances

從表2可以看出，HEA得到的平均解優(yōu)于B&C、XTS和GRASP(1 000)，并且求解的平均時(shí)間比B&C、XTS和GRASP(1 000)少很多.因此，HEA的性能優(yōu)于XTS和GRASP(1 000).HEA得到的平均解雖比GRASP(5 000)稍差，但GRASP(5 000)的求解時(shí)間遠(yuǎn)長于HEA.注意： B&C、XTS、GRASP(1 000)和GRASP(5 000)是在i5660 電腦(3.3 GHz,8 G內(nèi)存)上運(yùn)行的.根據(jù)http： //www.cpubenchmark.net的CPU速度數(shù)據(jù)報(bào)告，i5660 電腦(3.3 GHz,8 G內(nèi)存)的運(yùn)行速度是本文算法所用電腦運(yùn)行速度的1.6倍.所以，HEA的求解速度明顯快于XTS和GRASP.

以上的實(shí)驗(yàn)和比較結(jié)果表明，HEA能夠在較短時(shí)間內(nèi)找到高質(zhì)量的解，是求解厭惡型p-中位問題的有效算法.

3.4 主要模塊對HEA性能的影響分析

HEA的2個(gè)主要組成模塊： 初始種群生成方法記作HEA1，即將HEA中的初始種群生成方法改成隨機(jī)生成方法而其他模塊保持不變的算法；基于約束交換鄰域的局部搜索算法記作HEA2，即HEA的迭代過程中去掉基于約束交換鄰域的局部搜索算法.為了研究這2個(gè)模塊對HEA性能的影響，應(yīng)用HEA1、HEA2和HEA分別求解pmed29-p150，運(yùn)行結(jié)果見圖1.

圖1 HEA1、HEA2和HEA的運(yùn)行結(jié)果Fig.1 Experimental results of HEA1,HEA2 and HEA

從圖1中可以看出，HEA1、HEA2的性能明顯比HEA差.HEA采用初始種群生成方法，能夠生成具有良好多樣性的高質(zhì)量初始種群，有效提高搜索效率.HEA通過基于約束交換鄰域的局部搜索算法提高了算法的搜索能力，可更快地找到高質(zhì)量解.

4 結(jié) 語

針對現(xiàn)存算法求解速度慢的問題，提出了一種求解厭惡型p-中位問題的混合進(jìn)化算法(HEA).該算法主要由初始種群生成方法、概率模型、新解的產(chǎn)生方法和基于約束交換鄰域的局部搜索算法組成.初始種群生成方法通過貪心隨機(jī)自適應(yīng)搜索方法產(chǎn)生高質(zhì)量的解，并采用隨機(jī)構(gòu)造算法生成多樣性的解.HEA通過概率模型收集了搜索過程中得到的全局信息，并結(jié)合精英解的局部信息生成新解.新解既繼承了先前局部最優(yōu)解的優(yōu)良結(jié)構(gòu)，又具有較好的多樣性.最后，構(gòu)造基于約束交換鄰域的局部搜索算法.本算法提高了局部搜索能力，可快速有效提高解的質(zhì)量.通過72個(gè)標(biāo)準(zhǔn)測試?yán)訖z驗(yàn)，發(fā)現(xiàn)本算法能夠在較短時(shí)間內(nèi)找到高質(zhì)量的解，明顯快于B & C，XTS和GRASP.

本文通過概率模型收集全局信息，但該概率模型在搜索到一定程度后，容易使算法收斂.下一步要做的工作是改進(jìn)概率模型，并將本文算法推廣應(yīng)用于解決其他組合優(yōu)化問題，比如： 最大二等分問題、集合覆蓋問題等.

[1] 程郁琨.厭惡型、半?yún)拹盒图昂蜓a(bǔ)型p-中位問題[D].上海： 上海大學(xué)，2010： 14-52.

CHENG Y K.Obnoxious,Semi-obnoxiousandBackupp-MedianProblem[D].Shanghai： Shanghai University,2010： 14-52.

[2] 柏春松.半?yún)拹盒?、厭惡p-中位問題及具有連通約束的選址問題[D].上海： 上海大學(xué)，2014： 51-63.

BO C S.Semi-obnoxiousandObnoxiousp-MedianProblemandLocationProblemwithConnectedConstraints[D].Shanghai： Shanghai University,2014： 51-63.

[3] BATTA R,LEJEUNEB M,PRASAD S.Public facility location using dispersion,population,and equity criteria[J].EuropeanJournalofOperationalResearch, 2014,234(4)： 819-829.

[4] FARAHANI R,STEADIESEIFI M,ASGARI N.Multiple criteria facility location problem： A survey[J].AppliedMathematicalModeling,2010,34： 1689-1709.

[5] BELOTTI P,LABBE M,MAFFIOLI F,et al.A branch-and-cut method for the obnoxiousp-median problem[J].4OR,2007,5(4)： 299-314.

[6] COLMENAR J M,GREISTORFER P,MARTI R,et al.Advanced greedy randomized adaptive search procedure for the obnoxiousp-median problem[J].EuropeanJournalofOperationalResearch,2016,252： 432-442.

[7] RUIZ E,ALBAREDA-SAMBOLA M,FERNANDEZ E,et al.A biased random-key genetic algorithm for the capacitated minimum spanning tree problem[J].Computers&OperationsResearch,2015,57： 95-108.

[8] CEBERIO J,IRUROZKI E,MENDIBURU A,et al.A review on estimation of distribution algorithms in permutation-based combinatorial optimization problems[J].ProgressinArtificialIntelligence,2012,1(1)： 103-117.

[9] TAMIR A.Obnoxious facility location on graphs[J].SIAMJournalonDiscreteMathematics,1991,2(4)： 550-567.

[10] PAN Q K,RUIZ R.An estimation of distribution algorithm for lot-streaming flow shop problems with setup times[J].Omega,2012,40(2)： 166-180.

[11] VIDAL T,CRAINIC T G,GENDREAU M,et al.A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time-windows[J].Computers&OperationsResearch,2013,40(1)： 475-489.

[12] ZHANG Q,SUN J,TSANG E.An evolutionary algorithm with guided mutation for the maximum clique problem[J].IEEETransactionsonEvolutionaryComputation,2005,9(2)： 192-200.

[13] CHAURASIA S N,SUNDAR S,SINGH A.A hybrid evolutionary approach for set packing problem[J].Opsearch,2015,52(2)： 271-284.

[14] LIN G,ZHU W.An efficient memetic algorithm for the max-bisection problem[J].IEEETransactionsonComputers,2014,63(6)： 1365-1376.

[15] WU Q,HAO J K.Memetic search for the max-bisection problem[J].Computers&OperationsResearch,2013,40(1)： 166-179.

[16] NERI F,COTTA C.Memetic algorithms and memetic computing optimization： A literature review[J].SwarmandEvolutionaryComputation,2012(2)： 1-14.

[17] KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs[J].BellSystemTechnicalJournal,1970,49(2)： 291-307.

[18] AMIRI B,HOSSAIN L,CRAWFORD J W,et al.Community detection in detection in complex networks： Multi-objective enhanced firefly algorithm[J].Knowledge-BasedSystems,2013,45： 1-11.

[19] BEASLEY J E.OR-library： Distributing test problems by electronic mail[J].JournaloftheOperationalResearchSociety,1990,41(11)： 1069-1072.

LIN Geng
(DepartmentofMathematics,MinjiangUniversity,Fuzhou350108,China)

The obnoxious p-median problem is known to be NP-hard.A hybrid evolutionary algorithm is proposed to solve the obnoxiousp-median problem.Firstly,an initial population is generated by a greedy randomized adaptive search procedure and a random constructive procedure.Then,to diversify the search and avoid the premature convergence,the proposed algorithm uses the global information and the local information gathered during the search to generate new solutions.Finally,according to the characteristics of obnoxiousp-median problem,a constrained swap neighborhood based on local search procedure is developed to enhance the exploitation of the algorithm.Seventy two benchmark instances are tested to demonstrate the effectiveness of the algorithm.Experimental results and comparison with the existing algorithms show that the proposed algorithm is able to obtain high quality solutions in significantly less CPU time.

obnoxiousp-median problem; evolutionary algorithm; estimation of distribution algorithm; local search; heuristic algorithm

2016-12-05.

國家自然科學(xué)基金資助項(xiàng)目(11301255);福建省自然科學(xué)基金資助項(xiàng)目(2016J01025);福建省高校新世紀(jì)優(yōu)秀人才支持計(jì)劃項(xiàng)目.

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

10.3785/j.issn.1008-9497.2018.01.006

O 224； TP 301.6

A

1008-9497(2018)01-029-08

Ahybridevolutionaryalgorithmforsolvingtheobnoxiousp-medianproblem.Journal of Zhejiang University (Science Edition)，2018,45(1)： 029-036