.png){kind=icon}
返回
NuSC: An Effective Local Search Algorithm for Solving the Set Covering Problem
.png){kind=icon}
PRE
AI
DOI：10.1109/TCYB.2022.3199147.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The set covering problem (SCP) is a fundamental NP-hard problem in computer science and has a broad range of important real-world applications. In practice, SCP instances transformed from real-world applications would be of large scale, so it is of significant importance to design effective heuristic algorithms, especially local search ones. However, there exist only few research works on developing local search algorithms for solving SCP. In this article, we propose a new local search algorithm for solving SCP, dubbed NuSC. In particular, NuSC introduces a new combined scoring function for subset selection, which combines different subset properties in an effective way and helps NuSC find more optimized solutions. Besides, NuSC incorporates a dynamic weighting scheme for elements, a tabu search strategy, and a novelty selection mechanism to further enhance its practical performance. In order to study the effectiveness and robustness of our proposed NuSC algorithm, we conduct extensive experiments to compare NuSC against many state-of-the-art competitors on various types of SCP instances. Our experimental results demonstrate that NuSC significantly outperforms its competitors on the majority of instances, indicating the superiority of NuSC. Also, our empirical evaluations confirm the effectiveness of each algorithmic technique underlying NuSC.
Keyword:
Search problems
Costs
Heuristic algorithms
Optimization
Job shop scheduling
Dynamic scheduling
Transforms
Combined scoring function
dynamic weighting scheme
local search
novelty mechanism
set covering problem (SCP)
tabu search strategy
期刊
IF:
10.5
论文数:
1.1W
被引数:
5.0W
机构
引用论文
.png){kind=icon}
A scoping review on the field validation and implementation of rapid diagnostic tests for vector-borne and other infectious diseases of poverty in urban areas对城市地区媒介传播和其他贫困传染病的快速诊断测试的现场验证和实施的范围界定审查
OAAI
OAAI分享收藏分享收藏分享收藏
查看更多内容