Algoritmo de búsqueda basado en cuervos — Crow Search Algorithm (CSA)
21
0
Introducción
En este artículo analizaremos el algoritmo Crow Search Algorithm (CSA), cuya idea me ha parecido muy prometedora; se trata de un método metaheurístico de enjambre propuesto para la optimización global. El CSA simula el comportamiento de los cuervos al ocultar comida en «escondites» y buscarla. El algoritmo es sencillo de implementar, tiene pocos parámetros y ha dado lugar a numerosas modificaciones y versiones híbridas; nosotros analizaremos la versión original.
El algoritmo CSA fue propuesto por Ali Askarzadeh y publicado en 2016 en la revista «Computers & Structures (Elsevier)».
Implementación del algoritmo
Imagínese en un parque a primera hora de la mañana. En una rama hay un cuervo: negro, brillante, con unos ojos en los que se refleja una idea. No es solo un pájaro, es un estratega. No son simplemente aves, sino auténticos analistas del mundo natural, las más inteligentes de todas las aves. El comportamiento inteligente de estas aves inspiró la creación del Crow Search Algorithm (CSA), ya que son capaces de hacer lo que debe saber hacer un buen algoritmo: buscar, memorizar, adaptarse y no dejarse engañar.
Habilidad 1: Memoria de los escondites. El cuervo encuentra un trozo de pan y lo esconde bajo las hojas. No se limita a lanzarlo: también recuerda el lugar. Al día siguiente, el cuervo regresa y sabe exactamente dónde buscar. En el algoritmo, esto significa que cada «cuervo» (agente) guarda su mejor posición como un escondite. Es su tesoro personal y no olvida dónde está.
Habilidad 2: Vigilar a los demás. Otro cuervo observa. Está posado en un poste de luz y observa dónde ha escondido la comida el primer cuervo. Después, cuando el primer cuervo se marcha volando, baja a comprobarlo. En el CSA, un agente elige a otro e intenta «seguirlo» hasta su escondite, ya que, si ese ha dado con una buena solución, ¿por qué no comprobarla?
Habilidad 3: El engaño. Sin embargo, el primer cuervo no es tan ingenuo. Sabe que pueden estar vigilándolo. Por eso hace una maniobra engañosa: finge que esconde la comida debajo de un arbusto, cuando en realidad la esconde detrás de una piedra. En el algoritmo ocurre lo mismo: si el agente «se da cuenta de que le están observando», lleva al perseguidor a un lugar aleatorio. Esto ayuda a que el algoritmo no se quede estancado en una sola solución, como si el cuervo dijera: «¿pensabas que te llevaría a un sitio donde hay mucha comida rica? ¡Ja, te he engañado!»
Habilidad 4: Adaptación. Los cuervos no actúan siguiendo un patrón fijo. Hoy esconden la comida entre la hierba; mañana, en una rendija de la valla. Lo intentan, aprenden y cambian de estrategia. En el CSA, los parámetros de movimiento y comportamiento pueden variar. El algoritmo no se queda estancado: se adapta, como un cuervo que busca la mejor forma de sobrevivir.
En definitiva, el cuervo no es solo un pájaro, sino una metáfora de la inteligencia, y el Crow Search Algorithm no es una fórmula árida. Es de un intento de trasladar al mundo de los números lo que hacen los cuervos cada día: «buscar lo mejor, defender lo suyo, aprender de los demás y ser lo suficientemente astutos como para no dejarse engañar».
Figura 1. Ilustración del funcionamiento del algoritmo CSA
En la ilustración anterior se muestran los principales escenarios y las reglas de funcionamiento del algoritmo. Tras analizar en profundidad las estrategias del método de optimización CSA, podemos elaborar un pseudocódigo detallado del algoritmo.
- Configurar los parámetros:
- N = número de cuervos (tamaño de la población)
- max_iter = número máximo de iteraciones
- fl = longitud de vuelo (flight length)
- AP = probabilidad de conciencia (awareness probability)
- d = dimensión del problema
- Inicializar la población:
- Para cada cuervo i, de 1 a N:
- Posición[i] = posición aleatoria en el espacio de búsqueda
- Calcular fitness de posición[i]
- Memoria[i] = Posición[i] (inicialmente, la memoria es igual a la posición actual)
- Fitness_memoria[i] = fitness de posición[i]
- Para cada cuervo i, de 1 a N:
- Repetir para cada iteración t, desde 1 hasta max_iter:
- Para cada cuervo i, de 1 a N: a. Elegir un objetivo al que seguir:
- Seleccionar al azar un cuervo j (donde j ≠ i)
- r = número aleatorio entre 0 y 1
- Para cada dimensión k:
- ri = número aleatorio entre 0 y 1
- Nueva_posición[i][k] = Posición[i][k] + ri × fl × (Memoria[j][k] - Posición[i][k])
- Nueva_posición[i] = posición aleatoria en el espacio de búsqueda
- Asegurarse de que Nueva_posición[i] se encuentre dentro de los límites
- Si la posición queda fuera de los límites, devolverla al límite correspondiente
- Calcular el fitness de las nuevas posiciones:
- Para cada cuervo i:
- Fitness_nuevo[i] = calcular fitness(Nueva_posición[i])
- Para cada cuervo i:
- Actualizar la memoria:
- Para cada cuervo i:
- SI Fitness_nuevo[i] es mejor que Fitness_memoria[i]:
- Memoria[i] = Nueva_posición[i]
- Fitness_memoria[i] = Fitness_nuevo[i]
- SI NO:
- La memoria no cambia
- SI Fitness_nuevo[i] es mejor que Fitness_memoria[i]:
- Para cada cuervo i:
- Actualizar las posiciones actuales:
- Para cada cuervo i:
- Posición[i] = Nueva_posición[i]
- Para cada cuervo i:
- Para cada cuervo i, de 1 a N: a. Elegir un objetivo al que seguir:
- Encontrar la mejor solución:
- Mejor_solución = Memoria con el mejor fitness entre todos los cuervos
- Devolver Mejor_solución
Pasemos a lo más importante: escribir el código. La estructura «S_CrowMemory» está diseñada para almacenar información sobre la «memoria» del cuervo:
- Dimensión de la posición — número de coordenadas que componen una «posición» en esta memoria.
- Valores de las coordenadas de la posición — array en el que cada número representa el valor concreto de una coordenada de esa posición.
- Valor de fitness — indica en qué medida esta posición es «buena» o «apta».
El método «Init» sirve para inicializar esta estructura. Al invocarlo, se pasa el número de dimensiones. Este método reserva el espacio necesario para almacenar las coordenadas de la posición en función del número de dimensiones recibido y establece el valor inicial de fitness en un número muy pequeño (el valor más negativo posible), de modo que cualquier evaluación real de fitness que se obtenga sea mayor.
//———————————————————————————————————————————————————————————————————— // Estructura para el almacenamiento de la memoria del cuervo struct S_CrowMemory { double position[]; // posición en la memoria double fitness; // fitness de la posición en la memoria void Init(int dimensions) { ArrayResize(position, dimensions); fitness = -DBL_MAX; } }; //————————————————————————————————————————————————————————————————————
La clase «C_AO_CrowSearchAlgorithm» es una implementación del algoritmo de búsqueda basado en el comportamiento de los cuervos. Hereda de la clase base «C_AO». Al crear un objeto de la clase, además de establecer el nombre y la descripción, se inicializan los parámetros principales del algoritmo:
- popSize — número de agentes (cuervos) en la población,
- flightLength — parámetro que determina la distancia recorrida por el cuervo durante el vuelo,
- awarenessProbability — la probabilidad de que un cuervo «sea consciente» de su entorno y de las acciones de otros cuervos.
- SetParams () — este método sirve para actualizar los parámetros internos del algoritmo a partir de una fuente externa (del array «params»).
- Init () — punto principal de inicialización de todo el algoritmo. Acepta rangos de valores admisibles para los parámetros de búsqueda (mínimo, máximo, paso) y el número total de épocas (iteraciones).
- Moving () — se encarga del movimiento principal y de la actualización de las posiciones de los cuervos en el espacio de búsqueda en cada iteración del algoritmo.
- Revision () — realiza una comprobación y corrección de los estados, así como una evaluación de la calidad de las soluciones encontradas, tras cada iteración.
- InitializeMemory () — inicializa la memoria para todos los cuervos de la población,
- SelectRandomCrow () — selecciona un cuervo al azar de la población, excluyendo al cuervo especificado,
- UpdateMemory () — actualiza la entrada en memoria correspondiente a un cuervo concreto.
- flightLength — longitud de vuelo, parámetro del algoritmo
- awarenessProbability — probabilidad de conciencia, parámetro del algoritmo
//———————————————————————————————————————————————————————————————————— class C_AO_CrowSearchAlgorithm : public C_AO { public: //---------------------------------------------------------- ~C_AO_CrowSearchAlgorithm () { } C_AO_CrowSearchAlgorithm () { ao_name = "CSA"; ao_desc = "Crow Search Algorithm"; ao_link = "https://www.mql5.com/ru/articles/19669"; popSize = 20; // tamaño de la población (número de cuervos) flightLength = 2.0; // longitud de vuelo (fl) awarenessProbability = 0.1; // probabilidad de conciencia (AP) ArrayResize (params, 3); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "flightLength"; params [1].val = flightLength; params [2].name = "awarenessProbability"; params [2].val = awarenessProbability; } void SetParams () { popSize = (int)params [0].val; flightLength = params [1].val; awarenessProbability = params [2].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP); void Moving (); void Revision (); private: void InitializeMemory (); int SelectRandomCrow (int excludeCrow); void UpdateMemory (int crowIndex); //------------------------------------------------------------------ public: double flightLength; // longitud de vuelo (fl) double awarenessProbability; // probabilidad de conciencia (AP) private: //--------------------------------------------------------- S_CrowMemory crowMemory[]; // memoria de los cuervos (array de estructuras) }; //————————————————————————————————————————————————————————————————————
El método «Init» es el punto de partida para ejecutar el algoritmo de búsqueda basado en cuervos. Su función principal es preparar todas las estructuras necesarias y comprobar que los parámetros de entrada sean correctos.
Inicialización estándar. En primer lugar, se invoca el método «StandardInit», que lleva a cabo los preparativos generales necesarios para cualquier algoritmo de optimización: establece los intervalos de búsqueda, el paso, el número de épocas y determina el número de «dimensiones». Si esta inicialización estándar falla, el método «Init» devuelve inmediatamente «false».
Inicialización de la memoria de los cuervos. Se asigna memoria para el array de estructuras «crowMemory», cuyo tamaño es igual a «popSize» (el número de cuervos de la población). A continuación, se invoca el método «Init» propio de cada cuervo de ese array. Este método, a su vez, configura la estructura de memoria del cuervo, indicando cuántas dimensiones (parámetros) debe tener en cuenta (este valor se toma de «coords», establecido por «StandardInit»), y establece el valor inicial de fitness .
Comprobación y ajuste de los parámetros. Se comprueba el parámetro «flightLength». Si es menor o igual que cero, se le asigna el valor por defecto (2,0). Se comprueba el parámetro «awarenessProbability». Si es menor que cero, se le asigna el valor 0,0. Si es mayor que uno, se le asigna el valor 1,0. Estas comprobaciones garantizan que los parámetros probabilísticos se mantengan dentro del rango admisible.
Se devuelve el resultado. Si todos los pasos de inicialización se han completado correctamente, el método devuelve «true» y el algoritmo está listo para funcionar.//———————————————————————————————————————————————————————————————————— //--- Inicialización bool C_AO_CrowSearchAlgorithm::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Inicialización de un array de estructuras de memoria ArrayResize (crowMemory, popSize); for (int i = 0; i < popSize; i++) { crowMemory[i].Init(coords); } // Comprobación de la corrección de los parámetros if (flightLength <= 0.0) flightLength = 2.0; if (awarenessProbability < 0.0) awarenessProbability = 0.0; if (awarenessProbability > 1.0) awarenessProbability = 1.0; return true; } //————————————————————————————————————————————————————————————————————
El método «InitializeMemory» se encarga de rellenar inicialmente la «memoria» de cada cuervo con información sobre su posición actual y la calidad de fitness.
Recorrido por todos los cuervos. El método recorre cada cuervo de la población, utilizando un bucle que va de cero a «popSize» (el número total de cuervos).
Copiado de la posición. Para cada cuervo «i» se copia su posición actual; «a [i].c» contiene las coordenadas actuales del cuervo «i» (en forma de array), mientras que «coords» representa el número de dimensiones (parámetros) del espacio de búsqueda. Estas coordenadas se guardan a continuación en «crowMemory [i].position», es decir, en la memoria del cuervo «i».
Almacenamiento del fitness. Junto con la posición, se guarda en «crowMemory [i].fitness» el valor de fitness (calidad) de la posición actual del cuervo, «a [i].f».De este modo, tras ejecutar este método, cada cuervo almacenará en su estructura de memoria (crowMemory) la información sobre la posición que ocupaba al inicio del algoritmo y el valor de fitness correspondiente. Este es el punto de partida para el proceso de optimización posterior, en el que los cuervos utilizarán esta «memoria primaria» para tomar decisiones sobre sus desplazamientos.
//———————————————————————————————————————————————————————————————————— //--- Inicialización de la memoria de los cuervos void C_AO_CrowSearchAlgorithm::InitializeMemory () { // Inicializamos la memoria con las posiciones actuales for (int i = 0; i < popSize; i++) { ArrayCopy (crowMemory[i].position, a[i].c, 0, 0, coords); crowMemory[i].fitness = a[i].f; } } //————————————————————————————————————————————————————————————————————
El método «SelectRandomCrow» sirve para seleccionar un cuervo al azar de toda la población, garantizando que el cuervo seleccionado no sea aquel que queremos excluir (el indicado en el parámetro «excludeCrow»).
Comprobación del tamaño de la población. Si en la población solo hay un cuervo (popSize <= 1), el único cuervo disponible es el que tiene el índice «0», por lo que es el que se devuelve.
Generación de un índice aleatorio. El método entra en un bucle «do-while». Dentro del bucle se genera un número aleatorio (selectedCrow), que representa el índice del cuervo potencialmente seleccionado. Para la generación se utiliza la función «u.RNDfromCI», que devuelve un número aleatorio en el intervalo comprendido entre 0,0 y «popSize» (excluyendo el límite superior, por lo que se añade un pequeño desplazamiento). El número fraccionario obtenido se convierte en un número entero. Se realizan comprobaciones adicionales para garantizar que el índice obtenido se encuentre dentro de los límites admisibles del array de la población. Si el índice se sale de esos límites, se corrige.
Condición de exclusión. El bucle «do-while» sigue generando índices aleatorios hasta que el valor generado «selectedCrow» sea diferente de «excludeCrow». Es decir, si por casualidad se ha seleccionado el cuervo que queremos descartar, el proceso se repite.
Devolución del cuervo seleccionado. En cuanto se genera un índice aleatorio que no coincida con «excludeCrow», dicho índice se devuelve como resultado del método.
//———————————————————————————————————————————————————————————————————— //--- Selección de un cuervo al azar (excluyendo el indicado) int C_AO_CrowSearchAlgorithm::SelectRandomCrow (int excludeCrow) { if (popSize <= 1) return 0; int selectedCrow; do { selectedCrow = (int)MathFloor(u.RNDfromCI(0.0, popSize - 0.001)); if (selectedCrow >= popSize) selectedCrow = popSize - 1; if (selectedCrow < 0) selectedCrow = 0; } while (selectedCrow == excludeCrow); return selectedCrow; } //————————————————————————————————————————————————————————————————————
El método «Moving» es el principal mecanismo de funcionamiento del algoritmo de búsqueda basado en cuervos. Se encarga del movimiento y la actualización de las posiciones de los cuervos durante el proceso de búsqueda. El método consta de dos fases: la inicialización y el ciclo principal de iteraciones.
Fase 1: Inicialización de la población (en la primera ejecución). Si el algoritmo se ejecuta por primera vez (lo que se determina mediante el indicador «revision»), se inicializan todos los cuervos. Para cada cuervo de la población, sus coordenadas (a [i].c) se rellenan con valores aleatorios. Estos valores se generan dentro de los intervalos especificados (rangeMin, rangeMax) y teniendo en cuenta unos pasos determinados (rangeStep), lo que garantiza que las posiciones iniciales de los cuervos sean válidas. Tras la inicialización, el indicador «revision» se establece en «verdadero» para que la siguiente llamada al método pase a la fase del ciclo principal.
Fase 2: Ciclo principal de iteraciones (tras la inicialización). Este ciclo se ejecuta en cada iteración del algoritmo e incluye los siguientes pasos para cada cuervo:
- Guardar la posición anterior. Antes de generar una nueva posición, la posición actual (a [i].c) y el valor de fitness (a [i].f) del cuervo actual se guardan en las variables que almacenan los valores anteriores (a [i].cP y a [i].fP, respectivamente). Esto permite volver a la posición anterior si la nueva resulta ser peor,
- Elección del «rival». Se elige al azar otro cuervo (j) de la población. El cuervo seleccionado será aquel al que se seguirá. Es importante que el cuervo seleccionado no sea el mismo que estamos procesando ahora mismo (SelectRandomCrow(i) lo garantiza),
- Determinación del escenario de movimiento. Se genera un número aleatorio (r_j) entre 0 y 1 y se compara con el parámetro «awarenessProbability» (probabilidad de conciencia). Este parámetro determina cómo se moverá el cuervo:
-
Escenario 1: Un cuervo sigue a otro (Fórmula 1)
- Si «r_j» es mayor o igual que «awarenessProbability», esto significa que el cuervo «i» intentará acercarse a la mejor posición, basándose en la posición del cuervo «j» seleccionado.
- La nueva posición se calcula mediante la fórmula: nueva posición = posición actual + paso aleatorio * longitud de vuelo * (posición del cuervo (j) - posición actual).
- El paso aleatorio (r_i) es otro número aleatorio que aporta variabilidad.
- La longitud de vuelo «flightLength» es un parámetro que controla hasta dónde puede desplazarse el cuervo.
- Posición del cuervo (j) - posición_actual: vector dirigido desde la posición actual hacia la posición del cuervo seleccionado para seguirlo.
- Una vez calculada la nueva posición, también se comprueba que se encuentre dentro de los intervalos especificados (rangeMin, rangeMax, rangeStep).
-
Escenario 2: Desplazamiento completamente aleatorio (Fórmula 2)
- Si «r_j» es menor que «awarenessProbability», esto significa que el cuervo «j» «se da cuenta» de que lo están siguiendo y toma medidas enérgicas.
- En este caso, el cuervo «i» ignora la posición del cuervo «j» y se desplaza a una posición aleatoria completamente nueva dentro de todo el espacio de búsqueda.
- Esta nueva posición aleatoria también se genera teniendo en cuenta los rangos y los incrementos permitidos.
//———————————————————————————————————————————————————————————————————— //--- Paso principal del algoritmo (fórmulas 1 y 2 del documento) void C_AO_CrowSearchAlgorithm::Moving () { // Inicialización de la población if (!revision) { // Paso 1: Inicialización aleatoria de la población de cuervos for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } //------------------------------------------------------------------ // Ciclo principal de iteración // Paso 5: Generación de una nueva posición para cada cuervo for (int i = 0; i < popSize; i++) { // Guardamos las posiciones actuales en cP (coordenadas anteriores) ArrayCopy (a[i].cP, a[i].c, 0, 0, coords); a[i].fP = a[i].f; // Elegimos al azar un cuervo j al que seguir (excluyendo al propio cuervo) int j = SelectRandomCrow(i); // Generamos un número aleatorio para determinar si el cuervo es consciente de que lo siguen double r_j = u.RNDfromCI(0.0, 1.0); // Aplicamos las fórmulas de actualización de la posición según los escenarios if (r_j >= awarenessProbability) { // Escenario 1: El cuervo j no sabe que lo están vigilando // Fórmula (1): P_i^(t+1) = P_i^t + r_i * fl_j * (M_j^t - P_i^t) for (int c = 0; c < coords; c++) { double r_i = u.RNDfromCI(0.0, 1.0); a[i].c[c] = a[i].c[c] + r_i * flightLength * (crowMemory[j].position[c] - a[i].c[c]); // Paso 6: Comprobación de la admisibilidad de la nueva posición a[i].c[c] = u.SeInDiSp (a[i].c[c], rangeMin[c], rangeMax[c], rangeStep[c]); } } else { // Escenario 2: El cuervo j se da cuenta de que lo están vigilando // Fórmula (2): Desplazamiento a una posición aleatoria 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]); } } } } //————————————————————————————————————————————————————————————————————
El método «UpdateMemory» se encarga de actualizar la «memoria» de un cuervo concreto. La memoria del cuervo almacena la mejor posición que ha encontrado y el valor de fitness correspondiente.
Comparación del fitness actual con el almacenado. El método recibe el índice «crowIndex» del cuervo cuya memoria hay que actualizar. Compara el valor de fitness de la posición actual de este cuervo, «a [crowIndex].f», con el valor de fitness guardado previamente en su memoria.
Actualización de la memoria (si la nueva posición es mejor). Si el fitness actual es mejor que el almacenado anteriormente, se lleva a cabo una actualización: la posición actual del cuervo se copia en su memoria y el valor actual de fitness se copia en la memoria como el nuevo mejor valor encontrado.
De este modo, este método garantiza que la memoria de cada cuervo conserve siempre la información sobre el mejor punto al que ha llegado hasta ese momento. Si el cuervo encuentra una nueva posición que le proporciona un valor de fitness más alto, «memoriza» esa nueva posición y su fitness. De lo contrario, la memoria no sufre ningún cambio.
//———————————————————————————————————————————————————————————————————— //--- Actualización de la memoria del cuervo void C_AO_CrowSearchAlgorithm::UpdateMemory (int crowIndex) { // Fórmula (3): Actualizamos la memoria si la nueva posición es mejor if (a[crowIndex].f > crowMemory[crowIndex].fitness) { ArrayCopy (crowMemory[crowIndex].position, a[crowIndex].c, 0, 0, coords); crowMemory[crowIndex].fitness = a[crowIndex].f; } } //————————————————————————————————————————————————————————————————————
El método «Revision» se encarga de evaluar y actualizar los resultados tras cada ciclo principal de desplazamiento de los cuervos.
Inicialización de la memoria. Al ejecutar el algoritmo por primera vez (cuando los valores de fitness en la memoria de los cuervos están establecidos en el valor mínimo posible, lo que indica que aún no son válidos), se invoca un método independiente para inicializar la memoria. Esto garantiza que cada cuervo disponga de una «base» correctamente cumplimentada para la comparación.
Actualización de la memoria individual de cada cuervo. El método recorre todos los cuervos de la población y, para cada uno de ellos, se invoca el método «UpdateMemory», que compara la posición actual del cuervo con su mejor posición memorizada. Si la nueva posición es mejor, se actualiza la memoria de este cuervo.
Actualización de las mejores soluciones globales. El método vuelve a recorrer todos los cuervos, pero esta vez con el objetivo de encontrar la mejor y la peor solución entre las posiciones actuales de todos los cuervos. Si la posición actual de algún cuervo (a [i].f) resulta ser mejor que el mejor valor global conocido (fB), ese valor y la posición correspondiente se guardan como la nueva mejor solución global (fB y cB).
Comprobación adicional de la memoria. Tras evaluar las posiciones actuales, se lleva a cabo otra comprobación, pero esta vez de la memoria individual de cada cuervo. Si alguna de las mejores posiciones (máximas) almacenadas en la memoria (crowMemory [i].fitness) resulta ser mejor que la mejor solución global actual (fB), se actualiza la mejor solución global. Esto es importante, ya que el método «UpdateMemory» puede haber actualizado la memoria del cuervo, pero después el cuervo puede haberse alejado de esa mejor posición en la iteración actual.Por lo tanto, el método «Revision» constituye un punto de recopilación de información tras cada paso del algoritmo. Mantiene actualizados tanto los mejores resultados individuales de cada cuervo como la mejor y la peor solución global encontradas por toda la población en ese momento.
//———————————————————————————————————————————————————————————————————— //--- Actualización y verificación de los resultados void C_AO_CrowSearchAlgorithm::Revision () { // Si se trata de la primera iteración tras la inicialización if (crowMemory[0].fitness == -DBL_MAX) { InitializeMemory(); } // Paso 8: Actualización de la memoria de cada cuervo for (int i = 0; i < popSize; i++) { UpdateMemory(i); } // Actualizamos la mejor solución global for (int i = 0; i < popSize; i++) { if (a[i].f > fB) { fB = a[i].f; ArrayCopy (cB, a[i].c, 0, 0, WHOLE_ARRAY); } } // Además, comprobamos si hay mejores soluciones en la memoria for (int i = 0; i < popSize; i++) { if (crowMemory[i].fitness > fB) { fB = crowMemory[i].fitness; ArrayCopy (cB, crowMemory[i].position, 0, 0, WHOLE_ARRAY); } } } //————————————————————————————————————————————————————————————————————
Resultados de las pruebas
Como puede observarse, los resultados son de nivel medio, con un rendimiento inferior en la función discreta Megacity.
=============================
5 Hilly's; Func runs: 10000; result: 0.7780377334241331
25 Hilly's; Func runs: 10000; result: 0.5107983411957056
500 Hilly's; Func runs: 10000; result: 0.2671707154561419
=============================
5 Forest's; Func runs: 10000; result: 0.9221928451900311
25 Forest's; Func runs: 10000; result: 0.48104687904934185
500 Forest's; Func runs: 10000; result: 0.16367212698152436
=============================
5 Megacity's; Func runs: 10000; result: 0.4846153846153848
25 Megacity's; Func runs: 10000; result: 0.34215384615384614
500 Megacity's; Func runs: 10000; result: 0.11487692307692406
=============================
All score: 4.06456 (45.16%)
En la visualización se aprecia una gran dispersión en las funciones de baja dimensión, y las largas líneas horizontales verdes indican un estancamiento en extremos locales. También se observa una ligera dispersión en las funciones de dimensión media. Las mayores dificultades del algoritmo se presentan en los problemas de alta dimensión, representados por las líneas rojas.
CSA_crow en la función de prueba Hilly
CSA_crow en la función de prueba Forest
CSA_crow en la función de prueba Megacity
Tras una serie de pruebas, el algoritmo CSA_crow se incluye en la tabla de clasificación a título informativo.
| N.º | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of 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 | DOAdingom | dingo_optimization_algorithm_M | 0,47968 | 0,45367 | 0,46369 | 1,39704 | 0,94145 | 0,87909 | 0,91454 | 2,73508 | 0,78615 | 0,86061 | 0,84805 | 2,49481 | 6,627 | 73,63 |
| 2 | 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 |
| 3 | 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 |
| 4 | 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 |
| 5 | (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 |
| 6 | 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 |
| 7 | 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 |
| 8 | 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 |
| 9 | 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 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 14 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | AOSm | atomic orbital search 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 |
| 21 | 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 |
| 22 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 23 | 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 |
| 24 | 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 |
| 25 | CRO | chemical reaction optimisation | 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 |
| 26 | 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 |
| 27 | DOA | dream_optimization_algorithm | 0,85556 | 0,70085 | 0,37280 | 1,92921 | 0,73421 | 0,48905 | 0,24147 | 1,46473 | 0,77231 | 0,47354 | 0,18561 | 1,43146 | 4.825 | 53,62 |
| 28 | 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 |
| 29 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4.762 | 52,91 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | (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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 42 | 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 |
| 43 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 44 | DA_duelist | duelist_algorithm | 0,92782 | 0,53778 | 0,27792 | 1,74352 | 0,86957 | 0,47536 | 0,18193 | 1,52686 | 0,62153 | 0,33569 | 0,11715 | 1,07437 | 4,345 | 48,28 |
| 45 | 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 |
| CSA_crow | crow_search_algorithm | 0,77804 | 0,51080 | 0,26717 | 1,55601 | 0,92219 | 0,48105 | 0,16367 | 1,56691 | 0,48461 | 0,34215 | 0,11487 | 0,94163 | 4,065 | 45,16 | |
| RW | random walk | 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
Tras una serie de pruebas, el algoritmo no ha logrado situarse en la tabla de clasificación de los algoritmos de optimización poblacionales; se ha quedado un poco corto, pero se trata de un método muy prometedor. Sencillez elegante: es un algoritmo verdaderamente completo y autónomo. Es difícil añadir algo sin alterar el concepto básico. El problema es que la simplicidad, que es una ventaja para la comprensión, se convierte en un inconveniente para el rendimiento en este caso. No puedo decir que sea un mal método de optimización; tiene sus ventajas, pero se atasca, sobre todo en funciones de baja dimensión. A pesar de que los resultados generales no son muy buenos, el algoritmo muestra estabilidad en el sentido de que «no presenta grandes caídas en ningún tipo de problema» según la escala de colores, a diferencia de algunos algoritmos que se encuentran entre los mejores, pero que aparecen en rojo en determinados tipos de problemas.
Fundamento biológico: la metáfora de los cuervos resulta intuitiva y lógica, lo que hace que el algoritmo sea fácil de entender e implementar. Existen numerosas modificaciones del CSA (con vuelos de Lévy, parámetros adaptativos y mapas caóticos), pero la mayoría de ellas complican mucho el algoritmo, le hacen perder su principal ventaja — la simplicidad—, aportan una mejora limitada del rendimiento y convierten al CSA en un híbrido con otros métodos.
Mínimo de parámetros: solo 3 ajustes (N, fl, AP), lo que simplifica la configuración en comparación con metaheurísticas más complejas. El CSA es un buen recurso didáctico y un método básico de optimización muy válido. No es revolucionario, pero resulta fiable para tareas sencillas; en el arsenal del operador, su papel es el de una opción de reserva: cuando los métodos más complejos resultan excesivos o cuando importa la sencillez de implementación.
Figura 2. Escala de colores de los algoritmos según las pruebas correspondientes
Figura 3. Histograma de los resultados de las pruebas de los algoritmos (en una escala de 0 a 100; cuanto mayor sea el valor, mejor, donde 100 es el resultado teórico máximo posible; en el archivo se incluye el script para calcular la tabla de clasificación)
Ventajas e inconvenientes del algoritmo CSA_crow:
Ventajas:
- Es una idea atractiva y prometedora como punto de partida para futuros desarrollos.
- Tiene un número reducido de parámetros.
Desventajas:
- Gran variabilidad en los resultados.
- Baja eficacia en problemas de alta dimensión.
Se adjunta al artículo un archivo comprimido con las versiones actualizadas de los códigos de los algoritmos. El autor del artículo no se hace responsable de la exactitud absoluta de las descripciones de los algoritmos canónicos, ya que en muchos de ellos se han introducido modificaciones para mejorar las capacidades de búsqueda. Las conclusiones y consideraciones que figuran en los artículos se basan en los resultados de los experimentos realizados.
Programas utilizados en el artículo
| # | Nombre | Tipo | Descripción |
|---|---|---|---|
| 1 | #C_AO.mqh | Archivo de inclusión | Clase padre de los algoritmos de optimización poblacional |
| 2 | #C_AO_enum.mqh | Archivo de inclusión | Enumeración de algoritmos de optimización poblacional |
| 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 destinados a la tabla comparativa |
| 7 | Testing AOs.mq5 | Script | Banco de pruebas unificado para todos los algoritmos de optimización poblacional |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Ejemplo sencillo de uso de algoritmos de optimización poblacional sin visualización |
| 9 | Test_AO_CSA_crow.mq5 | Script | Banco de pruebas para CSA_crow |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/19669
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.
