Evidencia 11

perceprton INTRODUCCIÓN:

Optimización mediante Ant Colony Optimization (ACO) es una técnica probabilista creada por Marco Doringo en 1992 utilizada para solucionar problemas de cómputo; este algoritmo está inspirado en el comportamiento que presentan las hormigas para encontrar las trayectorias desde la colonia hasta el alimento.

En la naturaleza, las hormigas vagan aleatoriamente en su búsqueda de alimento, y a lo largo de su camino de regreso a la colonia depositan una hormona denominada feromona. Si otras hormigas encuentran este rastro, lo más probable es que sigan este camino para depositar el alimento en la colonia.
Con el paso del tiempo el rastro de la feromona comienza a evaporarse y se reduce su fuerza atractiva. Las hormigas que siguen el rastro aumentan la cantidad de la feromona, con lo que el rastro es más fuerte y dura más tiempo.
Cuantas más hormigas recorran ese camino, más intenso será el olor de la feromona, lo que estimula a más hormigas a seguir esa trayectoria.
Desde el punto de vista algorítmico, la evaporación de la feromona tiene la ventaja de provocar la convergencia a una solución localmente óptima. Si no hubiera evaporación, todas las trayectorias posibles serían igualmente atractivas para las hormigas. Esta situación haría que las trayectorias menos usadas por las hormigas, fueran igual de atractivas que las más utilizadas.
Así, cuando una hormiga encuentra una buena trayectoria de la colonia a una fuente de alimento, es más probable que otras hormigas sigan esa trayectoria, y la regeneración de la feromona provoca que finalmente todas las hormigas sigan una sola trayectoria.
Este comportamiento es la base para el diseño del algoritmo, donde las "hormigas simuladas" caminan alrededor del gráfico que representa el problema que solucionar.

Objetivo: Encontrar la solución más óptima para el problema del Agente Viajero (TSP- Traveling salesman problem) usando el algoritmo de ACO.

Justificación: Se escogió el problema del Agente Viajero porque es un problema que hemos resuelto pero con otros algoritmos heurísticos como el vecino más cercano (Nearest-neighbor algorithm) y queríamos ver como funcionaba el algoritmo de ACO en este tipo de problema.

Desarrollo:
El problema resuelto por medio de dos hormigas se encuentra en archivo pdf del siguiente enlace:


https://docs.google.com/file/d/0BzRiJ_wE61zsOWxScEExWHNLWTQ/edit?usp=sharing

Código:

https://docs.google.com/file/d/0BzRiJ_wE61zsclFteWJSdHRjdE0/edit?usp=sharing


Resultado: De los caminos hechos por las 8 hormigas a las cuales evaluamos en el programa , observamos que en las primeras 5 hubo variaciones, pero las ultimas 3 tomaron el mismo camino. El camino que tuvo mas repeticiones fue: 0-3-1-2-0 es decir: A-D-B-C-A. Por el cual pasaron las hormigas 4,6,7 y 8.


Video en Youtube:
.

h


Conclusiones:

El algoritmo de ACO no es muy exacto porque este depende de la cantidad de hormigas que se usen así como si hay muchas ciudades, el algoritmo cada vez se va haciendo más inexacto y se requieren más operaciones, si hay muchas ciudades en ese caso es necesario más hormigas por lo que el resultado puede variar
En el problema hecho a mano el resultado fue diferente porque la computadora es más exacta a la hora de elegir un número aleatorio esa es una variación ya que no se escoge el camino más corto sino que es por medio de % de probabilidad de que se elija un camino teniendo más probabilidad el que sea más corto sin embargo el camino que se elija no puede ser siempre el más corto variando a veces haciendo que a veces el resultado puede variar por 1 o 2 caminos respecto al más exacto.