Algoritmos de otimização populacional

MetaTrader 5 — Exemplos | 28 novembro 2022, 09:31

275

Andrey Dik

"Nada acontece no universo
em que alguma regra de máximo ou mínimo não aparece"
Leonhard Euler, século XVIII

Conteúdo:

1. Perspectiva histórica

Algoritmos de otimização são algoritmos que permitem encontrar pontos extremos no domínio de uma função, nos quais a função atinge seu valor mínimo ou máximo.

Os antigos especialistas gregos da antiguidade já sabiam que:

— De todas as formas com um determinado perímetro, o círculo tem a maior área.

— De todos os polígonos com um determinado número de lados e um determinado perímetro, um polígono regular tem a maior área.

— De todas as figuras tridimensionais com uma determinada área, a esfera tem o maior volume.

O primeiro problema com soluções variacionais também foi proposto na mesma época. Segundo a lenda, isso aconteceu por volta de 825 aC. Dido, a irmã do rei da cidade fenícia de Tiro, mudou-se para a costa sul do Mar Mediterrâneo e pediu a uma tribo local um pedaço de terra que pudesse ser coberto com uma pele de touro. Os moradores deram-lhe um esconderijo. A engenhosa garota cortou em cintos estreitos e os amarrou fazendo uma corda. Com esta corda, ela cobriu o território ao largo da costa e ali fundou a cidade de Cartago.

O problema reside em encontrar a curva mais eficiente, abrangendo a área de superfície máxima, entre curvas planas fechadas de um determinado comprimento. A área máxima neste problema é representada pela área circunscrita por um semicírculo.

didona1

Agora vamos pular um grande pedaço da história, incluindo a cultura antiga do Mediterrâneo, a opressão da Inquisição e o charlatanismo da Idade Média, até o Renascimento com sua fuga livre de pensamento e novas teorias. Em junho de 1696, Johann Bernoulli publica o seguinte texto para os leitores da Acta Eruditorum: "Eu, Johann Bernoulli, me dirijo aos matemáticos mais brilhantes do mundo. Nada é mais atraente para pessoas inteligentes do que um problema honesto e desafiador, cuja solução possível conferirá fama e permanecerá como um monumento duradouro. Seguindo o exemplo dado por Pascal, Fermat, etc., espero ganhar a gratidão de toda a comunidade científica apresentando aos melhores matemáticos de nosso tempo um problema que testará seus métodos e a força de seu intelecto. Se alguém me comunicar a solução do problema proposto, devo declará-lo publicamente digno de louvor”.

Problema da braquistócrona de Johann Bernulli:

"Dados dois pontos A e B em um plano vertical, qual é a curva traçada por um ponto atuado apenas pela gravidade, que começa em A e atinge B no menor tempo". Notavelmente, Galileu tentou resolver um problema semelhante em 1638, muito antes da publicação de Bernoulli. A resposta: o caminho mais rápido de todos, de um ponto a outro, não é o caminho mais curto, como parece à primeira vista, não uma linha reta, mas uma curva — uma cicloide que determina a curvatura da curva em cada ponto.

Brachistochrone9

Curva braquistócrona

Todas as outras soluções, incluindo a de Newton (que não foram reveladas na época), são baseadas em encontrar o gradiente em cada ponto. O método por trás da solução proposta por Isaac Newton forma a base do cálculo variacional. Os métodos do cálculo variacional são normalmente aplicados na resolução de problemas, nos quais os critérios de otimalidade são apresentados na forma de funcionais e cujas soluções são funções desconhecidas. Tais problemas geralmente surgem na otimização estática de processos com parâmetros distribuídos ou em problemas de otimização dinâmica.

Condições extremas de primeira ordem no cálculo variacional foram obtidas por Leonard Euler e Joseph Lagrange (as equações de Euler-Lagrange). Essas equações são amplamente utilizadas em problemas de otimização e, juntamente com o princípio da ação estacionária, são aplicadas em cálculos de trajetórias em mecânica. Logo, porém, ficou claro que as soluções dessas equações nem sempre dão um extremo real, o que significa que são necessárias condições suficientes que garantam o seu encontro. O trabalho continuou e as condições extremas de segunda ordem foram derivadas por Legendre e Jacobi, e depois pelo aluno deste último - Hesse. A questão da existência de uma solução no cálculo variacional foi levantada pela primeira vez por Weierstrass na segunda metade do século XIX.

Na segunda metade do século XVIII, a busca por soluções ótimas para os problemas formou os fundamentos matemáticos e os princípios da otimização. Infelizmente, os métodos de otimização tiveram pouco uso em muitas áreas da ciência e tecnologia até a segunda metade do século 20, uma vez que o uso prático de métodos matemáticos exigia enormes recursos computacionais. O advento de novas tecnologias de computação no mundo moderno finalmente tornou possível a implementação de métodos complexos de otimização, dando origem a uma grande variedade de algoritmos disponíveis.

A década de 1980 viu o início do desenvolvimento intensivo da classe de algoritmos de otimização estocástica, que foram o resultado da modelagem emprestada da natureza.

2. Classificação do OA

Classe

Classificação do AO

Ao otimizar os sistemas de negociação, as coisas mais interessantes são os algoritmos de otimização metaheurística. Eles não requerem conhecimento da fórmula da função que está sendo otimizada. Sua convergência para o ótimo global não foi comprovada, mas foi estabelecido experimentalmente que, na maioria dos casos, eles fornecem uma solução razoavelmente boa e isso é suficiente para vários problemas.

Muitos OAs apareceram como modelos emprestados da natureza. Tais modelos também são chamados de comportamentais, enxames ou populações, como o comportamento de pássaros em um bando (algoritmo de enxame de partículas) ou os princípios do comportamento de colônia de formigas (algoritmo de formigas).

