Algoritmo de optimización basado en

enjambres de partículas con comportamiento

de vorticidad y búsqueda individual y grupal
Vortex Particle Swarm Optimization with Individual and Group
Search



 
Ingeniero electrónico, ingeniero mecatrónico, especialista en Telecomunicacio-
nes Móviles, magíster en Ingeniería Industrial, magíster en Ingeniería Mecánica,
docente de la Universidad Distrital Francisco José de Caldas, Bogotá, Colombia.
Contacto: heespitiac@[Link]

    

Ingeniero eléctrico, magíster en Sistemas de Control, doctor en Sistemas de
Control, docente de la Universidad Nacional de Colombia, Bogotá, Colombia.
Contacto: jsofronye@[Link]

Fecha de recepción: 31 de agosto de 2013 Clasificación del artículo: investigación

Fecha de aceptación: 16 de mayo de 2014 Financiamiento: Universidad Nacional de Colombia

Palabras clave: algoritmo, comportamiento animal, optimización

Keywords: algorithm, animal behaviour, optimization

RESUMEN por el modelo seleccionado, el cual se encuentra

basado en el comportamiento de un enjambre de
En este documento se realiza la propuesta de un individuos. Para establecer el desempeño del al-
algoritmo de optimización basado en un enjam- goritmo se emplea un conjunto de funciones de
bre de partículas con características de vorticidad, prueba en dos dimensiones.
donde se considera una búsqueda grupal asociada
al punto medio del enjambre y una búsqueda in-
dividual dada por la mejor posición de cada indi- ABSTRACT
viduo. Con la búsqueda grupal se espera lograr la
convergencia de todo el enjambre, mientras que In this document, it will be introduced the pro-
la búsqueda individual permite una mejor explo- posal for optimization algorithm based on par-
ración del espacio de búsqueda. El algoritmo pre- ticle swarms vorticity features, where a search
senta fases de convergencia y exploración dadas group is considered through the association to the

24 Tecnura Vol. 18 No. 42 pp. 24 - 37 octubre - diciembre de 2014

 investigación
midpoint of the swarm and an individual search is The algorithm has convergence and exploration
given for the best position of each individual. The behavior given by the selected model which is
search group seeks to achieve the convergence of based on the behavior of a swarm of individuals.
the whole swarm, whereas the individual search For establishing the algorithm performance, a set
allows better exploration in pursuant of space. of test functions in two dimensions is used.

* * *

INTRODUCCIÓN de respuesta, dirección, inhibición, redundancia,

