MetaTrader 5 / Exemplos
English Русский 中文 Español Deutsch 日本語
preview
Algoritmos de otimização populacionais: Algoritmo de pesquisa gravitacional (GSA)

Algoritmos de otimização populacionais: Algoritmo de pesquisa gravitacional (GSA)

MetaTrader 5 — Exemplos | 31 maio 2023, 09:47
153 0
Andrey Dik
Andrey Dik

Conteúdo

1. Introdução
2. Descrição do algoritmo
3. Resultado dos testes


1. Introdução

O algoritmo de busca gravitacional (GSA) foi proposto por E. Rashedi inicialmente para resolver problemas de otimização, especialmente para problemas não lineares, seguindo os princípios da lei da gravidade de Newton. No algoritmo proposto, as partículas são consideradas como objetos, e seu desempenho é avaliado com base em suas massas. A gravidade é a tendência das massas de acelerar umas em direção às outras. É uma das quatro interações fundamentais na natureza (as outras são: interação eletromagnética, interação nuclear fraca e interação nuclear forte).

Cada partícula no universo atrai qualquer outra partícula. A gravidade existe em todos os lugares.  Embora seja a força mais fraca, é a mais visível. Devido ao trabalho da força gravitacional, as pessoas podem caminhar na Terra, e os planetas podem girar em órbita ao redor do Sol. A força da gravidade de qualquer objeto é proporcional à sua massa. Assim, objetos com mais massa têm mais gravidade. A inevitabilidade da gravidade a distingue de todas as outras forças da natureza. O comportamento da força gravitacional de Newton é chamado de ação à distância. Este é um princípio físico geral, derivado de observações empíricas com o que Isaac Newton chamou de raciocínio indutivo. É parte da mecânica clássica, formulada no trabalho de Newton "Philosophiae Naturalis Principia Mathematica" ("Princípios"), publicado pela primeira vez em 5 de julho de 1687.

Quando, em abril de 1686, Newton apresentou ao Royal Society o primeiro livro do texto ainda não publicado, Robert Hooke afirmou que Newton havia obtido dele a lei dos quadrados inversos. Falando em termos modernos, a lei afirma que cada massa pontual atrai qualquer outra massa pontual com uma força que atua ao longo da linha que intersecta os dois pontos.


2. Descrição do algoritmo

Neste artigo, apresenta-se um algoritmo de otimização baseado na lei da gravidade de Newton: "Cada partícula no Universo atrai qualquer outra partícula com uma força diretamente proporcional ao produto de suas massas e inversamente proporcional ao quadrado da distância entre elas". No algoritmo proposto, os agentes de busca são representados como um conjunto de massas que interagem entre si com base na gravidade newtoniana e nas leis do movimento. Além disso, todos os agentes podem trocar informações entre si, independentemente de sua localização no espaço de busca, por meio de uma força atrativa que depende da massa (calculada a partir dos valores da função objetivo) e da distância entre eles.

Os agentes são considerados como objetos e sua capacidade de adaptação é medida por suas massas. Em sua forma geral (quando as configurações do algoritmo se aproximam das leis físicas reais), todos esses objetos são atraídos uns pelos outros por uma força gravitacional, e essa força provoca um movimento global de todos os objetos em direção aos objetos com maior massa. Portanto, as massas interagem usando uma forma direta de conexão, através da força gravitacional.

No GSA clássico, cada partícula possui três tipos de massa:

a) massa ativa
b) massa passiva
c) massa inerte

Na maioria dos casos, é conveniente e adequado igualar esses conceitos do ponto de vista da simplificação do código e dos cálculos, bem como da eficiência das capacidades de busca do algoritmo. Portanto, no algoritmo, usaremos apenas uma massa, em vez de três.


fórmulas

Figura 1. Força gravitacional, aceleração e velocidade.



A posição das partículas fornece a solução do problema, enquanto a função de adaptação é usada para calcular as massas. O algoritmo possui duas etapas: reconhecimento e exploração. Esse algoritmo utiliza as capacidades de reconhecimento no início para evitar o problema de ficar preso em um ótimo local e, em seguida, explora as áreas de extremos.

O algoritmo de busca gravitacional deve transformar uma partícula em movimento no espaço em um objeto com uma massa específica. Esses objetos são atraídos uns pelos outros devido à interação gravitacional e cada partícula no espaço será atraída pela ação mútua das partículas, criando acelerações. Cada partícula é atraída por outras partículas e se move na direção da força atuante. Pode-se dizer que as partículas de massa menor se movem em direção às partículas de massa maior, mas objetos maciços também se movem, porém com velocidades inversamente proporcionais à massa. As soluções ótimas são encontradas pelos objetos "grandes", que refinam a solução movendo-se em velocidades mais baixas em comparação aos objetos "menores", que se movem mais rapidamente. O GSA implementa a transferência de informações por meio da interação entre objetos.

