|
Introducción Muchos problemas de optimización combinatoria son NP-difíciles, donde la complejidad de los algoritmos conocidos para su resolución aumenta de manera exponencial con el tamaño del problema. Por motivo, la aplicabilidad de los métodos exactos se encuentra limitada por el gran tiempo y consumo de recursos computacionales que demandan. Como alternativa viable se encuentran las metaheurísticas, las cuales no garantizan alcanzar una solución óptima al problema, pero pueden lograr soluciones aproximadas. Una metaheurística es un método heurístico de alto nivel para resolver un tipo de problema computacional general. Este proyecto tiene como objetivo el estudio de metaheurísticas y su aplicación para la reconstrucción de árboles filogenéticos que representen las relaciones de evolución entre un conjunto de especies de forma óptima y en tiempos de ejecución razonables. El problema de reconstrucción filogenética es de alta complejidad, es NP-difícil, y la aplicación de algoritmos tradicionales para su resolución puede insumir tiempos de procesamientos extremadamente grandes. Sin embargo la aparición de potentes computadoras y la inserción de las metaheurísticas permiten encontrar soluciones óptimas o cercanas a las óptimas en tiempos razonables. Un árbol filogenético es una representación gráfica de la evolución de las relaciones entre entidades o individuos que se supone comparten un antecesor. El principio que denomina la reconstrucción filogenética se base en el análisis de similitudes y diferencias entre entidades, pueden ser usadas para inferir la historia evolutiva de esas entidades. Sin embargo, inferir la historia en la práctica no es un proceso simple si se parte del punto final de la evolución. Este trabajo se centra básicamente en resolver el problema de la inferencia del árbol filogenético óptimo según el criterio de mínima evolución a partir de un conjunto de individuos iniciales. |
|
Algoritmos Genéticos Los AG son una técnica evolutiva muy versátil y robusta, además son muy populares y han resuelto exitosamente una amplia gama de problemas en diversas áreas. Los AG presentan características que los hacen ventajosos al compararlos con otras técnicas. Una de las ventajas más importantes es que la operativa del mecanismo evolutivo de los algoritmos genéticos es independiente de particularidades del dominio del problema a resolver, lo cual permite definir esquemas genéricos capaces de abordar diferentes clases de problemas. Desde el punto de vista de la resolución del problema, el algoritmo genético funciona como una caja negra que solamente utiliza como dato de entrada la función de fitness definida para el problema, para evaluar a los individuos en el ciclo evolutivo. No utiliza información adicional sobre las características del problema, aunque ciertas particularidades de la 20 codificación pueden complementar la operativa simple de los operadores evolutivos y dirigir la búsqueda. La independencia del mecanismo de búsqueda evolutivo de las características del problema permite a los algoritmos genéticos evitar, en ocasiones, el estancamiento en mínimos locales del problema. Este trabajo se centrará en particular en la aplicación de un algoritmo genético para la resolución del problema planteado por lo que en la sección 3.5 se presentarán las características mas importantes de los algoritmos genéticos y las particularidades de su mecanismo evolutivo.
|
|
Reconstrucción Filogenética El campo de la filogenia tiene la meta de estudiar las relaciones entre las especies, poblaciones, individuos o genes. Estas relaciones son tomadas es su sentido literal de parentesco o genealogía descendiendo de un ancestro en común. Las relaciones generalmente son representadas en forma de árbol, donde la raíz es el ancestro común a los individuos considerados. La filogenia es la descripción de las relaciones biológicas entre individuos, generalmente expresado en forma de árbol. Una afirmación de la filogenia entre los objetos asume la homología y depende de la clasificación. La filogenia determina una topología de las relaciones entre individuos basada en la clasificación de acuerdo a la similitud de uno o más conjuntos de caracteres o a un modelo de procesos evolutivos. En muchos casos las relaciones filogenéticas basadas en diferentes caracteres son consistentes y se apoyan unas en otras. Si diferentes caracteres inducen a relaciones filogenéticas inconsistentes, entonces son todas dudosas. En cambio, la misma similitud en la información puede ser consistente con diferentes topologías o árboles. Las relaciones filogenéticos se describen mediante árboles donde pueden tener raíz o no. Los árboles filogenético sin raíz muestran la topología de las relaciones entre un conjunto de individuos pero no un patrón de descendencia o un orden cronológico. Los árboles filogenéticos con raíz son grafos dirigidos, donde la dirección de la arista implica la relación ancestro-descendiente. Es posible asignar números a las aristas del grafo para representar la distancia entre los nodos conectados por esta arista, donde el largo de un camino es la suma de las distancias de las aristas que lo componen y en este caso el grafo puede ser dibujado a escala de acuerdo a estas distancias En árboles filogenéticos, el largo de una arista podría significar alguna medida de similitud entre las dos especies que conecta, o el tiempo desde su separación. La asunción de que las diferencias entre las propiedades de las especies actuales reflejan sus momentos de divergencias sería verdadera solo si su velocidad de divergencia es la misma en todas las ramas del árbol pero muchas excepciones son conocidas.
|
|
Metaheurísticas aplicadas
a la |
|
|
