A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem
A novel local search algorithm with configuration checking and scoring mechanism for the set k-covering problem
复制标题
一种针对集合 k 覆盖问题的具有配置检查和评分机制的新颖局部搜索算法
DOI：
10.1111/itor.12280
复制
发表时间：
2017
影响因子：
3.1
通讯作者：
Zhang Liming
中科院分区：
文献类型：
--
作者：
Wang Yiyuan;Yin Minghao;Ouyang Dantong;Zhang Liming
集合覆盖问题是经典集合覆盖问题的推广，是一个重要的NP-Hard组合优化问题，在计算生物学和无线网络等领域有着广泛的应用。本文的目的是设计一种新的局部搜索算法来解决这一问题。首先，为了克服局部搜索中的循环问题，提出了集合覆盖配置检查(SKCC)策略。其次，我们使用元素的代价方案来定义评分机制，以便我们的算法能够找到不同的可能的高质量的解。将SKCC策略与评分机制相结合，设计了一种子集选择策略来决定哪个子集应该被选为候选解组件。在此基础上，提出了一种新的局部搜索框架DLLccsm(基于配置检查和评分机制的分流局部搜索)。DLLccsms是针对两种最先进的算法进行评估的。实验结果表明，在大多数经典实例中，DLLCSSM在解的质量方面都优于其竞争对手。
The setk‐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 setk‐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. DLLccsmis evaluated against two state‐of‐the‐art algorithms. The experimental results show that DLLccsmperforms better than its competitors in terms of solution quality in most classical instances.