Inteligencia Artificial: Colonias de hormigas

5 septiembre, 2016

Este verano he tenido (y tengo) una plaga de hormigas en casa (no es broma). Es curioso el comportamiento comunitario de estos seres, que no dependen de un individuo en concreto, sino que basan su existencia en el funcionamiento coordinado de todo el equipo. Así, «acabar» con unos cuantos individuos no es, ni mucho menos, algo que afecte al día a día del grupo.

Curiosamente, a la vez, he estado programando -en Prolog- (soy de los que piensan que «real men/women program Prolog») una metaheurística basada en el comportamiento de las hormigas para la optimización de problemas combinatorios. Por si alguien quiere curiosear un poco, podéis encontrar, criticar, contribuir, hacer seguimiento, etc. de lo que llevo hasta ahora (ya funciona, parcialmente), que forma parte de un proyecto más ambicioso, aquí. El código se ejecuta sobre un lenguaje de programación lógica con restricciones llamado ECLiPSe y que podéis descargar aquí.

Hace poco os hablé de la existencia de algoritmos bioinspirados, basados en el «conocimiento» observado en ciertos procesos naturales a la hora de resolver problemas concretos. En dicha entrada, uno de los que os comentaba era el basado en colonias de hormigas.

800px-Ant_on_leaf
ACO – Ant Colony Optimization (imagen de Luke Elstad bajo licencia CC BY-SA 3.0)

Pero, ¿qué hacen las hormigas que nos pueda interesar a los informáticos/as? y ¿cómo lo trasladamos a un algoritmo? Pues bien, el interés que podemos tener en dichos seres viene de su manera de construir colaborativamente soluciones a partir de agentes muy simples. Así, la gracia de las hormigas no es que una sola sea capaz de encontrar el camino más corto entre dos puntos. La gracia, de hecho, es que es totalmente incapaz. Pero en cambio, un hormiguero, como equipo, lo consigue mediante un esfuerzo compartido. Todos hemos visto filas de hormigas que van del hormiguero a un trozo de algo comestible. ¿Cómo construyen ese camino si no tienen ni el olfato de un oso o un tiburón, ni la vista de un águila? La respuesta está (no en todas las especies de hormigas) en el uso de feromonas. Éstas son hormonas que las hormigas producen y detectan, y que les permiten saber que otra u otras han pasado por allí. Así pues, las hormigas pueden dejar feromonas en pequeñas cantidades a la vez que se desplazan. Estas hormonas se pueden ir acumulando si múltiples hormigas pasan por un mismo sitio, o bien, evaporarse con el paso del tiempo si es un camino desechado por el grupo. Con esto, las hormigas, a la hora de buscar comida toman la decisión de qué camino seguir en función de dos variables: su corta vista (y/o «intuición») y las feromonas que encuentran por el camino. Por esto, si volvemos al ejemplo de antes, tenemos esas largas filas de hormigas siguiendo un mismo camino. Aunque, si os fijáis bien, siempre hay alguna que se sale del camino y explora alternativas. Esa es otra característica clave a tener en cuenta.

Con todo esto, ¿cuál es el algoritmo que sigue el hormiguero y que acabamos copiando los informáticos/as? Es bastante sencillo: Cada hormiga comienza su búsqueda de manera independiente. En caso de encontrar algo interesante (comida), vuelve por el mismo camino dejando feromonas. A la hora de ir tomando decisiones, como he comentado anteriormente, la hormiga lo hace a partir de su vista y las feromonas que encuentra. Con esto, si una hormiga encuentra comida, dejará el rastro del camino, y el resto será más probable que sigan ese camino. Y si estas, a su vez, encuentran comida (no se ha acabado aún), reforzarán la presencia de feromonas, dejando más. Pero ese no tiene por qué ser el camino más corto. Por esto, habrá algunas hormigas (aleatoriamente, con menos probabilidad que las que seguirán el rastro de feromonas) que probarán otros caminos. Si encuentran uno más corto, volverán dejando feromonas, y algunas otras acabarán reforzando ese camino. En el momento en que los dos caminos entran en competencia, a la larga, la evaporación en el más largo actuará de mayor manera (por una cuestión de tiempo de recorrido) que en el corto, y al final, la gran mayoría de hormigas irán por el más corto.

Concretando aún más en lenguaje algoritmico (con el riesgo de ponerme pesado porque creo que ya se entiende): Partimos de un conjunto de hormigas (pongamos 50) y de un número máximo de iteraciones (2500, por ejemplo). Para cada hormiga, construimos un camino (dado un grafo, partiendo desde el nodo Hormiguero, se trata de escoger iterativamente el siguiente arco desde el nodo actual al próximo, hasta que llegamos a la comida -nodo Destino). Cada una de estas elecciones debe ser teniendo en cuenta la distancia euclidiana (por ejemplo) entre nodos, y las feromonas depositadas anteriormente en cada arco. Esto nos da un reparto de probabilidades entre los nodos vecinos, tiramos el dado y… ya tenemos el siguiente movimiento.

Una vez hemos generado las 50 rutas, las ordenamos y decidimos cuál es la mejor (en este caso, la más corta). A partir de aquí, tenemos que actualizar las feromonas de los arcos del grafo. Primero, evaporamos (restamos) un poco de cada arco, y luego añadimos nuevas feromonas a los arcos que formen la mejor ruta (NOTA: Hay diferentes estrategias para la actualización de feromonas. En este caso, se trataría de una estrategia elitista ya que nada más deja feromonas la mejor de las 50, pero podrían dejar feromonas todas, repartiendo una cantidad fija entre los arcos recorridos. De este modo, a más distancia, menos densidad de feromonas).

Este ciclo se repite tantas veces como decidamos. Si es 2500, por ejemplo, será como enviar 2500 grupos de 50 hormigas a buscar. Con el paso de las iteraciones, veremos que el camino escogido por la mejor de cada grupo tiende a mejorar, hasta un cierto punto, en el que se estabiliza. Si el problema es suficientemente complejo, ese será un mínimo local, ya que el mínimo global no se puede asegurar cuando estamos tratando con instancias grandes de problemas combinatorios.

En fin, si alguien tiene interés en profundizar más sobre el tema, hay muchos libros y artículos al respecto. Os dejo la referencia del que he usado yo. Hay que tener en cuenta que el algoritmo que he comentado es una metaheurística que permite «atacar» gran diversidad de problemas. La clave es saber representar correctamente el problema con los elementos que nos ofrece el algoritmo (i.e. hormigas, feromonas, evaporación, distancias, etc.)

En fin, yo me vuelvo a casa a resolver el problema de las hormigas (no digitales). A ver quién puede más…

Stützle, Thomas; Hoos, Holger H. MAX-MIN Ant System. Future Generation of Computer Systems. 2000

Daniel Riera es Doctor Ingeniero en Informática por la UAB. Actualmente es el director del Grado de Ingeniería Informática de la UOC y hace investigación dentro de los grupos ICSO y GRES-UOC en temas relacionados con el modelado, simulación y optimización de sistemas combinatorios.

(Visited 179 times, 1 visits today)
Autor / Autora
Daniel Riera Terren
Comentarios
Deja un comentario