A K-means Grasshopper Algorithm Applied to the Knapsack Problem

Hernan Pinto; Alvaro Peña; Leonardo Causa; Matías Valenzuela; Gabriel Villavicencio

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

A K-means Grasshopper Algorithm Applied to the Knapsack Problem

Hernan Pinto, Alvaro Peña, Leonardo Causa, Matías Valenzuela, Gabriel Villavicencio

SCHOOL OF CONSTRUCTION ENGINEERING

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

1 Scopus citations

Abstract

In engineering and science, there are many combinatorial optimization problems. A lot of these problems are NP-hard and can hardly be addressed by full techniques. Therefore, designing binary algorithms based on swarm intelligence continuous metaheuristics is an area of interest in operational research. In this paper we use a general binarization mechanism based on the k-means technique. We apply the k-means technique to grasshopper algorithm to solve multidimensional knapsack problem (MKP). Experiments are designed to demonstrate the utility of the k-means technique in binarization. Additionally we verify the efficiency of our algorithm through benchmark instances, showing that binary k-means grasshopper algorithm (BKGOA) obtains adequate results when it is evaluated against another state of the art algorithm.

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	234-244
Number of pages	11
ISBN (Print)	9783030519704
DOIs	https://doi.org/10.1007/978-3-030-51971-1_19
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
K-means
KnapSack
Metaheuristics

Access to Document

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

Cite this

Pinto, H., Peña, A., Causa, L., Valenzuela, M., & Villavicencio, G. (2020). A K-means Grasshopper Algorithm Applied to the Knapsack Problem. In R. Silhavy (Ed.), Artificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020 (pp. 234-244). (Advances in Intelligent Systems and Computing; Vol. 1225 AISC). Springer. https://doi.org/10.1007/978-3-030-51971-1_19

@inproceedings{fec6ad50a1c94782ba02bc3b8bdd65a4,

title = "A K-means Grasshopper Algorithm Applied to the Knapsack Problem",

abstract = "In engineering and science, there are many combinatorial optimization problems. A lot of these problems are NP-hard and can hardly be addressed by full techniques. Therefore, designing binary algorithms based on swarm intelligence continuous metaheuristics is an area of interest in operational research. In this paper we use a general binarization mechanism based on the k-means technique. We apply the k-means technique to grasshopper algorithm to solve multidimensional knapsack problem (MKP). Experiments are designed to demonstrate the utility of the k-means technique in binarization. Additionally we verify the efficiency of our algorithm through benchmark instances, showing that binary k-means grasshopper algorithm (BKGOA) obtains adequate results when it is evaluated against another state of the art algorithm.",

keywords = "Combinatorial optimization, K-means, KnapSack, Metaheuristics",

author = "Hernan Pinto and Alvaro Pe{\~n}a and Leonardo Causa and Mat{\'i}as Valenzuela and Gabriel Villavicencio",

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

language = "English",

isbn = "9783030519704",

series = "Advances in Intelligent Systems and Computing",

publisher = "Springer",

pages = "234--244",

editor = "Radek Silhavy",

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

}

Pinto, H , Peña, A, Causa, L, Valenzuela, M & Villavicencio, G 2020, A K-means Grasshopper Algorithm Applied to the 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. 234-244, 9th Computer Science On-line Conference, CSOC 2020, Zlin, Czech Republic, 15/07/20. https://doi.org/10.1007/978-3-030-51971-1_19

A K-means Grasshopper Algorithm Applied to the Knapsack Problem. / Pinto, Hernan ; Peña, Alvaro; 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. 234-244 (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 K-means Grasshopper Algorithm Applied to the Knapsack Problem

AU - Pinto, Hernan

AU - Peña, Alvaro

AU - Causa, Leonardo

AU - Valenzuela, Matías

AU - Villavicencio, Gabriel

PY - 2020

Y1 - 2020

N2 - In engineering and science, there are many combinatorial optimization problems. A lot of these problems are NP-hard and can hardly be addressed by full techniques. Therefore, designing binary algorithms based on swarm intelligence continuous metaheuristics is an area of interest in operational research. In this paper we use a general binarization mechanism based on the k-means technique. We apply the k-means technique to grasshopper algorithm to solve multidimensional knapsack problem (MKP). Experiments are designed to demonstrate the utility of the k-means technique in binarization. Additionally we verify the efficiency of our algorithm through benchmark instances, showing that binary k-means grasshopper algorithm (BKGOA) obtains adequate results when it is evaluated against another state of the art algorithm.

AB - In engineering and science, there are many combinatorial optimization problems. A lot of these problems are NP-hard and can hardly be addressed by full techniques. Therefore, designing binary algorithms based on swarm intelligence continuous metaheuristics is an area of interest in operational research. In this paper we use a general binarization mechanism based on the k-means technique. We apply the k-means technique to grasshopper algorithm to solve multidimensional knapsack problem (MKP). Experiments are designed to demonstrate the utility of the k-means technique in binarization. Additionally we verify the efficiency of our algorithm through benchmark instances, showing that binary k-means grasshopper algorithm (BKGOA) obtains adequate results when it is evaluated against another state of the art algorithm.

KW - Combinatorial optimization

KW - K-means

KW - KnapSack

KW - Metaheuristics

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

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

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

M3 - Conference contribution

AN - SCOPUS:85089718478

SN - 9783030519704

T3 - Advances in Intelligent Systems and Computing

SP - 234

EP - 244

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 -

Pinto H , Peña A, Causa L, Valenzuela M, Villavicencio G. A K-means Grasshopper Algorithm Applied to the 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. 234-244. (Advances in Intelligent Systems and Computing). doi: 10.1007/978-3-030-51971-1_19

A K-means Grasshopper Algorithm Applied to the Knapsack Problem

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this