Algoritmos de otimização populacionais: Algoritmo de mudas, semeadura e crescimento (SSG)

Conteúdo

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

1. Introdução

Todos os organismos vivos na natureza estão sujeitos a certas leis, o que condiciona a supervivência da flora e da fauna em ambientes em constante mudança. Há diferentes adaptações das plantas ao seu ambiente. Algumas são capazes de tolerar mudanças sazonais, outras se adaptam à falta de umidade, a temperaturas altas ou baixas e à falta de polinizadores. Um dos organismos mais resistentes entre as plantas são as árvores, algumas espécies podem viver por mais de 50 mil anos formando arvoredos.

A natureza é um campo inesgotável de inspiração para muitas ideias eficazes no desenvolvimento e na invenção de métodos computacionais. De fato, a computação evolucionária é a projeção da evolução em simulações de computador. Há muitas técnicas de otimização que foram inspiradas por processos que ocorrem na natureza, como computação evolucionária, imunologia artificial, métodos populacionais e outros. O algoritmo de “mudas, semeadura e crescimento” (Saplings Sowing and Growing up, SSG) é caracterizado por processos iterativos de geração e combinação que utilizam um jardim de soluções potenciais chamadas de mudas.  O SSG foi proposto por A. Karci et al. em 2002 e é inspirado na evolução de árvores em crescimento e modela o crescimento e a ramificação das árvores.

2. Descrição do algoritmo

O SSG é um dos poucos que não é descrito claramente pelos autores (existem apenas indicações e ideias gerais sobre ele). Os operadores de variação apresentados pelos autores também não são instruções prontas para a implementação algorítmica do mesmo, não existe indicação clara das árvores filha e pai e de sua interação; também não há requisitos para a sequência de procedimentos, e qualquer usuário pode alterar sua ordem para obter a melhor árvore.

Em um sentido amplo, o SSG não é um algoritmo de otimização, mas, sim, um conjunto genérico de regras que se destina a complementar outros algoritmos para melhorar a qualidade da otimização, ou seja, ele é uma espécie de estrutura complementar para qualquer algoritmo populacional evolutivo, de modo que posso dar asas à imaginação e à oportunidade de experimentar uma implementação específica do algoritmo de otimização. Apliquei algumas de minhas próprias ideias e experiência acumulada ao escrever algoritmos anteriores e as utilizei para trabalhar com o SSG; os resultados de meus experimentos são apresentados a seguir.

Para começar a entender o algoritmo, devemos imaginar uma árvore como um agente de otimização. Uma árvore é uma solução para um problema de otimização, em que cada ramo é um parâmetro otimizável do problema. De forma bastante abstrata e, eu diria, artística, podemos ilustrar uma árvore filha e uma árvore pai (o algoritmo opera com essas duas noções) na Figura 1. O tronco da árvore é um conjunto de parâmetros a serem otimizados. Cada ramo é um parâmetro otimizável separado, em que o comprimento do ramo é limitado pelo intervalo permitido de valores do parâmetro correspondente. A direção dos ramos não é importante e só é mostrada na figura para mostrar que eles são diferentes.

Figura 1. Árvore filha e árvore pai. A linha pontilhada indica os ramos filhos substituídos pelos ramos pais.

Assim, os ramos da árvore são coordenadas da árvore no espaço de busca.

O SSG é composto por operadores de variação que geram novas soluções, que são candidatas ao conjunto de soluções comum. Os principais operadores de variação são cruzamento, ramificação e vacinação. As mudas devem ser plantadas a distâncias equidistantes em cada direção uma da outra (oeste, leste, norte, sul), e essa é a etapa inicial do método. Quando há muito mais de três coordenadas (parâmetros otimizáveis), o plantio "uniforme" é simplesmente uma distribuição aleatória de mudas no espaço de busca. As mudas crescem, cruzam, se ramificam e o processo de vacinação ocorre.

Vejamos as etapas e os operadores do SSG:

1) Plantio de mudas.

