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

Yichao HE; Haoran XIE; Tak-Lam WONG; Xizhao WANG

doi:10.1016/j.future.2017.05.044

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 Publications › Journal Article (refereed) › peer-review

97 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, ABC_bin and binDE in terms of both time complexity and solution performance.

Original language	English
Pages (from-to)	77-86
Number of pages	10
Journal	Future Generation Computer Systems
Volume	78
Early online date	15 Jun 2017
DOIs	https://doi.org/10.1016/j.future.2017.05.044
Publication status	Published - Jan 2018
Externally published	Yes

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

Access to Document

10.1016/j.future.2017.05.044

Cite this

@article{81fed1615f02422ba94943f57c2d5b99,

title = "A novel binary artificial bee colony algorithm for the set-union knapsack problem",

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.",

keywords = "Artificial bee colony, Infeasible solution, Repairing and optimization, Set-union knapsack problem",

author = "Yichao HE and Haoran XIE and Tak-Lam WONG and Xizhao WANG",

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{\textquoteright}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.",

year = "2018",

month = jan,

doi = "10.1016/j.future.2017.05.044",

language = "English",

volume = "78",

pages = "77--86",

journal = "Future Generation Computer Systems",

issn = "0167-739X",

publisher = "Elsevier",

}

TY - JOUR

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

AU - HE, Yichao

AU - XIE, Haoran

AU - WONG, Tak-Lam

AU - WANG, Xizhao

N1 - 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.

PY - 2018/1

Y1 - 2018/1

N2 - 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.

AB - 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.

KW - Artificial bee colony

KW - Infeasible solution

KW - Repairing and optimization

KW - Set-union knapsack problem

UR - http://www.scopus.com/inward/record.url?scp=85028083529&partnerID=8YFLogxK

U2 - 10.1016/j.future.2017.05.044

DO - 10.1016/j.future.2017.05.044

M3 - Journal Article (refereed)

AN - SCOPUS:85028083529

SN - 0167-739X

VL - 78

SP - 77

EP - 86

JO - Future Generation Computer Systems

JF - Future Generation Computer Systems

ER -

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

Abstract

Bibliographical note

Keywords

Access to Document

Other files and links

Fingerprint

Cite this