Thursday, May 20, 2010

Swarm intelligence for optimal path solution / Inteligencia de enjambre para soluciones de ruta optima


El proceso de optimizacion de colonia de hormigas es un proceso de reglas muy simples pero de efecto muy potente en condiciones de información limitada (como en el caso de la mayoria de nuestros problemas reales), y por medio de uso de agentes que van dejando "rastros" de su paso por una ruta especifica.

¿Podemos usar este metodo para la resolucion de problemas prácticos en nuestra vida diaria? En efecto, sí se puede. Esta aproximación a un problema práctico se plantea hace muchos años en 1856, y a la hora de que los diseñadores del Parque Central en Nueva York debian definir las rutas que tendrían los pasos peatonales.

La respuesta de Robert J. Dillon, uno de los diseñadores, fue que la definición de estos caminos debía postponerse hasta que los mismos peatones hubieran establecido las mejores rutas por su uso. Esto es, propuso apovechar la inteligencia de enjambre de la población de Nueva York que hacía uso del parque, para determinar las rutas mas eficientes. Aquellos caminos mas utilizados se irian marcando solos a medida que el paso de peatones impide el crecimiento de vegetación.

El paso de peatones y el subsecuente retraso en el crecimiento de la vegetación por este paso, equivale al rastro de feromona que dejan las hormigas. Además el crecimiento posterior de vegetacion en caso de no haber mucho transito de peatones, equivaldría a la evaporación de feromonas, resultando en una disminución no lineal de rastros, y borrado de rutas no privilegiadas.

Este fenomeno es ampliamente visible en una variedad de situaciones y por una variedad de fuentes:
1.- Caminos mas transitados por montañistas en los cerros,
2.- Sitios de recomendación de otros sitios de Internet (tales como Digg.com, o Stumbleupon, en cuales casos los cibernautas dejan recomendaciones de sitios preferidos, equivalentes a "rastros" de feromona visibles por otros cibernautas),
3.- Senderos trazados por los bosquimanos en el desierto del Kalahari,
4.- Senderos cordilleranos usados por ganado pastando o migrando, senderos en bosques utilizados por pequeños mamiferos,
5.- etc.

Desafortunadamente la idea no fue acogida, pero este ejemplo de feedback positivo ha sido probado ser un metodo de obtencion de soluciones eficientes.

"Ant Colony" optimization is a process of very simple rules, but of very powerful effect in conditions of limited information (most of our real problems), and through the use of agents that leave trails of their path through a specific route.

Could we use a similar procedure to resolve traveling and networking problems in our own lives? Robert J. Dillon, one of the original Central Park commissioners, had one idea when he suggested in 1856 that the planning of pathways in the park should be postponed until New York City pedestrians had established them by habit, with the more deeply marked paths corresponding to those that were most used and therefore most efficient.

In other words, he proposed making use of the Swarm Intelligence of the population that used Central Park to determine those routes. Those routes used most frequently would become clear as each transit delayed vegetation growth (equivalent to the pheromone trail in the case of an ant colony). On the other hand, if a route was less travelled, vegetation would slowly start to grow again, process that would be equivalent to feromone evaporation, leading to a non-linear elimination of less-privileged routes.

This phenomenon is evident in a series of situations:
1.- Walking trains in mountains, situation similar to the central park example,
2.- Recommendation sites such as Digg.com or StumbleUpon (user recommendation would amount to "pheromone" creation as the recomendation is seen by other users),
3.- Bushmen trails through the kalahari desert,
4.- Trails through forests as used by small animals, etc.

Dillon did not get his way, but recent research by German traffic engineer Dirk Helbing and his colleagues has shown that Dillon’s solution, a neat example of ant colony optimization as practiced in human society, would have been a good one.

No comments:

Post a Comment

ShareThis