sincronización y egoísmo.
La descripción del comportamiento de muchos
seres vivos se caracteriza por presentar movi- Sobre los diferentes enfoques considerados para
miento cooperativo coordinado, tal como ban- modelos de enjambres, Couzin (2005) analiza el
dadas de aves, cardúmenes de peces e incluso efecto que tiene el liderazgo de un individuo, Ba-
microorganismos. Uno de los comportamientos de jec (2009) considera las diferentes formas de or-
interés consiste en el movimiento circular de par- ganización que presentan las aves y Zhang (2008)
tículas alrededor de un punto denominado vórtice observa el efecto que tiene incorporar mecanis-
(Ebeling, 2002), ya que esta forma de locomoción mos de predicción en un modelo de enjambre.
puede ser una buena estrategia para la búsqueda
de alimento y evasión de obstáculos y depredado- Modelos de partículas con comportamiento
res (García, 2007). Por las anteriores característi- de vorticidad
cas estos comportamientos pueden ser empleados
en la propuesta de algoritmos de optimización. La vorticidad es un comportamiento que se pre-
!"#$ %&" '*!%+!"%/$ !" 3& 4+/;& < ! ;!=! $3
Comportamientos de enjambres acoplamiento que existe entre las fuerzas inercia-
les y las fuerzas viscosas (número de Reynolds
En la naturaleza se pueden apreciar diferentes >?!*@AHKOQWXY 3$"[3//;!!#!%&\]&*#$\/!"-
comportamientos los cuales han sido estudiados to se realiza mediante las ecuaciones de Navier
y representados de forma analítica. En particular, Stokes, las cuales suelen ser difíciles de resolver
las congregaciones de individuos son una temáti- de forma analítica en casos generales (Çengel,
ca interesante por los comportamientos emergen- ^__QXY 3%&\]&*#$\/!"#&;!`&*#/%/;$;!%$*$%-
tes que surgen (Sumpter, 2006). Entre los trabajos teriza por el movimiento de forma rotacional de
que se pueden resaltar se encuentra el presentado partículas alrededor de un punto, el cual se de-
por Vicsek (1995), donde se desarrolla un modelo "&\/"$`{*#/%!Y|;!\[;!3&4+/;&A!#!#/]&
básico para representar un enjambre de indivi- de comportamiento se presenta en enjambres de
duos. Este último autor lleva a cabo una extensión individuos como peces, aves y bacterias, entre
de su trabajo (Vicsek, 2008), donde describe al- otros. Existen dos modelos que son los más em-
gunos patrones representativos de los enjambres. pleados para representar este comportamiento,
Por otro lado, Sumpter (2006) hace una revisión uno consiste en el modelo de partícula autopro-
del comportamiento colectivo para la formación pulsada (Levine, 2000; D’Orsogna, 2006) y el
de enjambres observando propiedades de autorre- otro corresponde al de partícula activa brownia-
gulación y principios de comportamiento colec- na (Ebeling, 2006). Este último, a diferencia del
tivo como: integridad, variabilidad, realimenta- primero, considera una componente estocástica.
ción positiva, realimentación negativa, umbrales Por lo general, estos modelos suelen emplear

Algoritmo de optimización basado en enjambres de partículas con comportamiento de vorticidad y búsqueda individual y grupal 25


      
investigación
potenciales de Morse para representar la interac- %$]$%/;$; ;! =ƒ„+!;$Y …"$ \&;/€%$%/{" $;/-
ción entre individuos; sin embrago, en el trabajo cional del algoritmo PSO consiste en reiniciarlo
de Erdmann (2005) se puede observar un modelo cuando se considera que hay un estancamiento de
que emplea un potencial parabólico. este (García, 1997).

Adicionalmente al enfoque de inercia modulada,

Algoritmos de enjambres de partículas con Hendtlass (2005) propone un método denominado
estrategias para evasión de mínimos locales olas de enjambres de partículas (Waves of Swarm
Particles WoSP), con el cual se busca impulsar el
De los diferentes algoritmos de optimización enjambre para que pueda escapar de un mínimo
bioinspirados, según Bratton (2007) los algorit- local y así continuar con el proceso de explora-
mos PSO (particle swarm optimization) de en- ción. Por otro lado, Parsopoulos (2004) propone
jambres de partículas son una buena alternativa; emplear técnicas de repulsión para cada mínimo
sin embargo, tienden a presentar convergencia local encontrado, así espera evadir soluciones en-
temprana en mínimos locales (Evers, 2009; contradas previamente. Asimismo, Liang (2006)
Schutte, 2002), y adicionalmente, son suscepti- presenta una variante del algoritmo PSO deno-
bles de una mala selección de sus parámetros, tal minada aprendizaje integral, la cual consiste en
como lo muestran Hvass (2010) y Van den Bergh emplear la información histórica de las partículas
(2001). Por lo anterior, se han desarrollado mo- para actualizar su velocidad. Este enfoque busca
;/€%$%/&"!<]*&]+!#$%&"3$%+$3!!=+%$ conservar la diversidad del enjambre evitando la
evadir mínimos locales, teniendo una mejor ex- convergencia prematura.
ploración del espacio de soluciones.
Finalmente, entre los algoritmos de optimización
Una estrategia general para el escape de mínimos que emplean el concepto de vorticidad se encuen-
locales consiste en realizar un proceso de disper- tra el presentado por Menser (2006), donde se de-
sión (explosión), luego de tener una convergencia sarrolla un algoritmo basado en el comportamien-
a un mínimo local. Un ejemplo de este concepto #&;!+"4+/;&!"+"+\/;!*&‰;*!"$Š!XY|!#!
se pueden apreciar en el trabajo de Mesa (2010) se le denomina Particle Swirl Algorithm (PSA).
con el algoritmo de optimización Supernova, en |+"„+!!\]3!$!3%&"%!]#&;!`&*#/%/;$;A;/€!-
el trabajo de Krishnanand (2009) para el algorit- re de la propuesta realizada en este documento,
mo de optimización Glowworm y en el trabajo de donde se busca emplear el concepto de vorticidad
Passino (2005) con el algoritmo de optimización para lograr que el enjambre de partículas escape
basado en forrajeo de bacterias. de un mínimo local y de esta forma pueda conti-
nuar el proceso de búsqueda. Un primer trabajo
En particular, para el algoritmo PSO una prime- donde se plantea un algoritmo de optimización
*$ \&;/€%$%/{" %&"/#! !" $;/%/&"$* +" '$%#&* basado en comportamiento de enjambres con ca-
de inercia modulada tal como lo proponen Feng *$%#!*‹#/%$;!`&*#/%/;$;!!3;! ]/#/$‰^_HQXA
(2007) y Yin (2009). Con este enfoque se busca quien no considera la búsqueda individual para
controlar la exploración del algoritmo sobre el es- mejorar las características de exploración el en-
pacio de búsqueda. Los citados autores exponen jambre. Con anterioridad este mismo concepto
que un factor grande de inercia acelera la conver- fue empleado para la planeación de trayectorias
gencia mientras que un valor pequeño mejora la de robots móviles (Espitia, 2011a, 2011b).

26 Tecnura Vol. 18 No. 42 octubre - diciembre de 2014

 investigación
METODOLOGÍA G a N
G G
Fint ,i = 
N
( r  r )
i j (5)
La metodología empleada para el desarrollo del j =1
algoritmo de optimización consiste, en primera G
instancia, en la selección y revisión de un mode- En este modelo R corresponde al centro de masa
lo de enjambre de partículas, seguida por su res- del enjambre. La información del ambiente (en
pectivo análisis matemático. Después se realiza este caso la función objetivo) está dada por Uesp
la propuesta del algoritmo y por último se valida La fuerza sobre cada partícula que se produce por
con funciones de prueba ampliamente conocidas el potencial Uesp se encuentra dada por la ecuación
en la literatura. (6).
G G
Fesp ,i = k f  iU esp (ri ) (6)
MODELO EMPLEADO
Donde Kf!+"$%&"#$"#!„+!]&";!*$3$/"4+!"-
El modelo seleccionado para realizar la propuesta cia de la función objetivo.
del algoritmo de optimización se basa en la forma
de locomoción de zooplancton Daphnia (Ebeling,
2006). Con este modelo se busca aprovechar el Análisis del enjambre de partículas
comportamiento de vorticidad, ya que tal como
lo muestra Abdel (2008) esta puede ser una buena El algoritmo propuesto utiliza dos tipos de com-
estrategia para evadir mínimos locales. El modelo portamiento. El primero corresponde a movi-
seleccionado se encuentra dado por las ecuacio- mientos de traslación del enjambre hacia un pun-
nes (1) y (2). to (óptimo) y el segundo a un comportamiento
G de vorticidad. La estrategia principal consiste en
dri G lograr la convergencia del enjambre a un estado
= vi (1)
dt de equilibrio (posiblemente un mínimo) con ve-
locidad baja y, una vez que se ha encontrado un
G
dvi G G G mínimo, se incrementa la fuerza de propulsión
mi = Fpro ,i  Fint ,i  Fesp ,i (2) para lograr un comportamiento de vorticidad, au-
dt mentando así la dispersión. Este comportamiento
G se espera que proporcione buenas capacidades de
La ecuación (1) permite establecer la posición ri
exploración y que permita que el enjambre escape
G la i-ésima partícula conociendo su velocidad
de
de mínimos locales. El parámetro autopropulsión
vi . La ecuación (2) relaciona la velocidad de las
Ž se utiliza para cambiar el comportamiento de
partículas con las fuerzas presentes sobre esta.
enjambre y se considera como una función del
tiempo, de tal manera que 0(tX max . Para
La fuerza de autopropulsión considerada corres-
el siguiente análisis se presentan dos casos extre-
]&";!$3$!%+$%/{"‰QXY
mos; estos son: (t)=0 y (t)= max.
G G
F pro ,i = (   || vi || 2 )vi ‰QX
Análisis de energía
La fuerza de interacción de las partículas está
dada por la ecuación (4). Siendo Ki y Ui la energía cinética y potencial de la
G G G i-ésima partícula, respectivamente. Estas cantida-
Fint ,i = a (ri  R) (4) des están dadas por la ecuación (7).

Algoritmo de optimización basado en enjambres de partículas con comportamiento de vorticidad y búsqueda individual y grupal 27


      
investigación
1 G G 
N
G 2 G
E = ( max   vi ) vi
2
K i = mi || vi ||2 U i = U int (ri ) (11)
2 (7) i =1
G
 k f U esp (ri ) Si T=0, el sistema permanece en un estado de
G
energía constante. Con vi = 0 las partículas
La energía total de la i‘’/\$]$*#‹%+3$!;!€"! deben encontrarse estáticas, en tanto que con
G
como Ei=Ki+Ui y la energía total del enjambre ET vi =  max / se logra el movimiento del en-
corresponde a la suma de la energía total de todas las jambre con energía constante. Finalmente, al in-
partículas. Tomando la derivada de tiempo de la ener- crementar max se aumenta la velocidad máxima
gía total de cada partícula se tiene la ecuación (8). de las partículas y por lo tanto hay una mayor dis-
G 2 G persión del enjambre.
E i = ( (t )   vi ) vi
2

G G G G (8)
 a (ri  R)ri  R Puntos de equilibrio

Mediante la adición de las contribuciones de cada Los puntos de equilibrio se pueden establecer con
G
partícula y empleando la igualdad (rGi  R) = 0 ,
N
3$!%+$%/&"!‰H^X<‰HQXY
entonces se tiene la ecuación (9). i =1 G
dri
N N
G 2 G =0 (12)
E T = E i = ( (t )   vi ) vi
2
(9) dt
i =1 i =1
G
A partir de la ecuación (9) es posible obser- dvi
mi =0 ‰HQX
var que un estado constante de energía (ET=0) dt
G G 2 G
se logra cuando vi = 0 o con vi = α (t ) / β . Por consiguiente, se tiene vi = 0 y la ecuación
Se consideran particularmente dos casos para (14).
(t): (i) (t)=0 y (i) (t)=max, donde max es un
G
valor positivo grande acotado. En el primer caso 0 = (−α + β || vi ||2 )vi
el enjambre converge a un punto de equilibrio, (14)
mientras que en el segundo caso el enjambre pre- a N
G G G
senta un comportamiento de vorticidad. −
N
∑ ( r − r ) − k ∇U
j =1
i j f |
G
esp ri

En el primer caso (i), con (t)=0, de la ecuación G

Considerando vi = 0 , la ecuación (14) se reduce
(9) se tiene la ecuación (10).
a la condición de equilibrio dada por la ecuación


N
G 2 G (15).
E =  (  v i ) v i
2
(10)
i =1 G G kf G
ri = R  U esp |rG (15)
Dado que la energía del sistema tiene derivada en a i
!3#/!\]&;!€"/;$"!@$#/`$]$*$#&;&vi0, el siste-
G G
ma tiende a un estado de energía mínima con vi = 0. En laG ecuación (15) si U esp |rG = 0 entonces
G i
G
ri = R , por lo tanto, el enjambre converge a un
En el caso (i), el parámetro (tX!€Š$!"+"`$3&* mínimo local. En otros casos cuando  U |
esp ri
G  0,
grande, pero acotado max tal que se tiene la ecua- se logra un equilibrio en función de la posición de
ción (11). las partículas y la función objetivo.

28 Tecnura Vol. 18 No. 42 octubre - diciembre de 2014

 investigación
SIMULACIÓN DEL MODELO ESTRATEGIA DE BÚSQUEDA BASADA
EN DISPERSIÓN
&"!3€";!&=!*`$*3$%$*$%#!*‹#/%$;!3\&-
delo se realiza un conjunto de simulaciones con Con la estrategia propuesta se espera tener una
un potencial parabólico Uesp= 0.5(x2+y2) y pará- exploración adecuada del espacio de búsqueda,
metros Kf=1, mi=1, a=1, N=20 y •HA%&"Ž/@+$3 de tal forma que después de encontrar un mínimo
a 4 y 9Y "3$€@+*$H!]*!!"#$"3&*!+3#$;& local se pueda escapar de este para seguir el pro-
para 200 iteraciones y condiciones iniciales alea- %!&;!=ƒ„+!;$Y&"!3€";!3&@*$*3&$"#!*/&*
torias para la posición. se propone aumentar la energía de propulsión del
!"Š$\=*!Ž%+$";&!$3%$"˜$+"\‹"/\&3&%$3A<
#$ €@+*$ \+!#*$ !3 %&\]&*#$\/!"#& ;! sólo se disminuye cuando el enjambre es capaz de
vorticidad y la magnitud de la velocidad de las escapar de este punto.
G
partículas, la cual tiende a ser | vi | = / .
–$*$Ž•—!#/!"!"3$€@+*$$<=\/!"#*$„+! La propuesta de búsqueda emplea el comporta-
]$*$Ž•K!#/!"!"3$€@+*$%<;Y miento de vorticidad como un mecanismo de

Figura 1. Distribución de las partículas y magnitud de velocidades.

Fuente: elaboración propia.

Algoritmo de optimización basado en enjambres de partículas con comportamiento de vorticidad y búsqueda individual y grupal 29


      
investigación
dispersión para lograr una búsqueda global. En la tal se detiene el algoritmo, considerando para esto
€@+*$^!]+!;!$]*!%/$*!3;/$@*$\$;!4+Š&]$*$ una dispersión máxima de las partículas sobre el
la estrategia de búsqueda propuesta. En un pri- espacio de búsqueda.
mer lugar se inicializa el enjambre y se procede a
encontrar el mínimo local más cercano almace- Para lograr lo anterior el algoritmo presenta tres
nando el valor del mínimo encontrado. Posterior- etapas:
mente, para lograr que el enjambre escape del
mínimo encontrado, se realiza el proceso de dis- 1. Convergencia de búsqueda grupal: en esta
persión, empleando para esto el comportamiento etapa el algoritmo converge al punto de equi-
de vorticidad. Con el anterior proceso, mediante librio de las partículas, el cual puede ser el
la búsqueda grupal e individual se espera encon- mínimo local más cercano. En esta etapa el
trar un valor mínimo menor al encontrado previa- comportamiento del enjambre está dado por
mente. En caso de que no se encuentre un valor la función objetivo, observando para esto la
posición media del enjambre.

