presentG8-ASasasasasasasasassasasasa.ppt

Colonia de Hormigas Algotirmos

1. Grupo 8 – Berger y Casarini
Ant Colony Optimization
A new Meta-Heuristic
Marco Dorigo
Gianni Di Caro

2. Agenda
Introducción
Autores
Inspiración
Modelado
Problemas
Rastro de Feromona (memoria colectiva)
Hormigas
Pseudocódigo
ACO
Actividad de las Hormigas
Aplicaciones
TSP
Tráfico en Redes
QAP
Conclusión

3. Introducción
Université Libre de Bruxelles
Marco Dorigo
Gianni Di Caro
En 1991, primer sistema AS, para resolver TSP.
Lo último anterior a este trabajo es una aplicación al ruteo
en redes de Di Caro y Dorigo, 1998.
Para muchos de los problemas tratados, Ant Systems
proporciona resultados comparables con los mejores
obtenidos con otras heurísticas.
Autores y sus trabajos

4. Introducción
ACO se inspira
en observaciones de las hormigas.
La colonia tiene un grado de organización alto,
comparado con la simplicidad del individuo.
Coordinación indirecta por medio de los rastros de
feromona.
Exploración paralela del ambiente.
Idea

5. Se puede resumir los algoritmos ACO, como un
conjunto de agentes concurrentes y
asincrónicos (colonia de hormigas) que se
mueven a través de un espacio de estados
correspondientes a soluciones parciales del
problema a resolver.
Se mueven aplicando políticas de decisión
locales estocástcias basadas en dos parámetros:
un valor heurístico que depende del modelado
del problema.
un valor que incorpora el conocimiento global
Introducción
Formalización

6. Modelado del Problema
C = {c
1
,c
2
,.....,c
n
} conjunto finito de componentes.
L = {l
c1c2
/(c
1
,c
2
)C}, conexiones o transiciones.
C es un subconjunto del producto cartesiano CxC.
|L|  N
c
2
J
ci,cj
 J(l
cicj
,t), función que asocia costos a las aristas.
  (C,L,t) conjunto finito de restricciones
asignadas a elementos de C y L.
s = (c
i
,c
j
,…,c
k
,…) estado del problema.
S = estados posibles.
S = estados factibles f(S,).

7. N
s
es la estructura de vecindad: si s
1
y s
2
son dos
estados, s
2
es vecino de s
1
si ambos están en S y s
2

puede obtenerse a partir de s
1
en un único paso
lógico. Si c
1
es el último componente de s
1
, debe existir
un componente c
2
 C, tal que l
c1c2
 L y s
2
= (s
1
,c
2
)
 es una solución, si es un elemento de S y satisface
todos los requerimientos del problema.
J

(L,t) define el costo asociado a cada solución. Es una
función de los costos J
cicj
de todas las conexiones
pertenecientes a la solución.
Modelado del Problema

8. Feromona
Codificación de la información recolectada: por las
hormigas, durante el proceso de búsqueda, almacenada
como rastros de feromona asociados a los arcos.
Lectura: Ante cada decisión una hormiga utiliza:
•información propia
•del nodo en que se encuentra
•de los arcos adyacentes (feromona).
Escritura: Para cada arco transitado por una hormiga,
ésta deja el rastro de feromona.
Feromona como memoria de largo plazo

9. Feromona
Propicia la interacción indirecta entre la colonia:
A cada hormiga se le hace difícil llegar a la solución
óptima. Encontrar buenas soluciones depende de la
interacción entre la colonia por medio de la
información que ellas leen y escriben en los arcos
por lo que pasan, mediante los rastros de feromona.
Percepción de la colonia: Las hormigas modifican
la forma en que el problema es representado y
percibido por las demás hormigas, pero no se
adaptan ellas mismas.
Memoria a largo plazo.
Feromona como base de la interacción

10. Modelado de las Hormigas
Propiedades
Objetivo: buscar en forma constructiva, una solución
factible de costo mínimo.
Movimientos: desde un estado s
r
=(s
r-1
,i), puede
moverse a cualquier nodo j de su vecindad factible,
definida como N
i
k
= { j/jN
i
 (s
r
,j)  S }
Memoria M
k
: usada para almacenar el camino
recorrido. Se usa para la construcción y evaluación de
las soluciones y para volver atrás.
Condiciones de comienzo y fin: A cada hormiga
k se le puede asignar un estado de comienzo y una o
más condiciones de fin (e
k
).

11. Modelado de las Hormigas
Ciclo de Vida
Comienzo: Cada una desde un estado inicial
(puede o no ser el mismo para todas)
Desplazamiento: A estados en la vecindad factible, de
acuerdo a una regla de decisión probabilística.
Final: El proceso de construcción termina cuando la
hormiga cumple al menos una de las condiciones de fin.
Muerte: Luego de cumplidas estas actividades, codifica
su aporte a la colonia y muere, liberando todos los
recursos.

