New binary artificial bee colony for the 0-1 knapsack problem

Mourad Nouioua; Zhiyong Li; Shilong Jiang

doi:10.1007/978-3-319-93815-8_16

New binary artificial bee colony for the 0-1 knapsack problem

Mourad Nouioua
, Zhiyong Li^*
, Shilong Jiang

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

The knapsack problem is one of the well known NP-Hard optimization problems. Because of its appearance as a sub-problem in many real world problems, it attracts the attention of many researchers on swarm intelligence and evolutionary computation community. In this paper, a new binary artificial bee colony called NB-ABC is proposed to solve the 0-1 knapsack problem. Instead of the search operators of the original ABC, new binary search operators are designed for the different phases of the ABC algorithm, namely the employed, the onlooker and the scout bee phases. Moreover, a novel hybrid repair operator called (HRO) is proposed to repair and improve the infeasible solutions. To assess the performance of the proposed algorithm, NB-ABC is compared with two other existing algorithms, namely GB-ABC and BABC-DE, for solving the 0-1 knapsack problem. Based on a set of 15 0-1 high dimensional knapsack problems classified in three categories. the experimental results in view of many criteria show the efficiency and the robustness of the proposed NB-ABC.

Original language	English
Title of host publication	Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings
Editors	Ying Tan, Yuhui Shi, Qirong Tang
Publisher	Springer Verlag
Pages	153-165
Number of pages	13
ISBN (Print)	9783319938141
DOIs	https://doi.org/10.1007/978-3-319-93815-8_16
State	Published - 2018
Externally published	Yes
Event	9th International Conference on Swarm Intelligence, ICSI 2018 - Shanghai, China Duration: 17 Jun 2018 → 22 Jun 2018

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	10941 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	9th International Conference on Swarm Intelligence, ICSI 2018
Country/Territory	China
City	Shanghai
Period	17/06/18 → 22/06/18

Bibliographical note

Publisher Copyright:
© Springer International Publishing AG, part of Springer Nature 2018.

Keywords

0-1 knapsack problem
Artificial bee colony
Binary optimization problem

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-319-93815-8_16

Cite this

Nouioua, M., Li, Z., & Jiang, S. (2018). New binary artificial bee colony for the 0-1 knapsack problem. In Y. Tan, Y. Shi, & Q. Tang (Eds.), Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings (pp. 153-165). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10941 LNCS). Springer Verlag. https://doi.org/10.1007/978-3-319-93815-8_16

Nouioua, Mourad ; Li, Zhiyong ; Jiang, Shilong. / New binary artificial bee colony for the 0-1 knapsack problem. Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. editor / Ying Tan ; Yuhui Shi ; Qirong Tang. Springer Verlag, 2018. pp. 153-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{ef0c4c7b885444558f90b966c9a6c797,

title = "New binary artificial bee colony for the 0-1 knapsack problem",

abstract = "The knapsack problem is one of the well known NP-Hard optimization problems. Because of its appearance as a sub-problem in many real world problems, it attracts the attention of many researchers on swarm intelligence and evolutionary computation community. In this paper, a new binary artificial bee colony called NB-ABC is proposed to solve the 0-1 knapsack problem. Instead of the search operators of the original ABC, new binary search operators are designed for the different phases of the ABC algorithm, namely the employed, the onlooker and the scout bee phases. Moreover, a novel hybrid repair operator called (HRO) is proposed to repair and improve the infeasible solutions. To assess the performance of the proposed algorithm, NB-ABC is compared with two other existing algorithms, namely GB-ABC and BABC-DE, for solving the 0-1 knapsack problem. Based on a set of 15 0-1 high dimensional knapsack problems classified in three categories. the experimental results in view of many criteria show the efficiency and the robustness of the proposed NB-ABC.",

keywords = "0-1 knapsack problem, Artificial bee colony, Binary optimization problem",

author = "Mourad Nouioua and Zhiyong Li and Shilong Jiang",

note = "Publisher Copyright: {\textcopyright} Springer International Publishing AG, part of Springer Nature 2018.; 9th International Conference on Swarm Intelligence, ICSI 2018 ; Conference date: 17-06-2018 Through 22-06-2018",

year = "2018",

doi = "10.1007/978-3-319-93815-8\_16",

language = "English",

isbn = "9783319938141",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "153--165",

editor = "Ying Tan and Yuhui Shi and Qirong Tang",

booktitle = "Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings",

address = "Germany",

}