Passos para o GSA:

1. Inicialização dos agentes
2. Evolução da função de adaptação
3. Cálculo da constante gravitacional
4. Cálculo das massas dos agentes


1. Inicialização dos agentes.
Todos os agentes são inicializados aleatoriamente. Cada agente é considerado uma solução candidata. Para que a análise de estabilidade seja significativa e confiável, é extremamente importante estabelecer condições iniciais equilibradas. Afinal, se o "disco" de objetos inicial não estiver em equilíbrio, seu relaxamento nos primeiros passos de tempo da simulação pode causar instabilidades que são de pouca importância para nossa compreensão da estabilidade de "discos galácticos". Infelizmente, não se conhece uma solução analítica para a densidade, campo de velocidades e temperatura de um disco gasoso tridimensional em equilíbrio hidrostático no potencial externo de um halo de matéria escura e/ou disco estelar.

2. Evolução da função de adaptação.
A confiabilidade e eficácia do GSA dependem do equilíbrio entre as capacidades de reconhecimento e exploração. Nas iterações iniciais do processo de busca da solução, a preferência é dada ao reconhecimento do espaço de busca. Isso pode ser alcançado permitindo que os agentes usem um passo grande nas iterações iniciais. Nas iterações mais tardias, é necessário refinar o espaço de busca para evitar a situação de perder os ótimos globais. Assim, as soluções candidatas devem ter passos menores para serem usadas nas iterações subsequentes.

3. Cálculo da constante gravitacional.
A constante gravitacional (também conhecida como "constante gravitacional universal", "constante gravitacional de Newton" ou "constante gravitacional de Cavendish"), denotada pela letra G, é uma constante física empírica envolvida no cálculo dos efeitos gravitacionais na lei da gravitação universal de Isaac Newton e na teoria geral da relatividade de Albert Einstein. Na lei de Newton, é a constante de proporcionalidade que liga a força gravitacional entre dois corpos ao produto de suas massas e ao inverso do quadrado de sua distância. Nas equações de campo de Einstein, quantitativamente define a relação entre a geometria do espaço-tempo e o tensor energia-momento.

4. Cálculo das massas dos agentes.
A massa é a quantidade de matéria presente no espaço.

Pseudocódigo do algoritmo:

1. Gerar o sistema de objetos de forma aleatória.
2. Determinar a adaptação de cada objeto.
3. Atualizar os valores da constante gravitacional, calcular as massas, o melhor e o pior objeto.
4. Calcular as forças atuantes em cada coordenada.
5. Calcular as acelerações e velocidades dos objetos.
6. Atualizar as posições dos objetos.
7. Determinar a adaptação de cada objeto.
8. Repetir a partir do passo 3 até que o critério de parada seja atingido.

Vamos considerar o código do GSA. Para descrever um objeto no sistema de interação gravitacional, precisaremos de uma estrutura chamada S_Object, que irá descrever todas as propriedades físicas necessárias do objeto para realizar a busca gravitacional: c[] - coordenadas no espaço de busca, v[] - vetor de velocidades em cada coordenada (o tamanho do vetor é igual ao número de coordenadas), M - massa do objeto (no GSA, a massa é uma medida relativa que representa um valor calculado com base nos valores máximos e mínimos de adaptação em todo o sistema de objetos), f - valor da função de adaptação, R[] - distância euclidiana para outros objetos (o tamanho do vetor é igual ao número de objetos), F[] - vetor de forças em cada coordenada (o tamanho do vetor é igual ao número de coordenadas). 

//——————————————————————————————————————————————————————————————————————————————
struct S_Object
{
  double c  [];   //coordinates
  double v  [];   //velocity
  double M;       //mass
  double f;       //fitness
  double R  [];   //euclidean distance to other objects
  double F  [];   //force vector
};
//——————————————————————————————————————————————————————————————————————————————

