Optimización Extrema — Extremal Optimization (EO)
189
0
Contenido
Introducción
Muchos problemas del mundo real, en particular los relacionados con el trading, se caracterizan por paisajes discretos complejos de la función objetivo con múltiples extremos locales, discontinuidades y regiones no diferenciables, lo cual hace que los métodos clásicos de gradiente no sean aplicables. Se han desarrollado numerosos algoritmos metaheurísticos para resolver este tipo de problemas, y cada enfoque posee sus propias ventajas y desventajas en cuanto al equilibrio entre la exploración y la explotación del espacio de búsqueda.
La optimización extrema (Extremal Optimization, EO) es un algoritmo de optimización metaheurística inspirado en el modelo de Bak-Sneppen. El algoritmo fue desarrollado por Stefan Boettcher y Allon Percus en 1999 como un método inspirado en el concepto de criticidad autoorganizada, que evoluciona naturalmente hacia un estado crítico donde se producen cambios en cascada de diversas escalas. La versión poblacional de EO se desarrolló para resolver problemas de optimización continua mediante operaciones iterativas sobre una población.
Implementación del algoritmo
El modelo de Bak-Sneppen se desarrolló para describir la evolución de los ecosistemas y demostrar el fenómeno de la criticidad autoorganizada. Se trata de un modelo de coevolución simple que muestra cómo las interacciones locales pueden conducir a eventos críticos globales.
Principios del modelo Bak-Sneppen
Ecosistema de especies:
- Las especies N están dispuestas en una cadena (o en una red).
- A cada especie i se le asigna un valor de aptitud fi ∈ [0,1]
- Fitness representa la capacidad de una especie para adaptarse a su entorno.
Dinámica de la evolución
На каждом шаге времени: 1. Найти вид с минимальным fitness: fmin = min{fi} 2. Заменить fitness этого вида и его соседей новыми случайными значениями 3. Повторять процессCriticidad autoorganizada
- El sistema se autoorganiza hasta alcanzar un estado crítico.
- El valor umbral fc ≈ 0,67 aparece
- Las especies con aptitud < fc se extinguen como una avalancha.
- El tamaño de las avalanchas sigue una ley de potencias.
En largos periodos de estancamiento, en los que pocos cambios son seguidos por cambios repentinos, similares a una avalancha, de diversa magnitud y en ausencia de control externo, el sistema se autoorganiza. Los tamaños de las avalanchas siguen una ley de potencias: P(s) ~ s^(-τ), donde los tiempos de vida de las especies también siguen una ley de potencias en ausencia de una escala característica. Los cambios que se producen en una especie afectan a sus vecinas. Las dinámicas globales surgen de las interacciones locales.
Boettcher y Perkus adaptaron los principios del modelo de Bak-Sneppen para crear un algoritmo de optimización. En lugar de mejorar lo mejor, se mejora lo peor. Centrarse en los peores elementos puede parecer contraintuitivo, pero es eficaz para salir de los óptimos locales. En el modelo de Bak-Sneppen, la evolución se produce a través de un "equilibrio discontinuo": largos periodos de estasis interrumpidos por cambios repentinos. La EO usa este principio: cuando solo se modifican los componentes defectuosos, y cuando cambiar un componente mejora drásticamente la solución, mejorar un componente puede hacer que otros componentes se vuelvan "malos".
Así, la optimización extrema traslada los principios de criticidad autoorganizada de la física de los ecosistemas al campo de la optimización. La principal innovación consiste en aprovechar la tendencia natural de los sistemas complejos a autoorganizarse para equilibrar automáticamente la exploración y la explotación del espacio de búsqueda. Pondremos a prueba esta estrategia en aplicaciones prácticas. Pasemos ahora a escribir el pseudocódigo del algoritmo.
Inicialización:
- Creación de una población de agentes popSize
- Inicialización de parámetros
- Creación de arrays para clasificar agentes y componentes.
Primera ejecución (inicialización de la población):
- Para cada agente de la población:
- Para cada componente (coordenadas):
- se asigna un valor aleatorio dentro del rango aceptable
- se aplica la discretización si es necesario
- Para cada componente (coordenadas):
Ciclo de optimización principal:
Para cada agente de la población, se realiza:
- Clasificación de agentes:
- se crea una lista de todos los agentes con su aptitud
- los agentes se clasifican según su aptitud (los peores al inicio, para maximizar).
- Selección de un agente objetivo :
- se usa la distribución de ley de potencias P(n) ∝ n^(-τ)
- se elige un rango según esta distribución
- se define como objetivo al agente con el rango seleccionado
- Clasificación de los componentes del agente objetivo:
- Para cada componente, se calcula su aptitud:
- fitness = 1 - (desviación normalizada respecto al mejor valor conocido)
- Se clasifican los componentes por aptitud, los peores al principio)
- Para cada componente, se calcula su aptitud:
- Selección y mutación de componentes:
- se utiliza una distribución de ley de potencias para elegir el rango del componente
- se reemplaza el componente seleccionado con un nuevo valor aleatorio
- se verifican los límites y se aplica la discretización
Actualización de resultados:
- Se clasifica a toda la población por aptitud (los mejores al principio)
- Se actualiza la mejor solución global si se encuentra alguna mejora
Vamos a implementar el algoritmo en código. Para ello escribiremos una clase que represente la implementación del algoritmo EO, basado en el método de optimización que utiliza el principio de eliminar los peores elementos para encontrar soluciones. La clase hereda de la clase básica "C_AO" e incluye, además, parámetros y métodos específicos del algoritmo. Constructor y destructor: inicializan los parámetros y liberan los recursos, respectivamente. Parámetros principales:
- popSize — tamaño de la población, número de agentes en funcionamiento;
- tau — parámetro de la distribución de potencia que determina las probabilidades de seleccionar elementos;
- greedyStart — proporción de agentes con inicialización codiciosa;
- eliteUpdate — proporción de agentes que participan en la actualización por iteración.
- SetParams — recupera los valores de los parámetros actuales del array y los aplica;
- Init — inicialización de la población considerando los rangos de parámetros y el número de épocas;
- Moving — ejecución de un paso del algoritmo, actualizando el estado de la población;
- Revision — recálculo de las calificaciones o preparación para la siguiente etapa.
- RankedComponent — estructura para almacenar la clasificación de los componentes de los agentes según su calidad (Fitness);
- RankedAgent — estructura para almacenar la clasificación de los propios agentes según su nivel de aptitud final.
- compRanks y agentRanks — arrays de estructuras para almacenar los componentes y agentes clasificados;
- tau, greedyStart y eliteUpdate permiten controlar el comportamiento del algoritmo.
- ApplyExtremalOptimization — mecanismo subyacente para seleccionar y actualizar elementos según sus rangos, dada una distribución de ley de potencias.
- CalculateComponentFitness — calcula la aptitud de un componente de agente.
- SelectRankByPowerLaw — selecciona la clasificación de un componente o agente utilizando una distribución de ley de potencias, lo que permite centrarse en los elementos con peor rendimiento.
Esta clase está destinada a la aplicación del algoritmo de optimización extrema, especialmente en problemas que requieren la búsqueda de una solución de alta calidad mediante la eliminación sucesiva de los componentes menos adecuados de la población.
//———————————————————————————————————————————————————————————————————— //--- Инициализация bool C_AO_EO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ ArrayResize (compRanks, coords); ArrayResize (agentRanks, popSize); return true; } //————————————————————————————————————————————————————————————————————
El método de inicialización de la clase EO es responsable de preparar las condiciones iniciales para el funcionamiento posterior del algoritmo. Admite parámetros para los rangos de valores mínimos y máximos de las variables, así como tamaños de paso para modificarlos y el número de épocas (iteraciones) si fuera necesario.
El método primero llama al procedimiento de inicialización estándar, que ajusta los parámetros básicos y prepara las estructuras de datos comunes. Si este procedimiento falla, se interrumpe la inicialización del método.
Si la inicialización es exitosa, el método redimensiona los arrays utilizados para almacenar los componentes y agentes clasificados. El tamaño del conjunto de componentes se establece según el número de coordenadas o variables del problema, mientras que el conjunto de agentes se establece en función del tamaño de la población dada. Una vez completados estos pasos, el método retorna el resultado de una inicialización exitosa.
//———————————————————————————————————————————————————————————————————— //--- Основной цикл алгоритма void C_AO_EO::Moving () { // Начальная инициализация популяции if (!revision) { int greedyCount = (int)(popSize * greedyStart); for (int i = 0; i < popSize; i++) { // Случайная инициализация для остальных for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } // Применяем Extremal Optimization --------------------------------- ApplyExtremalOptimization (); } //————————————————————————————————————————————————————————————————————
El método "ApplyExtremalOptimization" implementa el ciclo principal del algoritmo EO para actualizar la población de agentes. Su objetivo es mejorar las soluciones modificando los componentes de los agentes basándose en los principios del EO. El número de agentes que se actualizan por iteración se determina considerando el parámetro "eliteUpdate" (la proporción de agentes actualizados) y el tamaño de la población. Los agentes se clasifican según su calidad general. El algoritmo clasifica a los agentes de peor a mejor para que funcione en busca de los máximos. Usando una distribución de probabilidad de ley de potencias, se selecciona el agente que estará sujeto a cambios.
Para el agente seleccionado, sus componentes se clasifican. A cada componente se le asigna un valor de aptitud "fitness" para evaluar su contribución a la calidad general del agente. Los componentes se clasifican de peor a mejor según su aptitud. Luego se utiliza una distribución de probabilidad de ley de potencias para seleccionar uno de los componentes del agente que se modificará. Esto se hace para aumentar la probabilidad de que se seleccionen los componentes con la peor clasificación.
El componente del agente seleccionado se reemplaza por un valor aleatorio dentro del rango permitido, que se especifica usando los parámetros "rangeMin" y "rangeMax". El valor resultante se comprueba para verificar su validez y asegurar que cumple con los límites y los tamaños de paso especificados.El método repite estos pasos para cada agente que se va a actualizar, implementando la lógica clave del algoritmo EO: seleccionar los componentes con el peor rendimiento y reemplazarlos de forma aleatoria para mejorar la calidad global de las soluciones.
//———————————————————————————————————————————————————————————————————— //--- Применение Extremal Optimization void C_AO_EO::ApplyExtremalOptimization () { // Количество агентов для обновления на этой итерации int numUpdates = MathMax (1, (int)(popSize * eliteUpdate)); // Обновляем выбранных агентов по принципу EO //for (int update = 0; update < numUpdates; update++) for (int update = 0; update < popSize; update++) { // Шаг 1: Выбираем агента для модификации // Используем ранжирование по общему fitness int targetAgent; // Ранжируем агентов по fitness (от худшего к лучшему для максимизации) for (int i = 0; i < popSize; i++) { agentRanks [i].idx = i; agentRanks [i].fitness = a [i].f; } // Сортировка (худшие в начале для максимизации) for (int i = 0; i < popSize - 1; i++) { for (int j = i + 1; j < popSize; j++) { if (agentRanks [i].fitness > agentRanks [j].fitness) { RankedAgent temp = agentRanks [i]; agentRanks [i] = agentRanks [j]; agentRanks [j] = temp; } } } // Выбираем агента согласно степенному распределению int rank = SelectRankByPowerLaw (popSize); targetAgent = agentRanks [rank].idx; // Шаг 2: Ранжируем компоненты выбранного агента for (int c = 0; c < coords; c++) { compRanks [c].agentIdx = targetAgent; compRanks [c].componentIdx = c; compRanks [c].fitness = CalculateComponentFitness (targetAgent, c); } // Сортировка компонентов (худшие в начале) for (int i = 0; i < coords - 1; i++) { for (int j = i + 1; j < coords; j++) { if (compRanks [i].fitness > compRanks [j].fitness) { RankedComponent temp = compRanks [i]; compRanks [i] = compRanks [j]; compRanks [j] = temp; } } } // Шаг 3: Выбираем компонент для изменения согласно P(n) ∝ n^(-τ) int compRank = SelectRankByPowerLaw (coords); int compIdx = compRanks [compRank].componentIdx; // Шаг 4: Заменяем выбранный компонент новым случайным значением // Это ключевой принцип EO - безусловная замена на случайное a [targetAgent].c [compIdx] = u.RNDfromCI (rangeMin [compIdx], rangeMax [compIdx]); // Проверка границ a [targetAgent].c [compIdx] = u.SeInDiSp (a [targetAgent].c [compIdx], rangeMin [compIdx], rangeMax [compIdx], rangeStep [compIdx]); } } //————————————————————————————————————————————————————————————————————
El método CalculateComponentFitness calcula el valor de aptitud para un único componente del agente. Esta función desempeña un papel importante en el algoritmo de Optimización Extrema (EO), ya que evalúa la contribución de cada componente a la calidad general de la solución. El algoritmo usa una métrica simple basada en el cálculo de la "aptitud" como la contribución relativa de un componente a la calidad general.
Inicialmente, "fitness" se inicializa a cero. Luego se calcula el rango de valores de los componentes (range). Si este rango es mayor que cero, se calcula la desviación normalizada. La desviación se calcula como el valor absoluto de la diferencia entre el valor del componente del agente y el valor básico "cB", normalizado por el rango de valores del componente. La aptitud se calcula restando la "desviation" de 1.0. Esto hace que "fitness" sea inversamente proporcional a la desviación: cuanto menor sea la desviación de un componente respecto al valor objetivo, mayor será su "fitness".
De este modo, la función retorna una puntuación de aptitud para un componente en particular, que indica qué tan bien coincide el valor actual del componente con el valor objetivo, lo cual es necesario para una posterior clasificación de los componentes.
//———————————————————————————————————————————————————————————————————— //--- Расчет fitness компонента double C_AO_EO::CalculateComponentFitness (int agentIdx, int componentIdx) { // Для общей задачи оптимизации используем простую метрику // λi = относительный вклад компонента в общее качество double fitness = 0.0; double range = rangeMax [componentIdx] - rangeMin [componentIdx]; if (range > 0) { // Нормализованное отклонение double deviation = MathAbs (a [agentIdx].c [componentIdx] - cB [componentIdx]) / range; fitness = 1.0 - deviation; // Инвертируем, чтобы больше = лучше } return fitness; } //————————————————————————————————————————————————————————————————————
El método "SelectRankByPowerLaw" implementa la selección de la posición (rank) de un elemento de una lista basándose en una distribución de probabilidad potencial. Este método es clave para el algoritmo EO, ya que precisamente a través de él se realiza la selección de agentes y componentes para su modificación. El método toma como entrada "maxRank", que define el rango máximo del elemento.
El método se basa en el principio de transformación inversa para obtener un valor aleatorio, siguiendo la ley de potencia P(n) ∝ n^(-τ), donde: n es el rango del elemento y τ (tau) es el parámetro que determina la forma de la distribución de potencia.
Dependiendo del valor del parámetro "tau", se dan dos escenarios:
-
Caso general (τ ≠ 1,0):
- Se calcula un factor de normalización, denominado "norm", que garantiza la correcta escala de las probabilidades;
- Luego se genera un número aleatorio "r" en el rango [0, 1) usando "u.RNDprobab()";
- La fórmula de la transformada inversa se usa para calcular el rango "rank" en función de "r", "norm" y "τ";
- El rango está limitado a [0, maxRank - 1] para evitar que el array se salga de los límites.
-
Caso especial (τ = 1,0):
- El factor de normalización "norm" se calcula para el caso τ = 1,0;
- Se usa una fórmula especial para calcular la clasificación;
- El rango está limitado dentro del rango [0, maxRank - 1].
Como resultado, el método retorna un número entero llamado "rank", que indica la posición seleccionada del elemento en la lista clasificada. Esta selección es probabilística, es decir, los elementos con menor rango (peores) tienen mayor probabilidad de ser seleccionados, según los principios del EO.
//———————————————————————————————————————————————————————————————————— //--- Выбор ранга согласно степенному распределению int C_AO_EO::SelectRankByPowerLaw (int maxRank) { // P(n) ∝ n^(-τ), где n - ранг от 1 до maxRank // Используем метод обратного преобразования double r = u.RNDprobab (); if (tau != 1.0) { // Общий случай: обратное преобразование для P(n) ∝ n^(-τ) double norm = (1.0 - MathPow (maxRank + 1.0, 1.0 - tau)) / (1.0 - tau); double x = r * norm; int rank = (int)MathPow ((1.0 - tau) * x + 1.0, 1.0 / (1.0 - tau)) - 1; if (rank >= maxRank) rank = maxRank - 1; if (rank < 0) rank = 0; return rank; } else { // Специальный случай τ = 1: P(n) ∝ 1/n double norm = MathLog (maxRank + 1.0); int rank = (int)(MathExp (r * norm) - 1.0); if (rank >= maxRank) rank = maxRank - 1; if (rank < 0) rank = 0; return rank; } } //————————————————————————————————————————————————————————————————————
El método "Revision" está diseñado para actualizar la información sobre las mejores soluciones encontradas durante el funcionamiento del algoritmo EO. Su tarea consiste en determinar la mejor solución actual y actualizar las variables globales que almacenan información sobre ella. Así, se crea una array temporal "aT" para almacenar los agentes clasificados. La población de agentes "a" se ordena usando la función integrada "u.Sorting". La clasificación se realiza para maximizar, es decir, los mejores agentes (aquellos con el valor más alto de la función de aptitud "f") se colocan al principio del array "a" (que es la estructura de datos principal) que contiene información sobre los agentes, incluidos los valores de sus componentes "c" y el valor de la función de aptitud "f".
Después de la clasificación, se comprueba si el valor de la función de aptitud "f" del mejor agente (es decir, a[0]) es mayor que el mejor valor actual "fB" (que almacena el valor de la función de aptitud de la mejor solución encontrada hasta el momento). Si el mejor agente actual es mejor que la mejor solución global, entonces los valores de los componentes del mejor agente (a[0].c) se copian en el array "cB", que probablemente almacena los componentes de la mejor solución, mientras que "fB" se actualiza al valor de la función de aptitud del mejor agente (a[0].f).
De este modo, la función "Revision" actualiza la información sobre la mejor solución, conservando sus componentes y el valor de la función de aptitud, y clasifica la población de manera que las mejores soluciones estén siempre disponibles al principio de la lista.
//———————————————————————————————————————————————————————————————————— //--- Обновление лучших решений void C_AO_EO::Revision () { // Сортировка популяции для МАКСИМИЗАЦИИ static S_AO_Agent aT []; ArrayResize (aT, popSize); // Используем встроенную функцию сортировки u.Sorting (a, aT, popSize); // Обновление глобального лучшего решения if (a [0].f > fB) { ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); fB = a [0].f; } } //————————————————————————————————————————————————————————————————————
Resultados de las pruebas
Tras realizar las pruebas, el algoritmo no ha arrojado buenos resultados, por lo que hemos decidido revisar todos los métodos originales y crear una versión modificada destinada a mejorar la convergencia del algoritmo.EO|Extremal Optimization (Boettcher-Percus)|50.0|1.4|0.5|0.3|
=============================
5 Hilly's; Func runs: 10000; result: 0.5146369337195529
25 Hilly's; Func runs: 10000; result: 0.29089804555433085
500 Hilly's; Func runs: 10000; result: 0.25192095557138877
=============================
5 Forest's; Func runs: 10000; result: 0.367128650332966
25 Forest's; Func runs: 10000; result: 0.19477408852361866
500 Forest's; Func runs: 10000; result: 0.15367465708144543
=============================
5 Megacity's; Func runs: 10000; result: 0.2584615384615384
25 Megacity's; Func runs: 10000; result: 0.12707692307692314
500 Megacity's; Func runs: 10000; result: 0.09413846153846227
=============================
All score: 2.25271 (25.03%)
A continuación le presentamos una interpretación propia de este método de optimización. Hemos implementado una nueva clase que hereda de la clase básica de optimización.
El constructor establece los parámetros iniciales del algoritmo: el tamaño de la población, el número de soluciones desfavorables a mejorar, la probabilidad de mutación y los grados de distribución para la selección y la mutación. Los parámetros se almacenan en un array de estructuras para su posterior modificación y personalización.
El método SetParams actualiza las variables internas de la clase según los valores del array de parámetros. Luego se declaran los métodos para la inicialización del algoritmo, la ejecución de los pasos de movimiento (actualizar el estado) y la revisión (para evaluar y corregir decisiones). La parte privada de la clase almacena variables que registran las épocas actual y total de la ejecución del algoritmo. Después se define un método para mutar un componente específico de una solución en una población, lo cual constituye una parte clave del algoritmo.
//———————————————————————————————————————————————————————————————————— class C_AO_EOm : public C_AO { public: //---------------------------------------------------------- ~C_AO_EOm () { } C_AO_EOm () { ao_name = "EOm"; ao_desc = "Extremal Optimization M"; ao_link = "https://www.mql5.com/ru/articles/18755"; popSize = 50; // Размер популяции popRaising = 3; // Повышение самых худших mutationRate = 0.1; // Вероятность мутации powCh = 2.0; // Степень закона распределения отбора powMut = 8.0; // Степень закона распределения мутации ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "popRaising"; params [1].val = popRaising; params [2].name = "mutationRate"; params [2].val = mutationRate; params [3].name = "powCh"; params [3].val = powCh; params [4].name = "powMut"; params [4].val = powMut; } void SetParams () { popSize = (int)params [0].val; popRaising = (int)params [1].val; mutationRate = params [2].val; powCh = params [3].val; powMut = params [4].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ int popRaising; // Повышение самых худших double mutationRate; // Вероятность мутации double powCh; // Степень закона распределения отбора double powMut; // Степень закона распределения мутации private: //--------------------------------------------------------- int currentEpoch; // текущая эпоха int totalEpochs; // общее количество эпох void MutateComponent (int agentIdx, int componentIdx); }; //————————————————————————————————————————————————————————————————————
El método "Init" es el responsable de inicializar el algoritmo. La función toma como entrada los arrays con valores mínimos y máximos, el paso para los parámetros de optimización y el número total de épocas (ciclos) de la operación del algoritmo.
Dentro del método, primero se llama a la función "StandardInit" de la clase básica "C_AO". Esta función realiza la inicialización general, la asignación de memoria o la configuración de parámetros básicos relacionados con rangos y pasos para los parámetros de optimización.
Si "StandardInit" falla, la función "Init" también finaliza, retornando "false". Si "StandardInit" se ejecuta correctamente, el método inicializa las variables "currentEpoch" (época actual) a "0" y "totalEpochs" (número total de épocas) al valor recibido en el parámetro "epochsP".
Al final, el método devuelve "true", lo que indica que la inicialización se ha realizado correctamente. De este modo, el método prepara el algoritmo para su funcionamiento estableciendo los parámetros iniciales y los contadores de época.
//———————————————————————————————————————————————————————————————————— //--- Инициализация bool C_AO_EOm::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ currentEpoch = 0; totalEpochs = epochsP; return true; } //————————————————————————————————————————————————————————————————————
El método "Moving" representa el ciclo principal del algoritmo de optimización extrema. Se encarga de la evolución de la población de soluciones en el proceso de búsqueda de la solución óptima. Incremento de época: el contador "currentEpoch" se incrementa. Inicialización de la población (solo en la primera época): si el indicador "revision" (que indica la necesidad de revisar las decisiones) es "false" (es decir, en el primer ciclo del algoritmo), se inicializa la población.
Para cada "agente" (solución) en la población, para cada "coordenada" (parámetro de solución), se genera un valor aleatorio en un rango dado (rangoMin, rangoMax) para la coordenada actual. La discretización "SeInDiSp" se usa para garantizar que los valores de los parámetros correspondan a los pasos especificados. Tras la inicialización, se establece "revision" en "true" para que este bloque de código se ejecute solo una vez. El método finaliza.
Aplicación de una optimización extrema (en épocas posteriores): se crea una array temporal "aT" para almacenar soluciones nuevas (modificadas). Para cada agente de la población, se inicializa la estructura "aT[i]". Para cada coordenada de la solución, se genera un número aleatorio y se eleva a la potencia "powCh". Esto se usa para seleccionar el "padre".
El número aleatorio se ajusta para seleccionar el índice padre en la población "ind". Luego se determina el tipo de mutación: si el número aleatorio es menor que "mutationRate" (la mutación se habilita con una probabilidad "mutationRate"), entonces la mutación se aplica de acuerdo con la ley de distribución de potencia "PowerDistribution" al valor de la coordenada padre. De lo contrario, se dará un "movimiento dirigido" hacia la mejor solución con la adición de ruido aleatorio. El nuevo valor se calcula como la suma del valor de la coordenada padre, un número aleatorio y la diferencia entre "cB[c]" (la mejor coordenada hallada) y la coordenada padre. Se usa la discretización "SeInDiSp". Tras la mutación, todas las coordenadas del array temporal "aT" se copian al array principal de la población "a".
De este modo, el método implementa un ciclo evolutivo, donde en cada paso (época) las soluciones mutan (cambian), usando los mecanismos de selección, mutación aleatoria y búsqueda dirigida, con el objetivo de mejorar sus valores (minimizando o maximizando la función objetivo) para finalmente encontrar la solución óptima.
//———————————————————————————————————————————————————————————————————— //--- Основной цикл алгоритма void C_AO_EOm::Moving () { currentEpoch++; // Начальная инициализация популяции if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //Apply Extremal Optimization--------------------------------------- static S_AO_Agent aT []; ArrayResize (aT, popSize); for (int i = 0; i < popSize; i++) { aT [i].Init (coords); for (int c = 0; c < coords; c++) { double rnd = u.RNDprobab (); rnd = pow (rnd, powCh); int ind = (int)u.Scale (rnd, 0.0, 1.0, 0, popSize - 1); // Выбор типа мутации double mutType = u.RNDprobab (); if (mutType < mutationRate) { aT [i].c [c] = u.PowerDistribution (a [ind].c [c], rangeMin [c], rangeMax [c], powMut); } else { // Направленное движение к лучшему с шумом aT [i].c [c] = a [ind].c [c] + u.RNDprobab () * (cB [c] - a [ind].c [c]); } // Проверка границ aT [i].c [c] = u.SeInDiSp (aT [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, aT [i].c); } //————————————————————————————————————————————————————————————————————
Este método se encarga de actualizar la información sobre las mejores soluciones durante el funcionamiento del algoritmo.
Clasificación de la población: se crea una array temporal "aT" para almacenar una copia de la población. La población "a" se clasifica según el valor de la función objetivo. El método "u.Sorting" se utiliza para clasificar.
Actualización de la mejor solución global: se comprueba si el valor de la función objetivo "f" del primer elemento de la población (es decir, la mejor solución) es mejor que el valor óptimo global actual "fB". Si la solución actual es mejor, entonces "cB" se copia desde las coordenadas del primer elemento de "a[0].c", y "fB" se actualiza con el valor de "f" de la mejor solución.
Actualización de la peor solución: "fW" se actualiza con el valor de la función del último elemento de la población.
"Elevación" (Raising) las peores soluciones: en un ciclo ejecutado "popRaising" veces, se produce la "elevación" de las peores soluciones en la población: para "popRaise" los peores agentes (ubicados al final del array ordenado "a"), el valor de la función objetivo "f" se recalcula como un valor aleatorio ubicado entre "fW" (el peor resultado actual) y "fB" (el mejor resultado actual). Esto se hace para introducir variedad o para corregir las peores decisiones y convertirlas en mejores.
Reordenamiento de la población: la población "a" se reordena utilizando el método "u.Sorting". Esto es necesario para restablecer el orden en la población después de los cambios en los valores f.
//———————————————————————————————————————————————————————————————————— //--- Обновление лучших решений void C_AO_EOm::Revision () { // Сортировка популяции -------------------------------------------- static S_AO_Agent aT []; ArrayResize (aT, popSize); u.Sorting (a, aT, popSize); // Обновление глобального лучшего решения if (a [0].f > fB) { ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); fB = a [0].f; } fW = a [popSize - 1].f; //------------------------------------------------------------------ for (int i = 0; i < popRaising; i++) { a [popSize - 1 - i].f = u.RNDfromCI (fW, fB); } u.Sorting (a, aT, popSize); } //————————————————————————————————————————————————————————————————————
Ahora bien, el algoritmo, que en cierto modo hereda las ideas del EO, pero modificadas, utiliza una distribución de ley de potencias para seleccionar donantes (no necesariamente malos).
a [popSize - 1 - i].f = u.RNDfromCI (fW, fB); Hemos añadido una característica que no se encuentra en las descripciones del EO: el algoritmo esencialmente "resucita" a los peores agentes, asignándoles una aptitud aleatoria en el rango que va desde el peor hasta el mejor de la población. La distribución de potencia para la mutación: interpretación de "mutación basada en la distribución de la ley de potencia". El movimiento dirigido hacia lo mejor (con mutType >= mutationRate): adición para acelerar la convergencia.
Ahora podemos analizar los resultados de la versión modificada. Podemos incluir dichos resultados en nuestra tabla de clasificación.
EOm|Extremal Optimization Mod|50.0|3.0|0.1|2.0|8.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7616651321732368
25 Hilly's; Func runs: 10000; result: 0.7724295992586084
500 Hilly's; Func runs: 10000; result: 0.3174703398632668
=============================
5 Forest's; Func runs: 10000; result: 0.9999936711143977
25 Forest's; Func runs: 10000; result: 0.7675163269928252
500 Forest's; Func runs: 10000; result: 0.23527203643380376
=============================
5 Megacity's; Func runs: 10000; result: 0.7476923076923077
25 Megacity's; Func runs: 10000; result: 0.5396923076923076
500 Megacity's; Func runs: 10000; result: 0.14249230769230903
=============================
All score: 5,28422 (58,71%)
La visualización muestra una gran dispersión de resultados para funciones de baja dimensionalidad (líneas verdes).
EOm en la función de prueba Hilly
EOm en la función de prueba Forest
EOm en la función de prueba Megacity
Tras las pruebas realizadas, el algoritmo EOm ocupa el puesto 12 en nuestra tabla de clasificació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 | 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 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | (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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | ABHA | 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 |
| 45 | 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 |
| 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
La implementación compacta y modificada de EOm presentada demuestra un ejemplo interesante en el campo de la optimización metaheurística: una desviación significativa de los principios teóricos puede conducir a mejores resultados prácticos. El algoritmo, que ha ocupado el puesto 12 entre 45 métodos basados en poblaciones, es en realidad un híbrido que conserva únicamente la idea clave de la distribución de ley de potencias del EO original.
El mecanismo de "resurrección" de los peores agentes evita la convergencia prematura, mantiene la diversidad de la población y crea oportunidades adicionales para la exploración. Simplificación del esquema computacional: la evaluación componente por componente, se reduce la complejidad computacional, y el trabajo directamente con las soluciones acelera la convergencia.
El éxito de la versión modificada del EO confirma un principio importante en el diseño de metaheurísticas: la efectividad de un algoritmo no está determinada por la fidelidad a la idea original, sino por el equilibrio entre la exploración y la explotación del espacio de búsqueda. La implementación presentada, a pesar de apartarse de los principios clásicos de la Optimización Extrema, demuestra una alta velocidad de convergencia, resultados competitivos y facilidad de implementación y configuración.
Esto la convierte en una herramienta útil en el arsenal de métodos de optimización de poblaciones, especialmente para problemas en los que resulta importante el equilibrio entre la calidad de la solución y el costo computacional.
Figura 1. Clasificación por colores de los algoritmos según las pruebas respectivas
Figura 2. Histograma de los resultados de las pruebas de algoritmos (en una escala de 0 a 100, cuanto más mejor, donde 100 es el máximo resultado teórico posible, el script para calcular la tabla de puntuación está en el archivo)
Ventajas y desventajas del algoritmo EOm:
Ventajas:
- Implementación sencilla
- Rápido y productivo
- Buenos resultados en problemas discretos
Desventajas:
- Gran dispersión de resultados para funciones de dimensionalidad pequeña.
- Resultados promedio en problemas "suaves" de pequeña dimensionalidad.
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_EOm.mq5 | Script | Banco de pruebas para EOm |
Traducción del ruso hecha por MetaQuotes Ltd.
Artículo original: https://www.mql5.com/ru/articles/18755
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.
Simulación de mercado: Position View (VIII)
Del básico al intermedio: Como burbujas de jabón
Introducción a MQL5 (Parte 19): Automatización de la detección de las ondas de Wolfe
Simulación de mercado: Position View (VII)
- 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