aco teoria 1

Ant Colony Optimization(Optimización Basada en Colonias

de Hormigas)

Una Metaheurística Bio-inspirada

Nuevas Metaheurísticas basadas en población

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.

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

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

Conceptos Previos (Cont.)

Vecindario de un punto en el espacio

Operador

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.

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”

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?

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

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?

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)

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.

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.

ACO (Experimentos de base)

ACO (Exp. Camino más corto)Alimento

Nido

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.

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.

ACO aplicado a TSP

3 4

2

51

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?

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;

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

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

.

.

)(

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

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

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

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)

¿Que diferencia fundamental existe entre este enfoque ACO y los AEs o Simmulated Annealing ?

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

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)

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)

Información de interés

• Dorigo, M. & Th. Stützle - “Ant Colony Optimization”

• http://www.metaheuristics.net

•http://www.iridia.be/~mdorigo

FIN

Parte I