Otimização extrema — Extremal Optimization (EO)
53
0
Conteúdo
Introdução
Muitos problemas reais, em particular os de trading, são caracterizados por paisagens discretas complexas da função objetivo, com múltiplos extremos locais, descontinuidades e regiões não diferenciáveis, o que torna os métodos clássicos baseados em gradiente inaplicáveis. Para resolver esse tipo de problema, foi desenvolvido um grande número de algoritmos metaheurísticos, e cada abordagem tem suas próprias vantagens e desvantagens no equilíbrio entre exploração (exploration) e aproveitamento (exploitation) do espaço de busca.
Extremal Optimization (EO) é um algoritmo metaheurístico de otimização inspirado no modelo de Bak-Sneppen. O algoritmo foi desenvolvido por Stefan Boettcher e Allon Percus em 1999 como um método inspirado no conceito de criticidade auto-organizada, em que os sistemas evoluem naturalmente para um estado crítico, no qual ocorrem mudanças em avalanche de diferentes escalas. O Population-based EO foi desenvolvido para resolver problemas de otimização contínua, utilizando operações iterativas sobre a população.
Implementação do algoritmo
O modelo de Bak-Sneppen foi desenvolvido para descrever a evolução dos ecossistemas e demonstrar o fenômeno da criticidade auto-organizada. Trata-se de um modelo simples de coevolução que mostra como interações locais podem levar a fenômenos críticos globais.
Princípios do modelo de Bak-Sneppen
Ecossistema de espécies:
- N espécies estão dispostas em uma cadeia (ou em uma grade)
- A cada espécie i é atribuído um valor de fitness fi ∈ [0,1]
- O fitness representa a adaptação da espécie ao ambiente
Dinâmica da evolução
A cada passo de tempo: 1. Encontrar a espécie com o menor fitness: fmin = min{fi} 2. Substituir o fitness dessa espécie e de seus vizinhos por novos valores aleatórios 3. Repetir o processo
Criticidade auto-organizada
- O sistema se auto-organiza até um estado crítico
- Surge um valor limiar fc ≈ 0.67
- Espécies com fitness < fc entram em extinção em avalanche
- Os tamanhos das avalanches obedecem a uma lei de potência
Longos períodos de estagnação, em que ocorrem poucas mudanças, são substituídos por mudanças abruptas em avalanche de diferentes escalas na ausência de controle externo, ou seja, o sistema se auto-organiza. Os tamanhos das avalanches obedecem a uma lei de potência: P(s) ~ s^(-τ), enquanto os tempos de vida das espécies também seguem uma lei de potência, sem uma escala característica. A alteração de uma espécie afeta as vizinhas. A dinâmica global surge a partir de interações locais.
Boettcher e Percus adaptaram os princípios do modelo de Bak-Sneppen para criar um algoritmo de otimização. Em vez de melhorar os melhores, melhoramos os piores. O foco nos piores elementos contraria a intuição, mas é eficaz para sair de ótimos locais. No modelo de Bak-Sneppen, a evolução ocorre por meio de "equilíbrio pontuado" — longos períodos de estase são interrompidos por mudanças repentinas. O EO utiliza esse princípio: quando apenas os componentes ruins são modificados e quando a mudança de um componente melhora drasticamente a solução, a melhoria de um componente pode fazer com que outros componentes se tornem "ruins".
O Extremal Optimization transfere os princípios da criticidade auto-organizada da física dos ecossistemas para a área de otimização. A principal inovação é o uso da tendência natural de sistemas complexos à auto-organização para equilibrar automaticamente a exploração e o aproveitamento do espaço de busca, se isso é realmente assim, vamos verificar em tarefas práticas. Vamos à escrita do pseudocódigo do algoritmo.
Inicialização:
- Criar uma população de popSize agentes
- Inicializar os parâmetros
- Criar arrays para o ranqueamento dos agentes e dos componentes
Primeira execução (inicialização da população):
- Para cada agente da população:
- Para cada componente (coordenada):
- atribuir um valor aleatório dentro do intervalo permitido
- aplicar discretização, se necessário
- Para cada componente (coordenada):
Ciclo principal de otimização:
Para cada agente da população executar:
- Ranqueamento dos agentes:
- criar uma lista de todos os agentes com seus fitness
- ordenar os agentes por fitness (os piores no início, para maximização)
- Seleção do agente-alvo:
- usar a distribuição em lei de potência P(n) ∝ n^(-τ)
- selecionar a posição de acordo com essa distribuição
- definir como agente-alvo o agente com a posição selecionada
- Ranqueamento dos componentes do agente-alvo:
- Para cada componente, calcular seu fitness:
- fitness = 1 - (desvio normalizado em relação ao melhor valor conhecido)
- ordenar os componentes por fitness (os piores no início)
- Para cada componente, calcular seu fitness:
- Seleção e mutação do componente:
- usar a distribuição em lei de potência para selecionar a posição do componente
- substituir o componente selecionado por um novo valor aleatório
- verificar os limites e aplicar discretização
Atualização dos resultados:
- Ordenar toda a população por fitness (os melhores no início)
- Atualizar a melhor solução global caso seja encontrada uma melhoria
Vamos implementar o algoritmo em código. Escreveremos uma classe que representará a implementação do algoritmo EO, baseada no método de otimização que utiliza o princípio da remoção dos piores elementos para a busca de soluções. A classe herda da classe base "C_AO" e inclui adicionalmente parâmetros e métodos específicos do algoritmo. Construtor e destrutor: respectivamente, inicializam os parâmetros e liberam os recursos. Parâmetros principais:
- popSize — tamanho da população, quantidade de agentes em operação;
- tau — parâmetro da distribuição em lei de potência que determina as probabilidades de seleção dos elementos;
- greedyStart — fração de agentes com inicialização gulosa;
- eliteUpdate — fração de agentes que participam da atualização a cada iteração.
- SetParams — extrai os valores atuais dos parâmetros do array e os aplica;
- Init — inicialização da população levando em conta os intervalos dos parâmetros e o número de épocas;
- Moving — execução de um passo do algoritmo, com atualização do estado da população;
- Revision — recálculo das avaliações ou preparação para a próxima etapa.
- RankedComponent — estrutura para armazenar o ranqueamento dos componentes do agente de acordo com sua qualidade (Fitness);
- RankedAgent — estrutura para armazenar o ranqueamento dos próprios agentes de acordo com seu nível final de aptidão.
- compRanks e agentRanks — arrays de estruturas para armazenar os componentes e agentes ordenados;
- tau, greedyStart, eliteUpdate permitem controlar o comportamento do algoritmo.
- ApplyExtremalOptimization — mecanismo principal de seleção e atualização de elementos com base em suas posições no ranqueamento, levando em conta a distribuição em lei de potência.
- CalculateComponentFitness — cálculo do fitness do componente do agente.
- SelectRankByPowerLaw — seleção da posição de um componente ou agente usando uma distribuição em lei de potência, o que permite concentrar a busca nos piores elementos.
A classe se destina à aplicação do algoritmo de otimização extrema, especialmente em problemas que exigem a busca de uma solução de qualidade por meio da eliminação sequencial dos componentes menos adequados na população.
//———————————————————————————————————————————————————————————————————— //--- Inicialização bool C_AO_EO::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ ArrayResize (compRanks, coords); ArrayResize (agentRanks, popSize); return true; } //————————————————————————————————————————————————————————————————————
O método de inicialização da classe EO é responsável pela preparação das condições iniciais para o funcionamento posterior do algoritmo. Ele recebe os parâmetros dos intervalos de valores mínimos e máximos das variáveis, bem como os tamanhos dos passos para sua variação, além do número de épocas (iterações), se necessário.
Em primeiro lugar, o método chama o procedimento padrão de inicialização, responsável pela configuração dos parâmetros básicos e pela preparação das estruturas gerais de dados. Se esse procedimento falhar, a inicialização do método é interrompida.
Se a inicialização for concluída com sucesso, dentro do método ocorre o redimensionamento dos arrays destinados ao armazenamento dos componentes e agentes ranqueados. O tamanho do array de componentes é definido de acordo com o número de coordenadas ou variáveis do problema, e o array de agentes, de acordo com o tamanho especificado da população. Ao final dessas etapas, o método retorna o resultado de inicialização bem-sucedida.
//———————————————————————————————————————————————————————————————————— //--- Ciclo principal do algoritmo void C_AO_EO::Moving () { // Inicialização inicial da população if (!revision) { int greedyCount = (int)(popSize * greedyStart); for (int i = 0; i < popSize; i++) { // Inicialização aleatória para os demais for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } // Aplicamos Extremal Optimization --------------------------------- ApplyExtremalOptimization (); } //————————————————————————————————————————————————————————————————————
O método "ApplyExtremalOptimization" implementa o ciclo principal de funcionamento do algoritmo EO para atualizar a população de agentes. Seu objetivo é melhorar as soluções por meio da modificação dos componentes dos agentes, com base nos princípios do EO. É determinado o número de agentes a serem atualizados em uma única iteração, levando em conta o parâmetro "eliteUpdate" (fração de agentes atualizados) e o tamanho da população. Os agentes são ordenados com base em sua qualidade geral. O algoritmo ranqueia os agentes dos piores para os melhores, para que opere na busca por máximos. Usando uma distribuição de probabilidade em lei de potência, é selecionado o agente que será submetido a modificações.
Para o agente selecionado, é realizado o ranqueamento de seus componentes. A cada componente é atribuído um valor de fitness para avaliar sua contribuição para a qualidade geral do agente. Os componentes são ordenados dos piores para os melhores com base em seu "fitness". Usa-se uma distribuição de probabilidade em lei de potência para selecionar um dos componentes do agente para modificação. Isso é feito para que os componentes com pior posição no ranqueamento tenham maior probabilidade de serem escolhidos.
O componente selecionado do agente é substituído por um valor aleatório dentro do intervalo permitido, definido pelos parâmetros "rangeMin" e "rangeMax". Em seguida, é feita uma verificação de validade do valor obtido para garantir conformidade com os limites definidos e com os tamanhos de passo.O método repete essas etapas para cada agente sujeito à atualização, implementando a lógica central do algoritmo EO: selecionar os componentes com piores características e substituí-los aleatoriamente com o objetivo de melhorar a qualidade geral das soluções.
//———————————————————————————————————————————————————————————————————— //--- Aplicação do Extremal Optimization void C_AO_EO::ApplyExtremalOptimization () { // Número de agentes a serem atualizados nesta iteração int numUpdates = MathMax (1, (int)(popSize * eliteUpdate)); // Atualizamos os agentes selecionados segundo o princípio EO //for (int update = 0; update < numUpdates; update++) for (int update = 0; update < popSize; update++) { // Passo 1: Selecionamos um agente para modificação // Utilizamos o ranqueamento pelo fitness geral int targetAgent; // Ranqueamos os agentes por fitness (do pior para o melhor, para maximização) for (int i = 0; i < popSize; i++) { agentRanks [i].idx = i; agentRanks [i].fitness = a [i].f; } // Ordenação (os piores no início, para maximização) for (int i = 0; i < popSize - 1; i++) { for (int j = i + 1; j < popSize; j++) { if (agentRanks [i].fitness > agentRanks [j].fitness) { RankedAgent temp = agentRanks [i]; agentRanks [i] = agentRanks [j]; agentRanks [j] = temp; } } } // Selecionamos o agente conforme a distribuição de lei de potência int rank = SelectRankByPowerLaw (popSize); targetAgent = agentRanks [rank].idx; // Passo 2: Ranqueamos os componentes do agente selecionado for (int c = 0; c < coords; c++) { compRanks [c].agentIdx = targetAgent; compRanks [c].componentIdx = c; compRanks [c].fitness = CalculateComponentFitness (targetAgent, c); } // Ordenação dos componentes (os piores no início) for (int i = 0; i < coords - 1; i++) { for (int j = i + 1; j < coords; j++) { if (compRanks [i].fitness > compRanks [j].fitness) { RankedComponent temp = compRanks [i]; compRanks [i] = compRanks [j]; compRanks [j] = temp; } } } // Passo 3: Selecionamos um componente para alteração conforme P(n) ∝ n^(-τ) int compRank = SelectRankByPowerLaw (coords); int compIdx = compRanks [compRank].componentIdx; // Passo 4: Substituímos o componente selecionado por um novo valor aleatório // Это ключевой принцип EO - безусловная замена на случайное a [targetAgent].c [compIdx] = u.RNDfromCI (rangeMin [compIdx], rangeMax [compIdx]); // Verificação de limites a [targetAgent].c [compIdx] = u.SeInDiSp (a [targetAgent].c [compIdx], rangeMin [compIdx], rangeMax [compIdx], rangeStep [compIdx]); } } //————————————————————————————————————————————————————————————————————
O método "CalculateComponentFitness" calcula o valor de fitness de um componente individual do agente. Essa função desempenha um papel importante no algoritmo Extremal Optimization (EO), avaliando a contribuição de cada componente para a qualidade geral da solução. O algoritmo usa uma métrica simples baseada no cálculo do fitness como contribuição relativa do componente para a qualidade geral.
Inicialmente, o "fitness" é inicializado com zero. Em seguida, é calculado o intervalo de valores do componente ("range"). Se esse intervalo for maior que zero, calcula-se o desvio normalizado ("deviation"). O desvio é calculado como o valor absoluto da diferença entre o valor do componente do agente e o valor base "cB", normalizado pelo intervalo de valores do componente. A aptidão é calculada subtraindo-se o "deviation" de 1.0. Isso torna o "fitness" inversamente proporcional ao desvio: quanto menor o desvio do componente em relação ao valor-alvo, maior o seu "fitness".
Assim, a função retorna uma avaliação da aptidão de um componente específico, mostrando o quão bem o valor atual do componente corresponde ao valor-alvo, o que é necessário para o ranqueamento posterior dos componentes.
//———————————————————————————————————————————————————————————————————— //--- Cálculo do fitness do componente double C_AO_EO::CalculateComponentFitness (int agentIdx, int componentIdx) { // Para a tarefa geral de otimização utilizamos uma métrica simples // λi = contribuição relativa do componente para a qualidade geral double fitness = 0.0; double range = rangeMax [componentIdx] - rangeMin [componentIdx]; if (range > 0) { // Desvio normalizado double deviation = MathAbs (a [agentIdx].c [componentIdx] - cB [componentIdx]) / range; fitness = 1.0 - deviation; // Invertemos para que maior = melhor } return fitness; } //————————————————————————————————————————————————————————————————————
O método "SelectRankByPowerLaw" implementa a seleção da posição de um elemento em uma lista com base em uma distribuição de probabilidades em lei de potência. Esse método é fundamental para o algoritmo EO, pois é por meio dele que são selecionados os agentes e os componentes a serem modificados. O método recebe como entrada "maxRank", que define a posição máxima do elemento.
Na base do método está o princípio da transformação inversa para obtenção de um valor aleatório que segue a lei de potência P(n) ∝ n^(-τ), em que: n é a posição do elemento; τ (tau) é o parâmetro que determina a forma da distribuição em lei de potência.
Dependendo do valor do parâmetro "tau", são implementados dois cenários:
-
Caso geral (τ ≠ 1.0):
- é calculado o fator de normalização "norm", que garante o escalonamento correto das probabilidades;
- é gerado um número aleatório "r" no intervalo [0, 1) com a ajuda de "u.RNDprobab ()";
- é usada a fórmula de transformação inversa para calcular a posição "rank" com base em "r", "norm" e "τ";
- a posição é limitada ao intervalo [0, maxRank - 1], para evitar ultrapassar os limites do array.
-
Caso especial (τ = 1.0):
- é calculado o fator de normalização "norm" para o caso τ = 1.0;
- é usada uma fórmula especial para calcular a posição "rank";
- a posição é limitada ao intervalo [0, maxRank - 1].
Ao final, o método retorna um número inteiro "rank", que indica a posição selecionada do elemento na lista ranqueada. Essa seleção é probabilística, ou seja, os elementos com menor posição no ranqueamento (os piores) têm maior probabilidade de ser selecionados, de acordo com os princípios do EO.
//———————————————————————————————————————————————————————————————————— //--- Seleção do rank conforme a distribuição de lei de potência int C_AO_EO::SelectRankByPowerLaw (int maxRank) { // P(n) ∝ n^(-τ), onde n é o rank de 1 até maxRank // Utilizamos o método da transformação inversa double r = u.RNDprobab (); if (tau != 1.0) { // Caso geral: transformação inversa para P(n) ∝ n^(-τ) double norm = (1.0 - MathPow (maxRank + 1.0, 1.0 - tau)) / (1.0 - tau); double x = r * norm; int rank = (int)MathPow ((1.0 - tau) * x + 1.0, 1.0 / (1.0 - tau)) - 1; if (rank >= maxRank) rank = maxRank - 1; if (rank < 0) rank = 0; return rank; } else { // Caso especial τ = 1: P(n) ∝ 1/n double norm = MathLog (maxRank + 1.0); int rank = (int)(MathExp (r * norm) - 1.0); if (rank >= maxRank) rank = maxRank - 1; if (rank < 0) rank = 0; return rank; } } //————————————————————————————————————————————————————————————————————
O método "Revision" destina-se a atualizar as informações sobre as melhores soluções encontradas durante a execução do algoritmo EO. Sua tarefa é determinar a melhor solução atual e atualizar as variáveis globais que armazenam as informações sobre ela. É criado um array temporário "aT" para armazenar os agentes ordenados. A população de agentes "a" é ordenada usando a função embutida "u.Sorting". A ordenação é realizada para maximização, ou seja, os melhores agentes, aqueles cujo valor da função de aptidão "f" é maior, ficam no início do array "a" (que é a principal estrutura de dados), que contém informações sobre os agentes, incluindo os valores de seus componentes "c" e o valor da função de aptidão "f".
Após a ordenação, é verificado se o valor da função de aptidão "f" do melhor agente, isto é, a[0], é maior do que o valor atual da melhor solução "fB" (que armazena o valor da função de aptidão da melhor solução encontrada até o momento). Se o melhor agente atual for superior à melhor solução global, então os valores dos componentes do melhor agente (a[0].c) são copiados para o array "cB", que provavelmente armazena os componentes da melhor solução, e "fB" é atualizado com o valor da função de aptidão do melhor agente (a[0].f).
Assim, a função "Revision" atualiza as informações sobre a melhor solução, preservando seus componentes e o valor da função de aptidão, além de ordenar a população para que as melhores soluções estejam sempre disponíveis no início do array.
//———————————————————————————————————————————————————————————————————— //--- Atualização das melhores soluções void C_AO_EO::Revision () { // Ordenação da população para MAXIMIZAÇÃO static S_AO_Agent aT []; ArrayResize (aT, popSize); // Utilizamos a função de ordenação embutida u.Sorting (a, aT, popSize); // Atualização da melhor solução global if (a [0].f > fB) { ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); fB = a [0].f; } } //————————————————————————————————————————————————————————————————————
Resultados dos testes
Após os testes, o algoritmo não apresentou bons resultados, por isso decidi revisar todos os métodos originais e criar uma versão modificada, voltada para melhorar a convergência do algoritmo.EO|Extremal Optimization (Boettcher-Percus)|50.0|1.4|0.5|0.3|
=============================
5 Hilly's; Func runs: 10000; result: 0.5146369337195529
25 Hilly's; Func runs: 10000; result: 0.29089804555433085
500 Hilly's; Func runs: 10000; result: 0.25192095557138877
=============================
5 Forest's; Func runs: 10000; result: 0.367128650332966
25 Forest's; Func runs: 10000; result: 0.19477408852361866
500 Forest's; Func runs: 10000; result: 0.15367465708144543
=============================
5 Megacity's; Func runs: 10000; result: 0.2584615384615384
25 Megacity's; Func runs: 10000; result: 0.12707692307692314
500 Megacity's; Func runs: 10000; result: 0.09413846153846227
=============================
All score: 2.25271 (25.03%)
A seguir, é apresentada minha própria interpretação desse método de otimização. Vamos implementar uma nova classe que será herdada da classe base de otimização.
No construtor, são definidos os parâmetros iniciais do algoritmo: tamanho da população, quantidade das piores soluções que devem ser elevadas (melhoradas), probabilidade de mutação e os expoentes da distribuição para seleção e mutação. Os parâmetros são armazenados em um array de estruturas para posterior alteração e ajuste.
O método "SetParams" atualiza as variáveis internas da classe com base nos valores do array de parâmetros. São declarados métodos para inicialização do algoritmo, execução dos passos de movimento (atualização do estado) e revisão (para avaliação e correção das soluções). Na parte privada da classe, são armazenadas variáveis que acompanham a época atual e a época total de execução. Também é definido um método para mutação de um componente específico da solução na população, que é uma parte fundamental do algoritmo implementado.
//———————————————————————————————————————————————————————————————————— class C_AO_EOm : public C_AO { public: //---------------------------------------------------------- ~C_AO_EOm () { } C_AO_EOm () { ao_name = "EOm"; ao_desc = "Extremal Optimization M"; ao_link = "https://www.mql5.com/ru/articles/18755"; popSize = 50; // Tamanho da população popRaising = 3; // Elevação dos piores mutationRate = 0.1; // Probabilidade de mutação powCh = 2.0; // Expoente da lei de distribuição da seleção powMut = 8.0; // Expoente da lei de distribuição da mutação ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "popRaising"; params [1].val = popRaising; params [2].name = "mutationRate"; params [2].val = mutationRate; params [3].name = "powCh"; params [3].val = powCh; params [4].name = "powMut"; params [4].val = powMut; } void SetParams () { popSize = (int)params [0].val; popRaising = (int)params [1].val; mutationRate = params [2].val; powCh = params [3].val; powMut = params [4].val; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0); void Moving (); void Revision (); //------------------------------------------------------------------ int popRaising; // Elevação dos piores double mutationRate; // Probabilidade de mutação double powCh; // Expoente da lei de distribuição da seleção double powMut; // Expoente da lei de distribuição da mutação private: //--------------------------------------------------------- int currentEpoch; // época atual int totalEpochs; // número total de épocas void MutateComponent (int agentIdx, int componentIdx); }; //————————————————————————————————————————————————————————————————————
O método "Init" é responsável pela inicialização do algoritmo. A função recebe como entrada os arrays com os valores mínimos, máximos e o passo dos parâmetros de otimização, bem como o número total de épocas (ciclos) de execução do algoritmo.
Dentro do método, primeiro é chamada a função "StandardInit", da classe base "C_AO". Essa função executa a inicialização geral, a alocação de memória ou a definição dos parâmetros básicos relacionados aos intervalos e aos passos dos parâmetros de otimização.
Se "StandardInit" terminar com falha, a função "Init" também encerra sua execução, retornando "false". Se "StandardInit" for concluída com sucesso, o método inicializa a variável "currentEpoch" (época atual) com "0" e "totalEpochs" (número total de épocas) com o valor recebido no parâmetro "epochsP".
Ao final, o método retorna "true", sinalizando inicialização bem-sucedida. Assim, o método prepara o algoritmo para a execução, definindo os parâmetros iniciais e os contadores de épocas.
//———————————————————————————————————————————————————————————————————— //--- Inicialização bool C_AO_EOm::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ currentEpoch = 0; totalEpochs = epochsP; return true; } //————————————————————————————————————————————————————————————————————
O método "Moving" representa o ciclo principal de funcionamento do algoritmo de otimização extrema. Ele é responsável pela evolução da população de soluções durante a busca da solução ótima. Incremento da época: o contador "currentEpoch" é incrementado. Inicialização da população (apenas na primeira época): se a flag "revision" (que indica a necessidade de revisão das soluções) for igual a "false" (ou seja, no primeiro ciclo de execução do algoritmo), ocorre a inicialização da população.
Para cada "agente" (solução) da população, para cada "coordenada" (parâmetro da solução), é gerado um valor aleatório dentro do intervalo especificado (rangeMin, rangeMax) para a coordenada atual. Aplica-se a discretização "SeInDiSp" para que os valores dos parâmetros correspondam aos passos definidos. Após a inicialização, "revision" recebe o valor "true", para que esse bloco de código seja executado apenas uma vez. O método encerra sua execução.
Aplicação da otimização extrema (nas épocas subsequentes): é criado um array temporário "aT" para armazenar as novas soluções (mutadas). Para cada agente da população, a estrutura "aT[i]" é inicializada. Para cada coordenada da solução, é gerado um número aleatório, que é elevado à potência "powCh". Isso é usado para selecionar o "pai".
O número aleatório é escalonado para selecionar o índice do pai na população, "ind". Define-se o tipo de mutação: se o número aleatório for menor que "mutationRate" (a mutação é ativada com probabilidade "mutationRate"), aplica-se a mutação segundo a distribuição em lei de potência "PowerDistribution" ao valor da coordenada do pai. Caso contrário, ocorre um "movimento direcionado" em direção à melhor solução com adição de ruído aleatório. O novo valor é calculado como a soma do valor da coordenada do pai, de um número aleatório e da diferença entre "cB[c]" (a melhor coordenada encontrada) e a coordenada do pai. Aplica-se a discretização "SeInDiSp". Após a mutação, todas as coordenadas do array temporário "aT" são copiadas para o array principal da população "a".
Assim, o método implementa o ciclo evolutivo no qual, a cada passo (época), as soluções sofrem mutação, usando mecanismos de seleção, mutação aleatória e busca direcionada, com o objetivo de melhorar seus valores, minimizando ou maximizando a função objetivo, para ao final encontrar a solução ótima.
//———————————————————————————————————————————————————————————————————— //--- Ciclo principal do algoritmo void C_AO_EOm::Moving () { currentEpoch++; // Inicialização inicial da população if (!revision) { for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } //Apply Extremal Optimization--------------------------------------- static S_AO_Agent aT []; ArrayResize (aT, popSize); for (int i = 0; i < popSize; i++) { aT [i].Init (coords); for (int c = 0; c < coords; c++) { double rnd = u.RNDprobab (); rnd = pow (rnd, powCh); int ind = (int)u.Scale (rnd, 0.0, 1.0, 0, popSize - 1); // Seleção do tipo de mutação double mutType = u.RNDprobab (); if (mutType < mutationRate) { aT [i].c [c] = u.PowerDistribution (a [ind].c [c], rangeMin [c], rangeMax [c], powMut); } else { // Movimento direcionado para o melhor com ruído aT [i].c [c] = a [ind].c [c] + u.RNDprobab () * (cB [c] - a [ind].c [c]); } // Verificação de limites aT [i].c [c] = u.SeInDiSp (aT [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } for (int i = 0; i < popSize; i++) ArrayCopy (a [i].c, aT [i].c); } //————————————————————————————————————————————————————————————————————
Esse método é responsável por atualizar as informações sobre as melhores soluções durante a execução do algoritmo.
Ordenação da população: é criado um array temporário "aT" para armazenar uma cópia da população. A população "a" é ordenada de acordo com o valor da função objetivo. Para a ordenação, é usado o método "u.Sorting".
Atualização da melhor solução global: verifica-se se o valor da função objetivo "f" do primeiro elemento da população, isto é, da melhor solução, é melhor do que o valor atual da melhor solução global "fB". Se a solução atual for melhor, então "cB" é copiado das coordenadas do primeiro elemento "a[0].c", e "fB" é atualizado com o valor de "f" da melhor solução.
Atualização da pior solução: ""fW" é atualizado com o valor da função do último elemento da população.
"Elevação" (Raising) das piores soluções: em um ciclo executado "popRaising" vezes, ocorre a "elevação" das piores soluções da população: para os "popRaising" piores agentes, localizados no final do array ordenado "a", o valor da função objetivo "f" é recalculado como um valor aleatório situado entre "fW" (o pior resultado atual) e "fB" (o melhor resultado atual). Isso é feito para introduzir diversidade ou deslocar as piores soluções para uma posição mais favorável.
Reordenação da população: a população "a" é reordenada usando o método "u.Sorting". Isso é necessário para reorganizar a população após as alterações nos valores de "f".
//———————————————————————————————————————————————————————————————————— //--- Atualização das melhores soluções void C_AO_EOm::Revision () { // Ordenação da população -------------------------------------------- static S_AO_Agent aT []; ArrayResize (aT, popSize); u.Sorting (a, aT, popSize); // Atualização da melhor solução global if (a [0].f > fB) { ArrayCopy (cB, a [0].c, 0, 0, WHOLE_ARRAY); fB = a [0].f; } fW = a [popSize - 1].f; //------------------------------------------------------------------ for (int i = 0; i < popRaising; i++) { a [popSize - 1 - i].f = u.RNDfromCI (fW, fB); } u.Sorting (a, aT, popSize); } //————————————————————————————————————————————————————————————————————
Agora, o algoritmo, que em certo sentido herda ideias do EO, mas foi modificado, usa uma distribuição em lei de potência para selecionar doadores, que não são necessariamente ruins.
a [popSize - 1 - i].f = u.RNDfromCI (fW, fB); Adicionei uma característica que não aparece nas descrições do EO: o algoritmo efetivamente "ressuscita" os piores agentes, atribuindo a eles um fitness aleatório no intervalo entre o pior e o melhor da população. O PowerDistribution para mutação é uma interpretação da "mutação baseada em distribuição em lei de potência". O movimento direcionado em direção à melhor solução, quando mutType >= mutationRate, é um acréscimo para acelerar a convergência.
Agora podemos observar os resultados da versão modificada. Esses resultados podem ser incluídos em nossa tabela de classificação.
EOm|Extremal Optimization Mod|50.0|3.0|0.1|2.0|8.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7616651321732368
25 Hilly's; Func runs: 10000; result: 0.7724295992586084
500 Hilly's; Func runs: 10000; result: 0.3174703398632668
=============================
5 Forest's; Func runs: 10000; result: 0.9999936711143977
25 Forest's; Func runs: 10000; result: 0.7675163269928252
500 Forest's; Func runs: 10000; result: 0.23527203643380376
=============================
5 Megacity's; Func runs: 10000; result: 0.7476923076923077
25 Megacity's; Func runs: 10000; result: 0.5396923076923076
500 Megacity's; Func runs: 10000; result: 0.14249230769230903
=============================
All score: 5.28422 (58.71%)
Na visualização, nota-se uma grande dispersão dos resultados nas funções de baixa dimensionalidade (linhas verdes).
EOm na função de teste Hilly
EOm na função de teste Forest
EOm na função de teste Megacity
Após os testes realizados, o algoritmo EOm ocupa o 12º lugar em nossa tabela de classificação.
| № | 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 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 13 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 14 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 15 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 16 | BHAm | black hole algorithm M | 0,75236 | 0,76675 | 0,34583 | 1,86493 | 0,93593 | 0,80152 | 0,27177 | 2,00923 | 0,65077 | 0,51646 | 0,15472 | 1,32195 | 5,196 | 57,73 |
| 17 | ASO | anarchy society optimization | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5,178 | 57,54 |
| 18 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 19 | AOSm | 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 |
| 20 | TSEA | turtle shell evolution algorithm (joo) | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 21 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 22 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 23 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 24 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 25 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 26 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 27 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4,762 | 52,91 |
| 28 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 29 | SSG | saplings sowing and growing | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 30 | BCOm | bacterial chemotaxis optimization M | 0,75953 | 0,62268 | 0,31483 | 1,69704 | 0,89378 | 0,61339 | 0,22542 | 1,73259 | 0,65385 | 0,42092 | 0,14435 | 1,21912 | 4,649 | 51,65 |
| 31 | ABO | african buffalo optimization | 0,83337 | 0,62247 | 0,29964 | 1,75548 | 0,92170 | 0,58618 | 0,19723 | 1,70511 | 0,61000 | 0,43154 | 0,13225 | 1,17378 | 4,634 | 51,49 |
| 32 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 33 | FBA | fractal-based Algorithm | 0,79000 | 0,65134 | 0,28965 | 1,73099 | 0,87158 | 0,56823 | 0,18877 | 1,62858 | 0,61077 | 0,46062 | 0,12398 | 1,19537 | 4,555 | 50,61 |
| 34 | TSm | tabu search M | 0,87795 | 0,61431 | 0,29104 | 1,78330 | 0,92885 | 0,51844 | 0,19054 | 1,63783 | 0,61077 | 0,38215 | 0,12157 | 1,11449 | 4,536 | 50,40 |
| 35 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 36 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 37 | AEFA | artificial electric field algorithm | 0,87700 | 0,61753 | 0,25235 | 1,74688 | 0,92729 | 0,72698 | 0,18064 | 1,83490 | 0,66615 | 0,11631 | 0,09508 | 0,87754 | 4,459 | 49,55 |
| 38 | AEO | artificial ecosystem-based optimization algorithm | 0,91380 | 0,46713 | 0,26470 | 1,64563 | 0,90223 | 0,43705 | 0,21400 | 1,55327 | 0,66154 | 0,30800 | 0,28563 | 1,25517 | 4,454 | 49,49 |
| 39 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 40 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 41 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 42 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
| 43 | SOA | simple optimization algorithm | 0,91520 | 0,46976 | 0,27089 | 1,65585 | 0,89675 | 0,37401 | 0,16984 | 1,44060 | 0,69538 | 0,28031 | 0,10852 | 1,08422 | 4,181 | 46,45 |
| 44 | ABHA | artificial bee hive algorithm | 0,84131 | 0,54227 | 0,26304 | 1,64663 | 0,87858 | 0,47779 | 0,17181 | 1,52818 | 0,50923 | 0,33877 | 0,10397 | 0,95197 | 4,127 | 45,85 |
| 45 | ACMO | atmospheric cloud model optimization | 0,90321 | 0,48546 | 0,30403 | 1,69270 | 0,80268 | 0,37857 | 0,19178 | 1,37303 | 0,62308 | 0,24400 | 0,10795 | 0,97503 | 4,041 | 44,90 |
| RW | random walk | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Considerações finais
A implementação compacta modificada do EOm apresentada aqui demonstra um exemplo interessante no campo da otimização metaheurística: um desvio significativo dos princípios teóricos pode levar à melhoria dos resultados práticos. O algoritmo, que ocupou o 12º lugar entre 45 métodos populacionais, na prática representa um híbrido que preservou apenas a ideia central da distribuição em lei de potência do EO original.
Mecanismo de "ressurreição" dos piores agentes evita a convergência prematura, mantém a diversidade da população e cria oportunidades adicionais de exploração. A simplificação do esquema computacional, com a eliminação da avaliação por componente, reduz a complexidade computacional, e a atuação direta sobre as soluções acelera a convergência.
O sucesso da versão modificada do EO confirma um princípio importante no desenvolvimento de metaheurísticas: a eficácia de um algoritmo não é determinada pela fidelidade à ideia original, mas pelo equilíbrio entre exploração e aproveitamento do espaço de busca. A implementação apresentada, apesar do afastamento em relação aos princípios clássicos do Extremal Optimization, demonstra alta velocidade de convergência, resultados competitivos, simplicidade de implementação e facilidade de ajuste.
Isso a torna uma ferramenta útil no arsenal dos métodos de otimização populacional, especialmente para problemas em que o equilíbrio entre a qualidade da solução e os custos computacionais é importante.
Figura 1. Graduação de cores dos algoritmos por testes correspondentes
Figura 2. Histograma dos resultados de teste dos algoritmos (na escala de 0 a 100, quanto maior melhor, onde 100 é o resultado teórico máximo possível, no arquivo compactado há o script para cálculo da tabela de classificação)
Vantagens e desvantagens do algoritmo EOm:
Vantagens:
- Implementação simples
- Rápido e eficiente
- Bons resultados em problemas discretos
Desvantagens:
- Grande dispersão dos resultados em funções de baixa dimensionalidade
- Resultados medianos em problemas "suaves" de baixa 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_EOm.mq5 | Script | Ambiente de testes para o EOm |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/18755
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.
Caminhe em novos trilhos: Personalize indicadores no MQL5
Redes neurais em trading: Previsão probabilística de séries temporais (Conclusão)
Está chegando o novo MetaTrader 5 e MQL5
Rede neural quântica em MQL5 (Parte I): Criando um arquivo de inclusão
- 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