Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2018, Vol. 45 Issue (1): 29-36,43    DOI: 10.3785/j.issn.1008-9497.2018.01.006
数学与计算机科学     
一种求解厌恶型p-中位问题的混合进化算法
林耿
闽江学院 数学系, 福建 福州 350108
A hybrid evolutionary algorithm for solving the obnoxious p-median problem
LIN Geng
Department of Mathematics, Minjiang University, Fuzhou 350108, China
 全文: PDF(1100 KB)   HTML  
摘要： 厌恶型p-中位问题是一个NP-困难问题.提出了一种求解厌恶型p-中位问题的混合进化算法.首先，通过贪心随机自适应搜索方法和随机构造方法产生初始种群.然后，利用搜索过程中收集到的全局信息和局部信息构造新解，期间注意提高搜索的多样性，避免早熟.最后，针对厌恶型p-中位问题的特点，构造基于约束交换邻域的局部搜索算法，提高了算法的局部搜索能力.通过求解72个标准测试例子以检验算法的性能，发现该算法在较短时间内得到了高质量解，优于现有算法.
关键词： 厌恶型p-中位问题;  进化算法;  分布估计算法;  局部搜索;  启发式算法    
Abstract: The obnoxious p-median problem is known to be NP-hard.A hybrid evolutionary algorithm is proposed to solve the obnoxious p-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 obnoxious p-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.
Key words: obnoxious p-median problem    evolutionary algorithm    estimation of distribution algorithm    local search    heuristic algorithm
收稿日期: 2016-12-05 出版日期: 2017-12-15
CLC:  O224  
基金资助: 国家自然科学基金资助项目（11301255）；福建省自然科学基金资助项目（2016J01025）；福建省高校新世纪优秀人才支持计划项目.
作者简介: 林耿(1981-),ORCID:http://orcid.org/0000-0002-1643-6859,男,博士,副教授,主要从事优化理论与算法、智能计算等研究,E-mail:lingeng413@163.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
林耿

引用本文:

林耿. 一种求解厌恶型p-中位问题的混合进化算法[J]. 浙江大学学报（理学版）, 2018, 45(1): 29-36,43.

LIN Geng. A hybrid evolutionary algorithm for solving the obnoxious p-median problem. Journal of ZheJIang University(Science Edition), 2018, 45(1): 29-36,43.

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2018.01.006    或    https://www.zjujournals.com/sci/CN/Y2018/V45/I1/29

[1] 程郁琨.厌恶型、半厌恶型及候补型p-中位问题[D].上海:上海大学,2010:14-52. CHENG Y K.Obnoxious,Semi-obnoxious and Backup p-Median Problem[D].Shanghai:Shanghai University,2010:14-52.
[2] 柏春松.半厌恶型、厌恶p-中位问题及具有连通约束的选址问题[D].上海:上海大学,2014:51-63. BO C S.Semi-obnoxious and Obnoxious p-Median Problem and Location Problem with Connected Constraints[D].Shanghai:Shanghai University,2014:51-63.
[3] BATTA R,LEJEUNEB M,PRASAD S.Public facility location using dispersion,population,and equity criteria[J]. European Journal of Operational Research, 2014,234(4):819-829.
[4] FARAHANI R,STEADIESEIFI M,ASGARI N.Multiple criteria facility location problem:A survey[J].Applied Mathematical Modeling,2010,34:1689-1709.
[5] BELOTTI P,LABBE M,MAFFIOLI F,et al.A branch-and-cut method for the obnoxious p-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 obnoxious p-median problem[J].European Journal of Operational Research,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 & Operations Research,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].Progress in Artificial Intelligence,2012,1(1):103-117.
[9] TAMIR A.Obnoxious facility location on graphs[J].SIAM Journal on Discrete Mathematics,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 & Operations Research,2013,40(1):475-489.
[12] ZHANG Q,SUN J,TSANG E.An evolutionary algorithm with guided mutation for the maximum clique problem[J].IEEE Transactions on Evolutionary Computation,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].IEEE Transactions on Computers,2014,63(6):1365-1376.
[15] WU Q,HAO J K.Memetic search for the max-bisection problem[J].Computers & Operations Research,2013,40(1):166-179.
[16] NERI F,COTTA C.Memetic algorithms and memetic computing optimization:A literature review[J].Swarm and Evolutionary Computation,2012(2):1-14.
[17] KERNIGHAN B W,LIN S.An efficient heuristic procedure for partitioning graphs[J].Bell System Technical Journal,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-Based Systems,2013,45:1-11.
[19] BEASLEY J E.OR-library:Distributing test problems by electronic mail[J].Journal of the Operational Research Society,1990,41(11):1069-1072.
[1] 林耿. 求解最大二等分问题的混合二进制人工蜂群算法[J]. 浙江大学学报（理学版）, 2019, 46(5): 556-564.
[2] 万绍春, 张安, 陈永, 陈光亭. 关于带时间约束的单机排序的一个注记[J]. 浙江大学学报（理学版）, 2018, 45(1): 14-17.
[3] 林耿, 关健. 自适应memetic算法求解集合覆盖问题[J]. 浙江大学学报（理学版）, 2016, 43(2): 168-174.