Algoritmos de optimización de la población: Enjambre de partículas (PSO)
416
0
Forman enjambres separados, gracias a esto pueden estar al sol,
o se mueven tras las nubes de tormenta, es posible que extraigan energía de las descargas atmosféricas.
Pero en un momento de peligro o, de una forma más amplia, en un cambio repentino que amenaza su existencia, se unen...
Stanislav Lem "El Invencible"
Contenido:
- Introducción
- Principios del algoritmo
- Implementación clásica
- Versión modificada
- Resultados de la prueba
1. Introducción
Probablemente haya bastantes personas que han leído el maravilloso éxito de ventas de ciencia ficción de Stanislaw Lem, «El Invencible». Resulta sorprendente que una de las primeras descripciones de la inteligencia de "enjambre" nació precisamente con el lanzamiento de esta novela de ciencia ficción. La historia trata sobre robots que han sobrevivido sin centralización del control; además, han sobrevivido los especímenes más simples y más adaptados, no los más complejos, inteligentes y poderosos, sino los más numerosos y flexibles.
En el transcurso de miles de años de necroevolución, estos autómatas han aprendido a luchar de forma efectiva con competidores que los superaban tanto en inteligencia como en términos de disponibilidad de energía, y han tenido que luchar no solo con otros robots, sino también contra el mundo viviente del planeta, y han vencido. Los elementos de fantasía de esta obra se pueden comparar directamente y con toda certeza con la acción de la propia naturaleza y la evolución.
Desde tiempos inmemoriales, la gente se ha interesado por el comportamiento grupal de los animales, el llamado comportamiento de enjambre, sobre cómo funcionan las aves cuando una bandada vuela hacia países cálidos, cómo un enjambre de abejas consigue su alimento, cómo sobrevive una colonia de hormigas, creando estructuras complejas, o cómo se comporta un banco de peces, porque su comportamiento está muy sincronizado. La organización de los individuos en la sociedad, como en presencia de una sola mente controladora -a pesar de la descentralización del control-, ciertos patrones de un organismo integral bien coordinado, así como las relaciones observadas en la naturaleza fomentan la creación y el desarrollo de nuevas ideas en el campo de la optimización algorítmica.
La inteligencia de enjambre (Swarm intelligence) describe la simulación del comportamiento colectivo de un sistema autoorganizado. Existe un número bastante elevado de algoritmos semejantes. En la versión canónica, escrita en 1995 por Kennedy (J.Kennedy) y Eberhart (R.Eberhart), el modelo subyacente a este método se obtuvo simplificando el modelo de Reynolds. Como resultado de esta simplificación, los individuos individuales de la población comenzaron a representarse como objetos separados carentes de tamaño, pero poseedores de cierta velocidad.
Debido a la extrema similitud con las partículas materiales, los objetos simples resultantes comenzaron a llamarse partículas, y su población, enjambres. En cada momento temporal (en cada iteración) las partículas tienen un cierto vector de posición y una velocidad en el espacio. Para cada posición de la partícula, se calcula el valor correspondiente de la función objetivo, y sobre esta base, según ciertas reglas, las partículas cambian su posición y velocidad en el espacio de búsqueda; al determinar la siguiente posición de la partícula, se tiene en cuenta la información sobre la mejor posición entre todas las demás partículas vecinas, correspondiente a las tareas de la función de aptitud.
Ejemplos de algoritmos de enjambre:
- Método de enjambre de partículas
- Algoritmo de colonia de hormigas
- Algoritmo de colonia de abejas
- Sistema inmunológico artificial
- Algoritmo de lobo gris
- Algoritmo de murciélago
- Algoritmo de búsqueda gravitacional
- Algoritmo de altruismo
- Y muchos otros
La transición del modelado del comportamiento colectivo a la optimización colectiva se basa en la siguiente idea biológica: los organismos se unen en colonias para mejorar sus condiciones de vida; cada organismo de la colonia, de media, tiene más posibilidades de sobrevivir en la lucha contra los depredadores; la colonia puede buscar, procesar y almacenar alimentos con mayor eficiencia en comparación con los individuos por separado, etc. En otras palabras, cualquier colonia de organismos durante todo el tiempo de su existencia, y con diferentes grados de eficiencia, resuelve varios problemas de optimización, por ejemplo: maximizar la cantidad de alimentos y minimizar las pérdidas provocadas por los depredadores. Estas consideraciones formaron la base para la construcción de diversos métodos de optimización matemática.
El enjambre de partículas es uno de los algoritmos de optimización más famosos y populares desde sus inicios. Los autores de muchas de sus implementaciones afirman que el algoritmo resulta muy efectivo para optimizar funciones complejas con muchos argumentos e incluso es adecuado para entrenar redes neuronales.
En este artículo, trataremos de averiguar si el algoritmo resulta tan bueno para resolver problemas complejos. En la versión clásica del algoritmo y en muchas de sus modificaciones, existen importantes limitaciones vinculadas al hecho de que la función optimizada debe ser suave y continua, es decir, resulta completamente inadecuada para funciones discretas. No obstante, precisamente como pretendíamos en la serie de artículos, todos los algoritmos en consideración se cambiarán de tal forma (si hay alguna restricción) que sus deficiencias queden eliminadas, o al menos de manera que los algoritmos funcionen de forma puramente técnica, es decir, todos los algoritmos deberán mostrarse indiferentes a la suavidad de las funciones (como en los problemas de los tráders) y no tener restricciones en cuanto al paso de los argumentos.
2. Principios del algoritmo
Como el artículo anterior fue el principal artículo introductorio al mundo de la optimización, no abarcó el principio de interacción del programa principal (EA, script, indicador) con el núcleo del algoritmo de optimización, pero debemos prestar atención a esto, porque, en cualquier caso, los lectores atentos se harán la siguiente pregunta: ¿por qué los algoritmos y los programas de ejemplo se escriben de esa manera? En el dominio público, las versiones existentes de los algoritmos de optimización se construyen de forma que el algoritmo se refiera a la función de aptitud como a un objeto externo a él, mientras que él mismo constituye el principal programa ejecutable.
La figura 1, que vemos a continuación, muestra un esquema en el que el algoritmo transmite los parámetros optimizados a la función de aptitud y obtiene el valor de adecuación (criterio de evaluación). Este esquema resulta incómodo a la hora de construir un programa para que los usuarios resuelvan problemas, en particular es incómodo para los tráders. ¿Por qué? Porque no podemos llamar, por ejemplo, una pasada del simulador por la historia.
Figura 1. Esquema de interacción entre el algoritmo PSO y la función de aptitud.
Mucho más cómodo resulta el esquema mostrado en la Figura 2, en el que el algoritmo de optimización no es un programa independiente, sino un módulo separado o "caja negra". Este módulo contiene los parámetros min, max, step para cada argumento optimizado. El programa MQL recibe los argumentos optimizados tras solicitarlos, retornando luego los valores de adecuación o, en otras palabras, los valores de la función de aptitud. Este esquema permite crear una gama de soluciones muy flexibles, desde el uso de la optimización automática en asesores expertos hasta la creación de un administrador de optimización personalizado.
Figura 2. Esquema de interacción entre el programa MQL y PSO.
Mención aparte merece la organización de llamadas a los métodos de los algoritmos de optimización (bloque MQL en la Fig. 2), que podemos representar usando un esquema general que es el mismo para todos los algoritmos de optimización (AO), de la forma siguiente:
Inicialización_AO_0
Ciclo de iteraciones (épocas)
{
1) Método_AO_1
2) Obtención de valores de adecuación para cada variante de los parámetros optimizados
3) Método_AO_2
}
De esta forma, vemos que solo se utilizan tres métodos públicos: Inicialización_AO_0, Método_AO_1 y Método_AO_2. Esto ya resulta suficiente para organizar el proceso de optimización en proyectos personalizados de cualquier complejidad.
El esquema de trabajo del PSO en sí se muestra en la Figura 3 e incluye los siguientes pasos lógicos:
- Generación de partículas aleatorias (primera iteración)
- Obtención del valor de adecuación para cada partícula
- Obtención del valor de adecuación para todas las partículas en general
- Ajuste de velocidad de las partículas
- Punto de interrupción, o vuelta al paso 2
- Finalización del programa.
Figura 3. Esquema de trabajo del PSO.
Vamos a analizar el algoritmo de Particle Swarm con más detalle.
El sistema de inteligencia de enjambre está formado por muchas partículas que interactúan entre sí y con el entorno. Cada partícula sigue reglas simples, aunque no existe un sistema para controlar el comportamiento centralizado que le diga qué hacer a cada una, las interacciones locales y aleatorias entre ellas provoca la aparición de comportamientos grupales inteligentes que no están controlados por individuos.
Si realizamos una analogía con una bandada, entonces podremos decir que todas las partículas deben realizar tareas simples:
- evitar el cruce con otras partículas;
- ajustar su velocidad según las velocidades de las partículas circundantes;
- intentar mantener una distancia bastante pequeña entre sí mismo y el entorno.
El algoritmo de PSO comienza con la inicialización de la población. El segundo paso consiste en calcular los valores de adecuación de cada partícula, después de lo cual se actualizarán las mejores puntuaciones individuales y globales; luego se actualizarán la velocidad y la posición de las partículas. Cuando usamos el PSO, una posible solución al problema de la optimización numérica está representada por la posición de la partícula. Además, cada partícula tiene una velocidad de actual que refleja su magnitud y dirección absolutas hacia una solución/posición nueva, supuestamente mejor.
La partícula también almacena su valor de adecuación, la posición actual, la posición mejor conocida (es decir, la posición anterior con la adecuación más conocida) y la adecuación de la posición mejor conocida. Los pasos del dos al cuatro se repiten hasta que se cumpla la condición de finalización. En la primera iteración, todas las partículas se dispersan para encontrar la mejor solución (exploración). Cada partícula es valorada; luego se encuentran las mejores soluciones para la topología de vecindad y se actualizan las mejores partículas personales y globales para cada miembro del enjambre. La convergencia se logrará atrayendo todas las partículas a la partícula con la mejor solución.
Aunque, en esencia, el algoritmo de PSO es bastante simple, deberemos comprenderlo para poder modificar el código de este artículo según nuestras necesidades. El PSO es un proceso iterativo. En cada iteración en el ciclo de procesamiento principal, primero se actualiza la velocidad actual de cada partícula; en este caso, se tienen en cuenta la velocidad actual de la partícula, la información local de la partícula y la información global del enjambre. La posición de cada partícula luego se actualiza utilizando el valor de la nueva velocidad de esa partícula.
Matemáticamente, estas dos ecuaciones de actualización de coordenadas de partículas tienen el aspecto siguiente:
v(t+1) = w * v(t) + c1 * rp * (p(t) – x(t)) + (c2 * rg * (g(t) – x(t))
x(t+1) = x(t) + v(t+1)
El proceso de actualización de la posición es en realidad mucho más simple que las ecuaciones sugeridas. La primera ecuación sirve para actualizar la velocidad de la partícula.
El término v(t+1) indica la velocidad en el momento t+1. La nueva velocidad depende de tres términos.
- El primer término: w * v(t). El factor w se denomina fracción ponderal de inercia y es simplemente una constante; v(t) es la velocidad actual en el momento t.
- El segundo término: c1 * rp * (p(t) - x(t)). El factor c1 es una constante denominada fracción ponderal cognitiva (o personal o local). El multiplicador rp supone una variable aleatoria en el rango [0, 1]. La magnitud vectorial p(t) es la mejor posición de la partícula encontrada hasta ahora, y la magnitud vectorial x(t) es la posición actual de la partícula.
- El tercer término: actualización de la velocidad c2 * rg * (g(t) - x(t). El factor c2 es una constante llamada fracción de peso social (o global). El multiplicador rg supone una variable aleatoria en el rango [0, 1]. El valor del vector g(t) es la posición mejor conocida encontrada hasta ahora de cualquiera de las partículas en el enjambre. Una vez determinada la nueva velocidad, v(t+1), se utiliza para calcular la nueva posición x(t+1) de la partícula.
3. Implementación clásica
La unidad lógica que describe un conjunto de coordenadas en el espacio (parámetros optimizados) es una partícula que se puede representar como una estructura, donde c[] son las coordenadas de la partícula, cB[] son las mejores coordenadas de la partícula para todas las iteraciones , v[] es la velocidad para cada una de las coordenadas de la partícula, ff es el valor de adecuación actual de la partícula, y ffB es el mejor valor de adecuación de la partícula para todas las iteraciones. En el constructor de la estructura de partículas, inicializamos los valores de ff y ffB con el mínimo valor posible que pueda ser representado por el tipo double, ya que el algoritmo está diseñado para encontrar el máximo de la función (para encontrar el mínimo, bastará con añadir un signo "-" antes del valor de adecuación resultante).
//—————————————————————————————————————————————————————————————————————————————— struct S_Particles { public: double c []; //coordinates double cB []; //best coordinates double v []; //velocity double ff; //the value of the fitness function double ffB; //best value fitness function S_Particles () { ff = -DBL_MAX; ffB = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
En realidad, escribiremos el propio algoritmo de PSO como una clase en la que solo habrá tres métodos públicos, InitPS (), Preparation () y Dwelling () (Inicialización_АО_0, Método_АО_1 y Método_АО_2). De los métodos privados, GenerateRNDparticles () y ParticleMovement () son exclusivos de PSO, y ya hemos analizado el resto en el artículoanterior. El array de estructuras p[] es un enjambre de partículas. Además del hecho de que cada partícula tenga valores de adecuación, sus coordenadas y mejores coordenadas, el enjambre en su conjunto tiene las mejores coordenadas cB y el mejor valor de adecuación ffB.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_PSO { public: //---------------------------------------------------------------------------- S_Particles p []; //particles double rangeMax []; //maximum search range double rangeMin []; //manimum search range double rangeStep []; //step search double cB []; //best coordinates double ffB; //FF of the best coordinates void InitPS (const int params, //number of opt. parameters const int size, //swarm size const double inertiaP, //inertia const double selfBoostP, //boost const double groupBoostP); //group boost void Preparation (); void Dwelling (); private: //---------------------------------------------------------------------------- int swarmSize; //swarm size int parameters;//number of optimized parameters double inertia; double selfBoost; double groupBoost; bool dwelling; void GenerateRNDparticles (); void ParticleMovement (); double SeInDiSp (double in, double inMin, double inMax, double step); double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
El método InitPS () está diseñado para inicializar el algoritmo antes de comenzar la optimización (en el esquema Initialization_АО_0), en él asignamos los valores de los argumentos del método a los miembros privados y establecemos el tamaño del enjambre y los parámetros internos de cada partícula en el mismo.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::InitPS (const int paramsP, const int sizeP, const double inertiaP, const double selfBoostP, const double groupBoostP) { ffB = -DBL_MAX; parameters = paramsP; swarmSize = sizeP; ArrayResize (rangeMax, parameters); ArrayResize (rangeMin, parameters); ArrayResize (rangeStep, parameters); dwelling = false; inertia = inertiaP; selfBoost = selfBoostP; groupBoost = groupBoostP; ArrayResize (p, swarmSize); for (int i = 0; i < swarmSize; i++) { ArrayResize (p [i].c, parameters); ArrayResize (p [i].cB, parameters); ArrayResize (p [i].v, parameters); } ArrayResize (cB, parameters); } //——————————————————————————————————————————————————————————————————————————————
El método Preparation () se llama primero en cada iteración (época) (Método_AO_1). El método es simple, pero también muy importante. Dependiendo de si el método se llama en la primera época o en las posteriores (se determina con la bandera dwelling), el valor de adecuación del enjambre se restablecerá y se creará una población de enjambre aleatoria, o las partículas se desplazarán a nuevas coordenadas.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::Preparation () { if (!dwelling) { ffB = -DBL_MAX; GenerateRNDparticles (); dwelling = true; } else ParticleMovement (); } //——————————————————————————————————————————————————————————————————————————————
En el método GenerateRNDparticles(), se genera una población de enjambre aleatoria; las partículas tienen coordenadas aleatorias en el rango especificado para cada una de ellas y una velocidad aleatoria para cada una de las coordenadas.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::GenerateRNDparticles () { for (int s = 0; s < swarmSize; s++) { for (int k = 0; k < parameters; k++) { p [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]); p [s].c [k] = SeInDiSp (p [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); p [s].cB [k] = p [s].c [k]; p [s].v [k] = RNDfromCI (0.0, (rangeMax [k] - rangeMin [k]) * 0.5); } } } //——————————————————————————————————————————————————————————————————————————————
En el método ParticleMovement () se lleva a cabo el algoritmo de movimiento de las partículas a nuevas posiciones: para ello será necesario calcular la velocidad para cada coordenada según la fórmula anterior. No sé por qué se usa el término "velocidad", pues se trata básicamente de un valor de desplazamiento, o en otras palabras, de la diferencia entre dónde se encuentra la partícula en este momento y a dónde debería desplazarse. Tras calcular esta diferencia para cada una de las coordenadas, simplemente sumaremos a los valores actuales. Después de eso, verificaremos la inadmisibilidad de ir más allá de los límites mínimos/máximos de los parámetros optimizados (para una partícula, hablamos de coordenadas) con un paso dado.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::ParticleMovement () { double rp; //random component of particle movement double rg; double velocity; double posit; double positBest; double groupBest; for (int i = 0; i < swarmSize; i++) { for (int k = 0; k < parameters; k++) { rp = RNDfromCI (0.0, 1.0); rg = RNDfromCI (0.0, 1.0); velocity = p [i].v [k]; posit = p [i].c [k]; positBest = p [i].cB [k]; groupBest = cB [k]; p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit); p [i].c [k] = posit + p [i].v [k]; p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); } } } //——————————————————————————————————————————————————————————————————————————————
El método Dwelling () es el tercer método público del algoritmo utilizado por el usuario en su programa para realizar la optimización (según el esquema Method_АО_2). El propósito del método es actualizar las mejores coordenadas y valores de adecuación de cada partícula en relación con su rendimiento anterior, y también actualizar, si fuera necesario, la adecuación del enjambre y las mejores coordenadas del enjambre. El método se llamará después de obtener los valores de adecuación en el ciclo de iteraciones.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::Dwelling () { for (int i = 0; i < swarmSize; i++) { //remember the best position for the particle if (p [i].ff > p [i].ffB) { p [i].ffB = p [i].ff; for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k]; } if (p [i].ff > ffB) { ffB = p [i].ff; for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k]; } } } //——————————————————————————————————————————————————————————————————————————————
Función para discretizar un número double con un paso dado dentro del rango especificado.
//—————————————————————————————————————————————————————————————————————————————— // Choice in discrete space double C_AO_PSO::SeInDiSp (double in, double inMin, double inMax, double step) { if (in <= inMin) return (inMin); if (in >= inMax) return (inMax); if (step == 0.0) return (in); else return (inMin + step * (double)MathRound ((in - inMin) / step)); } //——————————————————————————————————————————————————————————————————————————————
Función para obtener un número double aleatorio en un rango dado.
//—————————————————————————————————————————————————————————————————————————————— // Random number generator in the custom interval double C_AO_PSO::RNDfromCI (double min, double max) { if (min == max) return (min); double Min, Max; if (min > max) { Min = max; Max = min; } else { Min = min; Max = max; } return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0))); } //——————————————————————————————————————————————————————————————————————————————
Se acabó la teoría, vamos a pasar a la práctica.
Como utilizaremos el mismo esquema para construir algoritmos que en el primer artículo del ciclo (y lo seguiremos haciendo en el futuro), descrito en la Fig. 2, no nos resultará difícil conectar el algoritmo al banco de pruebas.
Al ejecutar el banco de pruebas, veremos animaciones similares a las mostradas a continuación. En este caso, podemos ver claramente cómo se comporta un enjambre de partículas. El enjambre de verdad se comporta como un enjambre en la naturaleza. En el mapa de calor de la función, se desplaza en forma de nube densa.
Permítanme recordarles que el círculo negro destaca el óptimo global (máximo) de la función, mientras que el punto negro indica las mejores coordenadas promedio del algoritmo de búsqueda obtenidas en el momento de la iteración actual. Vamos a explicar de dónde proceden los valores promedio. En cuanto a sus coordenadas, el mapa de calor es bidimensional, y la función optimizada puede incluir cientos de variables (medidas); por consiguiente, el resultado se promediará sobre las coordenadas.
PSO en la función de prueba Skin.
PSO en la función de prueba Forest.
PSO en la función de prueba Megacity.
Como podemos ver en la animación, las pruebas muestran que el PSO se las arregla bastante bien con la primera función suave, pero solo al optimizar dos variables con un aumento en la dimensionalidad del espacio de búsqueda, la eficiencia del algoritmo desciende bruscamente; esto resulta especialmente notable en las funciones segunda y tercera discreta. Los resultados son sustancialmente peores que el algoritmo aleatorio descrito en el artículo anterior. Más tarde regresaremos a los resultados y los discutiremos con detalle al formar una tabla comparativa de resultados.
Viendo cómo el famoso algoritmo de PSO pierde vergonzosamente ante uno aleatorio, surge el deseo de darle al algoritmo una segunda oportunidad: la revancha. En el siguiente apartado del artículo, intentaremos modificar el algoritmo de PSO.
4. Versión modificada
A nuestro juicio, las debilidades del PSO son:
1) Necesariamente, con una probabilidad casi igual a 1, todas las coordenadas serán cambiadas. Esto significa que cada partícula del enjambre, en cada iteración, oscilará, en el mejor de los casos, en algún lugar del extremo local de la región global y, en el peor de los casos, nunca llegará exactamente al punto del extremo global. De aquí se deriva un rasgo característico del algoritmo: el atascamiento en los extremos locales, es decir, la mala convergencia.
2) No funciona bien con funciones discretas, en parte a causa del primer defecto. Las coordenadas de las partículas saltan a las "áreas" más cercanas de la superficie de la función optimizada, no pudiendo estudiar con detalle la vecindad de ningún extremo local.
3) La débil capacidad del algoritmo para explorar nuevas áreas. El enjambre se concentra en un solo lugar indeterminado y no intenta salir del "pozo" local. En la bibliografía al respecto se mencionan intentos de implementar una modificación de enjambres múltiples, pero dejándose abiertas las cuestiones relativas a la optimización de funciones multivariables complejas, ya que el principio de distancia mutua no queda claro, porque no solo se debe cumplir el principio de movimiento conjunto, sino también la posibilidad de repulsión mutua, de lo contrario, desaparecerá el sentido en tal implementación, porque los enjambres individuales simplemente convergerán en un área o punto. Y para optimizar funciones simples de una o dos variables, no habrá que preocuparse en absoluto de esto, ya que tales tareas se realizarán usando los métodos más simples con una excelente convergencia.
Ahora que hemos identificado los defectos específicos del PSO, ¿qué podemos hacer para mejorarlo?
La respuesta es obvia (aunque no necesariamente cierta): necesitamos transmitir a las partículas las mejores coordenadas individuales de otras partículas. Cuanto mejores sean las coordenadas generales de la partícula "donante", mayor será la probabilidad de transmitir las coordenadas. En la Figura 4 se muestra de forma esquemática el cambio en la probabilidad de selección de una partícula. Así, generaremos un número aleatorio de 0 a 1, luego transformaremos el número resultante con una función parabólica y lo escalaremos al rango de números ordinales de las partículas en el enjambre de 0 a SwarmSize-1. Para hacer esto, deberemos introducir un parámetro adicional para el PSOm (le daremos ese nombre al algoritmo modificado): la probabilidad de copiar una coordenada, y también deberemos clasificar el enjambre para que cuanto mejor sea la partícula, más cerca se encuentre respecto al índice 0.
Figura 4. Probabilidad de selección de partículas desplazada.
A continuación, modificaremos ligeramente el método ParticleMovement(). Y generaremos un número aleatorio [0;1], si el número resulta ser mayor que el parámetro copy. Luego realizaremos las operaciones habituales con la partícula (que describimos anteriormente con detalle), de lo contrario, copiaremos la coordenada de otra partícula con el índice elegido según la regla mostrada gráficamente en la Fig. 4 .
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSOm::ParticleMovement () { double rp; //random component of particle movement double rg; double velocity; double posit; double positBest; double groupBest; for (int i = 0; i < swarmSize; i++) { for (int k = 0; k < parameters; k++) { rp = RNDfromCI (0.0, 1.0); rg = RNDfromCI (0.0, 1.0); double rC = RNDfromCI (0.0, 1.0); if (rC > copy) { velocity = p [i].v [k]; posit = p [i].c [k]; positBest = p [i].cB [k]; groupBest = cB [k]; p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit); p [i].c [k] = posit + p [i].v [k]; p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); } else p [i].c [k] = p [GetPartcileAdress ()].cB [k]; } } } //——————————————————————————————————————————————————————————————————————————————
También deberemos cambiar el método Dwelling (). Luego añadimos una llamada a la función de clasificación SortParticles ().
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSOm::Dwelling () { for (int i = 0; i < swarmSize; i++) { //remember the best position for the particle if (p [i].ff > p [i].ffB) { p [i].ffB = p [i].ff; for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k]; } if (p [i].ff > ffB) { ffB = p [i].ff; for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k]; } } SortParticles (); } //——————————————————————————————————————————————————————————————————————————————
La función GetParticleAddress() posibilita que la dirección de la partícula se seleccione con una probabilidad desplazada hacia la mejor partícula.
//—————————————————————————————————————————————————————————————————————————————— //shift of probability in the smaller party (to an index 0) int C_AO_PSOm::GetParticleAdress () { double x = RNDfromCI (-1.0, 0.0); x = x * x; x = Scale (x, 0.0, 1.0, 0, swarmSize - 1); x = SeInDiSp (x, 0, swarmSize - 1, 1); return ((int)x); } //——————————————————————————————————————————————————————————————————————————————
La función SortParticles() supone una clasificación de burbujas normal.
//—————————————————————————————————————————————————————————————————————————————— //Sorting of particles void C_AO_PSOm::SortParticles () { //---------------------------------------------------------------------------- int cnt = 1; int t0 = 0; double t1 = 0.0; //---------------------------------------------------------------------------- // We will put indexes in the temporary array for (int i = 0; i < swarmSize; i++) { ind [i] = i; val [i] = p [i].ffB; //ffPop [i]; } while (cnt > 0) { cnt = 0; for (int i = 0; i < swarmSize - 1; i++) { if (val [i] < val [i + 1]) { t0 = ind [i + 1]; t1 = val [i + 1]; ind [i + 1] = ind [i]; val [i + 1] = val [i]; ind [i] = t0; val [i] = t1; cnt++; } } } // On the received indexes create the sorted temporary population for (int u = 0; u < swarmSize; u++) pT [u] = p [ind [u]]; // Copy the sorted array back for (int u = 0; u < swarmSize; u++) p [u] = pT [u]; } //——————————————————————————————————————————————————————————————————————————————
Función para escalar un número de un rango numérico a otro.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_PSOm::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX) { if (OutMIN == OutMAX) return (OutMIN); if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0)); else { if (In < InMIN) return (OutMIN); if (In > InMAX) return (OutMAX); return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN); } } //——————————————————————————————————————————————————————————————————————————————
5. Resultados de la prueba
Finalmente, vamos a resumir los resultados de la investigación de hoy. Por mucho que quisiéramos esperar buenos resultados, el algoritmo de PSO, por desgracia, no se ha justificado. Los estudios realizados han mostrado su débil convergencia para funciones discretas, con rupturas y con una gran cantidad de argumentos, incluso el intento de modificar el algoritmo ha carecido de éxito, los resultados han sido incluso peores que los de la implementación clásica.
El aumento del parámetro de copiado hasta valores cercanos a 0.8 todavía puede mostrar una convergencia instantánea, pero esto solo resulta así para la primera función suave en las pruebas y al mismo tiempo con solo dos argumentos, mientras que para las otras pruebas este parámetro solo empeora el resultados. La implementación clásica de PSO de alguna manera ha logrado distinguirse solo en la función Skin con 1000 argumentos, mientras que en las demás pruebas los resultados han sido mediocres.
El resultado final de la prueba ha sido de 0,47695 para la implementación clásica y 0,45144 para la modificada, respectivamente. Los resultados se muestran en la tabla de más abajo. El banco de pruebas permite seleccionar el número de repeticiones de prueba en la configuración (el valor por defecto es de 5), de modo que los lectores puedan obtener resultados estadísticamente más precisos poniendo este parámetro más alto si la potencia de la computadora lo permite.
| AO | Runs | Skin | Forest | Megacity (discrete) | Final result | ||||||
| 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | |||
| RND | 1000 | 0,98744 | 0,61852 | 0,49408 | 0,89582 | 0,19645 | 0,14042 | 0,77333 | 0,19000 | 0,14283 | 0,51254 |
| 10000 | 0,99977 | 0,69448 | 0,50188 | 0,98181 | 0,24433 | 0,14042 | 0,88000 | 0,20133 | 0,14283 | ||
| PSO | 1000 | 0,98436 | 0,72243 | 0,65483 | 0,71122 | 0,15603 | 0,08727 | 0,53333 | 0,08000 | 0,04085 | 0,47695 |
| 10000 | 0,99836 | 0,72329 | 0,65483 | 0,97615 | 0,19640 | 0,09219 | 0,82667 | 0,10600 | 0,04085 | ||
| PSOm | 1000 | 0,96678 | 0,64727 | 0,57654 | 0,80616 | 0,13388 | 0,06800 | 0,53333 | 0,08067 | 0,04211 | 0,45144 |
| 10000 | 0,99505 | 0,64986 | 0,57654 | 0,90401 | 0,18194 | 0,07104 | 0,74667 | 0,10400 | 0,04211 | ||
Para resumir todo lo anterior, podemos trazar una línea: El PSO tiende a provocar una convergencia rápida y prematura en los puntos óptimos medios, además de una convergencia lenta en el área de búsqueda mejorada (que posee una capacidad de búsqueda local deficiente). Dicho de forma aún más simple: el algoritmo es muy débil y no resulta adecuado para optimizar funciones complejas y más discretas, especialmente funciones con muchos argumentos.
Existen varios enfoques que se pueden utilizar para mejorar el PSO en general. El tamaño del enjambre es uno de los factores importantes. Un tamaño de enjambre más alto puede aumentar la probabilidad de una convergencia más rápida y precisa, pero a menudo, en problemas prácticos, existe un umbral en el número de ejecuciones permitidas de la función de adecuación, y aumentar el tamaño del enjambre solo reducirá proporcionalmente el número de épocas y, por lo tanto, reducirá las oportunidades de evolución del enjambre.
El segundo enfoque consiste en lograr un equilibrio entre la exploración y la explotación. Al comienzo de las iteraciones, un alto grado de inteligencia ofrecería una alta probabilidad de encontrar una solución cercana al óptimo global. Mientras tanto, al final de la iteración, un alto grado de explotación le daría a la partícula la oportunidad de encontrar la solución más precisa en el área prometedora. Una optimización general previa al enjambre usando otros métodos sería otra técnica a utilizar para mejorar el rendimiento subyacente del PSO, y se utiliza con bastante frecuencia en la actualidad. Asignar diferentes tareas u objetivos a cada subgrupo también puede incrementar la eficacia del PSO en tareas de objetivo múltiple.
Otro enfoque para mejorar el rendimiento del PSO consistiría en establecer los componentes constituyentes de la ecuación de velocidad (regulación dinámica de la velocidad). Tal enfoque puede enviar partículas en diferentes direcciones y posibilitar una convergencia más rápida hacia el óptimo global, pero esto es solo una suposición.Ventajas:
- El algoritmo es muy simple y poco exigente desde el punto de vista de los recursos informáticos; el código funciona a mucha velocidad, ya que la implementación clásica ni siquiera clasifica los arrays.
- Hace un buen trabajo con funciones suaves. Hasta ahora, el PSO es el líder indiscutible en la tabla de optimización de funciones suaves con muchos argumentos.
Desventajas:
- La baja calidad del estudio de la función optimizada, pues el algoritmo no puede aplicarse a la solución de problemas donde se requiere un conjunto de varias soluciones únicas.
- La baja velocidad y precisión de convergencia.
- La inadecuación para la optimización de funciones discretas.
- Prácticamente no resulta escalable.
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/11386
DoEasy. Elementos de control (Parte 22): SplitContainer. Cambiando las propiedades del objeto creado
Cómo construir un EA que opere automáticamente (Parte 06): Tipos de cuentas (I)
Cómo construir un EA que opere automáticamente (Parte 07): Tipos de cuentas (II)
Cómo construir un EA que opere automáticamente (Parte 05): Gatillos manuales (II)
- Aplicaciones de trading gratuitas
- 8 000+ señales para copiar
- Noticias económicas para analizar los mercados financieros
Usted acepta la política del sitio web y las condiciones de uso