A Binary Bat Algorithm Applied to Knapsack Problem

Lorena Jorquera; Gabriel Villavicencio; Leonardo Causa; Luis Lopez; Andrés Fernández

doi:10.1007/978-3-030-51971-1_14

A Binary Bat Algorithm Applied to Knapsack Problem

Lorena Jorquera, Gabriel Villavicencio, Leonardo Causa, Luis Lopez, Andrés Fernández

SCHOOL OF CONSTRUCTION ENGINEERING

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

2 Scopus citations

Abstract

Combinatorial problems with NP-hard complexity appear frequently in operational research. Making robust algorithms that solve these combinatorial problems is of interest in operational research. In this article, a binarization mechanism is proposed so that continuous metaheuristics can solve combinatorial problems. The binarization mechanism uses the concept of percentile. This percentile mechanism is applied to the bat algorithm. The NP-hard knapsack problem (MKP) was used to verify our algorithm. Additionally, the binary percentile algorithm was compared with other algorithms that have recently has solved the MKP, observing that the percentile algorithm produces competitive results.

Original language	English
Title of host publication	Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020
Editors	Radek Silhavy
Publisher	Springer
Pages	172-182
Number of pages	11
ISBN (Print)	9783030519704
DOIs	https://doi.org/10.1007/978-3-030-51971-1_14
State	Published - 2020
Event	9th Computer Science On-line Conference, CSOC 2020 - Zlin, Czech Republic Duration: 15 Jul 2020 → 15 Jul 2020

Publication series

Name	Advances in Intelligent Systems and Computing
Volume	1225 AISC
ISSN (Print)	2194-5357
ISSN (Electronic)	2194-5365

Conference

Conference	9th Computer Science On-line Conference, CSOC 2020
Country/Territory	Czech Republic
City	Zlin
Period	15/07/20 → 15/07/20

Keywords

Combinatorial optimization
Metaheuristics
Multidimensional knapsack problem

Access to Document

10.1007/978-3-030-51971-1_14

Cite this

Jorquera, L., Villavicencio, G., Causa, L., Lopez, L., & Fernández, A. (2020). A Binary Bat Algorithm Applied to Knapsack Problem. In R. Silhavy (Ed.), Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020 (pp. 172-182). (Advances in Intelligent Systems and Computing; Vol. 1225 AISC). Springer. https://doi.org/10.1007/978-3-030-51971-1_14

@inproceedings{6e79a9bcd28f4aed96a1804d211af89f,

title = "A Binary Bat Algorithm Applied to Knapsack Problem",

abstract = "Combinatorial problems with NP-hard complexity appear frequently in operational research. Making robust algorithms that solve these combinatorial problems is of interest in operational research. In this article, a binarization mechanism is proposed so that continuous metaheuristics can solve combinatorial problems. The binarization mechanism uses the concept of percentile. This percentile mechanism is applied to the bat algorithm. The NP-hard knapsack problem (MKP) was used to verify our algorithm. Additionally, the binary percentile algorithm was compared with other algorithms that have recently has solved the MKP, observing that the percentile algorithm produces competitive results.",

keywords = "Combinatorial optimization, Metaheuristics, Multidimensional knapsack problem",

author = "Lorena Jorquera and Gabriel Villavicencio and Leonardo Causa and Luis Lopez and Andr{\'e}s Fern{\'a}ndez",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG.; 9th Computer Science On-line Conference, CSOC 2020 ; Conference date: 15-07-2020 Through 15-07-2020",

year = "2020",

doi = "10.1007/978-3-030-51971-1_14",

language = "English",

isbn = "9783030519704",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer",

pages = "172--182",

editor = "Radek Silhavy",

booktitle = "Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020",

}

Jorquera, L , Villavicencio, G, Causa, L, Lopez, L & Fernández, A 2020, A Binary Bat Algorithm Applied to Knapsack Problem. in R Silhavy (ed.), Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020. Advances in Intelligent Systems and Computing, vol. 1225 AISC, Springer, pp. 172-182, 9th Computer Science On-line Conference, CSOC 2020, Zlin, Czech Republic, 15/07/20. https://doi.org/10.1007/978-3-030-51971-1_14

A Binary Bat Algorithm Applied to Knapsack Problem. / Jorquera, Lorena ; Villavicencio, Gabriel; Causa, Leonardo et al.
Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020. ed. / Radek Silhavy. Springer, 2020. p. 172-182 (Advances in Intelligent Systems and Computing; Vol. 1225 AISC).

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

TY - GEN

T1 - A Binary Bat Algorithm Applied to Knapsack Problem

AU - Jorquera, Lorena

AU - Villavicencio, Gabriel

AU - Causa, Leonardo

AU - Lopez, Luis

AU - Fernández, Andrés

PY - 2020

Y1 - 2020

N2 - Combinatorial problems with NP-hard complexity appear frequently in operational research. Making robust algorithms that solve these combinatorial problems is of interest in operational research. In this article, a binarization mechanism is proposed so that continuous metaheuristics can solve combinatorial problems. The binarization mechanism uses the concept of percentile. This percentile mechanism is applied to the bat algorithm. The NP-hard knapsack problem (MKP) was used to verify our algorithm. Additionally, the binary percentile algorithm was compared with other algorithms that have recently has solved the MKP, observing that the percentile algorithm produces competitive results.

AB - Combinatorial problems with NP-hard complexity appear frequently in operational research. Making robust algorithms that solve these combinatorial problems is of interest in operational research. In this article, a binarization mechanism is proposed so that continuous metaheuristics can solve combinatorial problems. The binarization mechanism uses the concept of percentile. This percentile mechanism is applied to the bat algorithm. The NP-hard knapsack problem (MKP) was used to verify our algorithm. Additionally, the binary percentile algorithm was compared with other algorithms that have recently has solved the MKP, observing that the percentile algorithm produces competitive results.

KW - Combinatorial optimization

KW - Metaheuristics

KW - Multidimensional knapsack problem

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

U2 - 10.1007/978-3-030-51971-1_14

DO - 10.1007/978-3-030-51971-1_14

M3 - Conference contribution

AN - SCOPUS:85089717744

SN - 9783030519704

T3 - Advances in Intelligent Systems and Computing

SP - 172

EP - 182

BT - Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020

A2 - Silhavy, Radek

PB - Springer

T2 - 9th Computer Science On-line Conference, CSOC 2020

Y2 - 15 July 2020 through 15 July 2020

ER -

Jorquera L , Villavicencio G, Causa L, Lopez L, Fernández A. A Binary Bat Algorithm Applied to Knapsack Problem. In Silhavy R, editor, Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020. Springer. 2020. p. 172-182. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-030-51971-1_14

A Binary Bat Algorithm Applied to Knapsack Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this