Tesis "Algoritmos avanzados para el problema de la suma del ancho de banda cíclico en grafos"
Sustentante: María Valentina Narváez Terán
Director: Dr. Eduardo Arturo Rodríguez Tello, Cinvestav Unidad Tamaulipas
Sinodales: Dr. Gregorio Toscano Pulido, Cinvestav Unidad Tamaulipas; Dr. José Torres Jiménez, Cinvestav Unidad Tamaulipas; Dr. Ricardo Landa Becerra, Cinvestav Unidad Tamaulipas; Dr. José Juan García Hernández, Cinvestav Unidad Tamaulipas; Dr. Eduardo Arturo Rodríguez Tello, Cinvestav Unidad Tamaulipas; Dr. Broderick Crawford Labrín, Pontificia Universidad Católica de Valparaíso, Chile.
Resumen:
El problema de la suma del ancho de banda cíclico (CBSP) es un problema de embebido de grafos. Esta clase de problemas consiste en la incrustación de los vértices y aristas de un grafo huésped dentro de los vértices y caminos de un grafo anfitrión. En el problema de la suma del ancho de banda cíclico, el objetivo es minimizar la suma de distancias cíclicas de los vértices adyacentes del grafo huésped embebidos en el anfitrión, el cuál tiene una topología de ciclo.
Se trata de un problema de optimización combinatoria que pertenece a la clase NP-hard.
En este trabajo, se estudiaron los aspectos que influyen en la dificultad del CBSP, se desarrollaron mejores métodos de solución y se propuso un análisis del problema desde una perspectiva integral.
La dificultad del CBSP es influenciada por la baja capacidad de discriminación de la función objetivo, causando neutralidad y multimodalidad en el paisaje de aptitud, lo cual puede afectar negativamente el desempeño de los algoritmos de búsqueda.
Con el fin de lidiar con la neutralidad y multimodalidad, se propuso una función de evaluación alternativa capaz de incrementar la capacidad de discriminación entre soluciones, manteniendo la compatibilidad con el objetivo del problema. Al ser incorporada en diversos algoritmos de búsqueda, esta función permitió mejorar significativamente su desempeño. Los efectos de la función de evaluación alternativa fueron estudiados mediante el análisis del paisaje de aptitud, comprobando que permite reducir la neutralidad y multimodalidad, mientras mantiene la estructura global del paisaje de aptitud.
Los enfoques de solución propuestos consideran el compromiso entre calidad de solución y tiempo de ejecución ofrecido por las técnicas metaheurísticas, la capacidad adaptativa de las hiperheurísticas y la obtención de óptimos mediante algoritmos exactos. Se llevó a cabo un análisis extensivo de diferentes configuraciones de operadores genéticos en el marco de un algoritmo memético y su interacción con la función de evaluación alternativa, obteniendo un algoritmo memético capaz de mejorar significativamente los resultados reportados en la literatura. Se implementó un bandido multiarmado dinámico como método hiperheurístico para la selección automática de los operadores y de la función de evaluación en el algoritmo memético. El resultado fue una mejora significativa en la calidad de solución obtenida.
En este trabajo se propusieron los primeros enfoques de tipo exacto para el problema, consistiendo en modelos programación con restricciones y un algoritmo de ramificación y poda. Comparativamente, el uso de programación con restricciones obtuvo un mejor desempeño en términos de calidad de solución y tiempo de ejecución.
Finalmente, este trabajo reporta un análisis conjunto ligando el paisaje de aptitud, las características de las instancias del problema y el desempeño observado en los algoritmos propuestos. Lo anterior reveló nuevo conocimiento sobre la interacción de dicho factores y su efecto en la dificultad.