Premium
A novel local search algorithm with configuration checking and scoring mechanism for the set k ‐covering problem
Author(s) -
Wang Yiyuan,
Yin Minghao,
Ouyang Dantong,
Zhang Liming
Publication year - 2017
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12280
Subject(s) - computer science , set (abstract data type) , local search (optimization) , algorithm , mathematical optimization , extension (predicate logic) , mechanism (biology) , selection (genetic algorithm) , set cover problem , search algorithm , mathematics , artificial intelligence , philosophy , epistemology , programming language
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 DLL ccsm (diversion local search based on configuration checking and scoring mechanism), is proposed. DLL ccsm is evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLL ccsm performs better than its competitors in terms of solution quality in most classical instances.