Estratégia evolutiva de adaptação da matriz de covariância, Covariance Matrix Adaptation Evolution Strategy (CMA-ES)
37
0
Conteúdo
Introdução
No mundo da otimização existem muitos algoritmos, porém buscamos os mais fortes para resolver as tarefas de otimização dos nossos robôs de trading. O CMA-ES (Covariance Matrix Adaptation Evolution Strategy) é um desses raros exemplos em que o rigor matemático se combina com a intuição biológica, criando um algoritmo que não apenas resolve problemas de otimização, mas aprende a compreender sua estrutura.
A história do CMA-ES começou no final da década de 1990, em laboratórios de pesquisa da Alemanha, onde Nikolaus Hansen e Andreas Ostermeier levantaram uma questão fundamental: seria possível criar um algoritmo de otimização que não apenas buscasse uma solução, mas se adaptasse à geometria do problema? Os algoritmos evolutivos tradicionais geravam descendentes em regiões esféricas ao redor dos indivíduos parentais, o que funcionava bem para funções simples, mas se mostrava ineficiente para problemas complexos e mal condicionados. Portanto, vamos analisar esse interessante algoritmo.
Implementação do algoritmo
Imagine a busca por um tesouro em uma ilha de formato irregular. A abordagem comum é procurar em todas as direções de maneira uniforme, como se a ilha fosse circular. O CMA-ES, por sua vez, estuda gradualmente o formato da ilha e passa a buscar predominantemente nas direções onde a probabilidade de encontrar o tesouro é maior. Além disso, ele memoriza rotas bem-sucedidas e utiliza essa memória para planejar buscas futuras.
Na base do CMA-ES está uma equação aparentemente simples: x_k ~ N(m, σ²C). Contudo, por trás dessa simplicidade existe uma profunda estrutura matemática. Cada símbolo aqui carrega uma informação importante sobre o estado da busca: m é a melhor estimativa atual da localização do ótimo, σ é a medida de quão longe estamos dispostos a arriscar afastar-nos do que já é conhecido, e C é a matriz de covariância, que codifica nosso entendimento da geometria da função. A única modificação justificada que introduziremos é substituir a distribuição normal por uma distribuição de potência, isto significa que a implementação seguirá a fórmula modificada: x_k ~ PowerDist(m, σ²C). Essa modificação altera o caráter da exploração do espaço, com "saltos" mais amplos, mas preserva a natureza adaptativa fundamental do algoritmo.
A matriz de covariância C é o verdadeiro coração do algoritmo Ela inicia sua existência como uma modesta matriz identidade, representando uma distribuição esférica. Porém, a cada iteração ela evolui, alongando-se nas direções de melhoria rápida e comprimindo-se onde o progresso é lento. Gradualmente, a esfera transforma-se em uma elipse e depois em um elipsoide alongado, perfeitamente orientado ao longo dos contornos da função que está sendo otimizada.
A principal inovação do CMA-ES — o conceito de caminhos evolutivos. Trata-se de uma espécie de memória genética do algoritmo, que se recorda não apenas de onde estavam os pontos bem-sucedidos, mas também de como o algoritmo chegou até eles. O caminho evolutivo acumula informações sobre passos consecutivos bem-sucedidos, criando um vetor direcionado que aponta para as regiões mais promissoras da busca. O segundo caminho evolutivo desempenha uma função mais sutil — ele controla o tamanho do passo. Se os passos consecutivos do algoritmo são correlacionados, isto é, cada passo seguinte continua a direção do anterior, o tamanho do passo aumenta — o algoritmo "sente" que está se movendo na direção correta. Se, por outro lado, os passos são aleatórios e não correlacionados, o tamanho do passo diminui — possivelmente o algoritmo já está próximo do ótimo e é necessário buscar com mais cautela.
Por trás da metáfora biológica da evolução no CMA-ES encontra-se um princípio matemático rigoroso — a maximização da verossimilhança. O algoritmo constantemente se pergunta: quais parâmetros da distribuição tornam os pontos bem-sucedidos observados os mais prováveis? Isso transforma a otimização evolutiva de uma heurística em um método estatisticamente fundamentado.
Cada atualização da matriz de covariância C consiste em dois componentes: rank-one atualização, baseada no caminho evolutivo, e rank-μ atualização, que utiliza informações de toda a população seleccionada. Rank-one atualização garante estabilidade e capacidade de captar tendências de longo prazo, enquanto rank-μ atualização permite adaptar-se rapidamente às novas informações da geração atual.
No contexto do CMA-ES é utilizada uma função de Heaviside modificada, que desempenha um papel importante no mecanismo de detecção de estagnação do algoritmo. A função compara o comprimento do caminho evolutivo com o comprimento esperado, se o caminho for muito curto — isso é um sinal de "andar em círculos". Condições de desativação (hsig = 0): o algoritmo "vaga" aleatoriamente e os passos se anulam mutuamente, nesse caso provavelmente o tamanho do passo é grande demais. Em situação de estagnação, reduz-se a influência da rank-one atualização e passa-se a confiar mais nas informações de toda a população. Condições de ativação (hsig = 1): o algoritmo progride em uma determinada direção, os passos consecutivos são correlacionados, então o tamanho do passo é adequado à situação atual.
Uma das propriedades mais profundas do CMA-ES é sua invariância às transformações do espaço de busca. O algoritmo resolve com a mesma eficiência a função f(x) e a função f(Ax + b), onde A é qualquer matriz não degenerada e b é qualquer vetor de deslocamento. Isso significa que o CMA-ES não depende da escolha do sistema de coordenadas. Essa invariância não é acidental — ela é consequência direta do uso do princípio da máxima verossimilhança e da adaptação da matriz de covariância. O algoritmo detecta automaticamente o sistema natural de coordenadas do problema, no qual os eixos coincidem com as direções principais de variação da função.
A beleza da teoria deve estar combinada com a aplicabilidade prática. O CMA-ES requer O(n²) de memória para armazenar a matriz de covariância e O(n³) de cálculos para sua própria decomposição, o que torna o algoritmo aplicável a tarefas com dimensionalidade de até algumas centenas de variáveis. Para dimensões maiores foram desenvolvidas modificações especializadas, sep-CMA-ES limita-se a matrizes de covariância diagonais, o VkD-CMA utiliza dimensionalidade variável e o LM-CMA aplica princípios de memória limitada, a implementação desses métodos por enquanto está fora do escopo do nosso artigo, possivelmente em artigos posteriores haverá a oportunidade de retornar a eles.
Figura 1. Na ilustração é mostrada a evolução ao longo das gerações,
três imagens do estado do algoritmo, gerações 1, 5 e 15, demonstrando como a população converge gradualmente para o ótimo,
Adaptação da matriz de covariância, as elipses azuis mostram como a forma da distribuição se altera quando a geração é: 1, circular, matriz identidade, 5, alongada e rotacionada, 15, ajustada com precisão à geometria local.
Componentes do algoritmo: pontos vermelhos, toda a população, λ descendentes, pontos verdes, as melhores soluções, μ pais, ponto preto m, média da população, círculos tracejados, isolinhas da função objetivo.
A fórmula-chave na parte inferior com a indicação da modificação para a distribuição de potência. A ilustração demonstra claramente como o algoritmo adapta sua estratégia de busca ao relevo da função otimizada, estreitando gradualmente a região de busca e aproximando-se do ótimo.
Passamos à escrita do pseudocódigo do algoritmo.
Inicialização
- Definir os parâmetros do algoritmo:
- Tamanho da população, lambda = 50
- Número de pais, mu = 25
- Taxa de aprendizado para atualização rank-1, c1 = 0.01
- Taxa de aprendizado para atualização rank-μ, cμ = 0.8
- Amortecimento do tamanho do passo = 0.6
- Tamanho inicial do passo, sigma = 0.3
- Calcular os pesos de recombinação:
- Para cada um dos μ pais calcular o peso como log(mu + 0.5) - log(i + 1)
- Normalizar os pesos de modo que sua soma seja igual a 1
- Calcular a massa efetiva de seleção μ_eff
- Inicializar os parâmetros da estratégia:
- Calcular as taxas de aprendizado para os caminhos evolutivos, cs, cc
- Definir a norma esperada da distribuição normal padrão, chiN
- Determinar o intervalo para a decomposição em autovalores
- Inicializar as estruturas de dados:
- Matriz de covariância C = matriz identidade
- Matriz de autovetores B = matriz identidade
- Vetor de autovalores D = vetor unitário
- Caminhos evolutivos pc e ps = vetores nulos
- Valor médio da população m = ponto aleatório no espaço de busca
- Criar a população inicial:
- Gerar lambda pontos aleatórios no espaço de busca
Ciclo principal da evolução
Repetir até que o critério de parada seja atingido:
Etapa 1: Geração de descendentes
- Para cada um dos lambda descendentes:
- Gerar um vetor aleatório z a partir da distribuição normal padrão
- Aplicar a transformação: y = B × D × z
- Criar o descendente: x_k = m + σ × y
- Aplicar as restrições do espaço de busca a x_k
Etapa 2: Avaliação e atualização
- Avaliar o fitness de todos os descendentes
- Ordenar a população:
- Organizar os descendentes em ordem decrescente de fitness
- Atualizar a melhor solução encontrada, se necessário
- Atualizar o valor médio da população:
- Salvar a média antiga m_old
- Calcular a nova média como soma ponderada dos μ melhores descendentes: m_new = Σ(w_i × x_i) para i de 1 até μ
- Atualizar os caminhos evolutivos:
- Calcular o deslocamento da média: y_w = (m_new - m_old) / σ
- Calcular C^(-1/2) × y_w por meio da decomposição em autovalores
- Atualizar o caminho evolutivo para o tamanho do passo: ps = (1 - cs) × ps + √(cs × (2 - cs) × μ_eff) × C^(-1/2) × y_w
- Verificar a condição de estagnação, função de Heaviside
- Atualizar o caminho evolutivo para a matriz de covariância: pc = (1 - cc) × pc + indicador_estagnação × √(cc × (2 - cc) × μ_eff) × y_w
- Atualizar a matriz de covariância:
- Preparar a atualização rank-1 a partir do produto externo de pc
- Preparar a atualização rank-μ a partir da soma ponderada dos desvios dos melhores descendentes
- Atualizar C: C = (1 - c1 - cμ) × C + c1 × (pc × pc^T) + cμ × Σ(w_i × y_i × y_i^T)
- Garantir a simetria da matriz
- Atualizar o tamanho do passo:
- Calcular o coeficiente de adaptação com base no comprimento do caminho ps
- Atualizar σ: σ = σ × exp((cs/damps) × (||ps||/chiN - 1))
- Limitar σ a valores razoáveis para estabilidade numérica
- Decomposição em autovalores, se necessário:
- Se tiverem passado iterações suficientes desde a última decomposição:
- Executar a decomposição C = B × D² × B^T pelo método de Jacobi
- Ordenar os autovalores e autovetores em ordem decrescente
- Garantir a definição positiva da matriz
- Se tiverem passado iterações suficientes desde a última decomposição:
- Verificação e correção da matriz de covariância:
- Verificar periodicamente a definição positiva de C
- Se necessário, adicionar um pequeno valor à diagonal
- Garantir a simetria da matriz
Agora vamos escrever a classe "C_AO_CMAES", derivada da classe "C_AO", que implementará o algoritmo de otimização CMA-ES.
Campos públicos, método:
- SetParams () - define os valores dos parâmetros do CMA-ES a partir do array "params".
- Init () - inicializa o algoritmo. Recebe os valores mínimos, máximos e o tamanho do passo para cada variável, assim como o número de épocas.
- Moving () - implementa o ciclo principal do algoritmo, responsável pela geração de novas soluções.
- Revision () - avaliação das novas soluções e atualização do estado do algoritmo.
Campos privados:
- Parâmetros do CMA-ES - variáveis, que contêm os parâmetros específicos do algoritmo CMA-ES: número de pais (mu), tamanho do passo (sigma), taxas de aprendizado (learningRateC1, learningRateCMu), fator de amortecimento (stepSizeDamping) e outros necessários para o funcionamento do algoritmo.
- Estruturas de dados do CMA-ES - arrays utilizados para armazenar os pesos de recombinação (weights), a matriz de covariância (covMatrix), autovetores (B), autovalores (D), caminhos evolutivos (pc, ps), assim como outros dados auxiliares. As variáveis "mu_eff", "counteval", "eigeneval", "chiN", "eigenInterval" são utilizadas para controle e gerenciamento do andamento do algoritmo.
- Variáveis para otimização de desempenho destinadas a acelerar os cálculos durante a execução do algoritmo, como as taxas de aprendizado e o amortecimento.
- Arrays auxiliares, utilizados como armazenamentos temporários para vetores e matrizes durante a execução de diferentes operações.
- Métodos auxiliares, executam etapas individuais do algoritmo CMA-ES, como a inicialização da distribuição, atualização da distribuição, cálculo da decomposição própria, ordenação da população, cálculo dos pesos, atualização do valor médio, verificação da definição positiva e garantia da definição positiva.
De modo geral, a classe "C_AO_CMAES" encapsula a lógica do algoritmo CMA-ES, fornecendo uma interface para inicialização, configuração de parâmetros e execução da otimização. Ela contém os parâmetros, arrays de dados e métodos necessários para a implementação do algoritmo. A separação entre campos públicos e privados garante o controle de acesso aos componentes internos da classe.
//———————————————————————————————————————————————————————————————————— class C_AO_CMAES : public C_AO { public: //---------------------------------------------------------- ~C_AO_CMAES () { } C_AO_CMAES () { ao_name = "CMAES"; ao_desc = "Covariance Matrix Adaptation Evolution Strategy"; ao_link = "https://www.mql5.com/ru/articles/18227"; // Параметры по умолчанию popSize = 50; // Размер популяции по умолчанию (lambda) mu = 25; // Количество родителей (половина популяции) learningRateC1 = 0.01; // Скорость обучения для ранг-1 обновления learningRateCMu = 0.8; // Скорость обучения для ранг-μ обновления stepSizeDamping = 0.6; // Демпфирование для размера шага // Создание и инициализация массива параметров ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "mu"; params [1].val = mu; params [2].name = "learningRateC1"; params [2].val = learningRateC1; params [3].name = "learningRateCMu"; params [3].val = learningRateCMu; params [4].name = "stepSizeDamping"; params [4].val = stepSizeDamping; } void SetParams () { popSize = (int)params [0].val; mu = (int)params [1].val; learningRateC1 = params [2].val; learningRateCMu = params [3].val; stepSizeDamping = params [4].val; } bool Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // размер шага const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ private: //--------------------------------------------------------- // Специфичные параметры CMA-ES int mu; // Количество родителей (выбранных точек) double sigma; // Размер шага double learningRateC1; // Скорость обучения для ранг-1 обновления double learningRateCMu; // Скорость обучения для ранг-μ обновления double stepSizeDamping; // Фактор демпфирования для обновления размера шага // Специфичные структуры данных CMA-ES double weights []; // Веса рекомбинации double covMatrix []; // Ковариационная матрица (хранится как одномерный массив) double B []; // Собственные векторы C double D []; // Собственные значения (квадратные корни) C double pc []; // Путь эволюции для C double ps []; // Сопряженный путь эволюции для sigma double mu_eff; // Эффективная масса выбора дисперсии int counteval; // Счетчик вычислений функции с последнего разложения int eigeneval; // Счетчик генераций, когда выполнялось разложение double chiN; // Ожидаемая норма N(0,I) int eigenInterval; // Интервал для разложения на собственные значения // Переменные для оптимизации производительности double cs; // Скорость обучения для пути sigma double cc; // Скорость обучения для пути ранг-1 double damps; // Демпфирование для sigma double hsig_threshold; // Порог для функции Хевисайда // Вспомогательные массивы double y_vec []; // Вектор мутации double arindex []; // Массив индексов для сортировки double arfitness []; // Массив фитнеса для сортировки double temp_vec []; // Временный вектор для матричных операций double invsqrtC_times_yw []; // Временное хранилище для C^(-1/2) * y_w // Переменные кэширования для Бокса-Мюллера double cached_normal; bool has_cached; // Вспомогательные методы void InitDistribution (); void UpdateDistribution (); void ComputeEigendecomposition (); double GetChiN (); void SortPopulation (); void ComputeWeights (); void UpdateMean (); bool CheckPositiveDefinite (); void EnforcePositiveDefinite (); }; //————————————————————————————————————————————————————————————————————
O método "Init" da classe "C_AO_CMAES" realiza a inicialização do algoritmo CMA-ES. Ele recebe como entrada os valores mínimos e máximos dos parâmetros, o tamanho do passo e o número de épocas. Primeiramente é chamado o método "StandardInit" para executar a inicialização padrão. O sinalizador "has_cached" é inicializado com "false" para indicar que não existe valor armazenado em cache para a geração de números aleatórios pelo método de Box-Muller. Em seguida, o tamanho do passo "sigma" é inicializado com o valor inicial igual a 0.3, 30% do intervalo de busca. É chamado o método "ComputeWeights" para calcular os pesos de recombinação e o método "GetChiN" para calcular a norma esperada de N(0, I).
São calculados os parâmetros "cs", "cc", "damps" e "hsig_threshold" com base em "mu_eff", massa efetiva, e no número de coordenadas, coords. Esses parâmetros são utilizados para adaptar a estratégia do CMA-ES durante a execução. É calculado e definido "eigenInterval", que determina a frequência de execução da decomposição em autovalores. Esse parâmetro é ajustado para otimizar o desempenho.
É alocada memória para os arrays específicos do CMA-ES, como a matriz de covariância "covMatrix", os autovetores "B", os autovalores "D", os caminhos evolutivos "pc" e "ps", os vetores temporários "y_vec", "arindex", "arfitness", "temp_vec" e "invsqrtC_times_yw". Os arrays são recriados apenas se for necessário alterar a dimensionalidade do problema.
Os arrays dos caminhos evolutivos "pc" e "ps" são inicializados com zeros, a matriz de covariância "covMatrix" e a matriz de autovetores "B" com a matriz identidade, e o array de autovalores "D" com uns. É chamado o método "InitDistribution" para inicializar a distribuição inicial. Em seguida, os contadores de avaliações da função "counteval" e "eigeneval" são zerados. O sinalizador "revision" é definido como "true" para indicar que é necessário recalcular os valores de fitness. Retorna-se "true" em caso de inicialização bem-sucedida.
Em conclusão, o método "Init" realiza toda a inicialização necessária para o funcionamento do algoritmo CMA-ES, incluindo a definição dos parâmetros, alocação de memória para os arrays e inicialização dos valores iniciais.
//———————————————————————————————————————————————————————————————————— bool C_AO_CMAES::Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // размер шага const int epochsP = 0) // количество эпох { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация кэширования Бокса-Мюллера has_cached = false; // Инициализация специфичных переменных CMA-ES sigma = 0.3; // Начальный размер шага (30% от диапазона поиска) // Вычисление эффективной массы выбора дисперсии ComputeWeights (); // Ожидаемая норма N(0,I) chiN = GetChiN (); // Вычисление и сохранение параметров стратегии cs = (mu_eff + 2.0) / (coords + mu_eff + 5.0); cc = (4.0 + mu_eff / coords) / (coords + 4.0 + 2.0 * mu_eff / coords); damps = 1.0 + 2.0 * MathMax (0.0, MathSqrt ((mu_eff - 1.0) / (coords + 1.0)) - 1.0) + cs; hsig_threshold = 1.4 + 2.0 / (coords + 1.0); // Установка интервала разложения на собственные значения - настройка для производительности eigenInterval = (int)(coords / (10.0 * MathSqrt (learningRateC1 + learningRateCMu))); eigenInterval = MathMax (1, eigenInterval); // Выделение массивов - выделяем только один раз ArrayResize (covMatrix, coords * coords); ArrayResize (B, coords * coords); ArrayResize (D, coords); ArrayResize (pc, coords); ArrayResize (ps, coords); ArrayResize (y_vec, coords); ArrayResize (arindex, popSize); ArrayResize (arfitness, popSize); ArrayResize (temp_vec, coords); ArrayResize (invsqrtC_times_yw, coords); // Инициализация путей эволюции нулями ArrayInitialize (pc, 0); ArrayInitialize (ps, 0); // Быстрая инициализация единичной ковариационной матрицы и разложения ArrayInitialize (covMatrix, 0.0); ArrayInitialize (B, 0.0); for (int i = 0; i < coords; i++) { covMatrix [i * coords + i] = 1.0; B [i * coords + i] = 1.0; D [i] = 1.0; } // Инициализация начального распределения InitDistribution (); // Сброс счетчиков вычислений counteval = 0; eigeneval = 0; // Принудительный пересчет фитнеса revision = true; return true; } //————————————————————————————————————————————————————————————————————
O método "Moving" na classe "C_AO_CMAES" é responsável pela geração de novos descendentes (soluções) na população. Transformação y = B * D * z: dentro do laço sobre a população há um laço aninhado que percorre todas as coordenadas, "coords", de cada indivíduo. Em cada coordenada "i" é calculado o valor "y_vec[i]". Isso é feito por meio de multiplicação matricial. Na prática, trata-se da multiplicação do vetor de números aleatórios "z" pela matriz "B * D", onde "B" são os autovetores da matriz de covariância, "D" são os autovalores da matriz de covariância, e "z" são números aleatórios gerados utilizando a função "u.PowerDistribution".
Geração do descendente: para cada coordenada "i" de cada descendente "k" é calculado o valor (a [k].c [i]). Isso é feito adicionando ao valor médio atual "cB [i]" (centro da distribuição atual) o vetor escalado "y_vec [i]". O escalonamento é realizado multiplicando "y_vec [i]" pelo tamanho do passo "sigma". Assim, a [k].c [i] = cB [i] + sigma * y_vec [i].
A função "u.SeInDiSp" garante que os valores das coordenadas dos descendentes permaneçam dentro dos limites permitidos definidos por "rangeMin [i]", "rangeMax [i]" e "rangeStep [i]". Ela pode truncar os valores, refletí-los nas fronteiras e quantizá-los para o valor de passo permitido mais próximo. Após a geração de todos os descendentes, o sinalizador "revision" é definido como "true", os valores da função de fitness (qualidade) para os descendentes gerados devem ser recalculados.
Em resumo, o método gera uma nova população de soluções com base na distribuição atual (média "cB" e matriz de covariância representada por "B" e "D") e no tamanho do passo "sigma". Ele utiliza números aleatórios para criar pequenas variações em torno da média atual, a fim de explorar o espaço de busca. A função "SeInDiSp" garante que as novas soluções permaneçam dentro dos limites permitidos, e o sinalizador "revision" assegura que a qualidade dessas soluções seja avaliada.
//———————————————————————————————————————————————————————————————————— void C_AO_CMAES::Moving () { // Генерация lambda новых потомков for (int k = 0; k < popSize; k++) { // Применение преобразования y = B*D*z for (int i = 0; i < coords; i++) { y_vec [i] = 0.0; for (int j = 0; j < coords; j++) { y_vec [i] += B [i * coords + j] * D [j] * u.PowerDistribution (0.0, -8, 8, 20); } // Генерация потомка: x_k = m + σ * y a [k].c [i] = cB [i] + sigma * y_vec [i]; a [k].c [i] = u.SeInDiSp (a [k].c [i], rangeMin [i], rangeMax [i], rangeStep [i]); } } // Отметка для пересчета фитнеса revision = true; } //————————————————————————————————————————————————————————————————————
O método "Revision" da classe "C_AO_CMAES" é responsável pela atualização dos parâmetros do algoritmo após a avaliação da função de fitness para a nova população. Inicialmente, o método verifica o valor do sinalizador "revision". Em seguida é chamado o método "SortPopulation ()", que ordena a população atual de modo que os melhores indivíduos sejam colocados no início. O método "UpdateDistribution ()" atualiza os parâmetros da distribuição do CMA-ES (valor médio "cB" do vetor de estratégia, matriz de covariância, tamanho do passo "sigma", caminhos evolutivos) com base nas informações dos melhores indivíduos da população. A atualização da distribuição é a etapa-chave do CMA-ES, pois permite que o algoritmo adapte sua estratégia de busca com base nos resultados obtidos.
Em síntese, o método "Revision" representa o ciclo principal de adaptação do CMA-ES. Ele ordena a população, atualiza os parâmetros da distribuição com base nos melhores indivíduos e incrementa o contador de avaliações.
//———————————————————————————————————————————————————————————————————— void C_AO_CMAES::Revision () { if (!revision) return; revision = false; // Сортировка популяции по фитнесу SortPopulation (); // Обновление параметров распределения на основе выбранных особей UpdateDistribution (); // Обновление счетчика вычислений counteval++; } //————————————————————————————————————————————————————————————————————
O método "InitDistribution" da classe "C_AO_CMAES" destina-se à inicialização da distribuição inicial de busca de soluções. O método define o valor médio inicial (cB) para cada coordenada no espaço de busca. Para cada coordenada "i", o valor "cB [i]" é definido aleatoriamente no intervalo entre "rangeMin [i]" e "rangeMax [i]" com o auxílio da função "u.RNDfromCI ()", o valor médio inicial é posicionado no centro do intervalo permitido para cada variável. O laço externo percorre toda a população (popSize indivíduos). Dentro desse laço há um laço interno que percorre todas as coordenadas (coords) de cada indivíduo. Para cada descendente, suas coordenadas são geradas. Inicialmente elas são selecionadas aleatoriamente dentro do intervalo especificado por "RNDfromCI", e em seguida são arredondadas para o passo de discretização utilizando "SeInDiSp".
A função "u.RNDfromCI" gera um número aleatório com distribuição uniforme dentro de um intervalo especificado. A função "u.SeInDiSp" garante que as coordenadas geradas para cada indivíduo estejam dentro dos limites permitidos definidos rangeMin [i], "rangeMax [i]" e rangeStep [i].
O método inicializa a população inicial случайными soluções distribuídas uniformemente no espaço de busca. O centro da distribuição (cB) também é escolhido aleatoriamente. Isso fornece o ponto de partida para as subsequentes iterações do CMA-ES, nas quais o algoritmo adaptará a estratégia de busca para encontrar a solução ótima.
//+------------------------------------------------------------------+ //| Инициализация распределения поиска | //+------------------------------------------------------------------+ void C_AO_CMAES::InitDistribution () { // Установка начального среднего в центр пространства поиска for (int i = 0; i < coords; i++) { cB [i] = u.RNDfromCI (rangeMin [i], rangeMax [i]); } for (int k = 0; k < popSize; k++) { for (int i = 0; i < coords; i++) { // Генерация равномерно распределенной точки a [k].c [i] = u.RNDfromCI (rangeMin [i], rangeMax [i]); a [k].c [i] = u.SeInDiSp (a [k].c [i], rangeMin [i], rangeMax [i], rangeStep [i]); } } } //————————————————————————————————————————————————————————————————————
Método "GetChiN" calcula o valor esperado da norma da distribuição normal padrão N (0,I) para um determinado número de coordenadas (coords). O resultado é aproximado com base na dimensionalidade do espaço de busca.
//+------------------------------------------------------------------+ //| Вычисление ожидаемой нормы N(0,I) | //+------------------------------------------------------------------+ double C_AO_CMAES::GetChiN () { double n = (double)coords; return MathSqrt (n) * (1.0 - 1.0 / (4.0 * n) + 1.0 / (21.0 * n * n)); } //————————————————————————————————————————————————————————————————————
Método "SortPopulation" destina-se a ordenar a população de soluções de acordo com os valores da função objetivo (fitness) a fim de determinar a melhor solução. Inicialmente, o método copia os valores de fitness de cada indivíduo da população para o array auxiliar "arfitness". Também é criado o array "arindex", que inicialmente contém os índices dos indivíduos. Isso é necessário para que, após a ordenação pelo fitness, seja possível restaurar a correspondência entre o fitness ordenado e o indivíduo original na população.
É utilizado o algoritmo de ordenação por inserção (insertion sort). Ele percorre o array "arfitness" e, para cada elemento, insere-o na posição correta da parte já ordenada do array, deslocando os elementos maiores para a direita. É importante observar que a ordenação é realizada по убыванию (a condição arfitness [j] < tempFitness no laço while), pois o objetivo é максимизировать a função objetivo (fitness). Juntamente com "arfitness", o array "arindex" é ordenado de forma sincronizada para acompanhar a posição dos índices originais dos indivíduos.
Após a ordenação, o método verifica se o fitness do melhor indivíduo é superior ao melhor valor atual e, em caso afirmativo, "fB" é atualizado e a melhor solução é substituída pelas coordenadas do melhor indivíduo da população. Dessa forma, o método não apenas ordena a população por fitness, mas também acompanha a melhor solução encontrada até o momento.
//+------------------------------------------------------------------+ //| Сортировка популяции по фитнесу | //+------------------------------------------------------------------+ void C_AO_CMAES::SortPopulation () { // Копирование значений фитнеса и индексов for (int i = 0; i < popSize; i++) { arindex [i] = i; arfitness [i] = a [i].f; } for (int i = 1; i < popSize; i++) { double tempFitness = arfitness [i]; double tempIndex = arindex [i]; int j = i - 1; // Сортировка по убыванию (для максимизации) while (j >= 0 && arfitness [j] < tempFitness) { arfitness [j + 1] = arfitness [j]; arindex [j + 1] = arindex [j]; j--; } arfitness [j + 1] = tempFitness; arindex [j + 1] = tempIndex; } // Обновление лучшего решения при необходимости if (arfitness [0] > fB) { fB = arfitness [0]; int bestIdx = (int)arindex [0]; ArrayCopy (cB, a [bestIdx].c, 0, 0, coords); } } //————————————————————————————————————————————————————————————————————
Método "UpdateMean" atualiza o valor médio da população (cB) por meio da recombinação ponderada dos melhores indivíduos. Para cada coordenada, a nova média é calculada como a soma ponderada dos valores das coordenadas dos melhores indivíduos, onde os pesos são definidos no array "weights".
//+------------------------------------------------------------------+ //| Обновление среднего с использованием взвешенной рекомбинации | //+------------------------------------------------------------------+ void C_AO_CMAES::UpdateMean () { // Взвешенная рекомбинация: m^(g+1) = Σ w_i * x_{i:λ}^(g+1) for (int j = 0; j < coords; j++) { double meanSum = 0.0; for (int i = 0; i < mu; i++) { int idx = (int)arindex [i]; meanSum += weights [i] * a [idx].c [j]; } cB [j] = meanSum; } } //————————————————————————————————————————————————————————————————————
O método "ComputeWeights" calcula os pesos para a recombinação ponderada, aloca o array "weights" com tamanho "mu", calcula log (mu + 0.5) para utilizá-lo na fórmula dos pesos. Para cada "i" de "0" até "mu-1" atribui o peso como a diferença entre log (mu + 0.5) e log (i+1); somando esses pesos, o método divide todos os pesos pela soma para que o total seja igual a 1, e calcula a soma dos quadrados dos pesos, determina "mu_eff", a eficiência do uso dos pesos, o que é importante para o ajuste da taxa e da dispersão no algoritmo.
Esse método garante pesos ótimos para a recombinação, levando em consideração a contribuição das melhores soluções.
//+------------------------------------------------------------------+ //| Вычисление весов взвешенной рекомбинации | //+------------------------------------------------------------------+ void C_AO_CMAES::ComputeWeights () { // Выделение массива весов ArrayResize (weights, mu); // Предварительное вычисление log(mu + 0.5) double log_mu_plus_half = MathLog (mu + 0.5); // Вычисление положительных весов double sum = 0.0; for (int i = 0; i < mu; i++) { weights [i] = log_mu_plus_half - MathLog (i + 1); sum += weights [i]; } // Нормализация весов double sum_weights = 0.0; double sum_squares = 0.0; for (int i = 0; i < mu; i++) { weights [i] /= sum; sum_weights += weights [i]; sum_squares += weights [i] * weights [i]; } // Вычисление эффективной массы выбора дисперсии mu_eff = sum_weights * sum_weights / sum_squares; } //————————————————————————————————————————————————————————————————————
O método "UpdateDistribution" atualiza os parâmetros da distribuição, especificamente a matriz de covariância (covMatrix) e o tamanho do passo (sigma) no algoritmo CMA-ES. Se tiverem passado gerações suficientes (counteval − eigeneval > eigenInterval), então é calculada a decomposição em autovalores, o valor médio atual "cB" é salvo no array temporário "oldMean". O método chama "UpdateMean" para calcular o novo valor médio, calcula a diferença entre a nova e a antiga média dividida por "sigma", e também realiza a multiplicação de "y_w" por C^(−1/2), dividida em várias etapas utilizando a decomposição "B" e "D", armazenando o resultado em "invsqrtC_times_yw".
Em seguida, o método atualiza o caminho evolutivo para o tamanho do passo "ps" utilizando "invsqrtC_times_yw", determina se o progresso deve ser considerado "estagnado" com base na norma de "ps" e no comprimento esperado, depois atualiza o caminho evolutivo para a matriz de covariância "pc" utilizando "y_w" e o indicador de progresso "hsig". Inicialmente o método calcula a matriz de atualização "rank-1", "c1a", depois a matriz de atualização "rank-μ", "cmu", com base na diferença entre os indivíduos e a média antiga, dividida por "sigma", utilizando os pesos "weights"; realiza a atualização da matriz de covariância "covMatrix" com o uso das atualizações "rank-1" e "rank-μ" e ajusta "c1" em caso de estagnação do progresso. Periodicamente é chamado "EnforcePositiveDefinite" para garantir a definição positiva da matriz de covariância. O tamanho do passo "sigma" é atualizado com base na norma de "ps" e limitado dentro de "min_sigma" e "max_sigma" para garantir estabilidade numérica.
De modo geral, "UpdateDistribution" ajusta os parâmetros da distribuição (matriz de covariância e tamanho do passo) com base no histórico da busca (caminhos evolutivos) e nos dados da população, para adaptar-se ao relevo da função objetivo.
//+------------------------------------------------------------------+ //| Обновление параметров распределения | //+------------------------------------------------------------------+ void C_AO_CMAES::UpdateDistribution () { // Проверка необходимости разложения на собственные значения if (counteval - eigeneval > eigenInterval) { ComputeEigendecomposition (); eigeneval = counteval; } // Сохранение старого среднего double oldMean []; ArrayResize (oldMean, coords); ArrayCopy (oldMean, cB, 0, 0, coords); // Обновление среднего UpdateMean (); // Вычисление смещения среднего double y_w []; ArrayResize (y_w, coords); for (int j = 0; j < coords; j++) { y_w [j] = (cB [j] - oldMean [j]) / sigma; } // Вычисление C^(-1/2) * y_w // Шаг 1: B^T * y_w ArrayInitialize (temp_vec, 0.0); for (int i = 0; i < coords; i++) { for (int j = 0; j < coords; j++) { temp_vec [i] += B [j * coords + i] * y_w [j]; } } // Шаг 2: D^(-1) * (B^T * y_w) for (int i = 0; i < coords; i++) { temp_vec [i] /= D [i]; } // Шаг 3: B * D^(-1) * B^T * y_w ArrayInitialize (invsqrtC_times_yw, 0.0); for (int i = 0; i < coords; i++) { for (int j = 0; j < coords; j++) { invsqrtC_times_yw [i] += B [i * coords + j] * temp_vec [j]; } } // Обновление пути эволюции для sigma double norm_ps_squared = 0.0; for (int i = 0; i < coords; i++) { ps [i] = (1.0 - cs) * ps [i] + MathSqrt (cs * (2.0 - cs) * mu_eff) * invsqrtC_times_yw [i]; norm_ps_squared += ps [i] * ps [i]; } // Функция Хевисайда double norm_ps = MathSqrt (norm_ps_squared); double expected_length = MathSqrt (1.0 - MathPow (1.0 - cs, 2.0 * counteval)) * chiN; bool hsig = norm_ps / expected_length < hsig_threshold; // Обновление пути эволюции для C double delta_hsig = hsig ? 1.0 : 0.0; for (int i = 0; i < coords; i++) { pc [i] = (1.0 - cc) * pc [i] + delta_hsig * MathSqrt (cc * (2.0 - cc) * mu_eff) * y_w [i]; } // Подготовка ранг-1 обновления double c1a []; ArrayResize (c1a, coords * coords); for (int i = 0; i < coords; i++) { for (int j = 0; j <= i; j++) { c1a [i * coords + j] = c1a [j * coords + i] = pc [i] * pc [j]; } } // Подготовка ранг-μ обновления double cmu []; ArrayResize (cmu, coords * coords); ArrayInitialize (cmu, 0.0); for (int k = 0; k < mu; k++) { int idx = (int)arindex [k]; // Вычисление y_i = (x_i - m_old) / sigma for (int i = 0; i < coords; i++) { temp_vec [i] = (a [idx].c [i] - oldMean [i]) / sigma; } // Добавление взвешенного внешнего произведения for (int i = 0; i < coords; i++) { for (int j = 0; j <= i; j++) { double update = weights [k] * temp_vec [i] * temp_vec [j]; cmu [i * coords + j] += update; if (i != j) cmu [j * coords + i] += update; } } } // Обновление ковариационной матрицы C double c1 = learningRateC1; double cmu_rate = learningRateCMu; // Корректировка c1 если hsig false (застой прогресса) if (!hsig) { c1 *= (1.0 - (1.0 - delta_hsig) * cc * (2.0 - cc)); } double one_minus_c1_cmu = 1.0 - c1 - cmu_rate; // Обновление C с ранг-1 и ранг-μ обновлениями for (int i = 0; i < coords; i++) { for (int j = 0; j <= i; j++) { covMatrix [i * coords + j] = one_minus_c1_cmu * covMatrix [i * coords + j] + c1 * c1a [i * coords + j] + cmu_rate * cmu [i * coords + j]; // Сохранение симметрии if (i != j) { covMatrix [j * coords + i] = covMatrix [i * coords + j]; } } } // Обеспечение положительной определенности if (counteval % (10 * eigenInterval) == 0) { EnforcePositiveDefinite (); } // Обновление размера шага sigma double exponent = (cs / damps) * (norm_ps / chiN - 1.0); sigma *= MathExp (exponent); // Ограничение sigma для численной стабильности double min_sigma = 1e-16; double max_eigenvalue = D [0]; // D отсортирован по убыванию double max_sigma = 1e4 * MathMax (1.0, MathSqrt (max_eigenvalue)); if (sigma < min_sigma) sigma = min_sigma; else if (sigma > max_sigma) sigma = max_sigma; } //————————————————————————————————————————————————————————————————————
O método "ComputeEigendecomposition" realiza a decomposição da matriz de covariância simétrica "covMatrix" em autovalores e autovetores por meio do método de Jacobi aprimorado; o método cria uma cópia de "covMatrix" para não modificar os dados originais. Inicialmente "B" é definida como matriz identidade, representando a base inicial. Executa um número máximo de iterações ou até que os elementos fora da diagonal se tornem menores que "tolerance".
Busca do maior elemento fora da diagonal: encontra o elemento com maior valor absoluto fora da diagonal para selecionar a rotação. Em seguida, se o valor máximo for menor que "tolerance", o laço é interrompido. O método calcula "phi" para realizar a rotação de Jacobi, modifica os elementos de "C_copy" aplicando a rotação, atualiza as colunas da matriz "B" (autovetores) de acordo com a rotação. Após as iterações, o método extrai a raiz quadrada dos elementos da diagonal (garantindo positividade mínima de 1e-14) e ordena em ordem decrescente os autovalores e os autovetores correspondentes para uso posterior. Assim, o método permite calcular com precisão os autovalores e autovetores da matriz de covariância.
//+------------------------------------------------------------------+ //| Вычисление разложения на собственные значения методом Якоби | //+------------------------------------------------------------------+ void C_AO_CMAES::ComputeEigendecomposition () { // Создание копии ковариационной матрицы для разложения double C_copy []; ArrayResize (C_copy, coords * coords); ArrayCopy (C_copy, covMatrix); // Инициализация B как единичной матрицы for (int i = 0; i < coords; i++) { for (int j = 0; j < coords; j++) { B [i * coords + j] = (i == j) ? 1.0 : 0.0; } } // Улучшенное разложение Якоби на собственные значения int max_iterations = 10; //50 * coords; double tolerance = 0.01; //1e-14 * coords * coords; for (int iter = 0; iter < max_iterations; iter++) { // Поиск наибольшего вне диагонального элемента double max_val = 0.0; int p = 0, q = 1; for (int i = 0; i < coords - 1; i++) { for (int j = i + 1; j < coords; j++) { double val = MathAbs (C_copy [i * coords + j]); if (val > max_val) { max_val = val; p = i; q = j; } } } // Проверка сходимости if (max_val < tolerance) break; // Вычисление угла поворота double app = C_copy [p * coords + p]; double aqq = C_copy [q * coords + q]; double apq = C_copy [p * coords + q]; double phi = 0.5 * MathArctan (2.0 * apq / (aqq - app + 1e-14)); double c = MathCos (phi); double s = MathSin (phi); // Обновление элементов матрицы double app_new = c * c * app - 2 * c * s * apq + s * s * aqq; double aqq_new = s * s * app + 2 * c * s * apq + c * c * aqq; C_copy [p * coords + p] = app_new; C_copy [q * coords + q] = aqq_new; C_copy [p * coords + q] = C_copy [q * coords + p] = 0.0; // Обновление других элементов в строках/столбцах p и q for (int i = 0; i < coords; i++) { if (i != p && i != q) { double aip = C_copy [i * coords + p]; double aiq = C_copy [i * coords + q]; C_copy [i * coords + p] = C_copy [p * coords + i] = c * aip - s * aiq; C_copy [i * coords + q] = C_copy [q * coords + i] = s * aip + c * aiq; } } // Обновление собственных векторов for (int i = 0; i < coords; i++) { double bip = B [i * coords + p]; double biq = B [i * coords + q]; B [i * coords + p] = c * bip - s * biq; B [i * coords + q] = s * bip + c * biq; } } // Извлечение собственных значений и обеспечение положительности double min_eigenvalue = 1e-14; for (int i = 0; i < coords; i++) { D [i] = MathSqrt (MathMax (min_eigenvalue, C_copy [i * coords + i])); } // Сортировка собственных значений и векторов по убыванию for (int i = 0; i < coords - 1; i++) { int max_idx = i; for (int j = i + 1; j < coords; j++) { if (D [j] > D [max_idx]) max_idx = j; } if (max_idx != i) { // Обмен собственных значений double temp = D [i]; D [i] = D [max_idx]; D [max_idx] = temp; // Обмен собственных векторов for (int k = 0; k < coords; k++) { temp = B [k * coords + i]; B [k * coords + i] = B [k * coords + max_idx]; B [k * coords + max_idx] = temp; } } } } //————————————————————————————————————————————————————————————————————
Método "CheckPositiveDefinite" verifica se a matriz de covariância é definida positiva. Ele realiza uma verificação rápida da positividade dos elementos da diagonal e compara o menor autovalor (do array "D", ordenado em ordem decrescente) com um pequeno número positivo 1e-14. Se ambas as verificações forem satisfeitas, o método retorna "true".
//+------------------------------------------------------------------+ //| Проверка положительной определенности ковариационной матрицы | //+------------------------------------------------------------------+ bool C_AO_CMAES::CheckPositiveDefinite () { // Быстрая проверка: все диагональные элементы должны быть положительными for (int i = 0; i < coords; i++) { if (covMatrix [i * coords + i] <= 0) return false; } // Проверка минимального собственного значения на положительность double min_eigenvalue = D [coords - 1]; // D отсортирован по убыванию return min_eigenvalue > 1e-14; } //————————————————————————————————————————————————————————————————————
Método "EnforcePositiveDefinite" garante a definição positiva da matriz de covariância "covMatrix". Ele executa várias etapas: encontra o menor elemento na diagonal e adiciona a quantidade necessária "correction" aos elementos da diagonal para que o menor seja igual a 1e-10, maximiza a simetria da matriz calculando a média de cada elemento fora da diagonal com o seu valor transposto.
Se a matriz ainda não for definida positiva, é realizada a decomposição em autovalores por meio de "ComputeEigendecomposition", todos os autovalores menores que √1e-10 são substituídos por √1e-10 para garantir positividade. Em seguida, o método recalcula "covMatrix" utilizando os autovetores "B" e os autovalores corrigidos "D", a fim de obter uma matriz ajustada e definida positiva. Essa abordagem garante que a matriz de covariância se torne definida positiva e adequada para os cálculos subsequentes no algoritmo CMA-ES.
//+------------------------------------------------------------------+ //| Обеспечение положительной определенности ковариационной матрицы | //+------------------------------------------------------------------+ void C_AO_CMAES::EnforcePositiveDefinite () { // Метод 1: Добавление малого значения к диагонали double min_diag = 1e308; // Очень большое число for (int i = 0; i < coords; i++) { if (covMatrix [i * coords + i] < min_diag) { min_diag = covMatrix [i * coords + i]; } } if (min_diag < 1e-10) { double correction = 1e-10 - min_diag; for (int i = 0; i < coords; i++) { covMatrix [i * coords + i] += correction; } } // Метод 2: Обеспечение симметрии for (int i = 0; i < coords; i++) { for (int j = i + 1; j < coords; j++) { double avg = (covMatrix [i * coords + j] + covMatrix [j * coords + i]) * 0.5; covMatrix [i * coords + j] = covMatrix [j * coords + i] = avg; } } // Если все еще не положительно определена, выполнить разложение и исправить if (!CheckPositiveDefinite ()) { ComputeEigendecomposition (); double min_eigenvalue = 1e-10; for (int i = 0; i < coords; i++) { if (D [i] < MathSqrt (min_eigenvalue)) { D [i] = MathSqrt (min_eigenvalue); } } // Восстановление C = B * D^2 * B^T ArrayInitialize (covMatrix, 0.0); for (int i = 0; i < coords; i++) { for (int j = 0; j <= i; j++) { double sum = 0.0; for (int k = 0; k < coords; k++) { sum += B [i * coords + k] * D [k] * D [k] * B [j * coords + k]; } covMatrix [i * coords + j] = covMatrix [j * coords + i] = sum; } } } } //————————————————————————————————————————————————————————————————————
Resultados dos testes
Agora, finalmente, podemos observar os resultados. O algoritmo, o que pode ser destacado de imediato, lida de forma excelente e rápida com tarefas de dimensionalidade média, sob determinadas configurações também com tarefas de baixa dimensionalidade, porém as tarefas mais difíceis e de alta dimensionalidade exigem um tempo de execução desproporcional aos recursos, por isso foram efetivamente excluídas dos resultados. A que isso se deve? Tradicionalmente, os cálculos matriciais em MQL5 representam um sério desafio computacional. Com a implementação manual das operações matriciais o algoritmo demonstra desempenho insatisfatório em tarefas de alta dimensionalidade, o que limita significativamente sua aplicabilidade prática. Contudo, com o surgimento das classes integradas para trabalho com matrizes, a situação muda radicalmente. Agora é criticamente importante utilizar a implementação nativa das operações matriciais da plataforma para todas as tarefas computacionalmente intensivas.
=============================
5 Hilly's; Func runs: 10000; result: 0.7625797883550075
25 Hilly's; Func runs: 10000; result: 0.7208874560706138
500 Hilly's; Func runs: 10000; result: 0.0
=============================
5 Forest's; Func runs: 10000; result: 0.8205636421348295
25 Forest's; Func runs: 10000; result: 0.7961602627346933
500 Forest's; Func runs: 10000; result: 0.0
=============================
5 Megacity's; Func runs: 10000; result: 0.7584615384615383
25 Megacity's; Func runs: 10000; result: 0.49076923076923074
500 Megacity's; Func runs: 10000; result: 0.0
=============================
All score: 4.34942 (48.33%)
Na visualização podemos notar que o algoritmo trabalha tanto com "grandes saltos" quanto se concentra nos extremos da função, explorando-os cuidadosamente.
CMA-ES na função de teste Hilly
CMA-ES na função de teste Forest
CMA-ES na função de teste Megacity
Ao final da execução, o algoritmo CMA-ES ocupa a 38ª posição no ranking dos algoritmos populacionais de otimização mais fortes.
№ | 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 ptimization 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 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | (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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | ADAMm | adaptive moment estimation M | 0,88635 | 0,44766 | 0,26613 | 1,60014 | 0,84497 | 0,38493 | 0,16889 | 1,39880 | 0,66154 | 0,27046 | 0,10594 | 1,03794 | 4,037 | 44,85 |
| 44 | CGO | chaos game optimization | 0,57256 | 0,37158 | 0,32018 | 1,26432 | 0,61176 | 0,61931 | 0,62161 | 1,85267 | 0,37538 | 0,21923 | 0,19028 | 0,78490 | 3,902 | 43,35 |
| 45 | CROm | coral reefs optimization M | 0,78512 | 0,46032 | 0,25958 | 1,50502 | 0,86688 | 0,35297 | 0,16267 | 1,38252 | 0,63231 | 0,26738 | 0,10734 | 1,00703 | 3,895 | 43,27 |
| 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 | |
Considerações finais
O CMA-ES é capaz de adaptar a estratégia de busca à geometria local da função objetivo, o que o torna praticamente indispensável para tarefas complexas, mal condicionadas e com estrutura desconhecida. As caudas pesadas da distribuição de potência permitem que o algoritmo realize "saltos longos", o que é criticamente importante para escapar de ótimos locais. A complexidade computacional O(n²) em memória e O(n³) em tempo limita rigidamente a aplicabilidade do algoritmo. Para tarefas de alta dimensionalidade (n > 100), o consumo de recursos torna-se desproporcional às vantagens obtidas. O tempo de execução em funções multidimensionais cresce tão rapidamente que torna o algoritmo praticamente inaplicável para grandes valores de n.
O CMA-ES funciona em funções com ruído, lida com funções objetivo descontínuas, é eficaz em paisagens com múltiplos extremos e o segredo dessa universalidade reside na filosofia fundamental do algoritmo: em vez de fazer suposições sobre a estrutura da função, ele a estuda cuidadosamente, adaptando sua estratégia de busca com base na experiência acumulada. O CMA-ES transforma o panorama da computação evolutiva, demonstrando que algoritmos inspirados biologicamente podem ter fundamentos matemáticos rigorosos e que a adaptação do algoritmo não é apenas ajuste de parâmetros, mas um princípio fundamental de aprendizado da estrutura do problema.
O algoritmo é excelente para tarefas de dimensionalidade média, é uma ferramenta especializada que se apresenta como uma alternativa digna em seu nicho. O algoritmo combina elegância matemática com eficiência prática, mas exige aplicação consciente levando em conta suas limitações computacionais. Em casos como esse, para o cálculo de matrizes, os desenvolvedores da linguagem MQL5 recentemente introduziram operações matriciais rápidas no MQL5, nesta implementação do algoritmo foram utilizados cálculos sequenciais convencionais.
Figura 2. Graduação de cores dos algoritmos nos testes correspondentes
Figura 3. Histograma dos resultados dos testes dos algoritmos (na escala de 0 a 100, quanto maior, melhor, onde 100 é o resultado teórico máximo possível; no arquivo há um script para calcular a tabela de classificação)
Vantagens e desvantagens do algoritmo CMAES:
Vantagens:
- Boa convergência em funções de dimensionalidade média.
Desvantagens:
- Grande variação de resultados em funções de baixa dimensionalidade.
- Elevado consumo de recursos em funções de alta dimensionalidade.
Um arquivo compactado com as versões atualizadas dos códigos dos algoritmos está anexado ao artigo. O autor do artigo não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, pois muitos deles foram modificados para melhorar as capacidades de busca. As conclusões e julgamentos apresentados nos artigos baseiam-se nos resultados dos experimentos realizados.
Programas utilizados no artigo
| # | Nome | Tipo | Descrição |
|---|---|---|---|
| 1 | #C_AO.mqh | Arquivo de inclusão | Classe base dos algoritmos populacionais de otimização |
| 2 | #C_AO_enum.mqh | Arquivo de inclusão | Enumeração dos algoritmos populacionais de otimização |
| 3 | TestFunctions.mqh | Arquivo de inclusão | Biblioteca de funções de teste |
| 4 | TestStandFunctions.mqh | Arquivo de inclusão | Biblioteca de funções do ambiente de testes |
| 5 | Utilities.mqh | Arquivo de inclusão | Biblioteca de funções auxiliares |
| 6 | CalculationTestResults.mqh | Arquivo de inclusão | Script para cálculo dos resultados na tabela comparativa |
| 7 | Testing AOs.mq5 | Script | Ambiente de testes unificado para todos os algoritmos populacionais de otimização |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Exemplo simples de uso de algoritmos populacionais de otimização sem visualização |
| 9 | Test_AO_CMAES.mq5 | Script | Ambiente de testes para CMAES |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/18227
Aviso: Todos os direitos sobre esses materiais pertencem à MetaQuotes Ltd. É proibida a reimpressão total ou parcial.
Esse artigo foi escrito por um usuário do site e reflete seu ponto de vista pessoal. A MetaQuotes Ltd. não se responsabiliza pela precisão das informações apresentadas nem pelas possíveis consequências decorrentes do uso das soluções, estratégias ou recomendações descritas.
Construindo um Indicador Keltner Channel com Gráficos Canvas Personalizados em MQL5
Redes neurais em trading: Pipeline inteligente de previsões (Mistura esparsa de especialistas)
Criando um Painel Administrador de Trading em MQL5 (Parte IX): Organização de Código (II): Modularização
Introdução à diversificação (en. diversification) de estruturas fractais de mercado com o auxílio de machine learning
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Você concorda com a política do site e com os termos de uso