O espaço de busca pode ser considerado como um jardim de mudas e, portanto, todas as mudas devem estar espalhadas uniformemente no jardim. Se o fazendeiro quiser plantar mudas, ele simplesmente as plantará a uma distância igual umas das outras para que as mudas cresçam mais rapidamente sem atrapalhar umas às outras. Para resolver o problema ao simular o cultivo de mudas, as soluções arbitrárias a serem geradas inicialmente devem ser distribuídas uniformemente no espaço de busca permitido.

Quando há duas ou três coordenadas, não há problema em distribuir as mudas uniformemente, mas quando há muito mais do que três coordenadas, é mais fácil usar a atribuição aleatória. Porém, na prática, quando o número de coordenadas é pequeno, não há necessidade de se preocupar com a distribuição uniforme das mudas, pois o problema não é grande e é sabido que a solução será obtida com alta precisão, por isso, independentemente do número de coordenadas no algoritmo, usaremos a distribuição aleatória de mudas no jardim. 

2) Cultivo de mudas (árvores), três operadores executados sequencialmente.

2.1) Cruzamento.

O objetivo do operador de cruzamento é criar uma nova muda a partir das mudas existentes, trocando informações entre elas. O cruzamento é basicamente enxertar uma cópia de um ramo de uma árvore-pai em uma árvore-filha (Figura 1). Para cada par de mudas, é usado um fator de cruzamento diferente, que é a probabilidade de cruzamento. A probabilidade de cruzamento depende da distância entre as mudas do par; quanto maior a distância, menor a probabilidade de cruzamento. O operador de cruzamento é um método muito importante do algoritmo que fornece mecanismos combinatórios, combinando informações entre agentes que podem melhorar muito a qualidade geral do algoritmo de otimização.

2.2) Ramificação.

Este operador simula o crescimento do ramo, e o crescimento pode ser tanto positivo (alongamento) quanto negativo (dessecação). "Para que um galho cresça em qualquer ponto do corpo de uma muda, não deve haver nenhum galho próximo que tenha surgido anteriormente ali.", é mais ou menos assim que os autores do algoritmo descrevem o operador de "ramificação". Na verdade, esse processo é mais simples e mais claro do que parece à primeira vista e representa uma modificação dos ramos existentes na árvore filha (o método específico de modificação não é especificado).

A modificação de cada ramo individual é mais provável quanto mais iterações tiverem ocorrido entre a iteração atual e aquela em que a última modificação do ramo foi realizada. Meus experimentos mostraram a ineficiência desse operador; além disso, não há instruções expressas para usar o método de modificação, e eu me permiti ser proativo nessa questão e apliquei uma alteração no comprimento do ramo de acordo com a lei de distribuição de voo de Levy. A modificação será aplicada com a probabilidade e a intensidade especificadas como parâmetros externos do algoritmo.   

2.3) Vacinação.

O processo de vacinação ocorre entre duas mudas diferentes se as mudas forem semelhantes. A similaridade das mudas afeta o sucesso da vacinação e é proporcional à média aritmética da distância ponderada. Este operador é semelhante ao de cruzamento e consiste na troca de ramos, apresentando ao algoritmo uma forma adicional de combinar informações entre os agentes. Este operador será apresentado no artigo, mas no código-fonte ele é comentado e os resultados dos testes são apresentados sem sua participação, pois, infelizmente, a vacinação piora os resultados.

3) Cálculo da adaptação das árvores.

4) Plantio de novas mudas no jardim.

As mudas obtidas pelos operadores de cruzamento, ramificação e vacinação representam soluções temporárias (jardim-filho). Nessa etapa, n é a melhor muda (o parâmetro externo do algoritmo) que deve ser selecionada e colocada no jardim, substituindo as n piores árvores do jardim. Observe que a substituição das mudas ocorrerá de qualquer forma, mesmo que elas sejam piores do que as piores árvores do jardim.

Este é um bom momento para revisar o código do SSG, o que nos aproxima cada vez mais do emocionante clímax deste estudo - a revisão dos resultados dos testes.

