Las hormigas ya resolvieron el problema del viajero
Casi toda la ingeniería —y buena parte de las ciencias de la computación— se reduce a problemas de optimización: maximizar o minimizar algo. El precio de un producto, el material que vas a usar, el tiempo. Si diseñas un medio de transporte, maximizar la velocidad y también la seguridad.
Uno de los más conocidos es el problema del viajero, o del comerciante viajero.
El enunciado
Una persona quiere visitar varias ciudades y quiere hacerlo recorriendo la menor distancia posible.
Con dos o tres ciudades es fácil calcularlo a mano: sabes las distancias, sabes cuánto tardas, decides a dónde ir primero.
Y tú tienes este problema todo el tiempo sin llamarlo así. Tienes que ir a visitar a tu abuelita, pasar a ver a un cliente y hacer el súper. En qué orden lo haces es exactamente el problema del viajero.
Por qué se vuelve imposible
Este problema es factorial. Entre más lugares tengas que visitar, el número de rutas posibles crece de una forma que rompe cualquier intuición.
Y aquí está la parte que cuesta aceptar: existe un algoritmo que lo resuelve exactamente. El problema no es que no sepamos cómo. El problema es que, con suficientes ciudades, puede tardar años en darnos la respuesta.
Un algoritmo correcto que tarda años es, en la práctica, un algoritmo que no tienes.
Por eso existen las heurísticas
Una heurística es una función que aproxima el resultado y lo consigue en mucho menos tiempo.
No te da la ruta óptima. Te da una ruta buena, ahora. Y en casi todos los problemas reales, una respuesta buena hoy vale infinitamente más que la respuesta perfecta el año que viene.
Lo que hacen las hormigas
Aquí es donde la naturaleza ya tenía una solución.
Si has tenido oportunidad de observarlas, las hormigas hacen un caminito desde su colonia hasta la comida. Cómo llegan a él es lo interesante.
Las exploradoras caminan un tanto al azar y un tanto no, hasta que encuentran la comida. Y de regreso van dejando un camino de feromonas para que las demás reconozcan por dónde ir.
Como son muchos individuos, ese camino se va reforzando: cada hormiga que pasa deja más feromonas. Las rutas más cortas se recorren más veces en el mismo tiempo, así que acumulan más señal, así que atraen más hormigas. Hasta que todas van en fila.
Ninguna hormiga calculó nada. Ninguna conoce el mapa. Y aun así el grupo converge a una ruta muy buena.
Eso, convertido en algoritmo, es la optimización por colonia de hormigas. Y existe también la optimización por enjambre de partículas, con la misma lógica desde otro modelo natural. Los algoritmos evolutivos son otro miembro de la misma familia.
Lo que tienen en común
Los tres hacen lo mismo: muchos intentos baratos, refuerzo de lo que funcionó, y ninguna necesidad de entender el problema entero.
Es la estrategia contraria a la que nos enseñan. Nosotros aprendemos a analizar, planear y después ejecutar. Estos métodos exploran mal, muchas veces, y dejan que la buena solución se acumule sola.
Funciona sorprendentemente bien justo en los problemas donde analizar de antemano es imposible.
Este texto sale del episodio 009 del Podcast Algoritmos, sobre la biónica.