Algoritmo de colonia de abejas artificiales modificado para problemas de cobertura de conjuntos de gran escala

Abstract

A lo largo de los años, las organizaciones se han enfrentado al desafío de optimizar el uso de sus recursos para satisfacer las necesidades de un sector específico. En este contexto surge el Problema de Cobertura de Conjuntos (PCC), un problema clásico de optimización combinatoria, informática y teoría de la complejidad computacional que se presenta al asignar recursos a un conjunto de necesidades al menor costo posible. La complejidad del PCC aumenta con el número de necesidades (o restricciones) a satisfacer, incrementando el número de posibles soluciones y el tiempo necesario para comprobarlas. Ante este desafío, se han explorado nuevas formas de abordar el PCC recurriendo al uso de algoritmos metaheurísticos, los cuales ofrecen una alternativa eficiente para encontrar soluciones óptimas o cercanas a la óptima en un tiempo razonable, superando las limitaciones asociadas con el aumento de la complejidad del problema. El presente trabajo propone el algoritmo ABC_SCP_IMP_RH_ILS para resolver PCC de gran escala, obtenido al reemplazar el método de inicialización y búsqueda local del algoritmo base del estado del arte colonia de abejas artificiales ABC_SCP con métodos que se han aplicado recientemente al problema. En este documento se describe el proceso de modificación del algoritmo ABC_SCP que involucró la identificación y selección de los métodos mencionados, la implementación del algoritmo base, el reemplazo de los métodos seleccionados en el algoritmo base para la obtención de seis variantes, y la selección de la variante ABC_SCP_IMP_RH_ILS con mejores resultados. La evaluación de los algoritmos se realizó con 20 problemas de prueba del repositorio de investigación de operaciones OR-Library considerados de gran escala, tomando como referencia los mejores valores de aptitud conocidos (BKS) de cada problema para compararlos con el mejor valor de aptitud (Best) y el valor promedio (Avg) obtenido por las variantes. Los resultados muestran que las modificaciones realizadas al algoritmo base generaron un impacto positivo al mejorar los valores reportados en varios problemas por el mismo algoritmo y por otros del estado del arte. Estos resultados posicionan al ABC_SCP_IMP_RH_ILS como un algoritmo metaheurístico competitivo de referencia en el ámbito de investigaciones relacionadas con el PCC.