An Effective Hybrid Memetic Algorithm for the Minimum Weight Dominating Set Problem
提出一种混合模因算法求解NP难的最小权重支配集问题，通过自适应罚函数转化约束、结合贪婪构造与禁忌搜索等策略，在大型实例上比现有算法快至少六倍。
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.