Algoritmo de la colonia de hormigas

En nuestro mundo natural, las hormigas (inicialmente) vagan de manera aleatoria, al azar, y una vez encontrada comida regresan a su colonia dejando un rastro de feromonas. Si otras hormigas encuentran dicho rastro, es probable que estas no sigan caminando aleatoriamente, puede que estas sigan el rastro de feromonas, regresando y reforzándolo si estas encuentran comida finalmente.[3]

Sin embargo, al paso del tiempo el rastro de feromonas comienza a evaporarse, reduciéndose así su fuerza de atracción. Cuanto más tiempo le tome a una hormiga viajar por el camino y regresar de vuelta otra vez, más tiempo tienen las feromonas para evaporarse. Un camino corto, en comparación, es marchado más frecuentemente, y por lo tanto la densidad de feromonas se hace más grande en caminos cortos que en los largos. La evaporación de feromonas también tiene la ventaja de evitar convergencias a óptimos locales. Si no hubiese evaporación en absoluto, los caminos elegidos por la primera hormiga tenderían a ser excesivamente atractivos para las siguientes hormigas. En este caso, el espacio de búsqueda de soluciones sería limitado.

Por tanto, cuando una hormiga encuentra un buen camino entre la colonia y la fuente de comida, hay más posibilidades de que otras hormigas sigan este camino y con una retroalimentación positiva se conduce finalmente a todas las hormigas a un solo camino. La idea del algoritmo colonia de hormigas es imitar este comportamiento con "hormigas simuladas" caminando a través de un grafo que representa el problema en cuestión.

La idea original proviene de la observación de la explotación de los recursos alimentarios entre hormigas, en el que las habilidades cognitivas de las hormigas son individualmente limitadas y en conjunto son capaces de buscar el menor camino existente entre la fuente de comida y su nido o colonia.

1. La primera hormiga encuentra la fuente de alimentos (F) a través de cualquier camino (a), entonces retorna a la colonia (N), dejando tras sí un rastro de feromonas;
2. Las hormigas indiscriminadamente siguen cuatro caminos posibles, pero el fortalecimiento de la pista hace más atractivo la ruta más corta;
3. Las hormigas toman la ruta más corta y largas porciones de otras rutas empiezan a perder su rastro de feromonas.

En una serie de experimentos en una colonia de hormigas donde existe la elección de dos rutas de distancias diferentes que llevan hasta la fuente de comida, los biólogos observaron que las hormigas tienden a usar la ruta más corta.[4] [5] El siguiente modelo explica este comportamiento:

1. Una hormiga (llamada “blitz”) vaga de manera aleatoria alrededor de la colonia.
2. Si esta encuentra una fuente de comida, retorna a la colonia de manera más o menos directa, dejando tras sí un rastro de feromonas.
3. Estas feromonas son atractivas, las hormigas más cercanas se verán atraídas por ellas y seguirán su pista de manera más o menos directa.
4. Regresando a la colonia estas hormigas habrán fortalecido dicha ruta.
5. Si existen dos rutas para que lleguen a la misma fuente de alimentos entonces, en una misma cantidad de tiempo dado, la ruta más corta será recorrida por más hormigas que la ruta más larga.
6. La ruta más corta habrá aumentado en cantidad de feromonas y por tanto empezará a ser más atractiva.
7. La ruta más larga irá desapareciendo debido a que las feromonas son volátiles.
8. Finalmente, todas las hormigas habrán determinado y escogido el camino más corto.

Las hormigas utilizan el entorno como medio de comunicación. Intercambian información de manera indirecta depositando feromonas en su trayectoria, detallando el estado de su trabajo. La información intercambiada tiene un ambiente local, solamente una hormiga ubicada cerca de donde las feromonas fueron depositadas va a tener una noción de estas. Este sistema es llamado "Estigmergia (Stigmergy)" y ocurre en muchas sociedades de animales (este sistema ha sido estudiado en el caso de la construcción de los pilares en los nidos de termitas). El mecanismo para resolver un problema demasiado complejo para ser abordado por hormigas solamente es un buen ejemplo de un sistema auto-organizado. Este sistema es basado en la retroalimentación positiva (el depósito de feromonas atrae otras hormigas y estas fortalecerán dicha retroalimentación) y la retroalimentación negativa (disipación de la ruta por evaporación). Teóricamente, si la cantidad de feromonas fue la misma en todas las rutas durante todo el tiempo, ninguna ruta fue elegida. Sin embargo, debido a la retroalimentación, una ligera variación en una arista amplificará y entonces se permitirá elegir una ruta. El algoritmo se moverá de un estado inestable en el que ninguna arista es más fuerte que otra, a un estado estable donde una ruta está compuesta por las aristas más fuertes.

