Ant Colony Optimization
(Parte II)
Familia de algoritmos derivados del
enfoque ACO
Nuevas Metaheurísticas basadas en población
(2004)
Familia de algoritmos ACO
• MinMax-AS (control sobre los valores del rastro)
• AS-rank (ranking se soluciones)
• AS-elistim (solo la mejor solución)
• Ant Colony System (ACS)
• Ant-Q (basado en Q-Learning)
Algoritmos ACO
• MixMaxAS: Ant System con valores Mínimos y
Máximos para los valores del rastro de feromona
¿Qué puede ocurrir si no se controlan los valores
del rastro de feromona?
¿Qué relación se puede establecer entre un
incremento (decremento) indiscriminado del rastro
y el comportamiento del algoritmo?
Valores extremos o nulos del rastro
2
1
5
3
4
MinMaxAS
Inicializar();
for c=1 to Nro_ciclos
{
Se controlan los
for k=1 to Nro_ants
ant-k construye solución k; valores Máximo y
Mínimos
Guardar la mejor solución;
Actualizar Rastro (i.e., ij);
Reubicar hormigas para el próximo ciclo;
}
Imprimir la mejor solución encontrada;
Algoritmos ACO
• AS-rank: Ant System que usa un ranking de las
mejores soluciones para realizar la actualización
del rastro.
¿Qué relación se puede establecer entre esta manera
de actualizar el rastro y el comportamiento del
algoritmo?
AS-rank
Inicializar();
for c=1 to Nro_ciclos
{
Se actualiza el rastro
for k=1 to Nro_ants
ant-k construye solución k; siguiendo el ranking
de las mejores
Guardar la mejor solución;
soluciones
Realizar un ranking;
Actualizar Rastro (i.e., ij);
Reubicar hormigas para el próximo ciclo;
}
Imprimir la mejor solución encontrada;
Actualización del Rastro en
AS-rank
w 1
  ij ( t  1) 

( w  r )   ij  w   ij
r
b
r 1
w: peso
r: índice del ranking
b: best-so-far
 ij ( t  1)   . ij ( t )    ij ( t  1)
Algoritmos ACO
• AS-elitism: Ant System que usa
complementariamente la mejor solución
encontrada hasta el momento para dar un
resfuerzo adicional.
¿Qué relación se puede establecer entre esta manera
de actualizar el rastro y el comportamiento del
algoritmo?
Actualización del Rastro en
AS-elitism
NroAnts
  ij ( t  1) 

  ij  e  ij
k
b
k 1
w: peso
r: índice del ranking
b: best-so-far
 ij ( t  1)   . ij ( t )    ij ( t  1)
Algoritmos ACO
Ant Colony System: Un algoritmo ACO que es una
extensión de un AS e introduce:
1. un esquema local y global de actualización del
rastro y,
2. una manera alternativa de selección de la
próxima componente
Ant Colony System (ACS)
1. Actualización del rastro
•LOCAL:
Cada vez que una hormiga avanza en el grado deja un rastro
muy pequeño sin considerar
 la calidad de la solución.
ij
 ij  (1   ). ij   0
• GLOBAL: (idem AS, es decir, después que termina un ciclo)
 ij ( t  1)  (1   ). ij ( t )     ( t  1)
b
ij
Ant Colony System (ACS)
2. Selección de la próxima componente de la solución:
 arg max

j  
Usar
Pij


{ ij . j }
 ij
en
qo  q
otro
caso
La usada en un AS
con  =1
Ant Colony System (ACS)


 ij . ij



Pij ( k )  
  ih . ih
 h NoVisitada s
0


j  NoVisitada s
en
otro
caso
Es decir que hay una combinación de greedy y proporcional.
NOTA: La parte greedy es sobre los valores combinados de
rastro y heurística
ACS
Inicializar();
for c=1 to Nro_ciclos
{
for k=1 to Nro_ants
ant-k construye solución (Actualización LOCAL)
Guardar la mejor solución;
Realizar un ranking;
Actualización GLOBAL Rastro;
Reubicar hormigas para el próximo ciclo;
}
Imprimir la mejor solución encontrada;
Posibilidades de Paralelización
• División en subcolonias
(distribuido)
• Muliprocesamiento (Memoria
Compartida)
• Otros....
FIN
Parte II
Descargar

ACO-Teoria-2160 KB