Tema 9: Optimización
por colonia de hormigas
ALGORITMOS DE BÚSQUEDA II
Introducción
Características principales
• La optimización por colonia de hormigas (Ant Colony Optimization,
ACO) data de 1992.
• Dorigo, M. (1992). Optimization, learning and natural algorithms. PhD thesis,
Politecnico di Milano, Italy.
• Se basa en el comportamiento de búsqueda de
alimento de las colonias de hormigas.
• Las hormigas son capaces de encontrar las rutas
más cortas hacia su objetivo (el alimento) gracias
a los caminos de feromonas:
• Cuando las hormigas recorren un camino, depositan feromonas.
• A mayor número de hormigas por un camino, mayor cantidad de
feromonas.
• La cantidad de feromonas determina la probabilidad de seguir el
camino, aunque también se pueden explorar otros caminos.
• Las feromonas se evaporan, permitiendo variar los caminos
cuando la fuente de alimento se agota.
• Cada hormiga es un organismo simple e
independiente.
Algoritmos de Búsqueda II – J.M. Colmenar 2
Introducción
Características principales
Fuente: Dorigo, M., Maniezzo,V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE
transactions on systems, man, and cybernetics, part b (cybernetics), 26(1), 29-41.
([Link]
Algoritmos de Búsqueda II – J.M. Colmenar 3
Introducción
Características principales
• Metaheurística poblacional.
• El recorrido de cada hormiga construye una solución al problema.
• La decisión de qué camino tomar en cada punto viene determinada
por una probabilidad definida en la literatura.
• La inicialización de las hormigas suele ser aleatoria.
• Se colocan aleatoriamente en puntos de decisión (nodos del grafo).
• Puede haber varias hormigas en el mismo nodo.
• Se comienza con una distribución de feromonas constante en
los puntos de decisión (típicamente nodos de un grafo).
• Las hormigas van depositando feromonas en su recorrido.
• La concentración de feromonas se actualiza cuando todas las
hormigas han completado el recorrido.
• Es decir, cuando cada hormiga ha construido una solución.
Algoritmos de Búsqueda II – J.M. Colmenar 4
Algoritmo
Ciclo de la hormiga
• Cada hormiga es un agente independiente con las siguientes
características:
• Elige el siguiente punto de decisión (nodo) con una probabilidad en función de
la distancia al nuevo punto y a la cantidad de feromona presente en la
conexión (arista) desde el punto actual (i) al nuevo punto (j).
• No se permite visitar puntos ya visitados en el recorrido actual.
• No hay ciclos
• Al completar el recorrido, se actualiza la cantidad de feromona en cada una de
las aristas (i,j) recorridas por la hormiga.
Algoritmos de Búsqueda II – J.M. Colmenar 5
Algoritmo
Probabilidad de transición
Para una hormiga k situada en el nodo i y considerando moverse hacia el nodo j, la
#
probabilidad de transición 𝑝!" se define generalmente como:
Donde
• 𝜏𝑖𝑗 es la intensidad, o cantidad de feromona en el camino que conecta el nodo i con el nodo j. Representa la
experiencia acumulada y cuán deseable es ese camino según exploraciones anteriores.
• 𝜂𝑖𝑗 es la visibilidad del movimiento de i a j. Es una heurística típicamente definida como la inversa de la distancia
𝑑𝑖𝑗 , es decir, 𝜂𝑖𝑗 = 1/𝑑𝑖𝑗 . Cuanto menor sea la distancia, más atractiva será la transición.
• 𝛼 ∈ (0,1] es un parámetro que controla la influencia de la feromona en la probabilidad de transición. Si 𝛼 es
grande, las hormigas preferirán rutas con mucha feromona.
• 𝛽 ∈ (0,1] es un parámetro que controla la influencia de la visibilidad (o heurística). Si 𝛽 es grande, las hormigas
preferirán caminos más cortos.
• 𝑁!" es el conjunto de nodos disponibles para ser seleccionados como el siguiente paso desde el nodo i, aún no
visitados por la hormiga k.
Algoritmos de Búsqueda II – J.M. Colmenar 6
Algoritmo
Actualización de feromonas
Una vez que todas las hormigas han construido una solución, la cantidad de feromonas se
actualiza con la siguiente fórmula:
Donde
• 𝜌 ∈ 0,1 es un coeficiente de modo que (1 − 𝜌) representa la evaporación de la feromona, dado que es
menor que 1.
"
• Δ𝜏!# es la cantidad de feromona que la hormiga k deja en la arista (i,j). Este valor normalmente depende de la
calidad de la solución obtenida. Una fórmula típica para este valor es la siguiente:
" 𝑄
Δ𝜏!# =
𝐿"
donde Q es una constante que suele valer 1, y 𝐿" es la longitud del camino recorrido por la hormiga k, que se
corresponde con la calidad de la solución. A menor longitud, mayor cantidad de feromona se añade.
Algoritmos de Búsqueda II – J.M. Colmenar 7
Algoritmo
Pseudo-código ACO
Parámetros de entrada: numHormigas,maxIteraciones,𝝆, 𝜶, 𝜷,Q,d,numNodos
𝜏 = inicializaFeromonas() // Inicialización de feromonas a valores aleatorios pequeños
S* = ∞ // Inicializa mejor solución (minimizando)
for t=1 to t=maxIteraciones { // Bucle principal
for k=1 to k=numHormigas { // Recorrido de las hormigas
𝐻! = nodoAleatorio() // Inicializar cada hormiga en un nodo aleatorio
while |𝐻! | ≠ numNodos { // Itera mientras no haya visitado todos los nodos
𝐻! = añadeNodoSegunProbabilidad(𝐻! , 𝜏, 𝛼, 𝛽)
}
𝐿! = evaluar(𝐻! ) // Evaluación de la hormiga
}
𝜏 = actualizaFeromonas(𝜏, 𝜌, 𝑄, 𝐿) // Actualización de feromonas
S* = actualizaBest(S*, 𝐻) // Actualización de mejor solución
}
return S* // Devuelve la mejor solución
Algoritmos de Búsqueda II – J.M. Colmenar 8
Selección de parámetros
Una configuración muy básica sería la siguiente:
• Número de hormigas: 10
• Número de iteraciones: 100
• 𝜌 = 0,9 , indica una evaporación del 10%
• 𝛼 = 0,5 , 𝛽 =1 , da mayor peso a la visibilidad (caminos cortos) frente a la intensidad
• Q=1
A partir de esos valores, se pueden ir modificando los parámetros:
• Si el conjunto de hormigas se estanca pronto, subir el número de hormigas.
• Si la evolución muestra tendencia a mejorar en las últimas iteraciones, subir número de
iteraciones.
• Se pueden variar los coeficientes para explorar diferentes comportamientos:
• Subir 𝛼 incrementa el peso de la intensidad, de manera que se beneficia al recorrido más común
entre las hormigas.
• Subir 𝛽 incrementa el peso de la heurística (visibilidad).
• Aumentar la evaporación (bajando 𝜌) ayuda a incrementar la exploración frente a la explotación
(diversificación frente a intensificación).
Algoritmos de Búsqueda II – J.M. Colmenar 9
Variantes
• Diferentes métodos de actualización de feromonas:
• Elitista: la hormiga que ha encontrado la mejor solución tiene más peso en la
actualización.
• Ranking: varias hormigas actualizan las feromonas, pero se pondera la
actualización en función de la calidad obtenida.
• ACO distribuido: varias colonias de hormigas trabajan en paralelo y comparten
información a través de hormigas “emigrantes”.
• Implementación binaria, continua, multiobjetivo, …
Algoritmos de Búsqueda II – J.M. Colmenar 10
Tema 9: Optimización
por colonia de hormigas
ALGORITMOS DE BÚSQUEDA II
