• Author / Uploaded
• bachuniv

• Categories
• Hormiga
• Vértice (teoría de grafos)
• Optimización Matemática
• Algoritmos y Estructuras de Datos
• Algoritmos

Citation preview

Algoritmos de Hormiga

Universidad Autónoma Metropolitana

Algoritmo de Hormiga ➲ ➲ ➲  

Simulación Multi-agente para resolver amplia variedad de problemas Algoritmos de Hormiga o Optimización de una Colonia de Hormigas[Dorigo96]. La naturaleza, numerosas ideas en el espacio de la optimización Pre-cocido Simulado(Simulated Annealing) Algoritmos Genéticos (Genetic Algorithms)

Motivación Natural ➲    

➲

A pesar de que las hormigas son prácticamente ciegas son capaces de: Navegar entornos complejos Encontrar comida a grandes distancias Comunicarse con otras (Stigmergía) Regresar a su nido

Ellas pueden hacer muchas de estás 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 concentración de feromona es mayor Donde hay mayor concentración de feromonas es por donde más circulan  El proceso iterativo transforma un trayecto sub-optimo a optimo

➲

Características ➲ ➲ ➲

Las hormigas son altruistas y cooperativas y trabajan por alcanzar una meta común Las hormigas trabajan en paralelo en el entorno para resolver un problema Mediante la stigmergia ayudan a otras a optimizar la solución

Algoritmo de hormiga ➲  

➲      

Red

Se representa como un grafo (Vértices y aristas) bidireccionado 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

➲ 

➲ 

Población inicial

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

El movimiento de la hormiga

Esta basado en una ecuación de probabilidad. La siguiente ecuación ayuda a identificar la siguiente arista τ(r , u)α∗η(r , u)β P= ∑ τ(r , u)α∗η(r , u)β k

➲   

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 ecuación muestra la cantidad de feromona dejada en cada arista del recorrido por la hormiga k. Δ τ kij (t )=

Q L k (t )

➲

Esta cantidad es usada en la siguiente ecuación para incrementar la feromona en las aristas del trayecto τij (t )=τ ij (t )+(Δ τ kij (t )∗p)

➲

La constante p es un valor entre cero y uno

➲  

Evaporación 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 evaporación de la feromona. La cual tiene lugar en todas las aristas de la red. La ecuación de evaporación 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 evaporación 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 solución.

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