An effective binary artificial bee colony algorithm for maximum set k-covering problem. (15th December 2020)

• Record Type: Journal Article
• Authors: Lin, Geng; Xu, Haiping; Chen, Xiang; Guan, Jian
• Is Part Of: Expert systems with applications. Volume 161(2020)
• Publication Date: 2020-12-15
• Subjects: Maximum set k-covering problem -- Artificial bee colony algorithm -- Local search -- Heuristic -- Binary programming; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2020.113717
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: A hybrid binary artificial bee colony algorithm is proposed. A new food source updating method is developed. Using a tabu search based simulated annealing to improve solution quality. Bucket sorting technique is employed to speed up the search. We find new best solutions for several instances. Abstract: Given a row set M and a column set C, where each column in C covers several rows of M, the maximum set k -covering problem (MKCP) is to select k columns from C, such hat the number of rows covered by the selected columns is maximized. It can be formulated as linear integer programming, and has several real world applications. Several heuristic approaches have been previously presented for solving the MKCP. However, the obtained solution quality is not stable, and the solution time increases very quickly as the size of the instance increases. This work proposes a hybrid binary artificial bee colony algorithm (HBABC) to solve the MKCP. First, based on the characteristic of MKCP, HBABC redesigns a food source updating method. The new updating method uses the previously found solutions to guide the search. Second, to improve the exploitation ability of the HBABC, a tabu based simulated annealing (TBSA) is proposed. Moveover, we employ a bucket sorting technique to speed up the TBSA. Finally, the computational results on 75 benchmark instances demonstrate that the HBABC competes favorably with other algorithms. Specifically, our algorithm improves the best known solutions on about 20 percent of the tested instances. In addition, the HBABC performs better than two binary artificial bee colony algorithms on the tested instances.