Algoritmos Geneticos

El algoritmo genético es una metaheurística de población, conceptualmente se basa en el principio de evolución de los seres vivos, planteado por Darwin en 1859. En este, se indica que los seres vivos tienen la necesidad de reproducirse, con el fin de generar descendencia, es en este punto en donde se genera una competencia entre los individuos de una misma especie, ya que un espécimen fuerte tiene una alta capacidad de sobrevivencia en comparación a sus pares, presentando una mayor probabilidad de generar descendientes. Esto implica que los genes de los mejores sujetos se propagarán en sucesivas generaciones, provocando de esta manera, mutaciones que originan la evolución en nuevas generaciones, teniendo esta mayor capacidad de sobrevivencia que sus antecesores. De igual forma que sus antecesores, las nuevas generaciones volverán a reproducirse y seguirán creándose evoluciones que permitan adaptarse al ambiente que habitan.

En 1975 John Holland crea los principios básicos del algoritmo genético, el cual es una analogía directa al principio de evolución de Darwin, en donde las soluciones encontradas en el problema del vendedor viajero son individuos. Ya que esta metaheurística es de tipo poblacional, la forma de evaluar cada iteración (generación) es a partir de un conjunto de soluciones, el cual es llamando población. En cada generación, se realizan cruzamientos entre padres para generar nuevos hijos, además de aplicar un factor de mutación que permite explorar el espacio de búsqueda. Por último, se seleccionan los mejores hijos y/o padres para generar una nueva población.

Con el fin de realizar el proceso de selección de la mejor solución con algoritmo genético, se necesitan llevar a cabo los siguientes pasos:

1. Se inicia el algoritmo generando una población inicial, la cual también será nuestra población actual (G), para ello se debe determinar la cantidad de soluciones que conforman la población. Cada solución es creada a partir de los mismos métodos de generación de solución inicial de Simulated Annealing: aleatoria, vecino más cercano o determinista.
2. La mejor solución encontrada (s*), en un comienzo estará determinada por la mejor solución dentro de la población inicial.
3. Al iniciar una iteración o generación se seleccionan dos o más padres (P) de la población.
4. Los padres escogidos crearán nuevos hijos (s), para ello pasan por un proceso llamado recombinación, en donde los padres combinan los componentes de sus cromosomas (posición de las ciudades).
5. Una vez generado los hijos, estos pasan por una pequeña modificación generando una solución alterada, este procedimiento es llamado mutación. La probabilidad de que ocurra esta mutación es pequeña, existen varios tipos de mutación de solución.
6. En este punto, si la cantidad de hijos generados no son suficientes para construir una nueva población (G*), se vuelve al paso 3 volviendo a generar otros hijos adicionales.
7. Ya creada la nueva población (G*), esta se compara con la población actual (G), en donde los individuos de ambas poblaciones son elegidos para sustituir la generación actual con el fin de pertenecer a la próxima iteración del algoritmo.
8. Se selecciona el mejor hijo (solución) dentro de la nueva población actual, y se compara con la mejor solución encontrada (s*), en caso de ser mejor la solución generada, esta pasa a ser la mejor solución encontrada.
9. En caso de cumplir el criterio de término, se retorna la mejor solución encontrada. De manera contraria, se vuelve a ejecutar el procedimiento desde el paso 3.

Para facilitar el proceso de compresión del algoritmo, se ha diseñado un diagrama de flujo, que muestra gráficamente la ejecución de este: