He comenzado a programar algunas heurísticas y meta-heurísticas para la resolución de problemas de rutas. La última novedad, es que ya está funcionando (y en fase de pruebas) la resolución del problema del viajante de comercio (TSP), mediante algoritmo de hormigas (Ant Colony Optimization).
El Algoritmo hormiga o algoritmo de las hormigas es una técnica probabilística para solucionar problemas de cómputo inspirado por el comportamiento de las hormigas para encontrar las trayectorias de la colonia al alimento.
En el mundo real, las hormigas (inicialmente) vagan aleatoriamente, y en el camino de vuelta a la colonia depositan una hormona denominada feromona. Si otras hormigas encuentran tal trayectoria lo más probable es que sigan esta trayectoria para depositar el alimento en la colonia.
En un cierto plazo, sin embargo, el rastro de la feromona comienza a evaporarse y se reduce su fuerza atractiva. Cuanto más tiempo sigue una hormiga el recorrido bajo la trayectoria de la feromona, más tiempo tarda este en evaporarse.
Cuanto mayor número de hormigas viajan tras esta trayectoria, más intenso es el olor de esta sustancia lo que provoca en las hormigas el estímulo de seguir en esa trayectoria.
La evaporación de la feromona tiene también la ventaja de evitar la convergencia a una solución localmente óptima. Si no hubiera evaporación en todas las trayectorias elegidas por las primeras hormigas tenderían a ser excesivamente atractivas para las siguientes. En ese caso, la exploración del espacio de la solución sería muy elevado.
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 todas las hormigas sigan una sola trayectoria. La idea del algoritmo de la colonia de la hormiga es idéntico al comportamiento de las «hormigas simuladas» que caminan alrededor del gráfico que representa el problema a solucionar.
Referencias:
- M. Dorigo, 1992. Optimization, Learning and Natural Algorithms, PhD thesis, Politecnico di Milano, Italy.
- M. Dorigo, V. Maniezzo & A. Colorni, 1996. «Ant System: Optimization by a Colony of Cooperating Agents», IEEE Transactions on Systems, Man, and Cybernetics–Part B, 26 (1): 29–41.
- M. Dorigo & L. M. Gambardella, 1997. «Ant Colony System: A Cooperative Learning Approach to the Traveling Salesman Problem». IEEE Transactions on Evolutionary Computation, 1 (1): 53–66.
- M. Dorigo, G. Di Caro & L. M. Gambardella, 1999. «Ant Algorithms for Discrete Optimization». Artificial Life, 5 (2): 137–172.
- E. Bonabeau, M. Dorigo et G. Theraulaz, 1999. Swarm Intelligence: From Natural to Artificial Systems, Oxford University Press. ISBN 0-19-513159-2
- M. Dorigo & T. Stützle, 2004. Ant Colony Optimization, MIT Press. ISBN 0-262-04219-3
- M. Dorigo, 2007. «Ant Colony Optimization». Scholarpedia.
Véase también:
- Ant Colony Optimization Home Page
- A list of dissertations related to the field of Ant Colony Optimization
- VisualBots – Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
- AntSim v1.0 A visual simulation of Ant Colony Optimization with artificial ants. (Windows Application)
- Ant Farm Simulator A simulation of ants food-gathering behaviour (Windows Application and source code available)
- ANT Colony Algorithm A Java Simulation of the Path Optimisation, on a changing ground. Presentation and source code available.