![Page 1: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/1.jpg)
Ant Colony Optimization(Optimización Basada en Colonias
de Hormigas)
Una Metaheurística Bio-inspirada
Nuevas Metaheurísticas basadas en población
![Page 2: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/2.jpg)
El enfoque ACO, marco general.
• El marco general en el cual situar al enfoque ACO es dentro la denominada SWARM INTELLIGENCE o INTELIGENCIA COLECTIVA
• Este marco presupone un sistema de agentes que obedecen a un conjunto de reglas muy simples, pero que actuando cooperativamente, surge un sistema mucho más complejo.
• Ejemplos: Hormigas, termitas, abejas, bandada, etc.
![Page 3: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/3.jpg)
Conceptos Previos
Métodos básicos para explorar el espacio de búsqueda a partir de los cuales se derivan las metaheurísticas:
• Búsqueda Local
• Algoritmos constructivos
![Page 4: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/4.jpg)
Conceptos Previos (Cont.)
Búsqueda Local
• Presupone una estructura bien definida del espacio de búsqueda (uso del concepto de vecindario).
• Comienza desde una solución inicial y repetidamente trata de mejorarla a través de cambios locales
• Cada cambio realizado le permite al método, “moverse” hacia otros puntos del espacio de búsqueda dentro del vecindario
![Page 5: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/5.jpg)
Conceptos Previos (Cont.)
Vecindario de un punto en el espacio
Operador
![Page 6: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/6.jpg)
Conceptos Previos (Cont.)
Algoritmos constructivos
• Las soluciones son construidas iterativamente añadiendo componentes a una solución partiendo desde una solución ‘vacía’.
• Por ejemplo, en el problema del Viajante de Comercio (TSP) la solución es construída añadiendo una ciudad tras otra incrementando la longitud del tour.
![Page 7: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/7.jpg)
Conceptos Previos (Cont.)
Ejemplo de un Algoritmo constructivo
Procedure GreedyConstHeurist; Sp ElegirPrimeraComponente; while (Sp no sea completada) C ComponenteGreedy(Sp);
Sp Sp C; end-while S Sp;
return S;end-procedure
Esta parte es la que determina la “voracidad”
![Page 8: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/8.jpg)
Conceptos Previos (Cont.)
• ¿Qué diferencia hay entre Búsqueda Local y un Algoritmo Constructivo?
• ¿Cómo visualizar el espacio de búsqueda para un Algoritmo Constructivo?
•¿Se pueden definir operadores para explorar dicho espacio?
![Page 9: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/9.jpg)
Espacio de Búsqueda del Problema (Ejemplo, TSP)
Tamaño N=5, 5!=120 Posibles soluciones N=6, 6!=720 N=100, 100! = ? EB
Cada punto en EB es una permutación de las ciudades, p.e. 35142 o 25341
3 4
2
51
![Page 10: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/10.jpg)
3
1 2 54
41 25
5
51
2
21
1
1 5
1
5
5! en Total
3
4
2
1
Espacio de Búsqueda - TSPAlgoritmo de Construcción
¿Cómo elegir la rama a seguir?
![Page 11: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/11.jpg)
Posibilidades de expansión del árbol
• Greedy (como en el ejemplo del algoritmo previamente mostrado)
• Aleatorio (¿tiene sentido?)
• Greedy-random (e.g., GRASP)
• Ant Colony Optimization (formulación clásica original del enfoque)
![Page 12: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/12.jpg)
Ant Colony Optimization (ACO)
•El enfoque ACO engloba a todos aquellos algoritmos cuyo diseño está basado en el comportamiento de las colonias de hormigas reales.
![Page 13: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/13.jpg)
Ant Colony Optimization (ACO)
• Las hormigas reales (ciertas especies) dejan un rastro (feromona) que puede ser detectado por el resto de la colonia (comunicación indirecta o stigmergy)
•Un Algoritmo ACO es un proceso distribuido en el que un conjunto de agentes (reactivos) que actúan en forma independiente y cooperan esporádicamente en forma indirecta para llevar a cabo un objetivo común.
![Page 14: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/14.jpg)
ACO (Experimentos de base)
![Page 15: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/15.jpg)
ACO (Exp. Camino más corto)Alimento
Nido
![Page 16: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/16.jpg)
Consideraciones para su aplicación
• El enfoque ACO es particularmente adecuado para ser aplicado a problemas que acepten una representación vía grafo (necesario para imitar la búsqueda de un camino)
• Representación del rastro de feromona y su asociación a las conexiones entre las componentes del problema.
• Posibilidad de añadir conocimiento del problema (heurística local) para guiar junto con el rastro la construcción de las soluciones.
![Page 17: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/17.jpg)
Consideraciones para su aplicación
• Como ejemplo clásico usaremos el problema TSP
• Representación del rastro de feromona puede ser realizado a través de una matriz de números reales () de nn.
• Heurística local: 1/dij, es decir, un valor inversamente
proporcional a la distancia entre las ciudades i y j.
![Page 18: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/18.jpg)
ACO aplicado a TSP
3 4
2
51
![Page 19: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/19.jpg)
3
1 2 54
41 25
5
51
2
21
1
1 5
1
5
3
4
2
1
Espacio de Búsqueda - TSPAlgoritmo ACO
¿Cómo se elige en un ACO la rama a seguir?
![Page 20: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/20.jpg)
El primer algoritmo ACO (Ant System o AS)
Inicializar();for c=1 to Nro_ciclos{ for k=1 to Nro_ants ant-k construye solución k; Guardar la mejor solución; Actualizar Rastro (i.e., ij);
Reubicar hormigas para el próximo ciclo;}Imprimir la mejor solución encontrada;
![Page 21: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/21.jpg)
El primer algoritmo ACO (Ant System o AS)
Inicializar();for c=1 to Nro_ciclos{ for k=1 to Nro_ants ant-k construye solución k; Guardar la mejor solución; Actualizar Rastro (i.e., ij);
Reubicar hormigas para el próximo ciclo;}Imprimir la mejor solución encontrada;
La construcción se realiza paso a paso en forma probabilística considerando
ij y ij
![Page 22: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/22.jpg)
AS - Construcción de una solución para TSP
/* Sk: Solución o permutación construida por la hormiga k */Sk = Ciudad_Inicial; (escogida de acuerdo a algún criterio)mientras no se haya completado el tour{ Seleccionar próx. Ciudad (j) con probabilidad (i es la última ciudad incluida)
Sk = Sk j}
casootroen
sNoVisitadajkP
sNoVisitadahihih
ijij
ij
0
.
.
)(
![Page 23: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/23.jpg)
El primer algoritmo ACO (Ant System o AS)
Inicializar();for c=1 to Nro_ciclos{ for k=1 to Nro_ants ant-k construye solución k; Guardar la mejor solución; Actualizar Rastro (i.e., ij);
Reubicar hormigas para el próximo ciclo;}Imprimir la mejor solución encontrada;
Se puede hacer considerando todas las soluciones encontradas o un subconjunto de ellas
![Page 24: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/24.jpg)
Actualización del Rastro en ASAcumulación de rastro proporcional a la calidad de las soluciones (i.e., NroAnts soluciones):
Actualización Efectiva ( es el factor de persistencia del rastro)
NroAnts
kij
kij t
1
)1(
)1()(.)1( ttt ijijij
Este valor es calculado directamente
proporcional a la calidad de la solución
![Page 25: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/25.jpg)
Importancia de Rastro ()• Como todo método heurístico, un algoritmo ACO tiene
su bloque de construcción a partir del cual se generan nuevas soluciones del espacio de búsqueda.
• El bloque de construcción está representado por la
estructura dado que incide directamente en las componentes a seleccionar.
El nivel de feromona indica la fortaleza de la conexión.
1
1
2
2 3
34
4
5
5
![Page 26: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/26.jpg)
Otros algoritmos ACO (Introducción)
Surgen como respuesta a ciertos problemas observados en AS y básicamente se diferencian en cómo usan y/o modifican el rastro de feromona.
• MinMax-AS (control sobre los valores del rastro)
• AS-rank (ranking de soluciones)
• AS-elistim (solo la mejor solución)
• Ant Colony System (ACS)
• Ant-Q (basado en Q-Learning)
![Page 27: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/27.jpg)
¿Que diferencia fundamental existe entre este enfoque ACO y los AEs o Simmulated Annealing ?
![Page 28: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/28.jpg)
EB desde la perspectiva de un AE y ACO
Solución Completa
3
1 2 54
41 25
5
51
2
21
1
1 5
1
![Page 29: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/29.jpg)
Aplicaciones de ACO
• TSP
• Scheduling
• Vehicle Routing Problem (VRP)
• Data Mining (Ant-Miner & Ant-Tree)
• Problemas de Grafos (Clique, Coloreo, etc.)
• Ruteo Dinámico (ANT-Net)
• Problemas con funciones continuas y restricciones
• Geometría Computacional (Algunas ideas)
![Page 30: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/30.jpg)
Estudios actuales en el campo de las Metaheurísticas
•Cambios en las componentes a los efectos de mejorar su performance.
•Hibridización.
•Estudio y análisis de sus propiedades.
•Aplicaciones a problemas de carácter no estacionario (ambientes dinámicos)
![Page 31: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/31.jpg)
Información de interés
• Dorigo, M. & Th. Stützle - “Ant Colony Optimization”
• http://www.metaheuristics.net
•http://www.iridia.be/~mdorigo
![Page 32: Ant Colony Optimization (Optimización Basada en Colonias de Hormigas) Una Metaheurística Bio-inspirada Nuevas Metaheurísticas basadas en población](https://reader034.vdocumento.com/reader034/viewer/2022051623/5665b4901a28abb57c923b83/html5/thumbnails/32.jpg)
FIN
Parte I