La filosofía básica del algoritmo implica el movimiento de una colonia de hormigas a través de los diferentes estados del problema influenciado por dos políticas de decisión a nivel local, rutas y atracción. De esta manera, cada hormiga incrementalmente construye una solución del problema. Cuando una hormiga completa una solución, o durante la fase de construcción, las hormigas evalúan la solución y modifican el valor de la ruta sobre las componentes utilizadas en la solución. Esta información de feromonas dirigirá la búsqueda de futuras hormigas. Además el algoritmo incluye dos mecanismos más, evaporación del rastro y acciones daemon. La evaporación del rastro reduce todos los valores de los rastros evitando la posibilidad de caer en óptimos locales. Las acciones daemon son usadas para desviar el proceso de búsqueda de una perspectiva local.

El sistema de hormigas es el primer algoritmo OCH propuesto. Se corresponde con el funcionamiento descrito en la anterior sección

La mejor solución global deposita feromonas en cada iteración junto con todas las otras hormigas.

Agregada la cantidad máxima y mínima de feromonas [t_max,t_min] Solamente la mejor iteración deposita feromonas. Todas las aristas son inicializadas con t_max y re-inicializadas con t_max cuando se acerca a un estancamiento. [6]

Se ha presentado anteriormente.[7]

Todas las soluciones se clasifican de acuerdo su longitud. La cantidad de feromonas depositadas es ponderada para cada solución, de tal manera que las soluciones con los caminos más cortos depositan más feromonas que las soluciones que con los caminos más largos.

El mecanismo de depósito de feromonas de COAC es permitir a las hormigas la búsqueda de soluciones en conjunto y efectiva. Usando un método de diseño ortogonal, las hormigas en un dominio factible pueden explorar las regiones elegidas de una manera rápida y eficiente, con mayor capacidad de búsqueda global y precisión. [8]

Este método introduce inteligencia difusa dentro de las hormigas para acelerar las habilidades de búsqueda. [9]

Una hormiga es un simple agente computacional en el algoritmo de optimización colonia de hormigas. Se construye iterativamente una solución para el problema en cuestión. Las soluciones intermedias se denominan estados solución. En cada iteración del algoritmo, cada hormiga se mueve de un estado ${\displaystyle x}$ a un estado ${\displaystyle y}$, correspondiendo a una solución intermedia más completa. Por tanto, cada hormiga ${\displaystyle k}$ computa un conjunto ${\displaystyle A_{k}(x)}$ de expansiones factibles de su estado actual en cada iteración y se mueve a una de estas de manera probabilística. Para una hormiga ${\displaystyle k}$, la probabilidad ${\displaystyle p_{xy}^{k}}$ de moverse de un estado ${\displaystyle x}$ a un estado ${\displaystyle y}$ depende de la combinación de dos valores , de el atractivo ${\displaystyle \eta _{xy}}$ del movimiento, computado por alguna heurística que indica a priori la conveniencia de dicho movimiento y el nivel de rastro ${\displaystyle \tau _{xy}}$ del movimiento, indicando que tan competente ha sido en el pasado este particular movimiento.

El nivel de rastro representa a posteriori una indicación de la conveniencia de ese movimiento. Los rastros son actualizados por lo general cuando todas las hormigas han completado su solución, aumentando o disminuyendo los niveles de los rastros de los movimientos correspondientes que fueron partes de "buenas" o "malas" soluciones respectivamente.

En general, la ${\displaystyle k}$th hormiga se mueve del estado ${\displaystyle x}$ al estado ${\displaystyle y}$ con probabilidad

${\displaystyle p_{xy}^{k}={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum (\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}}}$

donde

${\displaystyle \tau _{xy}}$ es la cantidad de feromonas depositadas en la transición del estado ${\displaystyle x}$ a ${\displaystyle y}$, 0 ≤ ${\displaystyle \alpha }$ es un parámetro para controlar la influencia de ${\displaystyle \tau _{xy}}$, ${\displaystyle \eta _{xy}}$ es la conveniencia del estado de transición ${\displaystyle xy}$ (un conocimiento a priori , típicamente ${\displaystyle 1/d_{xy}}$, donde ${\displaystyle d}$ es la distancia) y ${\displaystyle \beta }$ ≥ 1 es un parámetro para controlar la influencia de ${\displaystyle \eta _{xy}}$.

Cuando todas las hormigas han completado un solución, los rastros son actualizados por ${\displaystyle \tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k}\Delta \tau _{xy}^{k}}$

donde

${\displaystyle \tau _{xy}}$ es la cantidad de feromonas depositadas para un estado de transición${\displaystyle xy}$, ${\displaystyle \rho }$ es el coeficiente de evaporación de feromonas y ${\displaystyle \Delta \tau _{xy}^{k}}$ es la cantidad de feromonas depositadas por la ${\displaystyle k}$th hormiga, típicamente dado para el Problema del Viajante (con movimientos correspondientes a los arcos del grafo) por ${\displaystyle \Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{if ant }}k{\mbox{ uses curve }}xy{\mbox{ in its tour}}\\0&{\mbox{otherwise}}\end{cases}}}$

donde ${\displaystyle L_{k}}$ es el costo de la ruta de la ${\displaystyle k}$th hormiga (en la mayoría de los casos es la longitud) y ${\displaystyle Q}$ es una constante.