Assim, cada árvore é convenientemente representada como uma estrutura de jardim, que nos servirá de base para a criação de um jardim florido. Não há nada mais simples nesse algoritmo do que a entidade "árvore", que precisa de apenas dois componentes: coordenadas c [] e o valor de adaptação f.

//——————————————————————————————————————————————————————————————————————————————
struct S_Garden
{
  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

A classe C_AO_SSG do SSG não tem nada de especial, já que tudo foi visto nos algoritmos discutidos anteriormente. Na classe, declararemos membros e métodos para manusear jardins pai e filho, um jardim temporário para que o método de classificação funcione, pois precisaremos classificar os jardins pai e filho. Declararemos o array de coordenadas da melhor solução em geral e o valor do melhor ajuste, bem como variáveis constantes para armazenar parâmetros externos do algoritmo.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SSG
{
  //============================================================================
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: S_Garden pGarden []; //parent's garden
  public: S_Garden cGarden []; //child's garden
  public: S_Garden gardenT []; //temp garden
  public: double cB        []; //best coordinates
  public: double fB;           //fitness of the best coordinates

  public: void Init (const int    coordinatesP,          //Number of coordinates
                     const int    numberTreesP,          //Number of trees
                     const double seedlingsReplacementP, //Seedlings replacement
                     const double probabMatingOperatorP, //Probability mating operator
                     const double probabBranchOperatorP, //Probability branching operator
                     const double powerBranchOperatorP); //Power branching operator

  public: void Sowing      (int iter);
  public: void Germination ();


  //============================================================================
  private: void   Sorting        (S_Garden &garden []);
  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);

  private: double vec [];               //Vector
  private: int    ind [];
  private: double val [];
  private: double r;

  private: bool   sowing;               //Sowing
  private: int    coordinates;          //Coordinates number
  private: int    numberTrees;          //Number of trees
  private: int    seedlingsReplacement; //Seedlings replacement
  private: double probabMatingOperator; //Probability mating operator
  private: double probabBranchOperator; //Probability branching operator
  private: double powerBranchOperator;  //Power branching operator
};
//——————————————————————————————————————————————————————————————————————————————

No método de inicialização Init (), alocamos a memória para os arrays e atribuímos valores às constantes - parâmetros. Como o parâmetro seedlingsReplacementP é definido em frações do tamanho do jardim (de 0,0 a 1,0), responsável pelo número de mudas filhas a serem plantadas no jardim pai, ele deve ser recalculado para obter uma representação inteira do tamanho do jardim. Redefinimos o sinalizador inicial do jardim de mudas e inicializamos a variável de decisão global com o menor valor possível double.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SSG::Init (const int    coordinatesP,          //Number of coordinates
                     const int    numberTreesP,          //Number of trees
                     const double seedlingsReplacementP, //Seedlings replacement
                     const double probabMatingOperatorP, //Probability mating operator
                     const double probabBranchOperatorP, //Probability branching operator
                     const double powerBranchOperatorP)  //Power branching operator
{
  MathSrand (GetTickCount ());
  sowing = false;
  fB     = -DBL_MAX;

  coordinates    = coordinatesP;
  numberTrees    = numberTreesP;

  if (seedlingsReplacementP >= 1.0)
  {
    seedlingsReplacement = numberTreesP;
  }
  else
  {
    if (seedlingsReplacementP <= 0.0)
    {
      seedlingsReplacement = 1;
    }
    else seedlingsReplacement = int(numberTreesP * seedlingsReplacementP);
  }

  probabMatingOperator = probabMatingOperatorP;
  probabBranchOperator = probabBranchOperatorP;
  powerBranchOperator  = powerBranchOperatorP;

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);
  ArrayResize (vec,       coordinates);
  ArrayResize (cB,        coordinates);


  ArrayResize (pGarden,  numberTrees);
  ArrayResize (cGarden,  numberTrees);
  ArrayResize (gardenT,  numberTrees);
  ArrayResize (ind,      numberTrees);
  ArrayResize (val,      numberTrees);

  for (int i = 0; i < numberTrees; i++)
  {
    ArrayResize (pGarden  [i].c, coordinates);
    ArrayResize (cGarden  [i].c, coordinates);
    ArrayResize (gardenT  [i].c, coordinates);
    cGarden [i].f = -DBL_MAX;
  }
}
//——————————————————————————————————————————————————————————————————————————————

