En la disciplina de la Investigación Operativa, el algoritmo de optimización por colonia de hormigas (Ant Colony Optimisation – ACO) es una técnica para resolver problemas combinatorios complejos inspirada por el comportamiento que muestran las hormigas en la naturaleza, la inteligencia de enjambre. Este algoritmo fue propuesto por Marco Dorigo en 1992.
El origen
Una colonia de hormigas es capaz de encontrar la ruta más corta desde su hormiguero a una fuente de comida gracias a las feromonas que desprenden. Cuando una hormiga encuentra comida, regresa a su hormiguero mientras secreta feromonas muy atractivas para las otras hormigas. Estas feromonas funcionan a todos los efectos como un rastro de señales que el resto de la colonia tenderá a seguir.
Debido a lo grande de las poblaciones de hormigas, lo habitual es que sean varias las hormigas que encuentran diferentes rutas de diferente distancia entre el hormiguero y la comida. Aquí entra en juego la volatilidad de las feromonas, cuya intensidad decrece con el tiempo por lo que las rutas más largas, que exigen más tiempo para ser recorridas, presentan un rastro menos intenso que las cortas, resultan menos atractivas y son recorridas con menos frecuencia. De esta manera, el rastro de feromonas de las rutas más cortas es reforzado.
Esta técnica se aplica para encontrar soluciones alternativas a problemas clásicos como el Travelling Salesman y presenta la ventaja de adaptarse dinámicamente a cambios en las condiciones del problema. ACO puede ser utilizado en problemas reales relacionados con enrutamiento, muy útil por ejemplo para empresas de paquetería
Este heurístico combina de forma eficiente dos elementos de información. Por un lado, la distancia entre puntos de los diferentes caminos trazados (cuanto más cerca tienes el siguiente punto más probable es dirigirte a él); por otro, la feromona, es decir, la información de soluciones exploradas previamente. Así, cuando estamos en un punto A, los más cercanos son más atractivos, pero en soluciones anteriores ir de A a cada punto ha dado lugar a mejores o peores soluciones. Este algoritmo combina de forma equilibrada las dos fuentes de información.
Juego
Para mostrar el algoritmo ACO en funcionamiento, hemos creado un pequeño juego de demostración en este enlace.
– Dibuja 10 puntos en el lienzo. Para hacer el juego más interesante, nosotros dibujaremos otros 10 puntos de manera aleatoria.
Si pulsas sobre el icono de los dados, nos encargaremos de dibujar los puntos que falten hasta llegar a 20.
– Traza la ruta más corta que pase por todos los puntos, una sola vez por cada uno y que termine en el punto inicial. Solo necesitas pulsar sobre cada uno de los puntos. Por simplicidad, no es posible deshacer trazos, así que ten cuidado con no equivocarte.
– Cuando hayas terminado, el algoritmo de ACO resolverá el problema durante un máximo de 20 segundos y te mostrará la mejor solución que haya obtenido.
– La solución con la distancia más corta, gana.
¡Buena suerte!
Nota: por simplicidad, este juego esta diseñado para pantallas grandes: disfrútalo en tu PC o Mac.
Seguro que quieres saber más, suscríbete a nuestro canal y newsletter de linkedin
Iconos por: @flaticon
Imagen por: Poranimm @Athithawatthee from Pexels
