Hormigas y computacion

Colonia de Hormigas en un Ambiente Paralelo Asíncrono
Benjamín Barán Universidad Nacional de Asunción Centro Nacional de Computación San Lorenzo, Paraguay bbaran@cnc.una.py y Marta Almirón Universidad Nacional de Asunción Centro Nacional de Computación San Lorenzo, Paraguay malmiron@cnc.una.py Abstract
Ant Colony System (ACS) studies ant artificial systems that take inspiration from thecollective behavior of real ants to solve combinatorial optimization problems. ACS is based on the structured behavior of ant colony, where very simple individuals communicate information to each other using a chemical substance denominated pheromone, establishing the shortest paths from their nest to a feeding sources and back. The method consists in a computational simulation of the indirectcommunication that uses agents called ants to establish the shortest path keeping the information learned in a matrix of pheromone. Considering the ants are basically independent agents working in parallel without synchronization, this paper proposes a parallel asynchronous implementation in a network of personal computers, presenting experimental results that prove the usefulness of parallelism and theviability of the proposed asynchronous implementation. Keywords: Parallel and Distributed Systems, Artificial Intelligence, Combinatorial Optimization.

Resumen
Ant Colony System (ACS) estudia los sistemas artificiales de hormigas inspirados en la conducta colectiva de hormigas reales, utilizados para resolver problemas de optimización combinatoria. ACS se basa en el comportamiento estructurado deuna colonia de hormigas donde individuos muy simples de una colonia se comunican entre sí por medio de una sustancia química denominada feromona, estableciendo el camino más adecuado entre su nido y su fuente de alimentos. El método consiste en simular computacionalmente la comunicación indirecta que utilizan las hormigas para establecer el camino más corto, guardando la información aprendida enuna matriz de feromonas. Considerando que las hormigas son agentes básicamente autónomos que trabajan en paralelo, este trabajo presenta una implementación paralela asíncrona del algoritmo ACS en una red de computadoras personales, presentando resultados experimentales que prueban la ventaja de usar paralelismo y la viabilidad de la implementación propuesta. Palabras claves: Sistemas Distribuidosy Paralelismo, Inteligencia Artificial, Optimización Combinatoria.

1

Introducción

La observación de la naturaleza ha sido una de las principales fuentes de inspiración para la propuesta de nuevos paradigmas computacionales. Así nacieron diversas técnicas de Inteligencia Artificial como: los Algoritmos Genéticos (Genetic Algorithms), Templado Simulado (Simulated Annealing), RedesNeuronales (Neural Networks), y entre estas técnicas, el sistema basado en Colonias de Hormigas (Ant Colony System) [1]. Resulta realmente interesante analizar como las hormigas buscan su alimento y logran establecer el camino más corto para luego regresar a su nido. Para esto, al moverse una hormiga, deposita una sustancia química denominada feromona como una señal odorífera para que las demás puedanseguirla. Las feromonas son un sistema indirecto de comunicación química entre animales de una misma especie, que transmiten información acerca del estado fisiológico, reproductivo y social, así como la edad, el sexo y el parentesco del animal emisor, las cuales son recibidas en el sistema olfativo del animal receptor, quien interpreta esas señales, jugando un papel importante en la organización y lasupervivencia de muchas especies [2]. Al iniciar la búsqueda de alimento, una hormiga aislada se mueve a ciegas, es decir, sin ninguna señal que pueda guiarla, pero las que le siguen deciden con 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 la figura (a) las hormigas llegan a un...