Vamos declarar a classe do algoritmo de busca gravitacional C_AO_GSA. Das propriedades físicas dos objetos que atuam como agentes no algoritmo, só precisamos de uma: as coordenadas que representam a melhor solução - o valor fB. Na classe, definimos os intervalos aceitáveis das coordenadas do espaço de busca e o passo. Representaremos o sistema de objetos interligados gravitacionalmente como um array da estrutura S_Object. No algoritmo clássico, existem apenas três parâmetros externos: G_constant, a_constant, e_constant, que definem as propriedades da interação gravitacional dos objetos, e as demais constantes estão incorporadas nas fórmulas de cálculo, mas achei apropriado trazer essas constantes para os parâmetros externos do algoritmo, permitindo uma regulagem mais flexível das propriedades do algoritmo como um todo. Analisaremos todos os parâmetros mais tarde, pois eles influenciam bastante o comportamento do algoritmo. 

//——————————————————————————————————————————————————————————————————————————————
class C_AO_GSA
{
  //----------------------------------------------------------------------------
  public: S_Object o       []; //object
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates

  public: void Init (const int    coordinatesNumberP, //coordinates number
                     const int    objectsNumberP,     //objects number
                     const double PowerOfdistanceP,   //power of distance
                     const double GraviPert_MinP,     //gravitational perturbation Min
                     const double GraviPert_MaxP,     //gravitational perturbation Min
                     const double VelocityPert_MinP,  //Velocity perturbation Min
                     const double VelocityPert_MaxP,  //Velocity perturbation Max
                     const double G_constantP,        //G constant
                     const double a_constantP,        //a constant
                     const double e_constantP,        //e constant
                     const int    maxIterationsP);    //max Iterations

  public: void Moving   (int iter);
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber; //coordinates number
  private: int    objectsNumber;     //objects number
  private: double PowerOfdistance;   //power of distance
  private: double GraviPert_Min;     //gravitational perturbation Min
  private: double GraviPert_Max;     //gravitational perturbation Min
  private: double VelocPert_Min;     //velocity perturbation Min
  private: double VelocPert_Max;     //velocity perturbation Max
  private: double G_constant;        //G constant
  private: double a_constant;        //a constant
  private: double e_constant;        //e constant
  private: int    maxIterations;
  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
  private: double Scale     (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

O método público do algoritmo Init() é projetado para transmitir os parâmetros externos do algoritmo para constantes internas, para inicializar as variáveis de serviço e definir os tamanhos dos arrays.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GSA::Init (const int    coordinatesNumberP, //coordinates number
                     const int    objectsNumberP,     //objects number
                     const double PowerOfdistanceP,   //power of distance
                     const double GraviPert_MinP,     //gravitational perturbation Min
                     const double GraviPert_MaxP,     //gravitational perturbation Min
                     const double VelocityPert_MinP,  //Velocity perturbation Min
                     const double VelocityPert_MaxP,  //Velocity perturbation Max
                     const double G_constantP,        //G constant
                     const double a_constantP,        //a constant
                     const double e_constantP,        //e constant
                     const int    maxIterationsP)     //max Iterations
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber = coordinatesNumberP;
  objectsNumber     = objectsNumberP;
  PowerOfdistance   = PowerOfdistanceP;
  GraviPert_Min     = GraviPert_MinP;
  GraviPert_Max     = GraviPert_MaxP;
  VelocPert_Min     = VelocityPert_MinP;
  VelocPert_Max     = VelocityPert_MaxP;
  G_constant        = G_constantP;
  a_constant        = a_constantP;
  e_constant        = e_constantP;
  maxIterations     = maxIterationsP;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);

  ArrayResize (o,  objectsNumber);

  for (int i = 0; i < objectsNumber; i++)
  {
    ArrayResize (o [i].c,  coordinatesNumber);
    ArrayResize (o [i].v,  coordinatesNumber);
    ArrayResize (o [i].R,  objectsNumber);
    ArrayResize (o [i].F,  coordinatesNumber);
    o [i].f  = -DBL_MAX;
  }

  ArrayResize (cB, coordinatesNumber);
}
//——————————————————————————————————————————————————————————————————————————————

O primeiro método público, chamado a cada iteração, é o Moving(). Este método incorpora toda a física e lógica do algoritmo GSA, é bastante extenso, então vamos analisá-lo dividindo-o em partes. Note que o método recebe como parâmetro a iteração atual, que participa no cálculo da constante gravitacional, equilibrando o reconhecimento e a explotação.

