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 the collective 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 …ver más…

En consecuencia, la mitad de las hormigas de dirigirán hacia un extremo y la otra mitad hacia el otro extremo, como ilustra la figura (b). 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 que tomaron el camino más largo, quedando depositado mayor cantidad de feromona por unidad de longitud, como ilustra la figura (c). La mayor densidad de feromonas depositadas en el trayecto más corto hace que éste sea más deseable para las siguientes hormigas y por lo tanto la mayoría elige transitar por él. Considerando que la evaporación de la sustancia química hace que los caminos menos transitados sean cada vez menos deseables y la realimentación positiva en el camino con más feromonas, resulta claro que al cabo de un tiempo casi todas las hormigas transiten por el camino más corto.

(a)

(b)

(c)

(d) Figura 1: Comportamiento de las hormigas reales.

Basándose en el comportamiento de las hormigas arriba descrito, Dorigo et al. [1] propusieron una técnica conocida como Ant system para el conocido paradigma del cajero viajante (TSP – Traveler

2

Salesman Problem) [3] que presentaba tres variantes que se diferencian simplemente en el momento y la manera de actualizar una matriz que representa las feromonas de los sistemas biológicos. Trabajos posteriores de Dorigo y Gambardella extendieron los alcances del paradigma AS. Por ejemplo, Ant-Q es un híbrido