12. La regla de decisión probabilística de las hormigas es
una función de:
Un valor almacenado en tabla de ruteo, obtenido a
partir del valor de feromona del arco considerado y
un valor heurístico. 
i=[a
ij], a
ij=f (
ij, 
ij)
La memoria privada de las hormigas, que almacena
su pasado.
Restricciones del problema.
Modelado de las Hormigas
Regla de decisión probabilística de movimiento

13. Actualización de la Feromona
Actualización on-line paso a paso:
Cada hormiga al moverse de un nodo i, a un nodo j,
actualiza el valor de la feromona 
ij
del arco (i,j).
Actualización on-line retardada:
Una vez construida una solución, rehacen el camino
en sentido inverso, actualizando el valor de la
feromona de cada arco recorrido.
Modelado de las Hormigas

14. Intensificación vs.
Diversificación.
Intensificación: A través de las reglas de
actualización de la feromona que van reforzando
las buenas soluciones.
Diversificación: implementado a través de:
mecanismo probabilístico de construcción de
las soluciones.
Evaporación de la feromona.
Migración: Comienza con alta D y baja I. A
medida que evoluciona, la búsqueda se
intensifica hacia los caminos con mayores índices
de feromona.

15. Pseudocódigo
procedure ACO meta-heuristic()
while (termination_criterion_not_satisfied)
schedule_activities
ants_generation_and_activity();
pheromone_evaporation();
daemon_actions(); [opcional]
end schedule_activities
end while
end procedure
procedure ACO meta-heuristic()
while (termination_criterion_not_satisfied)
schedule_activities
ants_generation_and_activity();
pheromone_evaporation();
daemon_actions(); [opcional]
end schedule_activities
end while
end procedure
procedure ACO meta-heuristic()
while (termination_criterion_not_satisfied)
schedule_activities
ants_generation_and_activity();
pheromone_evaporation();
daemon_actions(); [opcional]
end schedule_activities
end while
end procedure
procedure ACO meta-heuristic()
while (termination_criterion_not_satisfied)
schedule_activities
ants_generation_and_activity();
pheromone_evaporation();
daemon_actions(); [opcional]
end schedule_activities
end while
end procedure
procedure ACO meta-heuristic()
while (termination_criterion_not_satisfied)
schedule_activities
ants_generation_and_activity();
pheromone_evaporation();
daemon_actions(); [opcional]
end schedule_activities
end while
end procedure

16. Ants Generation And Activity
Procedure Ants_Generation_And_Activity()
While (AvailableResources)
schedule_creation_of_new_ant();
new_active_ant();
End While
End Procedure
Procedure Ants_Generation_And_Activity()
While (AvailableResources)
schedule_creation_of_new_ant();
new_active_ant();
End While
End Procedure

17. new active ant()
while (current state  target state)
A = read local ant-routing table();
P = compute transition probabilities(A; M; );
next state = apply ant decision policy(P; );
move to next state(next state);
if (online step-by-step pheromone update)
deposit pheromone on the visited
arc();
update ant-routing table();
end if
M = update internal state();
end while
if (online delayed pheromone update)
foreach visited_arc   do
deposit pheromone on the visited arc();
update ant-routing table();
end foreach
end if
procedure new active ant()
initialize ant();
M = update ant memory();
Desplazarse
Dejar Aprendizaje a la Colonia
die();
end procedure

18. Aplicaciones
TSP (problema del vendedor viajero)
Ruteo en redes de comunicación
QAP
VRP y VRPTW
Ordenamiento Secuencial
Job-shop scheduling
Mayor Super-Secuencia Común
Asignamiento Generalizado

19. Aplicaciones – ACO-TSP
Descripción y Objetivo: Dada una ciudad inicial
y n ciudades a visitar, encontrar un circuito
Hamiltoniano de costo mínimo, sujeto a ciertas
restricciones.
Motivación: Fue el primer problema en ser
atacado por medio de ACO porque es:
Relativamente fácil de adaptar la metáfora de la colonia
de hormigas al problema
Un problema de difícil solución (NP-Hard)
Uno de los problemas de optimización combinatoria más
estudiados
Conocido y fácil de exponer y explicar
Nociones Generales

20. Aplicaciones – ACO-TSP
Modelado
C = Conjunto de ciudades
L = Conjunto de conexiones entre ciudades
J
cicj
= Distancias entre c
i
y c
j,
c
i
,c
j
 C
La ciudad inicial para cada hormiga es elegida
aleatoreamente
Actualización de la feromona: Solo retardada
La evaporación de feromona se hace luego de
que todas las hormigas terminan su tour

21. Aplicaciones – ACO-TSP
Se posicionan en paralelo m hormigas en m
ciudades, elegidas aleatoreamente.
Se inicializa la memoria M
k
con esa ciudad.
Comienza un ciclo hasta que cada hormiga
complete un tour:
Buscar la vecindad factible del nodo actual.

Leer las entradas a
ij
de la tabla de ruteo.

