VI Congreso Espaol sobre Metaheursticas, Algoritmos Evolutivos y Bioinspirados (MAEB'09)

Algoritmo Basado en C mulos de Partculas y u Evoluci n Diferencial para la Resoluci n de o o Problemas de Optimizaci n Continua o
Jose Manuel Garcia-Nieto1 , Javier Apolloni2 , Enrique Alba1 y Guillermo Leguizam n2 o
Resumen Los algoritmos de optimizaci n basados en Cumuo los de Partculas (Particle Swarm Optimization - PSO) y Evolu ci n Diferencial (Differential Evolution - DE) vienen siendo utilio zados satisfactoriamente, desde su creaci n en la pasada d cada, o e en la resoluci n de problemas complejos de optimizaci n de natuo o raleza continua. En este trabajo analizamos el comportamiento de una nueva t cnica metaheurstica, combinando las estrategias de e busqueda y operadores presentes en PSO y DE, con la que pretendemos mejorar los resultados existentes en el estado del arte. Para ello, seguimos el marco experimental propuesto en la sesi n espeo cial de optimizaci n continua de MAEB09 y se realizan comparao ciones estadsticas con tres algoritmos: G-CMA-ES, DE y K-PCX, tomados a su vez de la sesi n especial de optimizaci n continua o o de CEC05. Los resultados obtenidos muestran un alto grado de competitividad de nuestra propuesta con respecto a los algoritmos comparados. Palabras claveAlgoritmo de Cumulos de Partculas, Evoluci n o Diferencial, Benchmark de Funciones de Optimizaci n Continua o de CEC05

I. I NTRODUCCI ON Los algoritmos de optimizaci n basados en C mulos o u de Partculas (Particle Swarm Optimization - PSO) [1] y Evoluci n Diferencial (Differential Evolution - DE) [2] o vienen siendo utilizados satisfactoriamente, desde su creaci n en la pasada d cada, en la resoluci n de probleo e o mas complejos de optimizaci n de naturaleza continua. o Estos problemas se pueden encontrar tanto en el ambito de la industria como en el acad mico y consisten b sicae a mente en: encontrar un x tal que x f (x ) f (x). Donde f (.) es una funci n de dominio en el espacio o de los reales que modela un problema de optimizaci n, o x = {x1 , x2 , . . . , xD } es una posible soluci n a dicho o problema, D es el n mero de variables de la funci n u o y xi [xinf , xsup ] (1 i D). Por ultimo, xinf , i i i xsup R corresponden a los lmites inferior (inf ) y su i perior (sup) del dominio de la variable, respectivamente. En este trabajo estamos interesados en analizar el rendimiento de una nueva t cnica metaheurstica que llae maremos DEPSO (Differential Evolution Particle Swarm Optimization), consistente en un algoritmo hbrido que toma ideas tanto de PSO como de DE para la resoluci n de los problemas de optimizaci n continua propueso o tos en la sesi n especial de MAEB09 (disponible en la o URL [Link] [3]. De esta forma, combinando las estrategias de b squeda, adaptau
1 Lenguajes y Ciencias de la Computaci n. Universidad o de M laga. Campus de Teatinos s/n, 29071, Espa a. E-mail: a n {jnieto,eat}@[Link]. 2 LIDIC - Departamento de Inform tica. Universidad Nacional a de San Luis. Ej rcito de los Andes 950, 5700, Argentina. E-mail: e {javierma,legui}@[Link]

ci n de par metros y operadores presentes en PSO y DE o a pretendemos mejorar los resultados existentes en el estado del arte. Para ello, seguimos el marco experimental propuesto en dicha sesi n y se realizan comparaciones o estadsticas con tres algoritmos: G-CMA-ES [4], DE [5] y K-PCX [6], tomados de la sesi n especial de optimizao ci n continua del CEC05 [7]. o El resto de este artculo se organiza de la siguiente for ma: en la Secci n II se describen brevemente los algoo ritmos PSO y DE. La Secci n III presenta el algoritmo o DEPSO dando detalles de su estructura, implementaci n o y funcionamiento. La Secci n IV describe el estudio exo perimental realizado: los par metros utilizados, el bena chmark (CEC05) de funciones a optimizar, as como los resultados obtenidos. De forma adicional, se realiza un an lisis estadstico de los resultados en comparaci n con a o los algoritmos G-CMA-ES, DE y K-PCX. Por ultimo, en la Secci n V se incluyen las conclusiones y trabajo futuo ro a realizar continuando con esta lnea de investigaci n. o II. C ONCEPTOS B ASICOS En esta secci n se describen brevemente las t cnicas o e metaheursticas de los algoritmos basados en C mulos u de Partculas y Evoluci n Diferencial. o A. Algoritmos de C mulos de Partculas u Los algoritmos de optimizaci n basados en c mulos o u de partculas o Particle Swarm Optimization (PSO) [1] fueron desarrollados por Kennedy y Eberhart en 1995. Se trata de una t cnica metaheurstica basada en poblaci n e o e inspirada en el comportamiento social del movimiento de las bandadas de aves o de los bancos de peces. En la b squeda de una soluci n optima o cuasi- ptiu o o ma, PSO actualiza el c mulo actual de partculas utiliu zando informaci n acerca de la mejor soluci n obtenida o o por cada partcula (p) y la mejor soluci n obtenida en el o c mulo entero g. La posici n de cada partcula xi es un u o candidato a soluci n de un problema. Cada partcula tieo ne los siguientes atributos: la velocidad actual vi , la posici n actual xi , la mejor posici n obtenida por la partcula o o hasta el momento pi y la mejor posici n encontrada por o los vecinos de la partcula hasta el momento gi . El vecin dario de una partcula puede ser global, en el cual todas las partculas del c mulo son consideradas vecinas entre u s, o local, en el que s lo son vecinas las partculas inme o diatamente cercanas. En la primera fase del algoritmo, se inicializa aleatoriamente la velocidad y la posici n de o cada partcula del c mulo. u

433

Metaheursticas, Algoritmos Evolutivos y Bioinspirados para Problemas de Optimizacin Continua

En la segunda fase, para cada partcula del c mulo se u o actualizan la velocidad (vi ) y la posici n (xi ) mediante las siguientes ecuaciones: vi vi + 1 r1 (pi xi ) + 2 r2 (gi xi ) (1) xi xi + vi (2) la nueva generaci n si consigue alguna mejora sobre el o individuo anterior, como muestra la Ecuaci n 5. o vi = ui vi if f (ui ) f (vi ), en otro caso. (5)

donde es el factor de inercia [8] mediante el que se controla el balance entre explotaci n y exploraci n en la o o b squeda, 1 y 2 son factores de inuencia de los coeu cientes individual y social de cada partcula (normal mente 1 = 2 = 2). Por ultimo, r1 y r2 son valores uniformemente aleatorios (r1 = r2 = U N (0, 1)). B. Evoluci n Diferencial o El algoritmo de Evoluci n Diferencial (DE) fue proo puesto por Storm y Price [2], [9] en 1998. Se trata de una t cnica no determinista basada en la evoluci n de una e o poblaci n de vectores (individuos) de valores reales que o representan las soluciones en el espacio de b squeda. La u generaci n de nuevos individuos se lleva a cabo mediante o operadores diferenciales de mutaci n y cruce. o Mediante la mutaci n diferencial se a ade la difereno n cia proporcional de dos individuos elegidos aleatoriamente de la poblaci n a un tercer individuo (tambi n o e elegido aleatoriamente). Formalmente, dados tres individuos vr1 , vr2 y vr3 elegidos aleatoriamente de la poblaci n, donde r1, r2, r3 {1, 2, . . . , N } son n meros o u aleatorios diferentes entre s y N es el tama o de la po n blaci n, un nuevo individuo mutado wi se genera meo diante la siguiente expresi n: o wi vr1 + (vr2 vr3 ) (3)

En la siguiente secci n, se describe el algoritmo objeo to de este trabajo en el que se utilizan las estructuras y operadores, tanto de PSO como de DE, con la intenci n o de aprovechar las capacidades de b squeda intrnsecas de u cada uno de estos algoritmos. III. E L A LGORITMO DEPSO Bas ndonos en los estudios de Swagatam Das et a al. [10], en los que proponen un acercamiento inicial a la hibridaci n de PSO y DE para la optimizaci n contio o nua, el algoritmo implementado para el presente trabajo, al que llamamos DEPSO, b sicamente utiliza el esquea ma de variaci n diferencial que emplea DE para ajustar o la velocidad de las partculas en PSO. El mecanismo de actualizaci n de partculas por variao ci n diferencial proporciona un esquema para una r pio a da convergencia hacia un optimo. De este modo, la actualizaci n de la velocidad de las partculas utiliza dos o vectores de posici n de partculas seleccionados de mao nera aleatoria. Para cada partcula xi de la poblaci n se o obtiene el vector diferencia w = xr1 xr2 donde las partculas xr1 y xr2 son seleccionadas aleatoriamente. La velocidad para la partcula i se calcula utilizando la siguiente ecuaci n: o vi vi + w + (g xi ), (6)

La constante de mutaci n > 0 establece el rango de o diferenciaci n entre los individuos vr2 y vr3 con el objeo tivo de evitar el estancamiento en el proceso de b squeda. u Tras la mutaci n, se realiza una operaci n de recombio o naci n sobre cada individuo vi (target) para generar un o individuo intermedio ui (trial). Esta operaci n de cruce o selecciona uniformemente una posici n j del vector trial o con la misma probabilidad que del vector target obtenido del individuo mutado. ui (j) = wi (j) if r Cr o j = jr , vi (j) en otro caso. (4)

donde es el factor de inercia y es un factor de escala aplicado al vector diferencia ( = U N (0, 1)). El tercer sumando corresponde al factor social inuido por el mejor global de la poblaci n g, proporcional al coeciente o social (en este caso = U N (0, 1)). As, en el c lcu a lo del vector de la velocidad se reemplaza la experiencia personal de la partcula por el vector diferencial. De la misma forma que en DE, la actualizaci n de la o jesima componente de velocidad para la partcula i se realiza mediante la Ecuaci n 7 como sigue: o vi (j) = vi (j) vi (j) si r Cr, en otro caso. (7)

Como se puede observar en la Ecuaci n 4, el operao dor de cruce elige aleatoriamente un valor entero jr [1 . . . D] y un valor real aleatorio r (0, 1), tambi n e uniformemente distribuido para cada componente j (1 . . . D) del vector trial ui . De este modo, con una probabilidad de recombinaci n Cr o bien en el caso en el o que se cumpla la igualdad j = jr , se selecciona el elemento jesimo del individuo mutado wi (j) para ser colo cado en el elemento jesimo del individuo trial ui (j). En otro caso, se selecciona el elemento jesimo del individuo target vi (j) para ser colocado en el elemento jesimo del individuo trial. Finalmente, mediante un operador de selecci n se decide la aceptaci n del individuo trial para o o

Donde r [0, 1] es un valor uniformemente distribuido que determina si se escoge la componente j desde la nueva velocidad o desde la velocidad actual en base a la probabilidad de recombinaci n Cr [0, 1]. Mediante eso te mecanismo se permite seleccionar algunas de las componentes del vector de velocidad aumentando la habilidad de explotaci n del algoritmo. Finalmente, la partcuo la i cambia de posici n s lo si la nueva posici n xi mejoo o o ra respecto a la anterior en el proceso de evoluci n (asuo miendo que se pretende minimizar), en otro caso permanece en la posici n actual (ecuaciones 8 y 9). o xi = xi xi si f (x i ) f (xi ) en otro caso, (8)

434

VI Congreso Espaol sobre Metaheursticas, Algoritmos Evolutivos y Bioinspirados (MAEB'09)

siendo El benchmark utilizado consta de un subconjunto de las 20 funciones multimodales (desde la funci n f6 a o a la f25 ) incluyendo funciones b sicas en versiones rotadas y/o desplazadas adem s de funciones compuestas. El a optimo de las funciones est desplazado por un valor de a bias que permite evitar que el algoritmo de b squeda se u benecie de la simetra del espacio. Se ha considerado la optimizaci n de estas funciones con espacios de variao bles de dimensiones 10 y 30. Sobre cada funci n del benchmark y cada una de las o dimensiones se han realizado 25 ejecuciones independientes. La condici n de nalizaci n de cada ejecuci n o o o requiere que el n mero de evaluaciones de la funci n de u o optimizaci n alcance 104 D (siendo D las dimensioo nes: 10 y 30) o bien cuando el error obtenido sea inferior a 108 . Las ejecuciones independientes se realizaron utilizando una plataforma de clusters CONDOR sobre m quinas Pentium IV 2.4 GHz con 1GB de RAM y a sistema operativo Linux Fedora core 6. A. Par metros a El conjunto de par metros establecido en estos experia mentos ha sido el mismo para todas las ejecuciones independientes, funciones del benchmark y dimensiones. En la siguiente tabla se muestran los par metros empleados. a
TABLA I PAR AMETROS UTILIZADOS PARA LAS EJECUCIONES DE DEPSO Descripci n o Tama o de c mulo n u Probabilidad de cruce Inercia Mutaci n diferencial o Coeciente social Probabilidad de mutaci n o Par metro a tc Cr pmut Valor 50 0,9 0,1 . . . 0,5 (f6 a f12 ) 0,1 (f13 a f25 ) U N (0, 1) 1 U N (0, 1)
1 dimensin o

xi xi + v i

(9)

De manera adicional, con cierta probabilidad pmut , se realiza una operaci n de mutaci n sobre cada partcula o o con la intenci n de evitar una r pida convergencia a un o a optimo local. La nueva posici n de la partcula x se geo nerada utilizando la Ecuaci n 10. o x xinf + U N (0, 1) (xsup xinf ) (10) Los vectores xinf , xsup corresponden a los limites inferiores y superiores respectivamente de cada dimensi n o de la funci n que se desea optimizar. o En Algoritmo 1, se muestra el pseudoc digo del moo delo hbrido DEPSO implementado para este trabajo. Algoritmo 1 Pseudoc digo de DEPSO o
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: inicializa(C) mientras no alcance condici n de nal hacer o o para cada partcula xi de la poblaci n hacer /* Variaci n diferencial */ o para cada dimensi n j de la partcula xi hacer o w(j) xr1 (j) xr2 (j) si r Cr entonces vi (j) vi (j) + w(j) + (g(j) xi (j)) n si n para para cada dimensi n j de la partcula xi hacer o xi (j) xi (j) + vi (j) n para si f (x i ) f (xi ) entonces x ixi sino x i xi n si /* Mutati n */ o si U N (0, 1) < pmut entonces para cada dimensi n j de la partcula xi hacer o x i (j) xinf (j) + U N (0, 1) (xsup (j) xinf (j)) n para n si n para n mientras Salida: Mejor soluci n encontrada o

Tras la inicializaci n previa de la poblaci n (c mulo) o o u C de partculas y su evaluaci n inicial (lnea 1), en cada o paso de la evoluci n se actualizan las posiciones de todas o las partculas. Dentro del ciclo de evoluci n se realiza la o variaci n diferencial (lneas 4 a 18) mediante las ecuacioo nes anteriormente explicadas y la operaci n de mutaci n, o o si procede (lneas 20 a 24). Adem s, se actualiza la mejor a posici n global encontrada hasta el momento para guiar o el resto del c mulo. Finalmente, el algoritmo devuelve la u mejor soluci n encontrada. o IV. E XPERIMENTOS El algoritmo DEPSO se ha implementado en C++ utilizando la biblioteca de algoritmos de optimizaci n o MALLBA [11]. Para el benchmark de funciones que se desean optimizar se ha utilizado el c digo fuente, en leno guaje C, disponible en la p gina web de la sesi n especial a o de optimizaci n continua de CEC05 [7]. En la realizao ci n de los experimentos, se ha seguido el marco expeo rimental propuesto en la sesi n especial de optimizaci n o o continua de MAEB09 [3].

Unicamente para las funciones simples (f6 a f12 ), se ha utilizado un factor de inercia adaptativo (Ecuaci n 11) o cuyo valor decrece durante la ejecuci n del algoritmo o desde 0,5 (max ) hasta 0,1 (min ), respecto al n mero u actual de generaciones (#genactual ) y el n mero total u de generaciones (#gentotal ). max B. Resultados En esta secci n se presentan los resultados obtenidos o tras los experimentos llevados a cabo con DEPSO. Para facilitar su comparaci n con otros resultados encontrao dos en el estado del arte, se recogen en las siguientes tablas el error de los valores obtenidos de cada funci n o del benchmark sobre el optimo f (x ) en el valor de bias establecido (f (x)f (x )). En las tablas II y III, se muestran los resultados obtenidos sobre las funciones f6 a f15 y f16 a f25 , respectivamente con dimensi n D = 10. o (max min ) #genactual #gentotal (11)

435

Metaheursticas, Algoritmos Evolutivos y Bioinspirados para Problemas de Optimizacin Continua

TABLA II VALOR DE E RROR ALCANZADO POR DEPSO PARA LAS FUNCIONES f6 A f15 CON DIMENSI ON D = 10 Y 100.000 EVALUACIONES DE LA OBJETIVO FUNCI ON
No Ejecuci n o 1a (Mejor) a 7 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. f6 4,71E+04 1,70E+05 2,33E+05 3,49E+05 5,40E+05 2,68E+05 1,41E+05 5,40E-02 4,18E+00 4,82E+00 6,21E+00 9,25E+00 4,97E+00 2,22E+00 0,00E+00 2,50E-02 4,50E-02 8,70E-02 4,00E+00 4,75E-01 1,12E+00 f7 3,12E+00 7,11E+00 8,04E+00 1,11E+01 1,21E+01 8,26E+00 2,60E+00 1,00E-02 5,70E-02 1,41E-01 3,97E-01 5,61E-01 2,15E-01 1,90E-01 7,00E-03 4,40E-02 5,70E-02 9,60E-02 1,30E-01 6,46E-02 3,18E-02 f8 2,05E+01 2,06E+01 2,06E+01 2,07E+01 2,08E+01 2,07E+01 9,05E-02 2,03E+01 2,04E+01 2,05E+01 2,05E+01 2,06E+01 2,05E+01 9,23E-02 2,02E+01 2,03E+01 2,03E+01 2,04E+01 2,04E+01 2,03E+01 5,01E-02 f9 3,84E+01 4,59E+01 4,90E+01 5,27E+01 5,95E+01 4,93E+01 5,92E+00 9,63E+00 1,54E+01 1,82E+01 2,24E+01 2,58E+01 1,79E+01 4,46E+00 0,00E+00 9,95E-01 1,99E+00 2,99E+00 3,98E+00 1,99E+00 1,18E+00 f10 3,53E+01 4,80E+01 5,58E+01 6,22E+01 6,57E+01 5,48E+01 8,09E+00 2,25E+01 2,76E+01 3,36E+01 3,62E+01 3,84E+01 3,19E+01 5,04E+00 3,01E+00 5,97E+00 7,97E+00 1,44E+01 2,11E+01 1,02E+01 5,12E+00 f11 7,93E+00 1,05E+01 1,12E+01 1,19E+01 1,22E+01 1,11E+01 9,67E-01 2,22E+00 7,00E+00 8,08E+00 8,85E+00 9,99E+00 7,61E+00 1,84E+00 1,00E-04 2,02E-01 1,09E+00 1,75E+00 2,01E+00 1,00E+00 7,65E-01 f12 2,66E+03 6,70E+03 9,50E+03 1,17E+04 1,81E+04 9,39E+03 4,42E+03 2,00E-02 1,03E+01 1,25E+01 5,52E+01 7,27E+02 8,93E+01 1,99E+02 0,00E+00 9,40E-02 1,00E+01 1,88E+01 7,12E+02 3,70E+01 1,41E+02 f13 3,93E+00 5,31E+00 5,78E+00 6,21E+00 6,50E+00 5,60E+00 6,81E-01 1,83E+00 2,24E+00 3,07E+00 3,20E+00 3,33E+00 2,82E+00 5,01E-01 5,25E-01 9,13E-01 1,41E+00 1,72E+00 1,87E+00 1,32E+00 4,45E-01 f14 3,73E+00 4,03E+00 4,14E+00 4,25E+00 4,31E+00 4,11E+00 1,74E-01 2,79E+00 3,43E+00 3,66E+00 3,76E+00 3,81E+00 3,56E+00 2,49E-01 1,02E+00 2,13E+00 2,42E+00 2,75E+00 2,92E+00 2,31E+00 5,42E-01 f15 3,43E+02 4,81E+02 5,45E+02 5,99E+02 6,16E+02 5,35E+02 7,50E+01 1,26E+02 2,17E+02 2,65E+02 4,02E+02 4,27E+02 2,81E+02 9,91E+01 0,00E+00 6,30E+01 8,97E+01 1,39E+02 4,20E+02 1,34E+02 1,28E+02

1E+03

1E+04

1E+05

TABLA III VALOR DE E RROR ALCANZADO POR DEPSO PARA LAS FUNCIONES f16 A f25 CON DIMENSI ON D = 10 Y 100.000 EVALUACIONES DE LA FUNCI ON OBJETIVO
No Ejecuci n o 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. f16 2,00E+02 2,30E+02 2,50E+02 2,66E+02 2,73E+02 2,47E+02 2,08E+01 1,36E+02 1,64E+02 1,71E+02 1,78E+02 1,88E+02 1,68E+02 1,46E+01 8,21E+01 9,84E+01 1,06E+02 1,12E+02 1,20E+02 1,05E+02 9,49E+00 f17 1,69E+02 2,63E+02 2,85E+02 2,93E+02 3,17E+02 2,71E+02 3,32E+01 1,58E+02 1,88E+02 1,97E+02 2,05E+02 2,17E+02 1,94E+02 1,59E+01 1,03E+02 1,17E+02 1,24E+02 1,29E+02 1,52E+02 1,25E+02 1,05E+01 f18 8,43E+02 9,32E+02 1,01E+03 1,06E+03 1,08E+03 9,87E+02 7,10E+01 3,00E+02 8,00E+02 8,00E+02 8,00E+02 9,33E+02 7,05E+02 2,21E+02 3,00E+02 8,00E+02 8,00E+02 8,00E+02 9,32E+02 7,05E+02 2,21E+02 f19 8,41E+02 9,37E+02 1,01E+03 1,06E+03 1,08E+03 9,98E+02 7,42E+01 3,00E+02 8,00E+02 8,00E+02 9,08E+02 9,49E+02 7,83E+02 1,79E+02 3,00E+02 8,00E+02 8,00E+02 9,08E+02 9,46E+02 7,82E+02 1,78E+02 f20 4,08E+02 5,81E+02 7,12E+02 8,33E+02 9,63E+02 7,18E+02 1,61E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 0,00E+00 2,00E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 0,00E+00 f21 5,66E+02 9,85E+02 1,16E+03 1,22E+03 1,24E+03 1,05E+03 2,23E+02 3,00E+02 3,00E+02 3,00E+02 5,00E+02 9,00E+02 4,64E+02 2,12E+02 3,00E+02 3,00E+02 3,00E+02 5,00E+02 9,00E+02 4,64E+02 2,12E+02 f22 6,26E+02 8,23E+02 8,38E+02 8,64E+02 9,44E+02 8,44E+02 5,98E+01 1,00E+02 7,74E+02 7,76E+02 8,00E+02 8,00E+02 7,37E+02 1,65E+02 1,00E+02 7,60E+02 7,64E+02 8,00E+02 8,00E+02 7,29E+02 1,63E+02 f23 6,16E+02 1,02E+03 1,20E+03 1,22E+03 1,25E+03 1,11E+03 1,76E+02 3,00E+02 3,00E+02 3,00E+02 8,00E+02 1,05E+03 5,23E+02 2,76E+02 3,00E+02 3,00E+02 3,00E+02 8,00E+02 1,05E+03 5,23E+02 2,76E+02 f24 3,02E+02 4,17E+02 5,98E+02 7,49E+02 9,10E+02 5,94E+02 1,96E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 5,00E+02 2,68E+02 1,25E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 5,00E+02 2,68E+02 1,25E+02 f25 2,79E+02 4,13E+02 6,05E+02 7,74E+02 1,02E+03 5,96E+02 2,16E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 5,00E+02 2,48E+02 1,12E+02 2,00E+02 2,00E+02 2,00E+02 2,00E+02 5,00E+02 2,48E+02 1,12E+02

1E+03

1E+04

1E+05

En dichas tablas se muestran los valores nales de las ejecuciones independientes ordenados de mejor a peor: 1a (Mejor), 7a , 13a (Mediana), 19a y 25a (Peor). Estos valores se recogen a las 1.000, 10.000 y 100.000 evaluaciones de funci n objetivo. Adem s, se presentan las medias o a y desviaciones tpicas (Des. Tip.). En las tablas IV y V, se muestran los resultados obtenidos sobre las funcioo nes f6 a f15 y f16 a f25 , respectivamente con dimensi n D = 30. De esta forma seguimos el formato de tablas establecido en CEC05 y recomendado en MAEB09.

C. Discusi n y An lisis o a Para el an lisis de los resultados, se comparan las mea dias de los valores de error obtenidos por DEPSO en las 25 ejecuciones independientes con las medias obtenidas por tres algoritmos de referencia presentados en la sesi n o especial de optimizaci n continua de CEC05. Tales alo goritmos son los siguientes: G-CMA-ES [4]: Estrategia Evolutiva adaptando una matriz de Covarianza. K-PCX [6]: Algoritmo Gen tico de Optimizaci n de e o Estado Estacionario. DE [5]: Modelo cl sico de Evoluci n Diferencial para a o Optimizaci n de par metros reales. o a En esta comparativa hemos hecho uso de los m todos de e comparaci n no param tricos detallados en [12] ya que, o e como se muestra en dicho artculo, para las funciones de tests consideradas, no pueden emplearse las funciones param tricas como t-test al no cumplir las condicioe

Continuando con este protocolo, en la gura Fig. 1 se muestran las gr cas generadas mediante las trazas de a la ejecuci n n mero 13 (Mediana) de DEPSO sobre las o u funciones del benchmark con dimensi n D = 30, en las o que se recoge el mejor valor de error obtenido en cada evaluaci n de funci n objetivo de las 300.000 evaluacioo o nes totales.

436

VI Congreso Espaol sobre Metaheursticas, Algoritmos Evolutivos y Bioinspirados (MAEB'09)

TABLA IV VALOR DE E RROR ALCANZADO POR DEPSO PARA LAS FUNCIONES f6 A f15 CON DIMENSI ON D = 30 Y 300.000 EVALUACIONES DE LA OBJETIVO FUNCI ON
No Ejecuci n o 1a (Mejor) a 7 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. f6 7,26E+08 2,15E+09 3,18E+09 4,77E+09 9,68E+09 3,68E+09 2,24E+09 4,10E+00 2,32E+01 2,59E+01 7,36E+01 2,00E+03 1,43E+02 3,99E+02 0,00E+00 1,00E-03 5,90E-02 3,99E+00 8,50E+00 1,75E+00 2,51E+00 f7 2,92E+01 3,99E+01 4,88E+01 5,89E+01 6,39E+01 4,88E+01 1,05E+01 0,00E+00 1,70E-02 2,50E-02 3,80E-02 5,40E-02 2,76E-02 1,36E-02 0,00E+00 1,00E-02 1,00E-02 2,00E-02 3,20E-02 1,34E-02 7,95E-03 f8 2,10E+01 2,11E+01 2,11E+01 2,12E+01 2,12E+01 2,11E+01 5,28E-02 2,09E+01 2,10E+01 2,10E+01 2,11E+01 2,11E+01 2,10E+01 3,96E-02 2,08E+01 2,09E+01 2,09E+01 2,10E+01 2,10E+01 2,09E+01 4,63E-02 f9 1,88E+02 2,23E+02 2,43E+02 2,60E+02 2,66E+02 2,38E+02 2,49E+01 5,59E+01 1,15E+02 1,41E+02 1,52E+02 1,60E+02 1,30E+02 3,09E+01 1,49E+01 2,29E+01 2,49E+01 2,69E+01 3,38E+01 2,49E+01 4,84E+00 f10 2,13E+02 2,68E+02 2,79E+02 2,87E+02 2,94E+02 2,73E+02 2,04E+01 1,50E+02 1,97E+02 2,08E+02 2,24E+02 2,33E+02 2,06E+02 2,19E+01 5,38E+01 1,50E+02 1,74E+02 1,79E+02 1,91E+02 1,64E+02 2,86E+01 f11 3,97E+01 4,17E+01 4,31E+01 4,35E+01 4,50E+01 4,27E+01 1,45E+00 3,85E+01 4,03E+01 4,10E+01 4,14E+01 4,20E+01 4,08E+01 9,25E-01 1,05E+01 1,32E+01 1,58E+01 3,18E+01 3,81E+01 2,06E+01 1,06E+01 f12 1,09E+05 1,50E+05 1,79E+05 2,10E+05 2,96E+05 1,85E+05 5,13E+04 1,04E+03 4,50E+03 8,58E+03 1,17E+04 2,00E+04 8,59E+03 5,19E+03 4,20E+02 1,47E+03 2,60E+03 5,08E+03 8,22E+03 3,30E+03 2,43E+03 f13 1,92E+01 2,36E+01 2,46E+01 2,50E+01 2,59E+01 2,42E+01 1,55E+00 1,56E+01 1,70E+01 1,80E+01 1,85E+01 1,92E+01 1,77E+01 1,06E+00 2,42E+00 3,97E+00 1,10E+01 1,30E+01 1,58E+01 9,65E+00 4,80E+00 f14 1,35E+01 1,37E+01 1,38E+01 1,39E+01 1,41E+01 1,38E+01 1,49E-01 1,28E+01 1,32E+01 1,34E+01 1,36E+01 1,36E+01 1,34E+01 2,23E-01 1,20E+01 1,27E+01 1,28E+01 1,30E+01 1,31E+01 1,28E+01 2,76E-01 f15 4,86E+02 5,56E+02 6,10E+02 6,49E+02 7,32E+02 6,04E+02 7,09E+01 2,06E+02 2,20E+02 3,00E+02 3,30E+02 4,06E+02 2,95E+02 7,34E+01 2,02E+02 2,17E+02 3,00E+02 3,29E+02 4,04E+02 2,90E+02 7,64E+01

3E+03

3E+04

3E+05

TABLA V VALOR DE E RROR ALCANZADO POR DEPSO PARA LAS FUNCIONES f16 A f25 CON DIMENSI ON D = 30 Y 300.000 EVALUACIONES DE LA FUNCI ON OBJETIVO
No Ejecuci n o 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. 1a (Mejor) 7a 13a (Mediana) 19a 25a (Peor) Media Des. Tip. f16 2,66E+02 2,94E+02 3,18E+02 3,30E+02 4,29E+02 3,27E+02 4,56E+01 2,08E+02 2,21E+02 2,46E+02 2,59E+02 3,37E+02 2,52E+02 3,66E+01 3,82E+01 1,73E+02 2,01E+02 2,17E+02 2,93E+02 1,87E+02 7,11E+01 f17 3,01E+02 3,41E+02 3,72E+02 4,44E+02 4,86E+02 3,84E+02 5,79E+01 2,43E+02 2,61E+02 2,74E+02 3,01E+02 3,76E+02 2,91E+02 4,21E+01 6,40E+01 2,21E+02 2,27E+02 2,48E+02 3,25E+02 2,22E+02 6,59E+01 f18 9,07E+02 9,18E+02 9,27E+02 9,35E+02 9,37E+02 9,26E+02 9,44E+00 8,58E+02 8,63E+02 8,64E+02 8,65E+02 8,69E+02 8,64E+02 2,75E+00 8,35E+02 8,55E+02 8,59E+02 8,62E+02 8,65E+02 8,57E+02 8,08E+00 f19 9,05E+02 9,20E+02 9,24E+02 9,29E+02 9,48E+02 9,25E+02 9,37E+00 8,59E+02 8,62E+02 8,64E+02 8,66E+02 8,71E+02 8,64E+02 3,08E+00 8,27E+02 8,56E+02 8,58E+02 8,60E+02 8,62E+02 8,55E+02 8,57E+00 f20 9,92E+02 1,01E+03 1,05E+03 1,16E+03 1,27E+03 1,09E+03 1,00E+02 9,00E+02 9,00E+02 9,00E+02 9,00E+02 1,18E+03 9,40E+02 9,31E+01 9,00E+02 9,00E+02 9,00E+02 9,00E+02 1,18E+03 9,40E+02 9,31E+01 f21 5,20E+02 5,34E+02 5,51E+02 6,11E+02 1,00E+03 6,12E+02 1,43E+02 5,09E+02 5,09E+02 5,10E+02 5,10E+02 8,00E+02 5,33E+02 8,04E+01 5,09E+02 5,09E+02 5,10E+02 5,10E+02 8,00E+02 5,33E+02 8,04E+01 f22 6,36E+02 6,57E+02 7,30E+02 8,79E+02 9,05E+02 7,67E+02 1,09E+02 5,02E+02 5,04E+02 5,05E+02 5,50E+02 5,50E+02 5,21E+02 2,25E+01 5,00E+02 5,00E+02 5,01E+02 5,50E+02 5,50E+02 5,18E+02 2,43E+01 f23 5,22E+02 5,30E+02 5,41E+02 5,86E+02 8,44E+02 5,91E+02 1,03E+02 5,09E+02 5,10E+02 5,10E+02 5,10E+02 5,10E+02 5,10E+02 2,25E-01 5,09E+02 5,10E+02 5,10E+02 5,10E+02 5,10E+02 5,10E+02 2,24E-01 f24 4,38E+02 4,94E+02 5,56E+02 5,77E+02 6,92E+02 5,46E+02 6,67E+01 2,38E+02 2,42E+02 2,44E+02 2,47E+02 2,49E+02 2,44E+02 3,14E+00 2,32E+02 2,34E+02 2,34E+02 2,35E+02 2,35E+02 2,34E+02 7,55E-01 f25 4,14E+02 5,40E+02 5,88E+02 6,19E+02 7,00E+02 5,78E+02 7,44E+01 2,39E+02 2,43E+02 2,45E+02 2,47E+02 2,48E+02 2,45E+02 2,49E+00 2,32E+02 2,33E+02 2,34E+02 2,35E+02 2,37E+02 2,34E+02 1,34E+00

3E+03

3E+04

3E+05

nes de independencia, normalidad y heterocedasticidad requeridas para tal n. Debido al bajo n mero de algoritmos que comparau mos se ha utilizado el test no param trico de Ranking por e Signos de Wilcoxon [13], mediante el que comparamos DEPSO con cada uno de los algoritmos anteriormente citados. Este test es de una alternativa no param trica al e t-test por parejas. Su funcionamiento se basa en calcular el valor absoluto de la diferencia entre cada par de valores de la muestra, los resultados son ordenados de mayor a menor y se computa un ranking para determinar la posici n de cada diferencia, luego se determina el o signo de cada elemento del ranking de acuerdo al signo de la diferencia anterior y nalmente se computa la suma promedio de los ranking divididos en valores positivos R+ y negativos R. Si el p-valor calculado por el test es menor que el nivel de conanza adoptado (p-valor=0,05) se rechaza la hip tesis nula y el algoritmo asociado al o mayor de los valores es el mejor.

TABLA VI C OMPARACI ON DE DEPSO CONTRA G-CMA-ES, DE, K-PCX POR LA P RUEBA N O PARAM E TRICA DE R ANKING POR S IGNOS CONSIDE UN O LOS VALORES DE ERROR MEDIO PARA 10 Y 30 DIMENSIONES Y 95 % DE NIVEL DE CONFIANZA ( P - VALOR =0,05)
Algoritmo G-CMA-ES DE K-PCX Dimensi n o 10 30 10 30 10 30 R+ 111 103 102 82 66 111 R 79 107 108 128 144 79 p-valor 0,520 0,940 0,911 0,391 0,145 0,520

En la Tabla VI, se muestran los resultados de aplicar el test no param trico de Ranking por Signos en la compae raci n de los resultados de nuestra propuesta (DEPSO) o con los tres algoritmos a comparar: G-CMA-ES, DE y K-PCX, en las dimensiones 10 y 30. Al comparar dos algoritmos, por ejemplo DEPSO con G-CMA-ES, el valor

437

Metaheursticas, Algoritmos Evolutivos y Bioinspirados para Problemas de Optimizacin Continua

Funciones f f 10
4

10

(Dimensin 30) 10 f
6
6

Funciones f f
8

11

15

(Dimensin 30) f
11

10

12

13

14

15

Error (f(x) f(x*))

10

Error (f(x) f(x*)) 0 1 2 Nmero de Evaluaciones Funciones f16 f20 (Dimensin 30) f
16

10

10

3 x 10
5

10

1 2 Nmero de Evaluaciones Funciones f21 f25 (Dimensin 30) f

21

3 x 10
5

10

17

18

19

10

20

22

23

24

25

Error (f(x) f(x*))

10

Error (f(x) f(x*)) 1 2 Nmero de Evaluaciones 3 x 10

5

10

10

10

1 2 Nmero de Evaluaciones

3 x 10
5

Fig. 1 T RAZAS DE LA EJECUCI ON N UMERO 13 ( MEDIANA ) DE DEPSO SOBRE LAS FUNCIONES DEL BENCHMARK CON DIMENSI ON D = 30 EN I LAS QUE SE MUESTRA EL MEJOR ERROR EN ESCALA LOGAR TMICA EN CADA EVALUACI ON DE FUNCI ON

R+ indica el ranking promedio donde el algoritmo GCMA-ES obtiene valores de error medio (f (x) f (x )) inferiores al algoritmo DEPSO. Por otro lado, R muestra el ranking promedio donde el algoritmo DEPSO obtiene valores de error medio inferiores a G-CMA-ES. Como se puede observar en la Tabla VI, para dimensi n 10, o DEPSO obtiene mejor ranking promedio que DE y KPCX. Para dimensi n 30, DEPSO obtiene mejor ranking o promedio que G-CMA-ES y DE. No obstante, en ning n u caso se rechaza la hip tesis nula por lo que estadsticao mente no se puede asegurar que existan diferencias entre los resultados. A continuaci n, pasamos a comparar directamente o las medias de los resultados nales de DEPSO (tablas II, III, IV y V) con las medias nales de los algoritmos de CEC05. En la Tabla VII se resume un listado de los algoritmos a los que DEPSO consigue batir respecto a cada funci n del benchmark, indicando en las columnas o 3 y 5 las posiciones p en las que resulta DEPSO respecto a los algoritmos comparados (Alg. CEC05). As, por ejemplo, para la funci n f15 , DEPSO consigue mejores o resultados que DE, K-PCX y G-CMA-ES en dimensi n o 10 (p = 1) y mejores resultados que DE y K-PCX en dimensi n 30 (p = 2). De este modo, se puede observar o c mo para dimensi n 10, DEPSO obtiene los mejores reo o sultados para 6 funciones y los peores resultados s lo pao ra 4 funciones (smbolo - ). Para dimensi n 30, DEPSO o consigue los mejores resultados para 3 funciones, consigue batir a al menos 2 algoritmos en 6 funciones y no consigue mejorar los resultados tan s lo en 3. o

Respecto a DEPSO en particular, a partir de la funci n o f14 hasta la f25 (exceptuando tres casos) consigue un mejor comportamiento, lo que lleva a pensar que sobre las funciones compuestas el rendimiento es mayor que sobre las funciones simples. Este comportamiento no se observa sin embargo en G-CMA-ES, considerado el mejor algoritmo hasta el momento. Otra interesante observaci n o reside en la mejora que aporta la hibridaci n de DE con o PSO sobre el algoritmo DE b sico, ya que para dimena si n 10, DEPSO es mejor que DE en 11 de las 20 funcioo nes consideradas y para dimensi n 30 DEPSO es mejor o que DE en 13 de las 20 funciones consideradas.
TABLA VII F UNCIONES PARA LAS QUE DEPSO OBTIENE MEJORES
RESULTADOS QUE LOS ALGORITMOS MENCIONADOS

Func. f6 f7 f8 f9 f10 f11 f12 f13 f14 f15 f16 f17 f18 f19 f20 f21 f22 f23 f24 f25

Dimensi n 10 o Alg. CEC05 DE DE, K-PCX DE DE K-PCX K-PCX DE, K-PCX, C-MA-ES DE, K-PCX, C-MA-ES DE K-PCX DE, K-PCX, C-MA-ES DE, K-PCX, C-MA-ES C-MA-ES DE, K-PCX, C-MA-ES K-PCX DE, K-PCX, C-MA-ES

p 3 2 3 4 3 3 3 4 1 1 3 4 3 4 1 1 3 1 3 1

Dimensi n 30 o Alg. CEC05 DE, K-PCX K-PCX DE DE, K-PC C-MA-ES DE DE, K-PCX, C-MA-ES DE, K-PCX DE DE, C-MA-ES DE, C-MA-ES DE, C-MA-ES K-PCX DE, K-PCX, C-MA-ES DE, K-PCX, C-MA-ES C-MA-ES DE

p 2 3 3 4 4 2 3 3 1 2 3 2 2 2 4 3 1 1 3 3

438

VI Congreso Espaol sobre Metaheursticas, Algoritmos Evolutivos y Bioinspirados (MAEB'09)

V. C ONCLUSIONES En este trabajo se propone el uso de una nueva t cnie ca metaheurstica llamada DEPSO, mediante la que se combinan las estrategias de b squeda y operadores preu sentes en los algoritmos PSO y DE. Tras su evaluaci n o se consiguen mejoras sobre los resultados existentes en el estado del arte. Para ello, seguimos el marco experimental propuesto en la sesi n especial de optimizaci n o o continua de MAEB09 y se realizan comparaciones estadsticas con otros tres algoritmos: G-CMA-ES, DE y K-PCX, tomados a su vez de la sesi n especial de optio mizaci n continua de CEC05. Los resultados obtenidos o muestran un alto grado de competitividad de nuestra propuesta, superando para un buen n mero de las instancias u los resultados de algoritmos como CMA-ES que en la actualidad constituyen la referencia en el estado del arte. Como trabajo futuro se pretende evaluar DEPSO y nuevas hibridaciones de metaheursticas bioinspiradas con el mismo y nuevos benchmark de funciones utilizando espacios de variables de mayores dimensiones: 50, 100, 500 y 1.000 variables, as como realizar comparati vas con nuevos algoritmos encontrados en el estado del arte. Parte de este trabajo ya se est realizando para el a benchmark de funciones continuas de CEC08 [14], estableciendo comparativas con los algoritmos presentados en dicha sesi n especial. o AGRADECIMIENTOS Enrique Alba y Jos Manuel Garca-Nieto est n pare a cialmente nanciados por el CICE, Junta de Andaluca bajo contrato P07-TIC-03044 (Proyecto DIRI COM, [Link] J. Apolloni agradece a la Universidad de M laga, Espa a y a la Agencia Esa n pa ola de Cooperaci n Internacional y Desarrollo por la n o beca de investigaci n MAEC (BOE 157/2008). o R EFERENCIAS
[1] [2] [3] J. Kennedy and R. Eberhart, Particle swarm optimization, Neural Networks, Piscataway, NJ., Proceedings of IEEE International Conference on, pp. 19421948, 1995. K. V. Price, R. Storn, and J. Lampinen, Differential Evolution: A practical Approach to Global Optimization, Springer-Verlag, London, UK, 2005. F. Herrera and M. Lozano, Sesi n Especial en Metaheursticas, o Algoritmos Evolutivos y Bioinspirados para Problemas de Optimizaci n Continua, [online] [Link] Continuo/[Link], Feb 2009. A. Auger and N. Hansen, A restart cma evolution strategy with increasing population size, IEEE Congress on Evolutionary Computation, vol. 2, pp. 17691776, 2005. J. Ronkkonen, S. Kukkonen, and K.V. Price, Real-parameter optimization with differential evolution, IEEE Congress on Evolutionary Computation, vol. 1, pp. 506513, 2005. Ankur Sinha, Santosh Tiwari, and Kalyanmoy Deb, A population-based, steady-state procedure for real-parameter optimization, IEEE Congress on Evolutionary Computation, vol. 1, pp. 514521, 2005. P.N. Suganthan, N. Hansen, J. J. Liang, K. Deb, Y.-P. Chen, A. Auger, and S. Tiwari, Problem denitions and evaluation criteria for the cec 2005 special session on real-parameter optimization, Tech. Rep., Nanyang Technological University, 2005. R. Eberhart and Y. Shi, Comparing Inertia Weights and Constriction Factors in Particle Swarm Optimization, in Proceedings of the International Congress on Evolutionary Computation, July 2000, vol. 1, pp. 8488. [9] [10] R. Storn and K. V. Price, Differential evolution - a simple and efcient adaptive scheme for global optimization over continuous spaces, Tech. Rep., TR-95012-ICSI, 1995. Swagatam Das, Ajith Abraham, and Amit Konar, Particle swarm optimization and differential evolution algorithms: Technical analysis, applications and hybridization perspectives, In Advances of Computational Intelligence in Industrial Systems, 2008. E. Alba and MALLBA Group, Mallba: A Library of Skeletons for Combinatorial Optimisation, in Proceedings of the EuroPar, B. Monien and R. Feldmann, Eds., 2002, vol. LNCS 2400, pp. 927932. S. Garca, D. Molina, M. Lozano, and F. Herrera, An experimen tal study about the use of non-parametric tests for analysing the behaviour of evolutionary algorithms in optimization problems, in MAEB 2007 (V Congreso espa ol de Metaheursticas, Algoritn mos Evolutivos y Bioinspirados), 2007, pp. 275285. R. Wilcox, New statistical procedures for the social sciences, Hillsdale, 1987. K. Tang, X. Yao, P.N. Suganthan, C. MacNish, Y. P. Chen, C. M. Chen, , and Z. Yang, Benchmark Functions for the CEC2008 Special Session and Competition on Large Scale Global Optimization, Tech. Rep., Nature Inspired Computation and Applications Laboratory, USTC, China, November 2007.

[11]

[12]

[13] [14]

[4] [5] [6]

[7]

[8]

439

Metaheursticas, Algoritmos Evolutivos y Bioinspirados para Problemas de Optimizacin Continua

440