Inteligencia de enjambres

Diego Milone Inteligencia Computacional ´ Departamento de Informatica FICH-UNL

´ Introduccion

Colonia de hormigas

´ Automata de estados finitos • Definicion: ´

A =< X, Y, E, D >

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

´ Automata de estados finitos • Definicion: ´

A =< X, Y, E, D > • Extension ´ con funciones de salida: y = λ(x, E)

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

´ Automata de estados finitos • Definicion: ´

A =< X, Y, E, D > • Extension ´ con funciones de salida: y = λ(x, E) • Estados, reglas de transicion, ´ grafos

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automata de estados finitos • Definicion: ´

A =< X, Y, E, D > • Extension ´ con funciones de salida: y = λ(x, E) • Estados, reglas de transicion, ´ grafos • Ejemplos de reglas de transicion ´ determin´ısticas y

probabil´ısticas

:

´ Introduccion

Colonia de hormigas

´ Automatas celulares • Definicion: ´

R =< A, T, C >

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

´ Automatas celulares • Definicion: ´

R =< A, T, C > • Topolog´ıas: triangular, rectangular, hexagonal,...

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares • Definicion: ´

R =< A, T, C > • Topolog´ıas: triangular, rectangular, hexagonal,... • Acoplamiento: • Tipos y tamanos ˜ de vecindad: Von Neumann, Moore,... • Tipos de conexiones: isotropicas, ´ ´ anisotropicas,...

:

´ Introduccion

Colonia de hormigas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • Vivo con menos de 2 vivos en el entorno → muere

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • Vivo con menos de 2 vivos en el entorno → muere • Vivo con mas ´ de 3 vivos en el entorno → muere

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • Vivo con menos de 2 vivos en el entorno → muere • Vivo con mas ´ de 3 vivos en el entorno → muere • Vivo con 2 o 3 vivos en el entorno → vive

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • • • •

:

Vivo con menos de 2 vivos en el entorno → muere ´ de 3 vivos en el entorno → muere Vivo con mas Vivo con 2 o 3 vivos en el entorno → vive Muerto con 3 vivos en el entorno → nace

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • • • •

Vivo con menos de 2 vivos en el entorno → muere ´ de 3 vivos en el entorno → muere Vivo con mas Vivo con 2 o 3 vivos en el entorno → vive Muerto con 3 vivos en el entorno → nace

• → Mirek’s Cellebration

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • • • •

Vivo con menos de 2 vivos en el entorno → muere ´ de 3 vivos en el entorno → muere Vivo con mas Vivo con 2 o 3 vivos en el entorno → vive Muerto con 3 vivos en el entorno → nace

• → Mirek’s Cellebration • Crecimiento de plantas, bacterias,...

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • • • •

Vivo con menos de 2 vivos en el entorno → muere ´ de 3 vivos en el entorno → muere Vivo con mas Vivo con 2 o 3 vivos en el entorno → vive Muerto con 3 vivos en el entorno → nace

• → Mirek’s Cellebration • Crecimiento de plantas, bacterias,... • Poblaciones: colonias de hormigas, enjambre de abejas,

modelos presa predador,...

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • • • •

Vivo con menos de 2 vivos en el entorno → muere ´ de 3 vivos en el entorno → muere Vivo con mas Vivo con 2 o 3 vivos en el entorno → vive Muerto con 3 vivos en el entorno → nace

• → Mirek’s Cellebration • Crecimiento de plantas, bacterias,... • Poblaciones: colonias de hormigas, enjambre de abejas,

modelos presa predador,... • Tejidos biologicos: ´ card´ıaco, nervioso,...

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ Automatas celulares Ejemplos: • Juego de la vida de Conway: reglas basicas ´ • • • •

Vivo con menos de 2 vivos en el entorno → muere ´ de 3 vivos en el entorno → muere Vivo con mas Vivo con 2 o 3 vivos en el entorno → vive Muerto con 3 vivos en el entorno → nace

