Algoritmos Genéticos y Búsqueda Local

Las metaheurísticas seleccionadas para la resolución del problema fueron algoritmos genéticos y búsqueda local.
La formulación clásica de un AG puede encontrarse en Goldberg [10]. Basado en el esquema de un algoritmo evolutivo, el algoritmo genético define operadores de selección, cruzamiento y mutación para aplicar a la población en cada generación. El esquema de la formulación se presenta a continuación.

1 - Inicializar P(0)
2 - generación = 0
3 - Evaluar P(0)
4 - Mientras (no CriterioParada) hacer
     4.1- Padres = Selección (P(generacion))
     4.2- Hijos = Cruzamiento (Padres)
     4.3- Hijos = Mutación (Hijos)
     4.4- NuevaPob = Reemplazar (Hijos,P(generacion))
     4.5- generacion ++
     4.6- P(generacion) = NuevaPob
5- Fin mientras
6- retornar Mejor Solución Hallada

La estructura básica de un AG consiste en inicializar una población de individuos y evaluarla mediante la función de fitness definida. En cada generación se seleccionan los individuos progenitores y se efectúa el cruzamiento generando nuevos individuos llamados hijos. A los hijos se les aplica la mutación y finalmente los hijos reemplazan a sus progenitores para formar la población de la siguiente generación. A medida que corren las generaciones se va guardando el individuo mas apto según la función de fitness.

El cruzamiento es el operador principal en un algoritmo genético, mientras que el operador de mutación es secundario pero es fundamental para agregar diversidad a la población y de esta forma lograr una mejor exploración en el espacio de búsqueda. Sin embargo, es posible que este operador sea eliminado del algoritmo genético pero es recomendable utilizar otros operadores que introduzcan diversidad.

En general en un AG se utilizan codificaciones binarias para los problemas aunque es posible y a veces recomendable utilizar codificaciones reales, pero esto depende exclusivamente de problema planteado.

La búsqueda local es la base de muchos de los métodos usados en problemas de optimización y es un proceso iterativo que comienza en una solución y la mejora realizando modificaciones locales. Básicamente empieza con una solución inicial y busca en su vecindad por una mejor solución. Si encuentra una mejor solución, reemplaza su solución actual por la nueva y continua con el proceso hasta que no se pueda mejorar la solución actual.

Metaheurísticas aplicadas a la
reconstrucción de árboles filogenéticos