A K-means Grasshopper Algorithm Applied to the Knapsack Problem

HERNAN ANDRES PINTO ARANCET, ALVARO RODRIGO PEÑA FRITZ, Leonardo Causa, Matías Valenzuela, Gabriel Villavicencio

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

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 languageEnglish
Title of host publicationArtificial Intelligence and Bioinspired Computational Methods - Proceedings of the 9th Computer Science On-line Conference, CSOC 2020
EditorsRadek Silhavy
PublisherSpringer
Pages234-244
Number of pages11
ISBN (Print)9783030519704
DOIs
StatePublished - 2020
Externally publishedYes
Event9th Computer Science On-line Conference, CSOC 2020 - Zlin, Czech Republic
Duration: 15 Jul 202015 Jul 2020

Publication series

NameAdvances in Intelligent Systems and Computing
Volume1225 AISC
ISSN (Print)2194-5357
ISSN (Electronic)2194-5365

Conference

Conference9th Computer Science On-line Conference, CSOC 2020
CountryCzech Republic
CityZlin
Period15/07/2015/07/20

Keywords

  • Combinatorial optimization
  • K-means
  • KnapSack
  • Metaheuristics

Fingerprint Dive into the research topics of 'A K-means Grasshopper Algorithm Applied to the Knapsack Problem'. Together they form a unique fingerprint.

Cite this