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), Redes Neuronales (Neural Networks), y entre estas técnicas, el sistema basado en Colonias de Hormigas (Ant Colony System)
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 puedan seguirla.
Las feromonas son un sistema indirecto de comunicación química entre animales de una misma especie, 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 la supervivencia de muchas especies
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 siguiente figura en donde se observa como las hormigas establecen el camino más corto. En la figura (a) las hormigas llegan a un punto donde tienen que decidir por uno de los caminos que se les presenta, lo que resuelven de manera aleatoria. 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.
Ant System
Inspirados en el comportamiento de las hormigas, arriba descripto, Dorigo proponen tres variantes del algoritmo Ant System (AS), que básicamente difieren en el momento y la modalidad en que actualizan la matriz de feromonas que sirve para guiar el movimiento de los agentes computacionales llamados hormigas; estos algoritmos son:
· Ant-density: con actualización constante de las feromonas por donde pasa una hormiga.
· Ant-quantity: con actualización de feromonas 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.
Para el presente trabajo, se considera un conjunto de MAXC ciudades y se define b (t) i como el número de hormigas en la ciudad i en el tiempo t, por consiguiente, el número total de hormigas MAXH estará dado por:
MAXC
MAXH = Σ b i (t)
i = 1
Para satisfacer la restricción de que una hormiga visite todas las ciudades una sola vez, se asocia a cada hormiga k una estructura de datos llamada lista tabú, tabuk, que guarda las ciudades ya visitadas por dicha hormiga. Una vez que todas las ciudades hayan sido recorridas, el trayecto o tour (ciclo) es completado, la lista tabú se vacía y nuevamente la hormiga está libre para iniciar un nuevo tour. Se define como tabuk(s) al elemento s-esimo de la lista tabú de la hormiga k.
El punto de partida para la solución del problema en cuestión, es la matriz de distancias D = {di j -distancia entre la ciudad i y la ciudad j}, a partir de la cual se calcula la visibilidad Vij= 1/ dij. Por su parte, se denota como T = {Tij} a la matriz de feromonas a ser utilizada para consolidar la información que va siendo recogida por las hormigas; en otras palabras, la cantidad de feromona que se va almacenando entre cada par de ciudades i, j.
Durante la ejecución del algoritmo Ant System, cada hormiga elige en forma probabilística la próxima ciudad a visitar, realizando un cálculo de probabilidad que es función de la distancia y la cantidad de feromonas depositada en el arco que une a las ciudades origen-destino, esto es:
donde α y β son constantes que expresan la importancia relativa del sendero de feromonas y la distancia entre las ciudades respectivamente. Así, un alto valor de α significa que el sendero de feromonas es muy importante y que las hormigas tienden a elegir caminos por los cuales otras hormigas ya pasaron. Si por el contrario, el valor de β es muy alto, una hormiga tiende a elegir la ciudad más cercana. Se resalta aquí que cada hormiga debe realizar un tour legal o sea, no puede viajar a una ciudad ya visitada con anterioridad hasta que complete su tour.
En el instante t, las hormigas se mueven de una ciudad a la siguiente (movimiento llamado: iteración), en donde se encontrarán en el instante t+1. Lógicamente, al cabo de (MAXC – 1) iteraciones, las hormigas han visitado la última ciudad y están en condiciones de regresar a su ciudad origen, posiblemente para actualizar la matriz de feromonas con la información recogida en el tour completo.
La matriz Tij(t) que especifica la intensidad de las feromonas del arco (i, j) en t, se actualiza según la fórmula:
Tij (t + 1) = × Tij (t) + ATij (t, t + 1)
donde ρ es el coeficiente de persistencia de las feromonas, de forma tal que (1-ρ) representa la evaporación de la substancia entre t y t+1, mientras que la cantidad de feromona depositada en un arco (i, j), está dada por:
MAXH
ATij(t,t+1)=ΣATkij(t,t+1)
k=1
con ATkij (t, t+1) representando la cantidad de feromonas por unidad de longitud, depositada en el arco (i,j) por la hormiga k-esima entre t y t+1. Cabe destacar aquí que la principal diferencia entre las diversas variantes del algoritmo Ant System, está dada justamente en la forma de calcular ATkij (t, t+1), conforme será explicado en las próximas subsecciones.
El proceso se repite iterativamente hasta que se cumpla algún criterio de parada. En este trabajo, el proceso termina si el contador de tour alcanza un número máximo de ciclos NCMAX (definido por el usuario) o todas las hormigas realizan el mismo tour. En este último caso, es evidente que las hormigas han dejado de buscar nuevas soluciones, lo que constituye un criterio de convergencia del algoritmo (similar a la uniformización de la población de un algoritmo genético).
Ant Quantity
En esta variante del algoritmo (ver Pseudocódigo 1), la hormiga k que viaja desde la ciudad i a la ciudad j, deposita en el
trayecto una cantidad de feromonas inversamente proporcional a la distancia dij, esto es:
si la hormiga k – esima camina por el arco ( , ) entre y + 1
de otra manera
donde Q1 es una constante.
Pseudocódigo 1: Ant-quantity secuencial.
t=0; /*t es contador de tiempo*/
nc=0; /*nc es el contador de ciclos*/
s=1; /*índice de la lista tabú*/
Para cada arco (i,j) inicializar T (t) c ij = ; /*c es una constante positiva pequeña*/
Para cada arco (i,j) AT (t) ij = 0 ;
Colocar las MAXH hormigas en las MAXC ciudades;
Colocar la ciudad origen de la hormiga k-esima en tabuk(s)
DO WHILE (nc<=NCMAX y que todas las hormigas no realicen el mismo tour)
FOR t=1 hasta MAXC-1 /*se repite hasta que la lista tabú este llena*/
s=s+1
FOR i=1 hasta i<=MAXC
FOR k=1 hasta k<=b(t)
Elegir la ciudad j a mover, con probabilidad pij(t) dado por la ecuación (1);
Mover la hormiga k-esima a la ciudad;
Insertar la ciudad j en tabuk(s);
Calcular ATij (t, t +1) = AT ij (t, t+ 1) + Q 1 / d ij;
END FOR
END FOR
Para cada arco (i,j) calcular T (t t ) ij , + 1 según la ecuación (2);
END FOR
Guardar el camino más corto;
nc=nc+1;
IF (nc<=NCMAX)
Vaciar todas las listas tabú;
Para cada arco (i,j) AT ij(t + 1) = 0 ;
s=1;
Colocar la ciudad origen de la hormiga k-esima en tabuk(s);
END IF
END WHILE
Imprimir el mejor camino;
Faltan las referencias y una conexión concreta con esta materia. Buena explicación en general. Te pongo seis puntos.
ResponderEliminar