Técnicas bioinspiradas II : Colonias de hormigas

Esta semana aprovecho para comentaros otra de las técnicas inspiradas en un proceso natural, pero que es de utilidad en el mundo de la computación. En este caso se imita la manera que tienen de proceder las hormigas a la hora de encontrar el camino más corto entre la comida y su colmena. En todo esta entrada se empleará el término agente como sinónimo de hormiga, ya que éstas son unidades que actuan de manera independiente en el proceso de búsqueda de comida.

Hay dos ideas principales en simulación del funcionamiento de una colonia de hormigas en un ordenador. La primera es definir el comportamiento de una hormiga. Sus acciones se limitan a tres opciones: moverse, reconocer si hay comida donde está ella y dejar un rastro de feromonas por el camino que sigue. Inicialmente una hormiga deambula, es decir, se mueve sin oficio ni beneficio, esperando chocarse con algún trozo de comida en su paseo. Siempre que se desplaza, el agente deja un rastro, pero cuando encuentra comida, retorna a la colmena, pero incrementando la cantidad depositada en su viaje de vuelta. Estos marcadores químicos influencian el movimiento de otras hormigas, que dejaran de seguir rutas semialeatorias para tomar caminos similares a los de los rastros de feromonas. Esto conllevará a la larga que las rutas con más feromonas influencien tanto al resto de agentes hasta que todos sigan este camino. Para evitar que las rutas malas perduren, también se eliminan los caminos que no son visitados con mucha frecuencia, es decir, se emula el proceso de evaporación, el cual limita la influencia de aquellos trayectos que no llegaron a buen puerto.

De esta forma, al comienzo no hay apenas influencia química, por lo que las hormigas cubren una gran distancia (cuantas más hayan, más superficie cubrirán), pero una vez se encuentra la comida, el resto de hormigas, veran sus movimientos influenciados por la concentración de feromonas. Lo interesante es que no hay ni líderes que organicen la búsqueda ni comunicación directa entre los distintos agentes que conforman el sistema, sino que todo depende de las feromonas. El hecho de que no haya comunicación simplifica enormemente el proceso y lo hace mucho más eficiente. Se puede decir que estos productos químicos constituyen la memoria de la colonia, ya que indican que caminos tienen mayor probabilidad de llevar a las fuentes de comida.

El proceso de búsqueda puede verse con mayor claridad en el siguiente vídeo.

En el centro se encuentra la colmena de hormigas y en esquinas opuestas, las fuentes de comida. Para ponérselo más complicado a nuestros amados insectos, se han colocado obstáculos que fuerzan un proceso de búsqueda más complejo. Al comienzo sólo hay una hormiga, la cual deja rastros de feromonas tras de sí. El problema es que se ve inmersa en un bucle: toma una dirección aleatoria, pero al tiempo acaba siguiendo su propio rastro, permaneciendo siempre cerca de su lugar original. Podemos concluir que una hormiga por sí sola no es capaz de hacer absolutamente nada. Sin embargo, más adelante, la cosa cambia, otros agentes toman direcciones distintas y acaban llegando a la comida, reforzando en su trayecto de vuelta el rastro de feromonas. Esto conlleva a que nuevas hormigas tomen rutas parecidas abandonando su deambular.

Si hay varias rutas a un mismo foco de comida las más largas se acabarán evaporando, porque las hormigas reemplazan las feromonas a un mayor ritmo en aquellos caminos más cortos, ya que son capaces de recorrerlos más rápido. También es posible darse cuenta en este vídeo de como los rastros van evaporándose mientras que otros van ganando un mayor peso. Hacia el final del video se ve como el camino de la parte superior (que es completamente estúpido) pierde peso en favor de el de la derecha y el inferior.

Las aplicaciones de este tipo de técnicas son directas: es posible encontrar caminos en cualquier lugar de un mapa. No importa si se añaden obstáculos a posteriori, las hormigas siempre encuentran su camino.

Pepe "Puertas de acero" Pérez