Hormigas Artificiales

Insectos Sociales y Resolución Distribuida de Problemas.

Ing. Mauro San Martínmsmartin@elqui.cic.userena.cl

AcadémicoUniversidad de La Serena

InfoUDA - Agosto 2000

Agenda

Vida ArtificialHormigasHormigas ArtificialesAplicaciones de Hormigas Artificiales La ruta a la comida: un applet

ilustrativo.

Vida Artificial

Definición: La Vida Artificial es el estudio de los sistemas

concebidos por el hombre que presentan comportamientos característicos de los sistemas vivos.

La Vida Artificial completa el enfoque tradicional de la Biología (análisis de sistemas vivos) intentando la sintetizar el comportamiento de estos sistemas sobre el computador y/u otros medios artificiales.

Las Hormigas

Una Hormiga Cada hormiga es bastante tonta: poca memoria y unos

20 estados.

Una Colonia o Enjambre Es capaz de: construir nidos extremadamente

complejos, repartir labores de manera eficiente, agricultura y ganadería, ...

Comportamiento Emergente No poseen lenguaje No hay información

centralizada (“La Reina NO reina”)

Stigmergy. “El mapa se dibuja en el

terreno”

Las Hormigas Artificiales

Aplicación del conocimiento sobre insectos sociales en la creación de metáforas para la resolución de problemas.

Aspectos Claves

Distribución v/s Centralización. Comportamiento emergente v/s

Control y Preprogramación. Adaptación a condiciones

cambiantes del ambiente en tiempo real.

Aplicaciones de Hormigas Artificiales(1)

Sistemas multi-agentes Definición de Agente : inteligencia, autonomía y

capacidad de interacción.

Problemas en Grafos Ruta más corta Vendedor Viajero (TSP)

Ejemplo: Estrategia de forrageo Descubrimiento de la ruta más corta / barata. Stigmergy: Uso de feromonas virtuales.

Aplicaciones de Hormigas Artificiales(2)

Balance de Carga en Redes de Computadores.

Ruteo en Redes de Telecomunicaciones.Optimización Combinatorial.Comportamiento

Colaborativo de Robots.

La ruta a la comida: un applet ilustrativo. (1)

NIDO

COMIDA

Las Hormigas son capaces de: Encontrar la ruta más corta entre el

NIDO y la COMIDA sin tener un “mapa”.

¿Cómo lo hacen? En cada momento, una Hormiga

simplemente camina y va decidiendo su dirección usando como referencia un rastro químico dejado por las que pasaron antes por allí. A su vez, va dejando un rastro químico sobre la ruta que usa. El rastro se evapora.

Una ruta más corta puede ser transitadas más veces en un lapso dado su rastro químico es más intenso y tiene mayor probabilidad de ser elegida.

Usan el terreno para dibujar el mapa.

Las hormigas caminan entre el nido y la comida. Bajan hasta la comida, suben hasta el nido, y así sucesivamente.

Mientras más feromona hay en un arco (mientras más blanco está), más probable que se vayan por ahí. Y a su vez, van agregando feromona a los arcos por los que pasan, pero ese rastro se va debilitando a medida que se alejan del punto de donde partieron. Con una pequeña probabilidad, la hormiga toma un camino cualquiera, en lugar de fijarse en la feromona.

La feromona se va evaporando, así que si no pasan hormigas durante un rato, el rastro se borra.

La ruta a la comida: un applet ilustrativo. (2)

Un applet para modelar este comportamiento de las Hormigas: El terreno es representado por un grafo no dirigido. (Las rutas son discretas,

su tamaño está dado por la cantidad de aristas que las forman)

Para terminar

Queda mucho por hacer, muchas posibles aplicaciones por investigar y, muy importante, falta investigación teórica que nos permita entender a cabalidad cómo “funcionan” las hormigas.

Las Hormigas son Sistemas Distribuidos de Agentes Simples: No necesita información ni control centralizados (aptos para redes). Se adaptan a condiciones cambiantes del medio (on-line). Al ser simples, individualmente no requieren gran poder de

procesamiento.

Consultas

Referencias

1. Bonabeau, Dorigo, Theraulaz: SWARM INTELLIGENCE, FROM NATURALTO ARTIFICIAL SYSTEMS. Oxford University Press. 1999.

2. Schoonderwoerd, R.: COLLECTIVE INTELLIGENCE FOR NETWORK CONTROL. Tesis de Ingeniería Delft University of Technology. 1996.

3. Di Caro, Dorigo: “AntNet: Distributed Stigmergetic Control for Communications Networks”. 1998.

4. Schoonderwoerd, Holland, Bruten: “Ant-like agents for load balancing in telecommunications networks”. 1997.

5. Dorigo, Gambarella: Ant Colonies for the travelling salesman problem”. 1997.

6. Fenet, Hassas: “An Ant Based System for Dynamic Multiple Criteria Balancing”. 1998.

7. WWW: www.sfi.org, www.swarm.org, iridia.ulb.ac.be/dorigo.