Hormigas computacionales.
Uno de los problemas básicos en matemática es el de optimización. Encontrar el punto en el que una determinada función alcanza el máximo (maximización) o el mínimo (minimización). Es tan obvio el interés de las técnicas de optimización que no vale la pena insistir en ello. Sin embargo, el problema es muy general, y no admite un tratamiento global. Para empezar, el punto que se quiere encontrar puede ser cualquier cosa, dependiendo del problema. Los alumnos de bachiller hallan puntos en los que una función real de variable real tiene un extremo, pero la vida real es mucho más diversa. Vamos a hablar de un problema concreto que es un paradigma de complejidad computacional: el Problema del Agente Viajero, conocido en computación como el problema STP, por sus siglas en inglés.Un agente debe recorren n ciudades, y entre los posibles recorridos, debe elegir el más corto que pase por todas ellas para volver a la primera. Se conoce la matriz de distancias cruzadas entre las n ciudades, obviamente. Es muy fácil hacer un programa que de con la solución óptima: existen n! recorridos, y si no es importante la ciudad de comienzo (n-1)! recorridos diferentes. Basta hallar la distancia de todos los caminos posibles y tomar el mínimo. El problema es que la función factorial crece endiabladamente, y con un puñado de ciudades necesitaríamos años de computación para encontrar el camino más corto. Con sesenta ciudades, el número de caminos es comparable al de partículas atómicas del universo, y procesando un billón de ellas al segundo necesitaríamos más tiempo que la edad del cosmos para computarlas todas. No se conocen algoritmos que den la solución en tiempo polinómico (pero esa es otra historia que contaremos más adelante). Es evidente que necesitamos atajos.
Afortunadamente, estos existen, y sin bien no necesariamente nos proporcionan el óptimo, nos devuelven soluciones cercanas en tiempos aceptables. Vamos a hablar de uno de ellos, vistoso a más no poder, y de buenos resultados. Está inspirado en la naturaleza debido a la obviedad de que la evolución biológica lleva miles de millones de años ensayando estrategias para solucionar problemas (perdónenme los lectores la personalización de la evolución como algo capaz de tener intenciones y deseos de solucionar cosas, nada más lejos de mi intención; es sólo una metáfora).
Aquí es donde entran las hormigas. Cuando estos himenópteros van de un lugar a otro, podemos comprobar que siguen caminos muy cercanos al óptimo. Si un obstáculo impide el paso normal, tras ciertos titubeos iniciales se termina por rodear el obstáculo por el camino más corto. ¿Cómo lo consiguen?
La respuesta es decepcionante de puro simple. No hay inteligencia alguna tras esto: las hormigas siguen el camino de sus predecesoras porque huelen las feromonas que éstas van depositando a su paso. Ante una bifurcación, tienden a elegir el camino de más olor a hormiga. Entre varios caminos alternativos el más corto o más fácil estará más transitado por ser necesario menos tiempo en recorrerlo, y por ello, la exploración de los otros más penosos es un fenómeno transitorio: cada vez más hormigas tenderán a recorrer el más transitado, creando una realimentación positiva que solo cesará cuando los demás caminos sean olvidados. Además, las feromonas son volátiles: en cierto tiempo no quedará rastro de otro camino que el óptimo.
¿Cómo funciona un algoritmo de búsqueda basado en hormigas? Pues se ponen cierto número de hormigas a recorrer caminos entre las ciudades. Cada hormiga desde una ciudad elige la próxima de forma probabilística (las ya visitadas están excluidas de la búsqueda en cada ciclo) en función de la distancia entre sus vecinas, premiando las más cercanas ( es evidente que el recorrido óptimo no irá saltando entre ciudades lejanas unas de otras, pero no es claro que debo elegir siempre la más cercana, no mucho menos) y en función de la cantidad de feromona que hay entre ambas ciudades, premiando las rutas más olorosas. El programador debe ejustar la importancia relativa de estos dos aspectos con sendos parámetros. El nivel de olor no es sino un valor asociado a cada par de ciudades, que se ve incrementado cada vez que es elegido por una hormiga, y se ve decrementado en cierto porcentaje para simular la volatilidad. En cada ciclo computacional las hormigas avanzan un paso, y al cabo de n ciclos similares, cada hormiga ha regresado a la ciudad de la que partió.
Y vuelta a empezar. Se irán consolidado rutas, se irán olvidando otras, y al final; tras un criterio de parada establecido tendremos una buena aproximación al recorrido mínimo. El criterio de parada puede ser que se llegue al número máximo definido de ciclos completos, o que todas las hormigas sigan el mismo camino. En este último caso queda claro que no vale la pena continuar: la convergencia del algoritmo es clara. Ni siquiera en este caso tenemos asegurado que el recorrido obtenido será el óptimo, pero habremos obtenido una buena aproximación en un tiempo razonable.
Este tipo de técnicas nació con la tesis doctoral de Marco Dorigo en 1992 (Ant colony system). Actualmente existe toda una batería de métodos basados en esta idea, que difieren en la forma de actualizar el nivel de feromonas en cada tramo, principalmente. Dado que cada hormiga actúa con independencia (relativa) de las demás, se trata de computación en paralelo, y existen varias formas de paralelización; síncrona y parcialmente asíncrona.
Teneis una buena introducción a estos métodos en esta dirección
3 comentarios
Sildenafil -
jose antonio -
Jorge Moctezuma C. -
No he liedo por completo su artículo, más se que es lo que he andado buscando, de anticipado le doy mis más cumplidas gracias.
Posteriormente le enviare mis más amplios comentarios.
Saludos