An Effective Hybrid Memetic Algorithm for the Minimum Weight Dominating Set Problem

作者：Lin, Geng^*; Zhu, Wenxing; Ali, Montaz M.

来源：IEEE Transactions on Evolutionary Computation, 2016, 20(6): 892-907.

DOI：10.1109/TEVC.2016.2538819

• Adaptive penalty method
• dominating set problem
• local search
• memetic algorithm (MA)
• path relinking

The minimum weight-dominating set (MWDS) problem is NP-hard and has a lot of applications in the real world. Several metaheuristic methods have been developed for solving the problem effectively, but suffering from high CPU time on large-scale instances. In this paper, we design an effective hybrid memetic algorithm (HMA) for the MWDS problem. First, the MWDS problem is formulated as a constrained 0-1 programming problem and is converted to an equivalent unconstrained 0-1 problem using an adaptive penalty function. Then, we develop a memetic algorithm for the resulting problem, which contains a greedy randomized adaptive construction procedure, a tabu local search procedure, a crossover operator, a population-updating method, and a path-relinking procedure. These strategies make a good tradeoff between intensification and diversification. A number of experiments were carried out on three types of instances from the literature. Compared with existing algorithms, HMA is able to find high-quality solutions in much less CPU time. Specifically, HMA is at least six times faster than existing algorithms on the tested instances. With increasing instance size, the CPU time required by HMA increases much more slowly than required by existing algorithms.

• 出版日期2016-12
• 单位闽江学院; 福州大学