Sistema de hormigas

Sistema de hormigas

El algoritmo del sistema de hormigas está inspirado en el comportamiento de búsqueda de alimento de las hormigas, en particular la comunicación de feromonas entre las hormigas con respecto a un buen camino entre la colonia y una fuente de alimento en un medio ambiente. Este mecanismo se llama estigmergia.

Las hormigas inicialmente deambulan al azar en su entorno. Una vez que se localiza la comida, una hormiga comenzará a depositar feromonas en el medio ambiente. Se realizan muchos viajes entre la comida y la colonia y si se sigue la misma ruta que lleva a la comida se depositan feromonas adicionales. Las feromonas se descomponen en el medio ambiente, por lo que es menos probable que se sigan las viejas formas. Otras hormigas pueden descubrir el mismo camino hacia la comida y a su vez pueden seguirlo y también depositar feromonas. Un proceso de retroalimentación positiva dirige a más y más hormigas a caminos productivos que, a su vez, se refinan con el uso.

El objetivo de la estrategia del sistema de hormigas es explotar la información histórica y heurística para construir soluciones candidatas y plegar la información obtenida de la construcción de soluciones en la historia. Las soluciones son discretas y construidas probabilísticamente para cada paso. La probabilidad de selección de un componente está determinada por la contribución heurístico del componente al costo total de la solución y la calidad de las soluciones a partir de las cuales se sabe históricamente que se incluyó el componente. El historial se actualiza en proporción a la calidad de las soluciones candidatas y se reduce uniformemente, lo que garantiza que se conserve la información más reciente y útil.

El siguiente algoritmo proporciona una pseudocódigo del algoritmo del sistema hormiga principal para minimizar una función de costo. El proceso de actualización de feromonas se describe mediante una sola ecuación que combina las contribuciones de todas las soluciones candidatas con un coeficiente de decaimiento para determinar el nuevo valor de feromonas, de la siguiente manera:

sistema de hormigas

donde τ_i,j representa la feromona del componente (un borde en un grafico) (i; j), ρ es el factor de descomposición, m es el número de hormigas y la suma de los deltas es la suma de 1/S_cost (maximización del costo de la solución) para soluciones que incluyen el componente i, j . El algoritmo muestra esta ecuación como un equivalente de un proceso de descomposición de dos pasos seguido de una actualización por simplicidad.

La construcción probabilística paso a paso de la solución utiliza tanto el historial (feromonas) como la información heurística específica del problema para construir gradualmente una solución pieza por pieza. Cada componente solo puede seleccionarse si aún no se ha elegido (para la mayoría de los problemas combinatorios), y para los componentes que pueden seleccionarse (dado el componente i actual), su probabilidad de selección se define de la siguiente manera:

sistema de hormigas

donde η_i, j es la contribución maximizadora al puntaje general de selección de componentes (como 1 / distancia para el problema del viajante de comercio), α es el coeficiente heurístico, τ_i, j es el valor de feromonas para el componente, β es el coeficiente de la historia, y es el conjunto de componentes utilizables.

sistema de hormigas

El algoritmo del sistema hormiga fue diseñado para su uso con problemas combinatorios como el TSP, el problema de la mochila, problemas de asignación cuadrática, colorante gráficos y muchos más.

El coeficiente de historial (α) controla la cantidad de historial de contribución en la probabilidad de selección de componentes y generalmente se establece en 1.0. El coeficiente heurístico (β) controla la cantidad de información heurística específica del problema de contribución jugado en la probabilidad de selección de un componente y típicamente está entre 2 y 5, como 2.5. El factor de desintegración (ρ) controla la velocidad a la que se pierde la información histórica y, por lo general, se establece en 0,5. El número total de hormigas (m) generalmente se define por el número de componentes del problema, como el número de ciudades en el TSP.