Os algoritmos de população envolvem o tratamento simultâneo de várias opções para a resolução do problema de otimização e representam uma alternativa aos algoritmos clássicos baseados em trajetórias de movimento cuja área de busca possui apenas um candidato evoluindo na resolução do problema.

3. Convergência e taxa de convergência. Estabilidade de convergência. Escalabilidade do algoritmo de otimização

Eficiência, velocidade, convergência, bem como os efeitos das condições do problema e parâmetros do algoritmo requerem uma análise cuidadosa para cada implementação algorítmica e para cada classe de problemas de otimização.

3.1) Convergência e taxa de convergência

A propriedade de um algoritmo iterativo para atingir o ótimo da função objetivo ou chegar perto o suficiente dele em um número finito de etapas. No lado direito das capturas de tela acima, vemos um gráfico construído iterativamente dos resultados gerados pela função de teste calculada. Com base nessas duas imagens, nós podemos concluir que a convergência é afetada pela complexidade da superfície da função. Quanto mais complexo, mais difícil é encontrar o extremo global.

A taxa de convergência dos algoritmos é um dos indicadores mais importantes da qualidade de um algoritmo de otimização e é uma das principais características dos métodos de otimização. Quando nós ouvimos que um algoritmo é mais rápido que o outro, na maioria dos casos isso significa a taxa de convergência. Quanto mais próximo o resultado estiver do extremo global e mais rápido ele for obtido (ou seja, as iterações anteriores do algoritmo), maior será esse parâmetro. Observe que a taxa de convergência dos métodos geralmente não excede uma quadrática. Em casos raros, o método pode ter uma taxa cúbica de convergência.

3.2) Estabilidade de convergência

O número de iterações necessárias para atingir o resultado depende não apenas da capacidade de busca do próprio algoritmo, mas também da função em estudo. Se a função for caracterizada por uma alta complexidade da superfície (a presença de curvas acentuadas, distintas, descontinuidades), o algoritmo pode se tornar instável e incapaz de fornecer uma precisão aceitável. Além disso, a estabilidade da convergência pode ser entendida como a repetibilidade dos resultados da otimização quando vários testes consecutivos são realizados. Se os resultados tiverem grandes discrepâncias nos valores, a estabilidade do algoritmo é baixa.

3.3) Escalabilidade do algoritmo de otimização

convergence7 convergence6

A escalabilidade do algoritmo de otimização é a capacidade de manter a convergência com o aumento da dimensão do problema. Ou seja, com o aumento do número de variáveis da função otimizada, a convergência deve permanecer em um nível aceitável para fins práticos. Algoritmos populacionais de otimização de busca apresentam vantagens inegáveis em comparação com algoritmos clássicos, principalmente na resolução de problemas de alta dimensão e mal formalizados. Sob essas condições, os algoritmos de população podem fornecer uma alta probabilidade de localizar o extremo global da função que está sendo otimizada.

No caso de uma função otimizada suave e unimodal, os algoritmos de população são geralmente menos eficientes do que qualquer método de gradiente clássico. Além disso, as desvantagens dos algoritmos de população incluem uma forte dependência de sua eficiência nos graus de liberdade (o número de parâmetros de ajuste), que são bastante numerosos na maioria dos algoritmos.

4. Funções de teste, construção de um critério de avaliação de um OA complexo

Não existe uma metodologia geralmente aceita para testar e comparar os algoritmos de otimização. No entanto, existem muitas funções de teste propostas por pesquisadores em anos diferentes. Nós usaremos as funções que criei antes de postar o primeiro artigo. Essas funções podem ser encontradas na pasta da plataforma \MQL5\Experts\Examples\Math 3D\Functions.mqh e \MQL5\Experts\Examples\Math 3D Morpher\Functions.mqh. Essas funções atendem a todos os critérios de complexidade para testes dos OA. Além disso, as funções Forest e Megacity foram desenvolvidas para fornecer um estudo mais abrangente dos recursos de pesquisa do OA.

Função de teste Skin:

A função é suave em todo o seu domínio e tem muitos valores máximos/mínimos locais que diferem insignificantemente (armadilhas de convergência), o que faz com que os algoritmos que não atingem o extremo global fiquem presos.

Skin

Função de teste Forest:

A função representa vários máximos que não possuem diferencial em seus pontos. Portanto, pode ser difícil para os algoritmos de otimização, cuja robustez é criticamente dependente da suavidade da função em estudo.

Forest

Função de teste Megacity:

Uma função discreta que forma "áreas" (onde a mudança das variáveis não leva a uma mudança significativa no valor da função). Portanto, ele representa uma dificuldade para os algoritmos que requerem um gradiente.

Chinatown

Megacity

5. Bateria de testes

Para uma comparação abrangente dos algoritmos de otimização, foi feita uma tentativa de criar um critério de avaliação geral. A complexidade dessa ideia reside no fato de que não está claro como comparar os algoritmos, porque cada um deles é bom à sua maneira para a classe de problemas correspondente. Por exemplo, um algoritmo converge rapidamente, mas não escala bem, enquanto outro escala bem, mas é instável.

Convergência: Para estudar a convergência, nós usamos três funções apresentadas acima. Seus máximos e mínimos são convertidos para um intervalo de 0.0 (pior resultado) a 1.0 (melhor resultado), o que nos permitirá avaliar a capacidade dos algoritmos de garantir a convergência em diferentes tipos de problemas.
Taxa de convergência: Os melhores resultados do algoritmo são medidos na 1000ª e 10.000ª execução da função testada. Assim, nós podemos ver a rapidez com que o OA converge. Quanto mais rápida a convergência, mais curvado será o gráfico de convergência em direção ao máximo.
Estabilidade: Faça cinco execuções da otimização para cada uma das funções e calcule o valor médio no intervalo de 0.0 a 1.0. Isso é necessário porque os resultados de alguns algoritmos podem variar muito de execução para execução. Quanto maior a convergência em cada um dos cinco testes, maior a estabilidade.
Escalabilidade: Alguns OAs só conseguem mostrar resultados práticos em funções com um pequeno número de variáveis, por exemplo, não mais que duas, e alguns nem conseguem trabalhar com mais de uma variável. Além disso, existem algoritmos capazes de trabalhar com funções com mil variáveis. Tais algoritmos de otimização podem ser usados como OA para as redes neurais.

