Algoritmos de Hormiga

Universidad Autnoma Metropolitana

Algoritmo de Hormiga

Simulacin Multi-agente para resolver amplia variedad de problemas

Algoritmos de Hormiga o Optimizacin de una Colonia de Hormigas[Dorigo96].

La naturaleza, numerosas ideas en el espacio de la optimizacin

Pre-cocido Simulado(Simulated Annealing) Algoritmos Genticos (Genetic Algorithms)

Motivacin Natural

A pesar de que las hormigas son prcticamente ciegas son capaces de:

Navegar entornos complejos Encontrar comida a grandes distancias Comunicarse con otras (Stigmerga) Regresar a su nido Ellas pueden hacer muchas de ests

actividades gracias a las Feromonas

Rutas Optimizadas

Sorprendentemente tienden a encontrar la mejor ruta

Cuando su objetivo esta cerca dan muchas rondas hacia el mismo

Cuando su objetivo es lejano dan menos rondas -la concentracin de feromona es mayor-

Donde hay mayor concentracin de feromonas es por donde ms circulan

El proceso iterativo transforma un trayecto sub-optimo a optimo

Caractersticas

Las hormigas son altruistas y cooperativas y trabajan por alcanzar una meta comn

Las hormigas trabajan en paralelo en el entorno para resolver un problema

Mediante la stigmergia ayudan a otras a optimizar la solucin

Algoritmo de hormiga

Red Se representa como un grafo (Vrtices y aristas) bi-

direccionado Cada arista tiene un peso asociado que indica la

distancia entre los nodos La hormiga Es un simple agente usado para resolver un problema Tiene un conjunto de reglas simples que definen como

eligen la ruta en el grafo Tiene una lista de nodos tab visitados (con orden) El recorrido es una ruta Hamiltoniana La lista permite calcular la longitud del tour Irriga feromonas en las aristas una vez terminado el

tour

Poblacin inicial Esta es creada y distribuida a lo largo de los nodos del

grafo El movimiento de la hormiga Esta basado en una ecuacin de probabilidad. La

siguiente ecuacin ayuda a identificar la siguiente arista

P=(r ,u)(r ,u)

k(r ,u)(r ,u)

Recorrido de la hormiga El recorrido existe cuando una hormiga visit todos los

nodos. Una vez recorridos todos los nodos su distancia

puede ser calculada. La siguiente ecuacin muestra la cantidad de

feromona dejada en cada arista del recorrido por la hormiga k.

ijk (t )= Q

Lk(t )

Esta cantidad es usada en la siguiente ecuacin para incrementar la feromona en las aristas del trayecto

La constante p es un valor entre cero y uno

ij(t )= ij(t)+( ijk (t)p)

Evaporacin de la feromona En el recorrido inicial cada arista tiene la misma

probabilidad de ser tomada Con la finalidad de ir eliminando las aristas que son

parte de las rutas inconvenientes, existe la evaporacin de la feromona. La cual tiene lugar en todas las aristas de la red. La ecuacin de evaporacin es la siguiente:

ij(t )= ij(t)(1 p)

Reiniciar Cuando el recorrido esta completo, las aristas fueron

actualizadas basadas en la longitud del recorrido, y la evaporacin en todas las aristas fue efectuada, se reinicia el algoritmo.

Se limpia la lista tab y la longitud del recorrido es cero.

Se migran las hormigas a otras aristas que no han sido investigadas.

El proceso se repite varias veces hasta que no haya cambios para el mismo numero de recorridos. La mejor ruta es emitida como solucin.

Referencias

[Dorigo96] Dorigo Marco, Ant Colonies for the traveling Salesman Problem, BioSystems,1996,43:73-81

Tim Jones, AI Application Programming, Course Technology, 2nd Edition

Preguntas

Pgina 1Pgina 3Pgina 4Pgina 5Pgina 6Pgina 7Pgina 8Pgina 9Pgina 10Pgina 11Pgina 12Pgina 13Pgina 14Pgina 15