Asdssf

SISTEMA DISTRIBUIDO DE HORMIGAS PARA EL PROBLEMA DEL CAJERO VIAJANTE1
Marta Almirón
malmiron@cnc.una.py

Enrique Chaparro Viveros eviveros@cnc.una.py
Centro Nacional de Computación Universidad Nacional de Asunción Casilla de Correos 1439 Campus Universitario de San Lorenzo - Paraguay Tel./Fax: (595)(21) 585 619 y 585 550 http://www.cnc.una.py

Benjamín Barán
bbaran@cnc.una.py

ResumenLa metáfora natural de una colonia de hormigas ha sido utilizada para definir un Sistema de Hormigas (Ant System), una familia de algoritmos distribuidos para optimización combinatoria. Simples agentes computacionales, llamados hormigas, intercambian información para encontrar buenas soluciones, en este trabajo, para el conocido paradigma del Cajero Viajante (TSP – Traveler Salesman Problem). Almoverse, una hormiga real deposita una substancia denominada feromona, marcando el camino que fue recorrido. Inspirado en esta metáfora, Ant System utiliza una matriz de feromonas para establecer comunicación indirecta entre las diversas hormigas, facilitando la búsqueda de buenas soluciones. El presente trabajo propone ofrecer a las hormigas un conocimiento previo de las características delproblema, escalando la matriz de feromonas a partir de la matriz de distancias para el algoritmo conocido como Ant Quantity y disminuir considerablemente los tiempos de ejecución al paralelizar el algoritmo Ant Cycle, en un ambiente típicamente asíncrono.

Palabras Claves
Sistemas distribuidos y paralelismo, inteligencia artificial, sistemas evolutivos, Ant System, Hormiga, Feromonas, TSP.

1.INTRODUCCIÓN
Ant System, propuesto originalmente por Dorigo et al. [1-2], se basa en el comportamiento colectivo de las hormigas en la búsqueda de alimentos para su subsistencia. Resulta fascinante entender como animales casi ciegos, moviéndose casi 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 unrastro odorífero, depositando una substancia denominada feromona. Las feromonas son un sistema de comunicación química entre animales de la misma especie [3], que transmiten informaciones esenciales para la supervivencia de la especie como ser el estado fisiológico, reproductivo y social, así como la edad, sexo y parentesco del animal emisor. Dichas señales son recibidas por el sistema olfatorio delanimal receptor, quien las interpreta para decidir sobre su comportamiento posterior.

Este trabajo ha sido parcialmente desarrollado con los auspicios de la Dirección de Investigaciones, Postgrado y Relaciones Internacionales (DIPRI) de la Universidad Nacional de Asunción (UNA).

1

En principio, una hormiga aislada se mueve esencialmente al azar, pero las siguientes deciden con una buenaprobabilidad seguir el camino con mayor cantidad de feromonas. Como ejemplo, considere la Figura 1.a donde las hormigas han establecido un camino desde su nido hasta su fuente de alimento, y asumamos que repentinamente una piedra corta el camino (Figura 1.b), la mitad de las hormigas se dirigirán hacia el extremo A y la otra mitad hacia el extremo B. Al ser menor la distancia para rodear el extremoB, mayor cantidad de hormigas pasaran por este camino y por lo tanto mayor cantidad de feromonas será depositada en dicho trayecto (Figura 1.c); en consecuencia, las hormigas influenciadas por el sendero de feromonas elegirán rodear el obstáculo por el extremo B (Figura 1.d), lo que a su vez servirá para depositar más feromonas en dicho trayecto, que por realimentación positiva, será seleccionadacomo el camino más corto.

Figura 1: Comportamiento de las hormigas reales en la búsqueda de alimentos. El presente trabajo propone resolver el problema simétrico del cajero viajante (TSP - Traveler Salesman Problem) utilizando una familia de algoritmos, conocida como Ant System, inspirado en la metáfora natural arriba explicada. Esto es, dadas N ciudades y las distancias entre estas...