Cap´ıtulo 11 Optimizaci´ on basada en Colonia de Hormigas 11.1

Introducci´ on

Optimizaci´on de colonia de hormigas (ant colony optimization o ACO) est´a inspirado en el rastro y seguimiento de feromonas realizado por las hormigas como medio de comunicaci´on. La optimizaci´on de colonias de hormigas (ACO) es un m´etodo basado en una poblaci´on para resolver problemas de optimizaci´on combinatoria inspirado en el comportamiento de las hormigas (Dorigo & Socha 2006). Los algoritmos de ACO se consideran como parte de inteligencia de enjambres (swarm intelligence), que es el campo de investigaci´on que estudia algoritmos inspirados por la observaci´on del comportamiento de enjambres. Estos algoritmos utilizan individuos que cooperan a trav´es de auto-organizaci´on (sin ning´ un control central que act´ ue sobre los miembros del enjambre).

239

11.2

Hormigas

Se ha observado que en muchas especies que las hormigas que caminan hacia o desde un dep´osito de comida en el suelo dejan una sustancia llamada feromona (pheromone). Esta sustancia tiene una influencia en otras hormigas al momento de elegir su ruta, es decir; las hormigas tienden a elegir caminos con altos contenidos de feromona. De esta manera las hormigas siguen un camino de feromona que las lleva a encontrar buenas fuentes de alimentos que fueron previamente identificados por otras hormigas. Las hormigas s´olo detectan la feromona cuando est´an en contacto directo con ella, es decir; es un contacto local. En un experimento hecho por (Goss et al. 1989) hab´ıa 2 puentes, uno significantemente m´as largo que el otro. Al inicio del experimento las hormigas eleg´ıan uno de los 2 puentes (sin ninguna influencia) pero las que eleg´ıan el puente m´as corto regresaban m´as r´apido y es as´ı como ese camino obten´ıa m´as feromona que el otro. A este fen´omeno se le llama autocat´alisis y es como explotan la retroalimentaci´on positiva para encontrar la ruta m´as corta entre una fuente de alimento y su nido. Este es el modelo de comunicaci´on de las hormigas, tambi´en conocido como modelo de comunicaci´on por medio del ambiente o “stigmergic” en ingl´es.

11.3

Algoritmos

A partir de los resultados obtenidos con el experimento de (Goss et al. 1989) se desarroll´o un modelo para explicar el comportamiento observado en el experimento del puente binario. Asumiendo que despu´es de t unidades de tiempo del inicio del experimento, y que m1 hormigas usaron el primer puente y que m2 hormigas el segundo, la probabilidad p1 de que la (m + 1) hormiga elija el primer puente esta dada por:

p1(m+1)

(m1 + k)h = (m1 + k)h + (m2 + k)h

P2(m+1) = 1 − P1(m+1) 240

