Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches

Camilo Vásquez; José Lemus-Romani; Broderick Crawford; Ricardo Soto; Gino Astorga; Wenceslao Palma; Sanjay Misra; Fernando Paredes

doi:10.1007/978-3-030-58817-5_38

Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches

Camilo Vásquez, José Lemus-Romani, Broderick Crawford, Ricardo Soto, Gino Astorga, Wenceslao Palma, Sanjay Misra, Fernando Paredes

SCHOOL OF COMPUTER ENGINEERING

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

3 Scopus citations

Abstract

Metaheuristics are used to solve high complexity problems, where resolution by exact methods is not a viable option since the resolution time when using these exact methods is not acceptable. Most metaheuristics are defined to solve problems of continuous optimization, which forces these algorithms to adapt its work in the discrete domain using discretization techniques to solve complex problems. This paper proposes data-driven binarization approaches based on clustering techniques. We solve different instances of Knapsack Problems with Galactic Swarm Optimization algorithm using this machine learning techniques.

Original language	English
Title of host publication	Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings
Editors	Osvaldo Gervasi, Beniamino Murgante, Sanjay Misra, Chiara Garau, Ivan Blecic, David Taniar, Bernady O. Apduhan, Ana Maria A.C. Rocha, Eufemia Tarantino, Carmelo Maria Torre, Yeliz Karaca
Publisher	Springer Science and Business Media Deutschland GmbH
Pages	511-526
Number of pages	16
ISBN (Print)	9783030588168
DOIs	https://doi.org/10.1007/978-3-030-58817-5_38
State	Published - 2020
Event	20th International Conference on Computational Science and Its Applications, ICCSA 2020 - Cagliari, Italy Duration: 1 Jul 2020 → 4 Jul 2020

Publication series

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

Conference

Conference	20th International Conference on Computational Science and Its Applications, ICCSA 2020
Country/Territory	Italy
City	Cagliari
Period	1/07/20 → 4/07/20

Keywords

DBSCAN
Galactic Swarm Optimization
K-means
Knapsack problem
Machine learning
Metaheuristic

Access to Document

10.1007/978-3-030-58817-5_38

Cite this

Vásquez, C., Lemus-Romani, J., Crawford, B., Soto, R., Astorga, G., Palma, W., Misra, S., & Paredes, F. (2020). Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches. In O. Gervasi, B. Murgante, S. Misra, C. Garau, I. Blecic, D. Taniar, B. O. Apduhan, A. M. A. C. Rocha, E. Tarantino, C. M. Torre, & Y. Karaca (Eds.), Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings (pp. 511-526). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12254 LNCS). Springer Science and Business Media Deutschland GmbH. https://doi.org/10.1007/978-3-030-58817-5_38

Vásquez, Camilo ; Lemus-Romani, José ; Crawford, Broderick et al. / Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches. Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings. editor / Osvaldo Gervasi ; Beniamino Murgante ; Sanjay Misra ; Chiara Garau ; Ivan Blecic ; David Taniar ; Bernady O. Apduhan ; Ana Maria A.C. Rocha ; Eufemia Tarantino ; Carmelo Maria Torre ; Yeliz Karaca. Springer Science and Business Media Deutschland GmbH, 2020. pp. 511-526 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{bd0037f836d14db6969463cc7fe4d91a,

title = "Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches",

abstract = "Metaheuristics are used to solve high complexity problems, where resolution by exact methods is not a viable option since the resolution time when using these exact methods is not acceptable. Most metaheuristics are defined to solve problems of continuous optimization, which forces these algorithms to adapt its work in the discrete domain using discretization techniques to solve complex problems. This paper proposes data-driven binarization approaches based on clustering techniques. We solve different instances of Knapsack Problems with Galactic Swarm Optimization algorithm using this machine learning techniques.",

keywords = "DBSCAN, Galactic Swarm Optimization, K-means, Knapsack problem, Machine learning, Metaheuristic",

author = "Camilo V{\'a}squez and Jos{\'e} Lemus-Romani and Broderick Crawford and Ricardo Soto and Gino Astorga and Wenceslao Palma and Sanjay Misra and Fernando Paredes",

note = "Publisher Copyright: {\textcopyright} 2020, Springer Nature Switzerland AG. Copyright: Copyright 2020 Elsevier B.V., All rights reserved.; 20th International Conference on Computational Science and Its Applications, ICCSA 2020 ; Conference date: 01-07-2020 Through 04-07-2020",

year = "2020",

doi = "10.1007/978-3-030-58817-5_38",

language = "English",

isbn = "9783030588168",

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

publisher = "Springer Science and Business Media Deutschland GmbH",

pages = "511--526",

editor = "Osvaldo Gervasi and Beniamino Murgante and Sanjay Misra and Chiara Garau and Ivan Blecic and David Taniar and Apduhan, {Bernady O.} and Rocha, {Ana Maria A.C.} and Eufemia Tarantino and Torre, {Carmelo Maria} and Yeliz Karaca",

booktitle = "Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings",

}

