Algoritmo de Optimización por Colonia de Hormigas (ACO)

Como vimos en la parte de teoría, el problema del viajante es un problema clásico:

Imaginemos una distribución de ciudades en un mapa. Somos un vendedor que quiere visitarlas todas, sólo una vez cada una, gastando el menor combustible posible.

El algoritmo se basa en varias generaciones sucesivas de hormigas que recorren el mapa viajando de ciudad en ciudad, eligiendo su siguiente ciudad de manera aletoria hasta que las han recorrido todas. En cada etapa del viaje, las hormigas eligen moverse de una ciudad a otra teniendo en cuenta las siguientes reglas:

Debe visitar cada ciudad exactamente una vez, excepto la inicial en la que estará dos veces (salida y llegada final);
Una ciudad distante tiene menor posibilidad de ser elegida (Visibilidad);
Cuanto más intenso es el rastro de feromonas de una arista entre dos ciudades, mayor es la probabilidad de que esa arista sea elegida;
Después de haber completado su recorrido, la hormiga deposita feromonas en todas las aristas visitadas, mayor cantidad cuanto más pequeña es la distancia total recorrida;
Después de cada generación, algunas feromonas son evaporadas.



In [ ]:

    
#Comencemos importando los paquetes necesarios:

%matplotlib inline  
import numpy as np # Usaremos arrays
import matplotlib.pyplot as plt # Para pintar resultados
import ants as ants # Aquí están los objetos del algoritmo

Lo primero que vamos a hacer es crear un mapa que contenga nuestras ciudades. Como primer argumento le pasamos el número de ciudades, y como segundo, el tamaño del mapa. Al ser creado, el mapa generará automáticamente las ciudades en posiciones aleatorias.



In [ ]:

    
map1 = ants.Mapa(10)

Podemos ver el mapa con las ciudades unidas por líneas cuyo grosor depende de la distancia entre ellas:



In [ ]:

    
map1.draw_distances()

A continuación, lo siguiente que tenemos que hacer es crear un enjambre de hormigas. Con esta función, lo podremos hacer fácilmente.



In [ ]:

    
map1.swarm_create(100) # Creamos un enjambre de 100 hormigas

Si queremos ver dónde se encuentran nuestras hormigas en un momento dado, podemos hacerlo:



In [ ]:

    
map1.swarm_show()

Podemos comprobar fácilmente que la matriz de distancias es simétrica, y que la matriz de feromonas aún está vacía:



In [ ]:

    
map1.show_distances_matrix()
map1.show_feromones_matrix()

Empecemos a mover a nuestras hormigas!

Para que la primera generación de hormigas recorra el mapa llamaremos a la función swarm_generation():



In [ ]:

    
map1.swarm_generation()

Veamos cómo ha cambiado las feromonas!



In [ ]:

    
map1.show_feromones_matrix()
map1.draw_feromones()

Para poder encontrar una buena ruta, necesitaremos que pasen unas cuantras generaciones más... Pongamos que 50



In [ ]:

    
for i in range(50):
    print(i, end = '·')
    map1.swarm_generation()
map1.show_feromones_matrix()
map1.draw_feromones()

Parece que las hormigas ya tienen claros sus caminos favoritos!

Veamos qué pinta tiene el mejor camino que han encontrado:



In [ ]:

    
map1.draw_best_path()

Podemos borrar las feromonas y empezar de nuevo el algoritmo, para ver si siempre llegan a la misma solución. No te preocupes, al algoritmo no borrará la mejor ruta encontrada.



In [ ]:

    
for j in range(3):
    map1.feromone_reset()
    print()
    print('Ejecución', j+1, ', generación: ')
    for i in range(50):
        print(i+1, end = '·')
        map1.swarm_generation()
    map1.draw_feromones()

El algoritmo podría haber encontrado una ruta mejor, comprobémoslo:



In [ ]:

    
map1.draw_best_path()

Podemos observar cómo han ido variando las longitudes máxima, mínima y media de los caminos de las hormigas en cada generación, y compararlas con la del mejor camino encontrado:



In [ ]:

    
map1.draw_results()

También podemos dibujar las longitudes mínimas de cada ejecución del algoritmo:



In [ ]:

    
map1.draw_best_results()

Ajuste fino de las Feromonas

Supongamos ahora que queremos optimizar una ruta entre 40 ciudades:



In [ ]:

    
map2 = ants.Mapa(40)
map2.swarm_create(200)
map2.swarm_generation()
map2.show_feromones_matrix()
map2.draw_feromones()

¿Qué pasa? ¡No hay feromonas!

La solución es muy simple: las hormigas "standard" están adaptadas a mapas más pequeños, y no dejan tras de sí suficiente feromona como para que no se evapore toda.

Para solucionarlo, podemos modificar a nuestras hormigas para este entorno:



In [ ]:

    
#Con un valor de 5 es suficiente
map2.feromone_fine_tune()



In [ ]:

    
map2.swarm_generation()
map2.show_feromones_matrix()
map2.draw_feromones()



In [ ]:

    
for i in range(25):
    print(i, end = '·')
    map2.swarm_generation()
map2.show_feromones_matrix()
map2.draw_feromones()
map2.draw_best_path()
map2.draw_results()

Te toca trabajar

Ahora que ya hemos visto cómo funciona este algoritmo, probemos a cambiarlo. ¿Cómo funcionaría si no todas las ciudades estuvieran conectadas entre sí? Intenta cambiar el algoritmo para modelar este caso. Probablemente la manera más fácil sea modificar la matriz de distancias, hinchando el valor de algunas distancias por encima de su valor real para penalizar ciertas rutas. ¿Qué pasaría si la matriz se quedara asimétrica?

Una vez que lo hayas conseguido, te propongo el problema de enrutación de paquetes: En vez de recorrer todo el mapa, intenta ir de un nodo dado a otro. Puedes añadir feromonas atractivas en ciertos nodos para representar que son nodos de la red que están sobredimensionados, o crear feromonas negativas y esparcirlos por otros nodos para representar enlaces que están sobrecargados y es mejor evitar. Recuerda que las feromonas se disipan un poco cada generación, para efectos duraderos deberas añadirlas también cada turno.



In [ ]:



In [ ]:



In [ ]:

Siro Moreno, Aeropython, 8 de Noviembre de 2015



In [ ]: