Hormigas optimizadoras.

Las colonias de hormigas son capaces de resolver dinámicamente, y de manera óptima, problemas como encontrar el camino más corto entre dos puntos dentro de un laberinto.

Muchas de las ideas que utilizamos en ciencias de la computación han sido inspiradas por la Naturaleza. Así por ejemplo existen los algoritmos genéticos, que se basan en cierta idea de darwinismo para encontrar soluciones a ciertos problemas, sobre todo cuando queremos encontrar el mínimo de energía absoluto en un sistema en el que otros métodos caen en mínimos de energía locales de los que no salen. Existe también el método del enjambre (inspirado en la inteligencia colectiva de un enjambre de abejas) e incluso se pueden encontrar soluciones satisfactorias (aunque no necesariamente la mejor solución posible) al problema del viajante si nos inspiramos en las hormigas. De hecho hay un algoritmo denominado Ant Colony Optimisation (ACO) que se basa en el comportamiento de estos pequeños animales.
La pregunta es si podemos usar directamente a los animales sociales para resolver este tipo de problemas sin pasar por un ordenador y ver así las diferencias. Según han demostrado unos investigadores de la Universidad de Sydney eso mismo no sólo es posible, sino que han podido comprobar que las hormigas logran resolver un equivalente al problema de la torre de Hanoi sin demasiadas dificultades incluso cuando cambian las condiciones a mitad de juego.
La torre de Hanoi, en su versión más simple, consiste en tres barras verticales y tres discos agujereados por el centro de distintos tamaños. Se comienza con los tres discos apilados de mayor a menor (de abajo a arriba) en una de las barras y hay que moverlos a otra barra bajo ciertas restricciones en el menor número de movimientos posibles. Las reglas son que hay que mover los discos de uno en uno y que en ningún momento un disco esté sobre otro de menor tamaño.
Obviamente las hormigas no pueden mover discos de una barra a otra, así que los investigadores implicados crearon un laberinto (ver foto) de tal modo que encontrar el camino más corto entre dos puntos era equivalente a mover los discos en el menor número de movimientos posibles en el problema de la torre de Hanoi.
Este tipo de problemas de tratar de encontrar caminos más cortos en un grafo son típicos problemas de la matemática computacional. Para algunos de esos problemas tenemos algoritmos (Kruskal, Prim, Fleury, Dijkstra…) que nos dan la solución óptima en tiempo polinómico. Para otros problemas, como el problema del viajante o el de la mochila, al tratarse de problemas NP, no tenemos algoritmos que nos den eso mismo, sino algoritmos que nos dan una buena (o mala) aproximación en un tiempo polinómico. En estos últimos casos, si queremos tener seguro la solución óptima, no nos queda más remedio que enumerar por fuerza bruta todos los casos posibles y escoger el mejor, algo que tiene un coste computacional exponencial.
Encontrar el camino más eficiente a través de una red saturada es un desafío común en conductores, ingenieros y compañías telefónicas. Todos estos problemas se encuadran en lo que podemos denominar problemas de optimización y no hace falta decir que estos problemas tienen grandes implicaciones económicas. La optimización permite a una empresa de transportes ahorrar mucho dinero en combustible y una factoría puede producir más si los procesos de montaje están optimizados. Hay muchos problemas logísticos en el que se tiene que maximizar la eficiencia.
Por tanto, si encontramos pistas sobre cómo solucionar un problema de este tipo en la Naturaleza, aunque ya esté solucionado algorítmicamente, quizás lo podamos aplicar a otros casos que son especialmente duros computacionalmente.
Se sabe muy bien cómo solucionar el problema de la torre de Hanoi. Saber cómo se hace algorítmicamente forma parte del programa de estudios de las escuelas de ingeniería informática. Pero las hormigas quizás nos inspiren nuevos métodos algorítmicos para resolver otros problemas.
Quizás pensando en esto último, o simplemente en la diversión, Chris Reid, Madeleine Beekman y David Sumpter (éste de la Universidad de Upsala) pusieron a una colonia de hormigas argentinas (Linepithema humile) a resolver un problema de optimización dinámica de encontrar la ruta mejor en un laberinto.
Las hormigas son capaces de solucionar el problema aunque son sean seres muy simples. La “inteligencia colectiva” que emerge de ellas es suficiente para resolver el problema, aunque cada una de ellas, individualmente, sea incapaz de hacerlo. Recordemos que las hormigas crean caminos a través de unas señales de feromonas que van dejando en el suelo, reforzándose o debilitándose según el tráfico que haya, entre otros factores.
Aunque los algoritmos inspirados en la Naturaleza de los que hemos hablado antes funcionan satisfactoriamente, no necesariamente representan el mundo real de, por ejemplo, las hormigas. En general estos algoritmos son estáticos y están diseñados para resolver un tipo de problema en concreto. Los autores del estudio se plantearon cómo las hormigas reales podrían resolver un problema de optimización y cómo responderían a los cambios. Se preguntaban si sólo podían proporcionar una solución única fija o si se adaptarían a los cambios introducidos a mitad del juego.
En el laberinto equivalente al problema de la torre de Hanoi, las hormigas tenían que encontrar en camino más corto, de los 32768 caminos posibles entre un punto de entrada y otro en el que se colocaba una comida tentadora. Básicamente era un problema tipo Dijkstra en el que el peso de las aristas del grafo eran las longitudes de los segmentos del laberinto.
Al cabo de una hora las hormigas encontraron los dos caminos más cortos que representaban las dos posibles soluciones óptimas al problema. Estas soluciones eran las que más tráfico de hormigas contenían. Entonces los investigadores bloquearon algunos caminos y abrieron nuevas áreas del laberinto a las hormigas para ver si tenían la capacidad de resolver dinámicamente el problema.
Como hemos dicho, al cabo de una hora las hormigas encontraban el camino más corto, que en un caso bordeaba el borde del laberinto. Al bloquearlo las hormigas respondieron mediante una modificación del camino original, solución que no era óptima. Sin embargo, al cabo de otra hora ya habían encontrado la ruta óptima a través del centro del laberinto.
Los investigadores descubrieron que si se permitía a las hormigas exploradoras recorrer el laberinto sin comida durante una hora antes del experimento entonces el resto cometía menos errores y eran más rápidas que cuando se enfrentaban al problema por primera vez sin exploración previa. Esto, según sugieren los investigadores, sería debido a que la feromona dejada por las exploradoras era clave para ayudar a la resolución del problema cuando cambiaban las condiciones.
Contrariamente a lo que se creía, el uso de las feromonas no estanca a las hormigas en un camino en particular sin poder adaptase a las nuevas circunstancia. Según los investigadores tener al menos dos feromonas separadas les da a las hormigas mayor flexibilidad y les ayuda a encontrar buenas soluciones incluso si las condiciones ambientales cambian.
Añaden que descubrir cómo las hormigas son capaces de resolver dinámicamente problemas puede proporcionar inspiración para nuevos algoritmos de optimización, y que éstos pueden permitir la creación de software que resuelva mejor problemas de optimización en la industria.

Copyleft: atribuir con enlace a http://neofronteras.com/?p=3330

Fuentes y referencias:
Nota de prensa.
Artículo original.