IDEAS home Printed from https://ideas.repec.org/a/gam/jmathe/v9y2021i20p2611-d658091.html
   My bibliography  Save this article

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

Author

Listed:
  • 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)

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.

Suggested Citation

  • 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 Astor, 2021. "A Binary Machine Learning Cuckoo Search Algorithm Improved by a Local Search Operator for the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 9(20), pages 1-19, October.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:20:p:2611-:d:658091
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/9/20/2611/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/9/20/2611/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Adil Baykasoğlu & Fehmi Burcin Ozsoydan & M. Emre Senol, 2020. "Weighted superposition attraction algorithm for binary optimization problems," Operational Research, Springer, vol. 20(4), pages 2555-2581, December.
    2. José García & Gino Astorga & Víctor Yepes, 2021. "An Analysis of a KNN Perturbation Operator: An Application to the Binarization of Continuous Metaheuristics," Mathematics, MDPI, vol. 9(3), pages 1-20, January.
    3. Broderick Crawford & Ricardo Soto & Gino Astorga & José García & Carlos Castro & Fernando Paredes, 2017. "Putting Continuous Metaheuristics to Work in Binary Search Spaces," Complexity, Hindawi, vol. 2017, pages 1-19, May.
    4. El-Ghazali Talbi, 2016. "Combining metaheuristics with mathematical programming, constraint programming and machine learning," Annals of Operations Research, Springer, vol. 240(1), pages 171-215, May.
    5. Daniel Schermer, 2019. "Integration of Drones in Last-Mile Delivery: The Vehicle Routing Problem with Drones," Operations Research Proceedings, in: Bernard Fortz & Martine Labbé (ed.), Operations Research Proceedings 2018, pages 17-22, Springer.
    6. Yang, Xinan & Vernitski, Alexei & Carrea, Laura, 2016. "An approximate dynamic programming approach for improving accuracy of lossy data compression by Bloom filters," European Journal of Operational Research, Elsevier, vol. 252(3), pages 985-994.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Marcelo Becerra-Rozas & José Lemus-Romani & Felipe Cisternas-Caneo & Broderick Crawford & Ricardo Soto & Gino Astorga & Carlos Castro & José García, 2022. "Continuous Metaheuristics for Binary Optimization Problems: An Updated Systematic Literature Review," Mathematics, MDPI, vol. 11(1), pages 1-32, December.
    2. José García & Victor Yepes & José V. Martí, 2020. "A Hybrid k-Means Cuckoo Search Algorithm Applied to the Counterfort Retaining Walls Problem," Mathematics, MDPI, vol. 8(4), pages 1-22, April.
    3. José García & José V. Martí & Víctor Yepes, 2020. "The Buttressed Walls Problem: An Application of a Hybrid Clustering Particle Swarm Optimization Algorithm," Mathematics, MDPI, vol. 8(6), pages 1-22, May.
    4. José García & Paola Moraga & Matias Valenzuela & Hernan Pinto, 2020. "A db-Scan Hybrid Algorithm: An Application to the Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 8(4), pages 1-22, April.
    5. José García & Paola Moraga & Broderick Crawford & Ricardo Soto & Hernan Pinto, 2022. "Binarization Technique Comparisons of Swarm Intelligence Algorithm: An Application to the Multi-Demand Multidimensional Knapsack Problem," Mathematics, MDPI, vol. 10(17), pages 1-20, September.
    6. José García & Gino Astorga & Víctor Yepes, 2021. "An Analysis of a KNN Perturbation Operator: An Application to the Binarization of Continuous Metaheuristics," Mathematics, MDPI, vol. 9(3), pages 1-20, January.
    7. Kloster, Konstantin & Moeini, Mahdi & Vigo, Daniele & Wendt, Oliver, 2023. "The multiple traveling salesman problem in presence of drone- and robot-supported packet stations," European Journal of Operational Research, Elsevier, vol. 305(2), pages 630-643.
    8. Michael J. Ryoba & Shaojian Qu & Yongyi Zhou, 2021. "Feature subset selection for predicting the success of crowdfunding project campaigns," Electronic Markets, Springer;IIM University of St. Gallen, vol. 31(3), pages 671-684, September.
    9. Franco Peschiera & Robert Dell & Johannes Royset & Alain Haït & Nicolas Dupin & Olga Battaïa, 2021. "A novel solution approach with ML-based pseudo-cuts for the Flight and Maintenance Planning problem," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 43(3), pages 635-664, September.
    10. Václavík, Roman & Novák, Antonín & Šůcha, Přemysl & Hanzálek, Zdeněk, 2018. "Accelerating the Branch-and-Price Algorithm Using Machine Learning," European Journal of Operational Research, Elsevier, vol. 271(3), pages 1055-1069.
    11. José García & Andres Leiva-Araos & Broderick Crawford & Ricardo Soto & Hernan Pinto, 2023. "Exploring Initialization Strategies for Metaheuristic Optimization: Case Study of the Set-Union Knapsack Problem," Mathematics, MDPI, vol. 11(12), pages 1-20, June.
    12. Giuseppe Fragapane & Dmitry Ivanov & Mirco Peron & Fabio Sgarbossa & Jan Ola Strandhagen, 2022. "Increasing flexibility and productivity in Industry 4.0 production networks with autonomous mobile robots and smart intralogistics," Annals of Operations Research, Springer, vol. 308(1), pages 125-143, January.
    13. Lorena Pradenas & Marco Fuentes & Víctor Parada, 2020. "Optimizing waste storage areas in health care centers," Annals of Operations Research, Springer, vol. 295(1), pages 503-516, December.
    14. Paulo Figueroa-Torrez & Orlando Durán & Broderick Crawford & Felipe Cisternas-Caneo, 2023. "A Binary Black Widow Optimization Algorithm for Addressing the Cell Formation Problem Involving Alternative Routes and Machine Reliability," Mathematics, MDPI, vol. 11(16), pages 1-23, August.
    15. José Lemus-Romani & Marcelo Becerra-Rozas & Broderick Crawford & Ricardo Soto & Felipe Cisternas-Caneo & Emanuel Vega & Mauricio Castillo & Diego Tapia & Gino Astorga & Wenceslao Palma & Carlos Castro, 2021. "A Novel Learning-Based Binarization Scheme Selector for Swarm Algorithms Solving Combinatorial Problems," Mathematics, MDPI, vol. 9(22), pages 1-41, November.
    16. Sergio Valdivia & Ricardo Soto & Broderick Crawford & Nicolás Caselli & Fernando Paredes & Carlos Castro & Rodrigo Olivares, 2020. "Clustering-Based Binarization Methods Applied to the Crow Search Algorithm for 0/1 Combinatorial Problems," Mathematics, MDPI, vol. 8(7), pages 1-42, July.
    17. Emanuel Vega & Ricardo Soto & Broderick Crawford & Javier Peña & Carlos Castro, 2021. "A Learning-Based Hybrid Framework for Dynamic Balancing of Exploration-Exploitation: Combining Regression Analysis and Metaheuristics," Mathematics, MDPI, vol. 9(16), pages 1-23, August.
    18. Sunhyung Yoo & Jinwoo Brian Lee & Hoon Han, 2023. "A Reinforcement Learning approach for bus network design and frequency setting optimisation," Public Transport, Springer, vol. 15(2), pages 503-534, June.
    19. Yulia Sullivan & Marc Bourmont & Mary Dunaway, 2022. "Appraisals of harms and injustice trigger an eerie feeling that decreases trust in artificial intelligence systems," Annals of Operations Research, Springer, vol. 308(1), pages 525-548, January.
    20. Vicencio-Medina, Salvador J. & Rios-Solis, Yasmin A. & Ibarra-Rojas, Omar Jorge & Cid-Garcia, Nestor M. & Rios-Solis, Leonardo, 2023. "The maximal covering location problem with accessibility indicators and mobile units," Socio-Economic Planning Sciences, Elsevier, vol. 87(PB).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:gam:jmathe:v:9:y:2021:i:20:p:2611-:d:658091. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: MDPI Indexing Manager (email available below). General contact details of provider: https://www.mdpi.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.