Colonia de hormigas

Colonia de hormigas

Los algoritmos basados en colonias de hormigas resuelven problemas estáticos y proporcionan un alto grado de flexibilidad y robustez en entornos dinámicos. La colonia se adapta a cambios repentinos en el medio ambiente y continúa funcionando cuando ciertos individuos no logran completar su tarea.

La colonia de hormigas describe agentes que tienen un comportamiento colectivo autoorganizado, surgen estructuras a nivel colectivo a partir de interacciones simples basadas en el principio de feromonas dejadas por los agentes.

El principio de una colonia de hormigas es simple. Las hormigas pueden seleccionar la ruta más corta desde el nido hasta una fuente de alimento a través de la deposición y rastreo de feromonas. Estos son depositados por las hormigas en su camino. Las hormigas tienden a seguir el rastro con mayor impacto de feromonas. Las feromonas se disipan con el tiempo (no en todas las versiones del algoritmo). Por lo tanto, concluimos que después de un tiempo, las hormigas elegirán todas las pistas más cortas entre el nido y la comida.

El algoritmo de la colonia de hormigas se basa en un fenómeno autocatalítico, es decir, el fenómeno se refuerza a sí mismo (retroalimentación positiva). La pista más corta se ve favorecida gracias a su concentración de feromonas. Entonces, más hormigas tomarán este camino y, por lo tanto, fortalecerán su concentración de feromonas, etc. Luego hablamos de estigmergia. La optimización se realiza gracias a la propiedad emergente, aquí el camino con mayor concentración de feromonas. Se nota que los agentes actúan sin contacto físico ni centralización de datos.

Optimización de colonias de hormigas

El algoritmo fue introducido por M. Dorigo en 1991, inicialmente destinado al TSP (viajante de comercio). Representamos el problema a resolver en forma de encontrar el camino más corto en una gráfica.

La estructura del algoritmo de la colonia de hormigas es la siguiente:

  1. Inicializar
  2. Repita hasta un máximo de ciclos
    1. Cada hormiga construye una solución
    2. Mejorar las soluciones a través de la búsqueda local
    3. Premie las mejores soluciones agregando feromonas
    4. Evaporar trazas de feromonas

Los algoritmos de tipo ACO tienen pruebas de convergencia que no se mostrarán en este curso.

Inicialización (caso de TSP)

los metro Las hormigas se distribuyen aleatoriamente en el no ciudades. Para cada hormiga, se le asigna una lista tabú, que contiene su lista de inicio. Las pistas de feromonas se inicializan a un valor vs positivo no cero. Cada borde del gráfico ij tiene su pista de feromonas anotada Tij= c.

Construcción de la solución y búsqueda local

Hormigas k colocado en una ciudad I En este momento t elige su ciudad de destino j en función de :

  • La visibilidad de esta ciudad noij (distancia en el caso de TSP)
  • La cantidad de feromona Tij(t) depositado en la pista.

La elección es aleatoria según una probabilidad donde dos parámetros Para y B controlar la importancia relativa de la visibilidad y la cantidad de feromonas. sí b = 0, es más probable que se seleccionen las ciudades más cercanas, es un algoritmo codicioso. sí a = 0, solo actúa la amplificación de las feromonas, hay convergencia prematura y resultados no óptimos La nueva ciudad se suma a la lista tabú de las hormigas.

Cada hormiga procede de esta manera hasta que pasan por todos los pueblos.

Fin de un ciclo

Para cada hormigas k, calculamos la duración de su turno LOSk(t) luego vaciamos su lista tabú (excepto la inicialización).

Luego se actualizan las pistas de feromonas:

Tij(t + 1) = p * Tij(t) + feromonasij(t) con pag entre 0 y 1 y feromonasij(t) la cantidad de feromona depositada por las hormigas en la cresta ij al ciclo t.

La evaporación de la pista se calcula directamente en la fórmula anterior. En efecto, p representa la persistencia de la huella, es decir, la memoria de la cantidad de feromonas que se conservan para el ciclo siguiente. sí p = 1, no hay evaporación, por lo tanto, no hay limitación del fenómeno autocatalítico. sí p = 0, el sistema no tiene memoria, solo se tiene en cuenta el último ciclo realizado.

Para cada hormigas k pasando por la cresta ij, aumenta la cantidad de feromona depositada según el siguiente cálculo:

feromonasij(t) + = Q / Lk(t) o Q representa una cuota de feromonas asignadas a cada hormiga (a menudo Q = 100). La idea es suplir todo el trayecto recorrido por las hormigas de forma homogénea con feromonas.

La vuelta más pequeña se guarda en la memoria si es mejor que la última para memorizar. Las hormigas comienzan un ciclo nuevamente desde su ciudad inicial (mantenida en su lista de tabú).

Variantes de algoritmo: MMAS

El sistema de hormigas Max-min (MMAS) es una variante eficiente del algoritmo. Solo las mejores hormigas trazan senderos donde la deposición de feromonas está limitada por un límite superior y un límite inferior. Así evitamos que una pista esté demasiado reforzada y dejamos la posibilidad de explorar cualquier pista. En particular, esto evita una convergencia prematura.

colonia de hormigas

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