PDF de programación - Inteligencia Social - Optimización basada en organizaciones sociales biológicas

••

Inteligencia Social

Optimización basada en organizaciones

sociales biológicas

M. E. Mazzei

UNA

Organización de los Insectos Sociales

••

Qué los gobierna?

Cómo siguen órdenes?

Cómo se planifican?

Cómo preservan el equilibrio?

2/34

UNA

Enjambre

••

Qué es?: En biología se define un enjambre,
como un conjunto o una agrupación de
organismos semejantes, que permanecen juntos
y se mueven en una misma dirección.

3/34

UNA

Enjambre

Son ejemplos de enjambres:

Colonias de termitas
Bandadas de pájaros para encontrar
alimentos
Colonias de abejas para reproducirse
Un sistema inmune es un enjambre de
células y moléculas
Una multitud de personas

••

4/34

UNA

Características de las organizaciones de Insectos Sociales

••

Siguen reglas simples. Muestran conductas complejas
que surgen entre individuos que exhiben una conducta
simple (auto-organización).

Poseen autonomía: Las interacciones conducen a una
conducta global inteligente.

Poseen funcionamiento distribuido.

5/34

UNA

Conceptos

La auto-organización, proporciona poderosas
herramientas para transferir conocimiento.

Una colonia de hormigas resuelve problemas de:

Búsqueda de alimentos

Construcción de los nidos

Alimentación de las crías

Distribución del trabajo entre individuos

→ Tiene sus contrapartes en las ciencias de la
computación y en ingeniería.

••

6/34

UNA

Conceptos

La idea más importante es usar los principios de
auto-organización de las sociedades de insectos para
coordinar poblaciones de agentes artificiales que
colaboran para resolver problemas computacionales.

Una de las características más resaltantes que se
toma de estas sociedades es la adaptación a los
cambios de ambiente.

Interacción entre los miembros de la sociedad

Estimergía: Comunicación indirecta.

••

7/34

UNA

¿Qué es Inteligencia de Enjambres?

••

En este contexto es el diseño y la utilización de
algoritmos o técnicas inspiradas en la conducta
colectiva de las colonias de insectos u otras
sociedades de animales.

Un enjambre es una población de soluciones que
interactúan entre si y es capaz de optimizar una
función objetivo a través de una búsqueda colaborativa
en un espacio.

8/34

UNA

Sistemas de Enjambres Artificiales

••

Se trata de diseñar sistemas artificiales con el
uso del computador, que sean:

Adaptativos
Descentralizados
Flexibles
Robustos y capaces de resolver problemas.

9/34

UNA

Sistemas de Enjambres Artificiales

••

Trataremos dos técnicas heurísticas:

Algoritmos Hormiga
Enjambres de partículas

10/34

UNA

Colonias de Hormigas

Cómo actúan las hormigas en la búsqueda de alimento

••

11/34

UNA

Colonias de Hormigas

Cómo actúan las hormigas en la búsqueda de alimento

••

12/34

UNA

Colonias de Hormigas

Cómo actúan las hormigas en la búsqueda de alimento?

••

13/34

UNA

Colonias de Hormigas

Cómo actúan las hormigas en la búsqueda de alimento

••

14/34

UNA

Algoritmos Basados en Colonias de Hormigas(ACO)

••

Los algoritmos hormiga se inspiran en la organización
de las hormigas para construir las soluciones. Fueron
desarrollados por M. Dorigo en 1992.

Las soluciones se construyen de manera incremental.

Están basados en heurísticas(experiencias,
exploración)

Pueden aplicarse en cualquier problema de
optimización combinatoria.

15/34

UNA

Algoritmos ACO y el Problema del Agente Viajero

••

Las hormigas artificiales construyen soluciones
haciendo caminatas aleatorias en un grafo conexo.

Cada hormiga es colocada inicialmente en una ciudad
al azar.

