Printer Friendly

Algoritmo de optimizacion basado en enjambres de particulas con comportamiento de verticidad y busqueda individual y grupal.

Vortex Particle Swarm Optimization with Individual and Group Search

INTRODUCCION

La descripcion del comportamiento de muchos seres vivos se caracteriza por presentar movimiento cooperativo coordinado, tal como bandadas de aves, cardumenes de peces e incluso microorganismos. Uno de los comportamientos de interes consiste en el movimiento circular de particulas alrededor de un punto denominado vortice (Ebeling, 2002), ya que esta forma de locomocion puede ser una buena estrategia para la busqueda de alimento y evasion de obstaculos y depredadores (Garcia, 2007). Por las anteriores caracteristicas estos comportamientos pueden ser empleados en la propuesta de algoritmos de optimizacion.

Comportamientos de enjambres

En la naturaleza se pueden apreciar diferentes comportamientos los cuales han sido estudiados y representados de forma analitica. En particular, las congregaciones de individuos son una tematica interesante por los comportamientos emergentes que surgen (Sumpter, 2006). Entre los trabajos que se pueden resaltar se encuentra el presentado por Vicsek (1995), donde se desarrolla un modelo basico para representar un enjambre de individuos. Este ultimo autor lleva a cabo una extension de su trabajo (Vicsek, 2008), donde describe algunos patrones representativos de los enjambres. Por otro lado, Sumpter (2006) hace una revision del comportamiento colectivo para la formacion de enjambres observando propiedades de autorregulacion y principios de comportamiento colectivo como: integridad, variabilidad, realimentacion positiva, realimentacion negativa, umbrales de respuesta, direccion, inhibicion, redundancia, sincronizacion y egoismo.

Sobre los diferentes enfoques considerados para modelos de enjambres, Couzin (2005) analiza el efecto que tiene el liderazgo de un individuo, Bajec (2009) considera las diferentes formas de organizacion que presentan las aves y Zhang (2008) observa el efecto que tiene incorporar mecanismos de prediccion en un modelo de enjambre.

Modelos de particulas con comportamiento de vorticidad

