Ir al menú de navegación principal Ir al contenido principal Ir al pie de página del sitio

Vol. 32 Núm. 63 (2023)
Enero-Marzo 2023 (Publicación Continua)

Articulos

Métodos de inicialización y búsqueda local aplicados al problema de cobertura de conjuntos: un mapeo sistemático

https://doi.org/10.19053/01211129.v32.n63.2023.15235

Publicado 2023-02-28

Nelson-Enrique Quemá-Taimbud
Universidad del Cauca

Martha-Eliana Mendoza-Becerra
Universidad del Cauca

Oscar-Fernando Bedoya-Leyva
Universidad del Valle

Resumen

El problema de cobertura de conjuntos (PCC) es un problema de optimización combinatorio clásico que hace parte de los 21 problemas NP-completos de Karp. Muchas aplicaciones del mundo real pueden modelarse como PCC, como la ubicación servicios de emergencia, la planificación militar, la toma de decisiones en el contexto de la pandemia por COVID-19, entre otros. Entre los enfoques que han resuelto este tipo de problema se encuentran los algoritmos heurísticos (H) y metaheurísticos (MH), que integran métodos y procedimientos iterativos para explorar y explotar el espacio de búsqueda de forma inteligente. En la presente investigación realizamos un mapeo sistemático de la literatura enfocado en los métodos de inicialización y búsqueda local utilizados en estos algoritmos que se han aplicado al PCC con el fin de identificarlos y que puedan ser aplicados en otros algoritmos. Este mapeo se realizó en tres etapas principales: planificación de la investigación, ejecución y documentación de resultados. Se encontró que el método de inicialización más utilizado es el aleatorio con búsqueda heurística y que la inclusión de métodos de búsqueda local en los algoritmos MH mejoran los resultados obtenidos en comparación con estos sin búsqueda local. Por otra parte, se identificaron métodos de inicialización y búsqueda local que pueden ser utilizados para modificar otros algoritmos y evaluar el impacto que generan en los resultados obtenidos.

Palabras clave

problema de cobertura de conjuntos, búsqueda local, mapeo sistemático, heurísticas, inicialización, metaheurísticas, optimización

XML (English) PDF (English)

