Please wait a minute...
浙江大学学报（理学版）
浙江大学学报（理学版）  2016, Vol. 43 Issue (2): 168-174    DOI: 10.3785/j.issn.1008-9497.2016.02.008
数学与计算机科学     
自适应memetic算法求解集合覆盖问题
林耿1, 关健2
1. 闽江学院数学系, 福建福州 350108;
2. 闽江学院现代教育技术中心, 福建福州 350108
An adaptive memetic algorithm for solving the set covering problem
LIN Geng1, GUAN Jian2
1. Department of Mathematics, Minjiang University, Fuzhou 350108, China;
2. Modern Educational Technology Center, Minjiang University, Fuzhou 350108, China
 全文: PDF(1120 KB)  
摘要： 集合覆盖问题是一个经典的NP困难的组合优化问题,有着广泛的应用背景.首先,采用动态罚函数法将集合覆盖问题等价转化为无约束的0-1规划问题.然后,基于集合覆盖问题的结构特征,设计了初始种群构造方法、局部搜索方法、交叉算子、动态变异算子和路径重连策略,提出了一个高效求解该0-1规划问题的自适应memetic算法.该算法有效平衡了集中搜索和多样化搜索.通过45个标准例子测试该算法,并将其结果与现有遗传算法进行了比较,表明该算法能够在可接受的时间内找到高质量的解,能够有效求解大规模集合覆盖问题.
关键词： 集合覆盖问题;  memetic算法;  罚函数;  局部搜索;  路径重连    
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
收稿日期: 2015-06-03 出版日期: 2016-03-12
CLC:  O224.1  
基金资助: 国家自然科学基金资助项目(11301255);福建省自然科学基金资助项目(2015J01589,2016J01025).
作者简介: 林耿(1981-),ORCID:http://orcid.org/0000-0002-1643-6859,男,副教授,博士,主要从事优化理论与算法、智能计算等研究,E-mail:lingeng413@163.com.
服务　　
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章　　
林耿
关健

引用本文:

林耿, 关健. 自适应memetic算法求解集合覆盖问题[J]. 浙江大学学报（理学版）, 2016, 43(2): 168-174.

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

链接本文:

https://www.zjujournals.com/sci/CN/10.3785/j.issn.1008-9497.2016.02.008    或    https://www.zjujournals.com/sci/CN/Y2016/V43/I2/168

[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].小型微型计算机系统,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].数学的实践与认识,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 19th ACM/IEEE Design Automation Conference. New Jersey:IEEE Press,1982:175-181.
[1] 杨祎巍, 匡晓云, 黄开天, 洪超, 郑昌立, 蒋小文. 基于Memetic算法的仿真用例集约简技术[J]. 浙江大学学报（理学版）, 2021, 48(3): 331-337.
[2] 林耿. 求解最大二等分问题的混合二进制人工蜂群算法[J]. 浙江大学学报（理学版）, 2019, 46(5): 556-564.
[3] 林耿. 一种求解厌恶型p-中位问题的混合进化算法[J]. 浙江大学学报（理学版）, 2018, 45(1): 29-36,43.