donde k y h son par´ametros del modelo para ajustarlo a los datos experimentales. Con simulaci´on de Monte Carlo se encontr´o que para valores de k ≈ 20 y h ≈ 2 el modelo corresponde a los datos reales. El modelo anterior se utiliz´o como inspiraci´on para crear algoritmos con hormigas artificiales que simulan el concepto de feromona modificando variablesferomona asociadas a estados del problema que visitan al construir una soluci´on al problema de optimizaci´on. Las caracter´ısticas de la comunicacin por medio del ambiente (stigmergic) se llevan a agentes artificiales como: • Asociando variables de estado a diferentes estados del problema • Dando a los agentes solo acceso local a estas variables Otro aspecto del comportamiento de las hormigas que se puede llevar a las hormigas artificiales es el acoplamiento entre el mecanismo auto-catal´ıtico y la evaluaci´on impl´ıcita de soluciones (las rutas m´as cortas, que corresponden a soluciones con menor costo en caso de las hormigas artificiales, se encuentran m´as r´apido que las largas y por eso reciben su refuerzo de feromona m´as r´apido. La comunicaci´on por medio del ambiente (stigmergy), la evaluaci´on de soluci´on impl´ıcita y el comportamiento autocatal´ıtico dieron lugar a ACO. Cosas en com´ un entre hormigas reales y artificiales: • Ambas colonias de hormigas se componen de una poblaci´on de individuos que trabajan juntos para alcanzar una cierta meta • Una colonia es una poblaci´on de simples e independientes agentes as´ıncronos que cooperan para encontrar una buena soluci´on a el problema • En caso de hormigas reales la meta es encontrar comida, en caso de hormigas artificiales, la meta es encontrar la soluci´on a un problema dado de optimizaci´on

241

• Una sola hormiga es capaz de encontrar soluci´on a este problema pero solo la cooperaci´on entre muchos individuos a trav´es de la comunicaci´on por medio del ambiente (stigmergy) les permite encontrar buenas soluciones Las diferencias entre las hormigas reales y las artificiales se dan porque las hormigas reales depositan la sustancia qu´ımica llamada feromona y las reales utilizan variables con valores num´ericos que simulan la feromona. Los caminos de feromona de las hormigas reales se simulan con caminos de feromona artificiales que son una secuencia de valores de feromona asociados con estados del problema. En la vida real la feromona f´ısica se evapora y de esta manera las hormigas olvidan el pasado y se enfocan en nuevas direcciones prometedoras. Las hormigas artificiales crean soluciones secuenciales al ir de un estado a otro, van hacia los estados disponibles tomando una decisi´on a la vez. Diferencias entre hormigas reales y artificiales • Las hormigas artificiales viven en un mundo discreto, se mueven secuencialmente a trav´es de un conjunto finito de estados del problema • Las actualizaciones de feromona (dep´ositos y evaporaci´on de feromona) no se realiza de la misma manera. Algunas veces la actualizaci´on de feromona se hace solo para algunas de las hormigas artificiales y con frecuencia s´olo despu´es de que se construy´o una soluci´on. • Algunas implementaciones de hormigas artificiales usan mecanismos adicionales que no existen en hormigas reales: mirar hacia delante, b´ usqueda local, backtracking, etc.

11.4

La Meta-heur´ıstica de la Optimizaci´ on de Colonias de Hormigas

ACO se ve como una meta-heur´ıstica de optimizaci´on combinatoria (Combinatorial Optimization Problem COP). Para encontrar la soluci´on al prob242

lema se define el modelo de la feromona como un COP. MODELO Un modelo P=(S,ω,f) de un COP consta de: • Un espacio de b´ usqueda S definido sobre un conjunto finito de variables discretas de decisi´on y un conjunto ω de restricciones entre las variables. • Una funci´on objetivo f : S → ℜ+ a ser minimizada El espacio de b´ usqueda se define de la siguiente manera: |D|

• Variables Xi , i = 1, ..., n con valores vij ∈ Di = {vi1 , ..., vi } • Instanciaci´on de variables: asignar un valor vij a una variable Xi denotado como Xi ← vij • Una soluci´on s∗ ∈ S se llama ´optimo global s´ı y s´olo si f (s∗ ) ≤ f (s)∀s ∈ S • S ∗ ⊆ S es el conjunto de todas las soluciones ´optimas globales • Resolver un COP es encontrar al menos una s∗ ∈ S El modelo de un COP se usa para derivar el modelo de feromona de los ACO • Un componente de soluci´on cij es la instancia de una variable de decisi´on Xi = vij • El conjunto de todos los posibles componentes de soluci´on se denota con C. • A cada cij se asocia un par´ametro de rastro de feromona Tij • El conjunto de todos los par´ametros de rastro de feromona se denota con T • El valor de un par´ametro de rastro de feromona es τij 243

Tabla 11.1: Algoritmo de ACO. Algorithm 1: Ant colony optimization metaheuristic Set parameters, initialize pheromone trails While termination conditions not meet do ConstructAntSolutions ApplyLocalSearch (optional) UpdatePheromones end while

En un ACO se utiliza una representaci´on de conocimiento basada en grafos para encontrar la soluci´on al problema de optimizaci´on combinatoria. Para esto se hace un recorrido al grafo de construcci´on GC = (V, E). GC es un grafo totalmente conectado y el conjunto de componentes C se asocian ya sea a los v´ertices o a los arcos de GC . En este modelo la soluci´on se construye de la siguiente manera: • Las hormigas se mueven de un v´ertice a otro a trav´es de los arcos del grafo de construcci´on para construir una soluci´on de forma incremental. • Las hormigas depositan una cantidad de feromona en los componentes (puede ser en los v´ertices o en los arcos que visitan) • La cantidad de feromona depositada δτ depende de la calidad de la soluci´on encontrada • Las siguientes hormigas utilizan la informaci´on de la feromona depositada como una gu´ıa en la b´ usqueda de soluciones dentro del espacio de b´ usqueda En la tabla 11.1 se muestra el algoritmo de la Meta-Heur´ıstica ACO. ConstructAntSolutions Se inicia con una soluci´on parcial vac´ıa sp = varnothing, que se extiende a cada paso a˜ nadi´endole un componente de soluci´on factible cij elegido entre 244

los vecinos N(sp ) ⊆ C. Esto es equivalente a encontrar una ruta en el grafo de construcci´on GC = (V, E) guiada por el mecanismo de construcci´on que define el conjunto N(sp ) con respecto a la soluci´on parcial. La elecci´on de un elemento de N(sp ) se hace de manera probabil´ıstica en cada paso de construcci´on y la manera en que se hace var´ıa dependiendo de la variante de ACO pero una de las mejores es la del sistema “Ant System (AS)” (Dorigo et al. 1996).

p(cij |sp ) = P

τijα · η(Cij )β Cil ∈

N(sP )τilα

·

, ∀Cij η(Cilβ )

∈ N(sP ),

donde, • τij es el valor de feromona asociado al componente Cij • η(·) es una funci´on que asigna en cada paso de construcci´on un valor heur´ıstico a cada soluci´on factible cij ∈ N(sp ), (informaci´on heur´ıstica) • α y β son par´ametros positivos que determinan la relativa importancia de la feromona contra la informaci´on heur´ıstica ApplyLocalSearch Al terminar la construcci´on de soluciones pero antes de actualizar los valores de feromona, se requiere realizar algunas acciones opcionales conocidas como “acciones deamon”. Estas acciones implementan actividades espec´ıficas del problema o centralizadas que no puede realizar una hormiga individualmente. Com´ unmente se realiza una b´ usqueda local a las soluciones construidas y las soluciones ´optimas locales son las que se utilizan para decidir que feromonas se actualizan. UpdatePheromones En este paso se quiere aumentar el nivel de feromona de las rutas prometedoras y disminuir el de las rutas no tan buenas. Primero se decrementan todos los valores de feromona por medio de una evaporaci´on de feromona y 245

despu´es se incrementa el nivel de feromona al conjunto de soluciones buenas Supd X τij ← (1 − ρ) · τij + ρ · F (s), s∈Supd |Cij ∈S

donde: • Supd es el conjunto de soluciones que se actualizar´an • ρ ∈ (0, 1] es un par´ametro llamado tasa de evaporaci´on • F : S → ℜ+ es una funci´on tal que f (s) < f (s′ ) ⇒ F (s) ≥ F (s′ ), ∀s 6= s′ ∈ S • F (·) es conocida como la funci´on de aptitud La evaporaci´on de feromona evita una convergencia demasiado r´apida del algoritmo. Adem´as, esta forma de olvidar permite la exploraci´on de nuevas ´areas del espacio de b´ usqueda. Las versiones de algoritmos ACO difieren en la forma de actualizar los valores de feromona como “Ant Colony System -ACS” (Dorigo et al. 1997) o “MAX - MIN Ant System - MMAS” (Stutzle and Hoos, 2000). La forma de obtener instancias del conjunto Supd a actualizar tambi´en var´ıa. La regla que utiliza el sistema “Ant System” (Dorigo et al., 1996) se conoce como la regla AS-update: Supd ← Siter otra regla que es m´as com´ un es la conocida como IB-update, donde IB se refiere a “Iteration-Best”: Supd ← argmaxs∈Siter F (s) la regla IB-update introduce un mayor sesgo a encontrar la mejor soluci´on que la regla AS-update aunque tambi´en incrementa la probabilidad de converger prematuramente. 246

Otra regla que incrementa el sesgo a encontrar la mejor soluci´on es la regla BS-update (BS se refiere a la mejor soluci´on) y Supd contiene a {ssb }. En general los algoritmos que utilizan variaciones de las reglas IB-update o BS-update y que a˜ naden mecanismos para evitar la convergencia prematura funcionan mejor que aquellos utilizan la regla AS-update.

11.5

Ejemplo: Problema del Agente Viajero

Representaci´ on del problema La primera versi´on de ACO se utiliz´o para resolver el agente viajero. El grafo de construcci´on se crea asociando una ciudad a cada v´ertice y el paso de una ciudad a otra corresponde a los componentes de soluci´on. El movimiento de la ciudad i a la ciudad j es el componente de soluci´on Cij . El peso de los arcos indica la distancia entre ciudades (i.e. la longitud de los arcos) y el nivel de feromona se asocia a los arcos. Construcci´on de la soluci´on • Cada hormiga inicia desde una ubicaci´on aleatoria (v´ertice del grafo) • En cada paso de construcci´on, la hormiga se mueve a trav´es de los arcos del grafo • Cada hormiga mantiene memoria de la ruta que ha seguido y al construir su soluci´on no regresa a un v´ertice ya visitado • La hormiga termina de construir su soluci´on cuando ya visit´o todos los v´ertices del grafo • En cada paso de construcci´on la hormiga elige el arco a seguir (de los disponibles) de manera probabil´ıstica dependiendo de la implementaci´on • Cuando todas las hormigas terminaron su recorrido se actualiza la feromona de los arcos de acuerdo a alguna de las reglas vistas previamente 247

Al construir soluciones, una hormiga k decide irse de la ciudad i a la ciudad j con la siguiente probabilidad: pkij (t) = P

[τij (t)]α · [ηij ]β si j ∈ Nik α · [η ]β k [τ (t)] ij l∈Ni ij

donde ηij = 1/dij es informaci´on disponible, α y β son par´ametros que se tienen que definir, y Nik es la vecindad factible de la hormiga k (el conjunto de ciudades que k no ha visitado). Si α = 0 se visita la ciudad m´as cercana. Si β = 0 se basa solo en las trazas de feromona y tiende a converger r´apidamente a un punto de no mejora sub´optimo. Cuando todas las hormigas completan un circuito, se actualizan las feromonas.Primero se reducen todos los caminos por un factor constante (evaporaci´on) y despu´es cada hormiga deposita la siguiente cantidad de feromona en los nodos de su circuito: ∀(i, j) τij (t + 1) = (1 − ρ) · τij (t) +

m X

∆τijk (t)

k=1

donde 0 ≤ ρ ≤ 1 es la raz´on de evaporaci´on de feromona y m es el n´ umero de hormigas. ∆τijk (t) es la cantidad que deposita cada hormiga en cada nodo, definida por: ∆τijk (t)

=

(

1/Lk (t) si la liga (i, j) es usada por la hormiga k 0 de otra forma

donde Lk (t) es la longitud del circuito de la hormiga k.

11.6

Extensiones

Una primera extensi´on fu´e la de premiar de m´as a la mejor soluci´on global obtenida hasta el momento, algo parecido a una estrategia elitista. 248

Otra variante fue ordenar las hormigas de mejor a peor y solo permitir a las N mejores poner feromonas (adem´as de la mejor ruta global). Otra variante fu´e el mover a las hormigas usando una pol´ıtica ǫ−greedy. Algunas variantes solo actualizan la cantidad de feromona del camino de la mejor hormiga. El uso de feromonas sirve para balancear entre exploraci´on y explotaci´on. Un sistema utiliza un l´ımite inferior y superior de cantidad de feromona. El inferior garantiza un nivel m´ınimo de exploraci´on. Tambi´en se pueden variar los par´ametros α y β para balancear de forma diferente la exploraci´on y explotaci´on durante la b´ usqueda. Se puede combinar con b´ usqueda local (parecido a GRASP). Se construye con ACO y se sigue con b´ usqueda local. Si existen muchos posibles candidates en la parte de construcci´on de soluciones de puede tener tambi´en una lista de candidatos.

11.7

Principales variantes de ACO

• Ant System (Dorigo et al. 1991, Dorigo 1992, Dorigo et al. 1996) • MAX-MIN Ant System (Sttzle and Hoos 2000) • Ant Colony System (Gambardella and Dorigo 1996, Dorigo and Gambardella 1997) • HC-ACO (Hyper-cube ACO) (Blum and Dorigo 2004) • PB-ACO (Population-based ACO) (Guntsch and Middendorf 2002)

249

11.8

Futuro de ACO

• Aplicaci´on de algoritmos ACO a problemas de optimizaci´on del mundo real • Optimizaci´on din´amica (Guntsch and Middendorf 2002). Cuando las condiciones de b´ usqueda o la calidad de las soluciones cambia din´amicamente. • Optimizaci´on multi-objetivo. Resolver varios problemas de optimizaci´on simultaneamente con objetivos potencialmente en conflicto. • Problemas estoc´asticos • Optimizaci´on de valores continuos y variables mixtas • Implementaciones paralelas de ACO’s REFERENCIAS • C. Blum and M Dorigo. The Hyper-cube framework for ant colony optimization. IEEE Transactions on Systems, Man, and Cybernetics Part B, 34(2):1161-1172, 2004. • M. Dorigo. Optimization, Learning and Natural Algoritms (in Italian). PhD thesis, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1992. • M. Dorigo and L. M. Gambardella. Ant Colony System: A cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1):53-66, 1997. • M. Dorigo, V. Maniezzo, and A. Colorni. Positive feedback as a search strategy. Technical Report 91-016, Dipartimento di Elettronica, Politecnico di Milano, Italy, 1991. • M. Dorigo, V. Maniezzo, and A. Colorni. Ant System: Optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics - Part B, 26(1):29-41, 1996.

250

• M. Dorigo and K. Socha. An Introduction to Ant Colony Optimization. Technical Report TR/IRIDIA/2006-010, April 2006. • L. M. Gambardella and M. Dorigo. Solving symmetric and asymmetric TSPs by ant colonies. In T. Baeck, T. Fukuda, and Z. Michalewics, editors, Proceedings of the 1996 IEEE International Conference on Evolutionary Computation (ICEC’96), pages 622 - 627. IEEE Press, Piscataway, NJ, 1996. • S. Goss, S. Aron, J. Deneubourg, and J. Pasteels. Self-organized shortcuts in the Argentine ant. Naturwissenschaften, 76:579-581, 1989. • M. Guntsch and M. Middendorf. Applying population based ACO to dynamic optimization problems. In M. Dorigo, G. Di Caro, and M. Sampels, editors, Proceedings of ANTS 2002 - Third International Workshop on Ant Algorithms, volume 2463 of LNCS, pages 111 - 122. Springer Verlag, Berlin, Germany, 2002. • M. Guntsch and M. Middendorf. A population based approach for ACO. In S. Cagnoni, J. Gottlieb, E. Hart, M. Middendorf, and G. Raidl, editors, Applications of Evolutionary Computing, Proceedings of EvoWorkshops 2002: EvoCOP, EvoIASP, EvoSTim, volume 2279 of LNCS, pages 71-80. Springer Verlag, Berlin, Germany, 2002. • T. Stutzle and H. H. Hoos. MAX-MIN Ant System. Future Generation Computer Systems, 16(8):889-914, 2000.

251