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

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

Research output: Contribution to journalArticle

24 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. Copyright © 2017 Published by Elsevier B.V.
Original languageEnglish
Pages (from-to)77-86
JournalFuture Generation Computer Systems
Volume78
Issue numberPart 1
Early online dateJun 2017
DOIs
Publication statusPublished - Jan 2018

Fingerprint

Evolutionary algorithms
Consolidation
Mathematical models
Experiments

Citation

He, Y., Xie, H., Wong, T.-L., & Wang, X. (2018). A novel binary artificial bee colony algorithm for the set-union knapsack problem. Future Generation Computer Systems, 78(Part 1), 77-86.

Keywords

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