Inteligencia de enjambresinfofich.unl.edu.ar/upload/f20c89d95fcdd341f7fd8d4dccce4aab21fb08de.pdfAlgoritmo 1: Colonia de hormigas simple (sACO) 1. t= 0, Inicializar feromonas con valores

Inteligencia de enjambres

Diego Milone

Inteligencia ComputacionalDepartamento de Informática

FICH-UNL

Colonia de hormigas:introducción

Diego Milone


FICH-UNL

Inteligencia Computacional - FICH - UNL

La inspiración biológica

• Hay 1016 hormigas en la tierra (y 6 × 109 humanos)

• Igual peso total

• 30 millones por colonia













• Feromonas: las búsqueda del camino más corto a la comida

1. Comportamiento inicial aleatorio2. Cuando encuentran una fuente de comida se organizan y

comienzan a seguir el mismo camino2.1 Mecanismo de reclutamiento: mayormente por feromonas,

liberadas al regresar (algunas las liberan en proporción a lacantidad de alimento encontrado)

2.2 Si otras encuentran feromonas siguen el rastro (con másprobabilidad, tratando de alejarse del hormiguero si no llevancomida)

2.3 El camino se refuerza al ser seguido por más y más hormigas

• Notar:• Comunicación indirecta• Modificación del entorno físico: estigmergía



• Feromonas: las búsqueda del camino más corto a la comida1. Comportamiento inicial aleatorio

2. Cuando encuentran una fuente de comida se organizan ycomienzan a seguir el mismo camino2.1 Mecanismo de reclutamiento: mayormente por feromonas,







• Feromonas: las búsqueda del camino más corto a la comida1. Comportamiento inicial aleatorio2. Cuando encuentran una fuente de comida se organizan y

comienzan a seguir el mismo camino

2.1 Mecanismo de reclutamiento: mayormente por feromonas,liberadas al regresar (algunas las liberan en proporción a lacantidad de alimento encontrado)





































Experimento del puente binario

Colonia de hormigas:algoritmos

Diego Milone


FICH-UNL


Colonia de hormigas

Definiciones:

• G = (V ,E): grafo con vértices V y matriz de conexiones E• σij: feromonas en la conexión entre i y j• k = 1, 2, . . . ,N: hormigas

• Ni: nodos disponibles a partir del nodo i• pk(t): camino de la hormiga k

Notar:

• t → t + 1: se incremente una vez que todas las hormigasencuentran el alimento y vuelven al origen

• Nki : en algunos casos el entorno se limita a los nodos que no

haya visitado previamente la hormiga k


Colonia de hormigas

Definiciones:

• G = (V ,E): grafo con vértices V y matriz de conexiones E• σij: feromonas en la conexión entre i y j• k = 1, 2, . . . ,N: hormigas

• Ni: nodos disponibles a partir del nodo i• pk(t): camino de la hormiga k

Notar:

• t → t + 1: se incremente una vez que todas las hormigasencuentran el alimento y vuelven al origen

• Nki : en algunos casos el entorno se limita a los nodos que no

haya visitado previamente la hormiga k


Algoritmo 1: Colonia de hormigas simple (sACO)1. t = 0, Inicializar feromonas con valores pequeños al azar (σij(t)f U(0, σ0))2. Ubicar N hormigas en el nodo origen

3. repetir3.1 para cada hormiga k = 1, 2, . . . ,N

3.1.1 pk(t) = ∅3.1.2 repetir

• seleccionar el próximo nodo según la probabilidad

pkij(t) = · · ·

• agregar un paso (i, j) al camino pk(t)hasta alcanzar el destino

3.1.3 eliminar los ciclos en pk(t)3.1.4 calcular la longitud del camino econtrado f

(pk(t)

)3.2 para cada conexión (i, j)• reducir por evaporación la cantidad de feromonas: σij(t)← (1 − ρ)σij(t)

3.3 para cada conexión (i, j)• depositar feromonas proporcionalmente a la bondad de la solución

σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)3.4 t ← t + 1

hasta que todas las hormigas sigan el mismo camino

4. devolver el camino más corto (↓ f(pk(t)

))




3.1.1 pk(t) = ∅

3.1.2 repetir• seleccionar el próximo nodo según la probabilidad

pkij(t) = · · ·