Citas

  1. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, third edition. MIT Press, 2009. https://sd.blackball.lv/library/Introduction_to_Algorithms_Third_Edition_(2009).pdf
  2. Y. Deng, Y. Zhang, J. Pan, “Optimization for Locating Emergency Medical Service Facilities: A Case Study for Health Planning from China,” Risk Management and Healthcare Policy, vol. 14, pp. 1791–1802, 2021. https://doi.org/10.2147/RMHP.S304475 DOI: https://doi.org/10.2147/RMHP.S304475
  3. D. Sumrit, K. Thongsiriruengchai, “An Optimization Model for Advanced Life Support Ambulance Facility Location Problem,” Proceedings, vol. 39, no. 1, e10, 2020. https://doi.org/10.3390/proceedings2019039010 DOI: https://doi.org/10.3390/proceedings2019039010
  4. J. Purnomo, Z. Fanani, T. Domai, A. Hariswanto, “The model for determining location of naval base using ahp method and set covering problem,” Russian Journal of Agricultural and Socio-Economic Sciences, vol. 101, no. 5, pp. 122–131, 2020. https://doi.org/10.18551/rjoas.2020-05.13 DOI: https://doi.org/10.18551/rjoas.2020-05.13
  5. I. D. Argun, “An Overview on Set Covering Problems With a Focus on Military Applications,”in Operations Research for Military Organizations, pp. 54–66, 2019. https://doi.org/10.4018/978-1-5225-5513-1.CH003 DOI: https://doi.org/10.4018/978-1-5225-5513-1.ch003
  6. Q. Yong, D. Liu, G. Li, W. Wu, W. Sun, S. Liu, “Reducing exposure to COVID-19 by improving access to fever clinics: an empirical research of the Shenzhen area of China,” BMC Health Services Research, vol. 21, no. 1, pp. 1–10, 2021. https://doi.org/10.1186/S12913-021-06831-4 DOI: https://doi.org/10.1186/s12913-021-06831-4
  7. P. S. Muttaqin, R. A. Finata, A. A. Masturo, “Facility Location Model for Emergency Humanitarian Logistics Using Set Covering and Analytic Network Process (ANP) Method,” IPTEK Journal of Proceeding Series, no. 5, pp. 49–53, 2020. https://doi.org/10.12962/J23546026.Y2020I5.7931 DOI: https://doi.org/10.12962/j23546026.y2020i5.7931
  8. Y. Wang, D. Ouyang, L. Zhang, M. Yin, “A novel local search for unicost set covering problem using hyperedge configuration checking and weight diversity,” Science China Information Sciences, vol. 60, no. 6, e062103, 2017. https://doi.org/10.1007/s11432-015-5377-8 DOI: https://doi.org/10.1007/s11432-015-5377-8
  9. F. Xu, J. Li, “A hybrid encoded memetic algorithm for set covering problem,” in Proceedings - 2018 10th International Conference on Advanced Computational Intelligence, 2018, pp. 552–557. https://doi.org/10.1109/ICACI.2018.8377519 DOI: https://doi.org/10.1109/ICACI.2018.8377519
  10. M. Gendreau, J.-Y. Potvin, Handbook of Metaheuristics, 2010. DOI: https://doi.org/10.1007/978-1-4419-1665-5
  11. B. Kitchenham, S. Charters, Guidelines for performing Systematic Literature Reviews in Software Engineering, 2007.
  12. K. Petersen, R. Feldt, S. Mujtaba, M. Mattsson, “Systematic Mapping Studies in Software Engineering,” in 12th International Conference on Evaluation and Assessment in Software Engineering, 2008. https://doi.org/10.14236/EWIC/EASE2008.8 DOI: https://doi.org/10.14236/ewic/EASE2008.8
  13. T. Cañizares, C. Gómez, C. Pardo, O. S. Gómez, “What is there about scaling of agile software development? Preliminary findings from a systematic mapping study,” in XIV Jornadas Iberoamericanas de Ingenería de Software e Ingenería del Conocimiento, 2019, pp. 83–96.
  14. A. Bashab et al., “A systematic mapping study on solving university timetabling problems using meta-heuristic algorithms,” Neural Computing and Applications, vol. 32, no. 23, pp. 17397–17432, 2020. https://doi.org/10.1007/s00521-020-05110-3 DOI: https://doi.org/10.1007/s00521-020-05110-3
  15. J. García, G. Astorga, V. Yepes, “An analysis of a KNN perturbation operator: An application to the binarization of continuous metaheuristics,” Mathematics, vol. 9, no. 3, pp. 1–20, Jan. 2021. https://doi.org/10.3390/math9030225 DOI: https://doi.org/10.3390/math9030225
  16. J. García, B. Crawford, R. Soto, G. Astorga, “A clustering algorithm applied to the binarization of Swarm intelligence continuous metaheuristics,” Swarm and Evolutionary Computation, vol. 44, pp. 646–664, 2019. https://doi.org/10.1016/j.swevo.2018.08.006 DOI: https://doi.org/10.1016/j.swevo.2018.08.006
  17. B. Crawford et al., “A binary monkey search algorithm variation for solving the set covering problem,” Natural Computing, vol. 19, no. 4, pp. 825–841, 2020. https://doi.org/10.1007/s11047-019-09752-8 DOI: https://doi.org/10.1007/s11047-019-09752-8
  18. B. Crawford et al., “Binary Fruit Fly Swarm Algorithms for the Set Covering Problem,” Computers, Materials & Continua, vol. 71, no. 2, pp. 4295–4318, 2022. http://doi.org/10.32604/cmc.2022.023068 DOI: https://doi.org/10.32604/cmc.2022.023068
  19. V. Reyes, I. Araya, “A GRASP-based scheme for the set covering problem,” Operational Research, vol. 21, no. 4, pp. 2391–2408, 2019. https://doi.org/10.1007/s12351-019-00514-z DOI: https://doi.org/10.1007/s12351-019-00514-z
  20. H. Razip, M. N. Zakaria, “Combining approximation algorithm with genetic algorithm at the initial population for NP-complete problem,” in IEEE Student Conference on Research and Development: Inspiring Technology for Humanity, 2018, pp. 98–103. https://doi.org/10.1109/SCORED.2017.8305413 DOI: https://doi.org/10.1109/SCORED.2017.8305413
  21. H. Razip, N. Zakaria, “Genetic Algorithm with Approximation Algorithm Based Initial Population for the Set Covering Problem,” Springer, Singapore, 2021, pp. 59–78. https://doi.org/10.1007/978-981-16-3246-4_6 DOI: https://doi.org/10.1007/978-981-16-3246-4_6
  22. Z. Lei, S. Cai, “Solving set cover and dominating set via maximum satisfiability,” in AAAI, vol. 34, no. 02, pp. 1569–1576, 2020. https://doi.org/10.1609/aaai.v34i02.5517 DOI: https://doi.org/10.1609/aaai.v34i02.5517
  23. M. Pinard, L. Moalic, M. Brévilliers, J. Lepagnot, L. Idoumghar, “A memetic approach for the unicost set covering problem,” Lecture Notes in Computer Science, vol. 12096, pp. 233–248, 2020. https://doi.org/10.1007/978-3-030-53552-0_23 DOI: https://doi.org/10.1007/978-3-030-53552-0_23
  24. M. Brévilliers, J. Lepagnot, L. Idoumghar, M. Rebai, J. Kritter, “Hybrid differential evolution algorithms for the optimal camera placement problem,” Journal of Systems and Information Technology, vol. 20, no. 4, pp. 446–467, 2018. https://doi.org/10.1108/JSIT-09-2017-0081 DOI: https://doi.org/10.1108/JSIT-09-2017-0081
  25. M. F. L. Schmitt, M. H. Mulati, A. A. Constantino, F. Hernandes, T. A. Hild, “Ant-set: A subset-oriented ant colony optimization algorithm for the set covering problem,” Journal of Universal Computer Science, vol. 26, no. 2, pp. 293–316, 2020. https://doi.org/10.3897/jucs.2020.016 DOI: https://doi.org/10.3897/jucs.2020.016
  26. J. Bailey, D. Budgen, M. Turner, B. Kitchenham, P. Brereton, S. Linkman, “Evidence relating to object-oriented software design: A survey,” in First International Symposium on Empirical Software Engineering and Measurement, 2007, pp. 482–484. https://doi.org/10.1109/ESEM.2007.58 DOI: https://doi.org/10.1109/ESEM.2007.58
  27. L. Jorquera, P. Valenzuela, M. Valenzuela, H. Pinto, “A Binary Ant Lion Optimisation Algorithm Applied to the Set Covering Problem,” in Computer Science On-line Conference, 2019, pp. 156–167. https://doi.org/10.1007/978-3-030-19810-7_16 DOI: https://doi.org/10.1007/978-3-030-19810-7_16
  28. L. Pavez, F. Altimiras, G. Villavicencio, “A Percentil Gravitational Search Algorithm an Aplication to the Set Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2020, pp. 663–673. https://doi.org/10.1007/978-3-030-63319-6_62 DOI: https://doi.org/10.1007/978-3-030-63319-6_62
  29. A. Fernández, A. Peña, M. Valenzuela, H. Pinto, “A Binary Percentile Sin-Cosine Optimisation Algorithm Applied to the Set Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2019, pp. 285–295. https://doi.org/10.1007/978-3-030-00211-4_25 DOI: https://doi.org/10.1007/978-3-030-00211-4_25
  30. L. Jorquera, P. Valenzuela, F. Altimiras, P. Moraga, G. Villavicencio, “A Percentil Bat Algorithm an Application to the Set Covering Problem,” in Computer Science On-line Conference, 2020, pp. 223–233. https://doi.org/10.1007/978-3-030-51971-1_18 DOI: https://doi.org/10.1007/978-3-030-51971-1_18
  31. L. Jorquera, P. Valenzuela, L. Causa, P. Moraga, G. Villavicencio, “A Percentile Firefly Algorithm an Application to the Set Covering Problem,” in Lecture Notes in Networks and Systems, vol. 229, pp. 750–759, 2021. https://doi.org/10.1007/978-3-030-77445-5_67 DOI: https://doi.org/10.1007/978-3-030-77445-5_67
  32. G. Villavicencio, M. Valenzuela, L. Causa, P. Moraga, H. Pinto, “A Machine Learning Firefly Algorithm Applied to the Matrix Covering Problem,” in Computer Science On-line Conference, 2021, pp. 316–325. https://doi.org/10.1007/978-3-030-77445-5_29 DOI: https://doi.org/10.1007/978-3-030-77445-5_29
  33. L. Pavez, F. Altimiras, G. Villavicencio, “A K-means Bat Optimisation Algorithm Applied to the Set Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2020, pp. 622–632. https://doi.org/10.1007/978-3-030-63319-6_58 DOI: https://doi.org/10.1007/978-3-030-63319-6_58
  34. G. Villavicencio, M. Valenzuela, F. Altimiras, P. Moraga, H. Pinto, “A K-Means Grasshopper Optimisation Algorithm Applied to the Set Covering Problem,” in Computer Science On-line Conference, 2020, pp. 312–323. https://doi.org/10.1007/978-3-030-51971-1_25 DOI: https://doi.org/10.1007/978-3-030-51971-1_25
  35. M. Valenzuela, P. Moraga, L. Causa, H. Pinto, J.-M. Rubio, “A Machine Learning Whale Algorithm Applied to the Matrix Covering Problem,” in Proceedings of the Computational Methods in Systems and Software, 2021, pp. 413–422. https://doi.org/10.1007/978-3-030-90321-3_33 DOI: https://doi.org/10.1007/978-3-030-90321-3_33

Descargas

Los datos de descargas todavía no están disponibles.

Artículos similares

1 2 > >> 

También puede {advancedSearchLink} para este artículo.