Na primeira iteração, ocorre a fase de inicialização dos objetos. Atribuímos valores aleatórios a todas as coordenadas dos objetos dentro do intervalo aceitável com distribuição uniforme, verificamos se elas estão fora do intervalo. No início do processo de otimização, todos os objetos têm velocidade zero, ou seja, os objetos estão imóveis no espaço de busca em relação às coordenadas. Note que os objetos não têm massa, então eles deveriam se mover à velocidade da luz, mas vamos quebrar as leis da física para a primeira iteração, pois este momento é de certa forma equivalente ao Big Bang. A função de adaptação dos objetos neste momento é o menor valor possível para um número double. Ao depurar o algoritmo, tivemos problemas para encontrar bugs relacionados à massa zero, a solução você verá a seguir.

//----------------------------------------------------------------------------
if (!revision)
{
  fB = -DBL_MAX;

  for (int obj = 0; obj < objectsNumber; obj++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      o [obj].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      o [obj].c [c] = SeInDiSp (o [obj].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      o [obj].v [c] = 0.0;
      o [obj].M     = 0.0;
      o [obj].f     = -DBL_MAX;
    }
  }

  revision = true;
}

O restante do código do método Moving() se refere à segunda e às seguintes iterações, onde os objetos ganham massa, velocidade e aceleração.

Primeiro, é necessário calcular a massa, e como mencionado anteriormente, a massa (por definição, um valor escalar positivo) dos objetos é calculada a partir dos valores da função de adaptação, então é necessário determinar o valor mínimo e máximo de adaptação, e só então calcular a massa com base nestes valores. Neste ponto, na iteração anterior, já foi obtido o valor da função de adaptação.

//find the minimum and maximum fitness==========================================
for (int obj = 0; obj < objectsNumber; obj++)
{
  if (o [obj].f < Fmin) Fmin = o [obj].f;
  if (o [obj].f > Fmax) Fmax = o [obj].f;
}

Nesta parte do código, a massa é calculada pela fórmula Mo=(Fo-Fmin)/(Fmax-Fmin), onde:

  • Mo - massa do objeto
  • Fo - função de adaptação do objeto
  • Fmax - valor máximo da função de adaptação entre todos os objetos (melhor valor)
  • Fmin - valor mínimo da função de adaptação entre todos os objetos (pior valor)

Como vemos pela fórmula, a massa pode ter apenas valores positivos no intervalo de 0 a 1, inclusive. Como discutimos anteriormente que a massa não deve ser zero, caso contrário a velocidade seria igual à velocidade da luz, limitaremos o limite inferior da massa ao valor 0,1. O valor máximo pode ser igual a 1. Vale ressaltar que quando os valores mínimos e máximos da função de adaptação são iguais para todos os objetos, a massa será a mesma para todos e igual a 1. Isso corresponde ao caso em que o espaço de busca é homogêneo na região onde os objetos estão localizados e todos os objetos são iguais em termos da qualidade da função de adaptação, e também o movimento em qualquer direção tem a mesma prioridade. Pareceria que neste caso todos os objetos deveriam gradualmente se mover e se concentrar no centro de massa comum, mas isso não acontece devido à ação não linear da força gravitacional.

//calculating the mass of objects===========================================
for (int obj = 0; obj < objectsNumber; obj++)
{
  Fo = o [obj].f;
  if (Fmax == Fmin) Mo = 1.0;
  else Mo = (Fo - Fmin) / (Fmax - Fmin);
  o [obj].M = Scale (Mo, 0.0, 1.0, 0.1, 1.0, false);
}

Calculamos a massa para os objetos, agora precisamos calcular outro componente da fórmula R - a distância euclidiana de cada objeto para cada um. O cálculo envolve dois ciclos de iteração dos objetos e um ciclo de cálculo para cada coordenada. Como sabemos, a distância euclidiana é a raiz quadrada da soma dos quadrados das diferenças das coordenadas.

//calculation of Euclidean distances between all objects====================
for (int obj = 0; obj < objectsNumber; obj++) ArrayInitialize (o [obj].R, 0.0);

for (int obj = 0; obj < objectsNumber; obj++)
{
  for (int obj2 = 0; obj2 < objectsNumber; obj2++)
  {
    if (obj != obj2)
    {
      if (o [obj].R [obj2] == 0.0)
      {
        for (int c = 0; c < coordinatesNumber; c++)
        {
          diffDist = o [obj].c [c] - o [obj2].c [c];
          o [obj].R [obj2] += diffDist * diffDist;
        }

        o [obj].R [obj2] = sqrt (o [obj].R [obj2]);
        o [obj2].R [obj] = o [obj].R [obj2];
      }
    }
  }
}

