Con esta nota doy comienzo a la serie algoritmos genéticos, en la que abordaré varios problemas que pueden ser resueltos con estos algoritmos. En cada temporada explicaré la solución e implementación a un problema particular, el primer problema es el agente viajero y dicha solución será escrita en Python.
Descripción del problema
El Problema del Agente Viajero– TSP(Travelling Salesman Problem), consiste en que dadas n ciudades que tiene que visitar un vendedor, se requiere encontrar el camino más corto para que, partiendo de una de ellas, visitarlas todas sin pasar más de una vez por ninguna y volviendo, finalmente, a la ciudad de partida.
Figura 1. Problema del agente viajero.
A primera vista se puede pensar que este problema es muy sencillo de resolver por medio de la fuerza bruta, es decir, calculando cada uno de los recorridos posibles y eligiendo el óptimo de ellos. Tal vez esta solución suena muy atractiva cuando tenemos un recorrido pequeño como en la Figura 1, pero ¿qué ocurre si tenemos una cantidad increíblemente grande de ciudades por recorrer? Como es el caso de China(ver Figura 2), entonces esta solución ya no es nada atractiva, pues es completamente ineficiente.
Figura 3. Recorrido óptimo de las ciudades de China. Imagen tomada de University of WATERLOO.
¡Es impresionante!
Cuando nos encontramos con problemas de optimización de la clase NP-Completos, como es el caso del problema del agente viajero, es necesario recurrir a algoritmos evolutivos, como lo son los algoritmos genéticos.
Durante esta temporada utilizaré como instancia las ciudades de Djibouti, ilustradas en la Figura 5. Elegí esta instancia solamente por fines prácticos, ya que la simplicidad de sus recorridos serán de mucha utilidad cuando estemos en la etapa final de esta temporada y llevemos a cabo las pruebas del algoritmo. Si deseas utilizar otra instancia puedes obtener información en el siguiente enlace.
Figura 4. Djibouti cuenta con tan solo 38 ciudades. Imagen tomada de University of WATERLOO.Figura 5. Ciudades de Djibouti ilustradas como puntos. Imagen tomada de University of WATERLOO.
Nuestro objetivo será encontrar el recorrido óptimo para esta instancia del problema del agente viajero.
Figura 6. Recorrido óptimo del agente viajero de las ciudades de Djibouti. Imagen tomada de University of WATERLOO.
Las coordenadas de la ciudades ubicadas en este mapa las puedes obtener de puntos-dj38.tsp.
Espero que este problema sea lo suficientemente interesante para ti, para seguir esta temporada y así descubrir la solución y su implementación con algoritmos genéticos. En la siguiente nota explicaré y definiré la base del algoritmo: el cromosoma. ¡Hasta entonces!
One comment
Hola cada ciudad seria una variable la cual se le encontraria el minimo entre ellas?
Publicado por 
Hola cada ciudad seria una variable la cual se le encontraria el minimo entre ellas?