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

Swarm-Inspired Computing to Solve Binary Optimization Problems: A Backward Q-Learning Binarization Scheme Selector

Author

Listed:
  • Marcelo Becerra-Rozas

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • José Lemus-Romani

    (Escuela de Construcción Civil, Pontificia Universidad Católica de Chile, Avenida Vicuña Mackenna 4860, Macul, Santiago 7820436, Chile)

  • Felipe Cisternas-Caneo

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • Broderick Crawford

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • Ricardo Soto

    (Escuela de Ingeniería Informática, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2241, Valparaíso 2362807, Chile)

  • José García

    (Escuela de Ingeniería de Construcción y Transporte, Pontificia Universidad Católica de Valparaíso, Avenida Brasil 2147, Valparaíso 2362807, Chile)

Abstract

In recent years, continuous metaheuristics have been a trend in solving binary-based combinatorial problems due to their good results. However, to use this type of metaheuristics, it is necessary to adapt them to work in binary environments, and in general, this adaptation is not trivial. The method proposed in this work evaluates the use of reinforcement learning techniques in the binarization process. Specifically, the backward Q-learning technique is explored to choose binarization schemes intelligently. This allows any continuous metaheuristic to be adapted to binary environments. The illustrated results are competitive, thus providing a novel option to address different complex problems in the industry.

Suggested Citation

  • Marcelo Becerra-Rozas & José Lemus-Romani & Felipe Cisternas-Caneo & Broderick Crawford & Ricardo Soto & José García, 2022. "Swarm-Inspired Computing to Solve Binary Optimization Problems: A Backward Q-Learning Binarization Scheme Selector," Mathematics, MDPI, vol. 10(24), pages 1-30, December.
    • Handle: RePEc:gam:jmathe:v:10:y:2022:i:24:p:4776-:d:1004673
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/10/24/4776/pdf
    Download Restriction: no
    File URL: https://www.mdpi.com/2227-7390/10/24/4776/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Tiande Guo & Congying Han & Siqi Tang & Man Ding, 2019. "Solving Combinatorial Problems with Machine Learning Methods," Springer Optimization and Its Applications, in: Ding-Zhu Du & Panos M. Pardalos & Zhao Zhang (ed.), Nonlinear Combinatorial Optimization, pages 207-229, Springer.
    2. 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.
    3. Haoran Zhao & Sen Guo & Huiru Zhao, 2017. "Energy-Related CO 2 Emissions Forecasting Using an Improved LSSVM Model Optimized by Whale Optimization Algorithm," Energies, MDPI, vol. 10(7), pages 1-15, June.
    4. Y.C. Ho & D.L. Pepyne, 2002. "Simple Explanation of the No-Free-Lunch Theorem and Its Implications," Journal of Optimization Theory and Applications, Springer, vol. 115(3), pages 549-570, December.
    5. Shu-Xia Li & Jie-Sheng Wang, 2015. "Dynamic Modeling of Steam Condenser and Design of PI Controller Based on Grey Wolf Optimizer," Mathematical Problems in Engineering, Hindawi, vol. 2015, pages 1-9, December.
    6. Beasley, J. E. & Jornsten, K., 1992. "Enhancing an algorithm for set covering problems," European Journal of Operational Research, Elsevier, vol. 58(2), pages 293-300, April.
    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 & 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.
    3. Beasley, J. E. & Chu, P. C., 1996. "A genetic algorithm for the set covering problem," European Journal of Operational Research, Elsevier, vol. 94(2), pages 392-404, October.
    4. Shuyu Dai & Dongxiao Niu & Yaru Han, 2018. "Forecasting of Energy-Related CO 2 Emissions in China Based on GM(1,1) and Least Squares Support Vector Machine Optimized by Modified Shuffled Frog Leaping Algorithm for Sustainability," Sustainability, MDPI, vol. 10(4), pages 1-17, March.
    5. Lawrence Bodin & Aristide Mingozzi & Roberto Baldacci & Michael Ball, 2000. "The Rollon–Rolloff Vehicle Routing Problem," Transportation Science, INFORMS, vol. 34(3), pages 271-288, August.
    6. Lan, Guanghui & DePuy, Gail W. & Whitehouse, Gary E., 2007. "An effective and simple heuristic for the set covering problem," European Journal of Operational Research, Elsevier, vol. 176(3), pages 1387-1403, February.
    7. 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.
    8. 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.
    9. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    10. Yuhong Zhao & Ruirui Liu & Zhansheng Liu & Liang Liu & Jingjing Wang & Wenxiang Liu, 2023. "A Review of Macroscopic Carbon Emission Prediction Model Based on Machine Learning," Sustainability, MDPI, vol. 15(8), pages 1-28, April.
    11. Wang, Yiyuan & Pan, Shiwei & Al-Shihabi, Sameh & Zhou, Junping & Yang, Nan & Yin, Minghao, 2021. "An improved configuration checking-based algorithm for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 294(2), pages 476-491.
    12. Ferdinando Pezzella & Enrico Faggioli, 1997. "Solving large set covering problems for crew scheduling," TOP: An Official Journal of the Spanish Society of Statistics and Operations Research, Springer;Sociedad de Estadística e Investigación Operativa, vol. 5(1), pages 41-59, June.
    13. Modiri-Delshad, Mostafa & Aghay Kaboli, S. Hr. & Taslimi-Renani, Ehsan & Rahim, Nasrudin Abd, 2016. "Backtracking search algorithm for solving economic dispatch problems with valve-point effects and multiple fuel options," Energy, Elsevier, vol. 116(P1), pages 637-649.
    14. 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.
    15. Ola G. El‐Taliawi & Nihit Goyal & Michael Howlett, 2021. "Holding out the promise of Lasswell's dream: Big data analytics in public policy research and teaching," Review of Policy Research, Policy Studies Organization, vol. 38(6), pages 640-660, November.
    16. Bergantiños, Gustavo & Gómez-Rúa, María & Llorca, Natividad & Pulido, Manuel & Sánchez-Soriano, Joaquín, 2020. "Allocating costs in set covering problems," European Journal of Operational Research, Elsevier, vol. 284(3), pages 1074-1087.
    17. Nguyen, Tri-Dung, 2014. "A fast approximation algorithm for solving the complete set packing problem," European Journal of Operational Research, Elsevier, vol. 237(1), pages 62-70.
    18. 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.
    19. 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.
    20. 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.

    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:10:y:2022:i:24:p:4776-:d:1004673. 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.