
Senderos de hormigas
Insectos sin mapa que enseñan a los ordenadores a encontrar el camino
✦ Confirmado
Ninguna hormiga conoce un mapa. Aun así, toda la colonia encuentra el camino más corto hasta la comida. Un joven italiano convirtió ese truco en un programa informático.
Quién: Jean-Louis Deneubourg, Marco Dorigo · Cuándo: 1989–1992 · Dónde: Bruselas, Bélgica y Milán, Italia
Naturaleza e invento
Las hormigas marcan el camino con un olor, una feromona. En el sendero más corto las hormigas vuelven antes, así que el olor se concentra y atrae a más. El camino más largo se va desvaneciendo.
Algoritmos de hormigas, es decir, programas en los que hormigas virtuales buscan buenas rutas para camiones, planes de producción y tráfico en redes informáticas.
El relato
A finales de los años 80, el equipo belga de Jean-Louis Deneubourg planteó una tarea a hormigas argentinas: dos puentes, uno corto y otro largo, llevaban del nido a la comida. Al principio las hormigas usaban ambos caminos por igual.
Al cabo de unos minutos casi toda la colonia había elegido el puente más corto. Nadie lo dirigía. Bastó con que las hormigas del camino más corto volvieran antes y lo marcaran más a menudo.
Marco Dorigo, doctorando del Politécnico de Milán, concluyó que aquello era una receta lista para problemas matemáticos difíciles. En 1992, en su tesis doctoral, describió el primer algoritmo de hormigas: hormigas virtuales recorren un mapa de ciudades, dejan un olor digital, y el olor se evapora.
Hoy los algoritmos de hormigas son una de las familias de métodos de optimización. Se usan para planificar rutas de reparto, asignar tareas e investigar el enrutamiento en redes informáticas.
Cómo funciona
- Olor: Cada hormiga que vuelve con comida marca el camino. Las siguientes prefieren los senderos que huelen más fuerte.
- Refuerzo: El camino corto se recorre más rápido, así que recibe más olor en el mismo tiempo. Una buena ruta se refuerza sola.
- Evaporación: En el programa el olor desaparece poco a poco. Así las hormigas virtuales no se quedan atascadas en la primera ruta, elegida al azar, y siguen buscando una mejor.
Compruébalo tú mismo
- Dos caminos hacia el azúcar: En verano, pon una gota de miel a dos distancias de un sendero de hormigas, con dos palitos como puentes: uno corto y otro largo. Pasado un cuarto de hora, cuenta las hormigas de cada puente.
- Borra el rastro: Pasa un dedo a través de un sendero de hormigas sobre una baldosa. Observa cómo las hormigas se desorientan en ese punto y buscan el olor.
- Hormigas en papel: Dibuja cinco ciudades en una hoja y busca la ruta más corta que pase por todas. Cuenta cuántas rutas son posibles. Con veinte ciudades hay más que granos de arena en una playa.
Lo que se sabe con certeza
Los experimentos de los puentes fueron descritos por Goss, Aron, Deneubourg y Pasteels en 1989. El algoritmo de hormigas lo propuso Marco Dorigo en 1992 y desde entonces es un método muy utilizado para resolver de forma aproximada problemas de rutas. No siempre da el mejor resultado, pero normalmente uno bueno y rápido.