En cada iteración, escoge una ciudad que no ha
visitado, empleando la transición probabilística.

En cada iteración se actualizan los rastros de
feromonas.

La construcción de la solución termina cuando se han
visitado todas las ciudades.

16/34

UNA

Algoritmos ACO y el Problema del Agente Viajero

••

Rastro de feromona en arco (i,j): τij(t)

Visibilidad: ηij = 1/dij

pic(t) =

[ϕic(t)]α

[ϕic(t)]α+[ϕil(t)]α , pil(t) =

[ϕil(t)]α

[ϕic(t)]α+[ϕil(t)]α

α y β son parámetros, α ajusta el rastro de feromona y β la
visibilidad

17/34

UNA

Algoritmos ACO y el Problema del Agente Viajero

••

Transición:
pic(t) =

[ϕic(t)]α

[ϕic(t)]α+[ϕil(t)]α , pil(t) =

[ϕil(t)]α

[ϕic(t)]α+[ϕil(t)]α

La hormiga debe decidir a cuál ciudad visitar

18/34

UNA

Algoritmo en seudolenguaje

••

Comienzo

Para todas las k hormigas

Generar aleatoriamente k posiciones.
Colocar las hormigas en las posiciones, τ (0) = τ0

Fin Para

Para t = 1 hasta tmax hacer

Para todas las k hormigas

Construir una ruta Tk(t), calcular:

pil(t) =

[ϕil(t)]α

[ϕic(t)]α+[ϕil(t)]α

pk
ij (t) =

[ϕic(t)]α

[ϕic(t)]α+[ϕil(t)]α ,

Fin Para

Si se ha encontrado una ruta mejor, entonces actualizar T+ y L+ ( la ruta y su longitud).

continúa ...

19/34

UNA

Algoritmo en seudolenguaje

••

Para cada arco (i, j) hacer

Actualizar feromonas:

τij ← (1 − ρ)τij (t) + ρ∆τij (t) + eτ e

ij (t), donde

∆τij (t) =

n

X

i=1

∆τ k

ij (t)

∆τ k

ij = 


1
C k ,
0,

si arco (i, j) pertenece a T k
en otro caso

Fin Para

Para todo arco (i, j) hacer

τij (t + 1) = τij (t)

Fin Para

Fin Para

Fin

(1)

20/34

UNA

Aplicaciones de los algoritmos Hormiga

••

Se emplean en la resolución de problemas de combinatoria, entre ellos:

Problemas de rutas ( redes estáticas)

Problemas de redes dinámicas

Problemas de asignación

Problemas de planificación de horarios

Problemas de subconjuntos

Otros más recientes como los de aprendizaje de máquinas(machine learning), a
través de los cuales se pueden resolver problemas de clasificación de patrones.

También se han combinado estos algoritmos con otras técnicas para resolver
problemas, estas se conocen como híbridas.

21/34

UNA

Optimización por Enjambres de Partículas

••

22/34

UNA

Optimización por Enjambres de Partículas

••

Los algoritmos de Optimización de Partículas o
algoritmos PSO (Particle Swarm Optimization)
fueron desarrollados por Kennedy y Eberhart en
1995.
Se trata de métodos de optimización para
funciones no lineales en espacios continuos y
discretos, basados en el concepto de bandadas
de aves y cardúmenes.

23/34

UNA

PSO

••

Los enjambres de individuos se mueven libremente en un
espacio, en búsqueda de alimento. Cuando un individuo lo
halla, de alguna manera se comunica con sus vecinos, por
lo que el enjambre seguirá a dicho individuo.

El término partícula se refiere a elementos de la población
que no poseen masa ni volumen pero si poseen
movimiento, cuando se les puede llamar "puntos"se trata
de elementos que permanecen estáticos. Se le asocia a
cada partícula una posición y una velocidad.

24/34

UNA

PSO

••

Para simular este tipo de agrupación, en el computador, se
emplean 3 reglas muy simples:

