Algoritmo basado en fractales — Fractal-Based Algorithm (FBA)
513
0
Introducción
Los algoritmos metaheurísticos han demostrado ser herramientas poderosas para resolver problemas de optimización complejos gracias a su capacidad de encontrar soluciones aceptables en un tiempo razonable. En las últimas décadas, se han desarrollado muchos métodos metaheurísticos inspirados en diversos procesos naturales y sociales: algoritmos genéticos, optimización de enjambres de partículas, evolución diferencial, optimización de colonias de hormigas y muchos otros, que ya hemos discutido en artículos anteriores.
En este artículo, analizaremos un nuevo algoritmo metaheurístico para resolver problemas de optimización continua: el Fractal-based Algorithm (FBA) de Marjan Kaedi de 2017. Este enfoque se basa en las propiedades geométricas de los fractales y usa el concepto de autosimilitud para explorar el espacio de forma adaptativa. El algoritmo se basa en una heurística innovadora que evalúa las perspectivas de distintas áreas de búsqueda según la densidad de soluciones de alta calidad dentro de ellas.
El aspecto clave del método propuesto es la partición iterativa del espacio de búsqueda en subespacios con la identificación de las zonas más prometedoras, que luego se someten a un estudio más detallado e intensivo. Durante el funcionamiento del algoritmo se forman estructuras fractales autosimilares, dirigidas hacia la solución óptima, asegurando así un equilibrio entre la búsqueda global y el refinamiento local de las soluciones encontradas. En este artículo, analizaremos con detalle los fundamentos teóricos del algoritmo, los detalles de su implementación, la configuración de los parámetros clave y presentaremos los resultados de un análisis comparativo con otros métodos de optimización populares en funciones de prueba estándar.
Implementación del algoritmo
Imagina que estás buscando un tesoro en un campo enorme. ¿Cómo actuaría? Probablemente no se pondría a excavar cada centímetro del suelo: le llevaría demasiado tiempo. Este es precisamente el problema que resuelve el algoritmo fractal (FBA): ayuda a encontrar el "tesoro" (la solución óptima) en un vasto espacio de posibilidades sin comprobar cada punto.
¿Cómo podemos imaginar el funcionamiento de este algoritmo? Primero, dividimos el área de búsqueda completa en cuadrados iguales, como un tablero de ajedrez. Luego lanzamos "buscadores" (puntos aleatorios) por todo el campo para hacernos una primera impresión del área. Cada buscador informa sobre la calidad del sitio que ha encontrado. El algoritmo selecciona los más exitosos (el 60% de los mejores puntos) y observa en qué casillas se concentran estos. Estos cuadrados están marcados como "zonas prometedoras" (el 30% de mejores cuadrados).
Ahora centramos nuestra atención en las áreas prometedoras. Cada área está dividida en cuadrados más pequeños, creando una estructura fractal. La mayoría de los nuevos cazadores de tesoros se dirigen a estas áreas prometedoras y, para evitar perder tesoros fuera de sus zonas exploradas, el algoritmo obliga a algunos cazadores (5%) a actuar un tanto erráticamente: se alejan en direcciones aleatorias de sus posiciones, explorando lugares inesperados.
El proceso se repite una y otra vez. Con cada paso, el algoritmo determina con mayor precisión dónde podría encontrarse el tesoro y envía más buscadores allí. Poco a poco, se teje una estructura jerárquica de cuadrados de diferentes tamaños, que recuerda a un fractal; de ahí el nombre del algoritmo.
Figura 1. Visualización del esquema del algoritmo FBA
La idea básica del FBA, que se muestra en la figura anterior, consiste en dividir gradualmente el espacio de búsqueda en regiones cada vez más pequeñas de manera fractal, enfocando los recursos computacionales en las regiones más prometedoras. Esto crea una estructura autosimilar que explora el espacio de soluciones. Vamos a escribir ahora el pseudocódigo para el algoritmo FBA.
- Dividimos todo el espacio de búsqueda en subespacios iguales
- Generamos una población inicial uniformemente en todo el espacio
- Evaluamos la idoneidad de cada punto
- Identificamos los puntos prometedores: seleccionamos el P1% de puntos con mayor idoneidad.
- Calculamos el rango del subespacio: calculamos cuántos puntos prometedores entran en cada subespacio.
- Selección de subespacios prometedores: seleccionamos el P2% de subespacios con los rangos prometedores más altos.
- Subdivisión de subespacios prometedores: subdivisión adicional de regiones prometedores en subespacios más pequeños.
- Generación de nueva población: creación de nuevos puntos con mayor densidad en regiones prometedoras.
- Aplicar mutación: agregamos ruido gaussiano al P3% de puntos (mecanismo de exploración).
- Integración poblacional: combinación de las poblaciones actuales y nuevas preservando lo mejor.
- Continuamos hasta alcanzar un criterio de detención (número máximo de iteraciones, umbral de aptitud, etc.)
- Retornamos la mejor solución encontrada
Ahora que hemos entendido el concepto del algoritmo, podemos pasar a escribir el código. La clase "C_AO_FBA" supone una implementación especializada de un algoritmo de optimización basado en principios fractales y se deriva de la clase general "C_AO".
La clase tiene métodos y parámetros públicos responsables de la configuración y acciones básicas del algoritmo. El constructor indica los parámetros iniciales como el tamaño de la población, los porcentajes de puntos y subespacios prometedores, la proporción de puntos que se variarán aleatoriamente y el número de contenedores para separar cada dimensión. El método "SetParams" permite actualizar parámetros de fuentes externas sobre la marcha. El método "Init" y las funciones posteriores "Moving" y "Revision" controlan las etapas e iteraciones del algoritmo.
La clase también declara una representación estructural interna "S_Subspace", que se usa para describir el subespacio de búsqueda. Cada subespacio se caracteriza por límites mínimos y máximos para cada dimensión, el grado de su potencialidad, el nivel en la jerarquía y la conexión con el subespacio padre.
Los métodos principales dentro de la clase incluyen funcionalidad para:
- Comprobamos si un punto está dentro de un subespacio indicado.
- Creamos el marcado inicial del espacio y su posterior división.
- Identificamos los puntos prometedores, calculamos sus rangos y seleccionamos los mejores subespacios para una mayor división.
- Generamos una nueva población mediante combinación, mutación y clasificación según criterios de eficiencia o aptitud.
Así, la clase "C_AO_FBA" implementa un algoritmo adaptativo, jerárquico y basado en fractales para la búsqueda de soluciones óptimas en problemas multidimensionales complejos, usando partición dinámica del espacio, evaluación de áreas prometedoras y operadores heurísticos para mejorar la eficiencia de la búsqueda.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_FBA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_FBA () { } C_AO_FBA () { ao_name = "FBA"; ao_desc = "Fractal-Based Algorithm"; ao_link = "https://www.mql5.com/es/articles/17458"; popSize = 50; // population size P1 = 60; // percentage of promising points P2 = 30; // percentage of promising subspaces P3 = 0.8; // percentage of points for random modification m_value = 10; // number of intervals to split each dimension into ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "P1"; params [1].val = P1; params [2].name = "P2"; params [2].val = P2; params [3].name = "P3"; params [3].val = P3; params [4].name = "m_value"; params [4].val = m_value; } void SetParams () { popSize = (int)params [0].val; P1 = (int)params [1].val; P2 = (int)params [2].val; P3 = params [3].val; m_value = (int)params [4].val; } bool Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0); // number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int P1; // percentage of promising points int P2; // percentage of promising subspaces double P3; // share of points for random modification int m_value; // number of intervals to split each dimension into private: //------------------------------------------------------------------- // Structure for representing a subspace struct S_Subspace { double min []; // minimal boundaries of the subspace double max []; // maximum boundaries of the subspace double promisingRank; // potential rank (normalized value) bool isPromising; // flag of potential int parentIndex; // index of the parent subspace (-1 for root ones) int level; // level in hierarchy (0 for original space) void Init (int coords) { ArrayResize (min, coords); ArrayResize (max, coords); promisingRank = 0.0; isPromising = false; parentIndex = -1; level = 0; } }; S_Subspace subspaces []; // array of subspaces // Auxiliary methods bool IsPointInSubspace (const double &point [], const S_Subspace &subspace); void CreateInitialSpacePartitioning (); void DivideSubspace (int subspaceIndex); void IdentifyPromisingPoints (int &promisingIndices []); void CalculateSubspaceRanks (const int &promisingIndices []); void SelectPromisingSubspaces (); void DividePromisingSubspaces (); void GenerateNewPopulation (); void MutatePoints (); void SortByFitness (double &values [], int &indices [], int size, bool ascending = false); void QuickSort (double &values [], int &indices [], int low, int high, bool ascending); int Partition (double &values [], int &indices [], int low, int high, bool ascending); }; //——————————————————————————————————————————————————————————————————————————————
El método de inicialización "Init" tiene como objetivo establecer las condiciones iniciales para que el algoritmo funcione. Admite arrays con los límites de variables mínimos y máximos y los tamaños de paso para cada parámetro, así como el número de épocas. Dentro del método, primero se llama a la inicialización básica, después de lo cual se crea la división inicial del espacio de búsqueda, es decir, se forma la estructura inicial de subespacios según los rangos y los pasos especificados. Si todas las operaciones son exitosas, el método retorna "true", de lo contrario, "false".
El método básico “Moving” realiza un ciclo de búsqueda de soluciones a través de iteraciones sucesivas. La primera iteración es la inicialización de la población inicial de puntos de manera uniforme en todo el espacio de estudio: cada valor de la variable se selecciona dentro del rango de forma aleatoria y se ajusta a un paso dado.
A continuación, durante el funcionamiento principal, se dan varios pasos. En primer lugar, se identifican los puntos más prometedores: una pequeña parte de los mejores según el valor de la función de eficiencia. Luego se calculan los rangos de estos puntos en relación con sus perspectivas para cada subespacio. En base a estas clasificaciones, se seleccionan los subespacios más prometedores para dividirlos en áreas más pequeñas. Estas áreas prometedoras se dividen posteriormente, creando localizaciones de búsqueda más precisas. Luego, se forma una nueva población de puntos considerando su potencial, lo que permite concentrar los esfuerzos en las áreas más prometedoras. Al final se realiza una modificación aleatoria de puntos (mutación) para aumentar la variedad y evitar el estancamiento.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_FBA::Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0) // number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Create an initial partition of the search space CreateInitialSpacePartitioning (); return true; } //—————————————————————————————————————————————————————————————————————————————— //+----------------------------------------------------------------------------+ //| Basic optimization method | //+----------------------------------------------------------------------------+ void C_AO_FBA::Moving () { // First iteration - initialization of the initial population if (!revision) { // Initialize the initial population uniformly throughout the space 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]); } } revision = true; return; } // Main optimization // 1. Identifying promising points (P1% of points with the best function values) int promisingIndices []; IdentifyPromisingPoints (promisingIndices); // 2. Calculation of potential ranks for each subspace CalculateSubspaceRanks (promisingIndices); // 3. Selecting the P2% most promising subspaces SelectPromisingSubspaces (); // 4. Dividing promising subspaces into smaller ones DividePromisingSubspaces (); // 5. Generating new points taking into account potential ranks GenerateNewPopulation (); // 6. Random modification (mutation) MutatePoints (); } //——————————————————————————————————————————————————————————————————————————————
El método "Revision" es responsable de actualizar la mejor solución actual encontrada durante la operación del algoritmo. Itera sobre todos los elementos de la población actual y compara el valor de la función objetivo de cada elemento con el mejor valor actual. Si algún elemento tiene un mejor resultado, entonces se actualiza la variable que almacena el mejor resultado y se copia el array de variables (coordenadas) asociadas a él para registrar esta solución óptima. Gracias a ello, el método garantiza el seguimiento continuo y el almacenamiento del mejor resultado encontrado en el momento dado.
//+----------------------------------------------------------------------------+ //| Update the best solution | //+----------------------------------------------------------------------------+ void C_AO_FBA::Revision () { // Search for the best solution for (int i = 0; i < popSize; i++) { // Update the best solution if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
El método de creación de una división inicial del espacio tiene como objetivo formar una estructura de subespacios que se usarán para localizar la búsqueda de soluciones óptimas. Este determina el número total de subespacios según un grado de división y dimensionalidad determinados. Si la dimensionalidad muy alta, se limita a un máximo preestablecido para evitar un consumo excesivo de recursos.
Luego, se inicializa un array de subespacios, a cada una de los cuales se le asignan parámetros de nivel inicial y límite para cada coordenada. Dependiendo de las dimensionalidades del espacio se selecciona un método de división adecuado:
- Para un espacio unidimensional, este se divide en intervalos uniformes, cada subespacio creado ocupa una determinada sección del rango.
- Para el espacio bidimensional, se divide a lo largo de dos ejes, formando una cuadrícula de áreas rectangulares.
- En el caso de dimensiones superiores, se utiliza un enfoque iterativo, en el que, por analogía con el sistema de contadores, se generan combinaciones de índices para cada coordenada y, para cada región creada, se establecen límites según los intervalos correspondientes.
El cálculo de los límites se realiza dividiendo los rangos de cada dimensión en partes iguales y, para cada subespacio, se establecen límites mínimos y máximos de acuerdo con los índices actuales. La iteración continúa hasta que se hayan creado todos los subespacios necesarios o hasta que se alcance el límite de su número. Como resultado, se forma una estructura que representa la partición inicial del espacio de búsqueda, preparada para un mayor refinamiento y la búsqueda de soluciones.
//+----------------------------------------------------------------------------+ //| Create the initial partition of the search space | //+----------------------------------------------------------------------------+ void C_AO_FBA::CreateInitialSpacePartitioning () { // Create an initial partition of space int totalSubspaces = (int)MathPow (m_value, coords); // For very large dimensions, limit the number of subspaces if (totalSubspaces > 10000) totalSubspaces = 10000; ArrayResize (subspaces, totalSubspaces); // Initialize all subspaces for (int i = 0; i < totalSubspaces; i++) { subspaces [i].Init (coords); subspaces [i].level = 0; // Initial level } // Divide the initial space into equal subspaces int index = 0; // Select the division method depending on the dimensionality of the space if (coords == 1) { // One-dimensional case double intervalSize = (rangeMax [0] - rangeMin [0]) / m_value; for (int i = 0; i < m_value && index < totalSubspaces; i++) { subspaces [index].min [0] = rangeMin [0] + i * intervalSize; subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize; index++; } } else if (coords == 2) { // Two-dimensional case double intervalSize0 = (rangeMax [0] - rangeMin [0]) / m_value; double intervalSize1 = (rangeMax [1] - rangeMin [1]) / m_value; for (int i = 0; i < m_value && index < totalSubspaces; i++) { for (int j = 0; j < m_value && index < totalSubspaces; j++) { subspaces [index].min [0] = rangeMin [0] + i * intervalSize0; subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize0; subspaces [index].min [1] = rangeMin [1] + j * intervalSize1; subspaces [index].max [1] = rangeMin [1] + (j + 1) * intervalSize1; index++; } } } else { // Multidimensional case - use an iterative approach int indices []; ArrayResize (indices, coords); for (int i = 0; i < coords; i++) indices [i] = 0; while (index < totalSubspaces) { // Calculate the boundaries of the current subspace for (int c = 0; c < coords; c++) { double intervalSize = (rangeMax [c] - rangeMin [c]) / m_value; subspaces [index].min [c] = rangeMin [c] + indices [c] * intervalSize; subspaces [index].max [c] = rangeMin [c] + (indices [c] + 1) * intervalSize; } // Move on to the next subspace int c = coords - 1; while (c >= 0) { indices [c]++; if (indices [c] < m_value) break; indices [c] = 0; c--; } // If the full loop completed, exit if (c < 0) break; index++; } } } //——————————————————————————————————————————————————————————————————————————————
El siguiente método está diseñado para determinar si un punto concreto pertenece a un subespacio particular. Comprueba secuencialmente cada coordenada del punto, comparando su valor con los límites del subespacio correspondiente. Si al menos una coordenada tiene un punto fuera de los límites permitidos (menor que el mínimo, o mayor o igual que el máximo), el método devuelve "false", lo que significa que el punto no está contenido en el subespacio dado. Si todas las coordenadas cumplen las condiciones, el método confirma que el punto pertenece al subespacio dado y devuelve true.
//+----------------------------------------------------------------------------+ //| Determine whether a point belongs to a subspace | //+----------------------------------------------------------------------------+ bool C_AO_FBA::IsPointInSubspace (const double &point [], const S_Subspace &subspace) { // Check if the point is in the specified subspace for (int c = 0; c < coords; c++) { if (point [c] < subspace.min [c] || point [c] >= subspace.max [c]) { return false; } } return true; } //——————————————————————————————————————————————————————————————————————————————
El método para identificar puntos prometedores está diseñado para seleccionar las soluciones más "promising" de la población actual. Comienza creando arrays temporales para almacenar los valores de la función de aptitud de cada elemento y sus índices. Luego, estos arrays se rellenan con los valores e índices de los elementos correspondientes de la población.
A continuación, los elementos se clasifican según el valor de la función de aptitud en orden descendente. Después de la clasificación, se selecciona un cierto porcentaje de las mejores soluciones, dado como P1%, y a partir de éstas se forma una lista de índices que representan los puntos prometedores. Se garantiza que el número de puntos seleccionados sea al menos uno y no exceda el tamaño total de la población. Como resultado, la función devuelve un array de índices de soluciones prometedoras.
//+----------------------------------------------------------------------------+ //| Identify promising points | //+----------------------------------------------------------------------------+ void C_AO_FBA::IdentifyPromisingPoints (int &promisingIndices []) { // Select P1% points with the best function values // Create arrays for sorting double values []; int indices []; ArrayResize (values, popSize); ArrayResize (indices, popSize); // Fill in the arrays for (int i = 0; i < popSize; i++) { values [i] = a [i].f; indices [i] = i; } // Sort in descending order (for the maximization problem) SortByFitness (values, indices, popSize); // Select P1% best points int numPromisingPoints = (int)MathRound (popSize * P1 / 100.0); numPromisingPoints = MathMax (1, MathMin (numPromisingPoints, popSize)); ArrayResize (promisingIndices, numPromisingPoints); for (int i = 0; i < numPromisingPoints; i++) { promisingIndices [i] = indices [i]; } } //——————————————————————————————————————————————————————————————————————————————
Además, el método está diseñado para evaluar y clasificar los subespacios según sus perspectivas. Empieza restableciendo los valores de calificación actuales para todos los subespacios. Luego cuenta cuántos puntos prometedores caen en cada subespacio comparando las coordenadas de cada punto prometedor con los límites de cada subespacio e incrementando el contador correspondiente cuando hay una coincidencia.
Es importante que se considere un punto en un solo subespacio. Después de calcular los indicadores cuantitativos, los rangos de cada subespacio se normalizan dividiéndolos por el número total de puntos prometedores, lo cual da una puntuación relativa para la promesa de cada subespacio, donde el valor varía entre 0 y 1 y corresponde a la proporción de puntos prometedores dentro de cada subespacio en relación con toda la población de puntos prometedores. El resultado es una calificación.
//+----------------------------------------------------------------------------+ //| Calculate potential ranks of subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::CalculateSubspaceRanks (const int &promisingIndices []) { // Reset the ranks of subspaces for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = 0.0; } // Calculate promising points in each subspace for (int i = 0; i < ArraySize (promisingIndices); i++) { int pointIndex = promisingIndices [i]; for (int j = 0; j < ArraySize (subspaces); j++) { if (IsPointInSubspace (a [pointIndex].c, subspaces [j])) { subspaces [j].promisingRank++; break; // A point can only be in one subspace } } } // Normalize the potential ranks according to the article // PromisingRank = Number of promising points in s / Total promising points int totalPromisingPoints = ArraySize (promisingIndices); if (totalPromisingPoints > 0) { for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = subspaces [i].promisingRank / totalPromisingPoints; } } } //——————————————————————————————————————————————————————————————————————————————
El método "SelectPromisingSubspaces" determina qué subespacios deben considerarse prometedores según sus clasificaciones. Luego se crean arrays temporales denominadas "rangos" e "índices" para almacenar las clasificaciones del subespacio y sus índices correspondientes. Los valores de calificación y los índices de subespacio se copian en arrays temporales. Para cada subespacio, el indicador "isPromising" se establece en "false". Esto resulta necesario para empezar desde cero y no tener en cuenta los resultados de iteraciones anteriores. El array "ranks" se clasifica en orden descendente y, al mismo tiempo, el array "indices" se reorganiza para mantener la correspondencia entre índices y calificaciones.
Así, en "indices" después de la clasificación hay índices de subespacios ordenados considerando el orden descendente de sus calificaciones. El número de subespacios que se consideran prometedores se calcula según el parámetro "P2" (porcentaje de mejores subespacios). El valor resultante está limitado a un rango de 1 al número total de subespacios. Itera a través de los primeros elementos "numPromisingSubspaces" del array "indices". Para cada índice de este array, el indicador "isPromising" se establece en "true" para el subespacio correspondiente. Esto significa que este subespacio se considera prometedor.
También se realiza una comprobación para que el índice se encuentre dentro del rango permitido para evitar errores al acceder al array "subspaces". Como resultado de la ejecución del método, el indicador "isPromising" se establece en "true" para el "P2%" de subespacios con los rangos más altos.
//+----------------------------------------------------------------------------+ //| Select promising subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::SelectPromisingSubspaces () { // Select P2% subspaces with the highest ranks as promising ones // Create arrays for sorting double ranks []; int indices []; int numSubspaces = ArraySize (subspaces); ArrayResize (ranks, numSubspaces); ArrayResize (indices, numSubspaces); // Fill in the arrays for (int i = 0; i < numSubspaces; i++) { ranks [i] = subspaces [i].promisingRank; indices [i] = i; // Reset the potential flag subspaces [i].isPromising = false; } // Sort by descending ranks SortByFitness (ranks, indices, numSubspaces); // Select P2% most promising subspaces int numPromisingSubspaces = (int)MathRound (numSubspaces * P2 / 100.0); numPromisingSubspaces = MathMax (1, MathMin (numPromisingSubspaces, numSubspaces)); // Mark promising subspaces for (int i = 0; i < numPromisingSubspaces && i < ArraySize (indices); i++) { // Protection against exceeding the array size if (indices [i] >= 0 && indices [i] < ArraySize (subspaces)) { subspaces [indices [i]].isPromising = true; } } } //——————————————————————————————————————————————————————————————————————————————
El método "DividePromisingSubspaces" está diseñado para dividir subespacios prometedores en partes más pequeñas. Primero identifica todos los subespacios marcados como prometedores comprobando la bandera "isPromising". Los índices de estos subespacios se recopilan en un array temporal "promisingIndices". Luego, para cada subespacio cuyo índice esté en el array "promisingIndices", se llama a la función "DivideSubspace" para pasar el índice de ese subespacio.
De esta forma, el método itera a través de todos los subespacios prometedores encontrados y aplica secuencialmente la división a cada uno de ellos usando la función "DivideSubspace".
//+----------------------------------------------------------------------------+ //| Separate promising subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::DividePromisingSubspaces () { // Collect indices of promising subspaces int promisingIndices []; int numPromising = 0; for (int i = 0; i < ArraySize (subspaces); i++) { if (subspaces [i].isPromising) { numPromising++; ArrayResize (promisingIndices, numPromising); promisingIndices [numPromising - 1] = i; } } // Divide each promising subspace for (int i = 0; i < numPromising; i++) { DivideSubspace (promisingIndices [i]); } } //——————————————————————————————————————————————————————————————————————————————
El método "DivideSubspace" está diseñado para dividir un subespacio específico en partes más pequeñas. Primero, se selecciona el subespacio padre según el índice transmitido. Luego se comprueba si el número total de subespacios no supera el límite establecido (10.000). Después se determina el número total de nuevos subespacios que resultan de dividir cada dimensión en "partes de m_value", es decir, elevando "m_value" a una potencia igual al número de dimensiones.
El array que almacena todos los subespacios aumenta con la cantidad de nuevos subespacios creados. Para cada nuevo subespacio, se especifican parámetros iniciales, como el nivel, el índice del subespacio padre y los límites de cada coordenada, que se calculan según los límites del subespacio padre y la división en partes iguales.
Para cada dimensión, se determina un tamaño de intervalo y los límites del subespacio actual se establecen en consecuencia de acuerdo con los índices actuales. Después de la creación de cada nuevo subespacio, los índices en las dimensiones se incrementan para pasar a la siguiente partición según el sistema de múltiples índices. Cuando el índice de una dimensión alcanza "m_value", se restablece a cero, se incrementa el índice de la siguiente dimensión y se prueban todas las combinaciones.
El proceso continúa hasta que se crean todos los subespacios nuevos o hasta que se alcanza el límite. En el caso de una enumeración completa de todas las combinaciones usando contadores, la finalización se produce de forma natural. Como resultado del método, el subespacio padre se divide en muchos subespacios más pequeños, cada uno de los cuales cubre una parte correspondiente del rango original en todas las dimensiones.
//+----------------------------------------------------------------------------+ //| Partition a specific subspace | //+----------------------------------------------------------------------------+ void C_AO_FBA::DivideSubspace (int subspaceIndex) { // Divide the specified subspace into m_value^coords subspaces S_Subspace parent = subspaces [subspaceIndex]; // Limit the maximum number of subspaces if (ArraySize (subspaces) > 10000) return; // For each dimension, divide by m_value parts int totalNewSubspaces = (int)MathPow (m_value, coords); int currentSize = ArraySize (subspaces); ArrayResize (subspaces, currentSize + totalNewSubspaces); // Create new subspaces int newIndex = currentSize; int indices []; ArrayResize (indices, coords); for (int i = 0; i < coords; i++) indices [i] = 0; for (int idx = 0; idx < totalNewSubspaces && newIndex < ArraySize (subspaces); idx++) { subspaces [newIndex].Init (coords); subspaces [newIndex].level = parent.level + 1; subspaces [newIndex].parentIndex = subspaceIndex; // Calculate the boundaries of the current subspace for (int c = 0; c < coords; c++) { double intervalSize = (parent.max [c] - parent.min [c]) / m_value; subspaces [newIndex].min [c] = parent.min [c] + indices [c] * intervalSize; subspaces [newIndex].max [c] = parent.min [c] + (indices [c] + 1) * intervalSize; } // Move on to the next subspace int c = coords - 1; while (c >= 0) { indices [c]++; if (indices [c] < m_value) break; indices [c] = 0; c--; } // If the full loop completed, exit if (c < 0) break; newIndex++; } } //——————————————————————————————————————————————————————————————————————————————
El método "GenerateNewPopulation" crea una nueva población de puntos, distribuyéndolos en subespacios según el valor "promisingRank".
En primer lugar, se calcula la suma total "promisingRank" para todos los subespacios. Este valor se usará para determinar el número proporcional de puntos que se deben generar en cada subespacio. Si la suma de los rangos es cercana a cero (menor que 0,0001), lo que puede suceder cuando todos los subespacios tienen rango cero, entonces a todos los subespacios se les asigna el rango positivo mínimo (1,0) para garantizar una distribución uniforme de puntos. Luego, para cada subespacio, se calcula la cantidad de puntos a generar en él, proporcional a su “promisingRank” en relación con la suma total de rangos.
La fórmula usada es (subspaces[i].promisingRank / totalRank) * popSize, donde popSize es el tamaño de población requerido. El resultado se redondea al número entero más próximo. El número de puntos está limitado desde arriba para no superar el "popSize". Dentro de cada subespacio, se genera un número calculado de puntos y, para cada punto, se generan coordenadas "coords" usando una distribución uniforme dentro de los límites del subespacio. Para cada dimensión, el valor de la coordenada está restringido por los valores mínimo y máximo indicados y se cuadricula con un paso de "rangeStep[c]".
Si después de distribuir los puntos en los subespacios, el número total de puntos generados es menor que "popSize", los puntos restantes se generan de manera uniforme en todo el espacio de búsqueda usando los límites de todo el espacio "rangeMin[c]", "rangeMax[c]", restricciones y se cuadriculan con el paso "rangeStep[c]". Esto garantiza que la población siempre tenga el tamaño "popSize".
//+----------------------------------------------------------------------------+ //| Generate a new population | //+----------------------------------------------------------------------------+ void C_AO_FBA::GenerateNewPopulation () { // Calculate the sum of the ranks of all subspaces double totalRank = 0.0; for (int i = 0; i < ArraySize (subspaces); i++) { totalRank += subspaces [i].promisingRank; } // If all ranks are 0, set the uniform distribution if (totalRank <= 0.0001) // Check for approximate equality to zero { for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = 1.0; } totalRank = ArraySize (subspaces); } int points = 0; for (int i = 0; i < ArraySize (subspaces) && points < popSize; i++) { // Calculate the number of points for this subspace according to the equation int pointsToGenerate = (int)MathRound ((subspaces [i].promisingRank / totalRank) * popSize); // Limitation against exceeding the limits pointsToGenerate = MathMin (pointsToGenerate, popSize - points); // Generate points in this subspace for (int j = 0; j < pointsToGenerate; j++) { // Create a new point uniformly within the subspace for (int c = 0; c < coords; c++) { a [points].c [c] = u.RNDfromCI (subspaces [i].min [c], subspaces [i].max [c]); a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } points++; if (points >= popSize) break; } } // If not all points were generated, fill the remaining ones uniformly throughout the space while (points < popSize) { for (int c = 0; c < coords; c++) { a [points].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } points++; } } //——————————————————————————————————————————————————————————————————————————————
El método "MutatePoints" de la clase "C_AO_FBA" está diseñado para mutar puntos en una población y forma parte del procedimiento del algoritmo para aumentar la variabilidad de las soluciones y evitar quedar atrapados en trampas locales.
La parte original del método implica la idea de añadir ruido gaussiano a las coordenadas de puntos seleccionados aleatoriamente, lo que se realiza de acuerdo con el algoritmo FBA original. Sin embargo, con esta mutación, el algoritmo funciona muy mal y prácticamente no se diferencia de los resultados de un algoritmo aleatorio; por eso este bloque está comentado, porque encontré una mejor implementación.
La parte principal implementada del método consiste en iterar toda la población. Para cada agente (o punto) y cada coordenada, se comprueba una condición de probabilidad. Si se cumple (según una probabilidad de mutación preestablecida), el valor de la coordenada se modifica mediante una función basada en una distribución de ley de potencia con una potencia que permite controlar el grado de variación. Después de esto, el valor se refina y se limita usando una función que garantiza que se mantenga dentro de los rangos especificados, y que tiene en cuenta los pasos de muestreo.
Como resultado, el método posibilita mutaciones aleatorias de puntos individuales de la población, promoviendo la diversidad de soluciones y mejorando la capacidad de encontrar un óptimo global.
//+----------------------------------------------------------------------------+ //| Mutation of points in the population | //+----------------------------------------------------------------------------+ void C_AO_FBA::MutatePoints () { // Add Gaussian noise to P3% of randomly selected points from the new population /* int numToMutate = (int)MathRound (popSize * P3 / 100.0); numToMutate = MathMax (1, MathMin (numToMutate, popSize)); for (int i = 0; i < numToMutate; i++) { int index = u.RNDminusOne (popSize); // Add noise to each coordinate for (int c = 0; c < coords; c++) { // Standard deviation of 10% of the range //double stdDev = (rangeMax [c] - rangeMin [c]) * 0.1; // Gaussian noise using the Box-Muller method //double noise = NormalRandom (0.0, stdDev); // Add noise and limit the value a [index].c [c] += noise; a [index].c [c] = u.SeInDiSp (a [index].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } */ for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < P3) { a [p].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
El método "SortByFitness" está diseñado para clasificar dos arrays: uno que contiene los valores de la función de aptitud y otro que contiene los índices de los elementos correspondientes. Toma los siguientes parámetros: un array de valores, un array de índices, el tamaño de los arrays y un indicador opcional que especifica el orden de clasificación.
Si el tamaño del array es superior a uno, el método llama a la función interna "QuickSort", que realiza una clasificación rápida de los elementos. En este caso, ambos arrays se clasifican simultáneamente para que se mantenga la correspondencia entre valores e índices. Como resultado, después de ejecutar el método, los elementos se ordenarán según el valor de la función de aptitud según el orden seleccionado.
//+----------------------------------------------------------------------------+ //| Sort by fitness function value | //+----------------------------------------------------------------------------+ void C_AO_FBA::SortByFitness (double &values [], int &indices [], int size, bool ascending = false) { if (size > 1) QuickSort (values, indices, 0, size - 1, ascending); } //——————————————————————————————————————————————————————————————————————————————
El método "QuickSort" implementa un algoritmo de clasificación rápido para dos arrays relacionados: "value" e "indices". Divide y clasifica arrays de forma recursiva de tal manera que se conserva la correspondencia entre un valor y su índice original. Parámetros: arrays a ordenar, límites del área clasificada (bajo y alto) y la bandera "ascending" que determina el orden de clasificación.
//+----------------------------------------------------------------------------+ //| Quick sort algorithm | //+----------------------------------------------------------------------------+ void C_AO_FBA::QuickSort (double &values [], int &indices [], int low, int high, bool ascending) { if (low < high) { int pi = Partition (values, indices, low, high, ascending); QuickSort (values, indices, low, pi - 1, ascending); QuickSort (values, indices, pi + 1, high, ascending); } } //——————————————————————————————————————————————————————————————————————————————
El método de partición es una parte clave del algoritmo de clasificación rápida. Su tarea consiste en seleccionar un elemento de pivote y redistribuir los elementos del array "indices" de tal manera que todos los elementos "menores" que el pivote (o "mayores", dependiendo del orden de clasificación) estén a la izquierda de este, mientras que los "mayores" ("menores") estén a la derecha. "Menor que" y "mayor que" se definen en relación con los valores en el array "values" al que apuntan los índices en "indices".
//+----------------------------------------------------------------------------+ //| Partition function for QuickSort | //+----------------------------------------------------------------------------+ int C_AO_FBA::Partition (double &values [], int &indices [], int low, int high, bool ascending) { double pivot = values [indices [high]]; int i = low - 1; for (int j = low; j < high; j++) { bool condition = ascending ? (values [indices [j]] < pivot) : (values [indices [j]] > pivot); if (condition) { i++; // Exchange values int temp = indices [i]; indices [i] = indices [j]; indices [j] = temp; } } // Exchange values int temp = indices [i + 1]; indices [i + 1] = indices [high]; indices [high] = temp; return i + 1; } //——————————————————————————————————————————————————————————————————————————————
Resultados de las pruebas
El algoritmo muestra buenos resultados.FBA|Fractal-Based Algorithm|50.0|60.0|30.0|0.8|10.0|
=============================
5 Hilly's; Func runs: 10000; result: 0,7900044352090774
25 Hilly's; Func runs: 10000; result: 0.6513385092404853
500 Hilly's; Func runs: 10000; result: 0,2896548031738138
=============================
5 Forest's; Func runs: 10000; result: 0.8715768614282637
25 Forest's; Func runs: 10000; result: 0.5682316842631675
500 Forest's; Func runs: 10000; result: 0,18876552479611478
=============================
5 Megacity's; Func runs: 10000; result: 0.6107692307692306
25 Megacity's; Func runs: 10000; result: 0.46061538461538465
500 Megacity's; Func runs: 10000; result: 0,12398461538461655
=============================
All score: 4.55494 (50.61%)
La visualización muestra cómo el algoritmo divide el espacio de búsqueda en subespacios más pequeños. También existe una gran variabilidad de resultados al trabajar con funciones de pequeña dimensionalidad.
FBA sobre la función de prueba Hilly
FBA en la función de prueba Forest
FBA en la función de prueba Megacity
Según los resultados de las pruebas, el algoritmo FBA ocupa el puesto 29 en nuestra tabla de clasificación.
| # | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Resultado | % 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 | ANS | across neighbourhood search | 0.94948 | 0.84776 | 0.43857 | 2.23581 | 1.00000 | 0.92334 | 0.39988 | 2.32323 | 0.70923 | 0.63477 | 0.23091 | 1.57491 | 6.134 | 68.15 |
| 2 | CLA | code lock algorithm (joo) | 0.95345 | 0.87107 | 0.37590 | 2.20042 | 0.98942 | 0.91709 | 0.31642 | 2.22294 | 0.79692 | 0.69385 | 0.19303 | 1.68380 | 6.107 | 67.86 |
| 3 | AMOm | animal migration optimization M | 0.90358 | 0.84317 | 0.46284 | 2.20959 | 0.99001 | 0.92436 | 0.46598 | 2.38034 | 0.56769 | 0.59132 | 0.23773 | 1.39675 | 5.987 | 66.52 |
| 4 | (P+O)ES | (P+O) evolution strategies | 0.92256 | 0.88101 | 0.40021 | 2.20379 | 0.97750 | 0.87490 | 0.31945 | 2.17185 | 0.67385 | 0.62985 | 0.18634 | 1.49003 | 5.866 | 65.17 |
| 5 | CTA | comet tail algorithm (joo) | 0.95346 | 0.86319 | 0.27770 | 2.09435 | 0.99794 | 0.85740 | 0.33949 | 2.19484 | 0.88769 | 0.56431 | 0.10512 | 1.55712 | 5.846 | 64.96 |
| 6 | TETA | time evolution travel algorithm (joo) | 0.91362 | 0.82349 | 0.31990 | 2.05701 | 0.97096 | 0.89532 | 0.29324 | 2.15952 | 0.73462 | 0.68569 | 0.16021 | 1.58052 | 5.797 | 64.41 |
| 7 | 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 |
| 8 | BOAm | billiards optimization algorithm M | 0.95757 | 0.82599 | 0.25235 | 2.03590 | 1.00000 | 0.90036 | 0.30502 | 2.20538 | 0.73538 | 0.52523 | 0.09563 | 1.35625 | 5.598 | 62.19 |
| 9 | AAm | archery algorithm M | 0.91744 | 0.70876 | 0.42160 | 2.04780 | 0.92527 | 0.75802 | 0.35328 | 2.03657 | 0.67385 | 0.55200 | 0.23738 | 1.46323 | 5.548 | 61.64 |
| 10 | ESG | evolution of social groups (joo) | 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 |
| 11 | SIA | simulated isotropic annealing (joo) | 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 |
| 12 | ACS | artificial cooperative search | 0.75547 | 0.74744 | 0.30407 | 1.80698 | 1.00000 | 0.88861 | 0.22413 | 2.11274 | 0.69077 | 0.48185 | 0.13322 | 1.30583 | 5.226 | 58.06 |
| 13 | DA | dialectical algorithm | 0.86183 | 0.70033 | 0.33724 | 1.89940 | 0.98163 | 0.72772 | 0.28718 | 1.99653 | 0.70308 | 0.45292 | 0.16367 | 1.31967 | 5.216 | 57.95 |
| 14 | BHAm | black hole algorithm M | 0.75236 | 0.76675 | 0.34583 | 1.86493 | 0.93593 | 0.80152 | 0.27177 | 2.00923 | 0.65077 | 0.51646 | 0.15472 | 1.32195 | 5.196 | 57.73 |
| 15 | ASO | anarchy society optimization | 0.84872 | 0.74646 | 0.31465 | 1.90983 | 0.96148 | 0.79150 | 0.23803 | 1.99101 | 0.57077 | 0.54062 | 0.16614 | 1.27752 | 5.178 | 57.54 |
| 16 | RFO | royal flush optimization (joo) | 0.83361 | 0.73742 | 0.34629 | 1.91733 | 0.89424 | 0.73824 | 0.24098 | 1.87346 | 0.63154 | 0.50292 | 0.16421 | 1.29867 | 5.089 | 56.55 |
| 17 | AOSm | búsqueda de orbitales atómicos M | 0.80232 | 0.70449 | 0.31021 | 1.81702 | 0.85660 | 0.69451 | 0.21996 | 1.77107 | 0.74615 | 0.52862 | 0.14358 | 1.41835 | 5.006 | 55.63 |
| 18 | TSEA | turtle shell evolution algorithm (joo) | 0.96798 | 0.64480 | 0.29672 | 1.90949 | 0.99449 | 0.61981 | 0.22708 | 1.84139 | 0.69077 | 0.42646 | 0.13598 | 1.25322 | 5.004 | 55.60 |
| 19 | 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 |
| 20 | SRA | successful restaurateur algorithm (joo) | 0.96883 | 0.63455 | 0.29217 | 1.89555 | 0.94637 | 0.55506 | 0.19124 | 1.69267 | 0.74923 | 0.44031 | 0.12526 | 1.31480 | 4.903 | 54.48 |
| 21 | CRO | chemical reaction optimization | 0.94629 | 0.66112 | 0.29853 | 1.90593 | 0.87906 | 0.58422 | 0.21146 | 1.67473 | 0.75846 | 0.42646 | 0.12686 | 1.31178 | 4.892 | 54.36 |
| 22 | BIO | blood inheritance optimization (joo) | 0.81568 | 0.65336 | 0.30877 | 1.77781 | 0.89937 | 0.65319 | 0.21760 | 1.77016 | 0.67846 | 0.47631 | 0.13902 | 1.29378 | 4.842 | 53.80 |
| 23 | BSA | bird swarm algorithm | 0.89306 | 0.64900 | 0.26250 | 1.80455 | 0.92420 | 0.71121 | 0.24939 | 1.88479 | 0.69385 | 0.32615 | 0.10012 | 1.12012 | 4.809 | 53.44 |
| 24 | 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 |
| 25 | 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 |
| 26 | BCOm | bacterial chemotaxis optimization M | 0.75953 | 0.62268 | 0.31483 | 1.69704 | 0.89378 | 0.61339 | 0.22542 | 1.73259 | 0.65385 | 0.42092 | 0.14435 | 1.21912 | 4.649 | 51.65 |
| 27 | ABO | african buffalo optimization | 0.83337 | 0.62247 | 0.29964 | 1.75548 | 0.92170 | 0.58618 | 0.19723 | 1.70511 | 0.61000 | 0.43154 | 0.13225 | 1.17378 | 4.634 | 51.49 |
| 28 | (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 |
| 29 | FBA | Fractal-Based Algorithm | 0.79000 | 0.65134 | 0.28965 | 1.73099 | 0.87158 | 0.56823 | 0.18877 | 1.62858 | 0.61077 | 0.46062 | 0.12398 | 1.19537 | 4.555 | 50.61 |
| 30 | TSm | tabu search M | 0.87795 | 0.61431 | 0.29104 | 1.78330 | 0.92885 | 0.51844 | 0.19054 | 1.63783 | 0.61077 | 0.38215 | 0.12157 | 1.11449 | 4.536 | 50.40 |
| 31 | BSO | brain storm optimization | 0.93736 | 0.57616 | 0.29688 | 1.81041 | 0.93131 | 0.55866 | 0.23537 | 1.72534 | 0.55231 | 0.29077 | 0.11914 | 0.96222 | 4.498 | 49.98 |
| 32 | 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 |
| 33 | AEFA | artificial electric field algorithm | 0.87700 | 0.61753 | 0.25235 | 1.74688 | 0.92729 | 0.72698 | 0.18064 | 1.83490 | 0.66615 | 0.11631 | 0.09508 | 0.87754 | 4.459 | 49.55 |
| 34 | AEO | artificial ecosystem-based optimization algorithm | 0.91380 | 0.46713 | 0.26470 | 1.64563 | 0.90223 | 0.43705 | 0.21400 | 1.55327 | 0.66154 | 0.30800 | 0.28563 | 1.25517 | 4.454 | 49.49 |
| 35 | 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 |
| 36 | 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 |
| 37 | SOA | simple optimization algorithm | 0.91520 | 0.46976 | 0.27089 | 1.65585 | 0.89675 | 0.37401 | 0.16984 | 1.44060 | 0.69538 | 0.28031 | 0.10852 | 1.08422 | 4.181 | 46.45 |
| 38 | ABH | artificial bee hive algorithm | 0.84131 | 0.54227 | 0.26304 | 1.64663 | 0.87858 | 0.47779 | 0.17181 | 1.52818 | 0.50923 | 0.33877 | 0.10397 | 0.95197 | 4.127 | 45.85 |
| 39 | ACMO | atmospheric cloud model optimization | 0.90321 | 0.48546 | 0.30403 | 1.69270 | 0.80268 | 0.37857 | 0.19178 | 1.37303 | 0.62308 | 0.24400 | 0.10795 | 0.97503 | 4.041 | 44.90 |
| 40 | ADAMm | adaptive moment estimation M | 0.88635 | 0.44766 | 0.26613 | 1.60014 | 0.84497 | 0.38493 | 0.16889 | 1.39880 | 0.66154 | 0.27046 | 0.10594 | 1.03794 | 4.037 | 44.85 |
| 41 | CGO | chaos game optimization | 0.57256 | 0.37158 | 0.32018 | 1.26432 | 0.61176 | 0.61931 | 0.62161 | 1.85267 | 0.37538 | 0.21923 | 0.19028 | 0.78490 | 3.902 | 43.35 |
| 42 | ATAm | artificial tribe algorithm M | 0.71771 | 0.55304 | 0.25235 | 1.52310 | 0.82491 | 0.55904 | 0.20473 | 1.58867 | 0.44000 | 0.18615 | 0.09411 | 0.72026 | 3.832 | 42.58 |
| 43 | CROm | coral reefs optimization M | 0.78512 | 0.46032 | 0.25958 | 1.50502 | 0.86688 | 0.35297 | 0.16267 | 1.38252 | 0.63231 | 0.26738 | 0.10734 | 1.00703 | 3.895 | 43.27 |
| 44 | CFO | central force optimization | 0.60961 | 0.54958 | 0.27831 | 1.43750 | 0.63418 | 0.46833 | 0.22541 | 1.32792 | 0.57231 | 0.23477 | 0.09586 | 0.90294 | 3.668 | 40.76 |
| 45 | ASHA | artificial showering algorithm | 0.89686 | 0.40433 | 0.25617 | 1.55737 | 0.80360 | 0.35526 | 0.19160 | 1.35046 | 0.47692 | 0.18123 | 0.09774 | 0.75589 | 3.664 | 40.71 |
| R.W. | neuroboids optimization algorithm 2(joo) | 0.48754 | 0.32159 | 0.25781 | 1.06694 | 0.37554 | 0.21944 | 0.15877 | 0.75375 | 0.27969 | 0.14917 | 0.09847 | 0.52734 | 2.348 | 26.09 | |
Conclusiones
La versión modificada por mutaciones del algoritmo FBA, con resultados del 50,61%, demuestra una mejora doble en la eficiencia en comparación con los resultados de la versión original.
FBA|Fractal-Based Algorithm|50.0|60.0|30.0|5.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4780639253626462
25 Hilly's; Func runs: 10000; result: 0.3222029113692554
500 Hilly's; Func runs: 10000; result: 0,25720991988937014
=============================
5 Forest's; Func runs: 10000; result: 0.36567166223346415
25 Forest's; Func runs: 10000; result: 0,22043205527307377
500 Forest's; Func runs: 10000; result: 0,15869146061036057
=============================
5 Megacity's; Func runs: 10000; result: 0.2861538461538461
25 Megacity's; Func runs: 10000; result: 0.15015384615384622
500 Megacity's; Func runs: 10000; result: 0.09838461538461622
=============================
All score: 2.33696 (25.97%)
Gracias a cambios fundamentales en el mecanismo de mutación, el nuevo enfoque ofrece un equilibrio más razonable entre la exploración global del espacio de búsqueda y la explotación local de las soluciones prometedoras descubiertas.
El logro clave es que ahora el algoritmo usa el conocimiento acumulado sobre el panorama de búsqueda para guiar el proceso de mutación, en lugar de cambios completamente aleatorios. Esto es más consistente con los procesos de optimización naturales, donde la aleatoriedad y el determinismo coexisten de forma equilibrada. Este enfoque permite que el algoritmo converja al óptimo global con mayor rapidez, especialmente en espacios multidimensionales complejos con numerosos extremos locales, lo que explica la mejora significativa del rendimiento.
Figura 2. Clasificación por colores de los algoritmos según las pruebas respectivas
Figura 3. Histograma de los resultados de las pruebas de algoritmos (en una escala de 0 a 100, cuanto más mejor, donde 100 es el máximo resultado teórico posible, el script para calcular la tabla de puntuación está en el archivo)
Ventajas y desventajas del algoritmo FBA:
Ventajas:
- Resultados estables en funciones de dimensionalidad media y alta.
Desventajas:
- Gran dispersión de resultados para funciones de baja dimensionalidad.
- Una idea básica interesante, pero bastante "débil" del algoritmo.
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.
Programas usados en el artículo
| # | Nombre | Tipo | Descripción |
|---|---|---|---|
| 1 | #C_AO.mqh | Archivo de inclusión | Clase padre de algoritmos de optimización basados en la población |
| 2 | #C_AO_enum.mqh | Archivo de inclusión | Enumeración de los algoritmos de optimización basados en la población |
| 3 | TestFunctions.mqh | Archivo de inclusión | Biblioteca de funciones de prueba |
| 4 | TestStandFunctions.mqh | Archivo de inclusión | Biblioteca de funciones del banco de pruebas |
| 5 | Utilities.mqh | Archivo de inclusión | Biblioteca de funciones auxiliares |
| 6 | CalculationTestResults.mqh | Archivo de inclusión | Script para calcular los resultados en una tabla comparativa |
| 7 | Testing AOs.mq5 | Script | Banco de pruebas único para todos los algoritmos de optimización basados en la población |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Ejemplo sencillo de utilización de algoritmos de optimización basados en la población sin visualización |
| 9 | Test_FBA.mq5 | Script | Banco de pruebas FBA |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/17458
Advertencia: todos los derechos de estos materiales pertenecen a MetaQuotes Ltd. Queda totalmente prohibido el copiado total o parcial.
Este artículo ha sido escrito por un usuario del sitio web y refleja su punto de vista personal. MetaQuotes Ltd. no se responsabiliza de la exactitud de la información ofrecida, ni de las posibles consecuencias del uso de las soluciones, estrategias o recomendaciones descritas.
Automatización de estrategias de trading en MQL5 (Parte 17): Dominar la estrategia de scalping Grid-Mart con un panel de control dinámico
Optimización y ajuste de código sin procesar para mejorar los resultados de las pruebas retrospectivas
Modelos ocultos de Márkov en sistemas comerciales de aprendizaje automático
Del básico al intermedio: Objetos (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