Calcular las probabilidades de transición p
ij
k
(t).
Aplicar la regla de decisión para elegir una ciudad a la que
desplazarse.
Realizar el desplazamiento. Actualizar la memoria local.
Una vez terminado el tour, actualiza la feromona
del recorrido y termina su ejecución.
Comportamiento de las hormigas
Se posicionan en paralelo m hormigas en m
ciudades, elegidas aleatoreamente.
Se inicializa la memoria M
k
con esa ciudad.
Comienza un ciclo hasta que cada hormiga
complete un tour:
Buscar la vecindad factible del nodo actual

Leer las entradas a
ij
de la tabla de ruteo

Calcular las probabilidades de transición p
ij
k
(t)
Aplicar la regla de decisión para elegir una ciudad a la que
desplazarse.
Realizar el desplazamiento. Actualizar la memoria local.
Una vez terminado el tour, actualiza la
feromona del recorrido y termina su ejecución.

22. Aplicaciones – ACO-TSP
Toma de decisiones e interacción entre la colonia...
leer los a
ij de A
i
probabilidades de transición
actualizar rastros de feromona
evaporación de feromona
 = 1
 = 5
 = 0.5

23. Aplicación posterior a TSP.
Utilizado para encontrar el optimo en la
transferencia de DATOS en redes.
Distribuido y no sincronizado.
Rutear es difícil porque los costos son
dinámicos.

Motivación: encontrar R
i = [r
ijd ] para cada
nodo.
Aplicaciones – AntNet
Notas Generales

24. Aplicaciones – AntNet
Se modela cada nodo de la red
como un nodo de un grafo G(C,L).
C = Nodos de la red.
L = “links” entre nodos, su valores
estan relacionados con las
propiedades físicas del canal y el
trafico por el mismo.
Modelado

25. Cada Hormiga busca un “camino” ente 2
nodos con costo mínimo.
Hormiga(origen,destino)
Cada Hormiga parte de un nodo distinto,
desplazándose de uno a otro, hacia su
destino.
En cada paso debe optar ente los arcos
factibles, esta decisión esta basada en la
M
k
y en la tabla de ruteo de cada nodo.
Aplicaciones – AntNet
Modelado

26. Feromonas
En esta aplicación la feromona de
un arco esta en relación con la
calidad del camino desde el nodo
actual al destino.
El valor 
ijd  [0,1] con i actual, j
próximo, d destino.
A diferencia de TSP se genera
una estructura bidimensional
para el ruteo del nodo y las
feromonas
Aplicaciones – AntNet

27. Valores heurísticos
Para cada arco se coloca valor inicial, n
ij 
[0,1], independiente del destino.
q en este problema representa el largo de
la cola de bits para enviar por el link.
El efecto es desestimar los caminos mas
congestionados.
Aplicaciones – AntNet

28. Ruteo del nodo
Cada nodo tiene su tabla de ruteo y
depende de n
ij y 
ijd
Con un factor w  [0,1] se da mas peso a
uno u otro.

Aplicaciones – AntNet

29. Decisión de la Hormiga
La Hormiga decide entre los adyacentes,
no visitados (que no están en M
k
).
Los adyacentes factibles tienen p
ijd(t)
p
ijd(t) = a
ijd(t) ,valor de tabla de ruteo
(no visitados).
p
ijd(t) = 0, adyacentes ya visitados.
p
ijd(t)
= 1/|N
i
|, si no hay caminos posibles
(fueron ya todos visitados).
Aplicaciones – AntNet

30. Actualizaciones
Las Hormigas se mueven como se
moverían los datos en la red.
Igual que los bits reales tienen retraso
para su viaje hacia el destino.
Una vez que la Hormiga llega a destino,
regresa hacia atrás, depositando
feromonas.
Aplicaciones – AntNet

31. Actualización

T
sd
es una medida del tiempo que insume la ruta de i a d vía j.
Mide lo “buena que es una ruta”.
El incremento de feromona es proporcional al inverso
de T
sd.
Se coloca la feromona al final, porque hay que tener el valor
de T
sd
Se lleva cabo la evaporación, por un factor de normalización,
No hay “Daemon” para modificar las feromonas depositadas
en los arcos.
Aplicaciones – AntNet

32. Tabla de Ruteo resultado
Durante la ejecución de AntNet, las
Hormigas van modificando las tablas
de ruteo de cada nodo para optimizar
la transferencia de datos por la red.
Estas tablas son usadas al rutear los
datos a ser transmitidos por la red.
Aplicaciones – AntNet

33. Conclusiones
AntSystems se aplica bien para problemas
Optimización Combinatoria, donde la
dimensíón del espacio completo de
soluciones es exponencial con respecto a la
dimensión de la representación del
problema. Problemas NP-Hard
Noción de secuencia o distancia.
Problemas que cambian en t

34. Conclusiones
Fácil de paralelizar, propio del mecanismo
Esta metaheurística se ha comprobado, según
Gambardella, como altamente competitiva en:
MACS-VRPTW: Vehicle Routing Problem with Time
Windows
HAS-QAP: Quadratic Assignment Problem
HAS-SOP: Sequential Ordering Problem
Flexible Job Shop Problem

35. Preguntas
¿?