Agora podemos calcular os vetores de força para os objetos. Para isso, precisaremos passar por todos os objetos em dois ciclos e um ciclo para as coordenadas, já que a velocidade é calculada separadamente para cada coordenada. Precisamos adicionar uma condição que exclua a coincidência dos índices dos objetos, para que um objeto não se inclua no cálculo das forças. Aqui usamos a conhecida fórmula de Newton para calcular a força gravitacional entre dois objetos (Figura 1) com a correção da distância pelo coeficiente e_constant. Primeiramente, faremos o cálculo da constante gravitacional G, que deve mudar em cada iteração para diminuir, supondo-se que intensifique a otimização do algoritmo.

//calculate the force vector for each object================================
for (int obj = 0; obj < objectsNumber; obj++) ArrayInitialize (o [obj].F, 0.0);

double G = G_constant * exp (-a_constant * (iter / maxIterations));

for (int obj = 0; obj < objectsNumber; obj++)
{
  for (int obj2 = 0; obj2 < objectsNumber; obj2++)
  {
    if (obj != obj2)
    {
      for (int c = 0; c < coordinatesNumber; c++)
      {
        diffDist = o [obj2].c [c] - o [obj].c [c];

        if (o [obj].R [obj2] != 0.0)
        {
          o [obj] .F [c] += G * o [obj].M * o [obj2].M * diffDist / (pow (o [obj].R [obj2], PowerOfdistance) + e_constant);
        }
      }
    }
  }
}

Para que os objetos comecem a se mover, resta calcular a velocidade. Pela fórmula na Figura 1, vemos que a aceleração participa no cálculo da velocidade, e a aceleração é igual à força que atua no corpo dividida pela massa. A fórmula também inclui o tempo V=V0+a*t, no nosso algoritmo, o papel do tempo é desempenhado pela iteração, de modo que a mudança na velocidade é apenas a mudança na velocidade em uma iteração. O vetor de velocidades já foi calculado acima, só resta dividir pela massa, além disso, os autores introduzem uma perturbação na força e na velocidade. A perturbação é um número aleatório uniformemente distribuído de 0 a 1. Isso adiciona um componente aleatório ao movimento dos objetos, sem o qual, o movimento seria estritamente determinado e dependeria apenas da posição inicial dos corpos. Achei sensato trazer os indicadores de perturbação para os parâmetros externos do algoritmo, o que permitirá regular o movimento dos objetos de totalmente determinado para totalmente aleatório.

//calculation of acceleration and velocity for all objects==================
double a = 0.0; //acceleration

