Algoritmo Genético para el Problema del Viajante (TSP)

El problema del vendedor ambulante (Travelling Sales Problem) consiste encontrar la ruta más corta que conecte todas las ciudades que el vendedor planea visitar. El problema es muy simple de entender, sin embargo encontrar la solucion correcta es dificil, porque depende de encontrar la combinacion mas eficiente de ciudades por visitar.


Es por esto que el TSP es un ejemplo muy comun al aprender algoritmos de optimizacion. El numero de combinaciones crece de manera factorial N!. Por ejemplo, si hay 3 ciudades que visitar las posibilidades son: !3: 3 * 2 * 1 = 6. En el caso de !9: 9 * 8 ... 2 * 1 = 3,628,800 de posibilidades. En el caso de 20 ciudades por visitar el numero de posibilidades aumenta a: 2,432,902,008,176,640,000. Si cada combinacion es analizada a una velocidad de 1ms (0,001 segundo) un ordenador comun tardaria alrrededor de 77,146,816 años en encontrar la combinacion de ciudades para la ruta mas corta.


Ejemplo de differentes crecimientos. En azul: Crecimiento Lineal, en Naranja: Crecimiento Exponencial, en Gris: Crecimiento Factorial

Existen diferentes estrategias para resolver el problema TSP y los Algoritmos Geneticos han demostrado ser una buena opcion cuando se enfretan problemas de combinacion. En la tabla de abajo se pueden ver 9 pruebas de un simple AG y sus resultados.



Algoritmo Genetico
Parametros Descripcion
1 Poblacion Tamaño de la poblacion
2 Seleccion Natural Cuantas veces el individuo mas apto (la combinacion de ciudades con la ruta mas corta) sera seleccionado para la siguiente generacion
3 Cruce El cruce es de 1 punto y es a la mitad de los genes del individuo
4 Porcentaje de Mutacion Porcentaje de individuos a mutar
5 Numero de Generaciones Numero de generacion que se ejectura el algorimo
6 Mutacion Individuo Cuanta mutacion asumira el individuo
7 Presion Ruleta La "presion" en la seleccion natural tipo ruleta. Mientras mas grande es este valor mas individuos hay en la ruleta y mas determinista es el algoritmo



En verde la longitud original y en amarillo luego de la optimizacion



Designemergente ha utilizado Algoritmos Geneticos para distribuir cableados electricos en zonas con muchos puntos de iluminacion



0 Comments:

Add a comment