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

Clustering-Based Binarization Methods Applied to the Crow Search Algorithm for 0/1 Combinatorial Problems

Author

Listed:
  • Sergio Valdivia

    (Dirección de Tecnologías de Información y Comunicación, Universidad de Valparaíso, 2361864 Valparaíso, Chile)

  • Ricardo Soto

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

  • Broderick Crawford

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

  • Nicolás Caselli

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

  • Fernando Paredes

    (Escuela de Ingeniería Industrial, Universidad Diego Portales, 8370109 Santiago, Chile)

  • Carlos Castro

    (Departamento de Informática, Universidad Técnica Federico Santa Maria, 2390123 Valparaíso, Chile)

  • Rodrigo Olivares

    (Escuela de Ingeniería Informática, Universidad de Valparaíso, 2362905 Valparaíso, Chile)

Abstract

Metaheuristics are smart problem solvers devoted to tackling particularly large optimization problems. During the last 20 years, they have largely been used to solve different problems from the academic as well as from the real-world. However, most of them have originally been designed for operating over real domain variables, being necessary to tailor its internal core, for instance, to be effective in a binary space of solutions. Various works have demonstrated that this internal modification, known as binarization, is not a simple task, since the several existing binarization ways may lead to very different results. This of course forces the user to implement and analyze a large list of binarization schemas for reaching good results. In this paper, we explore two efficient clustering methods, namely KMeans and DBscan to alter a metaheuristic in order to improve it, and thus do not require on the knowledge of an expert user for identifying which binarization strategy works better during the run. Both techniques have widely been applied to solve clustering problems, allowing us to exploit useful information gathered during the search to efficiently control and improve the binarization process. We integrate those techniques to a recent metaheuristic called Crow Search, and we conduct experiments where KMeans and DBscan are contrasted to 32 different binarization methods. The results show that the proposed approaches outperform most of the binarization strategies for a large list of well-known optimization instances.

