Podrías dedicar toda tu vida a escoger el mejor itinerario para estas vacaciones, así que pregúntale a una hormiga

El problema del viajante es un acertijo endiabladamente complejo. Tan complejo, de hecho, que nadie es capaz de solucionarlo. A no ser que nos fijemos en las hormigas, claro: entonces la solución surge diáfana.

Pero vayamos por partes: ¿Qué es el problema del viajante? ¿Por qué es importante para escoger destino en vuestras próximas vacaciones?

Imaginaos que tenéis muchos días de vacaciones por delante y que aspiráis a visitar muchos lugares diferentes. El problema es que disponéis de un presupuesto limitado, y el tiempo no es infinito. Así que debéis optimizar. Escoger el camino más corto que os pueda llevar a todos esos sitios antes de volver a casa, sobre todo si esos sitios están muy separados entre sí.

Si vuestras opciones son un puñado de ciudades, tipo Moscú, París y Madrid, por ejemplo, la respuesta es relativamente fácil: imaginad que partís de Barcelona, pues lo más eficaz es ir primero a Moscú, luego saltar a París, y luego a Madrid, y finalmente a casa, o viceversa. Viajar primero a París, luego a Madrid, y finalmente a Moscú, por ejemplo, nos haría perder más tiempo de vuelo, y probablemente gastar más dinero.

Con tres ciudades en liza, por ejemplo, solo tenéis seis opciones a tener en cuenta. Calculáis el kilometraje de esa seis opciones, y listo: escoged la que implique menos kilometraje. Sin embargo, si añadimos una ciudad más, y tenemos cuatro, entonces el número de rutas a tener en cuenta ya es 24, en lugar de 6. Si añadimos una quinta ciudad, hay 120 rutas posibles. Si queremos visitar 10 ciudades, entonces… hay 3.600.000 rutas posibles. Si aspiráis a visitar 30 ciudades… entonces el número de rutas posible sería tan elevado que no vale la pena ni que lo escriba.

Calcular entonces cuál es la ruta más eficiente resulta largo, tedioso y hasta cierto punto imposible. Pero… aquí llegan las hormigas para salvarnos.

Las hormigas virtuales

En realidad no son hormigas que podemos encontrar en nuestro jardín, sino hormigas virtuales, generadas por ordenador, que siguen a rajatabla simples patrones. Dichas hormigas cooperan entre ellas, prueban los caminos posibles, y finalmente hallan el más corto de todos para el viajante. El secreto de las hormigas son las “feromonas virtuales”, es decir, una serie de marcas que las demás hormigas pueden detectar.

Lo explica así Peter Miller en su libro La manada inteligente:

Imaginemos un mapa en el que hay marcadas quince ciudades que el viajante debe visitar. Al principio del primer ciclo, las hormigas se dispusieron al azar en todas las ciudades. Luego cada hormiga utilizaba una fórmula basada en la probabilidad para decidir qué ciudad visitaría a continuación. Esa fórmula tenía en cuenta dos factores: cuál era la ciudad más próxima y cuál tenía el rastro de feromonas más intenso. Al principio no había rastros de feromonas, pero lo que tendían a seleccionarse las ciudades más cercanas. En cuanto cada hormiga había completado el recorrido que las había llevado por las quince ciudades, regresaba siguiendo el mismo camino y volvía a expulsar feromonas virtuales durante el trayecto. Las rutas más cortas que descubrieron las hormigas tendían a recibir más feromonas, mientras que en las más largas esas feromonas se “evaporaban” más rápidamente. Eso permitía que las hormigas, como colectivo, fueran capaces de recordar las mejores rutas.

En el segundo viaje de las hormigas, se escogieron rutas con más feromonas, en base a los éxitos ya obtenidos. En el tercer viaje, lo mismo. A medida que las hormigas repetían sus viajes una y otra vez, las hormigas reducían así su tiempo de viaje. De esta manera, las hormigas hallaron soluciones óptimas para 30, 50 e incluso 100 ciudades.

Esta clase de programas quizá se implanten algún día en nuestros teléfonos móviles o GPS´s, y así podremos escoger las mejores rutas para viajar (al menos desde un punto de vista de eficiencia). Y los resultados no serán producto de horas y horas de reflexión humana, sino simplemente dejar que una colonia de hormigas tontas repita una y otra vez el viaje.

Fotos | Wikipedia