Colonias distribuidas

Colonias Distribuidas de Hormigas en un Entorno Paralelo Asíncrono
D.Sc. Benjamín Barán1 bbaran@cnc.una.py Lic. Marta Almirón malmiron@cnc.una.py

Centro Nacional de Computación Universidad Nacional de Asunción Casilla de Correos 1439 Campus Universitario de San Lorenzo Paraguay

Resumen
El comportamiento colectivo de una colonia de hormigas ha servido para inspirar una novedosa técnicadenominada Sistema de Hormigas (Ant System), una familia de algoritmos distribuidos para optimización combinatoria. El método consiste en simular la comunicación indirecta que utilizan las hormigas para establecer el camino más corto desde su nido hasta la fuente de alimento y regresar. Basado en el asincronismo implícito de una colonia de hormigas, el presente trabajo propone la paralelización de unsistema de hormigas en un ambiente típicamente asíncrono, como el de una red de computadoras, permitiendo que cada procesador trabaje en forma independiente, a su propio ritmo y sin depender de datos ajenos, compartiendo sus mejores resultados con los demás procesadores de la red y aprovechando buenos resultados de otros procesadores para mejorar su capacidad de búsqueda. Con esto, se lograaprovechar los recursos computacionales generalmente disponibles, mejorando considerablemente los resultados experimentales.

Palabras Claves:
Sistemas distribuidos y paralelismo, inteligencia artificial, agente, optimización combinatoria.

1. Introducción
Ant System (AS) se basa en el comportamiento colectivo de las hormigas en la búsqueda de alimentos para su subsistencia. Resulta fascinanteentender como animales casi ciegos, moviéndose aproximadamente al azar, pueden encontrar el camino más corto desde su nido hasta la fuente de alimentos y regresar. Para esto, cuando una hormiga se mueve, deja una señal odorífera, depositando una substancia denominada feromona, para que las demás puedan seguirla. En principio, una hormiga aislada se mueve esencialmente al azar, pero las siguientesdeciden con una buena probabilidad seguir el camino con mayor cantidad de feromonas. Considere la Figura 1 en donde se observa como las hormigas establecen el camino más corto. En el figura (a) las hormigas llegan al punto en que tienen que decidir por uno de los caminos que se les presenta; en (b) realizan la elección de manera aleatoria, algunas hormigas eligen el camino hacia arriba y otras haciaabajo; en (c)
1

El presente trabajo fue parcialmente financiado por la Dirección de Investigaciones, Postgrado y Relaciones Internacionales – DIPRI de la Universidad Nacional de Asunción.

como las hormigas se mueven aproximadamente a una velocidad constante, las que eligieron el camino más corto alcanzarán el otro extremo más rápido que las otras que tomaron el camino más largo,depositando mayor cantidad de feromona por unidad de longitud; en (d) la cantidad de feromona depositada en el trayecto más corto hace que la mayoría de las hormigas elijan este camino, por realimentación positiva.

(a)

(b)

(c)

(d)

Figura 1: Comportamiento de las hormigas reales. Esta innovadora técnica basada en agentes muy simples llamados hormigas, nació con la tesis doctoral de MarcoDorigo (1992) [Dor98] quien en 1996 publicó tres variantes del algoritmo para la resolución del problema del cajero viajante (Traveling Salesman Problem - TSP [DG97]) que se diferencian simplemente en el momento y la manera de actualizar una matriz de feromonas [DMC96]: S S S Ant-density: con actualización constante de las feromonas por donde pasa una hormiga. Ant-quantity: con actualización deferomonas inversamente proporcional a la distancia entre 2 ciudades recorridas. Ant-cycle: con actualización de feromonas inversamente proporcional al trayecto completo, al terminar un recorrido. Este último presentó mejores resultados y las siguientes investigaciones se centraron en él.

Recientemente, Dorigo y Gambardella trabajaron en varias versiones extendidas del paradigma AS. Entre estas,...