Sowing () é o primeiro método público, necessariamente chamado em cada iteração. Na primeira iteração, quando o algoritmo está em execução, espalhamos as mudas pelo jardim (espaço de busca) de forma aleatória com distribuição uniforme. Aqui vemos que as coordenadas são geradas aleatoriamente em um intervalo permissível entre o min e o max dos parâmetros otimizados, verificamos se estão fora do intervalo permissível e, em seguida, ajustamos os valores das coordenadas à etapa de otimização.

Nesse estágio, a adaptação das mudas é mínimo. Definimos o vetor vec[], precisaremos dele para dimensionar os incrementos dos ramos no operador de ramificação e calcular a distância euclidiana máxima possível r no espaço de busca, o que será útil no operador de cruzamento para determinar a probabilidade dependendo da distância entre os pares de árvores.

//the first planting of trees-------------------------------------------------
if (!sowing)
{
  fB = -DBL_MAX;
  r = 0.0;

  for (int t = 0; t < numberTrees; t++)
  {
    for (int c = 0; c < coordinates; c++)
    {
      cGarden [t].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      cGarden [t].c [c] = SeInDiSp (cGarden [t].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }

    cGarden [t].f = -DBL_MAX;
  }

  for (int c = 0; c < coordinates; c++)
  {
    vec [c] = rangeMax [c] - rangeMin [c];
    r += vec [c] * vec [c];
  }

  r = sqrt (r);

  return;
}

Depois, no método Sowing(), os operadores de cruzamento, ramificação e vacinação são executados na segunda iteração e nas subsequentes. Esse é o laço principal em que os operadores são executados sequencialmente:

//tree growth-----------------------------------------------------------------
int child, parent;
double rnd;
double ed; //euclidean distance
double eM;
double u;
double temp;

for (int t = 0; t < numberTrees; t++)

Ao executar os operadores, os conceitos de "filho" e "pai" são muito condicionais; na verdade, eles são apenas informações básicas para gerar uma nova muda. A nova muda copia todos os ramos (e os ramos, como lembramos, são os parâmetros otimizados) da árvore filha e, além disso, recebe novos ramos da árvore pai.

Para cada nova muda, duas árvores são selecionadas individualmente do jardim, uma árvore filha e uma árvore mãe, aleatoriamente, com a mesma probabilidade para todas as árvores do jardim, ou seja, todas as árvores podem participar da geração da nova muda com a mesma probabilidade e independentemente de sua adaptabilidade. Assim, filho e pai são simplesmente índices das duas árvores de origem no array do jardim pai.

ed = 0.0;

rnd = RNDfromCI (0.0, numberTrees - 1);
child = (int)MathRound (rnd);
if (child < 0) child = 0;
if (child > numberTrees - 1) child = numberTrees - 1;

rnd = RNDfromCI (0.0, numberTrees - 1);
parent = (int)MathRound (rnd);
if (parent < 0) parent = 0;
if (parent > numberTrees - 1) parent = numberTrees - 1;

if (child == parent) parent++;
if (parent > numberTrees - 1) parent = 0;

ArrayCopy (cGarden [t].c, pGarden [child].c, 0, 0, WHOLE_ARRAY);

O primeiro operador é o de cruzamento (mating). Para executar esse operador sobre uma muda com índice t, precisamos calcular o espaço euclidiano entre as árvores filha e pai com índices child e parent:

//mating operator-----------------------------------------------------------
for (int c = 0; c < coordinates; c++)
{
  temp = pGarden [child].c [c] - pGarden [parent].c [c];
  ed += temp * temp;
}

ed = sqrt (ed);

A distância euclidiana entra na fórmula para calcular a probabilidade de cruzamento por meio da normalização da distância euclidiana máxima possível r no espaço de busca:

eM = 1.0 - (ed / r);

Geramos um número aleatório no intervalo [0,0;1,0] e, se o número resultante estiver dentro da probabilidade calculada eM, realizamos o cruzamento, copiando ramos da árvore principal com o probabMatingOperator para cada ramo. Se a probabilidade eM não for atendida, a muda passará à execução do próximo operador com todos os ramos iniciais da árvore filha.

rnd = RNDfromCI (0.0, 1.0);

if (rnd <= eM)
{
  for (int c = 0; c < coordinates; c++)
  {
    rnd = RNDfromCI (0.0, 1.0);

    if (rnd <= probabMatingOperator) cGarden [t].c [c] = pGarden [parent].c [c];
  }
}

Em seguida, o operador de ramificação é executado. A ramificação possibilita a variação dos ramos - alongamento e encurtamento - e é o principal operador responsável pela criação de ramos de novo comprimento; já os outros operadores desempenham apenas uma função combinatória e não criam novos ramos exclusivos. Para cada ramo, geramos um número aleatório no intervalo [0,0;1,0] e, se probabBranchOperator for atendido, ramificamos, isto é, alteramos o comprimento de um ramo de acordo com a lei de distribuição de Levy abordada aqui.

Como se pode ver, nem todos os ramos de uma muda serão modificados, e eles serão modificados independentemente de o ramo ter sido copiado da árvore pai no operador anterior ou de ser o ramo filho original. Depois de modificar um ramo, verificamos se há valores discrepantes e o alinhamos com o passo de otimização.

//branching operator--------------------------------------------------------
for (int c = 0; c < coordinates; c++)
{
  rnd = RNDfromCI (0.0, 1.0);

  if (rnd < probabBranchOperator)
  {
    double r1 = RNDfromCI (0.0, 1.0);
    r1 = r1 > 0.5 ? 1.0 : -1.0;
    double r2 = RNDfromCI (1.0, 20.0);

    cGarden [t].c [c] = cGarden [t].c [c] + r1 * vec [c] * powerBranchOperator * pow (r2, -2.0);
    cGarden [t].c [c] = SeInDiSp (cGarden [t].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}

O terceiro operador é o de vacinação. Ele foi concebido pelos autores, aparentemente, como um operador combinatório e deveria ser executado para copiar ramos da árvore pai quando os ramos da árvore filha e da árvore pai divergissem em mais de uma diferença média em todas as árvores. Isso parece muito complicado, mas há pouco uso para esse operador e, portanto, ele é comentado nos arquivos iniciais. Nesse caso, não posso agir como um especialista de última instância e, portanto, admito a possibilidade de que eu tenha entendido mal esse operador.

//vaccinating operator------------------------------------------------------
u = 0.0;
    
for (int c = 0; c < coordinates; c++)
{
  u += fabs (cGarden [t].c [c] - pGarden [parent].c [c]) / vec [c];
}

u /= coordinates;

for (int c = 0; c < coordinates; c++)
{
  if (fabs (cGarden [t].c [c] - pGarden [parent].c [c]) / vec [c] >= u)
  {
    cGarden [t].c [c] = pGarden [parent].c [c];
  }
}

Plantamos mudas, cruzamos e ramificamos, e às vezes até vacinamos. Agora é a vez da última, mas não a última, operação importante do algoritmo - a germinação, ou seja, executamos o segundo método aberto obrigatório Germination () a cada iteração.

Se a primeira iteração chegar ao fim, o que pode ser identificado pelo sinalizador sowing (semeadura), significa que o jardim dos pais está vazio, então plantamos todas as mudas do jardim dos filhos no jardim pai, copiando as árvores jovens uma a uma. Em seguida, classificamos o jardim pai pelo valor de adaptação usando o método Sorting (). E se as árvores estiverem classificadas, a árvore com índice 0 terá a melhor adaptação, e poderemos atualizar a melhor solução global se ela ainda não for a melhor.

if (!sowing)
{
  for (int t = 0; t < numberTrees; t++) pGarden [t] = cGarden [t];

  Sorting (pGarden);

  if (pGarden [0].f > fB)
  {
    fB = pGarden [0].f;

    ArrayCopy (cB, pGarden [0].c, 0, 0, WHOLE_ARRAY);
  }
  
  sowing = true;
  return;
}

Mais adiante no código, só chegaremos à segunda iteração e às subsequentes no algoritmo, porque atribuímos prudentemente ao sinalizador sowing o valor true. Na segunda iteração e nas subsequentes, precisamos classificar o jardim filho antes de transferir as mudas para o jardim pai e substituir as piores árvores. Verificamos que a solução global melhora e, em seguida, copiamos os n melhores exemplares das mudas para o final do jardim pai.

Por fim, só precisamos classificar o jardim pai; os novos membros da comunidade de árvores do jardim podem substituir as árvores das gerações mais antigas para nos deixar satisfeitos com os resultados da solução do problema de otimização.

//planting some part from all child trees-------------------------------------
Sorting (cGarden);

if (cGarden [0].f > fB)
{
  fB = cGarden [0].f;

  ArrayCopy (cB, cGarden [0].c, 0, 0, WHOLE_ARRAY);
}

for (int t = 0; t < seedlingsReplacement; t++) pGarden [numberTrees - seedlingsReplacement + t] = cGarden [t];

Sorting (pGarden);

3. Resultado dos testes

Saída obtida usando o SSG em uma bancada de teste:

2023.03.09 12:50:37.207    Test_AO_SSG (GBPUSD,M1)    C_AO_SSG:50;0.3;0.5;0.4;0.1
2023.03.09 12:50:37.207    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:50:45.954    Test_AO_SSG (GBPUSD,M1)    5 Rastrigin's; Func runs 10000 result: 80.7052793572295
2023.03.09 12:50:45.954    Test_AO_SSG (GBPUSD,M1)    Score: 0.99998
2023.03.09 12:50:59.290    Test_AO_SSG (GBPUSD,M1)    25 Rastrigin's; Func runs 10000 result: 77.3972262608643
2023.03.09 12:50:59.290    Test_AO_SSG (GBPUSD,M1)    Score: 0.95900
2023.03.09 12:52:25.368    Test_AO_SSG (GBPUSD,M1)    500 Rastrigin's; Func runs 10000 result: 52.24518909141432
2023.03.09 12:52:25.368    Test_AO_SSG (GBPUSD,M1)    Score: 0.64735
2023.03.09 12:52:25.368    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:52:31.419    Test_AO_SSG (GBPUSD,M1)    5 Forest's; Func runs 10000 result: 1.331178589711503
2023.03.09 12:52:31.419    Test_AO_SSG (GBPUSD,M1)    Score: 0.75298
2023.03.09 12:52:42.575    Test_AO_SSG (GBPUSD,M1)    25 Forest's; Func runs 10000 result: 1.019329018074209
2023.03.09 12:52:42.575    Test_AO_SSG (GBPUSD,M1)    Score: 0.57658
2023.03.09 12:53:48.922    Test_AO_SSG (GBPUSD,M1)    500 Forest's; Func runs 10000 result: 0.25410121872226443
2023.03.09 12:53:48.922    Test_AO_SSG (GBPUSD,M1)    Score: 0.14373
2023.03.09 12:53:48.922    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:53:57.201    Test_AO_SSG (GBPUSD,M1)    5 Megacity's; Func runs 10000 result: 6.4
2023.03.09 12:53:57.201    Test_AO_SSG (GBPUSD,M1)    Score: 0.53333
2023.03.09 12:54:08.004    Test_AO_SSG (GBPUSD,M1)    25 Megacity's; Func runs 10000 result: 4.504
2023.03.09 12:54:08.004    Test_AO_SSG (GBPUSD,M1)    Score: 0.37533
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    500 Megacity's; Func runs 10000 result: 1.2336
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    Score: 0.10280
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    =============================
2023.03.09 12:56:07.061    Test_AO_SSG (GBPUSD,M1)    All score: 5.09109

Embora o SSG não possua uma quantidade extensa de parâmetros, produto de minha incursão amadora na escrita de algoritmos (os criadores do SSG possuem menos parâmetros), é inegável que eles (os parâmetros) demandam um foco especial e uma discussão cuidadosa sobre seus valores. Nos testes, os seguintes parâmetros foram empregados e, para recordar, em cada um de meus artigos, eu apresento os parâmetros ótimos dos algoritmos, ou seja, aqueles que proporcionam os resultados mais altos possíveis.

C_AO_SSG:50;0,3;0,5;0,4;0,1

O parâmetro input int NumberTrees_P = 50 define a quantidade de árvores no jardim. Eu optei por não fazer experiências com este parâmetro, preferindo usar o valor padrão de meus testes. Com o valor aumentado para 100, o algoritmo exibe um desempenho ainda melhor, mas sua capacidade de escalonamento se reduz, devido ao decréscimo no número permitido de iterações por jardim, considerando seu tamanho. Um jardim com um número elevado de ramos acaba não tendo tempo suficiente para evoluir.

O parâmetro input double SeedlingsReplacement_P = 0,3 se refere à proporção de mudas do jardim filho que serão transferidas para o jardim pai.
O input double ProbabMatingOperator_P = 0,5 diz respeito à probabilidade de cruzamento (ou cópia de ramos da árvore pai), caso a probabilidade, que leva em consideração a distância entre dois pares de árvores, seja atendida.
O input double ProbabBranchOperator_P = 0,4 determina a probabilidade de ramificação (crescimento ou diminuição de ramos), um parâmetro crucial que tem um impacto significativo no desempenho do algoritmo (todos os parâmetros são importantes, na verdade).
O input double PowerBranchOperator_P = 0,1 define a força da ramificação, que é um coeficiente de escala na dimensão dos parâmetros a serem otimizados. Um valor de 1.0 ou mais indica um crescimento dos ramos até as bordas do jardim, enquanto um valor de 0.0 denota a ausência de crescimento dos ramos, resultando em um algoritmo que se degenera em uma ferramenta combinatória simples. (Uma ideia interessante para a aplicação do SSG, que, a propósito, ainda não foi explorada em pesquisas).

Se atentarmos para a animação do funcionamento do algoritmo SSG em funções de teste, percebemos a ausência de padrões definidos de movimento das árvores no jardim. Nota-se apenas um agrupamento discreto nos pontos de extremos locais. No entanto, a alta qualidade da convergência é imediatamente perceptível, especialmente quando comparada a outros algoritmos previamente analisados. Outro ponto de destaque é a consistência na reprodutibilidade dos resultados.

  SSG na função de teste Rastrigin.

  SSG na função de teste Forest.

  SSG no recurso de teste Megacity.

Vamos discutir os resultados do algoritmo SSG, que certamente fornecem um material rico para análise. O algoritmo de crescimento de árvores se destacou triunfantemente na primeira posição do ranking, deixando os concorrentes em pedaços! O algoritmo não utiliza o conhecimento de adaptação diretamente para modificar as árvores de decisão, a adaptação é utilizada apenas para classificar o jardim filho e o jardim pai. Portanto, é ainda mais surpreendente que o algoritmo tenha conseguido exibir resultados tão notáveis nos testes.

Seria como se um time de pessoas cegas superasse um time de pessoas com visão normal em um desafio de orientação. O algoritmo ultrapassou os demais participantes na tabela em quatro dos seis testes, sem ficar muito atrás nos testes em que não é o líder. O SSG exibiu a vantagem mais impressionante sobre os rivais na função discreta Megacity, superando o concorrente mais próximo, o HS, em quase 60%! Isso demonstra a excelente escalabilidade do algoritmo. Também apresentou o melhor resultado de escalabilidade na função de teste "afiada" do Forest, superando o melhor concorrente neste teste, o ACOm, por quase 30%.

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)
SSG	mudas, semeando e crescimento	1,00000	1,00000	0,65914	2,65914	0,70823	0,94522	1,00000	2,65345	0,71532	0,85412	1,00000	2,56944	100,000
HS	busca de harmonia	0,99676	0,95282	0,57048	2,52006	1,00000	0,98931	0,44806	2,43736	1,00000	1,00000	0,41537	2,41537	93,370
ACOm	otimização de colônia de formigas M	0,34611	0,17985	0,20182	0,72778	0,85966	1,00000	0,77362	2,63327	1,00000	0,88484	0,05606	1,94090	66,407
IWO	otimização invasiva de ervas daninhas	0,95828	0,67083	0,35295	1,98207	0,68718	0,46349	0,31773	1,46840	0,75912	0,39732	0,33289	1,48933	61,691
COAm	algoritmo de otimização de cuco M	0,92400	0,46794	0,30792	1,69987	0,55451	0,34034	0,16526	1,06012	0,67153	0,30326	0,17083	1,14561	48,226
FAm	algoritmo de vaga-lumes M	0,59825	0,33980	0,20290	1,14095	0,47632	0,42299	0,49790	1,39721	0,21167	0,25143	0,35258	0,81568	41,042
ABC	colônia artificial de abelhas	0,78170	0,32715	0,24656	1,35541	0,50591	0,21455	0,13344	0,85390	0,47444	0,23609	0,13926	0,84979	37,204
BA	algoritmo do morcego	0,40526	0,63761	1,00000	2,04287	0,15275	0,17477	0,25989	0,58741	0,15329	0,06334	0,17371	0,39034	36,703
GSA	algoritmo de busca gravitacional	0,70167	0,45217	0,00000	1,15384	0,26854	0,36416	0,33204	0,96475	0,51095	0,32436	0,00000	0,83531	35,834
BFO	otimização de forrageamento bacteriano	0,67203	0,30963	0,13988	1,12154	0,35462	0,26623	0,20652	0,82736	0,42336	0,30519	0,18932	0,91786	34,700
MA	algoritmo do macaco	0,33192	0,33451	0,17340	0,83983	0,03684	0,07891	0,08932	0,20508	0,05838	0,00383	0,10720	0,16941	13,185
FSS	busca por cardume de peixes	0,46812	0,25337	0,13383	0,85532	0,06711	0,05013	0,06516	0,18240	0,00000	0,00959	0,08283	0,09242	12,089
PSO	otimização de enxame de partículas	0,20449	0,08200	0,08478	0,37127	0,13192	0,10486	0,21738	0,45415	0,08028	0,02110	0,01957	0,12095	9,696
RND	aleatório	0,16826	0,09743	0,09495	0,36065	0,07413	0,04810	0,04715	0,16938	0,00000	0,00000	0,04922	0,04922	4,916
GWO	otimizador lobo-cinzento	0,00000	0,00000	0,02672	0,02672	0,00000	0,00000	0,00000	0,00000	0,18977	0,03645	0,02557	0,25179	1,000

Conclusões

Características do SSG: não requer diferenciabilidade e continuidade da função de otimização, não há restrições quanto ao tipo de representação e codificações usadas, o algoritmo não usa informações de adaptação de agentes individuais e da melhor solução em geral. Por causa desses recursos, o SSG pode ser facilmente aplicado a diversos problemas de otimização, inclusive os muito complexos; o SSG pode ser recomendado com segurança para ser usado por traders e para aprendizado de máquina. No momento da escrita deste artigo, o SSG é o líder indiscutível em termos de qualidade de convergência, estabilidade de resultados e escalabilidade.

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

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

Prós e contras do SSG:

Prós:
1. Simplicidade de implementação.
2. Excelente convergência em todos os tipos de funções.
3. Escalabilidade impressionante.

Contras:
1. Muitas opções de personalização, embora as opções sejam intuitivas.

Para cada artigo, eu anexo um arquivo que contém versões atualizadas dos códigos dos algoritmos para todos os artigos anteriores. O artigo é a experiência acumulada do autor e opinião pessoal, as conclusões e julgamentos são baseados em experimentos.