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
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.
林耿, 关健. 自适应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.
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.
[1]
GAREY M R, JOHNSON D S. Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. San Francisco:Freeman,1979.
[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.
[4]
HOCHBAUM D S. Approximation algorithms for the set covering and vertex cover problems[J]. SIAM Journal on Computing,1982,11(3):555-556.
[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.
[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.
[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.
[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.
[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.
[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.
2016, Vol. 43 
