Optimización de arrecifes de coral — Coral Reefs Optimization (CRO)
214
0
Contenido
Introducción
Los algoritmos bioinspirados basados en procesos y sistemas naturales han despertado últimamente un gran interés entre los desarrolladores. Entre estos algoritmos, destaca el algoritmo de optimización de arrecifes de coral (CRO), propuesto originalmente por S. Salcedo-Sanz y coautores en 2014.
El algoritmo CRO se basa en la modelización de los procesos de formación y desarrollo de los arrecifes de coral en la naturaleza. Estos procesos incluyen diversos mecanismos de reproducción de los corales (reproducción sexual externa e interna, así como reproducción asexual), la competencia por un espacio limitado en el arrecife y la muerte de los individuos débiles. Al igual que la evolución da forma a arrecifes de coral estables y adaptados en la naturaleza, el algoritmo CRO nos permite explorar el espacio de búsqueda y encontrar soluciones óptimas o casi óptimas a diferentes problemas.
Este artículo presentará una versión mejorada del algoritmo CROm con un mecanismo de aniquilación modificado basado en el uso de la distribución inversa de grados para generar nuevas soluciones en las proximidades de la mejor. El enfoque propuesto no solo conserva las ventajas tradicionales del CRO, como el poder exploratorio y el equilibrio natural entre la exploración global y la explotación local del espacio de búsqueda, sino que las complementa con un mecanismo más eficiente que permite localizar con mayor precisión las áreas de búsqueda prometedoras y converger más rápidamente a soluciones óptimas.
Realizaremos pruebas exhaustivas del algoritmo propuesto en un conjunto de funciones de prueba de optimización clásicas, demostrando su mejor rendimiento en comparación con el algoritmo CRO original y otras metaheurísticas modernas. Los resultados experimentales muestran que el enfoque propuesto resulta particularmente eficaz para problemas con funciones objetivo multimodales y una estructura compleja del paisaje de búsqueda.
El artículo se estructura de la siguiente manera: en primer lugar, repasaremos los conceptos básicos y los principios de funcionamiento del algoritmo CRO estándar; y a continuación, describiremos con detalle las modificaciones propuestas y su justificación teórica. A continuación, evaluaremos experimentalmente el algoritmo y analizaremos los resultados. Por último, discutiremos los resultados obtenidos, las limitaciones del método propuesto y los posibles rumbos para futuras investigaciones.
Implementación del algoritmo
La idea básica del CRO consiste en modelar colonias de coral que se desarrollen y compitan por el espacio en el arrecife, formando finalmente una estructura óptima. Cada coral del arrecife representa una solución potencial al problema de optimización analizado.
El arrecife se modela como una red bidimensional de tamaño N×M. Cada celda de la cuadrícula puede estar ocupada por un coral o estar vacía. El coral representa una solución codificada a un problema de optimización. Para cada coral, se define una función de aptitud (salud) que se corresponde con la función objetivo del problema de optimización.
El parámetro ρ₀ ∈ (0,1) define la fracción de ocupación coralina inicial del arrecife, es decir, la relación entre las celdas ocupadas y el número total de celdas al inicio del algoritmo. La inicialización del arrecife se realiza de la forma que sigue:
- Luego se especifica el tamaño del arrecife N×M y la fracción de ocupación inicial ρ₀.
- Después se seleccionan aleatoriamente ⌊ρ₀ × N × M⌋ celdas de arrecife para alojar a los corales iniciales.
- Los corales iniciales se generan de forma aleatoria dentro del área de búsqueda y se colocan en las celdas seleccionadas.
Una vez inicializado el arrecife, se inicia un proceso iterativo de formación y desarrollo del arrecife que consta de varias etapas:
Reproducción sexual externa (Broadcast Spawning). Para este tipo de propagación se selecciona una proporción determinada de los corales Fₑ existentes. Los corales seleccionados forman parejas y usan operadores de cruces para crear descendencia. Cada pareja produce una larva mediante un operador de cruce (promedio normal).
Reproducción sexual interna (Brooding). La fracción restante de corales (1-Fₑ) participa en la reproducción interna, en la que cada coral produce descendencia mediante mutación. Para cada coral seleccionado para la reproducción interna, se crea una larva usando el operador de mutación, y suele representar una pequeña variación aleatoria en la solución codificada. Asentamiento de larvas. Una vez formadas las larvas durante las fases de cría, cada una intenta fijar su residencia en el arrecife. El proceso de asentamiento se lleva a cabo según las siguientes reglas:
- La larva elige al azar una celda (i, j) del arrecife.
- Si una celda está vacía, la larva la ocupa.
- Si una celda está ocupada, una larva solo puede desplazar a un coral existente si su aptitud es mayor: f(larva) > f(Ξᵢⱼ).
- Si no se produce el desplazamiento, la larva puede tratar de asentarse en otro lugar (hasta un número máximo de intentos k).
- Si tras k intentos la larva no ha podido encontrar un lugar, muere.
Reproducción asexual (Budding). Los mejores corales del arrecife (fracción Fₐ) pueden reproducirse asexualmente, creando copias exactas (clones) de sí mismos. Técnicamente:
- Los corales se clasifican de acuerdo con la importancia de la función de adaptación.
- Los mejores corales Fₐ × 100% se seleccionan para la reproducción asexual.
- Cada coral seleccionado crea un clon que trata de asentarse en el arrecife siguiendo las mismas reglas que el proceso de asentamiento larvario.
Extinción. Al final de cada iteración, los peores corales del arrecife pueden morir con una probabilidad Pd, dejando sitio a nuevos corales en las siguientes iteraciones.
El proceso de formación de arrecifes se repite hasta que se cumple el criterio de parada indicado, alcanzando el número máximo de iteraciones. Tras detenerse, el mejor coral del arrecife representa la solución encontrada al problema de optimización.
Figura 1. Esquema del algoritmo CRO
La ilustración anterior muestra los seis pasos principales del algoritmo:
- Inicialización (ρ₀ = 0,6) — muestra un entramado bidimensional (arrecife) parcialmente lleno de corales multicolores que representan diferentes soluciones.
- Reproducción externa (Fb = 0,9) — muestra los corales que forman parejas y crean larvas mediante el cruce.
- Reproducción interna (1-Fb = 0,1) — muestra corales individuales que producen larvas por mutación.
- Asentamiento de larvas (k = 3 intentos) — ilustra el proceso de búsqueda de un lugar en el arrecife por parte de las larvas, incluidos los intentos con éxito y sin éxito.
- Reproducción asexual (Fa = 0,1) — muestra los mejores corales (marcados con asteriscos) haciendo copias exactas de sí mismos.
- Extinción (Fd = 0,1, Pd = 0,05) — muestra la eliminación de los peores corales del arrecife.
Entrada: Parámetros de arrecife (N, M, ρ₀, Fₑ, Fₐ, Fd, Pd, k).
Salida: La mejor solución encontrada
1. Inicialización:
- Creamos un arrecife de tamaño N×M
- Llenamos ⌊ρ₀ × N × M⌋ celdas con corales al azar.
- Calculamos la aptitud de cada coral
2. Hasta que se cumpla el criterio de parada:
3. Reproducción sexual externa:
- Seleccionamos una proporción de corales Fₑ para participar
- Se forman parejas y se crean larvas mediante cruces
4. Reproducción sexual interna:
- Para que los corales restantes (1-Fₑ) creen larvas por mutación
5. Asentamiento de larvas:
- Para cada larva:
- Se intenta ocupar una celda de arrecife aleatoria
- Si se ocupa, desplaza al coral existente con mayor adaptación
- Si no lo consigue, lo intenta de nuevo (hasta k intentos)
6. Reproducción asexual:
- Se clasifican los corales por adaptación
- Los mejores corales Fₐ crean clones de ellos
- Los clones intentan asentarse en el arrecife
7. Extinción:
- Con probabilidad Pd de realizar la destrucción
- Se elimina la fracción Fd de los peores corales
8. Recuperamos el mejor coral del arrecife
Ahora podemos componer el código del algoritmo CRO. Escribiremos la clase "C_AO_CRO", que implementará el algoritmo CRO y heredará de la clase básica "C_AO".
Parámetros de CRO:
La clase declara los parámetros que controlarán el comportamiento del algoritmo:
- popSize — tamaño de la población de corales.
- reefRows — altura del arrecife (número de filas en la cuadrícula).
- reefCols — anchura del arrecife (número de columnas de la cuadrícula).
- rho0 — ocupación inicial del arrecife. Es el porcentaje de celdas de arrecife ocupadas por corales al inicio del algoritmo.
- Fb — proporción de corales que participan en la reproducción externa (Broadcast Spawning).
- Fa — proporción de corales que participan en la reproducción asexual (fragmentación).
- Fd — proporción de corales que deben eliminarse debido a su baja aptitud.
- Pd — probabilidad de destrucción del coral.
- attemptsNum — número de intentos que hace una larva para asentarse en el arrecife.
Métodos de clase:
- SetParams () — el método establece los valores de los parámetros del algoritmo basándose en los valores almacenados en el array "params", que es un array que permite cambiar dinámicamente los parámetros del algoritmo en tiempo de ejecución.
- Init () — método de inicialización, acepta los rangos de búsqueda para las variables de optimización (rangeMinP, rangeMaxP, rangeStepP) y el número de épocas (epochsP). El método "Init" realizará los preparativos necesarios para poner en marcha el algoritmo, como inicializar la población y el arrecife.
- Moving () — la función implementa la lógica básica del movimiento de los corales en el arrecife.
- Revision () — el método se encarga de revisar y corregir las posiciones de los corales en el arrecife.
- InitReef () — inicializa la estructura del arrecife, preparándola para el asentamiento de los corales.
- LarvaSettling () — determina dónde se asentará una larva de coral en el arrecife, modelando el proceso de repoblación del arrecife por nuevos corales. El parámetro "larva" representará la larva de un coral.
- BroadcastSpawning () — proceso de reproducción externa en el que los corales liberan larvas en el agua.
- Brooding () — proceso reproductivo alternativo en el que las larvas se desarrollan en el interior del coral.
- AsexualReproduction () — proceso de reproducción asexual en el que los corales se fragmentan y forman nuevas colonias.
- Depredation () — proceso de extinción en el que se destruyen los corales.
- GetReefCoordIndex () — convierte las coordenadas del arrecife (fila y columna) en un índice de array unidimensional.
- SortAgentsByFitness () — clasifica los corales según su aptitud (fitness).
Variables privadas:
- totalReefSize — tamaño total del arrecife (producto de "reefRows" y "reefCols").
- ocupado [] — array de valores booleanos que indican si cada celda del arrecife está ocupada por un coral.
- reefIndices [] — array de índices que contiene los índices de los corales (del array "a []" de la clase básica "C_AO") en celdas de arrecife ocupadas.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_CRO : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_CRO () { } C_AO_CRO () { ao_name = "CRO"; ao_desc = "Coral Reef Optimization"; ao_link = "https://www.mql5.com/es/articles/17760"; popSize = 50; // population size reefRows = 20; // reef height reefCols = 20; // reef width rho0 = 0.2; // initial reef occupancy Fb = 0.99; // fraction of corals for broadcast spawning Fa = 0.01; // fraction of corals for asexual reproduction Fd = 0.8; // fraction of corals to remove Pd = 0.9; // probability of destruction attemptsNum = 20; // number of attempts for larvae to settle ArrayResize (params, 9); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "reefRows"; params [1].val = reefRows; params [2].name = "reefCols"; params [2].val = reefCols; params [3].name = "rho0"; params [3].val = rho0; params [4].name = "Fb"; params [4].val = Fb; params [5].name = "Fa"; params [5].val = Fa; params [6].name = "Fd"; params [6].val = Fd; params [7].name = "Pd"; params [7].val = Pd; params [8].name = "attemptsNum"; params [8].val = attemptsNum; } void SetParams () { popSize = (int)params [0].val; reefRows = (int)params [1].val; reefCols = (int)params [2].val; rho0 = params [3].val; Fb = params [4].val; Fa = params [5].val; Fd = params [6].val; Pd = params [7].val; attemptsNum = (int)params [8].val; } bool Init (const double &rangeMinP [], // minimum search range const double &rangeMaxP [], // maximum search range const double &rangeStepP [], // search step const int epochsP = 0); // number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int reefRows; // reef height int reefCols; // reef width double rho0; // initial reef occupancy double Fb; // fraction of corals for broadcast spawning double Fa; // fraction of corals for asexual reproduction double Fd; // fraction of corals to remove double Pd; // probability of destruction int attemptsNum; // number of attempts for larvae to settle private: //------------------------------------------------------------------- int totalReefSize; // total reef size bool occupied []; // flags of reef cell occupancy int reefIndices []; // agent indices in a[] corresponding to occupied cells // Auxiliary methods void InitReef (); int LarvaSettling (S_AO_Agent &larva); void BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount); void Brooding (S_AO_Agent &larvae [], int &larvaCount); void AsexualReproduction (); void Depredation (); int GetReefCoordIndex (int row, int col); void SortAgentsByFitness (int &indices [], int &count); }; //——————————————————————————————————————————————————————————————————————————————
El método "Init" inicializa el algoritmo CRO: llama a "StandardInit" de la clase básica, luego calcula el tamaño total del arrecife "totalReefSize", determina el número inicial de corales "initialPopSize", inicializa los arrays "occupied" (ocupación de celdas) y "reefIndices" (índices de corales), llama a "InitReef ()" para colocar los corales en el arrecife y finalmente devolverá "true" en caso de éxito.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_CRO::Init (const double &rangeMinP [], // minimum search range const double &rangeMaxP [], // maximum search range const double &rangeStepP [], // search step const int epochsP = 0) // number of epochs { // Standard initialization of the parent class if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Calculate the reef total size totalReefSize = reefRows * reefCols; // The number of starting corals should not exceed popSize int initialPopSize = (int)MathRound (rho0 * totalReefSize); if (initialPopSize > popSize) initialPopSize = popSize; // Initialize the occupancy array and indices ArrayResize (occupied, totalReefSize); ArrayResize (reefIndices, totalReefSize); // Fill the arrays with initial values for (int i = 0; i < totalReefSize; i++) { occupied [i] = false; reefIndices [i] = -1; } // Reef initialization InitReef (); return true; } //——————————————————————————————————————————————————————————————————————————————El método "InitReef ()" de la clase "C_AO_CRO" inicializa la población inicial de corales en el arrecife. Primero se calcula el número de corales a inicializar basándose en una densidad dada del arrecife (rho0), este número está limitado por el tamaño de la población "popSize". A continuación, para cada coral, se asigna una posición aleatoria pero libre en el arrecife; una vez encontrada, se marca como ocupada y el coral se vincula a esa posición en el array "reefIndices". Después se generan las coordenadas para cada coral. Cada coordenada se selecciona aleatoriamente dentro de los límites especificados (rangeMin, rangeMax) y se discretiza usando la función "u.SeInDiSp" que tiene en cuenta el paso de muestreo (rangeStep). Esto garantiza una distribución uniforme y controlada de las soluciones (corales) iniciales en el espacio de búsqueda.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::InitReef () { // Number of starting corals in the reef (based on rho0) int initialCorals = (int)MathRound (rho0 * totalReefSize); // The number of starting corals should not exceed the population size if (initialCorals > popSize) initialCorals = popSize; // Initialize initialCorals random positions in the reef for (int i = 0; i < initialCorals; i++) { int pos; // Look for a free position do { pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Protection against exceeding the array size if (pos < 0) pos = 0; if (pos >= totalReefSize) pos = totalReefSize - 1; } while (occupied [pos]); // Create a new coral at the found position occupied [pos] = true; reefIndices [pos] = i; // Generate random coordinates for a new coral for (int c = 0; c < coords; c++) { double coordinate = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (coordinate, rangeMin [c], rangeMax [c], rangeStep [c]); } } } //——————————————————————————————————————————————————————————————————————————————
El método "Moving ()" realiza una estimación inicial de la población de corales. Si "revision" se establece en "false", el método iterará a través de todas las posiciones del arrecife. Para cada posición ocupada (determinada por el valor del elemento del array "occupied"), el método recupera el índice del coral en esa posición del array "reefIndices". Si el índice "idx" resultante es válido, se realizará un cálculo de la aptitud de ese coral.
Debemos señalar que el método "Moving ()" no calcula directamente el alojamiento en sí, sino que solo proporciona la información necesaria para calcularlo. Una vez completada la iteración para todas las posiciones del arrecife, el método establecerá el valor "revision" en "true" para evitar que el ciclo de evaluación del coral vuelva a pasar por la misma iteración de optimización. Esencialmente, el método "Moving ()" actúa como disparador para calcular la aptitud de los corales, garantizando que este proceso se realice una vez en cada iteración de la optimización.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Moving () { if (!revision) { // Initial assessment of all corals in the reef for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { int idx = reefIndices [i]; if (idx >= 0 && idx < popSize) { // Calculating fitness does not require using GetFitness() // since it will be evaluated in external code (in FuncTests) } } } revision = true; } } //——————————————————————————————————————————————————————————————————————————————
El método "Revision ()" actualiza la mejor solución global: busca los corales en el arrecife con una aptitud mejor que la mejor solución global actual y la sustituye. Luego crea un array preparando espacio para las larvas producidas por la reproducción. A continuación, el método activa la reproducción sexual: llama a los métodos "BroadcastSpawning" y "Brooding" para crear larvas. El siguiente paso del método implementa el asentamiento de larvas, usando el método "LarvaSettling" para identificar las ubicaciones de las nuevas larvas en el arrecife. Después comienza la reproducción asexual "AsexualReproduction", al final tiene lugar la destrucción. En resumen: actualiza la solución, reproduce corales, coloca larvas y modela el impacto de la extinción.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Revision () { // Update the global best solution for (int i = 0; i < totalReefSize; i++) { if (occupied [i] && a [reefIndices [i]].f > fB) { fB = a [reefIndices [i]].f; ArrayCopy (cB, a [reefIndices [i]].c, 0, 0, WHOLE_ARRAY); } } // Form an array to store larvae S_AO_Agent larvae []; ArrayResize (larvae, totalReefSize * 2); // Allocate with reserve int larvaCount = 0; // Stage 1: Broadcast Spawning BroadcastSpawning (larvae, larvaCount); // Stage 2: Brooding Brooding (larvae, larvaCount); // Calculate the fitness function for each larva // (will be executed in external code in FuncTests) // Stage 3: Larval settlement for (int i = 0; i < larvaCount; i++) { LarvaSettling (larvae [i]); } // Stage 4: Asexual reproduction AsexualReproduction (); // Stage 5: Depredation Depredation (); } //——————————————————————————————————————————————————————————————————————————————
El método LarvaSettling simula el proceso de asentamiento de las larvas en el arrecife. Intenta encontrar un lugar adecuado para la larva y, o bien la coloca en el espacio vacante, o bien sustituye a un coral ya existente pero menos adaptable. Al intentar ubicarse, la larva intenta ubicarse "attemptsNum" veces. En cada intento se selecciona una posición aleatoria en el arrecife. Si la posición seleccionada está libre (no ocupada por un coral), el método buscará un índice libre en el array de agentes "a []", si se encuentra un índice libre, la larva copiará su solución (coordenadas "c []" y aptitud "f") en la celda correspondiente del array de agentes.
Luego la información de que la posición en el arrecife está ahora ocupada se actualizará, y el método retornará el índice de la posición ocupada con éxito "pos". Si la posición seleccionada está ocupada, el método comparará la aptitud de la larva con la aptitud del coral actual en esa posición. Si la larva es mejor, sustituirá al coral existente copiando sus parámetros en su celda del array de agentes, y el método devolverá el índice "pos" de la posición en la que se ha producido la sustitución. Si, después de todos los intentos, la larva no ha logrado ubicarse (ya sea en un espacio vacante o sustituyendo a un coral existente), el método devolverá -1.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::LarvaSettling (S_AO_Agent &larva) { // Try to settle the larva attemptsNum times for (int attempt = 0; attempt < attemptsNum; attempt++) { // Select a random position in the reef int pos = (int)MathFloor (u.RNDfromCI (0, totalReefSize)); // Check that the position is within the array if (pos < 0 || pos >= totalReefSize) continue; // If the position is free, populate the larva if (!occupied [pos]) { // Search for a free index in the agents array int newIndex = -1; for (int i = 0; i < popSize; i++) { bool used = false; for (int j = 0; j < totalReefSize; j++) { if (reefIndices [j] == i) { used = true; break; } } if (!used) { newIndex = i; break; } } if (newIndex != -1) { // Copy the larva's solution ArrayCopy (a [newIndex].c, larva.c, 0, 0, WHOLE_ARRAY); a [newIndex].f = larva.f; // Update information about the reef occupied [pos] = true; reefIndices [pos] = newIndex; return pos; } } // If the position is occupied, check if the larva is better than the current coral else if (occupied [pos] && reefIndices [pos] >= 0 && reefIndices [pos] < popSize && larva.f > a [reefIndices [pos]].f) { // The larva displaces the existing coral ArrayCopy (a [reefIndices [pos]].c, larva.c, 0, 0, WHOLE_ARRAY); a [reefIndices [pos]].f = larva.f; return pos; } } // If the larva failed to settle, return -1 return -1; } //——————————————————————————————————————————————————————————————————————————————
El método BroadcastSpawning simula la reproducción externa de los corales por desove. Realiza los siguientes pasos básicos: encuentra los índices de todos los lugares ocupados por el coral en el arrecife, determina el número de corales que participan en el desove basándose en el parámetro "Fb" (Brooding Fraction), la proporción de corales que participan en la reproducción externa, mezcla los índices de los corales ocupados y, a continuación, selecciona las parejas para el desove. Creación de larvas por cruce: se crea una nueva larva para cada pareja de corales, las coordenadas de la larva se calculan como la media de las coordenadas de los progenitores con una pequeña mutación aleatoria añadida. Este proceso de cruce busca combinar los mejores rasgos de los progenitores, las larvas creadas se añaden al array "larvae".
Puntos clave:
- "Fb" aquí es responsable de la proporción de corales en la reproducción externa, en contraposición a "Brooding", que se refiere a la proporción de corales dedicados a la reproducción interna.
- El cruce y la mutación aumentan la diversidad genética de una población.
- El objetivo del método es crear nuevas larvas derivadas de una combinación de genes de corales progenitores para que sigan colonizando el arrecife. El método consiste en el cruce por parejas.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::BroadcastSpawning (S_AO_Agent &larvae [], int &larvaCount) { // Find all occupied positions int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Check if there are no occupied positions if (occupiedCount == 0) return; // Select the Fb share for broadcast spawning int broadcastCount = (int)MathRound (Fb * occupiedCount); if (broadcastCount <= 0) broadcastCount = 1; // At least one coral if (broadcastCount > occupiedCount) broadcastCount = occupiedCount; // Shuffle the indices for (int i = 0; i < occupiedCount; i++) { // Register the array out-of-bounds problem int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Ensure that j is within the array bounds if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // Form pairs and create offspring for (int i = 0; i < broadcastCount - 1; i += 2) { if (i + 1 < broadcastCount) // Make sure there is a second parent { int idx1 = reefIndices [occupiedIndices [i]]; int idx2 = reefIndices [occupiedIndices [i + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) { // Initialize the larva larvae [larvaCount].Init (coords); // Create a new larva as a result of crossover for (int c = 0; c < coords; c++) { // Simple crossover method: average of parents' coordinates with a small mutation double value = (a [idx1].c [c] + a [idx2].c [c]) / 2.0 + u.RNDfromCI (-0.1, 0.1) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Increase the larvae counter larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
El método Brooding imita el proceso de incubación interna de larvas en corales en el CRO y sigue los pasos siguientes:
- determina qué posiciones del arrecife están ocupadas por corales y almacena los índices de estas posiciones.
- calcula cuántos corales participarán en la incubación de larvas usando el parámetro "Fb" (Brooding Fraction). Los índices de las posiciones ocupadas se barajan para seleccionar aleatoriamente los corales que participan en la reproducción.
- crea y muta las larvas: se crea una larva para cada coral seleccionado. La larva se inicializa y muta: sus coordenadas se desvían ligeramente de las del coral progenitor de forma aleatoria. Las larvas mutadas se añaden al array "larvae".
Puntos clave:
- "Fb" define la proporción de corales NO implicados en la reproducción asexual (es decir, implicados en la cría interna).
- La mutación aporta diversidad genética a la población larvaria.
- El objetivo es crear nuevos individuos, potencialmente mejores, que compitan por un lugar en el arrecife.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Brooding (S_AO_Agent &larvae [], int &larvaCount) { // Find all occupied positions int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // Check if there are no occupied positions if (occupiedCount == 0) return; // Number of corals for internal reproduction int broodingCount = (int)MathRound ((1.0 - Fb) * occupiedCount); if (broodingCount <= 0) broodingCount = 1; // At least one coral if (broodingCount > occupiedCount) broodingCount = occupiedCount; // Shuffle the indices for (int i = 0; i < occupiedCount; i++) { // Register the array out-of-bounds problem int j = (int)MathFloor (u.RNDfromCI (0, occupiedCount)); // Ensure that j is within the array bounds if (j >= 0 && j < occupiedCount && i < occupiedCount) { int temp = occupiedIndices [i]; occupiedIndices [i] = occupiedIndices [j]; occupiedIndices [j] = temp; } } // For each selected coral, create a mutated copy for (int i = 0; i < broodingCount; i++) { if (i < occupiedCount) // Check for out-of-bounds { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Initialize the larva larvae [larvaCount].Init (coords); // Create a new larva as a mutation of the original coral for (int c = 0; c < coords; c++) { // Mutation: add a small random deviation double value = a [idx].c [c] + u.RNDfromCI (-0.2, 0.2) * (rangeMax [c] - rangeMin [c]); larvae [larvaCount].c [c] = u.SeInDiSp (value, rangeMin [c], rangeMax [c], rangeStep [c]); } // Increase the larvae counter larvaCount++; } } } } //——————————————————————————————————————————————————————————————————————————————
El método de reproducción asexual modela la reproducción asexual de los corales por gemación. El método realiza los siguientes pasos: encuentra los índices de todas las posiciones ocupadas por corales en el arrecife, clasifica los índices de las posiciones ocupadas en orden descendente de aptitud, es decir, las posiciones con los corales más adaptables aparecen en primer lugar. Se basa en el parámetro "Fa" (Fraction for Asexual reproduction), que establece la proporción de corales que participan en la reproducción asexual. Se determina el número de mejores corales que producirán clones. Creación y asentamiento de clones: para cada coral seleccionado, se crea una copia exacta (clon), es decir, una larva con las mismas coordenadas y aptitud. Se llama al método "LarvaSettling" para intentar ubicar un clon en el arrecife.
Puntos clave:
- La reproducción asexual permite a los corales mejor adaptados propagar rápidamente sus genes.
- El parámetro "Fa" controla la intensidad de la reproducción asexual.
- Usar "LarvaSettling" para ubicar los clones implica que éstos deben competir por el espacio del arrecife del mismo modo que las larvas producidas sexualmente.
- El método de clonación, en este caso, supone una copia exacta del progenitor SIN mutaciones. Las mutaciones solo se producen durante la reproducción sexual.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::AsexualReproduction () { // Find all occupied positions and their indices int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // If there are no occupied positions, exit if (occupiedCount == 0) return; // Sort indices by fitness SortAgentsByFitness (occupiedIndices, occupiedCount); // Select the best Fa% of corals for asexual reproduction int budCount = (int)MathRound (Fa * occupiedCount); if (budCount <= 0) budCount = 1; // At least one coral if (budCount > occupiedCount) budCount = occupiedCount; // For each selected coral, create a clone and try to populate it for (int i = 0; i < budCount; i++) { if (i < occupiedCount) // Check for out-of-bounds { int idx = reefIndices [occupiedIndices [i]]; if (idx >= 0 && idx < popSize) { // Create a new larva as an exact copy of the original coral S_AO_Agent clone; clone.Init (coords); ArrayCopy (clone.c, a [idx].c, 0, 0, WHOLE_ARRAY); clone.f = a [idx].f; // Try to populate the clone LarvaSettling (clone); } } } } //——————————————————————————————————————————————————————————————————————————————
El método "Depredation" modela el proceso de extinción de los corales debido a la depredación o a otros factores negativos (por ejemplo, la contaminación). En este caso, la destrucción se aplica con una probabilidad "Pd". Si el número aleatorio es inferior a "Pd", se ejecutará el proceso de destrucción. La búsqueda de posiciones ocupadas determinará los índices de todas las posiciones del arrecife ocupadas por corales. Los índices de ocupación se clasifican según la aptitud (fitness) de los corales.
El array de índices ordenados se invierte para que los índices de los corales menos adaptados estén al principio del array. Luego se determina la cantidad de coral a eliminar en función del parámetro "Fd" (Fraction for Depredation). Este valor se redondea a un número entero. Después se elimina un número determinado de los corales menos adaptados. A continuación, se limpia el arrecife: para cada posición programada para eliminarse, la celda correspondiente del array "ocupado" se pone en "false", lo que indica que la posición está ahora libre. La celda correspondiente del array "reefIndices" se pone a -1, lo cual indica que no hay coral en esa posición.
//—————————————————————————————————————————————————————————————————————————————— oid C_AO_CRO::Depredation() { // Apply destruction with Pd probability if (u.RNDfromCI(0, 1) < Pd) { // Find all occupied positions and their indices int occupiedIndices[]; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied[i]) { ArrayResize(occupiedIndices, occupiedCount + 1); occupiedIndices[occupiedCount] = i; occupiedCount++; } } // If there are no occupied positions, exit if (occupiedCount == 0) return; // Sort indices by fitness SortAgentsByFitness(occupiedIndices, occupiedCount); // Reverse the array so the worst ones are first for (int i = 0; i < occupiedCount / 2; i++) { if(i < occupiedCount && (occupiedCount - 1 - i) < occupiedCount) // Check for out-of-bounds { int temp = occupiedIndices[i]; occupiedIndices[i] = occupiedIndices[occupiedCount - 1 - i]; occupiedIndices[occupiedCount - 1 - i] = temp; } } // Remove the worst Fd% corals int removeCount = (int)MathRound(Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // At least one coral if (removeCount > occupiedCount) removeCount = occupiedCount; // Overflow protection for (int i = 0; i < removeCount; i++) { if(i < occupiedCount) // Check for out-of-bounds { int pos = occupiedIndices[i]; if(pos >= 0 && pos < totalReefSize) // Additional check { occupied[pos] = false; reefIndices[pos] = -1; } } } } } //——————————————————————————————————————————————————————————————————————————————
El método "GetReefCoordIndex" convierte las coordenadas del arrecife (fila y columna) en un índice unidimensional y toma la fila "row" y la columna "col" como entrada, y devolverá el índice correspondiente en un array que representa el arrecife. El método comprueba primero si las coordenadas transmitidas están fuera de los límites del arrecife. En caso contrario, se calcula el índice mediante la fórmula (row * reefCols + col, donde "reefCols" es el número de columnas del arrecife). Este método se usa para acceder a los elementos de los arrays que representan el arrecife.
//—————————————————————————————————————————————————————————————————————————————— int C_AO_CRO::GetReefCoordIndex (int row, int col) { // Check for out-of-bounds if (row < 0 || row >= reefRows || col < 0 || col >= reefCols) return -1; // Convert a two-dimensional position to a one-dimensional index return row * reefCols + col; } //——————————————————————————————————————————————————————————————————————————————
El método "SortAgentsByFitness" clasifica el array de índices "indices" de los corales de "count" elementos en orden descendente según su aptitud utilizando un algoritmo de clasificación de burbujas que se realiza basándose en los valores de aptitud almacenados en el array "a" al que se accede a través del array "reefIndices". Así, tras la ejecución del método, "indices" contendrá los índices de los corales clasificados del más adaptado al menos adaptado. Hemos incluido comprobaciones adicionales para evitar que se sobrepasen los límites del array.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::SortAgentsByFitness (int &indices [], int &count) { // Check for an empty array if (count <= 0) return; // Bubble sort by decreasing fitness for (int i = 0; i < count - 1; i++) { for (int j = 0; j < count - i - 1; j++) { if (j + 1 < count) // Check that j+1 is not out of bounds { int idx1 = reefIndices [indices [j]]; int idx2 = reefIndices [indices [j + 1]]; if (idx1 >= 0 && idx1 < popSize && idx2 >= 0 && idx2 < popSize) // Check indices { if (a [idx1].f < a [idx2].f) { int temp = indices [j]; indices [j] = indices [j + 1]; indices [j + 1] = temp; } } } } } } //——————————————————————————————————————————————————————————————————————————————
Ya hemos terminado de preparar el algoritmo, y también hemos descrito en el código todos los numerosos métodos para su funcionamiento; ahora podemos proceder directamente a la prueba.
Resultados de las pruebas
Tras las pruebas, observamos que el algoritmo CRO funciona bastante mal y que es necesario revisar algunos métodos del enfoque original.CRO|Coral Reef Optimization|50.0|5.0|5.0|0.4|0.9|0.1|0.1|0.01|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.365266682511984
25 Hilly's; Func runs: 10000; result: 0.270828009448956
500 Hilly's; Func runs: 10000; result: 0.2504192846772352
=============================
5 Forest's; Func runs: 10000; result: 0.23618879234608753
25 Forest's; Func runs: 10000; result: 0.19453106526100442
500 Forest's; Func runs: 10000; result: 0.1679109693993047
=============================
5 Megacity's; Func runs: 10000; result: 0.13076923076923075
25 Megacity's; Func runs: 10000; result: 0.11138461538461542
500 Megacity's; Func runs: 10000; result: 0.09366153846153921
=============================
All score: 1.82096 (20.23%)
En primer lugar, hemos analizado en el algoritmo CRO el método de destrucción. Para mejorar la búsqueda, sustituiremos los peores corales del arrecife por otros nuevos que se generen en las proximidades de los mejores corales (soluciones), desplazando así la búsqueda hacia zonas más prometedoras. Luego determinaremos el número de corales mejores "eliteCount" y peores "removeCount".
Sustitución de las peores soluciones: para cada "víctima", se selecciona un coral "de élite" y se genera un nuevo coral en las proximidades de ese coral "de élite". En el mecanismo de destrucción mejorado, aplicaremos una distribución de potencia inversa con exponente 10 (donde la potencia = 0,1) para generar desviaciones de la mejor solución. Esta distribución se caracteriza por el hecho de que la mayoría de las nuevas soluciones se generan muy cerca de la mejor solución, pero con una pequeña probabilidad de que se produzcan desviaciones significativas, lo cual proporciona un equilibrio entre la búsqueda (explotación) local y la exploración global del espacio de soluciones. Las nuevas coordenadas se limitan al rango permitido. El lugar desocupado del arrecife se repoblará con nuevos corales.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_CRO::Depredation () { // Apply destruction with Pd probability if (u.RNDfromCI (0, 1) < Pd) { // Find all occupied positions and their indices int occupiedIndices []; int occupiedCount = 0; for (int i = 0; i < totalReefSize; i++) { if (occupied [i]) { ArrayResize (occupiedIndices, occupiedCount + 1); occupiedIndices [occupiedCount] = i; occupiedCount++; } } // If there are no occupied positions, exit if (occupiedCount == 0) return; // Sort the indices by fitness (from best to worst) SortAgentsByFitness (occupiedIndices, occupiedCount); // Determine the number of best solutions used to generate new ones int eliteCount = (int)MathRound (0.1 * occupiedCount); // Use top 10% if (eliteCount <= 0) eliteCount = 1; // At least one elite solution if (eliteCount > occupiedCount) eliteCount = occupiedCount; // Determine the number of worst solutions to be replaced int removeCount = (int)MathRound (Fd * occupiedCount); if (removeCount <= 0) removeCount = 1; // At least one solution is replaced if (removeCount > occupiedCount - eliteCount) removeCount = occupiedCount - eliteCount; // Do not remove elite solutions // Remove the worst solutions and replace them with new ones in the vicinity of the best ones for (int i = 0; i < removeCount; i++) { // Index of the solution to be removed (from the end of the sorted array) int removeIndex = occupiedCount - 1 - i; if (removeIndex < 0 || removeIndex >= occupiedCount) continue; int posToRemove = occupiedIndices [removeIndex]; if (posToRemove < 0 || posToRemove >= totalReefSize) continue; // Choose one of the elite solutions double power = 0.1; // Power distribution parameter double r = u.RNDfromCI (0, 1); int eliteIdx = (int)(eliteCount); if (eliteIdx >= eliteCount) eliteIdx = eliteCount - 1; int posBest = occupiedIndices [eliteIdx]; if (posBest < 0 || posBest >= totalReefSize) continue; int bestAgentIdx = reefIndices [posBest]; if (bestAgentIdx < 0 || bestAgentIdx >= popSize) continue; // Free up space for a new solution occupied [posToRemove] = false; // Generate a new solution in the neighborhood of the selected elite solution int newAgentIdx = reefIndices [posToRemove]; // Use the same agent index if (newAgentIdx >= 0 && newAgentIdx < popSize) { // Generation via power-law distribution around the best solution for (int c = 0; c < coords; c++) { // Determine the search radius (can be adapted depending on progress) double radius = 0.7 * (rangeMax [c] - rangeMin [c]); // 10% of the range // Generate a value using a power law double sign = u.RNDfromCI (0, 1) < 0.5 ? -1.0 : 1.0; // Random sign double deviation = sign * radius * MathPow (u.RNDfromCI (0, 1), 1.0 / power); // New value in the neighborhood of the best one double newValue = a [bestAgentIdx].c [c] + deviation; // Limit the value to an acceptable range a [newAgentIdx].c [c] = u.SeInDiSp (newValue, rangeMin [c], rangeMax [c], rangeStep [c]); } // Populate the new solution into the reef occupied [posToRemove] = true; reefIndices [posToRemove] = newAgentIdx; } } } } //——————————————————————————————————————————————————————————————————————————————
Ahora, tras los cambios realizados, probaremos el algoritmo CROm. Como podemos ver en los resultados de más abajo, el algoritmo ha mejorado mucho el rendimiento.
CROm|Optimización de Arrecifes de Coral M|50,0|20,0|20,0|0,2|0,99|0,01|0,8|0,9|20,0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7851210159578113
25 Hilly's; Func runs: 10000; result: 0.4603296933002806
500 Hilly's; Func runs: 10000; result: 0.25958379129490083
=============================
5 Forest's; Func runs: 10000; result: 0.8668751980437325
25 Forest's; Func runs: 10000; result: 0.3529695710837671
500 Forest's; Func runs: 10000; result: 0.16267582083006701
=============================
5 Megacity's; Func runs: 10000; result: 0.6323076923076923
25 Megacity's; Func runs: 10000; result: 0.2673846153846154
500 Megacity's; Func runs: 10000; result: 0.10733846153846247
=============================
All score: 3.89459 (43.27%)
La visualización del algoritmo no destaca especialmente: para el algoritmo resulta un poco más difícil hacer frente a problemas discretos en la función de prueba "Megacity".
CROm en la función de prueba Hilly
CROm en la función de prueba Forest
CROm en la función de prueba Megacity
Según los resultados de la prueba, el algoritmo CROm ocupa el puesto 42 en la tabla de clasificación de algoritmos de optimización basados en la població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 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | ASBO | adaptive social behavior optimization | 0.76331 | 0.49253 | 0.32619 | 1.58202 | 0.79546 | 0.40035 | 0.26097 | 1.45677 | 0.26462 | 0.17169 | 0.18200 | 0.61831 | 3.657 | 40.63 |
| 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
Los arrecifes de coral vivos son un sistema sutil en el que se mantiene constantemente un equilibrio entre estabilidad y variabilidad, entre el mantenimiento de estrategias de supervivencia probadas y la experimentación de otras nuevas. El mecanismo de extinción modificado con generación de nuevas soluciones en las proximidades de la mejor imita el proceso natural de éxito ecológico en los arrecifes de coral.
En la naturaleza, tras la muerte de algunas colonias, en las zonas desalojadas del arrecife no aparecen especies al azar, sino aquellas que se han adaptado con mayor éxito a las condiciones ambientales locales. Además, la tasa de supervivencia de las nuevas colonias resulta mayor en las zonas que rodean a las colonias que existen "con éxito", lo cual se refleja directamente en el algoritmo a través de la generación de nuevas soluciones alrededor de las soluciones "de élite". Esto garantiza que se exploren continuamente las áreas prometedoras del espacio de búsqueda y mantiene constante el tamaño de la población.
La aplicación de una distribución de potencia inversa (con exponente 10, donde la potencia = 0,1) permite generar desviaciones de la mejor solución. Esta distribución concentra la mayoría de las nuevas soluciones cerca de la mejor, con escasas desviaciones significativas, lo cual proporciona un equilibrio óptimo entre explotación local y exploración global.
Ampliar el radio de búsqueda al 70% del rango permitido permite al algoritmo explorar regiones más amplias del espacio de soluciones.
El uso exclusivo de las mejores soluciones como base para generar nuevas soluciones acelera la convergencia hacia regiones óptimas y mejora la calidad de las soluciones resultantes, mientras que una amplia variedad de operadores modelan aspectos clave de la evolución de los corales: la reproducción externa e interna, el asentamiento de larvas y la reproducción asexual pueden utilizarse en el desarrollo de otros métodos de optimización basados en poblaciones.
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 e inconvenientes del algoritmo CROm:
Ventajas:
- Es una idea interesante.
- Desarrollo prometedor.
- Resultados estables.
Desventajas:
- Resultados más débiles en funciones discretas.
- Gran número de parámetros externos.
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_AO_CROm.mq5 | Script | Banco de pruebas para CROm |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/17760
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.
Pruebas retrospectivas manuales simplificadas: herramientas personalizadas en MQL5 para el Probador de Estrategias
Trading con algoritmos: La IA y su camino hacia las alturas doradas
Redes neuronales en el trading: Actor—Director—Crítico (Actor—Director—Critic)
Automatización de estrategias de trading en MQL5 (Parte 14): Estrategia Trade Layering con técnicas estadísticas basadas en MACD y RSI
- 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