A novel binary artificial bee colony algorithm for the set-union knapsack problem

Yichao HE, Haoran XIE, Tak-Lam WONG, Xizhao WANG*

*Corresponding author for this work

Research output: Journal PublicationsJournal Article (refereed)

33 Citations (Scopus)

Abstract

This article investigates how to employ artificial bee colony algorithm to solve Set-Union Knapsack Problem (SUKP). A mathematical model of SUKP, which is to be easily solved by evolutionary algorithms, is developed. A novel binary artificial bee colony algorithm (BABC) is also proposed by adopting a mapping function. Furthermore, a greedy repairing and optimization algorithm (S-GROA) for handling infeasible solutions by employing evolutionary technique to solve SUKP is proposed. The consolidation of S-GROA and BABC brings about a new approach to solving SUKP. Extensive experiments are conducted upon benchmark datasets for evaluating the performance of our proposed models. The results verify that the proposed approach is significantly superior to the baseline evolutionary algorithms for solving SUKP such as A-SUKP, ABCbin and binDE in terms of both time complexity and solution performance.

Original languageEnglish
Pages (from-to)77-86
Number of pages10
JournalFuture Generation Computer Systems
Volume78
Early online date15 Jun 2017
DOIs
Publication statusPublished - Jan 2018
Externally publishedYes

    Fingerprint

Bibliographical note

The first author and corresponding authors contributed equally the same to this article which was supported by Basic Research Project of Knowledge Innovation Program in Shenzhen (JCYJ20150324140036825), China Postdoctoral Science Foundations (2015M572361 and 2016T90799), National Natural Science Foundations of China (61503252 and 71371063), Scientific Research Project Program of Colleges and Universities in Hebei Province (ZD2016005), and Natural Science Foundation of Hebei Province (F2016403055). Haoran Xie’s work was supported by the Start-Up Research Grant (RG 37/2016-2017R) and the Internal Research Grant (RG 66/2016–2017) of The Education University of Hong Kong.

Keywords

  • Artificial bee colony
  • Infeasible solution
  • Repairing and optimization
  • Set-union knapsack problem

Cite this