Algoritmo Genético para el problema del viajante.

Este post lleva varios meses en el ordenador y es tiempo de mostrarlo.
El problema del viajante (TSP), es un problema de combinatoria que consiste encontrar la ruta más corta que pase por una serie de puntos (ciudades). El problema es simple, en el sentido que solo hay que combinar el orden de puntos para encontrar la ruta. El verdadero problema se encuentra en el tamaño del espacio de búsqueda, que es factorial de N! (N el número de puntos (ciudades)). Por ejemplo si tenemos 20 puntos el número de posibilidades es 2432902008176640000. Si tardamos 1ms e analizar cada una de las posibilidades, tardaríamos 77.146.816 años en encontrar la mejor solución. El problema se escapa cuando tenemos 1500 puntos  o más.

Existen varias maneras de atacar este problema: Ant Colony Optimization.

La idea de este post es hacer una pequeña introducción a los Algoritmos Genéticos (AGs) y mostrar parte de la lógica que existe detrás de la computación evolutiva. Para esto he programado un simple AGs en RVB y un tutorial donde se explica el tipo de selección, cruce y mutación de este AG en particular.

TABLA

En esta tabla se pueden ver 9 diferentes pruebas del AG con sus resultados. Desde que estamos evaluando la longitud de una ruta, la lista de números que aparece en cada prueba son las longitudes al principio de la optimización (verde) y al final de la optimización (amarillo). Los recuadros de colores representan los diferentes parámetros del AG.

Initial Population:

Es el tamaño de la población.

Natural Selection:

Especifica cuantas veces el mejor individuo quedará seleccionado en la ruleta (ver tutorial selección natural).

Crossover Pointer:

Determina que parte hereda el hijo del padre y la madre. 1/2 significa que heredará la mitad de los genes del padre y la madre (primer el padre).  (ver el tutorial de cruce).

Mutation Rate:

La primera población es aleatoria y este valor determina que tan diferente será. Si pones un valor bajo el algoritmo buscará en un espacio más reducido que si la mutación inicial es total. En principio este valor puede servir para hacer una aproximación al resultado con otro tipo de algoritmo. Por ejemplo generar un individuo que una todos los puntos más cercanos, (esto sería un acercamiento). Luego usar un valor bajo de aleatoriedad para que el AG busqué alrrededor de esta solución.

Number of Iterations:

Número de veces que se ejecutará el AG.

Child Mutation:

Está es la mutación del individuo. haz pruebas con valores pequeños y luego con valores grandes >10. verás como la convergencia de resultados es completamente diferente
(ver tutorial sobre mutación).

Displace:

Este valor tiene que ver con la “presión” que se le puede asignar a la selección natural. (ver el tutorial de selección natural).

Descargas:

1 Comment

  • Catriel Nov 5, 2014, 5:15

    Como puedo obtener mas datos sobre esto? No tengo enlace al tutorial que dejaste online, lo tenes resubido en otro repo?

Leave a Reply