Vásquez, C, Lemus-Romani, J, Crawford, B , Soto, R, Astorga, G, Palma, W, Misra, S & Paredes, F 2020, Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches. in O Gervasi, B Murgante, S Misra, C Garau, I Blecic, D Taniar, BO Apduhan, AMAC Rocha, E Tarantino, CM Torre & Y Karaca (eds), Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 12254 LNCS, Springer Science and Business Media Deutschland GmbH, pp. 511-526, 20th International Conference on Computational Science and Its Applications, ICCSA 2020, Cagliari, Italy, 1/07/20. https://doi.org/10.1007/978-3-030-58817-5_38

Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches. / Vásquez, Camilo; Lemus-Romani, José; Crawford, Broderick et al.
Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings. ed. / Osvaldo Gervasi; Beniamino Murgante; Sanjay Misra; Chiara Garau; Ivan Blecic; David Taniar; Bernady O. Apduhan; Ana Maria A.C. Rocha; Eufemia Tarantino; Carmelo Maria Torre; Yeliz Karaca. Springer Science and Business Media Deutschland GmbH, 2020. p. 511-526 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 12254 LNCS).

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

TY - GEN

T1 - Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches

AU - Vásquez, Camilo

AU - Lemus-Romani, José

AU - Crawford, Broderick

AU - Soto, Ricardo

AU - Astorga, Gino

AU - Palma, Wenceslao

AU - Misra, Sanjay

AU - Paredes, Fernando

PY - 2020

Y1 - 2020

N2 - Metaheuristics are used to solve high complexity problems, where resolution by exact methods is not a viable option since the resolution time when using these exact methods is not acceptable. Most metaheuristics are defined to solve problems of continuous optimization, which forces these algorithms to adapt its work in the discrete domain using discretization techniques to solve complex problems. This paper proposes data-driven binarization approaches based on clustering techniques. We solve different instances of Knapsack Problems with Galactic Swarm Optimization algorithm using this machine learning techniques.

AB - Metaheuristics are used to solve high complexity problems, where resolution by exact methods is not a viable option since the resolution time when using these exact methods is not acceptable. Most metaheuristics are defined to solve problems of continuous optimization, which forces these algorithms to adapt its work in the discrete domain using discretization techniques to solve complex problems. This paper proposes data-driven binarization approaches based on clustering techniques. We solve different instances of Knapsack Problems with Galactic Swarm Optimization algorithm using this machine learning techniques.

KW - DBSCAN

KW - Galactic Swarm Optimization

KW - K-means

KW - Knapsack problem

KW - Machine learning

KW - Metaheuristic

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

U2 - 10.1007/978-3-030-58817-5_38

DO - 10.1007/978-3-030-58817-5_38

M3 - Conference contribution

AN - SCOPUS:85092672848

SN - 9783030588168

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

SP - 511

EP - 526

BT - Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings

A2 - Gervasi, Osvaldo

A2 - Murgante, Beniamino

A2 - Misra, Sanjay

A2 - Garau, Chiara

A2 - Blecic, Ivan

A2 - Taniar, David

A2 - Apduhan, Bernady O.

A2 - Rocha, Ana Maria A.C.

A2 - Tarantino, Eufemia

A2 - Torre, Carmelo Maria

A2 - Karaca, Yeliz

PB - Springer Science and Business Media Deutschland GmbH

T2 - 20th International Conference on Computational Science and Its Applications, ICCSA 2020

Y2 - 1 July 2020 through 4 July 2020

ER -

Vásquez C, Lemus-Romani J, Crawford B , Soto R, Astorga G, Palma W et al. Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches. In Gervasi O, Murgante B, Misra S, Garau C, Blecic I, Taniar D, Apduhan BO, Rocha AMAC, Tarantino E, Torre CM, Karaca Y, editors, Computational Science and Its Applications – ICCSA 2020 - 20th International Conference, Proceedings. Springer Science and Business Media Deutschland GmbH. 2020. p. 511-526. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-58817-5_38

Solving the 0/1 Knapsack Problem Using a Galactic Swarm Optimization with Data-Driven Binarization Approaches

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this