APLICACIONES METAHEURÍSTICAS AL PROBLEMA DEL CONJUNTO DOMINANTE

Abstract

En el ámbito de investigación de la optimización combinatoria, se busca resolver problemas para los cuales encontrar la mejor solución posible resulta muy costoso, y por lo tanto, surge la necesidad de idear aproximaciones que sean capaces de encontrar soluciones suficientemente buenas en un tiempo reducido.

En este Trabajo de Fin de Grado se pretende resolver el problema de grafos conexos del Mínimo Conjunto Dominante o Minimum Dominating Set (MDS), el cual cuenta con aplicaciones prácticas de interés, como la colocación de sensores de medición en sistemas de distribución energética, o la realización de pruebas en redes de comunicación.

Para tratar de resolver el problema, se ha hecho uso de un algoritmo que utiliza el método metaheurístico Greedy Randomized Adaptive Search Procedure (GRASP), aplicando previamente una regla de inferencia para agilizar la creación de soluciones, y una búsqueda local que elimina elementos de la solución en caso de que estos sean redundantes.

Esta propuesta se compara con el estado del arte, y es capaz de obtener unos resultados prometedores en cuanto a tiempo de ejecución y calidad de las soluciones, llegando a igualarlo e incluso superarlo con bastante frecuencia en grafos de mayor densidad.