Las hormigas nos enseñan a viajar

Publicado el 8 de Noviembre de 2022 | Matemáticas

Hoy vamos a viajar… Bueno, más bien vamos a ver los problemas que supone viajar. Hay un problema de optimización que tenemos cuando nos movemos: llegar en el mínimo tiempo posible a un destino, recorriendo el camino más corto. Esto se llama históricamente: PROBLEMA DEL VIAJANTE.

Formalmente decimos: dado un conjunto de ciudades conectadas por carreteras, se trata de diseñar la ruta más corta que saliendo desde un determinado punto, recorra todas las ciudades y vuelva a dicho punto de partida. Eso hace el GPS, pero también lo hacen las hormigas. Sí, has leído bien.

En un primer acercamiento a este problema, alguien podría pensar, y tiene razón, que para resolverlo basta con probar con todas las rutas posibles, intercambiando el orden de las ciudades visitadas, calcular la longitud de cada una de esas posibles rutas y quedarse con la más corta. Bien. Salvo por el pequeño detalle de que esta solución solo es posible de calcular para un número muy pequeño de ciudades. Para que nos hagamos una idea, si tenemos 100 ciudades, ¡el número de rutas posibles es 100! (factorial de 100, no es que esté gritando) y 100!, créanme, es un número una barbaridad de grande. Es mucho más grande que el número de partículas elementales en el universo observable. Por lo tanto, este primer intento de solución no es válido ni con la potencia de cálculo de los ordenadores.

¿Qué hacemos cuando no podemos encontrar la solución óptima (la mejor) ni siquiera con ordenadores? Pues tratar de buscar la más buena posible, por aquello de que a falta de pan... Para ello, lo que se puede usar, por ejemplo, son los llamados algoritmos genéticos: algoritmos que tratan de simular el proceso darwinista mediante el cual la naturaleza consigue especies que se adapten a su medio.

Y si hablo de Darwin, hablamos de vida, de evolución, y vamos a las hormigas. Concretamente, al problema de Optimización por Colonia de Hormigas. El investigador de Inteligencia artificial, Marco Dorigo describió en 1997 un método que genera “buenas soluciones” para el Problema del Viajante usando una simulación de una colonia de hormigas llamada ACS (Ant Colony System). El cual modela el comportamiento observado en las hormigas reales de encontrar caminos cortos entre las fuentes de comida y su nido, emergió como un comportamiento la preferencia de cada hormiga de seguir el sendero de feromonas depositado por las otras hormigas.

ACS envía un gran número de hormigas (agentes virtuales) para explorar las posibles rutas en el mapa. Cada hormiga elige probabilísticamente la próxima ciudad a visitar combinando la distancia a la ciudad y la cantidad de feromonas depositadas en la ruta hacia la ciudad. La hormiga exploradora, deposita feromonas en cada arista que ella cruce, hasta que complete todo el camino. En este punto la hormiga que completó el camino más corto deposita feromonas virtuales a lo largo de toda la ruta recorrida (actualización del camino global). La cantidad de feromonas depositadas es inversamente proporcional a la longitud del camino: el camino más corto, tiene más cantidad de feromonas.

Las hormigas nos dan una lección y nos han inspirado para programar y entender algo mejor nuestro mundo. El GPS usa este algoritmo, pero lo usamos casi todo el rato para casi todo. Nuestro día a día es ensayo y error, y una toma de decisiones constante en base a esas buenas soluciones que de vez en cuando encontramos. ¡Gracias, hormigas!

Aplicación en el aula

Un algoritmo es un proceso de operaciones en base de decisiones, buscando una solución óptima. Por ejemplo, esto es un algoritmo:

Las hormigas nos enseñana a viajar