Problema del viajero con algoritmos geneticos

El problema del viajante

Considerando el ejemplo de un viajante que parte de una ciudad “origen” y tiene que pasar por un número determinado de ciudades, digamos 70. La ruta a escoger resulta diferente según el orden en que se visiten las ciudades. Si se van visitando ciudades en un orden en que cada una está lo más cerca  posible de la próxima entonces el viaje resultará más rentableque si se visita primero una ciudad que esté muy lejos de la “origen”, luego se vuelve a otra cerca de ésta, luego se vuelve a ir al otro extremo etc. Por eso puede interesar visitar  las ciudades en un orden en que la distancia total  sea la más corta posible.

Se presenta un programa que consiste en lo siguiente:

Dadas las coordenadas (x, y) de las ciudades origen y de las demásciudades a visitar, el programa evalúa todas las maneras posibles de efectuar el recorrido y vaya calculando sus respectivas distancias una a una, dándonos al final como resultado la más pequeña.

Pero se tiene un problema. El ejemplo con 70 ciudades el número de maneras diferentes de recorrerlas es demasiado grande pues es 70! Está claro que si se diseña un programa que intente calcular lasolución exacta por evaluación de todas las rutas posibles, el programa eficiente en cuanto a tiempo.
 
Solución de este problema mediante algoritmos genéticos

* Inicialización: Se genera la población inicial (tamaño de la población = 70), que está constituida por un conjunto de cromosomas los cuales representan las posibles soluciones del problema.
* Evaluación: A cadauno de los cromosomas de esta población se aplicará la función de aptitud para saber que tan "buena" es la solución que se está codificando.
* Condición de término: El Algoritmo Genético se deberá detener cuando se alcance la solución óptima, pero ésta generalmente se desconoce, por lo que se deben utilizar otros criterios de detención. Normalmente se usan dos criterios: correr el AG unnúmero máximo de iteraciones (generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla la condición de término se hace lo siguiente:

* Selección: Después de saber la aptitud de cada cromosoma se procede a elegir los cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitud tienen mayor probabilidad de ser seleccionados.
*Cruzamiento: El cruzamiento es el principal operador genético, representa la reproducción sexual, opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan las características de ambos cromosomas padres.
* Mutación: modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonas del espacio de búsqueda que no estaban cubiertas por los individuos dela población actual.
* Reemplazo: una vez aplicados los operadores genéticos, se seleccionan los mejores individuos para conformar la población de la generación siguiente.

Los algoritmos genéticos permiten encontrar una solución aproximada a este problema, una solución que puede ser en la mayoría de las veces muy cercana a la mejor.

Se identifica a cada ciudad con unnúmero (1, 2,3...70) y se generan 70 filas con los 70 números de las ciudades ordenados de manera aleatoria, de manera que tengamos 70 rutas diferentes que se han generado al azar. Ahora se van a reproducir esas filas; esto es que a partir de cada una se generarán 10 más: la primera de ellas se deja igual que la fila “padre” (Ósea la que se usó para generar este hijo) y en cada una de las otras 9 permutamos dos ciudades al azar. Por ejemplo, si una de las 70 filas generadas aleatoriamente que contienen un orden concreto de visita de las ciudades es:

20 3 4 1 15 16 18 2 5 6 7 11 12 8 9 10 19 17 14 13 30 25 28 50 69 33 45 70…

Entonces la primera de las 10 filas que llamaremos “hijas” será ella misma y la segunda será la misma, excepto que habremos permutado 2 elementos (por...