Tesis "Metaheurísticas para la Resolución del Problema de Máxima Parsimonia"
Alumna: Karla Esmeralda Vázquez Ortiz
Asesor: Dr. Eduardo Arturo Rodríguez Tello
Sinodales: Dr. José Gabriel Ramírez Torres, Dr. Gregorio Toscano Pulido
El problema de Máxima Parsimonia (MP) consiste en encontrar una topología de árbol, entre todas las posibles, que permita representar las relaciones evolutivas para un grupo de especies dado, de forma tal que esta contenga el menor número de cambios evolutivos (mutaciones) posibles. El problema de MP pertenece a la clase de problemas NP-completos y es altamente combinatorio, por lo que los algoritmos exactos existentes para resolverlo solo funcionan para instancias pequeñas del problema (con menos de 10 especies). Una alternativa viable a esta problemática consiste en el uso de algoritmos aproximados para resolverlo.
En este trabajo de investigación se analizaron diversos métodos aproximados para resolver el problema de MP y se seleccionaron dos de ellos para su implementación: la búsqueda local iterativa (ILS, iterated local search) y el recocido simulado (SA, simulated annealing), los cuales llamamos ILS-MP y SA-MP, respectivamente. Para cada componente esencial de estos algoritmos metaheurísticos, se consideraron diferentes opciones entre las que se encuentran dos métodos de inicialización, dos funciones de vecindad básicas y diecisiete vecindarios combinados. En el caso de ILS-MP se analizó el impacto de la función de vecindad en el desempeño del algoritmo de búsqueda local embebido. Por otra parte para el algoritmo SA-MP se estudiaron dos diferentes métodos para determinar el valor de la temperatura inicial, un esquema de enfriamiento de la temperatura de tipo estático así como uno dinámico y dos criterios de paro para el algoritmo.
A partir de una extensa comparación experimental, utilizando 18 instancias estándar de la literatura, se logró identificar la mejor combinación de componentes esenciales para cada una de las metaheurísticas propuestas. ILS-MP y SA-MP fueron comparados empleando sus mejores componentes y se demostró que SA-MP permite obtener mejores resultados que los proporcionados por ILS-MP. Posteriormente, se efectuó la sintonización de los parámetros de entrada de SA-MP mediante una técnica inspirada en pruebas de interacción combinatoria con la finalidad de potenciar su desempeño. La versión sintonizada de SA-MP se comparó empíricamente contra tres métodos representativos del estado del arte, permitiendo observar que SA-MP fue capaz de mejorar en el 28% de las instancias las mejores soluciones previamente conocidas y en el 72% restante igualar estos resultados. Finalmente, se ejemplificó la utilidad práctica del algoritmo SA-MP, en el área de epidemiología, para la construcción de árboles filogenéticos usados en el análisis de un problema real compuesto por 148 cepas del virus de influenza.