(pk(t)



σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)3.4 t ← t + 1



))




3.1.1 pk(t) = ∅3.1.2 repetir


pkij(t) = · · ·

pkij(t) =

σαij(t)∑

∀u∈Ni

σαiu(t)si j ∈ Ni

0 en otro caso.



(pk(t)



σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)3.4 t ← t + 1



))




3.1.1 pk(t) = ∅3.1.2 repetir

• seleccionar el próximo nodo según la probabilidad pkij(t) = · · ·



(pk(t)

)

3.2 para cada conexión (i, j)• reducir por evaporación la cantidad de feromonas: σij(t)← (1 − ρ)σij(t)


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)3.4 t ← t + 1



))




3.1.1 pk(t) = ∅3.1.2 repetir




(pk(t)



σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)3.4 t ← t + 1



))




3.1.1 pk(t) = ∅3.1.2 repetir




(pk(t)



σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)

3.4 t ← t + 1hasta que todas las hormigas sigan el mismo camino


))




3.1.1 pk(t) = ∅3.1.2 repetir




(pk(t)



σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

1/f(pk(t)

)3.4 t ← t + 1



))


Algoritmo 2: Sistema de hormigas (AS)1. t = 0, σij(t)f U(0, σ0)2. Ubicar N hormigas en el nodo origen


3.1.1 pk(t) = ∅3.1.2 repetir


pkij(t) = · · ·


3.1.3 calcular la longitud del camino econtrado f(pk(t)

)3.2 para cada conexión (i, j)• reducir por evaporación la cantidad de feromonas: σij(t)← (1 − ρ)σij(t)• depositar feromonas proporcionalmente a la bondad de la solución

∆σkij(t) =

Q/f

(pk(t)

)global.

Q uniforme.Q/dij local.

σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)


4. devolver el mejor camino




3.1.1 pk(t) = ∅

3.1.2 repetir• seleccionar el próximo nodo según la probabilidad

pkij(t) = · · ·




∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)






3.1.1 pk(t) = ∅3.1.2 repetir


pkij(t) = · · ·

pkij(t) =

σαij(t)η

βij(t)∑

∀u∈Nki

σαiu(t)ηβij(t)si j ∈ Nk

i

0 en otro caso.

→ Deseo de moverse inverso al costo entre nodos: ηij = 1/dij.→ Lista de nodos vecinos con tabú: Nk

i




∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)






3.1.1 pk(t) = ∅3.1.2 repetir




)

3.2 para cada conexión (i, j)• reducir por evaporación la cantidad de feromonas: σij(t)← (1 − ρ)σij(t)• depositar feromonas proporcionalmente a la bondad de la solución

∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)






3.1.1 pk(t) = ∅3.1.2 repetir





• depositar feromonas proporcionalmente a la bondad de la solución

∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)






3.1.1 pk(t) = ∅3.1.2 repetir





∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)






3.1.1 pk(t) = ∅3.1.2 repetir





∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)






3.1.1 pk(t) = ∅3.1.2 repetir





∆σkij(t) =

Q/f

(pk(t)

)global.


σij(t + 1) = σij(t) +∑

∀k/(i,j)∈pk(t)

∆σkij(t)



Enjambre de partículas

Diego Milone


FICH-UNL



• Bandadas de pájaros

• Cada individuo vuela/navega el espacio ajustando su posiciónen base a su experiencia y a la información de los individuosde su entorno

• Emular el éxito de los vecinos y propio• xk(t): posición de la partícula k, en el tiempo t (espacio RN)• vk(t): velocidad de la partícula k, en el tiempo t• Regla básica: xk(t + 1) = xk(t) + vk(t)





• Emular el éxito de los vecinos y propio• xk(t): posición de la partícula k, en el tiempo t (espacio RN)• vk(t): velocidad de la partícula k, en el tiempo t

• Regla básica: xk(t + 1) = xk(t) + vk(t)





• Emular el éxito de los vecinos y propio• xk(t): posición de la partícula k, en el tiempo t (espacio RN)• vk(t): velocidad de la partícula k, en el tiempo t• Regla básica: xk(t + 1) = xk(t) + vk(t)



Definiciones:

• yk: mejor posición personal de la partícula k (la mejor quevisitó desde t = 0 hasta la actualidad)

• f (x): función de error a minimizar