2. Dispersión y búsqueda: cuando el enjambre

encuentra un mínimo local se realiza el proce-
so de dispersión, buscando tener movimien-
tos circulares de las partículas. En esta misma
etapa se realiza la búsqueda de un mejor valor
al encontrado previamente. Esta búsqueda se
realiza tanto individual como grupalmente.
En el caso de que se encuentre un mejor valor
grupal o individual, se procede a realizar la
respectiva convergencia.

QY Convergencia de búsqueda individual: en este

caso una de las partículas encuentra un mejor
valor, por lo cual el potencial de la función
objetivo se reemplaza por un potencial de
atracción hacia el mejor punto encontrado, de
tal forma que el enjambre pueda converger a
este punto.

Valor mínimo individual y grupal

&"!3€";!!#$=3!%!*3$'$!;!3$3@&*/#\&!
considera el valor mínimo encontrado por la posi-
ción media de las partículas UminG y un valor míni-
mo dado por la mejor posición de las partículas de
forma individual UminP. Estos valores se determi-
nan considerando la función objetivo Uobj.

Figura 2. Esquema propuesto para el proceso de El mejor valor del grupo se determina conocien-
búsqueda
G
do el promedio de las posiciones del enjambre R
Fuente: elaboración propia. mediante las ecuaciones (16) y (17).

