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.
El principio de la colonia de hormigas es simple. Las hormigas pueden seleccionar el camino más corto para ir del nido a una fuente de alimento depositando y siguiendo rastros de feromonas. Estos son depositados por las hormigas en su camino. Una hormiga tiende a seguir el rastro con el 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, todas las hormigas elegirán el camino más corto entre el nido y la comida.
Optimización de colonias de hormigas
El algoritmo fue introducido por el Sr. Dorigo en 1991, inicialmente destinado al TSP (viajero de comercio). Representamos el problema a resolver en la forma de la búsqueda de un camino más corto en un grafico.
La estructura del algoritmo de la colonia de hormigas es la siguiente:
- Inicializar
- Repita hasta un máximo de ciclos
- Cada hormiga construye una solución
- Mejorar las soluciones por busqueda local
- Premie las mejores soluciones agregando feromonas
- 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, un lista tabú asignado a él, contiene su lista de salida. Los rastros 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, esta es una algoritmo glotón. Ya sea 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.
ES 
FR 
EN