1. Evitar las colisiones de individuos con sus vecinos.

2. Ajustar la velocidad de un individuo a la misma de sus

vecinos.

3. Hacer que cada individuo permanezca cerca de sus

vecinos.

25/34

UNA

PSO

••

Las partículas cambian de estado al desplazarse dentro
del espacio de búsqueda. Cada partícula i es una solución
y se trata como un punto del espacio, se le representa
como:

x = (x1, . . . , xd)

Se evalúa el çomportamiento"de cada partícula, de
acuerdo a una función de costo o de fitness. La que tiene
un menor costo asociado (problema de minimización) se
denominará:

p = (p1, . . . , pd)

26/34

UNA

PSO

••

La tasa de cambio es la velocidad, y se denota por:

v = (v1, . . . , vd)

La velocidad de cada partícula se calcula de acuerdo a la
siguiente ecuación:

v(k+1)
j

= v(k)

j + c1ǫ1(p(k)

j − x(i)

j ) + c2ǫ2(g(k)

j − x(k)
j )

x(k+1)
j

= x(k)

j + v(k+1)

j

ǫ1 y ǫ2 son números aleatorios uniformes en (0,1]

(2)

(3)

27/34

UNA

PSO

••

El algoritmo considera una memoria de partículas. En la
ecuación de actualización de la velocidad, p representa la
mejor partícula i en su historia y g la mejor partícula en su
vecindario. Existen diferentes maneras de tratar la
organización de partículas.

La topología de las partículas es su forma de agrupación
y relación.

28/34

UNA

PSO

Las topologías más conocidas son la anillo y la estrella.
Existen otras como: la Von Newmann y cualquier otra con
la que sea posible experimentar. Originalmente se
denominó al modelo en el que se empleaba la topología
anillo, modelo lbest y el asociado a la topología estrella,
modelo gbest

••

29/34

UNA

PSO

••

El algoritmo genera una población inicial de partículas con
posición y velocidad al azar. Estas partículas cambian de
posición y velocidad de acuerdo al desempeño del grupo.

Es importante considerar el tipo de topología a emplear,
en cuanto a la relación de las mismas con sus vecinas. El
proceso se puede realizar un número fijo de
iteraciones(maxiter) o también se puede comparar dos
iterados sucesivos y dependiendo de su aproximación el
proceso se detiene o continúa.

30/34

UNA

Algoritmo PSO

Comienzo

Crear población inicial de partículas {xi}
Para cada partícula i en el enjambre hacer

Si f (x) < f (p) entonces Copiar (p, x)

// copia x en p

// asignación arbitraria

g = i
Para j ∈ J

//J conjunto de índices de las partículas vecinas

Si f (pj ) < f (pg) entonces g = j

//g el índice de mejor en vecindad

Fin Para
Para d = 1 hasta D hacer

vd(t) = vd(t − 1) + c1ǫ1(pd − xd(t − 1)) + c2ǫ2(gd − xd(t − 1))
xd = xd + vd

Fin Para

Fin Para

Fin

••

31/34

UNA

Ajustes y Variantes al algoritmo PSO

••

Ajuste de la velocidad: Para evitar que la velocidad
alcance valores muy grandes, lo cual ocasiona
igualmente valores muy grandes para las posiciones
en el espacio de búsqueda,se limita a un valor Vmax,
en mayor absoluto no mayor que 4

La introducción del peso inicial w, frena el crecimiento
de la velocidad, de manera dinámica, ocasionando en
un principio una exploración global y al final un
refinamiento de la solución.

d = wv(i)
v(i)

d + c1ǫ1(p(i)

d − x(i)

d ) + c2ǫ2(g(i)

d − x(i)
d )

(4)

32/34

UNA

Ajustes y Variantes al algoritmo PSO

••

El peso inercial se actualiza de acuerdo a la siguiente ecuación:

w = wmax − (wmax − wmin)

k

maxiter

Comú