Métodos de inicialización y búsqueda local aplicados al problema de cobertura de conjuntos: un mapeo sistemático
Agencias de apoyo
Universidad del Cauca
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
Referencias
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- M. Gendreau, J.-Y. Potvin, Handbook of Metaheuristics, 2010. DOI: https://doi.org/10.1007/978-1-4419-1665-5
- B. Kitchenham, S. Charters, Guidelines for performing Systematic Literature Reviews in Software Engineering, 2007.
- 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
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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.