摘要

The set k-covering problem, an extension of the classical set covering problem, is an important NP-hard combinatorial optimization problem with extensive applications, including computational biology and wireless network. The aim of this paper is to design a new local search algorithm to solve this problem. First, to overcome the cycling problem in local search, the set k-covering configuration checking (SKCC) strategy is proposed. Second, we use the cost scheme of elements to define the scoring mechanism so that our algorithm can find different possible good-quality solutions. Having combined the SKCC strategy with the scoring mechanism, a subset selection strategy is designed to decide which subset should be selected as a candidate solution component. After that, a novel local search framework, as we call DLLccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLLccsm is evaluated against two state-of-the-art algorithms. The experimental results show that DLLccsm performs better than its competitors in terms of solution quality in most classical instances.