Solving maximum set k-covering problem by an adaptive binary particle swarm optimization method

摘要

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.