Nouioua, M, Li, Z & Jiang, S 2018, New binary artificial bee colony for the 0-1 knapsack problem. in Y Tan, Y Shi & Q Tang (eds), Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 10941 LNCS, Springer Verlag, pp. 153-165, 9th International Conference on Swarm Intelligence, ICSI 2018, Shanghai, China, 17/06/18. https://doi.org/10.1007/978-3-319-93815-8_16

New binary artificial bee colony for the 0-1 knapsack problem. / Nouioua, Mourad; Li, Zhiyong; Jiang, Shilong.
Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. ed. / Ying Tan; Yuhui Shi; Qirong Tang. Springer Verlag, 2018. p. 153-165 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 10941 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - New binary artificial bee colony for the 0-1 knapsack problem

AU - Nouioua, Mourad

AU - Li, Zhiyong

AU - Jiang, Shilong

N1 - Publisher Copyright: © Springer International Publishing AG, part of Springer Nature 2018.

PY - 2018

Y1 - 2018

N2 - The knapsack problem is one of the well known NP-Hard optimization problems. Because of its appearance as a sub-problem in many real world problems, it attracts the attention of many researchers on swarm intelligence and evolutionary computation community. In this paper, a new binary artificial bee colony called NB-ABC is proposed to solve the 0-1 knapsack problem. Instead of the search operators of the original ABC, new binary search operators are designed for the different phases of the ABC algorithm, namely the employed, the onlooker and the scout bee phases. Moreover, a novel hybrid repair operator called (HRO) is proposed to repair and improve the infeasible solutions. To assess the performance of the proposed algorithm, NB-ABC is compared with two other existing algorithms, namely GB-ABC and BABC-DE, for solving the 0-1 knapsack problem. Based on a set of 15 0-1 high dimensional knapsack problems classified in three categories. the experimental results in view of many criteria show the efficiency and the robustness of the proposed NB-ABC.

AB - The knapsack problem is one of the well known NP-Hard optimization problems. Because of its appearance as a sub-problem in many real world problems, it attracts the attention of many researchers on swarm intelligence and evolutionary computation community. In this paper, a new binary artificial bee colony called NB-ABC is proposed to solve the 0-1 knapsack problem. Instead of the search operators of the original ABC, new binary search operators are designed for the different phases of the ABC algorithm, namely the employed, the onlooker and the scout bee phases. Moreover, a novel hybrid repair operator called (HRO) is proposed to repair and improve the infeasible solutions. To assess the performance of the proposed algorithm, NB-ABC is compared with two other existing algorithms, namely GB-ABC and BABC-DE, for solving the 0-1 knapsack problem. Based on a set of 15 0-1 high dimensional knapsack problems classified in three categories. the experimental results in view of many criteria show the efficiency and the robustness of the proposed NB-ABC.

KW - 0-1 knapsack problem

KW - Artificial bee colony

KW - Binary optimization problem

UR - https://www.scopus.com/pages/publications/85049067925

U2 - 10.1007/978-3-319-93815-8_16

DO - 10.1007/978-3-319-93815-8_16

M3 - Conference contribution

AN - SCOPUS:85049067925

SN - 9783319938141

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 153

EP - 165

BT - Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings

A2 - Tan, Ying

A2 - Shi, Yuhui

A2 - Tang, Qirong

PB - Springer Verlag

T2 - 9th International Conference on Swarm Intelligence, ICSI 2018

Y2 - 17 June 2018 through 22 June 2018

ER -

Nouioua M, Li Z, Jiang S. New binary artificial bee colony for the 0-1 knapsack problem. In Tan Y, Shi Y, Tang Q, editors, Advances in Swarm Intelligence - 9th International Conference, ICSI 2018, Proceedings. Springer Verlag. 2018. p. 153-165. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-93815-8_16

New binary artificial bee colony for the 0-1 knapsack problem

Abstract

Publication series

Conference

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this