for (int obj = 0; obj < objectsNumber; obj++)
{
  for (int c = 0; c < coordinatesNumber; c++)
  {
    r = RNDfromCI (GraviPert_Min, GraviPert_Max);
    a = o [obj].F [c] * r / o [obj].M;
    r = RNDfromCI (GraviPert_Min, GraviPert_Max);
    o [obj].v [c] = o [obj].v [c] * r + a;
    o [obj].c [c] = o [obj].c [c] + o [obj].v [c];

    if (o [obj].c [c] > rangeMax [c]) o [obj].c [c] = rangeMin [c];
    if (o [obj].c [c] < rangeMin [c]) o [obj].c [c] = rangeMax [c];

    o [obj].c [c] = SeInDiSp (o [obj].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}

O segundo método obrigatório para ser executado em cada iteração é o Revision(). Este método é projetado para determinar o melhor valor de função de adaptação na iteração atual. Em um loop, vamos percorrer todos os objetos e substituir a melhor solução global. 

//——————————————————————————————————————————————————————————————————————————————
void C_AO_GSA::Revision ()
{
  for (int s = 0; s < objectsNumber; s++)
  {
    if (o [s].f > fB)
    {
      fB = o [s].f;
      ArrayCopy (cB, o [s].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————


3. Resultado dos testes

Vamos aos resultados do teste. Saída dos resultados da bancada de teste com os melhores parâmetros GSA que pude encontrar:

2023.02.03 14:12:43.440    Test_AO_GSA (EURUSD,M1)    C_AO_GSA:10;2.0;0.2;0.6;0.0;1.0;2.0;20.0;0.01
2023.02.03 14:12:43.440    Test_AO_GSA (EURUSD,M1)    =============================
2023.02.03 14:12:52.198    Test_AO_GSA (EURUSD,M1)    5 Rastrigin's; Func runs 10000 result: 73.64619475145881
2023.02.03 14:12:52.198    Test_AO_GSA (EURUSD,M1)    Score: 0.91252
2023.02.03 14:13:06.105    Test_AO_GSA (EURUSD,M1)    25 Rastrigin's; Func runs 10000 result: 59.4327218024363
2023.02.03 14:13:06.105    Test_AO_GSA (EURUSD,M1)    Score: 0.73640
2023.02.03 14:14:16.529    Test_AO_GSA (EURUSD,M1)    500 Rastrigin's; Func runs 10000 result: 37.550565227034724
2023.02.03 14:14:16.529    Test_AO_GSA (EURUSD,M1)    Score: 0.46527
2023.02.03 14:14:16.529    Test_AO_GSA (EURUSD,M1)    =============================
2023.02.03 14:14:30.577    Test_AO_GSA (EURUSD,M1)    5 Forest's; Func runs 10000 result: 0.741456333008312
2023.02.03 14:14:30.577    Test_AO_GSA (EURUSD,M1)    Score: 0.41941
2023.02.03 14:14:50.281    Test_AO_GSA (EURUSD,M1)    25 Forest's; Func runs 10000 result: 0.46894018717768426
2023.02.03 14:14:50.282    Test_AO_GSA (EURUSD,M1)    Score: 0.26526
2023.02.03 14:16:01.856    Test_AO_GSA (EURUSD,M1)    500 Forest's; Func runs 10000 result: 0.11382493516764165
2023.02.03 14:16:01.856    Test_AO_GSA (EURUSD,M1)    Score: 0.06439
2023.02.03 14:16:01.856    Test_AO_GSA (EURUSD,M1)    =============================
2023.02.03 14:16:18.195    Test_AO_GSA (EURUSD,M1)    5 Megacity's; Func runs 10000 result: 5.279999999999999
2023.02.03 14:16:18.195    Test_AO_GSA (EURUSD,M1)    Score: 0.44000
2023.02.03 14:16:34.536    Test_AO_GSA (EURUSD,M1)    25 Megacity's; Func runs 10000 result: 2.296
2023.02.03 14:16:34.536    Test_AO_GSA (EURUSD,M1)    Score: 0.19133
2023.02.03 14:17:46.887    Test_AO_GSA (EURUSD,M1)    500 Megacity's; Func runs 10000 result: 0.23399999999999999
2023.02.03 14:17:46.887    Test_AO_GSA (EURUSD,M1)    Score: 0.01950

Parâmetros do algoritmo:

input double PowerOfdistance_P  = 2.0;   //Power of distance
input double GraviPert_Min_P    = 0.2;   //Gravitational perturbation Min
input double GraviPert_Max_P    = 0.6;   //Gravitational perturbation Max
input double VelocityPert_Min_P = 0.0;   //Velocity perturbation Min
input double VelocityPert_Max_P = 1.0;   //Velocity perturbation Max
input double G_constant_P       = 2.0;   //G constant
input double a_constant_P       = 20.0;  //a constant
input double e_constant_P       = 0.01;  //e constant

PowerOfdistance_P - é o expoente ao qual a distância entre os objetos é elevada, influenciando na formação de objetos gravitacionalmente ligados. Quanto maior o expoente na fórmula, menor é a influência que os objetos têm sobre outros objetos.

  • GraviPert_Min_P - limite inferior da faixa de perturbação gravitacional.
  • GraviPert_Max_P - limite superior da faixa de perturbação gravitacional.
  • Com GraviPert_Min_P = 1,0 e GraviPert_Max_P = 1,0, não há perturbação gravitacional.
  • VelocityPert_Min_P - limite inferior da faixa de perturbação da velocidade.
  • VelocityPert_Max_P - limite superior da faixa de perturbação de velocidade.

Quando VelocityPert_Min_P = 1.0 e VelocityPert_Max_P = 1.0, não há perturbação na velocidade.

  • G_constant_P - constante gravitacional, que atua como um coeficiente de escala. Quanto maior o valor, mais fortes são as forças gravitacionais e mais rápida é a mudança de velocidade dos objetos.
  • a_constant_P - coeficiente de correção na constante gravitacional, destinado a reduzir o campo de pesquisa durante toda a otimização com o objetivo de refinar os extremos encontrados.
  • e_constant_P - coeficiente de correção na distância entre os objetos.

Vamos prestar atenção nos resultados dos testes na visualização. O comportamento do algoritmo nas funções de teste é muito peculiar e interessante. Essencialmente, o experimento exibe visualmente o funcionamento das forças gravitacionais. O movimento dos objetos é fortemente influenciado pelos parâmetros externos do algoritmo, bem como pelos resultados de otimização obtidos. Inicialmente, os objetos com velocidade zero são distribuídos aleatoriamente no espaço de pesquisa e já na próxima iteração começam a se mover. Essas configurações, que foram usadas no teste (as melhores que encontrei), fazem com que os objetos se movam em direção ao centro de massa comum.

Não esqueçamos que cada objeto, com sua própria gravidade, influencia os outros objetos, cujas leis de movimento são descritas com bastante precisão no algoritmo. Ao se aproximarem do centro de massa comum, os objetos continuam o movimento, agora a uma velocidade alta. Parece um movimento pulsante da massa das partículas em direção ao centro de massa comum e de volta. Depois de algumas iterações, o movimento dos objetos muda de trajetória sob a influência do relevo do espaço da função de adaptação, que age como uma inomogeneidade gravitacional, afetando a massa dos objetos. Como discutimos antes, a massa dos objetos é calculada a partir do valor da função de adaptação. Embora a função Rastigin, simétrica em relação aos eixos, influencie uniformemente o movimento dos objetos e a decomposição em grupos não seja particularmente notável.

Rastr

  GSA na função de teste Rastrigin.

Os objetos apresentam um comportamento ainda mais interessante nas funções Forest e Megacity. Essas funções são assimétricas e, portanto, têm um efeito inomogêneo em todo o grupo de objetos.

Forest

  GSA na função de teste Forest.

Megacity

GSA na função de teste Megacity.

Após extensos experimentos com o GSA, tive a ideia de criar um simulador de movimento de objetos espaciais. Embora não tenha valor prático, ele proporciona uma visão dos princípios físicos que regem os sistemas planetários e estelares. O simulador é uma versão do GSA com fatores de aleatoriedade desativados. Além disso, três objetos foram introduzidos para simular três estrelas: um gigante azul, uma estrela amarela e uma anã branca. Para eles, os parâmetros de massa são separadamente apresentados nas configurações.

Uma nova função de adaptação chamada Universe, com um espaço uniforme, foi criada especialmente para o simulador. O simulador demonstra claramente como o grau (parâmetro) da distância entre os objetos afeta seu movimento mútuo. Assim, na visualização abaixo, um grau 3 é aplicado em vez do valor padrão da lei de Newton de 2. Fica claro como o grau afeta a formação de sistemas gravitacionalmente ligados, como sistemas estelares binários e triplos.

Se em nosso universo o grau de distância fosse maior, as galáxias teriam se formado muito mais cedo do que na realidade. Na animação, vemos que nos primeiros estágios já surgem objetos pareados, orbitando em torno de um centro de massa comum. Como esperado, o gigante azul na visualização atraiu mais objetos para si.

Uni1

Observação do simulador de movimento de objetos espaciais com base no algoritmo GSA.


Agora, vamos analisar os resultados dos testes do GSA. As técnicas originais usadas no algoritmo não permitiram que ele alcançasse resultados significativos em nosso teste. As numerosas variações de parâmetros que tentei não conseguiram melhorar a convergência do algoritmo. O algoritmo apresentou alguns resultados positivos na suave função de Rastigin com 10 variáveis e na Megacity, comparado com outros participantes do teste. Em outros testes, o GSA apresenta resultados abaixo da média da tabela, ocupando o 8º lugar de 12.

AO

Description

Rastrigin

Rastrigin final

Forest

Forest final

Megacity (discrete)

Megacity final

Final result

10 params (5 F)

50 params (25 F)

1000 params (500 F)

10 params (5 F)

50 params (25 F)

1000 params (500 F)

10 params (5 F)

50 params (25 F)

1000 params (500 F)

IWO

otimização invasiva de ervas daninhas

1,00000

1,00000

0,35295

2,35295

0,79937

0,46349

0,41071

1,67357

0,75912

0,44903

0,94416

2,15231

100,000

ACOm

otimização de colônia de formigas M

0,36118

0,26810

0,20182

0,83110

1,00000

1,00000

1,00000

3,00000

1,00000

1,00000

0,15901

2,15901

96,805

COAm

algoritmo de otimização de cuco M

0,96423

0,69756

0,30792

1,96971

0,64504

0,34034

0,21362

1,19900

0,67153

0,34273

0,48451

1,49877

74,417

FAm

algoritmo de vaga-lumes M

0,62430

0,50653

0,20290

1,33373

0,55408

0,42299

0,64360

1,62067

0,21167

0,28416

1,00000

1,49583

70,740

BA

algoritmo do morcego

0,42290

0,95047

1,00000

2,37337

0,17768

0,17477

0,33595

0,68840

0,15329

0,07158

0,49268

0,71755

59,383

ABC

colônia artificial de abelhas

0,81573

0,48767

0,24656

1,54996

0,58850

0,21455

0,17249

0,97554

0,47444

0,26681

0,39496

1,13621

57,393

BFO

otimização de forrageamento bacteriano

0,70129

0,46155

0,13988

1,30272

0,41251

0,26623

0,26695

0,94569

0,42336

0,34491

0,53694

1,30521

55,563

GSA

algoritmo de busca gravitacional

0,73222

0,67404

0,00000

1,40626

0,31238

0,36416

0,42921

1,10575

0,51095

0,36658

0,00000

0,87753

52,786

FSS

busca por cardume de peixes

0,48850

0,37769

0,13383

1,00002

0,78060

0,05013

0,08423

0,91496

0,00000

0,01084

0,23493

0,24577

20,094

PSO

otimização de enxame de partículas

0,21339

0,12224

0,08478

0,42041

0,15345

0,10486

0,28099

0,53930

0,08028

0,02385

0,05550

0,15963

14,358

RND

aleatório

0,17559

0,14524

0,09495

0,41578

0,08623

0,04810

0,06094

0,19527

0,00000

0,00000

0,13960

0,13960

8,117

GWO

otimizador lobo-cinzento

0,00000

0,00000

0,02672

0,02672

0,00000

0,00000

0,00000

0,00000

0,18977

0,04119

0,07252

0,30348

1,000


Em geral, o algoritmo GSA é sensível à presença de um gradiente na função a ser otimizada, e a baixa escalabilidade não permite o seu uso para tarefas sérias que contêm muitas variáveis, por isso eu não o recomendaria para uso com redes neurais e para otimização de sistemas de negociação. É importante notar que, na minha opinião, as capacidades do algoritmo de busca gravitacional não foram totalmente exploradas por mim, e pesquisas adicionais pelos usuários podem revelar novos aspectos positivos desconhecidos deste algoritmo muito interessante e incomum sob todos os pontos de vista. Entre as principais vantagens do algoritmo, podemos mencionar a independência em relação à melhor solução global atualmente encontrada e a capacidade de todos os agentes interagirem entre si. 

A histograma dos resultados do teste dos algoritmos é mostrado na Figura 2.

chart

Figura 2. Histograma dos resultados finais dos testes dos algoritmos.


Conclusões sobre as propriedades do algoritmo de pesquisa gravitacional (Gravity Search Optimization, GSA):

Prós:
1. Simplicidade de implementação.
2. Desempenho decente em funções suaves com poucas variáveis.

Contras:
1. Alta complexidade computacional.
2. Resultados não tão bons em funções discretas.
3. Baixa escalabilidade.


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

Arquivos anexados |
Baixar como ZIP
12_The_world_of_AO_GSA.zip (99.29 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
Redes neurais de retropropagação em matrizes MQL5 Redes neurais de retropropagação em matrizes MQL5
Este artigo trata da teoria e prática do uso do algoritmo de retropropagação de erros no MQL5 através de matrizes. Oferecemos classes prontas e exemplos de scripts, indicadores e EAs.
Alan Andrews e suas técnicas de análise de séries temporais Alan Andrews e suas técnicas de análise de séries temporais
Alan Andrews é um dos mais renomados "educadores" do mundo do trading atual, no campo da análise de mercado. Suas "forquilhas" estão presentes em praticamente todos os programas modernos de análise de cotações. No entanto, a maioria dos traders utiliza apenas uma pequena fração das possibilidades oferecidas por essa ferramenta. O curso original de Andrews abrange não apenas a descrição das forquilhas (embora sejam o aspecto principal), mas também outras diretrizes úteis. Este artigo apresenta uma visão dessas incríveis técnicas de análise de gráficos que Andrews ensinou em seu curso original. Atenção: muitas imagens serão utilizadas.
Algoritmos de otimização populacionais: Busca harmônica (Harmony Search, HS) Algoritmos de otimização populacionais: Busca harmônica (Harmony Search, HS)
Hoje, estudaremos e testaremos o algoritmo de otimização mais avançado, a busca harmônica (HS), que é inspirada no processo de procura da harmonia sonora perfeita. Então, qual algoritmo é agora o líder em nossa classificação?
Esperança moral na negociação Esperança moral na negociação
Este artigo trata da esperança moral. Veremos vários exemplos de como ela é aplicada na negociação e quais resultados podem ser obtidos com ela.