Algoritmos de optimización de la población: Algoritmo de optimización de cuco (Cuckoo Optimization Algorithm — COA)
683
0
Contenido:
1. Introducción2. Descripción del algoritmo, árbol de decisión y vuelo de Levy
3. Analizamos el código COA
4. Resultados de la prueba
1. Introducción
El cuco es un ave fascinante, no solo por el extraordinario sonido de su canto, sino también por su agresiva estrategia de reproducción, que consiste en poner los huevos en los nidos de otras aves, transfiriendo por completo a otras especies las responsabilidades parentales respecto a sus crías. Cada especie tiene una puesta de huevos inherente, con un cierto color y tamaño para que coincida mejor con los huevos de varios padres adoptivos. Los polluelos de cuco dejados en los nidos de otras especies suelen ser más grandes y fuertes que los propios pollitos de los dueños del nido, por lo que los cucos necesitan más comida. Durante su evolución, los polluelos de cuco de Hodgson han desarrollado un patrón especial en sus alas con forma de pico abierto que les permite obtener más comida de los padres adoptivos debido a esta ilusión. Pero esta cualidad no es ni mucho menos la única: se ha detectado parasitismo de anidación en al menos 80 especies de aves. Además, este fenómeno está muy extendido en algunas especies de insectos sociales: abejorros, abejas y hormigas, cuyas hembras penetran en una colonia extraña, eliminan a la reina y ponen sus propios huevos. El parasitismo de anidación también existe en los peces, como por ejemplo en el siluro del lago africano Tanganica, que deja sus huevas a otros peces, que las incuban en la boca.
La búsqueda de cuco es uno de los últimos algoritmos heurísticos inspirados en la naturaleza desarrollados por Yang y Deb 2009, y se basa en el parasitismo de algunas especies de cucos. Este algoritmo ha sido mejorado todavía más por los llamados vuelos de Levy, en lugar de simples métodos isotrópicos de paseo aleatorio.
2. Descripción del algoritmo
El algoritmo de optimización de cuco (COA) se usa para la optimización no lineal continua. El COA está inspirado en el estilo de vida de esta familia de aves. El estilo de vida de esta especie, así como sus características de oviposición y reproducción son la base del desarrollo de este algoritmo de optimización. Al igual que otros enfoques evolutivos, el COA comienza con una población inicial. La base del algoritmo es el intento de supervivencia: compitiendo por la supervivencia, algunos de ellos mueren. Los cucos supervivientes se mudan a mejores lugares y comienzan a reproducirse y poner huevos. Finalmente, los cucos supervivientes convergen de tal forma que se obtiene una sociedad de cucos con valores de aptitud similares.
La principal ventaja de este método es su simplicidad: la búsqueda de cuco requiere solo cuatro parámetros comprensibles, por lo que su ajuste se convertirá en una tarea bastante obvia.
En el algoritmo de búsqueda de cuco, los huevos del nido se interpretarán como posibles soluciones al problema de optimización, mientras que el huevo del cuco representará la nueva solución. El objetivo final del método consistirá en utilizar estas nuevas (y potencialmente mejores) soluciones de huevos de cuco parasitarios para reemplazar la solución actual, relacionada con los huevos en el nido. Este reemplazo, realizado de forma iterativa, eventualmente nos llevará a una solución del problema.
Los profesores Yang y Deb propusieron los siguientes tres conjuntos de estados ideales para el algoritmo:
1. Cada cuco pone un huevo y lo deja caer en un nido seleccionado aleatoriamente.
2. Los mejores nidos con huevos de alta calidad serán transmitidos a las siguientes generaciones.
3. El número de nidos disponibles es fijo y el nido podrá detectar un huevo extraño con probabilidad «pa». En este caso, el ave huésped puede tirar el huevo o abandonar el nido, y el huevo morirá.
Para simplificar, la tercera suposición puede aproximarse usando la fracción pa de n nidos. Para el problema de maximización, la calidad o el ajuste de la solución podrá ser simplemente proporcional a la función objetivo. No obstante, podremos definir otras expresiones (más complejas) para la función de aptitud.
Para cada iteración g, se seleccionará aleatoriamente un huevo de cuco i y se generarán nuevas soluciones xi (g + 1) usando el vuelo de Levy, una especie de paseo aleatorio en el que los pasos se determinarán dentro de los límites de las longitudes de paso que tengan una cierta distribución de probabilidad, además, las direcciones de los pasos serán isotrópicas y aleatorias. Según los creadores originales del método, la estrategia de uso de los vuelos de Levy resulta preferible a otros paseos aleatorios simples porque da como resultado un mejor rendimiento general. La ecuación general de vuelo de Levy tiene la forma siguiente
xi(g + 1) = xi(g) + α ⊕ levy(λ),
donde g indica el número de la generación actual, mientras que α > 0 indica el tamaño del paso, que deberá estar relacionado con la escala del problema particular analizado. El símbolo ⊕ se usa para denotar la multiplicación por elementos. Tenga en cuenta que esto supone esencialmente una cadena de Markov, ya que la siguiente ubicación en la generación g + 1 dependerá solo de la ubicación actual en la generación g y la probabilidad de transición dada por el primer y segundo término, respectivamente. Esta probabilidad de transición estará modulada por la distribución de Levy como:
levy(λ) ∼ g−λ, (1 < λ ≤ 3),
que tiene una varianza infinita con un valor medio infinito. La práctica ha demostrado que los mejores resultados se consiguen con un grado fijo de 2.0. Aquí, los pasos formarán esencialmente un proceso de paseo aleatorio con una distribución de longitud de paso con cola pesada de ley de potencia. Desde un punto de vista computacional, la generación de números aleatorios usando vuelos de Levy consta de dos etapas: primero, elegiremos una dirección aleatoria según una distribución uniforme, luego generaremos los pasos de acuerdo con la distribución de Levy elegida. Después, el algoritmo evaluará la idoneidad de la nueva solución y la comparará con la actual. Si la nueva solución ofrece una mejor idoneidad, reemplazaremos la actual. Por otro lado, algunos nidos serán abandonados (el dueño del nido ha tirado el huevo de cuco o ha dejado el nido y el huevo ha muerto) para aumentar la exploración del espacio de búsqueda en busca de soluciones más prometedoras. La tasa de reemplazo estará determinada por la probabilidad pa, un parámetro del modelo que deberá ajustarse para mejorar el rendimiento. El algoritmo se aplicará iterativamente hasta que se cumpla el criterio de parada. Los criterios comunes de finalización serán: que se haya encontrado una solución que cumpla con el umbral más bajo, que se haya alcanzado un número fijo de generaciones o que las iteraciones sucesivas ya no produzcan mejores resultados.
Veamos con más detalle el proceso de puesta de huevos por parte del cuco. De todos los nidos, se seleccionará al azar el nido donde se supone que se deberá poner el huevo. Como el huevo será una solución, podrá representarse mediante la calidad del huevo: si el huevo de cuco es de mayor calidad que el huevo original, entonces será reemplazado. De lo contrario, el huevo del progenitor se quedará en el nido. En esencia, la evolución posterior continuará partiendo del pollito superviviente, y esto significará que si el polluelo del huevo del progenitor ha sobrevivido, la evolución continuará desde el mismo lugar. Un mayor desarrollo solo resultará posible si el huevo de cuco resulta más viable, y la búsqueda para resolver el problema continuará desde un nuevo lugar. El árbol de decisión se muestra de forma esquemática en la figura 1.
Figura 1. Árbol de decisión. El punto rojo será el comienzo, mientras que el punto verde será la decisión final.
El segundo componente de la base del algoritmo después del árbol de decisión será el vuelo de Levy. El vuelo de Levy es un paseo aleatorio (un proceso estadístico de Markov) en el que la longitud del salto cambia de forma escalonada; la dirección de los saltos cambiará aleatoriamente, mientras que la distribución de la probabilidad será un caso especial de la distribución de Pareto y se caracterizará por las colas pesadas. Se definirá como un salto en el espacio, y el salto será isotrópico en direcciones aleatorias. El vuelo de Levy es una herramienta para describir procesos estocásticos anómalos. Así, la dispersión es infinita (son posibles saltos de gran longitud), y las longitudes de los saltos son autosimilares en todos los niveles (los saltos cortos se intercalan con vuelos largos). El término vuelo de Levy a veces se amplía para incluir un paseo aleatoria que ocurre en una cuadrícula discreta en lugar de en un espacio continuo.
Podemos imaginar una aplicación clara del vuelo de Levy en el algoritmo de cuco si consideramos el problema de la optimización con un parámetro. Tomemos, por ejemplo, una función hipotética (la línea negra en la figura 2) que no cambia en la mayor parte de su área de definición, es decir, en línea horizontal (y=x), y solo en un área pequeña, la función cambia y tiene un máximo. Si comenzamos la búsqueda del máximo desde el punto naranja en la figura 2, y luego obtenemos un valor aleatorio x con la distribución de Levy, nos alejaremos del punto de partida sin obtener un cambio en la función. No obstante, con un fuerte salto en la cola de la distribución, obtendremos un punto verde, que será mejor solución que el naranja original, y luego solo desde el punto verde podremos mejorar el resultado, aproximándonos al máximo de la función. En este ejemplo, el vuelo de Levy mejora drásticamente la capacidad de búsqueda del algoritmo.
Figura 2. Ejemplo de búsqueda de la solución de una hipotética función unidimensional usando el vuelo de Levy
El concepto de vuelo de Levy se usa en la teoría del caos al modelar fenómenos naturales aleatorios o pseudoaleatorios (por ejemplo, el vuelo de un albatros, combinando trayectorias largas y cortas). Los ejemplos incluyen análisis de datos de terremotos, matemáticas financieras, criptografía, análisis de señales, movimientos turbulentos y muchas aplicaciones en astronomía, biología y física.
Pseudocódigo del algoritmo COA (Figura 3):
1. Inicialización de los cucos con valores aleatorios.
2. Definición de la adaptabilidad.
3. Puesta de huevos en nidos aleatorios.
4. Vaciado del nido con una probabilidad dada
5. Envío de cucos desde la posición actual en una dirección aleatoria dentro de la distancia del vuelo de Levy
6. Definición de la adaptabilidad.
7. Puesta de huevos en nidos aleatorios.
8. Vaciado del nido con una probabilidad dada.
9. Repetición del paso 5 hasta que se cumpla el criterio de parada.
Figura 3. Esquema de bloques del algoritmo COA.
3. Análisis del código
Comenzaremos analizando el código del algoritmo. La solución al problema es el cuco, que es también el propio huevo. Se trata de una estructura simple que incluye las coordenadas en el espacio de búsqueda y el valor de la función de aptitud (calidad del huevo).
//—————————————————————————————————————————————————————————————————————————————— struct S_Cuckoo { double c []; //coordinates (egg parameters) double e; //egg quality }; //——————————————————————————————————————————————————————————————————————————————
El nido lo describiremos como una estructura. Aquí, al igual que en la estructura de un huevo, existen coordenadas en el espacio, además del valor de la función de aptitud. "Poner el huevo en el nido" significará esencialmente copiar la estructura del huevo en la estructura del nido. Al usar el parámetro probabilístico pa, el huevo será expulsado del nido cuando un número aleatorio de 0.0 a pa caiga en el rango [0.0;1.0] y el valor de e se establezca igual a -DBL_MAX.
//—————————————————————————————————————————————————————————————————————————————— struct S_Nest { void Init (int coordinates) { ArrayResize (c, coordinates); e = -DBL_MAX; } double c []; //coordinates (egg parameters) double e; //egg quality }; //——————————————————————————————————————————————————————————————————————————————
Clase del algoritmo. Aquí se declararán los métodos de inicialización públicos y los dos métodos principales de llamada en el programa de usuario, así como los rangos de valores de los argumentos del problema de optimización y los métodos privados adicionales que realizarán funciones de servicio.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_COA { //============================================================================ public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: S_Cuckoo cuckoos []; //all the cuckoos public: double cB []; //best coordinates (egg parameters) public: double eB; //best eggs quality public: void Init (const int coordinatesP, //number of opt. parameters const int cuckoosP, //number of cuckoos const int nestsP, //number of cuckoo nests const double koef_paP, //probability of detection of cuckoo eggs const double koef_alphaP); //step control value public: void CuckooFlight (); public: void LayEggs (); //============================================================================ private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double Min, double Max); private: double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool Revers); private: S_Nest nests []; //nests private: int cuckoosNumber; //number of cuckoos private: int nestsNumber; //number of cuckoo nests private: double koef_pa; //probability of detection of cuckoo eggs private: double koef_alpha; //step control value private: double v []; private: int coordinates; //coordinates number private: bool clutchEggs; //clutch of eggs }; //——————————————————————————————————————————————————————————————————————————————
El método público Init(). Aquí, los valores de las variables se restablecerán y se asignará memoria para los arrays.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_COA::Init (const int coordinatesP, //number of opt. parameters const int cuckoosP, //number of cuckoos const int nestsP, //number of cuckoo nests const double koef_paP, //probability of detection of cuckoo eggs const double koef_alphaP) //step control value { MathSrand (GetTickCount ()); clutchEggs = false; eB = -DBL_MAX; coordinates = coordinatesP; cuckoosNumber = cuckoosP; nestsNumber = nestsP; koef_pa = koef_paP; koef_alpha = koef_alphaP; ArrayResize (nests, nestsNumber); for (int i = 0; i < nestsNumber; i++) { nests [i].Init (coordinates); } ArrayResize (rangeMax, coordinates); ArrayResize (rangeMin, coordinates); ArrayResize (rangeStep, coordinates); ArrayResize (cB, coordinates); ArrayResize (v, coordinates); ArrayResize (cuckoos, cuckoosNumber); for (int i = 0; i < cuckoosNumber; i++) { ArrayResize (cuckoos [i].c, coordinates); } } //——————————————————————————————————————————————————————————————————————————————
El primer método público llamado en cada iteración del "vuelo de cuco". Si la bandera clutchEggs está desactivada, enviaremos los cucos en una dirección aleatoria, generando números aleatorios en el rango de la coordenada correspondiente. Si la bandera está activada, entonces el vuelo real del cuco se realizará según la distribución del vuelo de Levy en el rango del vector v. El vector v se calculará previamente en Init() para cada coordenada por separado, ya que cada coordenada podrá tener un rango de valores diferente.
La expresión cuckoos [i].c [c] = cuckoos [i].c [c] + r1 * v [c] * pow (r2, -2.0); significa que añadiremos el desplazamiento r1 * v [c] * pow (r2, -2.0) a la coordenada actual del cuco, donde r1 será el número -1 o 1, que determinará la dirección del desplazamiento desde la posición original, v será el vector de desplazamiento, y r2 será un número aleatorio en el rango de 0,0 a 20,0 elevado a la potencia de -2,0. Precisamente elevar un número aleatorio a una potencia es la función de vuelo de Levy, cuyo gráfico se puede ver en la figura 2.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_COA::CuckooFlight () { //---------------------------------------------------------------------------- if (!clutchEggs) { for (int i = 0; i < coordinates; i++) v [i] = (rangeMax [i] - rangeMin [i]) * koef_alpha; for (int i = 0; i < cuckoosNumber; i++) { for (int c = 0; c < coordinates; c++) { cuckoos [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); cuckoos [i].c [c] = SeInDiSp (cuckoos [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } clutchEggs = true; } else { double r1 = 0.0; double r2 = 0.0; for (int i = 0; i < cuckoosNumber; i++) { for (int c = 0; c < coordinates; c++) { r1 = RNDfromCI (0.0, 1.0); r1 = r1 > 0.5 ? 1.0 : -1.0; r2 = RNDfromCI (1.0, 20.0); cuckoos [i].c [c] = cuckoos [i].c [c] + r1 * v [c] * pow (r2, -2.0); cuckoos [i].c [c] = SeInDiSp (cuckoos [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
El segundo método público llamado en cada iteración será "la puesta de huevos". En este método, la simulación de la puesta de un huevo de cuco en un nido se reproducirá algorítmicamente. Esto sucederá eligiendo un nido al azar de todos los existentes. Después de ello, se comparará la calidad del huevo de cuco con la calidad del huevo que ya está en el nido. Si el huevo de cuco es mejor, se producirá el reemplazo. Una característica interesante del algoritmo en este método será la probabilidad de que el huevo muera después de la puesta, incluso si el huevo de cuco estaba más adaptado. Esto significará que existe una probabilidad koef_pa de que cualquier huevo, sea el que sea, muera, al igual que en la naturaleza. Si el huevo ha muerto o ha sido expulsado del nido, lo cual, en la práctica, es lo mismo, el nido quedará libre para una nueva puesta de un huevo de cualquier nivel de adaptación, incluso el más bajo, lo que algorítmicamente significará investigar en un nuevo lugar.
Entonces, en unas pocas líneas de código, podremos describir uno de los métodos de evolución natural, como es el parasitismo de nidos. Muchos autores en sus publicaciones recomiendan inicializar el nido después de eliminar el huevo con nuevos valores aleatorios, lo cual significará comenzar la búsqueda desde el principio. En la gran mayoría de los casos, esto no dará el resultado deseado en cuanto al aumento la capacidad exploratoria del algoritmo, nuestra propia investigación ha demostrado que resulta más conveniente simplemente dejar el nido vacío y uno de los cucos pondrá un huevo en él, independientemente de la calidad del huevo, es decir, podría ser cualquiera. Esto resultará mejor que simplemente usar valores aleatorios, y la variabilidad en el estudio se ofrecerá mediante saltos aleatorios en direcciones aleatorias desde las coordenadas actuales. Como resultado, se requerirán menos iteraciones en la búsqueda de la mejor solución, aumentando así la tasa de convergencia del algoritmo en su conjunto.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_COA::LayEggs () { int ind = 0; //^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ for (int i = 0; i < cuckoosNumber; i++) { ind = (int)round (RNDfromCI (0.0, nestsNumber - 1)); if (cuckoos [i].e > nests [ind].e) { nests [ind].e = cuckoos [i].e; ArrayCopy (nests [ind].c, cuckoos [i].c, 0, 0, WHOLE_ARRAY); if (cuckoos [i].e > eB) { eB = cuckoos [i].e; ArrayCopy (cB, cuckoos [i].c, 0, 0, WHOLE_ARRAY); } } else { ArrayCopy (cuckoos [i].c, nests [ind].c, 0, 0, WHOLE_ARRAY); } } //vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv for (int n = 0; n < nestsNumber; n++) { if (RNDfromCI (0.0, 1.0) < koef_pa) { nests [ind].e = -DBL_MAX; } } } //——————————————————————————————————————————————————————————————————————————————
4. Resultados de la prueba
Impresión de los resultados de la prueba:
2022.11.30 11:31:54.490 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:31:54.507 Test_AO_COA_fast (EURUSD,M1) 1 Skin's; Func runs 10000 result: 4.918379100238852
2022.11.30 11:31:54.507 Test_AO_COA_fast (EURUSD,M1) Score: 1.00000
2022.11.30 11:31:54.854 Test_AO_COA_fast (EURUSD,M1) 20 Skin's; Func runs 10000 result: 4.257477577760983
2022.11.30 11:31:54.854 Test_AO_COA_fast (EURUSD,M1) Score: 0.84220
2022.11.30 11:32:02.346 Test_AO_COA_fast (EURUSD,M1) 500 Skin's; Func runs 10000 result: 1.3521208312080903
2022.11.30 11:32:02.346 Test_AO_COA_fast (EURUSD,M1) Score: 0.14849
2022.11.30 11:32:02.346 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:32:02.368 Test_AO_COA_fast (EURUSD,M1) 1 Forest's; Func runs 10000 result: 1.7600394018343262
2022.11.30 11:32:02.368 Test_AO_COA_fast (EURUSD,M1) Score: 0.99557
2022.11.30 11:32:02.775 Test_AO_COA_fast (EURUSD,M1) 20 Forest's; Func runs 10000 result: 0.4968964923017033
2022.11.30 11:32:02.775 Test_AO_COA_fast (EURUSD,M1) Score: 0.28107
2022.11.30 11:32:13.125 Test_AO_COA_fast (EURUSD,M1) 500 Forest's; Func runs 10000 result: 0.07638950254648778
2022.11.30 11:32:13.125 Test_AO_COA_fast (EURUSD,M1) Score: 0.04321
2022.11.30 11:32:13.125 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:32:13.148 Test_AO_COA_fast (EURUSD,M1) 1 Megacity's; Func runs 10000 result: 12.0
2022.11.30 11:32:13.148 Test_AO_COA_fast (EURUSD,M1) Score: 1.00000
2022.11.30 11:32:13.584 Test_AO_COA_fast (EURUSD,M1) 20 Megacity's; Func runs 10000 result: 2.69
2022.11.30 11:32:13.584 Test_AO_COA_fast (EURUSD,M1) Score: 0.22417
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) 500 Megacity's; Func runs 10000 result: 0.40800000000000003
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) Score: 0.03400
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) =============================
2022.11.30 11:32:24.379 Test_AO_COA_fast (EURUSD,M1) All score for C_AO_COA: 0.507633670637353
El algoritmo de búsqueda de cuco con vuelo de Levy ha mostrado resultados impresionantes, en la mayoría de las pruebas ha superado a otros algoritmos de optimización. Así, el algoritmo ha mostrado una convergencia del 100% en la función Skin suave con dos variables y la función Megacity discreta con dos variables. Y lo que es aún más sorprendente, ha mostrado una excelente escalabilidad en una función discreta. En otras pruebas, resulta solo ligeramente inferior al algoritmo de colonia de hormigas. Por el momento, entre los algoritmos de optimización analizados, tenemos un líder indudable en la tabla de calificación.
Querríamos aclarar que todos los algoritmos tienen parámetros de ajuste que afectan a los resultados finales en un grado u otro, por lo que es muy posible que algunos de estos algoritmos tengan parámetros aún mejores y que la tabla de calificación se vea diferente. Acabamos de mostrar los resultados de las pruebas con los parámetros que hemos podido encontrar para asegurar el mejor resultado. Si el lector elige parámetros óptimos propios y obtiene mejores resultados, podremos corregir la tabla de calificación en función de estos resultados. Se supone que el algoritmo de la hormiga puede competir con éxito con el líder actual, ya que en algunos indicadores está por delante del algoritmo de búsqueda del cuco y se encuentra mínimamente por detrás en cuanto a los indicadores finales, mientras que en la función Skin con 1000 variables, el GWO sigue siendo el más fuerte. En cualquier caso, quienes usen algoritmos en sus proyectos al resolver sus problemas de optimización podrán navegar por la tabla y elegir un algoritmo para sus especificaciones.
COA en función de prueba Skin.
COA en la función de prueba Forest.
COA en la función de prueba Megacity.
En la visualización del banco de pruebas, el comportamiento del algoritmo se distingue de los analizados anteriormente, sin embargo, se notan algunas características propias de los algoritmos que dividen la tarea en áreas de estudio, como el algoritmo de colonia de abejas. Esto caracteriza la capacidad del algoritmo de no centrarse en un único extremo, sino de explorar varias áreas potencialmente prometedoras, ofreciendo al algoritmo resistencia contra el atascamiento en los extremos locales. En este sentido, se nos ocurrió que podría ser posible mejorar el algoritmo clasificando los nidos y eligiendo entre ellos según el cuco de acuerdo con su calidad. Esto significaría lo mismo que si el cuco eligiera los nidos, en lugar de poner un huevo en un nido seleccionado al azar, como en la versión canónica del algoritmo. No obstante, esto no ha mejorado los resultados y, en la práctica, muestra el significado de la elección aleatoria de los nidos. Quizás esto se identifique con lo que sucede en la naturaleza, es decir, el reemplazo de un huevo con huéspedes más inteligentes sería más difícil de lo que se justifica estadística y aleatoriamente.
Otra característica del algoritmo es que se comporta como un paseo aleatorio en funciones con muchas variables. Visualmente, parece ruido blanco o una pantalla de televisión vieja, y solo al final de las iteraciones, se percibe cierta concentración de coordenadas en los lugares de los extremos locales. Querríamos ofrecer una "cristalización" más clara de los parámetros, como sucede con el algoritmo de colonia de hormigas. Así, hemos llegado al problema general de todos los algoritmos de optimización: no tiene solución general. Muchos autores de algoritmos clásicos y bastante nuevos han tratado de resolverlo.
La esencia del problema es la siguiente: no sabemos con certeza cuál de los parámetros optimizados de la función analizada tiene prioridad o vigencia, ni tampoco sabemos en qué medida y cómo influye cada uno de los parámetros en el resultado. Por ejemplo, tenemos varios parámetros y el algoritmo ya ha encontrado el correcto, pero se desconoce cuál exactamente. El algoritmo seguirá intentando cambiarlos todos, aunque bastaría con cambiar solo unos pocos para llegar al extremo global. El problema se agudiza cuando se trata de una función con decenas y miles de variables: cuantas más variables, más acuciante será el problema. Visualmente, esto parece el ruido blanco en una pantalla.
Hemos intentado resolver este problema, si no de forma cardinal, al menos parcialmente. Si no sabemos a priori qué parámetros de la función analizada se deben cambiar y cuáles se deben mantener, podemos intentar resolver esto de forma probabilística. Es decir, asumiremos que solo deberemos cambiar una parte de todos los parámetros, y no todos al mismo tiempo. El algoritmo PSO se comporta de una forma característica, y, al aumentar el número de parámetros (argumentos) de la función optimizada, se comporta como una nube que no tiene capacidad de concentración. Para hacer esto, hemos introducido un nuevo parámetro para el algoritmo que establece la probabilidad de cambiar una coordenada, de lo contrario, la coordenada se mantendrá igual.
Finalmente... ¡¡¡Lo hemos logrado!!! Los resultados de las pruebas son ahora mejores. En funciones con muchas variables, se ha manifestado la misma "cristalización" que queríamos lograr.
Impresión del banco de pruebas:
2022.12.03 16:01:26.256 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:01:27.511 Test_AO_COAm (EURUSD,M1) 1 Skin's; Func runs 10000 result: 4.918367945334852
2022.12.03 16:01:27.511 Test_AO_COAm (EURUSD,M1) Score: 1.00000
2022.12.03 16:01:30.291 Test_AO_COAm (EURUSD,M1) 20 Skin's; Func runs 10000 result: 4.328327964103814
2022.12.03 16:01:30.291 Test_AO_COAm (EURUSD,M1) Score: 0.85911
2022.12.03 16:01:59.306 Test_AO_COAm (EURUSD,M1) 500 Skin's; Func runs 10000 result: 1.3297901702583084
2022.12.03 16:01:59.306 Test_AO_COAm (EURUSD,M1) Score: 0.14316
2022.12.03 16:01:59.306 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:02:00.511 Test_AO_COAm (EURUSD,M1) 1 Forest's; Func runs 10000 result: 1.755200932219688
2022.12.03 16:02:00.511 Test_AO_COAm (EURUSD,M1) Score: 0.99283
2022.12.03 16:02:03.566 Test_AO_COAm (EURUSD,M1) 20 Forest's; Func runs 10000 result: 0.5089243656052672
2022.12.03 16:02:03.566 Test_AO_COAm (EURUSD,M1) Score: 0.28787
2022.12.03 16:02:35.468 Test_AO_COAm (EURUSD,M1) 500 Forest's; Func runs 10000 result: 0.08044934398920801
2022.12.03 16:02:35.468 Test_AO_COAm (EURUSD,M1) Score: 0.04551
2022.12.03 16:02:35.468 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:02:36.628 Test_AO_COAm (EURUSD,M1) 1 Megacity's; Func runs 10000 result: 12.0
2022.12.03 16:02:36.628 Test_AO_COAm (EURUSD,M1) Score: 1.00000
2022.12.03 16:02:39.628 Test_AO_COAm (EURUSD,M1) 20 Megacity's; Func runs 10000 result: 2.9899999999999998
2022.12.03 16:02:39.628 Test_AO_COAm (EURUSD,M1) Score: 0.24917
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) 500 Megacity's; Func runs 10000 result: 0.4244
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) Score: 0.03537
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) =============================
2022.12.03 16:03:11.892 Test_AO_COAm (EURUSD,M1) All score for C_AO_COAm: 0.5125572342985216
Podemos ver claramente la "cristalización" en la visualización: la pantalla, que al principio parecía un ruido blanco, queda más limpia, y las coordenadas comienzan a concentrarse, los centros de concentración son móviles:
COAm en la función de prueba Megacity. El efecto de "cristalización" es más acusado.
Se manifiesta siempre por un lado: la variabilidad, es decir, la capacidad de buscar dinámicamente nuevas áreas, y, por otro lado, de aclarar las coordenadas de los extremos ya alcanzados. A modo de comparación, podemos ver la animación del algoritmo de colonia de hormigas con una "cristalización" pronunciada:
ACOm en la función de prueba Forest.
4. Resultados de la prueba
| AO | Description | Skin | Forest | Megacity (discrete) | Final result | ||||||
| 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | |||
| cuckoo optimization algorithm | 1,00000 | 0,85911 | 0,14316 | 0,99283 | 0,28787 | 0,04551 | 1,00000 | 0,24917 | 0,03537 | 0,51255778 | |
| ant colony optimization | 0,98229 | 0,79108 | 0,12602 | 1,00000 | 0,62077 | 0,11521 | 0,38333 | 0,44000 | 0,02377 | 0,49805222 | |
| artificial bee colony M | 1,00000 | 0,63922 | 0,08076 | 0,99908 | 0,20112 | 0,03785 | 1,00000 | 0,16333 | 0,02823 | 0,46106556 | |
| artificial bee colony | 0,99339 | 0,73381 | 0,11118 | 0,99934 | 0,21437 | 0,04215 | 0,85000 | 0,16833 | 0,03130 | 0,46043000 | |
| grey wolf optimizer | 0.99900 | 0,48033 | 0,18924 | 0,83844 | 0,08755 | 0,02555 | 1,00000 | 0,10000 | 0,02187 | 0,41577556 | |
| particle swarm optimisation | 0,99627 | 0,38080 | 0,05089 | 0,93772 | 0.14540 | 0,04856 | 1,00000 | 0,09333 | 0,02233 | 0,40836667 | |
| random | 0,99932 | 0,44276 | 0,06827 | 0,83126 | 0,11524 | 0,03048 | 0,83333 | 0,09000 | 0,02403 | 0,38163222 | |
Una ventaja del algoritmo de búsqueda de cuco es que su búsqueda global utiliza vuelos o el proceso de Levy en lugar de los paseos aleatorios estándar. Como los vuelos de Levy tienen una media y una varianza infinitas, el COA puede explorar el espacio de búsqueda de forma más eficiente que los algoritmos de procesos gaussianos estándar. El vuelo de Levy es un proceso de paseo aleatorio caracterizado por una serie de saltos instantáneos seleccionados de una función de densidad de probabilidad que tiene una cola de ley de potencia.
Por el momento, el algoritmo es el líder de la tabla, superando sustancialmente a otros algoritmos en pruebas individuales y no muy lejos en otras "disciplinas". Ha obtenido excelentes resultados en la función discreta Megacity con 1000 argumentos, lo que convierte a la búsqueda de cuco en una gran herramienta para las tareas de trading (tareas discretas en la mayoría de los casos). Los resultados excelentes, aunque no mejores, en la función Skin con 1000 argumentos ofrecen motivos para afirmar que el algoritmo resulta adecuado para entrenar redes neuronales en particular, y para aprendizaje automático en general.
Ventajas:
1. Es rápido.
2. Su versatilidad. Se puede usar en una amplia variedad de problemas de optimización.
3. La capacidad de no centrarse solo en los extremos locales.
4. Posee una alta convergencia para funciones suaves y discretas.
5. Escalamos.
Desventajas:
1. Muchos parámetros de ajuste.
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/11786
Recetas MQL5 - Servicios
DoEasy. Elementos de control (Parte 28): Estilos de barra en el control «ProgressBar»
DoEasy. Elementos de control (Parte 29): Control auxiliar "ScrollBar"
Algoritmos de optimización de la población: Optimización del Lobo Gris (Grey Wolf Optimizer - GWO)
- 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