30 Tecnura Vol. 18 No. 42 octubre - diciembre de 2014

 investigación
G 1 G
N Incremento de energía
R=
N
rj
j =1 La adición de energía se realiza mediante el factor
G G de propulsión, el cual está dado por la ecuación (20).
⎪⎧U obj ( R), si U minG ≥ U obj ( R);
U minG =⎨ G G
si U minG < U obj ( R). (17) ⎧ dα
⎩⎪U minG , ⎪ = g (t ), si U minG ≥ U obj ( R );
⎨ dt G (20)
La mejor posición de la partícula está dada por la ⎪α = 0, si U minG < U obj ( R).
⎩
evaluación de cada partícula de la ecuación (18).
Para la función g(t) se considera un tiempo Ta
G
⎧U obj (ri ), si U minP ≥ U obj (ri ); asociado al incremento de energía y un tiempo Te
U minP =⎨ (18)
para la espera, momento en el cual las partículas
⎩U minP , si U minP < U obj (ri ).
se dispersan de forma circular sobre el espacio



 
 de búsqueda. El número total de iteraciones que
toma este ciclo es Ta+Te, donde se emplea la varia-
–$*$/;!"#/€%$*3$'$!!"3$%+$3!!"%+!"#*$!3 ble cont para realizar la cuenta de las iteraciones.
algoritmo existen las siguientes condiciones: La función g(t) está dada por la ecuación (21).