Para facilitar o uso das funções de teste, vamos escrever uma classe pai e um enumerador que nos permitirá selecionar um objeto da classe filha da função de teste correspondente no futuro:

//——————————————————————————————————————————————————————————————————————————————
class C_Function
{
  public: //====================================================================
  double CalcFunc (double &args [], //function arguments
                   int     amount)  //amount of runs functions
  {
    double x, y;
    double sum = 0.0;
    for (int i = 0; i < amount; i++)
    {
      x = args [i * 2];
      y = args [i * 2 + 1];

      sum += Core (x, y);
    }

    sum /= amount;

    return sum;
  }
  double GetMinArg () { return minArg;}
  double GetMaxArg () { return maxArg;}
  double GetMinFun () { return minFun;}
  double GetMaxFun () { return maxFun;}
  string GetNamFun () { return fuName;}

  protected: //==================================================================
  void SetMinArg (double min) { minArg = min;}
  void SetMaxArg (double max) { maxArg = max;}
  void SetMinFun (double min) { minFun = min;}
  void SetMaxFun (double max) { maxFun = max;}
  void SetNamFun (string nam) { fuName = nam;}

  private: //====================================================================
  virtual double Core (double x, double y) { return 0.0;}
  
  double minArg;
  double maxArg;
  double minFun;
  double maxFun;
  string fuName;
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
enum EFunc
{
  Skin,
  Forest,
  Megacity,
  
};
C_Function *SelectFunction (EFunc f)
{
  C_Function *func;
  switch (f)
  {
    case  Skin:
      func = new C_Skin (); return (GetPointer (func));
    case  Forest:
      func = new C_Forest (); return (GetPointer (func));
    case  Megacity:
      func = new C_Megacity (); return (GetPointer (func));
    
    default:
      func = new C_Skin (); return (GetPointer (func));
  }
}
//——————————————————————————————————————————————————————————————————————————————

Então as classes filhas ficarão assim:

//——————————————————————————————————————————————————————————————————————————————
class C_Skin : public C_Function
{
  public: //===================================================================
  C_Skin ()
  {
    SetNamFun ("Skin");
    SetMinArg (-5.0);
    SetMaxArg (5.0);
    SetMinFun (-4.3182);  //[x=3.07021;y=3.315935] 1 point
    SetMaxFun (14.0606);  //[x=-3.315699;y=-3.072485] 1 point
  }

  private: //===================================================================
  double Core (double x, double y)
  {
    double a1=2*x*x;
    double a2=2*y*y;
    double b1=MathCos(a1)-1.1;
    b1=b1*b1;
    double c1=MathSin(0.5*x)-1.2;
    c1=c1*c1;
    double d1=MathCos(a2)-1.1;
    d1=d1*d1;
    double e1=MathSin(0.5*y)-1.2;
    e1=e1*e1;

   double res=b1+c1-d1+e1;
   return(res);
  }
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
class C_Forest : public C_Function
{
  public: //===================================================================
  C_Forest ()
  {
    SetNamFun ("Forest");
    SetMinArg (-50.0);
    SetMaxArg (-18.0);
    SetMinFun (0.0);             //many points
    SetMaxFun (15.95123239744);  //[x=-25.132741228718345;y=-32.55751918948773] 1 point
  }

  private: //===================================================================
  double Core (double x, double y)
  {
    double a = MathSin (MathSqrt (MathAbs (x - 1.13) + MathAbs (y - 2.0)));
    double b = MathCos (MathSqrt (MathAbs (MathSin (x))) + MathSqrt (MathAbs (MathSin (y - 2.0))));
    double f = a + b;

    double res = MathPow (f, 4);
    if (res < 0.0) res = 0.0;
    return (res);
  }
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
class C_Megacity : public C_Function
{
  public: //===================================================================
  C_Megacity ()
  {
    SetNamFun ("Megacity");
    SetMinArg (-15.0);
    SetMaxArg (15.0);
    SetMinFun (0.0);   //many points
    SetMaxFun (15.0);  //[x=`3.16;y=1.990] 1 point
  }

  private: //===================================================================
  double Core (double x, double y)
  {
    double a = MathSin (MathSqrt (MathAbs (x - 1.13) + MathAbs (y - 2.0)));
    double b = MathCos (MathSqrt (MathAbs (MathSin (x))) + MathSqrt (MathAbs (MathSin (y - 2.0))));
    double f = a + b;

    double res = floor (MathPow (f, 4));
    return (res);
  }
};
//——————————————————————————————————————————————————————————————————————————————

Para verificar a validade dos resultados do teste dos OA obtidos na bateria de testes, nós podemos usar um script que enumera as funções X e Y com o tamanho do passo Step. Tome cuidado ao escolher o passo, pois um tamanho de passo muito pequeno fará com que o cálculo demore muito. Por exemplo, a função Skin tem o intervalo de argumentos [-5;5]. Com o passo de 0.00001 ao longo do eixo X, será (5-(-5))/0,00001=1'000'000 (milhões) de passos, o mesmo número ao longo do eixo Y, respectivamente, o número total de execuções da função de teste para calcular o valor em cada um dos pontos será igual a 1'000'000 х 1'000'000= 1'000'000'000'000 (10^12, trilhão).

É necessário entender o quão difícil é a tarefa para o OA, pois é necessário encontrar o máximo em apenas 10.000 passos (é o valor aproximado que é usado no otimizador da MetaTrader 5). Observe que este cálculo é feito para uma função com duas variáveis, e o número máximo de variáveis que serão usadas nos testes é 1000.

Tenha em mente o seguinte: os testes de algoritmo neste e nos artigos subsequentes usam o passo 0.0! ou o mínimo possível para uma implementação específica do OA correspondente.

//——————————————————————————————————————————————————————————————————————————————
input EFunc  Function          = Skin;
input double Step              = 0.01;

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  C_Function *TestFunc = SelectFunction (Function);

