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

An Analysis of a KNN Perturbation Operator: An Application to the Binarization of Continuous Metaheuristics

Author

Listed:
  • José García

    (Escuela de Ingeniería en Construcción, Pontificia Universidad Católica de Valparaíso, Valparaíso 2362807, Chile
    These authors contributed equally to this work.)

  • Gino Astorga

    (Escuela de Negocios Internacionales, Universidad de Valparaíso, Valparaíso 2361864, Chile
    These authors contributed equally to this work.)

  • Víctor Yepes

    (Institute of Concrete Science and Technology (ICITECH), Universitat Politècnica de València, 46022 València, Spain
    These authors contributed equally to this work.)

Abstract

The optimization methods and, in particular, metaheuristics must be constantly improved to reduce execution times, improve the results, and thus be able to address broader instances. In particular, addressing combinatorial optimization problems is critical in the areas of operational research and engineering. In this work, a perturbation operator is proposed which uses the k-nearest neighbors technique, and this is studied with the aim of improving the diversification and intensification properties of metaheuristic algorithms in their binary version. Random operators are designed to study the contribution of the perturbation operator. To verify the proposal, large instances of the well-known set covering problem are studied. Box plots, convergence charts, and the Wilcoxon statistical test are used to determine the operator contribution. Furthermore, a comparison is made using metaheuristic techniques that use general binarization mechanisms such as transfer functions or db-scan as binarization methods. The results obtained indicate that the KNN perturbation operator improves significantly the results.

Suggested Citation

  • 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.
    • Handle: RePEc:gam:jmathe:v:9:y:2021:i:3:p:225-:d:486085
    as

    Download full text from publisher

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

    References listed on IDEAS

    as
    1. Yogesh Kumar & Shashi Kant Verma & Sandeep Sharma, 2020. "Quantum-inspired binary gravitational search algorithm to recognize the facial expressions," International Journal of Modern Physics C (IJMPC), World Scientific Publishing Co. Pte. Ltd., vol. 31(10), pages 1-24, October.
    2. Víctor Yepes & José V. Martí & José García, 2020. "Black Hole Algorithm for Sustainable Design of Counterfort Retaining Walls," Sustainability, MDPI, vol. 12(7), pages 1-18, April.
    3. Egon Balas & Maria C. Carrera, 1996. "A Dynamic Subgradient-Based Branch-and-Bound Procedure for Set Covering," Operations Research, INFORMS, vol. 44(6), pages 875-890, December.
    4. Hu Hu & Kan Yang & Lang Liu & Lyuwen Su & Zhe Yang, 2019. "Short-Term Hydropower Generation Scheduling Using an Improved Cloud Adaptive Quantum-Inspired Binary Social Spider Optimization Algorithm," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 33(7), pages 2357-2379, May.
    5. Beasley, J. E., 1987. "An algorithm for set covering problem," European Journal of Operational Research, Elsevier, vol. 31(1), pages 85-93, July.
    6. 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.
    7. Juan, Angel A. & Faulin, Javier & Grasman, Scott E. & Rabe, Markus & Figueira, Gonçalo, 2015. "A review of simheuristics: Extending metaheuristics to deal with stochastic combinatorial optimization problems," Operations Research Perspectives, Elsevier, vol. 2(C), pages 62-72.
    8. 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.
    9. Edmund K Burke & Michel Gendreau & Matthew Hyde & Graham Kendall & Gabriela Ochoa & Ender Özcan & Rong Qu, 2013. "Hyper-heuristics: a survey of the state of the art," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(12), pages 1695-1724, December.
    10. 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.
    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. 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.
    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. 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.

    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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. Patrizia Beraldi & Andrzej Ruszczyński, 2002. "The Probabilistic Set-Covering Problem," Operations Research, INFORMS, vol. 50(6), pages 956-967, December.
    6. 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.
    7. Victor Reyes & Ignacio Araya, 2021. "A GRASP-based scheme for the set covering problem," Operational Research, Springer, vol. 21(4), pages 2391-2408, December.
    8. 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.
    9. 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.
    10. 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.
    11. Helena R. Lourenço & José P. Paixão & Rita Portugal, 2001. "Multiobjective Metaheuristics for the Bus Driver Scheduling Problem," Transportation Science, INFORMS, vol. 35(3), pages 331-343, August.
    12. 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.
    13. Grossman, Tal & Wool, Avishai, 1997. "Computational experience with approximation algorithms for the set covering problem," European Journal of Operational Research, Elsevier, vol. 101(1), pages 81-92, August.
    14. 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.
    15. 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.
    16. Chunyan Liu & Hejiao Huang & Hongwei Du & Xiaohua Jia, 2017. "Optimal RSUs placement with delay bounded message dissemination in vehicular networks," Journal of Combinatorial Optimization, Springer, vol. 33(4), pages 1276-1299, May.
    17. Ibrahim, Walid & El-Sayed, Hesham & El-Chouemie, Amr & Amer, Hoda, 2009. "An adaptive heuristic algorithm for VLSI test vectors selection," European Journal of Operational Research, Elsevier, vol. 199(3), pages 630-639, December.
    18. 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.
    19. Helena Ramalhinho-Lourenço, 2001. "The crew-scheduling module in the GIST system," Economics Working Papers 547, Department of Economics and Business, Universitat Pompeu Fabra.
    20. Torbjörn Larsson & Michael Patriksson, 2006. "Global Optimality Conditions for Discrete and Nonconvex Optimization---With Applications to Lagrangian Heuristics and Column Generation," Operations Research, INFORMS, vol. 54(3), pages 436-453, June.

    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:3:p:225-:d:486085. 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.