Tesis "Una Metaheurística de Recocido Simulado para el Problema de Maximización del Antibandwidth en Grafos"
Alumno: Luis Carlos Betancourt Rodríguez
Asesor: Dr. Eduardo Arturo Rodríguez Tello
Sinodales: Dr. José Torres Jiménez, Dr. Gregorio Toscano Pulido y Dr. Eduardo Arturo Rodríguez Tello
El objeto de estudio en esta tesis es el problema de optimización combinatoria conocido como Maximización del Antibandwidth en Grafos. Este consiste en encontrar un etiquetado para los nodos de un grafo de modo tal que se maximice la mínima diferencia absoluta entre las etiquetas de nodos adyacentes. La maximización del antibandwidth al igual que otros problemas de etiquetado de grafos es NP-completo. Actualmente existen reportados métodos que resuelven, de manera óptima y en tiempo polinomial, instancias muy específicas de este problema. Sin embargo, existe aún la necesidad de crear algoritmos que permitan resolver eficientemente el problema para el caso de grafos generales. En esta tesis se desarrolló un algoritmo metaheurístico basado en recocido simulado que permite resolver el problema de Maximización del Antibandwidth en Grafos de una manera competitiva con respecto a otras técnicas propuestas en el estado del arte.
La sintonización de parámetros para este algoritmo se realizó mediante una técnica conocida como pruebas de interacción combinatoria que emplea arreglos de cobertura (covering arrays) para representar dichas pruebas. El algoritmo que se propone en este trabajo de tesis se comparó contra dos diferentes enfoques del estado del arte: un algoritmo memético y un algoritmo de tipo GRASP. Se probó sobre un total 78 instancias provenientes de 3 diferentes conjuntos. Para el 66.67% de los casos se obtuvieron resultados superiores a los reportados en la literatura y para otro 17.95 % se lograron igualar estas soluciones.