1. Convergencia G de búsqueda grupal: ⎧τ , si 0 ≤ cont < Ta ;

g (t ) = ⎨ c (21)
U minG  U obj (R) . En este caso =0 y Uesp ⎩α , si Ta ≤ cont < Ta + Te .
corresponde al potencial de la función objeti-
vo Uobj. Con la anterior estrategia se espera que la energía
G de propulsión aumente hasta que las partículas
2. Dispersión: U minG  U obj (R) . En este caso se logren evadir el mínimo local. El aumento de la
incrementa la energía mediante (t) y Uesp co- energía está dado por el parámetro c, el cual co-
rresponde al potencial de la función objetivo rresponde a la tasa con la cual se incrementa la
Uobj. energía de autopropulsión.

QY Convergencia de búsqueda G individual:

Criterio de parada del algoritmo
UminP minG y UminGUobj (R ) . En este caso
=0 y Uesp corresponde a un potencial cuadrá-
Como se ha mencionado previamente, el algorit-
tico asociado a la mejor posición encontrada.
mo utiliza la dispersión para escapar de mínimos
3&%$3!<!š]3&*$*;!\$"!*$!€%/!"#!!3!]$%/&
Función objetivo de búsqueda. Por lo tanto, el nivel de dispersión
se emplea como criterio de parada del algoritmo.
G
Considerando que rind es la mejor posición Considerando lo anterior, el criterio de parada
encontrada por algún individuo, entonces Uesp se propuesto establece que si el número de partícu-
puede determinar con la ecuación (19). las en el espacio de búsqueda es menor que un
`$3&*!]!%‹€%&A!"#&"%!!3$3@&*/#\&!;!#/!"!Y
G
⎧⎪k F || rind ||2 , si U minP ≥ U minG y
U esp =⎨ G Implementación del algoritmo
⎪⎩U obj (ri ), otrocaso.
(19)
G Para implementar el modelo dinámico del enjam-
U minG ≤ U obj ( R); bre en el algoritmo, las ecuaciones diferenciales

Algoritmo de optimización basado en enjambres de partículas con comportamiento de vorticidad y búsqueda individual y grupal 31


      
investigación
se convierten a tiempo discreto considerando un
⎧⎪α [n + 1] = α [n] + g[n]Δt ,
intervalo de tiempo
, de tal forma que se tienen ⎨
3$!%+$%/&"!‰^^X<‰^QXY ⎪⎩α [n + 1] = 0,
G G G G (24)
ri [n + 1] = ri [n] + vi Δt (22) si U minG ≥ U obj ( R);
G
G G si U minG < U obj ( R).
vi [n + 1] = vi [n − 1]
G G G ‰^QX Finalmente, el algoritmo de optimización pro-
+ ( Fpro ,i + Fint ,i + Fobj ,i )Δt / mi ]+!#&!]+!;!$]*!%/$*!"3$€@+*$QY

3%[3%+3&;!Ž!"#/!\]&;/%*!#&!*!$3/˜$%&" ANÁLISIS CUALITATIVO DEL

la ecuación (24). ALGORITMO
Algoritmo 1: Algoritmo propuesto de optimización VPSO.
1 Inicializar el enjambre, posiciones aleatorias y velocidad cero.; De los diferentes parámetros involucrados en el
2 begin algoritmo de optimización se puede hacer la si-
3 while Bajo algún criterio de finalización. Número de iteraciones o depresión. do
JG
4 Establecer la posición media del enjambre R empleando la ecuación 16; guiente descripción:
5 Calcular UminG y UminP ecuaciones 17 y 18;
6 Establecer la fase de algoritmo;  : Factor de frenado de las partículas. Al au-
7 Determinar empleando la expresión 24;
8 for i = 1 hasta N do mentar, las partículas tienden a ir más lento.
9 Calcular la nueva posición de las partículas con la ecuación 22;
10 Calcular la nueva velocidad de las partículas empleando la ecuación 23;
 ŽžŸ$%#&*;!]*&]+3/{"Y|3/"%*!\!"#$*!A3$
11 end
12 Pasar a la siguiente iteración. partículas aumentan su energía cinética, ele-
13 end
14 Establecer el valo óptimo encontrado por las partículas.
vándose de esta forma su velocidad.
15 end
 a: Factor de interacción. Al aumentar, el en-
Figura 3. Algoritmo de optimización propuesto jambre de partículas tiende a unirse más y al
Fuente: elaboración propia. disminuir se dispersan más.
a) Iteración: 1 b) Iteración: 30

c) Iteración: 84 d) Iteración: 174 e) Iteración: 230

Figura 4. Representación gráfica del funcionamiento del algoritmo en un potencial parabólico

Fuente: elaboración propia.

32 Tecnura Vol. 18 No. 42 octubre - diciembre de 2014

 investigación
 Kf: Factor de ponderación de la función ob- '+"%/{"#/!"!+"\‹"/\&@3&=$3!"‰_AHHQA‘QA^ K¡XA
jetivo. Al incrementarse, las partículas con- %+<& `$3&* ! ‘QA—Q — #$ '+"%/{" ;! ]*+!=$ !
vergen rápidamente a un mínimo local, y al encuentra descrita por la ecuación (25).
disminuir, estas se pueden mover, sobre todo
el espacio de búsqueda. Peaks: esta función tiene dos mínimos locales
y un mínimo global en (0,2282,-1,6199) que es
Para mostrar el funcionamiento del algoritmo igual a -6,4169. La ecuación (26) describe esta
se realiza una simulación, considerando un po- función de prueba.
tencial cuadrático de la forma Uobj=2(x2+y2). En 2 + ( y +1)2 )
3$ €@+*$ — ! ]+!;! $]*!%/$* !3 ]&#!"%/$3 < 3$ U obj ,2 = 3(1 − x) 2 e − ( x
evolución que tiene la posición de las partícu- ⎛x ⎞ 2 2 1 2 2 (26)
−10 ⎜ − x3 − y 5 ⎟ e − ( x + y ) − e − (( x +1) + y )
las en la medida que pasan las iteraciones. Es de ⎝5 ⎠ 3
apreciar que luego de encontrar el mínimo local,
Rastrigins: esta función representa un problema
las partículas inician el proceso de dispersión rea-
bastante difícil debido a su gran número de lo-
lizando un movimiento circular.
cales mínimos y máximos. El mínimo global se
encuentra en (0,0) con un valor de 0. Esta función
RESULTADOS se encuentra dada por la ecuación (27).

Para ilustrar el desempeño del algoritmo pro-

U obj,3 = 0,1(20 + ( x 2 − 10 cos(2π x)
(27)
puesto se considera un conjunto de funciones de + y 2 − 10 cos(2π y )))
prueba de 2 dimensiones, las cuales se pueden ob-
Circles: esta función presenta varios círcu-
servar en Passino (2002) y Krishnanand (2009).
los concéntricos como regiones de máximos y
"3$€@+*$ !]+!;!$]*!%/$*3$*!]*!!"#$%/{"
mínimos locales. El mínimo global se encuentra
@*[€%$;!3$'+"%/&"!&=Š!#/`&!\]3!$;$Y
en (0,0) con un valor de 0. La ecuación (28) des-
cribe esta función de prueba.
Passino: esta función de prueba es una adaptación
de la presentada en Passino (2002). En este caso la U obj,4 = ( x 2  y 2 )0,25
(28)
U obj ,1 = 5e −0 ,8(( x )2 + ( y −1, 7)2 ) ((sin (50( x 2  y 2 )0,1 )) 2  1, 0)
2 + ( y − 0)2 ) Equal Peaks: esta función tiene varios mínimos
− 2e −0,64(( x −1,7) con un valor de 0 y situados periódicamente en
2 2
+3e −0,64(( x −3,3) + ( y +1,7) ) x y y. Esta función se encuentra descrita por la
2 2 ecuación (29).
+ 2e −0,8(( x +1,7) + ( y +1,7) )
2 2 U obj,5 = cos( x) 2  sin ( y ) 2
−2e −4(( x +3,3) + ( y +1,7) ) (29)
2 2 (25) Himmelblaus: consiste en una adaptación de la
− 4e −0,8(( x −0) + ( y +3,3) )
2 2 función representada en Krishnanand (2009),la
−2e −4(( x + 2,3) + ( y −3,3) ) cual tiene cuatro mínimos con valor de -2
2 2
− 2e −4(( x − 2,0) + ( y −3,3) ) situados en (-1,5616,2,29260), (2,5616,2,1068),
2 2 (2,5615,-2,1068) y (1,5616,-29260). La ecuación
+2e −4(( x −3,3) + ( y −0,3) ) ‰Q_X;!%*/=!!#$'+"%/{";!]*+!=$Y
2 2
+ 2e −4(( x +3,3) + ( y + 0,3) ) U obj,6 = −0, 01(200 − ( x 2 + y 2 − 11) 2
‰Q_X
0, 05( x  y )
2 2
− ( x + y 2 − 7) 2 )

Algoritmo de optimización basado en enjambres de partículas con comportamiento de vorticidad y búsqueda individual y grupal 33


      
investigación
Para la ejecución del algoritmo se toma: mi=1, ]$*$ %$;$ %&"Š+"#& ;! %&"€@+*$%/&"!Y ¤$
=1, max=20 y
 0,1. El rango del espacio tabla 1 muestra los valores máximos y mínimos
;! =ƒ„+!;$ %&"/;!*$;& ! ‰‘£ x £X < encontrados durante el proceso de optimización
‰‘£ y £XY ¤$ %&";/%/&"! /"/%/$3! ;! 3$ (mejores y peores resultados), el valor medio y
partículas son aleatorias en posición y cero en la desviación estándar (STD) de los resultados.
`!3&%/;$;Y ¥& %&"€@+*$%/&"! ;! ]$*[\!#*& También se aprecia el número de iteraciones
consideradas son: Set 1 a=1, Kf=1; Set 2 a=0,5, empleadas por el algoritmo con cada función de
Kf•_A Y –&* ƒ3#/\&A ! *!$3/˜$" Q_ !Š!%+%/&"! prueba.

Figura 5. Funciones objetivo en 2D

Fuente: elaboración propia.

Tabla 1. Resultados para 30 ejecuciones

Configuración Set 1 Set 2

Función 1 Valor Iteraciones Valor Iteraciones
Máximo 0,361 383 0,3751 447
Mínimo -3,4354 178 -3,4353 175
Promedio -2,4562 289,9 -2,508 283,7
STD 1,0601 52,6 1,1156 71,5
Función 2 Valor Iteraciones Valor Iteraciones
Máximo -2,7524 754 0,2263 518
Mínimo -6,4168 168 -6,4164 135
Promedio -5,2747 431,1 -3,775 283,3
STD 1,6175 162,9 2,1602 90,6

34 Tecnura Vol. 18 No. 42 octubre - diciembre de 2014

 investigación
Configuración Set 1 Set 2
Función 3 Valor Iteraciones Valor Iteraciones
Máximo 0,754 681 1,2772 609
Mínimo 0,00008 157 0,0191 150
Promedio 0,2207 378,8 0,31 304,8
STD 0,1997 153,5 0,3483 99,5
Función 4 Valor Iteraciones Valor Iteraciones
Máximo 1,7705 795 1,559 745
Mínimo 0,0661 169 0,2213 123
Promedio 0,62 427,7 0,8181 283
STD 0,412 193,5 0,2875 127,1
Función 5 Valor Iteraciones Valor Iteraciones
Máximo 0,011 537 1,5746 772
Mínimo 0,0000057 212 0,000237 70
Promedio 0,0036 315,5 0,1066 284
STD 0,0037 73,3 0,312 124,8
Función 6 Valor Iteraciones Valor Iteraciones
Máximo -1,8839 559 -1,5351 693
Mínimo -2 222 -1,9999 165

Promedio -1,9913 340,7 -1,9441 358,9

STD 0,0221 89,5 0,113 104,8

Fuente: elaboración propia.

CONCLUSIONES En los resultados de la tabla 1 se puede apreciar

que hay un mejor desempeño del algoritmo para
El modelo empleado fue seleccionado buscando 3$ ]*/\!*$ %&"€@+*$%/{" ;! ]$*[\!#*& ‰!# HXY
tener una expresión compacta con pocos térmi- Adicionalmente, en estos resultados se observa
nos y que permita describir comportamientos que en promedio el mayor número de iteracio-
de enjambre como desplazamientos uniformes y "!!!"%+!"#*$!"!#$\/\$%&"€@+*$%/{";!
movimientos circulares, los cuales se observan en parámetros. También es de notar que en la ma-
diferentes grupos de seres vivos. yoría de la funciones objetivo el algoritmo logra
encontrar el mínimo global.
El algoritmo propuesto es un proceso de optimiza-
ción basado en un comportamiento emergente que En particular la función objetivo Circles resulta de
utiliza la vorticidad de un enjambre de partículas interés, debido a la simetría circular que presenta,
para mejorar las capacidades de búsqueda y esca- 3&%+$3]+!;!;/€%+3#$*!3!%$]!;!3$]$*#‹%+3$
par de los mínimos locales. Los resultados que se de los mínimos locales. En la tabla 1 se puede ob-
]*!!"#$"\+!#*$"3$!€%$%/$;!3$!#*$#!@/$]*&- servar que para esta función objetivo el algoritmo
puesta, donde el enjambre fue capaz de evitar los emplea el mayor número de iteraciones.
mínimos locales y encontrar una solución global
(aproximada) de las funciones propuestas.

Algoritmo de optimización basado en enjambres de partículas con comportamiento de vorticidad y búsqueda individual y grupal 35


      
investigación
FINANCIAMIENTO AGRADECIMIENTO

3 €"$"%/$\/!"#& ;!3 ]*!!"#! ]*&<!%#& ! !"- ¤& $+#&*! \$"/€!#$" + $@*$;!%/\/!"#& $ 3$
cuentra en el marco del proyecto con código Universidad Distrital Francisco José de Caldas
H£QQ^;!3$¥/*!%%/{";!"`!#/@$%/{"!;!?&- y a la Universidad Nacional de Colombia por el
gotá - Universidad Nacional de Colombia. apoyo en el desarrollo de este trabajo.

REFERENCIAS

Abdel, M. y McInnes, C., “Wall Following to Es- chanics and its ApplicationsAª&3YQH—A«&Y
cape Local Minima for Swarms of Agents 1-4, 2002, pp. 92-96.
Using Internal States and Emergent Beha-
vior”, International Conference of Com- Erdmann, U., Ebeling, W. y Mikhailov, A., “Noi-
putational Intelligence and Intelligent se-Induced Transition from Translational
Systems ICCIIS, 2008. to Rotational Motion of Swarms”, Physical
Review E, Vol. 71, No. 5, 2005.
Bajec, I. y Heppner, F., “Organized Flight in
Birds”, Animal Behaviour, Vol. 78, No. 4, Espitia, H. y Sofrony J., “Path Planning of Mobile
2009, pp. 777-89. Robots Using Potential Fields and Swarms
of Brownian Particles”, IEEE Congress on
Berg H., Random Walks in Biology, Princeton Evolutionary Computation (CEC), 2011,
…"/`!*/#<–*!AHKOQY ]]YH^Q‘H^KY

?*$##&"A¥Y<¨!""!;<AYA©¥!€"/"@$#$";$*; Espitia H. y Sofrony J., “Vortex Particle Swarm