Mejor global (gEP):

• Topología estrella: usa información de todo el enjambre

• y: mejor posición visitada por todo el enjambre



Definiciones:

• yk: mejor posición personal de la partícula k (la mejor quevisitó desde t = 0 hasta la actualidad)

• f (x): función de error a minimizar

Mejor global (gEP):

• Topología estrella: usa información de todo el enjambre

• y: mejor posición visitada por todo el enjambre


Algoritmo 3: Enjambre del mejor global (gEP)1. Inicializar xki(0)f U(xmin

i , xmaxi )

2. repetir2.1 para cada partícula k = 1, 2, . . . ,N

• si f (xk(t)) < f (yk)→ yk = xk(t)• si f (yk) < f (y)→ y = yk

2.2 para cada partícula k = 1, 2, . . . ,N• vki(t + 1) = vki(t) + c1r1i

[yki − xki(t)

]+ c2r2i

[yi − xki(t)

]r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)

hasta cummplir con al condición de finalización

3. devolver la mejor partícula encontrada



i , xmaxi )


• si f (xk(t)) < f (yk)→ yk = xk(t)

• si f (yk) < f (y)→ y = yk


[yki − xki(t)

]+ c2r2i

[yi − xki(t)

]r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)





i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yi − xki(t)

]r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)





i , xmaxi )




[yki − xki(t)

]

+ c2r2i[yi − xki(t)

]r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)





i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yi − xki(t)

]

r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)





i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yi − xki(t)

]r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)





i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yi − xki(t)

]r1i, r2i f U(0, 1)

• xk(t + 1) = xk(t) + vk(t + 1)





Definiciones:• yk: mejor posición personal de la partícula k (la mejor que

visitó desde t = 0 hasta la actualidad)• f (x): función de error a minimizar

Mejor local (ÈP):• Topología anillo: usa información del entorno cercano a la

partícula• Selección: basada en los índices de las partículas (caso más

simple)

Ek = {yk−n, yk−n+1, . . . , yk−1, yk, yk+1, . . . , yk+n}:

• yk = arg min∀yu∈Ek {f (yu)} mejor posición visitada por elentorno de la partícula k



Definiciones:• yk: mejor posición personal de la partícula k (la mejor que

visitó desde t = 0 hasta la actualidad)• f (x): función de error a minimizar

Mejor local (ÈP):• Topología anillo: usa información del entorno cercano a la

partícula• Selección: basada en los índices de las partículas (caso más

simple)

Ek = {yk−n, yk−n+1, . . . , yk−1, yk, yk+1, . . . , yk+n}:• yk = arg min∀yu∈Ek {f (yu)} mejor posición visitada por el

entorno de la partícula k


Algoritmo 4: Enjambre del mejor local (ÈP)1. Inicializar xki(0)f U(xmin

i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yki − xki(t)

]r1i, r2i f U(0, 1)yk = arg min∀yu∈Ek {f (yu)}

• xk(t + 1) = xk(t) + vk(t + 1)

hasta cummplir con al condición de finalización3. devolver la mejor partícula encontrada



i , xmaxi )


• si f (xk(t)) < f (yk)→ yk = xk(t)

• si f (yk) < f (y)→ y = yk


[yki − xki(t)

]+ c2r2i

[yki − xki(t)


• xk(t + 1) = xk(t) + vk(t + 1)




i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yki − xki(t)


• xk(t + 1) = xk(t) + vk(t + 1)




i , xmaxi )




[yki − xki(t)

]

+ c2r2i[yki − xki(t)


• xk(t + 1) = xk(t) + vk(t + 1)




i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yki − xki(t)

]

r1i, r2i f U(0, 1)yk = arg min∀yu∈Ek {f (yu)}

• xk(t + 1) = xk(t) + vk(t + 1)




i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yki − xki(t)


• xk(t + 1) = xk(t) + vk(t + 1)




i , xmaxi )




[yki − xki(t)

]+ c2r2i

[yki − xki(t)


• xk(t + 1) = xk(t) + vk(t + 1)


Documents

Inteligencia de enjambresinfofich.unl.edu.ar/upload/f20c89d95fcdd341f7fd8d4dccce4aab21fb08de.pdfAlgoritmo 1: Colonia de hormigas simple (sACO) 1. t= 0, Inicializar feromonas con valores