La vorticidad es un comportamiento que se presenta con frecuencia en los fluidos y se debe al acoplamiento que existe entre las fuerzas inerciales y las fuerzas viscosas (numero de Reynolds [Berg, 1983]). El analisis de este comportamiento se realiza mediante las ecuaciones de Navier Stokes, las cuales suelen ser dificiles de resolver de forma analitica en casos generales (Cengel, 2003). El comportamiento de vorticidad se caracteriza por el movimiento de forma rotacional de particulas alrededor de un punto, el cual se denomina vortice. Ademas de los fluidos, este tipo de comportamiento se presenta en enjambres de individuos como peces, aves y bacterias, entre otros. Existen dos modelos que son los mas empleados para representar este comportamiento, uno consiste en el modelo de particula autopropulsada (Levine, 2000; D'Orsogna, 2006) y el otro corresponde al de particula activa browniana (Ebeling, 2006). Este ultimo, a diferencia del primero, considera una componente estocastica. Por lo general, estos modelos suelen emplear potenciales de Morse para representar la interaccion entre individuos; sin embrago, en el trabajo de Erdmann (2005) se puede observar un modelo que emplea un potencial parabolico.

Algoritmos de enjambres de particulas con estrategias para evasion de minimos locales

De los diferentes algoritmos de optimizacion bioinspirados, segun Bratton (2007) los algoritmos PSO (particle swarm optimization) de enjambres de particulas son una buena alternativa; sin embargo, tienden a presentar convergencia temprana en minimos locales (Evers, 2009; Schutte, 2002), y adicionalmente, son susceptibles de una mala seleccion de sus parametros, tal como lo muestran Hvass (2010) y Van den Bergh (2001). Por lo anterior, se han desarrollado modificaciones y propuestas con las cuales se busca evadir minimos locales, teniendo una mejor exploracion del espacio de soluciones.

Una estrategia general para el escape de minimos locales consiste en realizar un proceso de dispersion (explosion), luego de tener una convergencia a un minimo local. Un ejemplo de este concepto se pueden apreciar en el trabajo de Mesa (2010) con el algoritmo de optimizacion Supernova, en el trabajo de Krishnanand (2009) para el algoritmo de optimizacion Glowworm y en el trabajo de Passino (2005) con el algoritmo de optimizacion basado en forrajeo de bacterias.

En particular, para el algoritmo PSO una primera modificacion consiste en adicionar un factor de inercia modulada tal como lo proponen Feng (2007) y Yin (2009). Con este enfoque se busca controlar la exploracion del algoritmo sobre el espacio de busqueda. Los citados autores exponen que un factor grande de inercia acelera la convergencia mientras que un valor pequeno mejora la capacidad de busqueda. Una modificacion adicional del algoritmo PSO consiste en reiniciarlo cuando se considera que hay un estancamiento de este (Garcia, 1997).

Adicionalmente al enfoque de inercia modulada, Hendtlass (2005) propone un metodo denominado olas de enjambres de particulas (Waves of Swarm Particles WoSP), con el cual se busca impulsar el enjambre para que pueda escapar de un minimo local y asi continuar con el proceso de exploracion. Por otro lado, Parsopoulos (2004) propone emplear tecnicas de repulsion para cada minimo local encontrado, asi espera evadir soluciones encontradas previamente. Asimismo, Liang (2006) presenta una variante del algoritmo PSO denominada aprendizaje integral, la cual consiste en emplear la informacion historica de las particulas para actualizar su velocidad. Este enfoque busca conservar la diversidad del enjambre evitando la convergencia prematura.

Finalmente, entre los algoritmos de optimizacion que emplean el concepto de vorticidad se encuentra el presentado por Menser (2006), donde se desarrolla un algoritmo basado en el comportamiento de un fluido en un sumidero (drenaje). A este se le denomina Particle Swirl Algorithm (PSA). Aunque emplea el concepto de vorticidad, difiere de la propuesta realizada en este documento, donde se busca emplear el concepto de vorticidad para lograr que el enjambre de particulas escape de un minimo local y de esta forma pueda continuar el proceso de busqueda. Un primer trabajo donde se plantea un algoritmo de optimizacion basado en comportamiento de enjambres con caracteristicas de vorticidad es el de Espitia (2013), quien no considera la busqueda individual para mejorar las caracteristicas de exploracion el enjambre. Con anterioridad este mismo concepto fue empleado para la planeacion de trayectorias de robots moviles (Espitia, 2011a, 2011b).

METODOLOGIA

La metodologia empleada para el desarrollo del algoritmo de optimizacion consiste, en primera instancia, en la seleccion y revision de un modelo de enjambre de particulas, seguida por su respectivo analisis matematico. Despues se realiza la propuesta del algoritmo y por ultimo se valida con funciones de prueba ampliamente conocidas en la literatura.

MODELO EMPLEADO

El modelo seleccionado para realizar la propuesta del algoritmo de optimizacion se basa en la forma de locomocion de zooplancton Daphnia (Ebeling, 2006). Con este modelo se busca aprovechar el comportamiento de vorticidad, ya que tal como lo muestra Abdel (2008) esta puede ser una buena estrategia para evadir minimos locales. El modelo seleccionado se encuentra dado por las ecuaciones (1) y (2).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (1)

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (2)

La ecuacion (1) permite establecer la posicion [[??].sub.i] de la i-esima particula conociendo su velocidad [[??].sub.i]. La ecuacion (2) relaciona la velocidad de las particulas con las fuerzas presentes sobre esta.

La fuerza de autopropulsion considerada corresponde a la ecuacion (3).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (3)

La fuerza de interaccion de las particulas esta dada por la ecuacion (4).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (4)

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (5)

En este modelo [??] corresponde al centro de masa del enjambre. La informacion del ambiente (en este caso la funcion objetivo) esta dada por [U.sub.esp] La fuerza sobre cada particula que se produce por el potencial [U.sub.esp] se encuentra dada por la ecuacion (6).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (6)

Donde [K.sub.f] es una constante que pondera la influencia de la funcion objetivo.

Analisis del enjambre de particulas El algoritmo propuesto utiliza dos tipos de comportamiento. El primero corresponde a movimientos de traslacion del enjambre hacia un punto (optimo) y el segundo a un comportamiento de vorticidad. La estrategia principal consiste en lograr la convergencia del enjambre a un estado de equilibrio (posiblemente un minimo) con velocidad baja y, una vez que se ha encontrado un minimo, se incrementa la fuerza de propulsion para lograr un comportamiento de vorticidad, aumentando asi la dispersion. Este comportamiento se espera que proporcione buenas capacidades de exploracion y que permita que el enjambre escape de minimos locales. El parametro autopropulsion [alfa] se utiliza para cambiar el comportamiento de enjambre y se considera como una funcion del tiempo, de tal manera que 0 [menor que o iqual a] [alfa](t) [menor que o iqual a] [[alfa].sub.max]. Para el siguiente analisis se presentan dos casos extremos; estos son: [alfa](t) = 0 y [alfa](t)= [[alfa].sup.max].

Analisis de energia

Siendo [K.sub.i] y [U.sub.i] la energia cinetica y potencial de la i-esima particula, respectivamente. Estas cantidades estan dadas por la ecuacion (7).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (7)

La energia total de la i-esima particula se define como [E.sub.i] = [K.sub.i] + [U.sub.i] y la energia total del enjambre [E.sub.T] corresponde a la suma de la energia total de todas las particulas. Tomando la derivada de tiempo de la energia total de cada particula se tiene la ecuacion (8).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (8)

Mediante la adicion de las contribuciones de cada particula y empleando la igualdad [EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] = o, entonces se tiene la ecuacion (9).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (9)

A partir de la ecuacion (9) es posible observar que un estado constante de energia ([E.sub.T] = 0) se logra cuando [paralelo][[??].sub.i][paralelo] = 0 o con [[paralelo]vi[paralelo].sup.2] = [alfa](t)/[beta] . Se consideran particularmente dos casos para [alfa](t): (i) [alfa](t) = 0 y (i) [alfa](t)= [[alfa].sub.max], donde [[alfa].sub.max] es un valor positivo grande acotado. En el primer caso el enjambre converge a un punto de equilibrio, mientras que en el segundo caso el enjambre presenta un comportamiento de vorticidad.

En el primer caso (z), con [alfa](t) = 0, de la ecuacion (9) se tiene la ecuacion (10).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (10)

Dado que la energia del sistema tiene derivada en el tiempo definida negativa para todos [v.sub.i] [desiqual a] 0, el sistema tiende a un estado de energia minima con [??] = 0.

En el caso (i), el parametro [alfa](t) se fija en un valor grande, pero acotado [[alfa].sub.max] tal que se tiene la ecuacion (11).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (11)

Si [E.sub.T] = 0, el sistema permanece en un estado de energia constante. Con [paralelo][??][paralelo] = 0 las particulas deben encontrarse estaticas, en tanto que con [paralelo][[??].sub.i] [paralelo] = [raiz quadrada de ([[alfa].sub.max/[beta])] se logra el movimiento del enjambre con energia constante. Finalmente, al incrementar [[alfa].sub.max] se aumenta la velocidad maxima de las particulas y por lo tanto hay una mayor dispersion del enjambre.

Puntos de equilibrio

Los puntos de equilibrio se pueden establecer con las ecuaciones (12) y (13).

[[??].sub.i]/dt (12)

[m.sub.i] = [[??].sub.i]/dt (13)

Por consiguiente, se tiene [[??].sub.i] =0 y la ecuacion (14).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (14)

Considerando [[??].sub.i] = 0, la ecuacion (14) se reduce a la condicion de equilibrio dada por la ecuacion (15).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (15)

En la ecuacion (15) si [EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] entonces [EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII], por lo tanto, el enjambre converge a un minimo local. En otros casos cuando [EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] , se logra un equilibrio en funcion de la posicion de las particulas y la funcion objetivo.

SIMULACION DEL MODELO

Con el fin de observar las caracteristicas del modelo se realiza un conjunto de simulaciones con un potencial parabolico [U.sub.esp] = 0.5([x.sub.2] + [y.sub.2]) y para metros [K.sub.f] = 1, [m.sub.i] = 1, [alfa] = 1, N=20 y [beta]=1, con [alfa] igual a 4 y 9. En la figura 1 se presentan los resultados para 200 iteraciones y condiciones iniciales aleatorias para la posicion.

[FIGURA 1 OMITIR]

Esta figura muestra el comportamiento de vorticidad y la magnitud de la velocidad de las particulas, la cual tiende a ser |[[??].sub.i] = [raiz quadrada de([alfa]/[beta])]. Para [alfa] = 4 se tienen las figuras a y b mientras que para [alfa] = 9 se tienen las figuras c y d.

ESTRATEGIA DE BUSQUEDA BASADA EN DISPERSION

Con la estrategia propuesta se espera tener una exploracion adecuada del espacio de busqueda, de tal forma que despues de encontrar un minimo local se pueda escapar de este para seguir el proceso de busqueda. Con el fin de lograr lo anterior se propone aumentar la energia de propulsion del enjambre [alfa] cuando se alcanza un minimo local, y solo se disminuye cuando el enjambre es capaz de escapar de este punto.

La propuesta de busqueda emplea el comportamiento de vorticidad como un mecanismo de dispersion para lograr una busqueda global. En la figura 2 se puede apreciar el diagrama de flujo para la estrategia de busqueda propuesta. En un primer lugar se inicializa el enjambre y se procede a encontrar el minimo local mas cercano almacenando el valor del minimo encontrado. Posteriormente, para lograr que el enjambre escape del minimo encontrado, se realiza el proceso de dispersion, empleando para esto el comportamiento de vorticidad. Con el anterior proceso, mediante la busqueda grupal e individual se espera encontrar un valor minimo menor al encontrado previamente. En caso de que no se encuentre un valor tal se detiene el algoritmo, considerando para esto una dispersion maxima de las particulas sobre el espacio de busqueda.

[FIGURA 2 OMITIR]

Para lograr lo anterior el algoritmo presenta tres etapas:

1. Convergencia de busqueda grupal: en esta etapa el algoritmo converge al punto de equilibrio de las particulas, el cual puede ser el minimo local mas cercano. En esta etapa el comportamiento del enjambre esta dado por la funcion objetivo, observando para esto la posicion media del enjambre.

2. Dispersion y busqueda: cuando el enjambre encuentra un minimo local se realiza el proceso de dispersion, buscando tener movimientos circulares de las particulas. En esta misma etapa se realiza la busqueda de un mejor valor al encontrado previamente. Esta busqueda 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.

3. Convergencia de busqueda individual: en este caso una de las particulas encuentra un mejor valor, por lo cual el potencial de la funcion objetivo se reemplaza por un potencial de atraccion hacia el mejor punto encontrado, de tal forma que el enjambre pueda converger a este punto.

Valor minimo individual y grupal

Con el fin de establecer la fase del algoritmo se considera el valor minimo encontrado por la posicion media de las particulas [U.sub.min] y un valor minimo dado por la mejor posicion de las particulas de forma individual [U.sup.minP]. Estos valores se determinan considerando la funcion objetivo [U.sub.obj].

El mejor valor del grupo se determina conociendo el promedio de las posiciones del enjambre [??] mediante las ecuaciones (16) y (17).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (17)

La mejor posicion de la particula esta dada por la evaluacion de cada particula de la ecuacion (18).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (18)

Identificacion de las fases del algoritmo

Para identificar la fase en la cual se encuentra el algoritmo existen las siguientes condiciones:

1. Convergencia de busqueda grupal: [U.sub.minG] [mayor que o iqual to] [U.sub.obj] ([??]). En este caso [alfa] = 0 y [U.sub.esp] corresponde al potencial de la funcion objetivo [U.sub.obj]

2. Dispersion: [U.sub.minG] [mayor que o iqual to] [U.sub.u] incrementa la energia mediante [alfa](t) y [U.sub.esp] corresponde al potencial de la funcion objetivo [U.sub.obj]

3. Convergencia de busqueda individual: [U.sub.minP] [mayor que o iqual to] [U.sub.minG] y [U.sub.minG] [menor que o iqual to] [U.sub.obj] ([??]). En este caso [alfa] = 0 y [U.sub.esp] corresponde a un potencial cuadratico asociado a la mejor posicion encontrada.

Funcion objetivo

Considerando que [[??].sub.u] es la mejor posicion encontrada por algun individuo, entonces [U.sub.esp] se puede determinar con la ecuacion (19).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (19)

Incremento de energia La adicion de energia se realiza mediante el factor de propulsion, el cual esta dado por la ecuacion (20).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (20)

Para la funcion g(t) se considera un tiempo [T.sub.a] asociado al incremento de energia y un tiempo [T.sub.e] para la espera, momento en el cual las particulas se dispersan de forma circular sobre el espacio de busqueda. El numero total de iteraciones que toma este ciclo es [T.sub.a] + [T.sub.e] , donde se emplea la variable cont para realizar la cuenta de las iteraciones. La funcion g(t) esta dada por la ecuacion (21).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (21)

Con la anterior estrategia se espera que la energia de propulsion aumente hasta que las particulas logren evadir el minimo local. El aumento de la energia esta dado por el parametro [[tau].sub.c], el cual corresponde a la tasa con la cual se incrementa la energia de autopropulsion.

Criterio de parada del algoritmo

Como se ha mencionado previamente, el algoritmo utiliza la dispersion para escapar de minimos locales y explorar de manera eficiente el espacio de busqueda. Por lo tanto, el nivel de dispersion se emplea como criterio de parada del algoritmo. Considerando lo anterior, el criterio de parada propuesto establece que si el numero de particulas en el espacio de busqueda es menor que un valor especifico, entonces el algoritmo se detiene.

Implementacion del algoritmo

Para implementar el modelo dinamico del enjambre en el algoritmo, las ecuaciones diferenciales se convierten a tiempo discreto considerando un intervalo de tiempo [DELTA]t, de tal forma que se tienen las ecuaciones (22) y (23).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (22)

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (23)

El calculo de a en tiempo discreto se realiza con la ecuacion (24).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (24)

Finalmente, el algoritmo de optimizacion propuesto se puede apreciar en la figura 3.
Figura 3. Algoritmo de optimizacion propuesto

Algoritmo 1: Algoritmo propuesto de optimizacion VPSO._

1    Inicializar el enjambre, posiciones aleatorias y velocidad cero.;
2    begin
3       while Bajo algun criterio de finalizacion.
          Numero de iteraciones o depresion. do
4             Establecer la posicion media del enjambre [??]
                empleando la ecuacion 16;
5             Calcular [U.sub.minG] y [U.sub.minP] ecuaciones 17 y 18;
6             Establecer la fase de algoritmo;
7             Determinar [alfa] empleando la expresion 24;
8             for i = 1 hasta N do
9                Calcular la nueva posicion de las particulas con
                   la ecuacion 22;
10               Calcular la nueva velocidad de las particulas
                   empleando la ecuacion 23;
11            end
12            Pasar a la siguiente iteracion.
13       end
14       Establecer el valo optimo encontrado por las particulas.
15   end

Fuente: elaboracion propia.


ANALISIS CUALITATIVO DEL ALGORITMO

De los diferentes parametros involucrados en el algoritmo de optimizacion se puede hacer la siguiente descripcion:

* [beta]: Factor de frenado de las particulas. Al aumentar, las particulas tienden a ir mas lento.

* [alfa]: Factor de propulsion. Al incrementarse, las particulas aumentan su energia cinetica, elevandose de esta forma su velocidad.

* a : Factor de interaccion. Al aumentar, el enjambre de particulas tiende a unirse mas y al disminuir se dispersan mas.

* [K.sub.f] : Factor de ponderacion de la funcion objetivo. Al incrementarse, las particulas convergen rapidamente a un minimo local, y al disminuir, estas se pueden mover, sobre todo el espacio de busqueda.

[FIGURA 4 OMITIR]

Para mostrar el funcionamiento del algoritmo se realiza una simulacion, considerando un potencial cuadratico de la forma [U.sup.obj] = 2([x.sup.2] + [y.sup.2]). En la figura 4 se puede apreciar el potencial y la evolucion que tiene la posicion de las particulas en la medida que pasan las iteraciones. Es de apreciar que luego de encontrar el minimo local, las particulas inician el proceso de dispersion realizando un movimiento circular.

RESULTADOS

Para ilustrar el desempeno del algoritmo propuesto se considera un conjunto de funciones de prueba de 2 dimensiones, las cuales se pueden observar en Passino (2002) y Krishnanand (2009). En la figura 5 se puede apreciar la representacion grafica de las funciones objetivo empleadas. Passino: esta funcion de prueba es una adaptacion de la presentada en Passino (2002). En este caso la funcion tiene un minimo global en (0, 113, -3, 2597), cuyo valor es -3,4354 Esta funcion de prueba se encuentra descrita por la ecuacion (25).

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (25)

Peaks: esta funcion tiene dos minimos locales y un minimo global en (0, 2282, -1, 6199) que es igual a -6,4169. La ecuacion (26) describe esta funcion de prueba.

[EXPRESION MATEMATICA IRREPRODUCIBLE EN ASCII] (26)

Rastrigins: esta funcion representa un problema bastante dificil debido a su gran numero de locales minimos y maximos. El minimo global se encuentra en (0,0) con un valor de 0. Esta funcion se encuentra dada por la ecuacion (27).

[U.sub.obj,3] = 0, 1(20 + ([x.sup.2] - 10cos (2[pi]x) + [y.sup.2] - 10cos(2[pi]y))) (27)

Circles: esta funcion presenta varios circulos concentricos como regiones de maximos y minimos locales. El minimo global se encuentra en (0,0) con un valor de 0. La ecuacion (28) describe esta funcion de prueba.

[U.sub.obj] = [([x.sup.2] + [y.sup.2]).sup.0,25] [((sin(50( [x.sup.2] + [y.sup.2])0,1)).sup.2] + 1,0) (28)

Equal Peaks: esta funcion tiene varios minimos con un valor de 0 y situados periodicamente en x y y. Esta funcion se encuentra descrita por la ecuacion (29).

[U.sub.obj,5] = cos[(x).sup.2] + sin[(y).sup.2] (29)

Himmelblaus: consiste en una adaptacion de la funcion representada en Krishnanand (2009),la cual tiene cuatro minimos con valor de -2 situados en (-1, 5616,2,29260), (2,5616,2,1068), (2,5615,-2,1068) y (1,5616,-29260). La ecuacion (30) describe esta funcion de prueba.

[U.sub.obJ,6] = -0,01(200 - [([x.sup.2] + [y.sup.2] -11).sup.2] - [(x + [y.sup.2] -7).sup.2)] (30)

Para la ejecucion del algoritmo se toma: [m.sub.i]=1, [beta]=1, [[alpha].sub.max] = 20 y [DELTA]t = 0,1. El rango del espacio de busqueda considerado es (-6 [menor uqe o iqual to] x [menor uqe o iqual to] 6) y (-6 [menor uqe o iqual to] y [menor uqe o iqual to] 6). Las condiciones iniciales de las particulas son aleatorias en posicion y cero en velocidad. Dos configuraciones de parametros consideradas son: Set 1 a = 1, [K.sub.f] = 1; Set 2 a = 0,5, [K.sub.f] = 0,5. Por ultimo, se realizan 30 ejecuciones para cada conjunto de configuraciones. La tabla 1 muestra los valores maximos y minimos encontrados durante el proceso de optimizacion (mejores y peores resultados), el valor medio y la desviacion estandar (STD) de los resultados. Tambien se aprecia el numero de iteraciones empleadas por el algoritmo con cada funcion de prueba.

[FIGURA 5 OMITIR]

CONCLUSIONES

El modelo empleado fue seleccionado buscando tener una expresion compacta con pocos terminos y que permita describir comportamientos de enjambre como desplazamientos uniformes y movimientos circulares, los cuales se observan en diferentes grupos de seres vivos.

El algoritmo propuesto es un proceso de optimizacion basado en un comportamiento emergente que utiliza la vorticidad de un enjambre de particulas para mejorar las capacidades de busqueda y escapar de los minimos locales. Los resultados que se presentan muestran la eficacia de la estrategia propuesta, donde el enjambre fue capaz de evitar los minimos locales y encontrar una solucion global (aproximada) de las funciones propuestas.

En los resultados de la tabla 1 se puede apreciar que hay un mejor desempeno del algoritmo para la primera configuracion de parametros (Set 1). Adicionalmente, en estos resultados se observa que en promedio el mayor numero de iteraciones se encuentra en esta misma configuracion de parametros. Tambien es de notar que en la mayoria de la funciones objetivo el algoritmo logra encontrar el minimo global.

En particular la funcion objetivo Circles resulta de interes, debido a la simetria circular que presenta, lo cual puede dificultar el escape de las particulas de los minimos locales. En la tabla 1 se puede observar que para esta funcion objetivo el algoritmo emplea el mayor numero de iteraciones.

FINANCIAMIENTO

El financiamiento del presente proyecto se encuentra en el marco del proyecto con codigo 16332 de la Direccion de Investigacion Sede Bogota--Universidad Nacional de Colombia.

AGRADECIMIENTO

Los autores manifiestan su agradecimiento a la Universidad Distrital Francisco Jose de Caldas y a la Universidad Nacional de Colombia por el apoyo en el desarrollo de este trabajo.

REFERENCIAS

Abdel, M. y McInnes, C., "Wall Following to Escape Local Minima for Swarms of Agents Using Internal States and Emergent Behavior", International Conference of Computational Intelligence and Intelligent Systems ICCIIS, 2008.

Bajec, I. y Heppner, F., "Organized Flight in Birds", Animal Behaviour, Vol. 78, No. 4, 2009, pp. 777-89.

Berg H., Random Walks in Biology, Princeton University Press, 1983.

Bratton, D. y Kennedy, J., "Defining a Standard for Particle Swarm Optimization", Proceedings of IEEE Swarm Intelligence Symposium SIS, 2007.

Cengel, Y., Mecanica de fluidos, McGraw-Hill, 2003.

Couzin, I., Krause, J., Franks, N. y Levin, S., "Effective Leadership and Decision Making in Animal Groups on Themove", Letters to Nature, Vol. 433, 2005, pp. 513-16.

D'Orsogna, M., Chuang, Y., Bertozzi, A. y Chayes, L., "Self-Propelled Particles with SoftCore Interactions: Patterns, Stability, and Collapse", Physical Review Letters, Vol. 96, 2006.

Ebeling, W. y Erdmann, U., "Nonequilibrium Statistical Mechanics of Swarms of Driven Particles", Physica A: Statistical Mechanics and its Applications, Vol. 314, No. 1-4, 2002, pp. 92-96.

Erdmann, U., Ebeling, W. y Mikhailov, A., "Noise-Induced Transition from Translational to Rotational Motion of Swarms", Physical Review E, Vol. 71, No. 5, 2005.

Espitia, H. y Sofrony J., "Path Planning of Mobile Robots Using Potential Fields and Swarms of Brownian Particles", IEEE Congress on Evolutionary Computation (CEC), 2011, pp. 123-129.

Espitia H. y Sofrony J., "Vortex Particle Swarm Optimization", IEEE Congress on Evolutionary Computation (CEC), 2013.

Espitia, H., Sofrony, J. y Gonzalez C., "Vortex Swarm Path Planning Algorithm", IEEE Electronics, Robotics and Automotive Mechanics Conference (CERMA), 2011, pp. 184-90.

Evers, G., An Automatic Regrouping Mechanism to Deal with Stagnation in Particle Swarm Optimization (Master Thesis), University of Texas-Pan American, 2009.

Feng, C., Cong, S. y Feng, X., "A New Adaptive Inertia Weight Strategy in Particle Swarm Optimization", IEEE Congress on Evolutionary Computation (CEC), 2007.

Garcia, J. y Alba, E., "Restart Particle Swarm Optimization with Velocity Modulation: A Scalability Test", Springer, Soft Computing --A Fusion of Foundations, Methodologies and Applications, Vol. 1, 1997.

Garcia, R., Moss, F., Nihongi, A., Strickler, R., Goller, S., Erdmann, U., Schimansky, L. y Sokolov, I., "Optimal Foraging by Zooplankton within Patches: The Case of Daphnia", Elsevier, Mathematical Biosciences, Vol. 2, 2007, pp. 165-88.

Hendtlass, T., "A Particle Swarm Algorithm for High Dimensional, Multi-Optima Problem Spaces", IEEE Swarm Intelligence Symposium, 2005.

Hvass, M., Tuning & Simplifying heuristical optimization (Ph.D. Thesis), University of Southampton, UK, 2010.

Krishnanand, K. y Ghose, D., "Glowworm Swarm Optimization for Simultaneous Capture of Multiple Local Optima of Multimodal Functions", Springer Science, Swarm Intelligence, Vol. 3, No. 2, 2009, pp. 87-124.

Levine, H., Rappel, W. y Cohen, I., "Self-Organization in Systems of Self-Propelled Particles", Physical Review E, Vol. 63, No. 1, 2000.

Liang, J., Qin, A., Suganthan, P. y Baskar, S., "Comprehensive Learning Particle Swarm Optimizer for Global Optimization of Multimodal Functions", IEEE Transactions on Evolutionary Computation, Vol. 10, 2006.

Menser, S. y Hereford, J., "A New Optimization Technique", Proceedings of the IEEE Digital Object Identifier Southeast Con, 2006.

Mesa, E., Supernova: un algoritmo novedoso de optimizacion global (tesis de maestria), Universidad Nacional de Colombia, Sede Medellin, 2010.

Parsopoulos, K. y Vrahatis, M., "On the Computation of all Global Minimizers through Particle Swarm Optimization", IEEE Transactions on Evolutionary Computation, Vol. 8, 2004.

Passino, K., "Biomimicry of Bacterian Foragin for Distributed Optimization and Control", IEEE Control Systems Magazine, 2002.

Passino, K., Biomimicry for Optimization, Control, and Automation, Springer-Verlag, London, UK, 2005.

Schutte, J., Particle Swarms in Sizing and Global Optimization (Master's Dissertation), University of Pretoria, 2002.

Sumpter, D., "The Principles of Collective Animal Behaviour", Philosophical Transactions of the Royal Society B, Vol. 361, No. 1465, 2006, pp. 5-22.

Van den Bergh, F., An Analysis of Particle Swarm Optimizers (PhD. Thesis), University of Pretoria, Pretoria, 2001.

Vicsek T., "Universal Patterns of Collective Motion from Minimal Models of Flocking", Second IEEE International Conference on Self-Adaptive and Self-Organizing Systems, 2008.

Vicsek, T., Czirok, A., Ben, E., Cohen, I. y Shochet, O., "Novel Type of Phase Transition in a System of Self-Driven Particles", Physical Review Letters, Vol. 75, No. 6, 1995.

Yin, L. y Liu, X., "A PSO Algorithm Based on Biology Population Multiplication (PMPSO)", Proceedings of the Second Symposium International Computer Science and Computational Technology (ISCSCT '09), 2009.

Zhang, H., Chen, M., Stan, G., Zhou, T. y Maciejowski, J., "Collective Behavior Coordination with Predictive Mechanisms", IEEE Circuits and Systems Magazine, 2008.

Helbert Eduardo Espitia Cuchango

Ingeniero electronico, ingeniero mecatronico, especialista en Telecomunicaciones Moviles, magister en Ingenieria Industrial, magister en Ingenieria Mecanica, docente de la Universidad Distrital Francisco Jose de Caldas, Bogota, Colombia. Contacto: heespitiac@udistrital.edu.co

Jorge Ivan Sofrony Esmeral

Ingeniero electrico, magister en Sistemas de Control, doctor en Sistemas de Control, docente de la Universidad Nacional de Colombia, Bogota, Colombia. Contacto: jsofronye@unal.edu.co

Fecha de recepcion: 31 de agosto de 2013

Fecha de aceptacion: 16 de mayo de 2014

Clasificacion del articulo: investigacion

Financiamiento: Universidad Nacional de Colombia
Tabla 1. Resultados para 30 ejecuciones

Configuracion          Set 1                    Set 2

Funcion 1         Valor     Iteraciones    Valor     Iteraciones
Maximo            0,361         383        0,3751        447
Minimo           -3,4354        178       -3,4353        175
Promedio         -2,4562       289,9       -2,508       283,7
STD              1,0601        52,6        1,1156       71,5
Funcion 2         Valor     Iteraciones    Valor     Iteraciones
Maximo           -2,7524        754        0,2263        518
Minimo           -6,4168        168       -6,4164        135
Promedio         -5,2747       431,1       -3,775       283,3
STD              1,6175        162,9       2,1602       90,6
Funcion 3         Valor     Iteraciones    Valor     Iteraciones
Maximo            0,754         681        1,2772        609
Minimo           0,00008        157        0,0191        150
Promedio         0,2207        378,8        0,31        304,8
STD              0,1997        153,5       0,3483       99,5
Funcion 4         Valor     Iteraciones    Valor     Iteraciones
Maximo           1,7705         795        1,559         745
Minimo           0,0661         169        0,2213        123
Promedio          0,62         427,7       0,8181        283
STD               0,412        193,5       0,2875       127,1
Funcion 5         Valor     Iteraciones    Valor     Iteraciones
Maximo            0,011         537        1,5746        772
Minimo          0,0000057       212       0,000237       70
Promedio         0,0036        315,5       0,1066        284
STD              0,0037        73,3        0,312        124,8
Funcion 6         Valor     Iteraciones    Valor     Iteraciones
Maximo           -1,8839        559       -1,5351        693
Minimo             -2           222       -1,9999        165
Promedio         -1,9913       340,7      -1,9441       358,9
STD              0,0221        89,5        0,113        104,8

Fuente: elaboracion propia.
COPYRIGHT 2014 Universidad Distrital Francisco Jose de Caldas
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2014 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Espitia Cuchango, Helbert Eduardo; Sofrony Esmeral, Jorge Ivan
Publication:Revista Tecnura
Date:Oct 1, 2014
Words:5680
Previous Article:Aproximacion numerica del modelo epidemiologico si para la propagacion de gusanos informaticos, simulacion y analisis de su error.
Next Article:Hibrido rat-race miniaturizado para la banda ISM 2,4 GHZ.
Topics:

Terms of use | Privacy policy | Copyright © 2018 Farlex, Inc. | Feedback | For webmasters