• → Mirek’s Cellebration • Crecimiento de plantas, bacterias,... • Poblaciones: colonias de hormigas, enjambre de abejas,

modelos presa predador,... • Tejidos biologicos: ´ card´ıaco, nervioso,... • Fluidos

:

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Denominaciones y relaciones: • Computacion ´ evolutiva • Inteligencia de colonias • Inteligencia de enjambres • Inteligencia colaborativa • Inteligencia social • ...

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Caracter´ısticas generales: • Auto-organizacion ´

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Inteligencia colectiva Caracter´ısticas generales: • Auto-organizacion ´ • Estigmerg´ıa: “colaboracion ´ a traves ´ del medio f´ısico”

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Inteligencia colectiva Caracter´ısticas generales: • Auto-organizacion ´ • Estigmerg´ıa: “colaboracion ´ a traves ´ del medio f´ısico” • Comportamiento emergente: inteligencia distribuida,

robustez • Fuerte interaccion ´ local • Organizacion ´ social altamente estructurada • Colaboracion ´ versus competencia

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Inteligencia colectiva Caracter´ısticas generales: • Auto-organizacion ´ • Estigmerg´ıa: “colaboracion ´ a traves ´ del medio f´ısico” • Comportamiento emergente: inteligencia distribuida,

robustez • Fuerte interaccion ´ local • Organizacion ´ social altamente estructurada • Colaboracion ´ versus competencia • Componentes estocasticas ´ • Bio-inspiracion ´

:

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Ejemplos: • Bandadas de pajaros ´

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Ejemplos: • Bandadas de pajaros ´ • Colonias de hormigas

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Ejemplos: • Bandadas de pajaros ´ • Colonias de hormigas • Paneles/enjambres de abejas

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Ejemplos: • Bandadas de pajaros ´ • Colonias de hormigas • Paneles/enjambres de abejas • Cardumenes de peces ´

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Ejemplos: • Bandadas de pajaros ´ • Colonias de hormigas • Paneles/enjambres de abejas • Cardumenes de peces ´ • Rebanos ˜ de ovejas o cabras

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Ejemplos: • Bandadas de pajaros ´ • Colonias de hormigas • Paneles/enjambres de abejas • Cardumenes de peces ´ • Rebanos ˜ de ovejas o cabras • Manadas de predadores

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Elementos individuales: • ”Boids”: part´ıculas, objetos, elementos...

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Elementos individuales: • ”Boids”: part´ıculas, objetos, elementos... • Automatas: ´ ´ redes de automatas celulares

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Elementos individuales: • ”Boids”: part´ıculas, objetos, elementos... • Automatas: ´ ´ redes de automatas celulares • Agentes: en estructuras de multi-agentes

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Algoritmos: X Colonias de hormigas X Enjambre de part´ıculas

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Algoritmos: X Colonias de hormigas X Enjambre de part´ıculas • Difusion ´ estocastica ´ • Formacion ´ de r´ıos • Busqueda gravitacional ´ • Sistema inmune artificial • Algor´ıtmos memeticos ´ • ...

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Inteligencia colectiva Algoritmos: X Colonias de hormigas X Enjambre de part´ıculas • Difusion ´ estocastica ´ • Formacion ´ de r´ıos • Busqueda gravitacional ´ • Sistema inmune artificial • Algor´ıtmos memeticos ´ • ... • Relacionados: algoritmos evolutivos, SOM,...

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Inteligencia colectiva Principales aplicaciones: • Optimizacion: ´ aproximacion ´ de funciones, entrenamiento, ´ identificacion, ´ planificacion,... ´ estimacion,

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Inteligencia colectiva Principales aplicaciones: • Optimizacion: ´ aproximacion ´ de funciones, entrenamiento, ´ identificacion, ´ planificacion,... ´ estimacion, • Busqueda, ruteo ´ • Agrupamiento no supervisado, clasificacion ´ • ...

:

´ Introduccion

Colonia de hormigas

