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 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 probabilísticamente construidas para cada paso. La probabilidad de seleccionar un componente está determinada por la contribución heurística del componente al costo total de la solución y la calidad de las soluciones de las que históricamente se sabe que se ha incluido 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 un pseudocódigo del algoritmo principal del sistema de hormigas para minimizar una función de costo. El proceso de actualización de feromonas se describe mediante una única ecuación que combina las contribuciones de todas las soluciones candidatas con un coeficiente de desintegración para determinar el nuevo valor de feromonas, de la siguiente manera:

sistema de hormigas

donde τ_i, j representa la feromona para el componente (un borde en un gráfico) (i; j), ρ es el factor de desintegración, m es el número de hormigas y la suma de los deltas es la suma de 1 / S_cost (maximización 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 disminución de dos pasos seguido de una actualización para simplificar.

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 Ant System fue diseñado para su uso con problemas combinatorios como TSP, problema de mochila, problemas de asignación cuadrática, problemas de coloración de 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.

Compartir, repartir
es_ESES
A los bloggers de %d les gusta esto: