A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem

José García, José Lemus-Romani, Francisco Altimiras, Broderick Crawford, Ricardo Soto, Marcelo Becerra-Rozas, Paola Moraga, Alex Paz Becerra, Alvaro Peña Fritz, Jose-Miguel Rubio and Gino Astorga
Additional contact information
José García: Escuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile
José Lemus-Romani: Escuela de Construcción Civil, Pontificia Universidad Católica de Chile, Santiago 7820436, Chile
Francisco Altimiras: Facultad de Ingeniería y Negocios, Universidad de las Américas, Santiago 7500975, Chile
Broderick Crawford: Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile
Ricardo Soto: Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile
Marcelo Becerra-Rozas: Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile
Paola Moraga: Escuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile
Alex Paz Becerra: Escuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile
Alvaro Peña Fritz: Escuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, Chile
Jose-Miguel Rubio: Facultad de Ingeniería, Ciencia y Tecnología, Universidad Bernardo O’Higgins Santiago, Metropolitana 8370993, Chile
Gino Astorga: Escuela de Negocios Internacionales, Universidad de Valparaíso, Viña del Mar 2572048, Chile

Mathematics, 2021, vol. 9, issue 20, 1-19

Abstract: Optimization techniques, specially metaheuristics, are constantly refined in order to decrease execution times, increase the quality of solutions, and address larger target cases. Hybridizing techniques are one of these strategies that are particularly noteworthy due to the breadth of applications. In this article, a hybrid algorithm is proposed that integrates the k-means algorithm to generate a binary version of the cuckoo search technique, and this is strengthened by a local search operator. The binary cuckoo search algorithm is applied to the NP -hard Set-Union Knapsack Problem. This problem has recently attracted great attention from the operational research community due to the breadth of its applications and the difficulty it presents in solving medium and large instances. Numerical experiments were conducted to gain insight into the contribution of the final results of the k-means technique and the local search operator. Furthermore, a comparison to state-of-the-art algorithms is made. The results demonstrate that the hybrid algorithm consistently produces superior results in the majority of the analyzed medium instances, and its performance is competitive, but degrades in large instances.

Keywords: combinatorial optimization; machine learning; metaheuristics; set-union knapsack (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/9/20/2611/pdf (application/pdf)
https://www.mdpi.com/2227-7390/9/20/2611/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:9:y:2021:i:20:p:2611-:d:658091

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().