Colonias de Hormigas

Introdución

Ant System (AS) 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 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 siguientes deciden con una buena probabilidad seguir el camino con mayor cantidad de feromonas.

Figura 1 Comportamiento de las Hormigas Reales.

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 hacia abajo; en (c) 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.

Esta innovadora técnica basada en agentes muy simples llamados hormigas, nació con la tesis doctoral de Marco Dorigo (1992) quien en 1996 publicó tres variantes del algoritmo para la resolución del problema del cajero viajante (Traveling Salesman Problem ­ TSP).