  double argMin = TestFunc.GetMinArg ();
  double argMax = TestFunc.GetMaxArg ();

  double maxFuncValue = 0;
  double xMaxFunc     = 0.0;
  double yMaxFunc     = 0.0;
  
  double minFuncValue = 0;
  double xMinFunc     = 0.0;
  double yMinFunc     = 0.0;
  
  double fValue       = 0.0;

  double arg [2];

  arg [0] = argMin;
  arg [1] = argMin;

  long cnt = 0;

  while (arg [1] <= argMax && !IsStopped ())
  {
    arg [0] = argMin;

    while (arg [0] <= argMax && !IsStopped ())
    {
      cnt++;

      fValue = TestFunc.CalcFunc (arg, 1);

      if (fValue > maxFuncValue)
      {
        maxFuncValue = fValue;
        xMaxFunc = arg [0];
        yMaxFunc = arg [1];
      }
      if (fValue < minFuncValue)
      {
        minFuncValue = fValue;
        xMinFunc = arg [0];
        yMinFunc = arg [1];
      }

      arg [0] += Step;
      
      if (cnt == 1)
      {
       maxFuncValue = fValue;
       minFuncValue = fValue;
      }
    }

    arg [1] += Step;
  }
  
  Print ("======", TestFunc.GetNamFun (), ", launch counter: ", cnt);
  Print ("MaxFuncValue: ", DoubleToString (maxFuncValue, 16), " X: ", DoubleToString (xMaxFunc, 16), " Y: ", DoubleToString (yMaxFunc, 16));
  Print ("MinFuncValue: ", DoubleToString (minFuncValue, 16), " X: ", DoubleToString (xMinFunc, 16), " Y: ", DoubleToString (yMinFunc, 16));
         