for Particle Swarm Optimization”, Procee- Optimization”, IEEE Congress on Evolu-
dings of IEEE Swarm Intelligence Sympo- tionary Computation (CEC)A^_HQY
sium SIS, 2007.
Espitia, H., Sofrony, J. y González C., “Vortex
Çengel, Y.,   , McGraw-Hill, Swarm Path Planning Algorithm”, IEEE
^__QY Electronics, Robotics and Automotive
Mechanics Conference (CERMA), 2011,
Couzin, I., Krause, J., Franks, N. y Levin, S., pp. 184-90.
“Effective Leadership and Decision Ma-
king in Animal Groups on Themove”, Let- Evers, G., An Automatic Regrouping Mechanism
ters to NatureAª&3Y—QQA^__ A]]Y HQ‘H£Y to Deal with Stagnation in Particle Swarm
Optimization (Master Thesis), University
D’Orsogna, M., Chuang, Y., Bertozzi, A. y Cha- of Texas-Pan American, 2009.
yes, L., “Self-Propelled Particles with Soft-
Core Interactions: Patterns, Stability, and Feng, C., Cong, S. y Feng, X., “A New Adaptive
Collapse”, Physical Review Letters, Vol. Inertia Weight Strategy in Particle Swarm
96, 2006. Optimization”, IEEE Congress on Evolu-
tionary Computation (CEC), 2007.
Ebeling, W. y Erdmann, U., “Nonequilibrium
Statistical Mechanics of Swarms of Dri- García, J. y Alba, E., “Restart Particle Swarm
ven Particles”, Physica A: Statistical Me- Optimization with Velocity Modulation: A

36 Tecnura Vol. 18 No. 42 octubre - diciembre de 2014

 investigación
Scalability Test”, Springer, Soft Computing Particle Swarm Optimization”, IEEE Tran-
- A Fusion of Foundations, Methodologies sactions on Evolutionary Computation,
and Applications, Vol. 1, 1997. Vol. 8, 2004.

García, R., Moss, F., Nihongi, A., Strickler, R., Passino, K., “Biomimicry of Bacterian Foragin
Göller, S., Erdmann, U., Schimansky, L. for Distributed Optimization and Control”,
y Sokolov, I., “Optimal Foraging by Zoo- IEEE Control Systems Magazine, 2002.
plankton within Patches: The Case of Da-
phnia”, Elsevier, Mathematical Bioscien- Passino, K., Biomimicry for Optimization, Con-
ces, Vol. 2, 2007, pp. 165-88. trol, and Automation, Springer-Verlag,
London, UK, 2005.
Hendtlass, T., “A Particle Swarm Algorithm for
High Dimensional, Multi-Optima Problem Schutte, J., Particle Swarms in Sizing and Global
Spaces”, IEEE Swarm Intelligence Sympo- Optimization (Master’s Dissertation), Uni-
sium, 2005. versity of Pretoria, 2002.

Hvass, M., Tuning & Simplifying heuristical Sumpter, D., “The Principles of Collective Ani-
optimization (Ph.D. Thesis), University of mal Behaviour”, Philosophical Transac-
Southampton, UK, 2010. tions of the Royal Society BAª&3YQ£HA«&Y
1465, 2006, pp. 5-22.
Krishnanand, K. y Ghose, D., “Glowworm Swarm
Optimization for Simultaneous Capture Van den Bergh, F., An Analysis of Particle Swarm
of Multiple Local Optima of Multimodal Optimizers (PhD. Thesis), University of
Functions”, Springer Science, Swarm Inte- Pretoria, Pretoria, 2001.
lligenceAª&3YQA«&Y^A^__KA]]YO¡‘H^—Y
Vicsek T., “Universal Patterns of Collective Mo-
Levine, H., Rappel, W. y Cohen, I., “Self-Organiza- tion from Minimal Models of Flocking”,
tion in Systems of Self-Propelled Particles”, Second IEEE International Conferen-
Physical Review EAª&3Y£QA«&YHA^___Y ce on Self-Adaptive and Self-Organizing
Systems, 2008.
Liang, J., Qin, A., Suganthan, P. y Baskar, S.,
“Comprehensive Learning Particle Swarm Vicsek, T., Czirók, A., Ben, E., Cohen, I. y Sho-
Optimizer for Global Optimization of Mul- chet, O., “Novel Type of Phase Transition
timodal Functions”, IEEE Transactions on in a System of Self-Driven Particles”, Phy-
Evolutionary Computation, Vol. 10, 2006. sical Review Letters, Vol. 75, No. 6, 1995.

Menser, S. y Hereford, J., “A New Optimization Yin, L. y Liu, X., “A PSO Algorithm Based on
Technique”, Proceedings of the IEEE Digi- Biology Population Multiplication (PMP-
!"#, 2006. SO)”, Proceedings of the Second Sympo-
sium International Computer Science and
Mesa, E., Supernova: un algoritmo novedoso de Computational Technology (ISCSCT ’09),
optimización global (tesis de maestría), 2009.
Universidad Nacional de Colombia, Sede
Medellín, 2010. Zhang, H., Chen, M., Stan, G., Zhou, T. y Ma-
ciejowski, J., “Collective Behavior Coordi-
Parsopoulos, K. y Vrahatis, M., “On the Com- nation with Predictive Mechanisms”, IEEE
putation of all Global Minimizers through Circuits and Systems Magazine, 2008.

Tecnura Vol. 18 No. 42 pp. 24 - 37 octubre - diciembre de 2014 37