.png){kind=icon}
.png){kind=icon}
返回
Solving maximum set k-covering problem by an adaptive binary particle swarm optimization method
.png){kind=icon}
PRE
AI
DOI：10.1016/j.knosys.2017.11.028.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The maximum set k-covering problem (MKCP) consists in selecting a subset of k columns from a given set of n columns, in such a way that the number of rows covered by the selected columns is maximized. The problem is NP-hard and has lots of applications. In this paper, we propose an adaptive particle swarm optimization for solving the maximum set k-covering problem. The proposed algorithm uses a greedy constructive procedure to generate an initial swarm with good quality solutions. Based on the characteristic of the MKCP, an iterative local search procedure is developed to enhance the solution quality. Furthermore, a position updating procedure and a mutation procedure with adaptive mutation strength are employed to guide the search to a more promising area. These strategies achieve a good tradeoff between exploitation and exploration. Extensive evaluations on a set of benchmark instances show that the proposed algorithm performs significantly better than the existing heuristic for MKCP. In particular, it yields improved lower bounds for 96 out of 150 instances, and attains the previous best known results for remaining 54 instances. The key features of the proposed algorithm are analyzed to shed light on their influences on the performance of the proposed algorithm. (C) 2017 Elsevier B.V. All rights reserved.
Keyword:
Metaheuristics
Particle swarm optimization
Local search
Maximum set k-covering problem
Combinatorial optimization
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。