 |
| Laberinto utilizado con caminos de hormigas. |
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 encontramos 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 se puede 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 afianza o
consolida 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.
.png "English"){kind=small}
