A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem
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....
| Main Authors: | , , , , , , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2021-10-01
|
| Series: | Mathematics |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2227-7390/9/20/2611 |
| _version_ | 1797513966446968832 |
|---|---|
| author | 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 Gino Astorga |
| author_facet | 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 Gino Astorga |
| author_sort | José García |
| collection | DOAJ |
| description | 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">NP</mi></semantics></math></inline-formula>-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. |
| first_indexed | 2024-03-10T06:24:59Z |
| format | Article |
| id | doaj.art-6e71ed41fcab43e48c8d239a09e3224c |
| institution | Directory Open Access Journal |
| issn | 2227-7390 |
| language | English |
| last_indexed | 2024-03-10T06:24:59Z |
| publishDate | 2021-10-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Mathematics |
| spelling | doaj.art-6e71ed41fcab43e48c8d239a09e3224c2023-11-22T19:02:38ZengMDPI AGMathematics2227-73902021-10-01920261110.3390/math9202611A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack ProblemJosé García0José Lemus-Romani1Francisco Altimiras2Broderick Crawford3Ricardo Soto4Marcelo Becerra-Rozas5Paola Moraga6Alex Paz Becerra7Alvaro Peña Fritz8Jose-Miguel Rubio9Gino Astorga10Escuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, ChileEscuela de Construcción Civil, Pontificia Universidad Católica de Chile, Santiago 7820436, ChileFacultad de Ingeniería y Negocios, Universidad de las Américas, Santiago 7500975, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, ChileEscuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, ChileEscuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, ChileEscuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362804, ChileFacultad de Ingeniería, Ciencia y Tecnología, Universidad Bernardo O’Higgins Santiago, Metropolitana 8370993, ChileEscuela de Negocios Internacionales, Universidad de Valparaíso, Viña del Mar 2572048, ChileOptimization 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 <inline-formula><math xmlns="http://www.w3.org/1998/Math/MathML" display="inline"><semantics><mi mathvariant="script">NP</mi></semantics></math></inline-formula>-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.https://www.mdpi.com/2227-7390/9/20/2611combinatorial optimizationmachine learningmetaheuristicsset-union knapsack |
| spellingShingle | 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 Gino Astorga A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem Mathematics combinatorial optimization machine learning metaheuristics set-union knapsack |
| title | A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem |
| title_full | A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem |
| title_fullStr | A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem |
| title_full_unstemmed | A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem |
| title_short | A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem |
| title_sort | binary machine learning cuckoo search algorithm improved by a local search operator for the set union knapsack problem |
| topic | combinatorial optimization machine learning metaheuristics set-union knapsack |
| url | https://www.mdpi.com/2227-7390/9/20/2611 |
| work_keys_str_mv | AT josegarcia abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT joselemusromani abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT franciscoaltimiras abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT broderickcrawford abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT ricardosoto abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT marcelobecerrarozas abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT paolamoraga abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT alexpazbecerra abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT alvaropenafritz abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT josemiguelrubio abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT ginoastorga abinarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT josegarcia binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT joselemusromani binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT franciscoaltimiras binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT broderickcrawford binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT ricardosoto binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT marcelobecerrarozas binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT paolamoraga binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT alexpazbecerra binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT alvaropenafritz binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT josemiguelrubio binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem AT ginoastorga binarymachinelearningcuckoosearchalgorithmimprovedbyalocalsearchoperatorforthesetunionknapsackproblem |