Suggested Citation

  • 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.
  • Handle: RePEc:gam:jmathe:v:8:y:2020:i:7:p:1070-:d:379345
    as

    Download full text from publisher

    File URL: https://www.mdpi.com/2227-7390/8/7/1070/pdf
    Download Restriction: no

    File URL: https://www.mdpi.com/2227-7390/8/7/1070/
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Luis Hernández & Carlos Baladrón & Javier M. Aguiar & Belén Carro & Antonio Sánchez-Esguevillas, 2012. "Classification and Clustering of Electricity Demand Patterns in Industrial Parks," Energies, MDPI, vol. 5(12), pages 1-14, December.
    2. Constantine Toregas & Ralph Swain & Charles ReVelle & Lawrence Bergman, 1971. "The Location of Emergency Service Facilities," Operations Research, INFORMS, vol. 19(6), pages 1363-1373, October.
    3. Roberto Battiti & Mauro Brunato, 2010. "Reactive Search Optimization: Learning While Optimizing," International Series in Operations Research & Management Science, in: Michel Gendreau & Jean-Yves Potvin (ed.), Handbook of Metaheuristics, chapter 0, pages 543-571, Springer.
    4. 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.
    5. Vasko, Francis J. & Wolf, Floyd E. & Stott, Kenneth L., 1989. "A set covering approach to metallurgical grade assignment," European Journal of Operational Research, Elsevier, vol. 38(1), pages 27-34, January.
    6. Xiaoyu Li & Kai Song & Guo Wei & Rengui Lu & Chunbo Zhu, 2015. "A Novel Grouping Method for Lithium Iron Phosphate Batteries Based on a Fractional Joint Kalman Filter and a New Modified K-Means Clustering Algorithm," Energies, MDPI, vol. 8(8), pages 1-26, July.
    7. Alberto Caprara & Matteo Fischetti & Paolo Toth, 1999. "A Heuristic Method for the Set Covering Problem," Operations Research, INFORMS, vol. 47(5), pages 730-743, October.
    8. Salah Bouktif & Ali Fiaz & Ali Ouni & Mohamed Adel Serhani, 2020. "Multi-Sequence LSTM-RNN Deep Learning and Metaheuristics for Electric Load Forecasting," Energies, MDPI, vol. 13(2), pages 1-21, January.
    9. Chunyan Fu & Susu Cheng & Yongxi Yi, 2019. "Dynamic Control of Product Innovation, Advertising Effort, and Strategic Transfer-Pricing in a Marketing-Operations Interface," Mathematical Problems in Engineering, Hindawi, vol. 2019, pages 1-14, February.
    10. Alberto Caprara & Paolo Toth & Matteo Fischetti, 2000. "Algorithms for the Set Covering Problem," Annals of Operations Research, Springer, vol. 98(1), pages 353-371, December.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Fabián Riquelme & Francisco Muñoz & Rodrigo Olivares, 2023. "A depth-based heuristic to solve the multi-objective influence spread problem using particle swarm optimization," OPSEARCH, Springer;Operational Research Society of India, vol. 60(3), pages 1267-1285, September.

    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. Nicolás Caselli & Ricardo Soto & Broderick Crawford & Sergio Valdivia & Rodrigo Olivares, 2021. "A Self-Adaptive Cuckoo Search Algorithm Using a Machine Learning Technique," Mathematics, MDPI, vol. 9(16), pages 1-28, August.
    2. İbrahim Muter & Ş. İlker Birbil & Güvenç Şahin, 2010. "Combination of Metaheuristic and Exact Algorithms for Solving Set Covering-Type Optimization Problems," INFORMS Journal on Computing, INFORMS, vol. 22(4), pages 603-619, November.
    3. 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.
    4. Masoud Yaghini & Mohammad Karimi & Mohadeseh Rahbar, 2015. "A set covering approach for multi-depot train driver scheduling," Journal of Combinatorial Optimization, Springer, vol. 29(3), pages 636-654, April.
    5. Murray, Alan T., 2001. "Strategic analysis of public transport coverage," Socio-Economic Planning Sciences, Elsevier, vol. 35(3), pages 175-188, September.
    6. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    7. Marco E. Lübbecke & Jacques Desrosiers, 2005. "Selected Topics in Column Generation," Operations Research, INFORMS, vol. 53(6), pages 1007-1023, December.
    8. Otto, Alena & Tilk, Christian, 2024. "Intelligent design of sensor networks for data-driven sensor maintenance at railways," Omega, Elsevier, vol. 127(C).
    9. Shane N. Hall & Sheldon H. Jacobson & Edward C. Sewell, 2008. "An Analysis of Pediatric Vaccine Formulary Selection Problems," Operations Research, INFORMS, vol. 56(6), pages 1348-1365, December.
    10. Amadeu A. Coco & Andréa Cynthia Santos & Thiago F. Noronha, 2022. "Robust min-max regret covering problems," Computational Optimization and Applications, Springer, vol. 83(1), pages 111-141, September.
    11. Bautista, Joaquín & Pereira, Jordi, 2006. "Modeling the problem of locating collection areas for urban waste management. An application to the metropolitan area of Barcelona," Omega, Elsevier, vol. 34(6), pages 617-629, December.
    12. João Vitor Leme & Wallace Casaca & Marilaine Colnago & Maurício Araújo Dias, 2020. "Towards Assessing the Electricity Demand in Brazil: Data-Driven Analysis and Ensemble Learning Models," Energies, MDPI, vol. 13(6), pages 1-20, March.
    13. Dimitris Bertsimas & Dan A. Iancu & Dmitriy Katz, 2013. "A New Local Search Algorithm for Binary Optimization," INFORMS Journal on Computing, INFORMS, vol. 25(2), pages 208-221, May.
    14. Naji-Azimi, Zahra & Toth, Paolo & Galli, Laura, 2010. "An electromagnetism metaheuristic for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 205(2), pages 290-300, September.
    15. Marianov, Vladimir & Eiselt, H.A., 2024. "Fifty Years of Location Theory - A Selective Review," European Journal of Operational Research, Elsevier, vol. 318(3), pages 701-718.
    16. Li, Shengyin & Huang, Yongxi, 2014. "Heuristic approaches for the flow-based set covering problem with deviation paths," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 72(C), pages 144-158.
    17. Ran Wei & Alan Murray & Rajan Batta, 2014. "A bounding-based solution approach for the continuous arc covering problem," Journal of Geographical Systems, Springer, vol. 16(2), pages 161-182, April.
    18. Gao, Chao & Yao, Xin & Weise, Thomas & Li, Jinlong, 2015. "An efficient local search heuristic with row weighting for the unicost set covering problem," European Journal of Operational Research, Elsevier, vol. 246(3), pages 750-761.
    19. Rongbing Huang & Seokjin Kim & Mozart Menezes, 2010. "Facility location for large-scale emergencies," Annals of Operations Research, Springer, vol. 181(1), pages 271-286, December.
    20. Marín, Alfredo & Martínez-Merino, Luisa I. & Rodríguez-Chía, Antonio M. & Saldanha-da-Gama, Francisco, 2018. "Multi-period stochastic covering location problems: Modeling framework and solution approach," European Journal of Operational Research, Elsevier, vol. 268(2), pages 432-449.

    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:8:y:2020:i:7:p:1070-:d:379345. 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.