Lo que nos enseñan las hormigas sobre computación y algoritmos

No, no me lo estoy inventando: el comportamiento de las colonias de hormigas ha sido imitado en computación para tratar de resolver problemas que no se pueden tratar con los métodos matemáticos clásicos. Por ejemplo, para tratar de resolver problemas como el TSP del que hablábamos hace unos días. Y como también contamos en esta casa, no es la primera vez que la computación trata de imitar a la naturaleza para resolver problemas: en aquella ocasión fueron los algoritmos genéticos inspirados en el proceso darwinista mediante el cual la naturaleza consigue especies que se adapten a su medio.

¿Qué nos pueden enseñar las hormigas? Pues podemos aprender muchas cosas de su inteligencia como colectivo: son flexibles, ya que se adaptan a perturbaciones internas o externas; son robustas, ya que las tareas se realizan aunque fallen algunos individuos de la colonia; son descentralizadas, ya que no necesitan a ningún líder para que la tarea llegue a buen puerto; y se autoorganizan, ya que aunque los caminos hacia el objetivo no esten predefinidos, los van encontrando.

Y todo ello siguiendo unas reglas simples y con una comunicación, si cabe, más simple todavía. Qué envidia, ¿verdad?

Pero estábamos hablando de matemáticas.

¿Cómo puede un modelo matemático imitar a una colonia de hormiga? Vamos a pensar, por ejemplo, sobre el problema de encontrar un recorrido mínimo en un grafo. Tenemos uno en el que los vértices (puntos) representan ciudades y las aristas (líneas) las carreteras que las unen, sobre las que hemos marcado la longitud. Queremos calcular el camino más corto desde el vértice A al vértice Z, ¿cómo lo hacemos?

Pues, evidentemente, se puede hacer de forma determinista (y de hecho no se usan algoritmos de hormigas para este problema, pero lo usaremos como ejemplo) y se puede hacer también tratando de mimetizar el método que utilizan estos insectos para encontrar el camino más corto entre un alimento y el hormiguero.

Si observamos una fila de hormigas transportando alimento hasta su refugio hemos de saber que ellas siguen el rastro de feromonas (estimergia) que van dejando las anteriores en su camino y que pueden oler. Si ponemos un obstáculo en mitad de su camino se romperá dicho rastro de feromonas.

En ese momento, las hormigas deciden de forma aleatoria qué camino alternativo han de seguir. Algunas elegirán el camino más corto para evitar el obstáculo y otras no (las que solemos ver a veces desconcertadas). La cosa está en que la cantidad de feromonas que las hormigas segregan el tiempo que están fuera del hormiguero es, más o menos, fija. Por lo tanto, la concentración de feromonas segregada por las que eligieron el camino más corto es más alta en dichos caminos, puesto que estuvieron menos tiempo fuera del hormiguero. De esta forma, el rastro que las hormigas 'listas' dejaron es más intenso y animará a las siguientes a elegir también ese camino más corto, óptimo. Estas, las perseguidoras de las 'listas' seguirán, por lo tanto, incrementando ese rastro de feromonas y, como resultado, al cabo de poco tiempo, todas estarán volviendo al hormiguero por el camino más corto.

Todo esto se puede simular fácilmente con un ordenador y diseñar un algortimo ACO (Ant Colony Optimization). No voy a explicar con detalle cómo funciona un ACO, pero la idea es la siguiente.

Si tenemos un grafo y queremos calcular el camino más corto entre dos de sus vértices, 'lanzamos' una hormiga desde el primer vértice. Ésta elegirá una arista para moverse a otro de los vértices del grafo, a uno que esté unido al primero, claro. Para ello, habremos asignado una cantidad inicial de feromonas a cada arista y, con ello, dotaremos a las aristas de una probabilidad directamente proporcional a la cantidad de feromona e inversamente proporcional a la longitud de la arista.

En función de esta probabilidad asignada, la hormiga elige la primera arista de su camino. Cuando llega a un nuevo vértice (representaría una bifurcación ante un posible obstáculo o intersección de caminos) la hormiga decide con una probabilidad alta seguir por la arista que tiene mayor rastro de feromona (efectuamos un sorteo asignando mayor probabilidad a las aristas que tengan más feromona). Cuando dicha hormiga llega al vértice objetivo repartimos una cantidad fija de feromonas entre las aristas que ha recorrido (cuanto más largo sea el recorrido, menos feromona le tocará a cada una de ellas). Después, lanzamos otra hormiga y así sucesivamente.

Al cabo de unas cuantas iteraciones, las hormigas habrán encontrado en camino más corto en el grafo.

Esta es, más o menos, la filosofía intrínseca de un algoritmo ACO. Así que, la próxima vez que nuestras amigas invadan su azucarero, recuerden que, bueno, al menos ellas aportan algo al mundo de la computación y que soportamos diariamente a otros bichos más dañinos. Algunos andan sobre dos piernas...

Por cierto, certificamos que ninguna hormiga ha sufrido daño alguno durante la ejecución de estos algoritmos.