Algoritmo de optimización Brain Storm - Brain Storm Optimization (Parte II): Multimodalidad
20
0
Contenido:
1. Introducción
En la primera parte de este artículo, nos sumergimos en el mundo de la optimización con el algoritmo BSO (Brain Storm Optimization), y desvelamos los principios básicos de esta innovadora técnica inspirada en la tormenta de ideas. No solo exploramos su estructura lógica, sino que también nos sumergimos en un debate sobre los métodos de clusterización, K-Means y K-Means++. El algoritmo BSO (Brain Storm Optimization) es un método de optimización que incluye las fases de generación y evaluación de ideas en actividades de grupo. Este algoritmo ha contribuido al campo de la optimización junto con las técnicas de clusterización. La clusterización identifica grupos de datos de elementos similares, lo cual ayuda al BSO a encontrar soluciones óptimas. El uso del método de mutación permite al algoritmo sortear obstáculos en el espacio de búsqueda de soluciones y hallar caminos más eficientes hacia el óptimo.
Ahora es el momento de pasar a la acción. En la segunda parte de nuestra investigación, nos sumergiremos en la aplicación práctica del algoritmo, hablaremos de la multimodalidad, realizaremos pruebas con el algoritmo y resumiremos los resultados.
2. Aplicación del algoritmo
Vamos a resumir brevemente los puntos clave de la lógica del algoritmo BSO:
- Clusterización.
- Desplazamiento de grupos.
- Selección de ideas de clústeres: centroides de clústeres o ideas de clústeres.
- Combinación de las ideas seleccionadas.
- Mutación de las ideas obtenidas en las etapas anteriores.
- Selección de ideas para los pasos 2, 3, 4. Colocación de las nuevas ideas en la población padre y clasificación de las mismas.
Vamos a proceder ahora a describir el código del algoritmo BSO.
Para ello, escribiremos la estructura de agente del algoritmo "S_BSO_Agent", que se utilizará para describir cada agente del algoritmo BSO.
1. La estructura contendrá los siguientes campos:
- c[] - array para almacenar las coordenadas del agente.
- f - variable para almacenar la puntuación del agente (aptitud).
- label - variable para almacenar la etiqueta de pertenencia al clúster.
2. Init - método de la estructura "S_BSO_Agent" que inicializa los campos de la estructura. Toma un argumento entero "coords", que se utiliza para redimensionar el array de coordenadas "c" mediante la función "ArrayResize".
3. f = -DBL_MAX - establece un valor inicial de la variable "f" igual al valor mínimo posible de un número de tipo double.
4. label = -1 - establece un valor inicial de la variable "label" igual a -1, lo cual significa que el agente no pertenece a ningún clúster.
Este código representa la estructura de datos básica para los agentes en el algoritmo de optimización BSO e inicializará sus campos al crearse un nuevo agente.
//—————————————————————————————————————————————————————————————————————————————— struct S_BSO_Agent { double c []; //coordinates double f; //fitness int label; //cluster membership label void Init (int coords) { ArrayResize (c, coords); f = -DBL_MAX; label = -1; } }; //——————————————————————————————————————————————————————————————————————————————
Los algoritmos de clusterización K-Means y K-Means++ ya se han descrito detalladamente en el artículo anterior, por lo que no nos detendremos en ellos aquí.
Vamos a pasar ahora a la descripción del código de la clase "C_AO_BSO", que es la sucesora de la clase básica de algoritmos poblacionales "C_AO" y contiene los siguientes campos y métodos:
1. Campos públicos:
- ao_name - nombre del algoritmo de optimización.
- ao_desc - descripción del algoritmo de optimización.
- ao_link - enlace a un artículo sobre el algoritmo de optimización.
- popSize - tamaño de la población.
- parentPopSize - tamaño de la población padre.
- clustersNumb - número de clústeres.
- p_Replace - probabilidad de sustitución.
- p_One - probabilidad de una sola elección.
- p_One_center - probabilidad de seleccionar un centro o individuo en el clúster seleccionado.
- p_Two_center - probabilidad de seleccionar dos centros o dos individuos en el clúster seleccionado.
- k_Mutation - coeficiente de mutación.
- distribCoeff - coeficiente de distribución.
- agent - array de agentes.
- parents - array de padres.
- clusters - array de clústeres.
- km - objeto de la clase KMeans.
2. Métodos:
- SetParams - método para establecer los parámetros del algoritmo.
- Init - método para inicializar el algoritmo. Admite rangos de búsqueda mínimo y máximo, paso de búsqueda y número de épocas.
- Moving - método para desplazar a los agentes.
- Revision - método para revisar los agentes.
3. Campos privados:
- parentsTemp - array temporal de padres.
- epochs - número máximo de épocas.
- epochsNow - época actual.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_BSO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_BSO () { } C_AO_BSO () { ao_name = "BSO"; ao_desc = "Brain Storm Optimization"; ao_link = "https://www.mql5.com/en/articles/14622"; popSize = 25; //population size parentPopSize = 50; //parent population size; clustersNumb = 5; //number of clusters p_Replace = 0.1; //replace probability p_One = 0.5; //probability of choosing one p_One_center = 0.3; //probability of choosing one center p_Two_center = 0.2; //probability of choosing two centers k_Mutation = 20.0; //mutation coefficient distribCoeff = 1.0; //distribution coefficient ArrayResize (params, 9); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "parentPopSize"; params [1].val = parentPopSize; params [2].name = "clustersNumb"; params [2].val = clustersNumb; params [3].name = "p_Replace"; params [3].val = p_Replace; params [4].name = "p_One"; params [4].val = p_One; params [5].name = "p_One_center"; params [5].val = p_One_center; params [6].name = "p_Two_center"; params [6].val = p_Two_center; params [7].name = "k_Mutation"; params [7].val = k_Mutation; params [8].name = "distribCoeff"; params [8].val = distribCoeff; } void SetParams () { popSize = (int)params [0].val; parentPopSize = (int)params [1].val; clustersNumb = (int)params [2].val; p_Replace = params [3].val; p_One = params [4].val; p_One_center = params [5].val; p_Two_center = params [6].val; k_Mutation = params [7].val; distribCoeff = params [8].val; } bool Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0); //number of epochs void Moving (); void Revision (); void Injection (const int popPos, const int coordPos, const double value); //---------------------------------------------------------------------------- int parentPopSize; //parent population size; int clustersNumb; //number of clusters double p_Replace; //replace probability double p_One; //probability of choosing one double p_One_center; //probability of choosing one center double p_Two_center; //probability of choosing two centers double k_Mutation; //mutation coefficient double distribCoeff; //distribution coefficient S_BSO_Agent agent []; S_BSO_Agent parents []; S_Clusters clusters []; S_BSO_KMeans km; private: //------------------------------------------------------------------- S_BSO_Agent parentsTemp []; int epochs; int epochsNow; }; //——————————————————————————————————————————————————————————————————————————————
El método "Init" de la clase "C_AO_BSO" realizará las siguientes acciones para inicializar el algoritmo de optimización:
- Comprobación de la inicialización. En primer lugar, se llamará al método "StandardInit" con los parámetros de rango de búsqueda y paso. Si "StandardInit" retorna "false", se interrumpirá la inicialización y el método "Init" retornará "false".
- Inicialización del agente. El tamaño del array "agent" se redimensionará a "popSize" y se llamará al método "Init" para cada agente con el parámetro "coords" definiendo el número de coordenadas.
- Inicialización del clúster. El tamaño del array "clusters" se cambiará a "clustersNumb" (número máximo de clústeres), y se llamará al método "Init" para cada clúster.
- Inicialización de los padres. Las arrays "parents" y "parentsTemp" se redimensionarán a "parentPopSize + popSize" y se llamará al método "Init" para cada padre. Las arrays deberán tener un tamaño que permita acomodar las poblaciones de padres e hijos para su posterior clasificación.
- Establecimiento de épocas. Los valores de "epochs" y "epochsNow" se establecerán según el parámetro transmitido "epochsP" y "0", respectivamente.
El método retornará "true" si todos los pasos de inicialización se han completado con éxito. Esto preparará al algoritmo para realizar la optimización para un número determinado de épocas.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_BSO::Init (const double &rangeMinP [], //minimum search range const double &rangeMaxP [], //maximum search range const double &rangeStepP [], //step search const int epochsP = 0) //number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- ArrayResize (agent, popSize); for (int i = 0; i < popSize; i++) agent [i].Init (coords); ArrayResize (clusters, clustersNumb); for (int i = 0; i < clustersNumb; i++) clusters [i].Init (coords); ArrayResize (parents, parentPopSize + popSize); ArrayResize (parentsTemp, parentPopSize + popSize); for (int i = 0; i < parentPopSize + popSize; i++) { parents [i].Init (coords); parentsTemp [i].Init (coords); } epochs = epochsP; epochsNow = 0; return true; } //——————————————————————————————————————————————————————————————————————————————
El método "Moving" de la clase "C_AO_BSO" se utilizará para desplazar los agentes durante el proceso de optimización. El método efectuará las siguientes acciones:
- Se incrementará el valor de la época actual ("epochsNow++").
- Si "revision" es "false", las coordenadas del agente se inicializarán utilizando valores aleatorios dentro de los rangos especificados. A continuación, el método finalizará su funcionamiento.
- Si "revision" no es igual a "false", se calcularán nuevas coordenadas para cada agente utilizando fórmulas y probabilidades.
- Para determinar las nuevas coordenadas de los agentes se usarán diversos cálculos matemáticos, números aleatorios y probabilidades.
- Las nuevas coordenadas se calcularán según las condiciones y probabilidades.
- Las nuevas coordenadas se fijarán mediante el método "SeInDiSp" para corregir los valores según los rangos y pasos de búsqueda.
- Se generará una nueva idea que sustituirá al centro del clúster seleccionado (desplazamiento del centro del clúster) si se cumple la condición "u.RNDprobab () < p_Replace".
- Se seleccionará una idea de un clúster si se cumple la condición "u.RNDprobab () < p_One".
- Se seleccionarán ideas de dos clústeres a menos que se cumpla la condición "u.RNDprobab () < p_One".
- Se producirá una mutación de las coordenadas de los agentes.
- Se almacenarán las nuevas coordenadas del agente.
Este método se encargará de actualizar las coordenadas de los agentes en el algoritmo de optimización BSO según la época actual y las probabilidades. Vamos a resaltar las secciones de código relevantes que describen los diferentes comportamientos de los agentes:
- Generación de una nueva idea. En cada nueva época, los agentes explorarán más a fondo la vecindad de la solución global encontrada según el coeficiente "p_Replace", intentando acercarse al óptimo global y desplazando los centroides de los clústeres.
- Estudio de la vecindad de un único clúster. Dado un factor "p_One", los agentes explorarán la vecindad de un clúster seleccionado al azar. Así pues, se seguirán investigando todas las áreas en las que se encuentran agentes en la población.
- Selección de ideas de dos clústeres. Si no se cumple la condición "u.RNDprobab () < p_One", se elegirán ideas de dos clústeres seleccionados al azar.
- Mutación. Las coordenadas de los agentes se someterán a mutación, lo cual proporcionará diversidad a la población y ayudará a evitar la convergencia prematura a óptimos locales.
- Almacenamiento de agentes. Después de todas las operaciones, las nuevas coordenadas de los agentes se guardarán para la siguiente iteración.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BSO::Moving () { epochsNow++; //---------------------------------------------------------------------------- if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); agent [i].c [c] = a [i].c [c]; } } return; } //---------------------------------------------------------------------------- //---------------------------------------------------------------------------- int cIndx_1 = 0; //index in the list of non-empty clusters int iIndx_1 = 0; //index in the list of ideas in the cluster int cIndx_2 = 0; //index in the list of non-empty clusters int iIndx_2 = 0; //index in the list of ideas in the cluster double min = 0.0; double max = 0.0; double dist = 0.0; double val = 0.0; double X1 = 0.0; double X2 = 0.0; int clListSize = 0; int clustList []; ArrayResize (clustList, 0, clustersNumb); //---------------------------------------------------------------------------- //let's make a list of non-empty clusters for (int cl = 0; cl < clustersNumb; cl++) { if (clusters [cl].count > 0) { clListSize++; ArrayResize (clustList, clListSize); clustList [clListSize - 1] = cl; } } for (int i = 0; i < popSize; i++) { //========================================================================== //generating a new idea that replaces the selected cluster center (cluster center offset) if (u.RNDprobab () < p_Replace) { cIndx_1 = u.RNDminusOne (clListSize); for (int c = 0; c < coords; c++) { val = clusters [clustList [cIndx_1]].centroid [c]; dist = (rangeMax [c] - rangeMin [c]) * 0.8; min = val - dist; if (min < rangeMin [c]) min = rangeMin [c]; max = val + dist; if (max > rangeMax [c]) max = rangeMax [c]; val = u.GaussDistribution (val, min, max, 3); val = u.SeInDiSp (val, rangeMin [c], rangeMax [c], rangeStep [c]); clusters [clustList [cIndx_1]].centroid [c] = val; } } //========================================================================== //an idea from one cluster is selected if (u.RNDprobab () < p_One) { cIndx_1 = u.RNDminusOne (clListSize); //------------------------------------------------------------------------ if (u.RNDprobab () < p_One_center) //select cluster center { for (int c = 0; c < coords; c++) { a [i].c [c] = clusters [clustList [cIndx_1]].centroid [c]; } } //------------------------------------------------------------------------ else //random idea from the cluster { iIndx_1 = u.RNDminusOne (clusters [clustList [cIndx_1]].count); for (int c = 0; c < coords; c++) { a [i].c [c] = parents [clusters [clustList [cIndx_1]].ideasList [iIndx_1]].c [c]; } } } //========================================================================== //select ideas from two clusters else { if (clListSize == 1) { cIndx_1 = 0; cIndx_2 = 0; } else { if (clListSize == 2) { cIndx_1 = 0; cIndx_2 = 1; } else { cIndx_1 = u.RNDminusOne (clListSize); do { cIndx_2 = u.RNDminusOne (clListSize); } while (cIndx_1 == cIndx_2); } } //------------------------------------------------------------------------ if (u.RNDprobab () < p_Two_center) //two cluster centers selected { for (int c = 0; c < coords; c++) { X1 = clusters [clustList [cIndx_1]].centroid [c]; X2 = clusters [clustList [cIndx_2]].centroid [c]; a [i].c [c] = u.RNDfromCI (X1, X2); } } //------------------------------------------------------------------------ else //two ideas from two selected clusters { iIndx_1 = u.RNDminusOne (clusters [clustList [cIndx_1]].count); iIndx_2 = u.RNDminusOne (clusters [clustList [cIndx_2]].count); for (int c = 0; c < coords; c++) { X1 = parents [clusters [clustList [cIndx_1]].ideasList [iIndx_1]].c [c]; X2 = parents [clusters [clustList [cIndx_2]].ideasList [iIndx_2]].c [c]; a [i].c [c] = u.RNDfromCI (X1, X2); } } } //========================================================================== //Mutation for (int c = 0; c < coords; c++) { int x = (int)u.Scale (epochsNow, 1, epochs, 1, 200); double ξ = (1.0 / (1.0 + exp (-((100 - x) / k_Mutation))));// * u.RNDprobab (); double dist = (rangeMax [c] - rangeMin [c]) * distribCoeff * ξ; double min = a [i].c [c] - dist; if (min < rangeMin [c]) min = rangeMin [c]; double max = a [i].c [c] + dist; if (max > rangeMax [c]) max = rangeMax [c]; val = a [i].c [c]; a [i].c [c] = u.GaussDistribution (val, min, max, 8); } //Save the agent----------------------------------------------------------- for (int c = 0; c < coords; c++) { val = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); a [i].c [c] = val; agent [i].c [c] = val; } } } //——————————————————————————————————————————————————————————————————————————————
La tarea principal del método Revision de la clase "C_AO_BSO" consistirá en actualizar la solución global y construir clústeres de soluciones. El método efectuará las siguientes acciones:
- Obtención de la adaptabilidad. Para cada agente de la población, se extraerá un valor de adaptabilidad que se almacenará en el campo correspondiente de la estructura del agente.
- Transferencia de nuevas ideas a la población. Las nuevas ideas (agentes) generadas durante el proceso de optimización se añadirán a la población padre.
- Clasificación de la población padre. La población padre se clasificará según el valor de adaptabilidad. Esto permitirá que solo las mejores soluciones de la época siguiente participen en la creación de nuevas ideas.
- Comprobación de la mejor solución. Si la adaptabilidad del mejor agente de la población padre supera a la mejor solución actual, se actualizarán la mejor solución y sus coordenadas.
- Ejecución de la clusterización. Si se trata de la primera iteración, el algoritmo k-means se inicializará con la población padre y los clústeres. A continuación, se ejecutará el algoritmo k-means para clusterizar la población padre.
- Asignación de la mejor solución del clúster como centro del mismo. Para cada clúster, se comprobará si hay agentes en él (los clústeres pueden resultar estar vacíos). En caso afirmativo, se comprobará si cada agente de la población padre pertenece a este clúster. Si la adaptabilidad del agente supera la adaptabilidad actual del clúster, se actualizará la adaptabilidad del clúster y de su centroide (el centroide participa en la creación de nuevas ideas).
//—————————————————————————————————————————————————————————————————————————————— void C_AO_BSO::Revision () { //get fitness-------------------------------------------------- for (int i = 0; i < popSize; i++) { agent [i].f = a [i].f; } //pass new ideas to the population-------------------------------------------- for (int i = parentPopSize; i < parentPopSize + popSize; i++) { parents [i] = agent [i - parentPopSize]; } //sort out the parent population---------------------------------------- u.Sorting (parents, parentsTemp, parentPopSize + popSize); if (parents [0].f > fB) { fB = parents [0].f; ArrayCopy (cB, parents [0].c, 0, 0, WHOLE_ARRAY); } //perform clustering----------------------------------------------------- if (!revision) { km.KMeansInit (parents, parentPopSize, clusters); revision = true; } km.KMeansInit (parents, parentPopSize, clusters); km.KMeans (parents, parentPopSize, clusters); //Assign the best cluster solution as the cluster center-------------------------- for (int cl = 0; cl < clustersNumb; cl++) { clusters [cl].f = -DBL_MAX; if (clusters [cl].count > 0) { for (int p = 0; p < parentPopSize; p++) { if (parents [p].label == cl) { if (parents [p].f > clusters [cl].f) { clusters [cl].f = parents [p].f; ArrayCopy (clusters [cl].centroid, parents [p].c, 0, 0, WHOLE_ARRAY); } } } } } }//——————————————————————————————————————————————————————————————————————————————
Hablando de multimodalidad, el algoritmo BSO se presentó originalmente como un método de optimización para resolver problemas multimodales. Sin embargo, los resultados de las pruebas han mostrado que este algoritmo no explora suficientemente los extremos locales significativos, y muchos de ellos quedan sin detectar. Quizá nuestra aplicación actual no sea la más óptima. Por ello, hemos decidido prestar más atención a la adaptabilidad de los agentes en el contexto de la clusterización de K-Means. Esto ha requerido algunas modificaciones en el algoritmo de clusterización.
Recordemos que la multimodalidad en el marco de los algoritmos de optimización implica que la función a optimizar tendrá varios puntos óptimos o picos. Dichas funciones pueden contener varios óptimos locales que pueden encontrarse cerca del óptimo global en cuanto al valor de la función de aptitud o resultar significativos dentro del problema a resolver. La clusterización puede ayudar a destacar distintas regiones del espacio de búsqueda en las que una característica tiene distintas modalidades.
Así pues, intentaremos potenciar la influencia de la adaptabilidad de los agentes en el proceso de clusterización. Así, envolveremos la función para el cálculo de distancias entre agentes en una nueva función "FitnessDistance"; esta tendrá un parámetro adicional "alpha" que actuará como coeficiente para equilibrar la importancia entre distancia y adaptabilidad.
La función "FitnessDistance" calculará la distancia entre el agente y el centroide del clúster, considerando tanto la distancia como la diferencia en la función de aptitud entre ambos. Para ello, se calculará la suma ponderada de la distancia y el valor absoluto de la diferencia entre la función de aptitud del agente y el centroide. El peso "alpha" determinará la importancia relativa de la distancia frente a la diferencia en la función de aptitud.
//—————————————————————————————————————————————————————————————————————————————— double FitnessDistance (S_BSO_Agent &data, S_Cluster &clust, double alpha) { double distance = VectorDistance (data.c, clust.centroid); double fitness_diff = fabs (data.f - clust.f); return alpha * distance + (1 - alpha) * fitness_diff; } //——————————————————————————————————————————————————————————————————————————————
Completaremos el método "KMeans" con el parámetro "alpha":
void KMeans (S_BSO_Agent &data [], int dataSizeClust, S_Cluster &clust [], double alpha)
Luego cambiaremos la sección de código del método "KMeans", responsable de actualizar los centroides, para que cada clúster tenga el valor de adaptabilidad máximo del individuo en el clúster.
// Update the centroids double sum_c []; ArrayResize (sum_c, ArraySize (data [0].c)); double sum_f = 0.0; for (int cl = 0; cl < nClusters; cl++) { ArrayInitialize (sum_c, 0.0); clust [cl].count = 0; ArrayResize (clust [cl].ideasList, 0); sum_f = -DBL_MAX; for (int d = 0; d < dataSizeClust; d++) { if (data [d].label == cl) { for (int k = 0; k < ArraySize (data [d].c); k++) { sum_c [k] += data [d].c [k]; } if (data [d].f > sum_f) sum_f = data [d].f; clust [cl].count++; ArrayResize (clust [cl].ideasList, clust [cl].count); clust [cl].ideasList [clust [cl].count - 1] = d; } } if (clust [cl].count > 0) { for (int k = 0; k < ArraySize (sum_c); k++) { clust [cl].centroid [k] = sum_c [k] / clust [cl].count; } } }
Los cambios realizados permiten tener en cuenta la función de aptitud en la clusterización, pero no han mejorado notablemente la separación de los modos individuales en la función de aptitud y no han afectado a los resultados. Esto puede deberse a que el uso de una función de aptitud en el proceso de clusterización no siempre resulta eficiente, al menos en esta implementación de BSO.
Si los métodos K-Means y K-Means++ no han dado los resultados deseados, podemos intentar considerar otros métodos de clusterización:
1. La clusterización espacial basada en la densidad para aplicaciones con ruido (DBSCAN), el método de clusterización se basará en la densidad y no en la distancia. Este agrupará los puntos que se encuentren próximos entre sí en el espacio de características y tengan un número suficiente de vecinos. DBSCAN es uno de los algoritmos de clusterización más utilizados.
2. La clusterización jerárquica (Hierarchical Clustering); en ella, el método construye una jerarquía de clústeres donde cada clúster está relacionado con dos clústeres cercanos. La clusterización jerárquica puede ser aglomerativa (ascendente) o divisional (descendente).
3. La mezcla de modelos gaussianos (GMM); este modelo estadístico supone que todos los datos observados se generan a partir de una mezcla de varias distribuciones gaussianas cuyos parámetros se desconocen. Cada grupo se corresponderá con una de estas distribuciones.
4. La clusterización espectral (Spectral Clustering); el método utiliza los vectores propios de la matriz de similitud para reducir la dimensionalidad de los datos antes de clusterizarlos en un espacio de baja dimensionalidad.
Existen muchos métodos de clusterización para probar y seguir investigando en este campo; si el lector desea experimentar, le será bastante fácil sustituir el método K-Means por cualquier otro método en el código adjunto.
3. Resultados de las pruebas
Impresión de los resultados del algoritmo BSO:
BSO|Brain Storm Optimization|25.0|50.0|5.0|0.1|0.5|0.3|0.2|20.0|1.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.9301770731803266
25 Hilly's; Func runs: 10000; result: 0.5801719580773876
500 Hilly's; Func runs: 10000; result: 0.30916005647304245
=============================
5 Forest's; Func runs: 10000; result: 0.929981802038364
25 Forest's; Func runs: 10000; result: 0.5907047167619348
500 Forest's; Func runs: 10000; result: 0.2477599978259004
=============================
5 Megacity's; Func runs: 10000; result: 0.5246153846153847
25 Megacity's; Func runs: 10000; result: 0.2784615384615384
500 Megacity's; Func runs: 10000; result: 0.1253384615384627
=============================
All score: 4.51637 (50.18%)
Los resultados de la prueba del algoritmo con las funciones de prueba (el resultado global (All score) de 4,51637 corresponde al 50,18% del valor máximo posible) muestran que, utilizando los parámetros especificados en la primera línea de las impresiones, se obtienen resultados razonablemente buenos. Los valores de los resultados de la función oscilan entre 0,125 para 1000 parámetros optimizados y hasta 0,93 para 10, respectivamente, lo cual indica que el algoritmo tiene bastante éxito a la hora de encontrar soluciones óptimas.
Nos gustaría señalar aparte cómo se ve la clusterización de soluciones en la visualización, este proceso resulta especialmente visible en las funciones con el máximo número de parámetros, ya que las áreas características de los clústeres empiezan a destacarse cada vez más claramente del caos inicial con cada iteración pasada.
BSO en la función de prueba Hilly.
BSO en la función de prueba Forest.
BSO en la función de prueba Megacity.
Tenía grandes esperanzas puestas en este algoritmo: esperaba verlo en lo más alto de la tabla de clasificación. De hecho, es la primera vez que aplico el método de clusterización en combinación con el método de mutación: se supone que debían mostrar resultados únicos de este algoritmo. Y la verdad es que me ha decepcionado un poco ver que, aunque el algoritmo se ha colocado en la parte alta de la tabla de clasificación, no se halla entre los líderes. Me gustaría señalar que el BSO muestra unos resultados excelentes en las funciones Forest y Megacity con 1 000 parámetros, a la altura de los líderes de la tabla.
№ | AO | Description | Hilly | Hilly final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | % de MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | ||||||||
| 1 | BGA | binary genetic algorithm | 0,99992 | 0,99484 | 0,50483 | 2,49959 | 1,00000 | 0,99975 | 0,32054 | 2,32029 | 0,90667 | 0,96400 | 0,23035 | 2,10102 | 6,921 | 76,90 |
| 2 | (P+O)ES | (P+O) evolution strategies | 0,99934 | 0,91895 | 0,56297 | 2,48127 | 1,00000 | 0,93522 | 0,39179 | 2,32701 | 0,83167 | 0,64433 | 0,21155 | 1,68755 | 6,496 | 72,18 |
| 3 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 4 | ESG | evolution of social groups | 0,99906 | 0,79654 | 0,35056 | 2,14616 | 1,00000 | 0,82863 | 0,13102 | 1,95965 | 0,82333 | 0,55300 | 0,04725 | 1,42358 | 5,529 | 61,44 |
| 5 | SIA | simulated isotropic annealing | 0,95784 | 0,84264 | 0,41465 | 2,21513 | 0,98239 | 0,79586 | 0,20507 | 1,98332 | 0,68667 | 0,49300 | 0,09053 | 1,27020 | 5,469 | 60,76 |
| 6 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 7 | BSA | bird swarm algorithm | 0,90857 | 0,73661 | 0,25767 | 1,90285 | 0,90437 | 0,81619 | 0,16401 | 1,88457 | 0,61692 | 0,54154 | 0,10951 | 1,26797 | 5,055 | 56,17 |
| 8 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 9 | SSG | saplings sowing and growing | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 10 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 11 | BSO | brain storm optimization | 0,91301 | 0,56222 | 0,30047 | 1,77570 | 0,97162 | 0,57162 | 0,23449 | 1,77772 | 0,60462 | 0,27138 | 0,12011 | 0,99611 | 4,550 | 50,55 |
| 12 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 13 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 14 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
| 15 | MEC | mind evolutionary computation | 0,69533 | 0,53376 | 0,32661 | 1,55569 | 0,72464 | 0,33036 | 0,07198 | 1,12698 | 0,52500 | 0,22000 | 0,04198 | 0,78698 | 3,470 | 38,55 |
| 16 | IWO | invasive weed optimization | 0,72679 | 0,52256 | 0,33123 | 1,58058 | 0,70756 | 0,33955 | 0,07484 | 1,12196 | 0,42333 | 0,23067 | 0,04617 | 0,70017 | 3,403 | 37,81 |
| 17 | Micro-AIS | micro artificial immune system | 0,79547 | 0,51922 | 0,30861 | 1,62330 | 0,72956 | 0,36879 | 0,09398 | 1,19233 | 0,37667 | 0,15867 | 0,02802 | 0,56335 | 3,379 | 37,54 |
| 18 | COAm | cuckoo optimization algorithm M | 0,75820 | 0,48652 | 0,31369 | 1,55841 | 0,74054 | 0,28051 | 0,05599 | 1,07704 | 0,50500 | 0,17467 | 0,03380 | 0,71347 | 3,349 | 37,21 |
| 19 | SDOm | spiral dynamics optimization M | 0,74601 | 0,44623 | 0,29687 | 1,48912 | 0,70204 | 0,34678 | 0,10944 | 1,15826 | 0,42833 | 0,16767 | 0,03663 | 0,63263 | 3,280 | 36,44 |
| 20 | NMm | Nelder-Mead method M | 0,73807 | 0,50598 | 0,31342 | 1,55747 | 0,63674 | 0,28302 | 0,08221 | 1,00197 | 0,44667 | 0,18667 | 0,04028 | 0,67362 | 3,233 | 35,92 |
| 21 | FAm | firefly algorithm M | 0,58634 | 0,47228 | 0,32276 | 1,38138 | 0,68467 | 0,37439 | 0,10908 | 1,16814 | 0,28667 | 0,16467 | 0,04722 | 0,49855 | 3,048 | 33,87 |
| 22 | GSA | gravitational search algorithm | 0,64757 | 0,49197 | 0,30062 | 1,44016 | 0,53962 | 0,36353 | 0,09945 | 1,00260 | 0,32667 | 0,12200 | 0,01917 | 0,46783 | 2,911 | 32,34 |
| 23 | BFO | bacterial foraging optimization | 0,61171 | 0,43270 | 0,31318 | 1,35759 | 0,54410 | 0,21511 | 0,05676 | 0,81597 | 0,42167 | 0,13800 | 0,03195 | 0,59162 | 2,765 | 30,72 |
| 24 | ABC | artificial bee colony | 0,63377 | 0,42402 | 0,30892 | 1,36671 | 0,55103 | 0,21874 | 0,05623 | 0,82600 | 0,34000 | 0,14200 | 0,03102 | 0,51302 | 2,706 | 30,06 |
| 25 | BA | bat algorithm | 0,59761 | 0,45911 | 0,35242 | 1,40915 | 0,40321 | 0,19313 | 0,07175 | 0,66810 | 0,21000 | 0,10100 | 0,03517 | 0,34617 | 2,423 | 26,93 |
| 26 | SA | simulated annealing | 0,55787 | 0,42177 | 0,31549 | 1,29513 | 0,34998 | 0,15259 | 0,05023 | 0,55280 | 0,31167 | 0,10033 | 0,02883 | 0,44083 | 2,289 | 25,43 |
| 27 | IWDm | intelligent water drops M | 0,54501 | 0,37897 | 0,30124 | 1,22522 | 0,46104 | 0,14704 | 0,04369 | 0,65177 | 0,25833 | 0,09700 | 0,02308 | 0,37842 | 2,255 | 25,06 |
| 28 | PSO | particle swarm Optimization | 0,59726 | 0,36923 | 0,29928 | 1,26577 | 0,37237 | 0,16324 | 0,07010 | 0,60572 | 0,25667 | 0,08000 | 0,02157 | 0,35823 | 2,230 | 24,77 |
| 29 | Boids | boids algorithm | 0,43340 | 0,30581 | 0,25425 | 0,99346 | 0,35718 | 0,20160 | 0,15708 | 0,71586 | 0,27846 | 0,14277 | 0,09834 | 0,51957 | 2,229 | 24,77 |
| 30 | MA | monkey algorithm | 0,59107 | 0,42681 | 0,31816 | 1,33604 | 0,31138 | 0,14069 | 0,06612 | 0,51819 | 0,22833 | 0,08567 | 0,02790 | 0,34190 | 2,196 | 24,40 |
| 31 | SFL | shuffled frog-leaping | 0,53925 | 0,35816 | 0,29809 | 1,19551 | 0,37141 | 0,11427 | 0,04051 | 0,52618 | 0,27167 | 0,08667 | 0,02402 | 0,38235 | 2,104 | 23,38 |
| 32 | FSS | fish school search | 0,55669 | 0,39992 | 0,31172 | 1,26833 | 0,31009 | 0,11889 | 0,04569 | 0,47467 | 0,21167 | 0,07633 | 0,02488 | 0,31288 | 2,056 | 22,84 |
| 33 | RND | random | 0,52033 | 0,36068 | 0,30133 | 1,18234 | 0,31335 | 0,11787 | 0,04354 | 0,47476 | 0,25333 | 0,07933 | 0,02382 | 0,35648 | 2,014 | 22,37 |
| 34 | GWO | grey wolf optimizer | 0,59169 | 0,36561 | 0,29595 | 1,25326 | 0,24499 | 0,09047 | 0,03612 | 0,37158 | 0,27667 | 0,08567 | 0,02170 | 0,38403 | 2,009 | 22,32 |
| 35 | CSS | charged system search | 0,44252 | 0,35454 | 0,35201 | 1,14907 | 0,24140 | 0,11345 | 0,06814 | 0,42299 | 0,18333 | 0,06300 | 0,02322 | 0,26955 | 1,842 | 20,46 |
| 36 | EM | electroMagnetism-like algorithm | 0,46250 | 0,34594 | 0,32285 | 1,13129 | 0,21245 | 0,09783 | 0,10057 | 0,41085 | 0,15667 | 0,06033 | 0,02712 | 0,24412 | 1,786 | 19,85 |
Conclusiones
El algoritmo BSO presenta varias ventajas, como la flexibilidad, el equilibrio entre investigación y explotación y la adaptabilidad a distintos problemas de optimización.
No obstante, debemos tener en cuenta que la eficacia del algoritmo depende en gran medida de la configuración de los parámetros externos (el número de parámetros externos es el principal inconveniente del BSO), por lo que deberemos realizar investigaciones y experimentos minuciosos para determinar la configuración óptima para cada tarea específica.
Animo a todos los entusiastas de la optimización a unirse a los experimentos y explorar juntos las capacidades del algoritmo para resolver problemas prácticos. Si alguien encuentra resultados más interesantes y con mejor apariencia, por favor, le ruego que los comparta en los comentarios al artículo.
Figura 1. Gradación por colores de los algoritmos según sus respectivas pruebas. Los resultados superiores o iguales a 0,99 aparecen resaltados en blanco.
Figura 2. Histograma con los resultados de las pruebas de los algoritmos (en una escala de 0 a 100, cuanto mayor, mejor),
donde 100 es el máximo resultado teórico posible; hay un script para calcular la tabla de puntuación en el archivo).
Ventajas y desventajas del algoritmo de optimización basado en la tormenta de ideas (BSO):
Ventajas:
- Buenos resultados en la función Forest aguda y Megacity discreta con alta dimensionalidad.
Desventajas:
- Número muy elevado de parámetros externos.
- Arquitectura y aplicación complejas.
- Exigente en recursos informáticos.
Adjuntamos al artículo un archivo con las versiones actuales de los códigos de los algoritmos. El autor de este artículo no se responsabiliza de la exactitud absoluta de la descripción de los algoritmos canónicos, muchos de ellos han sido modificados para mejorar las capacidades de búsqueda. Las conclusiones y juicios presentados en los artículos se basan en los resultados de los experimentos realizados.
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/14622
Utilizando redes neuronales en MetaTrader
Desarrollamos un asesor experto multidivisa (Parte 8): Realizamos pruebas de carga y procesamos la nueva barra
Particularidades del trabajo con números del tipo double en MQL4
Reimaginando las estrategias clásicas: El petróleo
- 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