Colonia de hormigas
Los algoritmos basados en colonias de hormigas resuelven problemas estáticos y ofrecen un alto grado de flexibilidad y solidez en entornos dinámicos. La colonia se adapta a los cambios repentinos del entorno y continúa funcionando cuando algunos individuos no logran realizar 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
- Repetir hasta el 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 a la visibilidad y la cantidad de feromonas. Ya sea 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 ha recorrido 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. Efectivamente p representa la persistencia de la huella, es decir, el recuerdo de la cantidad de feromonas que guardamos para el siguiente ciclo. Ya sea p = 1, no hay evaporación y por lo tanto no hay limitación del fenómeno autocatalítico. Ya sea 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 abastecer todo el camino cubierto por una hormiga de forma homogénea con feromonas.
La vuelta más corta se guarda en la memoria si es mejor que la última memorizada. Las hormigas comienzan un ciclo nuevamente desde su ciudad inicial (mantenida en su lista de tabúes).
Variantes del algoritmo: MMAS
El sistema de hormigas Max-min (MMAS) es una variante eficiente del algoritmo. Solo las mejores hormigas trazan huellas donde el depósito de feromonas está limitado por un límite superior y un límite inferior. Así evitamos que una pista se refuerce demasiado y dejamos la posibilidad de explorar cualquier pista. En particular, esto evita la convergencia prematura.
