Tesis "Nuevos Planteamientos Multi-Objetivo Para Resolver el Problema de Máxima Parsimonia"
Sustentante: Daniel Rafael Torres Avalos
Directores: Dr. Gregorio Toscano Pulido, Dr. Eduardo Arturo Rodríguez Tello
Sinodales: Dr. José Gabriel Ramírez Torres, Dr. Ricardo Landa Becerra
Resumen:
En bioinformática, el problema de construcción filogenética implica construir hipótesis evolutivas mediante árboles, usualmente binarios, en los que las hojas representan un set de n especies conocidas y los nodos internos son ancestros hipotéticos derivados de las mismas. El problema de Máxima Parsimonia (MP) consiste en la búsqueda o construcción de la topología de árbol para la cual los cambios evolutivos sean mínimos.
El problema MP está clasificado como un problema NP-Completo, es altamente combinatorio, y el tamaño de su espacio de búsqueda crece factorialmente respecto al número de especies estudiadas. Existen estudios que indican que la complejidad del espacio de búsqueda también incrementa con el número de especies, añadiendo planicies y óptimos locales conforme las especies estudiadas aumentan. La multi-objetivización del problema presenta una alternativa para permitir que un algoritmo evolutivo encuentre soluciones competitivas con respecto a aquellas reportadas en el estado del arte.
En este trabajo de investigación se analizaron dos paradigmas de multi-objetivización para el problema de MP. Se presentaron seis re-formulaciones del problema basadas en la descomposición de la función objetivo original y doce basadas en la adición de funciones objetivo suplementarias. Después de comparación experimental extensa se seleccionaron las tres propuestas mas prometedoras y se implementaron en el algoritmo NSGA-II, utilizando un algoritmo de cruza topológica y cinco funciones de vecindad.
Se realizó una comparación de las tres propuestas prometedoras contra un algoritmo mono-objetivo (evaluando solo MP), y contra algoritmos del estado del arte. Se utilizaron ocho instancias binarias reales, 14 instancias binarias sintéticas, y 19 instancias reales con caracteres multi-estado.
Los resultados obtenidos de la experimentación muestran que las propuestas de multi-objetivización presentadas son competitivas. Contra un algoritmo mono-objetivo que evalúa MP, la primer propuesta obtuvo resultados competitivos para el 71.4% de las instancias, la segunda para 64.2% de las instancias, y la tercera para 57.1% de las instancias. La comparación contra dos métodos representativos del estado del arte permite observar que la segunda propuesta iguala la calidad de los resultados para 52.6% de las instancias de prueba, y las otras dos igualan las soluciones de 47.3% de las instancias de prueba utilizando una fracción del tiempo requerido por los algoritmos del estado del arte.