  delete TestFunc;
}

//——————————————————————————————————————————————————————————————————————————————

Vamos escrever uma bateria de testes:

#include <Canvas\Canvas.mqh>
#include <\Math\Functions.mqh>
#include "AO_RND.mqh"

//——————————————————————————————————————————————————————————————————————————————
input int    Population_P       = 50;
input double ArgumentStep_P     = 0.0;
input int    Test1FuncRuns_P    = 1;
input int    Test2FuncRuns_P    = 20;
input int    Test3FuncRuns_P    = 500;
input int    Measur1FuncValue_P = 1000;
input int    Measur2FuncValue_P = 10000;
input int    NumberRepetTest_P  = 5;
input int    RenderSleepMsc_P   = 0;

//——————————————————————————————————————————————————————————————————————————————
int WidthMonitor = 750;  //monitor screen width
int HeighMonitor = 375;  //monitor screen height

int WidthScrFunc = 375 - 2;  //test function screen width
int HeighScrFunc = 375 - 2;  //test function screen height

CCanvas Canvas;  //drawing table
C_AO_RND AO;     //AO object

C_Skin       SkiF;
C_Forest     ForF;
C_Megacity  ChiF;

struct S_CLR
{
    color clr [];
};

S_CLR FunctScrin []; //two-dimensional matrix of colors
double ScoreAll = 0.0;

//——————————————————————————————————————————————————————————————————————————————
void OnStart ()
{
  //creating a table -----------------------------------------------------------
  string canvasName = "AO_Test_Func_Canvas";
  if (!Canvas.CreateBitmapLabel (canvasName, 5, 30, WidthMonitor, HeighMonitor, COLOR_FORMAT_ARGB_RAW))
  {
    Print ("Error creating Canvas: ", GetLastError ());
    return;
  }
  ObjectSetInteger (0, canvasName, OBJPROP_HIDDEN, false);
  ObjectSetInteger (0, canvasName, OBJPROP_SELECTABLE, true);

  ArrayResize (FunctScrin, HeighScrFunc);
  for (int i = 0; i < HeighScrFunc; i++)
  {
    ArrayResize (FunctScrin [i].clr, HeighScrFunc);
  }
  
  //============================================================================
  //Test Skin###################################################################
  Print ("=============================");
  CanvasErase ();
  FuncTests (SkiF, Test1FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrLime);
  FuncTests (SkiF, Test2FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrAqua);
  FuncTests (SkiF, Test3FuncRuns_P, SkiF.GetMinFun (), SkiF.GetMaxFun (), -3.315699, -3.072485, clrOrangeRed);
  
  //Test Forest#################################################################
  Print ("=============================");
  CanvasErase ();
  FuncTests (ForF, Test1FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrLime);
  FuncTests (ForF, Test2FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrAqua);
  FuncTests (ForF, Test3FuncRuns_P, ForF.GetMinFun (), ForF.GetMaxFun (), -25.132741228718345, -32.55751918948773, clrOrangeRed);
  
  //Test Megacity#############################################################
  Print ("=============================");
  CanvasErase ();
  FuncTests (ChiF, Test1FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrLime);
  FuncTests (ChiF, Test2FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrAqua);
  FuncTests (ChiF, Test3FuncRuns_P, ChiF.GetMinFun (), ChiF.GetMaxFun (), 3.16, 1.990, clrOrangeRed);
  
  Print ("All score for C_AO_RND: ", ScoreAll / 18.0);
}
//——————————————————————————————————————————————————————————————————————————————

void CanvasErase ()
{
  Canvas.Erase (XRGB (0, 0, 0));
  Canvas.FillRectangle (1,                1, HeighMonitor - 2, HeighMonitor - 2, COLOR2RGB (clrWhite));
  Canvas.FillRectangle (HeighMonitor + 1, 1, WidthMonitor - 2, HeighMonitor - 2, COLOR2RGB (clrWhite));
}

//——————————————————————————————————————————————————————————————————————————————
void FuncTests (C_Function &f,
                int        funcCount,
                double     minFuncVal,
                double     maxFuncVal,
                double     xBest,
                double     yBest,
                color      clrConv)
{
  DrawFunctionGraph (f.GetMinArg (), f.GetMaxArg (), minFuncVal, maxFuncVal, f);
  SendGraphToCanvas (1, 1);
  int x = (int)Scale (xBest, f.GetMinArg (), f.GetMaxArg (), 0, WidthScrFunc - 1, false);
  int y = (int)Scale (yBest, f.GetMinArg (), f.GetMaxArg (), 0, HeighScrFunc - 1, false);
  Canvas.Circle (x + 1, y + 1, 10, COLOR2RGB (clrBlack));
  Canvas.Circle (x + 1, y + 1, 11, COLOR2RGB (clrBlack));
  Canvas.Update ();
  Sleep (1000);

  int xConv = 0.0;
  int yConv = 0.0;

  int EpochCmidl = 0;
  int EpochCount = 0;

  double aveMid = 0.0;
  double aveEnd = 0.0;

  //----------------------------------------------------------------------------
  for (int test = 0; test < NumberRepetTest_P; test++)
  {
    InitAO (funcCount * 2, f.GetMaxArg (), f.GetMinArg (), ArgumentStep_P);

    EpochCmidl = Measur1FuncValue_P / (ArraySize (AO.S_Colony));
    EpochCount = Measur2FuncValue_P / (ArraySize (AO.S_Colony));

    // Optimization-------------------------------------------------------------
    AO.F_EpochReset ();


    for (int epochCNT = 1; epochCNT <= EpochCount && !IsStopped (); epochCNT++)
    {
      AO.F_Preparation ();

      for (int set = 0; set < ArraySize (AO.S_Colony); set++)
      {
        AO.A_FFcol [set] = f.CalcFunc (AO.S_Colony [set].args, funcCount);
      }

      AO.F_Sorting ();

      if (epochCNT == EpochCmidl) aveMid += AO.A_FFpop [0];

      SendGraphToCanvas  (1, 1);

      //draw a population on canvas
      for (int i = 0; i < ArraySize (AO.S_Population); i++)
      {
        if (i > 0) PointDr (AO.S_Population [i].args, f.GetMinArg (), f.GetMaxArg (), clrWhite, 1, 1, funcCount);
      }
      PointDr (AO.S_Population [0].args, f.GetMinArg (), f.GetMaxArg (), clrBlack, 1, 1, funcCount);

      Canvas.Circle (x + 1, y + 1, 10, COLOR2RGB (clrBlack));
      Canvas.Circle (x + 1, y + 1, 11, COLOR2RGB (clrBlack));

      xConv = (int)Scale (epochCNT,       1,          EpochCount, 2, WidthScrFunc - 2, false);
      yConv = (int)Scale (AO.A_FFpop [0], minFuncVal, maxFuncVal, 1, HeighScrFunc - 2, true);

      Canvas.FillCircle (xConv + HeighMonitor + 1, yConv + 1, 1, COLOR2RGB (clrConv));

      Canvas.Update ();
      Sleep (RenderSleepMsc_P);
    }

    aveEnd += AO.A_FFpop [0];

    Sleep (1000);
  }

  aveMid /= (double)NumberRepetTest_P;
  aveEnd /= (double)NumberRepetTest_P;

  double score1 = Scale (aveMid, minFuncVal, maxFuncVal, 0.0, 1.0, false);
  double score2 = Scale (aveEnd, minFuncVal, maxFuncVal, 0.0, 1.0, false);
  
  ScoreAll += score1 + score2;

  Print (funcCount, " ", f.GetNamFun (), "'s; Func runs ", Measur1FuncValue_P, " result: ", aveMid, "; Func runs ", Measur2FuncValue_P, " result: ", aveEnd);
  Print ("Score1: ", DoubleToString (score1, 5), "; Score2: ", DoubleToString (score2, 5));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void InitAO (const int    params,  //amount of the optimized arguments
             const double max,     //maximum of the optimized argument
             const double min,     //minimum of the optimized argument
             const double step)    //step of the optimized argument
{
  AO.F_Init (params, Population_P);
  for (int idx = 0; idx < params; idx++)
  {
    AO.A_RangeMax  [idx] = max;
    AO.A_RangeMin  [idx] = min;
    AO.A_RangeStep [idx] = step;
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void PointDr (double &args [], double Min, double Max, color clr, int shiftX, int shiftY, int count)
{
  double x = 0.0;
  double y = 0.0;
  
  double xAve = 0.0;
  double yAve = 0.0;
  
  int width  = 0;
  int height = 0;
  
  color clrF = clrNONE;
  
  for (int i = 0; i < count; i++)
  {
    xAve += args [i * 2];
    yAve += args [i * 2 + 1];
       
    x = args [i * 2];
    y = args [i * 2 + 1];
    
    width  = (int)Scale (x, Min, Max, 0, WidthScrFunc - 1, false);
    height = (int)Scale (y, Min, Max, 0, HeighScrFunc - 1, false);
    
    clrF = DoubleToColor (i, 0, count - 1, 0, 360);
    Canvas.FillCircle (width + shiftX, height + shiftY, 1, COLOR2RGB (clrF));
  }
  
  xAve /= (double)count;
  yAve /= (double)count;

  width  = (int)Scale (xAve, Min, Max, 0, WidthScrFunc - 1, false);
  height = (int)Scale (yAve, Min, Max, 0, HeighScrFunc - 1, false);

  Canvas.FillCircle (width + shiftX, height + shiftY, 3, COLOR2RGB (clrBlack));
  Canvas.FillCircle (width + shiftX, height + shiftY, 2, COLOR2RGB (clr));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void SendGraphToCanvas (int shiftX, int shiftY)
{
  for (int w = 0; w < HeighScrFunc; w++)
  {
    for (int h = 0; h < HeighScrFunc; h++)
    {
      Canvas.PixelSet (w + shiftX, h + shiftY, COLOR2RGB (FunctScrin [w].clr [h]));
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void DrawFunctionGraph (double     min,
                        double     max,
                        double     fMin,
                        double     fMax,
                        C_Function &f)
{
  double ar [2];
  double fV;

  for (int w = 0; w < HeighScrFunc; w++)
  {
    ar [0] = Scale (w, 0, HeighScrFunc, min, max, false);
    for (int h = 0; h < HeighScrFunc; h++)
    {
      ar [1] = Scale (h, 0, HeighScrFunc, min, max, false);
      fV = f.CalcFunc (ar, 1);
      FunctScrin [w].clr [h] = DoubleToColor (fV, fMin, fMax, 0, 250);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Scaling a number from a range to a specified range
double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool Revers = false)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return ((OutMIN + OutMAX) / 2.0);
  else
  {
    if (Revers)
    {
      if (In < InMIN) return (OutMAX);
      if (In > InMAX) return (OutMIN);
      return (((InMAX - In) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
    }
    else
    {
      if (In < InMIN) return (OutMIN);
      if (In > InMAX) return (OutMAX);
      return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
color DoubleToColor (const double in,    //input value
                     const double inMin, //minimum of input values
                     const double inMax, //maximum of input values
                     const int    loH,   //lower bound of HSL range values
                     const int    upH)   //upper bound of HSL range values
{
  int h = (int)Scale (in, inMin, inMax, loH, upH, true);
  return HSLtoRGB (h, 1.0, 0.5);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
color HSLtoRGB (const int    h, //0   ... 360
                const double s, //0.0 ... 1.0
                const double l) //0.0 ... 1.0
{
  int r;
  int g;
  int b;
  if (s == 0.0)
  {
    r = g = b = (unsigned char)(l * 255);
    return StringToColor ((string)r + "," + (string)g + "," + (string)b);
  }
  else
  {
    double v1, v2;
    double hue = (double)h / 360.0;
    v2 = (l < 0.5) ? (l * (1.0 + s)) : ((l + s) - (l * s));
    v1 = 2.0 * l - v2;
    r = (unsigned char)(255 * HueToRGB (v1, v2, hue + (1.0 / 3.0)));
    g = (unsigned char)(255 * HueToRGB (v1, v2, hue));
    b = (unsigned char)(255 * HueToRGB (v1, v2, hue - (1.0 / 3.0)));
    return StringToColor ((string)r + "," + (string)g + "," + (string)b);
  }
}
//——————————————————————————————————————————————————————————————————————————————
//——————————————————————————————————————————————————————————————————————————————
double HueToRGB (double v1, double v2, double vH)
{
  if (vH < 0) vH += 1;
  if (vH > 1) vH -= 1;
  if ((6 * vH) < 1) return (v1 + (v2 - v1) * 6 * vH);
  if ((2 * vH) < 1) return v2;
  if ((3 * vH) < 2) return (v1 + (v2 - v1) * ((2.0f / 3) - vH) * 6);
  return v1;
}
//——————————————————————————————————————————————————————————————————————————————

Para converter um número do tipo double de um intervalo para uma cor, foi usado o algoritmo de conversão de HSL para RGB (o sistema de cores da MetaTrader 5).

A unidade de teste exibe uma imagem no gráfico. Ele está dividido ao meio.

A função de teste é exibida no lado esquerdo. Seu gráfico tridimensional é projetado em um plano, onde o vermelho significa o máximo, enquanto o azul significa o mínimo. Ele exibe a posição dos pontos na população (a cor corresponde ao número ordinal da função de teste com o número de variáveis 40 e 1000, a coloração não é realizada para uma função com duas variáveis), os pontos cujas coordenadas são calculadas são marcados em branco, enquanto o melhor é marcado em preto.
O gráfico de convergência é exibido no lado direito, os testes com 2 variáveis são marcados em verde, os testes com 40 variáveis são azuis e os testes com 1000 variáveis são vermelhos. Cada um dos testes é realizado cinco vezes (5 gráficos de convergência de cada cor). Aqui nós podemos observar o quanto a convergência do OA se deteriora com o aumento do número de variáveis.

6. OA simples usando RNG

Vamos implementar a estratégia de busca mais simples como um teste de exemplo. Ele não tem valor prático, mas será de alguma forma um padrão para comparar os algoritmos de otimização. A estratégia gera um novo conjunto de variáveis de função em uma escolha aleatória 50/50: copiamos a variável de um conjunto pai selecionado aleatoriamente da população ou geramos uma variável do intervalo mínimo/máximo. Depois de receber os valores das funções de teste, o novo conjunto de variáveis resultante é copiado para a segunda metade da população e é ordenado. Assim, novos conjuntos substituem constantemente metade da população, enquanto os melhores conjuntos se concentram na outra.

Abaixo está um código do OA baseado em RNG:

//+————————————————————————————————————————————————————————————————————————————+
class C_AO_RND
{
  public: //||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||

  struct ArrColony
  {
      double args [];
  };

  //----------------------------------------------------------------------------
  double    A_RangeStep []; //Step ranges of genes
  double    A_RangeMin  []; //Min ranges of genes
  double    A_RangeMax  []; //Max ranges of genes

  ArrColony S_Population []; //Population
  ArrColony S_Colony     []; //Colony

  double    A_FFpop [];      //Values of fitness of individuals in population
  double    A_FFcol [];      //Values of fitness of individuals in colony

  //----------------------------------------------------------------------------
  // Initialization of algorithm
  void F_Init (int argCount,       //Number of arguments

               int populationSize) //Population size
  {
    MathSrand ((int)GetMicrosecondCount ()); //reset of the generator

    p_argCount  = argCount;
    p_sizeOfPop = populationSize;
    p_sizeOfCol = populationSize / 2;

    p_dwelling  = false;

    f_arrayInitResize (A_RangeStep, argCount, 0.0);
    f_arrayInitResize (A_RangeMin,  argCount, 0.0);
    f_arrayInitResize (A_RangeMax,  argCount, 0.0);

    ArrayResize (S_Population, p_sizeOfPop);
    ArrayResize (s_populTemp, p_sizeOfPop);
    for (int i = 0; i < p_sizeOfPop; i++)
    {
      f_arrayInitResize (S_Population [i].args, argCount, 0.0);
      f_arrayInitResize (s_populTemp [i].args, argCount, 0.0);
    }

    ArrayResize (S_Colony, p_sizeOfCol);
    for (int i = 0; i < p_sizeOfCol; i++)
    {
      f_arrayInitResize (S_Colony [i].args, argCount, 0.0);
    }

    f_arrayInitResize (A_FFpop, p_sizeOfPop, -DBL_MAX);
    f_arrayInitResize (A_FFcol, p_sizeOfCol, -DBL_MAX);

    f_arrayInitResize (a_indexes, p_sizeOfPop, 0);
    f_arrayInitResize (a_valueOnIndexes, p_sizeOfPop, 0.0);
  }

  //----------------------------------------------------------------------------
  void F_EpochReset ()   //Reset of epoch, allows to begin evolution again without initial initialization of variables
  {
    p_dwelling = false;
    ArrayInitialize (A_FFpop, -DBL_MAX);
    ArrayInitialize (A_FFcol, -DBL_MAX);
  }
  //----------------------------------------------------------------------------
  void F_Preparation ();  //Preparation
  //----------------------------------------------------------------------------
  void F_Sorting ();      //The settling of a colony in population and the subsequent sorting of population

  private: //|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
  //----------------------------------------------------------------------------
  void F_PopulSorting ();

  //----------------------------------------------------------------------------
  ArrColony          s_populTemp      []; //Temporal population
  int                a_indexes        []; //Indexes of chromosomes
  double             a_valueOnIndexes []; //VFF of the appropriate indexes of chromosomes

  //----------------------------------------------------------------------------
  template <typename T1>
  void f_arrayInitResize (T1 &arr [], const int size, const T1 value)
  {
    ArrayResize     (arr, size);
    ArrayInitialize (arr, value);
  }

  //----------------------------------------------------------------------------
  double f_seInDiSp         (double In, double InMin, double InMax, double step);
  double f_RNDfromCI        (double min, double max);
  double f_scale            (double In, double InMIN, double InMAX, double OutMIN, double OutMAX);

  //---Constants----------------------------------------------------------------
  int  p_argCount;   //Quantity of arguments in a set of arguments
  int  p_sizeOfCol;  //Quantity of set in a colony
  int  p_sizeOfPop;  //Quantity of set in population
  bool p_dwelling;   //Flag of the first settling of a colony in population
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void C_AO_RND::F_Preparation ()
{
  //if starts of algorithm weren't yet - generate a colony with random arguments
  if (!p_dwelling)
  {
    for (int person = 0; person < p_sizeOfCol; person++)
    {
      for (int arg = 0; arg < p_argCount; arg++)
      {
        S_Colony [person].args [arg] = f_seInDiSp (f_RNDfromCI (A_RangeMin [arg], A_RangeMax [arg]),
                                                    A_RangeMin  [arg],
                                                    A_RangeMax  [arg],
                                                    A_RangeStep [arg]);
      }
    }

    p_dwelling = true;
  }
  //generation of a colony using with copying arguments from parent sets--------
  else
  {
    int parentAdress = 0;
    double rnd       = 0.0;
    double argVal    = 0.0;

    for (int setArg = 0; setArg < p_sizeOfCol; setArg++)
    {
      //get a random address of the parent set
      parentAdress = (int)f_RNDfromCI (0, p_sizeOfPop - 1);

      for (int arg = 0; arg < p_argCount; arg++)
      {
        if (A_RangeMin [arg] == A_RangeMax [arg]) continue;

        rnd = f_RNDfromCI (0.0, 1.0);

        if (rnd < 0.5)
        {
          S_Colony [setArg].args [arg] = S_Population [parentAdress].args [arg];
        }
        else
        {
          argVal = f_RNDfromCI (A_RangeMin [arg], A_RangeMax [arg]);
          argVal = f_seInDiSp (argVal, A_RangeMin [arg], A_RangeMax [arg], A_RangeStep [arg]);

          S_Colony [setArg].args [arg] = argVal;
        }
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void C_AO_RND::F_Sorting ()
{
  for (int person = 0; person < p_sizeOfCol; person++)
  {
    ArrayCopy (S_Population [person + p_sizeOfCol].args, S_Colony [person].args, 0, 0, WHOLE_ARRAY);
  }
  ArrayCopy (A_FFpop, A_FFcol, p_sizeOfCol, 0, WHOLE_ARRAY);

  F_PopulSorting ();
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Ranging of population.
void C_AO_RND::F_PopulSorting ()
{
  //----------------------------------------------------------------------------
  int   cnt = 1, i = 0, u = 0;
  int   t0 = 0;
  double t1 = 0.0;
  //----------------------------------------------------------------------------

  // We will put indexes in the temporary array
  for (i = 0; i < p_sizeOfPop; i++)
  {
    a_indexes [i] = i;
    a_valueOnIndexes [i] = A_FFpop [i];
  }
  while (cnt > 0)
  {
    cnt = 0;
    for (i = 0; i < p_sizeOfPop - 1; i++)
    {
      if (a_valueOnIndexes [i] < a_valueOnIndexes [i + 1])
      {
        //-----------------------
        t0 = a_indexes [i + 1];
        t1 = a_valueOnIndexes [i + 1];
        a_indexes [i + 1] = a_indexes [i];
        a_valueOnIndexes [i + 1] = a_valueOnIndexes [i];
        a_indexes [i] = t0;
        a_valueOnIndexes [i] = t1;
        //-----------------------
        cnt++;
      }
    }
  }

  // On the received indexes create the sorted temporary population
  for (u = 0; u < p_sizeOfPop; u++) ArrayCopy (s_populTemp [u].args, S_Population [a_indexes [u]].args, 0, 0, WHOLE_ARRAY);

  // Copy the sorted array back
  for (u = 0; u < p_sizeOfPop; u++) ArrayCopy (S_Population [u].args, s_populTemp [u].args, 0, 0, WHOLE_ARRAY);

  ArrayCopy (A_FFpop, a_valueOnIndexes, 0, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Choice in discrete space
double C_AO_RND::f_seInDiSp (double in, double inMin, double inMax, double step)
{
  if (in <= inMin) return (inMin);
  if (in >= inMax) return (inMax);
  if (step == 0.0) return (in);
  else return (inMin + step * (double)MathRound ((in - inMin) / step));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Random number generator in the custom interval.
double C_AO_RND::f_RNDfromCI (double min, double max)
{
  if (min == max) return (min);
  double Min, Max;
  if (min > max)
  {
    Min = max;
    Max = min;
  }
  else
  {
    Min = min;
    Max = max;
  }
  return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0)));
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
double C_AO_RND::f_scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
  else
  {
    if (In < InMIN) return (OutMIN);
    if (In > InMAX) return (OutMAX);
    return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
  }
}
//——————————————————————————————————————————————————————————————————————————————

7. Resultados

AO	Execuções	Skin			Forest			Megacity (discreto)			Resultado final
AO	Execuções	2 parâmetros (1 F)	40 parâmetros (20 F)	1000 parâmetros (500 F)	2 parâmetros (1 F)	40 parâmetros (20 F)	1000 parâmetros (500 F)	2 parâmetros (1 F)	40 parâmetros (20 F)	1000 parâmetros (500 F)	Resultado final
RND	1000	0.98744	0.61852	0.49408	0.89582	0.19645	0.14042	0.77333	0.19000	0.14283	0.51254
RND	10,000	0.99977	0.69448	0.50188	0.98181	0.24433	0.14042	0.88000	0.20133	0.14283	0.51254

Após o teste na bateria de testes, os resultados do RND OA revelaram-se bastante inesperados. O algoritmo é capaz de encontrar o ótimo das funções de duas variáveis com precisão muito alta, enquanto no caso da Forest e Megacity, os resultados são visivelmente piores. Por outro lado, minhas suposições sobre as propriedades de busca fracas para as funções com muitas variáveis foram confirmadas. Os resultados já são muito medíocres com 40 argumentos. O valor cumulativo final é 0.51254.

Nos próximos artigos, eu analisarei e testarei os algoritmos de otimização conhecidos e amplamente utilizados e eu continuarei preenchendo a tabela de resultados que compõe a classificação do OA.

Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/8122

Arquivos anexados |

Baixar como ZIP

MQL5.zip (9.71 KB)

Aviso: Todos os direitos sobre esses materiais pertencem à MetaQuotes Ltd. É proibida a reimpressão total ou parcial.

Outros artigos do autor

Ir para discussão

Como desenvolver um sistema de negociação baseado no indicador DeMarker

Aqui está um novo artigo em nossa série sobre como desenvolver um sistema de negociação pelos indicadores técnicos mais populares. Neste artigo, nós apresentaremos como criar um sistema de negociação pelo indicador DeMarker.

Como desenvolver um sistema de negociação baseado no indicador VIDYA

Bem-vindo a um novo artigo da nossa série sobre como desenvolver um sistema de negociação pelos indicadores técnicos mais populares, neste artigo aprenderemos sobre uma nova ferramenta técnica e aprenderemos como desenvolver um sistema de negociação pelo Variable Index Dynamic Average (VIDYA).

Redes neurais de maneira fácil (Parte 28): algoritmo de gradiente de política

Continuamos a estudar métodos de aprendizado por reforço. No artigo anterior, nos iniciamos no método de aprendizado Q profundo. Com ele, treinamos um modelo para prever a recompensa imediata dependendo da ação tomada por nós em uma determinada situação. E, em seguida, realizamos uma ação de acordo com nossa política e a recompensa esperada. Mas nem sempre é possível aproximar a função Q ou nem sempre sua aproximação dá o resultado desejado. Nesses casos, os métodos de aproximação são usados não para funções de utilidade, mas, sim, para uma política (estratégia) direta de ações. E é precisamente a esses métodos que o gradiente de política pertence.

Crie o seu próprio Indicador técnico

Neste artigo, eu abordarei os algoritmos que permitem que você crie o seu próprio indicador técnico. Você aprenderá como obter resultados bem complexos e interessantes com suposições iniciais muito simples.