Colonia de hormigas

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • Hay 1016 hormigas en la tierra (y 6 × 109 humanos) • Igual peso total • 30 millones por colonia

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • • • •

:

Hay 1016 hormigas en la tierra (y 6 × 109 humanos) Igual peso total 30 millones por colonia ´ corto a la Feromonas: las busqueda del camino mas ´ comida

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • • • •

Hay 1016 hormigas en la tierra (y 6 × 109 humanos) Igual peso total 30 millones por colonia ´ corto a la Feromonas: las busqueda del camino mas ´ comida 1. Comportamiento inicial aleatorio 2. Cuando encuentran una fuente de comida se organizan y comienzan a seguir el mismo camino 2.1 Mecanismo de reclutamiento: mayormente por feromonas, ´ a la liberadas al regresar (algunas las liberan en proporcion cantidad de alimento encontrado) ´ 2.2 Si otras encuentran feromonas siguen el rastro (con mas probabilidad, tratando de alejarse del hormiguero si no llevan comida) ´ y mas ´ 2.3 El camino se refuerza al ser seguido por mas hormigas

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • • • •

Hay 1016 hormigas en la tierra (y 6 × 109 humanos) Igual peso total 30 millones por colonia ´ corto a la Feromonas: las busqueda del camino mas ´ comida 1. Comportamiento inicial aleatorio 2. Cuando encuentran una fuente de comida se organizan y comienzan a seguir el mismo camino 2.1 Mecanismo de reclutamiento: mayormente por feromonas, ´ a la liberadas al regresar (algunas las liberan en proporcion cantidad de alimento encontrado) ´ 2.2 Si otras encuentran feromonas siguen el rastro (con mas probabilidad, tratando de alejarse del hormiguero si no llevan comida) ´ y mas ´ 2.3 El camino se refuerza al ser seguido por mas hormigas

:

• Notar: • Comunicacion ´ indirecta • Modificacion ´ del entorno f´ısico: estigmerg´ıa

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Experimento del puente binario

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Colonia de hormigas Definiciones: • G = (V, E): grafo con vertices ´ V y matriz de conexiones E • σij : feromonas en la conexion ´ entre i y j • k = 1, 2, . . . , nk : hormigas • Ni : nodos disponibles a partir del nodo i • xk (t): camino de la hormiga k

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Algoritmo 1: Colonia de hormigas simple (sACO)

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Algoritmo 2: Sistema de hormigas (AS)

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

:

Enjambre de part´ıculas

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • Bandadas de pajaros ´ • Cada individuo vuela/navega el espacio ajustando su

´ en base a su experiencia y a la informacion ´ de los posicion individuos de su entorno

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • Bandadas de pajaros ´ • Cada individuo vuela/navega el espacio ajustando su

´ en base a su experiencia y a la informacion ´ de los posicion individuos de su entorno • Emular el exito ´ de los vecinos y propio • xi (t): posicion ´ de la part´ıcula i, en el tiempo t (espacio RN ) • vi (t): velocidad de la part´ıcula i, en el tiempo t

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

´ biologica ´ La inspiracion • Bandadas de pajaros ´ • Cada individuo vuela/navega el espacio ajustando su

´ en base a su experiencia y a la informacion ´ de los posicion individuos de su entorno • Emular el exito ´ de los vecinos y propio • xi (t): posicion ´ de la part´ıcula i, en el tiempo t (espacio RN ) • vi (t): velocidad de la part´ıcula i, en el tiempo t • Regla basica: ´ xi (t + 1) = xi (t) + vi (t)

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Enjambre de part´ıculas Definiciones: • yi : mejor posicion ´ personal de la part´ıcula i (la mejor que

visito´ desde t = 0 hasta la actualidad) • y ˆi : mejor posicion ´ visitada por todo el enjambre

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Algoritmo 3: Enjambre del mejor global (gEP)

:

´ Introduccion

Colonia de hormigas

Enjambre de part´ıculas

Algoritmo 4: Enjambre del mejor local (`EP)

: