Estratégia evolutiva de adaptação da matriz de covariância, Covariance Matrix Adaptation Evolution Strategy (CMA-ES)
273
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/en/articles/18227"; // Default parameters popSize = 50; // Default population size (lambda) mu = 25; // Number of parents (half of the population) learningRateC1 = 0.01; // Learning rate for rank-1 update learningRateCMu = 0.8; // Learning rate for rank-μ update stepSizeDamping = 0.6; // Damping for step size // Create and initialize the parameters array 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 [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step size const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ private: //--------------------------------------------------------- // CMA-ES specific parameters int mu; // Number of parents (selected points) double sigma; // Step size double learningRateC1; // Learning rate for rank-1 update double learningRateCMu; // Learning rate for rank-μ update double stepSizeDamping; // Damping factor for step size update // CMA-ES specific data structures double weights []; // Recombination weights double covMatrix []; // Covariance matrix (stored as a one-dimensional array) double B []; // C eigenvectors double D []; // C eigenvalues (square roots) double pc []; // Evolution path for C double ps []; // Evolution path for step-size control double mu_eff; // Effective selection mass int counteval; // Counter of function evaluations since the last decomposition int eigeneval; // Generation counter when decomposition was performed double chiN; // Expected norm N(0,I) int eigenInterval; // Interval for eigenvalue decomposition // Variables for performance optimization double cs; // Learning rate for the sigma path double cc; // Learning rate for rank-1 path double damps; // Damping for sigma double hsig_threshold; // Threshold for the Heaviside function // Auxiliary arrays double y_vec []; // Mutation vector double arindex []; // Array of indices for sorting double arfitness []; // Fitness array for sorting double temp_vec []; // Temporary vector for matrix operations double invsqrtC_times_yw []; // Temporary storage for C^(-1/2) * y_w // Caching variables for Box-Muller double cached_normal; bool has_cached; // Auxiliary methods 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 [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step size const int epochsP = 0) // number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Initialize Box-Muller caching has_cached = false; // Initialize CMA-ES specific variables sigma = 0.3; // Initial step size (30% of search range) // Calculate the effective mass of the variance selection ComputeWeights (); // Expected norm N(0,I) chiN = GetChiN (); // Calculate and save strategy parameters 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); // Set the eigenvalue decomposition interval - tuning for performance eigenInterval = (int)(coords / (10.0 * MathSqrt (learningRateC1 + learningRateCMu))); eigenInterval = MathMax (1, eigenInterval); // Allocate arrays only once 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); // Initialize evolution paths with zeros ArrayInitialize (pc, 0); ArrayInitialize (ps, 0); // Fast initialization of the identity covariance matrix and decomposition 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; } // Initialize initial distribution InitDistribution (); // Reset calculation counters counteval = 0; eigeneval = 0; // Forced fitness recalculation 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 () { // Generate new lambda descendants for (int k = 0; k < popSize; k++) { // Apply the transformation 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); } // Generate a descendant: 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]); } } // Fitness recalculation mark 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; // Sort the population by fitness SortPopulation (); // Update distribution parameters based on selected individuals UpdateDistribution (); // Update the calculation counter 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 random 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.
//+------------------------------------------------------------------+ //| Initialize search distribution | //+------------------------------------------------------------------+ void C_AO_CMAES::InitDistribution () { // Set the initial mean to the center of the search space 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++) { // Generate a uniformly distributed point 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.
//+------------------------------------------------------------------+ //| Calculate the expected norm 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 por ordem decrescente (a condição arfitness [j] < tempFitness no laço while), pois o objetivo é maximize 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.
//+------------------------------------------------------------------+ //| Sort the population by fitness | //+------------------------------------------------------------------+ void C_AO_CMAES::SortPopulation () { // Copy fitness values and indices 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; // Sort in descending order (for maximization) 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; } // Update the best solution if necessary 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".
//+------------------------------------------------------------------+ //| Update the mean using weighted recombination | //+------------------------------------------------------------------+ void C_AO_CMAES::UpdateMean () { // Weighted recombination: 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.
//+------------------------------------------------------------------+ //| Calculate weighted recombination weights | //+------------------------------------------------------------------+ void C_AO_CMAES::ComputeWeights () { // Allocate the array of weights ArrayResize (weights, mu); // Pre-calculate log(mu + 0.5) double log_mu_plus_half = MathLog (mu + 0.5); // Calculate positive weights double sum = 0.0; for (int i = 0; i < mu; i++) { weights [i] = log_mu_plus_half - MathLog (i + 1); sum += weights [i]; } // Normalize weights 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]; } // Calculate the effective mass of the variance selection 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.
//+------------------------------------------------------------------+ //| Update distribution parameters | //+------------------------------------------------------------------+ void C_AO_CMAES::UpdateDistribution () { // Check the necessity of eigenvalue decomposition if (counteval - eigeneval > eigenInterval) { ComputeEigendecomposition (); eigeneval = counteval; } // Preserve the old average double oldMean []; ArrayResize (oldMean, coords); ArrayCopy (oldMean, cB, 0, 0, coords); // Update average UpdateMean (); // Calculate the mean shift double y_w []; ArrayResize (y_w, coords); for (int j = 0; j < coords; j++) { y_w [j] = (cB [j] - oldMean [j]) / sigma; } // Calculate C^(-1/2) * y_w // Step 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]; } } // Step 2: D^(-1) * (B^T * y_w) for (int i = 0; i < coords; i++) { temp_vec [i] /= D [i]; } // Step 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]; } } // Update the evolution path for 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]; } // Heaviside function 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; // Update the evolution path for 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]; } // Prepare rank-1 update 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]; } } // Prepare rank-μ update double cmu []; ArrayResize (cmu, coords * coords); ArrayInitialize (cmu, 0.0); for (int k = 0; k < mu; k++) { int idx = (int)arindex [k]; // Calculate y_i = (x_i - m_old) / sigma for (int i = 0; i < coords; i++) { temp_vec [i] = (a [idx].c [i] - oldMean [i]) / sigma; } // Add the weighted outer product 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; } } } // Update C the covariance matrix double c1 = learningRateC1; double cmu_rate = learningRateCMu; // Adjust c1 if hsig is 'false' (progress stalled) if (!hsig) { c1 *= (1.0 - (1.0 - delta_hsig) * cc * (2.0 - cc)); } double one_minus_c1_cmu = 1.0 - c1 - cmu_rate; // Update C with rank-1 and rank-μ updates 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]; // Maintain symmetry if (i != j) { covMatrix [j * coords + i] = covMatrix [i * coords + j]; } } } // Ensure positive definiteness if (counteval % (10 * eigenInterval) == 0) { EnforcePositiveDefinite (); } // Update the sigma step size double exponent = (cs / damps) * (norm_ps / chiN - 1.0); sigma *= MathExp (exponent); // Limit sigma for numerical stability double min_sigma = 1e-16; double max_eigenvalue = D [0]; // D sorted in descending order 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.
//+------------------------------------------------------------------+ //| Calculate the eigenvalue decomposition using the Jacobi method | //+------------------------------------------------------------------+ void C_AO_CMAES::ComputeEigendecomposition () { // Create a copy of the covariance matrix for decomposition double C_copy []; ArrayResize (C_copy, coords * coords); ArrayCopy (C_copy, covMatrix); // Initialize B as the identity matrix for (int i = 0; i < coords; i++) { for (int j = 0; j < coords; j++) { B [i * coords + j] = (i == j) ? 1.0 : 0.0; } } // Improved Jacobi eigenvalue decomposition int max_iterations = 10; //50 * coords; double tolerance = 0.01; //1e-14 * coords * coords; for (int iter = 0; iter < max_iterations; iter++) { // Find the largest off-diagonal element 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; } } } // Check convergence if (max_val < tolerance) break; // Calculate the rotation angle 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); // Update the matrix elements 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; // Update other elements in p and q rows/columns 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; } } // Update eigenvectors 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; } } // Extract eigenvalues and ensure positivity double min_eigenvalue = 1e-14; for (int i = 0; i < coords; i++) { D [i] = MathSqrt (MathMax (min_eigenvalue, C_copy [i * coords + i])); } // Sort eigenvalues and vectors in descending order 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) { // Exchange eigenvalues double temp = D [i]; D [i] = D [max_idx]; D [max_idx] = temp; // Exchange eigenvectors 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".
//+------------------------------------------------------------------+ //| Check the positive definiteness of the covariance matrix | //+------------------------------------------------------------------+ bool C_AO_CMAES::CheckPositiveDefinite () { // Quick check: all diagonal elements should be positive for (int i = 0; i < coords; i++) { if (covMatrix [i * coords + i] <= 0) return false; } // Check if the minimum eigenvalue is positive double min_eigenvalue = D [coords - 1]; // D is sorted in descending order 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.
//+------------------------------------------------------------------+ //| Ensuring positive definiteness of the covariance matrix | //+------------------------------------------------------------------+ void C_AO_CMAES::EnforcePositiveDefinite () { // Method 1: Adding a small value to the diagonal double min_diag = 1e308; // A very large number 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; } } // Method 2: Ensuring symmetry 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 still not positive definite, perform the factorization and fix 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); } } // Reconstruct 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 optimization | 0.94629 | 0.66112 | 0.29853 | 1.90593 | 0.87906 | 0.58422 | 0.21146 | 1.67473 | 0.75846 | 0.42646 | 0.12686 | 1.31178 | 4.892 | 54.36 |
| 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