Algoritmos de otimização populacionais: salto de sapo embaralhado

Conteúdo:

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

1. Introdução

O algoritmo salto de sapo embaralhado (Shuffled Frog Leaping Algorithm, SFL) foi proposto por M. Eusuff e outros autores em 2003. Este algoritmo combina princípios do algoritmo memético e do algoritmo enxame de partículas, e seu desenvolvimento foi inspirado no comportamento de um grupo de sapos na busca por alimento.

Originalmente, o algoritmo SFL foi desenvolvido como um método metaheurístico para resolver problemas de otimização combinatória. Ele é baseado no uso de funções matemáticas e busca heurística informada.

O algoritmo SFL consiste em várias populações virtuais interativas de sapos, chamadas memplexos. Os sapos virtuais desempenham o papel de hospedeiros ou portadores de memes, aqui um meme representa uma unidade de evolução cultural. Em cada memplexo, ocorre uma busca local independente usando um método semelhante à otimização por enxame de partículas, mas com foco na busca local.

Para facilitar as explorações globais, os sapos virtuais são periodicamente embaralhados e reorganizados em novos memplexos usando um método semelhante ao algoritmo de evolução complexa embaralhada. Além disso, sapos virtuais aleatórios são gerados e substituídos na população para permitir a geração aleatória de informações aprimoradas.

O algoritmo salto de sapo embaralhado é um método eficaz para resolver problemas complexos de otimização e permite alcançar soluções ótimas em várias áreas de aplicação. Neste artigo, examinaremos os princípios fundamentais e a aplicação deste algoritmo, bem como suas vantagens e limitações.

2. Descrição do algoritmo

A memética (memetics) representa uma abordagem aos modelos de transmissão evolutiva de informações, baseada no conceito de memes. Os memes, sendo análogos aos genes, servem como unidades de informação cultural, disseminadas entre as pessoas por meio de imitação, treinamento e outros meios. O conceito de meme foi introduzido e os fundamentos da memética foram desenvolvidos por Dawkins (C.R. Dawkins) em 1976. Os memes podem ser transmitidos verticalmente de antecessores, pais, educadores, livros, artefatos culturais, etc. Também é possível a transmissão horizontal de memes de pessoa para pessoa e de cultura para cultura. Embora os memes representem informações puras, seu funcionamento leva a mudanças significativas no comportamento humano.

Algoritmos meméticos (Memetic Algorithms, MA) são definidos como algoritmos metaheurísticos populacionais híbridos de otimização de busca, baseados no conceito de meme e no princípio evolutivo não darwiniano. No contexto dos MA, um meme é a implementação de um algoritmo de otimização local, refinando as soluções atuais a cada iteração ou através de um certo número de iterações. Os MA podem ser vistos como a hibridização de um dos algoritmos populacionais de busca global com um ou mais algoritmos clássicos ou populacionais de otimização local. Originalmente, os MA foram propostos como uma das variantes para aumentar a eficiência dos algoritmos genéticos.

A eficácia dos MA depende em grande parte dos seus parâmetros livres. Vários estudos mostraram que a escolha dos memes utilizados tem um impacto muito grande na eficiência desses algoritmos. Portanto, este problema ocupa um dos lugares centrais nos trabalhos dedicados aos MA.

Os memes representam uma das ideias revolucionárias, implicando uma semelhança entre a evolução dos genes e a evolução da cultura humana. Dawkins chamou a unidade de troca cultural, um análogo do gene na cultura, de meme. Um meme pode ser um gesto, palavra ou ideia; qualquer unidade de informação cultural que possa ser transmitida de pessoa para pessoa através da imitação de treinamento é um meme.

Diferentemente dos algoritmos genéticos, os algoritmos meméticos imitam o processo de evolução cultural. O método desenvolvido por Moscato utiliza a analogia com a evolução dos memes. O algoritmo memético consiste nas seguintes etapas: busca local, cooperação, competição e critério de término da busca. A memética cobre uma vasta classe de algoritmos unidos por uma ideia comum: a inclusão no algoritmo genético do aprendizado de cada indivíduo e o uso de informações sobre a estrutura do espaço de soluções possíveis. O problema do equilíbrio entre a busca populacional e local pode ser visto como um problema geral de manter o equilíbrio entre as explorações extensivas e intensivas do espaço de busca.

De modo geral, o algoritmo memético inclui os seguintes componentes:

1. Busca local. Para isso, pode-se usar o algoritmo de simulação de recozimento e algoritmos de subida.
2. Cooperação. A troca de informações entre os indivíduos pode ser realizada por meio de um procedimento semelhante à aplicação do operador de cruzamento em dois pontos nos algoritmos genéticos.
3. Competição. O procedimento de seleção é semelhante ao dos algoritmos genéticos e geralmente envolve a seleção dos indivíduos mais aptos na população e a eliminação dos menos aptos.
4. Critério de término da busca. Nos algoritmos meméticos, ele pode incluir a avaliação da diversidade dos indivíduos, além do cálculo do número de iterações e da avaliação da melhoria do resultado.

Os algoritmos meméticos cobre uma vasta classe de rotinas unidas por uma ideia comum, que é a inclusão no algoritmo genético do aprendizado de cada indivíduo e o uso de informações sobre a estrutura do espaço de soluções possíveis.

Os memes, assim como os genes, são replicadores, ou seja, objetos capazes de se autorreplicar. Para os memes, a sobrevivência e reprodução dependem da presença de um hospedeiro que propague o meme. Os memes podem sofrer variações, formando novos memes, e participam da luta por recursos - as mentes das pessoas.

Os memes frequentemente se unem em complexos, ou memplexos, para fortalecer-se na luta por hospedeiros. Os memplexos são semelhantes a conjuntos simbióticos de genes que compõem os códigos genéticos de organismos biológicos. Um exemplo de memplex pode ser uma religião. Os memplexos exercem uma influência profunda na formação do comportamento individual e social.

Vamos agora diretamente para o algoritmo salto de sapo embaralhado. A ideia principal do algoritmo reside na divisão de toda a população de sapos com um líder global G em memes - grupos, cada um dos quais tem um líder L (figura 1).

Figura 1. População de sapos com líder global (G), dividida em memes com seu líder local (L).

Dentro de cada meme, os sapos se esforçam para se mover na direção do líder local. A liderança é atualizada se a posição de um dos sapos melhora. Os memes não são separados no espaço de busca e podem ter sobreposições. Assim, um sapo que está no território de um meme pode muito bem pertencer a outro. Isso cria um ambiente dinâmico, onde os sapos podem transitar espacialmente de um meme para outro, dependendo das mudanças em suas posições no espaço de busca.

Consideramos o problema da otimização condicional global, onde a função de adaptação está sujeita à maximização. O algoritmo SFL inclui os seguintes passos básicos.

1.0 Inicializar o algoritmo
1.1 Criar a população inicial de sapos com coordenadas aleatórias.
1.2 Avaliar a adaptação de cada sapo.
1.3 Criar memplexos (subpopulações), distribuindo os sapos pelos memplexos.

2.0 Ciclo de busca pela solução ótima
2.1 Para cada memplexo:
    2.1.1 Identificar o melhor sapo.
    2.1.2 Mover os outros sapos em direção ao melhor sapo no memplexo.
2.2 Se o movimento do sapo não melhorar sua adaptação:
    2.2.1 Mover em direção ao sapo globalmente melhor.
    2.2.2 Se isso também não melhorar a adaptação, mover o sapo para um local aleatório no campo.

3.0 Medição da adaptação dos sapos
3.1 Medir a adaptação de cada sapo na população.
3.2 Atualizar as informações sobre o melhor sapo em cada memplexo e na população como um todo.

4.0 Identificação do melhor sapo globalmente e atualização dos memplexos
4.1 Identificar o melhor sapo em toda a população.
4.2 Se este for o último ciclo:
    4.2.1 Reiniciar o contador de ciclos do memplexo.
    4.2.2 Gerar índices aleatórios para os sapos.
    4.2.3 Copiar os sapos para os memplexos de acordo com os novos índices.
    4.2.4 Identificar o melhor sapo em cada memplexo.
    4.2.5 Reiniciar a adaptação dos sapos e o passo.
4.3 Se este não for o último ciclo:
    4.3.1 Copiar a adaptação e coordenadas dos sapos da população para os sapos correspondentes nos memplexos.
    4.3.2 Identificar o melhor sapo em cada memplexo.
    4.3.3 Definir a direção do próximo salto para cada sapo, dependendo de sua adaptação.

Dessa forma, a base do algoritmo SFL é a combinação da busca local dentro de cada um dos memplexos e da busca global por meio da troca de informações sobre as posições dos melhores agentes dos memplexos.
Este algoritmo representa uma modificação do SFL, na qual, na etapa de busca local, o agente move-se não exatamente na direção do melhor agente do respectivo memplexo, mas em uma direção aleatoriamente perturbada. São conhecidas tanto hibridizações sequenciais quanto paralelas do algoritmo com muitos algoritmos populacionais, como o algoritmo do sistema imunológico artificial.

Figura 2. Saltos dos sapos. Se o movimento anterior não foi bem-sucedido, o próximo salto será feito do mesmo lugar.

A unidade lógica do algoritmo de otimização SFL é o sapo, que pode ser descrito pela estrutura S_Frog, que representa um agente no espaço de busca.

A estrutura S_Frog contém os seguintes campos:

• c - array de coordenadas da posição atual do sapo.
• cPrev - array de coordenadas da posição anterior do sapo.
• f - valor da função de adaptação para a posição atual do sapo.
• fPrev - valor da função de adaptação para a posição anterior do sapo.
• frogStep - número do passo em que o sapo está.

//——————————————————————————————————————————————————————————————————————————————
struct S_Frog
{
  void Init (int coords)
  {
    ArrayResize (c,     coords);
    ArrayResize (cPrev, coords);
    f        = -DBL_MAX;
    fPrev    = -DBL_MAX;
    frogStep = 0;
  }
  double c     []; //coordinates
  double cPrev []; //previous coordinates
  double f;        //fitness
  double fPrev;    //previous fitness
  int    frogStep; //frog step
};
//——————————————————————————————————————————————————————————————————————————————

A estrutura S_Memeplex descreve um memplexo no algoritmo. Ela contém os seguintes campos:

• frogs - array de sapos que compõem o memplexo.
• fBest - melhor valor de função de adaptação entre todos os sapos no memplexo.
• cBest - array de coordenadas correspondentes ao melhor valor de função de adaptação no memplexo.

//——————————————————————————————————————————————————————————————————————————————
struct S_Memeplex
{
  S_Frog frogs [];
  double fBest;     //best fitness
  double cBest [];  //best coordinates
};
//——————————————————————————————————————————————————————————————————————————————

A classe C_AO_SFL oferece métodos para a inicialização do algoritmo, movimentação dos sapos e revisão da população. Ela também contém métodos auxiliares para a conversão de valores e geração de números aleatórios.

Vamos escrever a classe do algoritmo SFL, incluindo os campos:

• cB - array que armazena as melhores coordenadas (best coordinates);
• fB - variável que armazena o valor da função objetivo (fitness function) para as melhores coordenadas;
• frogs - array que armazena todos os sapos na população;
• mems - array que armazena os memplexos (grupos de sapos);
• rangeMax - array que armazena os valores máximos para cada coordenada de busca;
• rangeMin - array que armazena os valores mínimos para cada coordenada de busca;
• rangeStep - array que armazena os passos de busca para cada coordenada.

Métodos públicos da classe:

• Init - método de inicialização dos parâmetros do algoritmo, aceita os seguintes parâmetros:
• coordinatesNumberP - quantidade de coordenadas de busca;
• populationSizeP - tamanho da população (número de sapos);
• numbMemsP - quantidade de memplexos (grupos de sapos);
• numbCyclesP - número de ciclos no memplexo;
• frogStepsToLocalMaxP - número de passos do sapo até o máximo local;
• movConstantP - constante de movimentação (passo de busca) dos sapos.

Moving - método que implementa o movimento dos sapos no espaço de busca.
Revision - método que realiza a revisão da população de sapos e atualiza as melhores coordenadas.
SeInDiSp - método auxiliar que realiza a conversão de um valor de um intervalo para outro com um passo definido.
RNDfromCI - método auxiliar que gera um número aleatório dentro de um intervalo especificado.

Descrição dos campos privados da classe:

• coordinatesNumber - número de coordenadas de busca;
• frogsNumber - número de sapos na população;
• numbMems - número de memplexos (grupos de sapos);
• numbCycles - número de ciclos no memplexo;
• frogStepsToLocalMax - número de passos do sapo até o máximo local;
• movConstant - constante de movimentação (passo de busca) dos sapos;
• memsFrogs - quantidade de sapos em cada memplexo;
• numbCyclesCNT - contador de ciclos;
• vect - array que armazena o vetor;
• indexes - array que armazena os índices;
• revision - flag que indica a necessidade de revisão da população.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SFL
{
  //----------------------------------------------------------------------------
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates
  public: S_Frog frogs     []; //all frogs
  public: S_Memeplex mems  []; //memeplexes

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search


  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    numbMemsP,            //number of memeplexes
                     const int    numbCyclesP,          //number of cycles in the memeplex
                     const int    frogStepsToLocalMaxP, //frog steps to the local maximum
                     const double movConstantP);        //movement step (0.0 .. 1.0)

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

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber;   //coordinates number
  private: int    frogsNumber;         //frogs number
  private: int    numbMems;            //number of memeplexes
  private: int    numbCycles;          //number of cycles in the memeplex
  private: int    frogStepsToLocalMax; //frog steps to the local maximum
  private: double movConstant;         //movement step (0.0 .. 1.0)
  private: int    memsFrogs;           //number of frogs in the memplex
  private: int    numbCyclesCNT;       //cycle counter

  private: double vect    [];          //vector
  private: int    indexes [];          //indexes
  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

Para inicializar o algoritmo, usaremos o método de inicialização Init, que possui vários parâmetros:

• coordinatesNumberP - número de coordenadas
• populationSizeP - tamanho da população
• numbMemsP - número de memplexos
• numbCyclesP - número de ciclos no memplexo
• frogStepsToLocalMaxP - número de passos do sapo até o máximo local
• movConstantP - passo de movimentação (de 0.0 a 1.0)

Inicialmente, o método reinicia o gerador de números aleatórios e define o valor inicial da variável fB (-DBL_MAX) e revision (false).
Em seguida, o método cria arrays rangeMax, rangeMin, rangeStep, vect, indexes, cB, frogs e mems com os tamanhos necessários.
O método inicializa cada sapo no array frogs e cada sapo em cada memplexo no array mems usando o método Init, passando o número de coordenadas.
Em seguida, o método define o valor inicial da variável fBest de cada memplexo como -DBL_MAX e cria um array cBest para cada memplexo com o tamanho necessário.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SFL::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    numbMemsP,            //number of memeplexes
                     const int    numbCyclesP,          //number of cycles in the memeplex
                     const int    frogStepsToLocalMaxP, //frog steps to the local maximum
                     const double movConstantP)         //movement step (0.0 .. 1.0)
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber   = coordinatesNumberP;
  frogsNumber         = populationSizeP;
  numbMems            = numbMemsP;
  numbCycles          = numbCyclesP;
  frogStepsToLocalMax = frogStepsToLocalMaxP;
  movConstant         = movConstantP;
  memsFrogs           = frogsNumber / numbMems;

  numbCyclesCNT       = 0;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);
  ArrayResize (vect,      coordinatesNumber);
  ArrayResize (indexes,   frogsNumber);

  ArrayResize (cB, coordinatesNumber);

  ArrayResize (frogs, frogsNumber);
  for (int i = 0; i < frogsNumber; i++)
  {
    frogs [i].Init (coordinatesNumber);
  }

  ArrayResize (mems, numbMems);
  for (int i = 0; i < numbMems; i++)
  {
    ArrayResize (mems [i].frogs, memsFrogs);
    for (int frgs = 0; frgs < memsFrogs; frgs++)
    {
      mems [i].frogs [frgs].Init (coordinatesNumber);
    }

    mems [i].fBest = -DBL_MAX;
    ArrayResize (mems [i].cBest, coordinatesNumber);
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método Moving é destinado à movimentação dos sapos no espaço de busca. O método é bastante extenso e será analisado em partes.

No início do código, verifica-se o valor da variável revision. Se for false, o seguinte bloco de código é executado:

- É definido o valor inicial da variável fB, que representa a melhor avaliação da função. Neste caso, é atribuído a ela o valor -DBL_MAX (negativo infinito).
- Inicia-se um laço em que cada sapo é inicializado. Para cada sapo:
- Inicia-se um laço para cada coordenada c.
- Um valor aleatório para a coordenada c é gerado usando a função RNDfromCI, que retorna um número aleatório dentro de um intervalo especificado.
- O valor da coordenada c é ajustado para o intervalo usando a função SeInDiSp, que permite deslocar o valor dentro do intervalo com um passo definido.
- O valor da função f para o sapo é definido como -DBL_MAX.
- O valor da função anterior fPrev para o sapo é definido como -DBL_MAX.
- O passo do sapo frogStep é definido como 0.

- Inicia-se um laço para cada coordenada c.
- Calcula-se o valor vect[c], que representa o produto da diferença entre o valor máximo e mínimo do intervalo pelo movConstant.
- A variável revision é definida como true, indicando que a inicialização foi completada.
- A variável numbCyclesCNT é definida como 0.

Assim, este código realiza a inicialização dos sapos, estabelece valores iniciais para a função e outros parâmetros, além de calcular o valor de vect[c] para cada coordenada c.

if (!revision)
{
  fB = -DBL_MAX;

  for (int frgs = 0; frgs < frogsNumber; frgs++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      frogs [frgs].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      frogs [frgs].c [c] = SeInDiSp (frogs [frgs].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      frogs [frgs].f        = -DBL_MAX;
      frogs [frgs].fPrev    = -DBL_MAX;
      frogs [frgs].frogStep = 0;
    }
  }

  for (int c = 0; c < coordinatesNumber; c++)
  {
    vect [c] = (rangeMax [c] - rangeMin [c]) * movConstant;
  }

  revision      = true;
  numbCyclesCNT = 0;
}

Se o flag revision for true, isso significa que o algoritmo avançou para a fase de movimentação dos sapos. Já conhecemos as variáveis do método, então não entraremos em detalhes sobre elas novamente. Nesta parte do código, os saltos dos sapos são implementados de acordo com o passo individual de cada sapo. No primeiro passo, o sapo salta em direção ao líder local, e a tentativa é considerada bem-sucedida se a posição do sapo melhorar; caso contrário, o contador de passos é incrementado. Ou seja, um número fixo de tentativas é alocado para saltos em direção ao líder local, conforme os parâmetros externos do algoritmo.

Para o sapo líder, um princípio diferente de movimento é utilizado em comparação com todos os outros no memplexo. O líder simplesmente realiza saltos em uma direção aleatória dentro de uma pequena vizinhança de sua posição.

Em contraste com o líder, todos os outros sapos realizam saltos em direção ao líder usando a seguinte fórmula:

coord = mems[m].frogs[frgs].cPrev[c] + rnd * vect[c] * ((mems[m].cBest[c] - mems[m].frogs[frgs].cPrev[c]) / eDistance);

A fórmula indica que a nova coordenada do sapo será obtida movendo-se em direção ao líder pela distância entre eles, normalizada pela distância euclidiana em todas as coordenadas, introduzindo-se uma componente aleatória rnd.

else
{
  int cnt = 0;
  double eDistance = 0.0; //euclidean distance
  double coordDiff = 0.0; //the difference in coordinates

  for  (int m = 0; m < numbMems; m++)
  {
    for (int frgs = 0; frgs < memsFrogs; frgs++)
    {
      //2.1 move the frogs towards the best one in the memeplex-----------------
      if (mems [m].frogs [frgs].frogStep < frogStepsToLocalMax)
      {
        if (mems [m].frogs [frgs].fPrev != -DBL_MAX && mems [m].fBest != -DBL_MAX)
        {
          if (mems [m].frogs [frgs].fPrev == mems [m].fBest)
          {
            for (int c = 0; c < coordinatesNumber; c++)
            {
              rnd = RNDfromCI (-1.0, 1.0);
              rnd = rnd < 0.0 ? -rnd * rnd : rnd * rnd;
              coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * 0.2;
              mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
            }
          }
          else
          {
            eDistance = 0.0;
            coordDiff = 0.0;

            //calculate Euclidean distance----------------------------------
            for (int c = 0; c < coordinatesNumber; c++)
            {
              coordDiff  = mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c];
              coordDiff *= coordDiff;
              eDistance += coordDiff;
            }

            eDistance = sqrt (eDistance);

            for (int c = 0; c < coordinatesNumber; c++)
            {
              rnd = RNDfromCI (-1.0, 1.0);
              coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((mems [m].cBest [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);
              mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
            }
          }
        }
        else
        {
          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);
            rnd = rnd < 0.0 ? -rnd * rnd : rnd * rnd;
            coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c];
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
      }
      else
      {
        //2.2 move towards global if the move is worse than the previous one-----
        if (mems [m].frogs [frgs].frogStep /*==*/ >= frogStepsToLocalMax)
        {
          eDistance = 0.0;
          coordDiff = 0.0;

          //calculate Euclidean distance------------------------------------
          for (int c = 0; c < coordinatesNumber; c++)
          {
            coordDiff  = cB [c] - mems [m].frogs [frgs].cPrev [c];
            coordDiff *= coordDiff;
            eDistance += coordDiff;
          }

          eDistance = sqrt (eDistance);

          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);
            coord = mems [m].frogs [frgs].cPrev [c] + rnd * vect [c] * ((cB [c] - mems [m].frogs [frgs].cPrev [c]) / eDistance);
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
        //2.3 move randomly across the field --------------------------------
        else
        {
          for (int c = 0; c < coordinatesNumber; c++)
          {
            rnd = RNDfromCI (-1.0, 1.0);

            coord    = RNDfromCI (rangeMin [c], rangeMax [c]);
            mems [m].frogs [frgs].c [c] = SeInDiSp (coord, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
      }

      frogs [cnt] = mems [m].frogs [frgs];
      cnt++;
    }
  }


  //--------------------------------------------------------------------------
  numbCyclesCNT++;
}

O método Revision é destinado a determinar o líder global em cada iteração do algoritmo e identificar os líderes locais. Se o número de ciclos alocados para os movimentos dos sapos dentro de cada memplexo estiver esgotado, então procede-se ao embaralhamento - os sapos são redistribuídos aleatoriamente entre os memplexos, permitindo assim a troca de informações entre eles. Este método também considera os passos correspondentes dos saltos - para onde o sapo se moverá na próxima iteração (em direção ao líder local ou global ou em uma direção aleatória no espaço de busca).

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SFL::Revision ()
{
  //4.1 determine the globally best one by population-------------------------------
  for (int i = 0; i < frogsNumber; i++)
  {
    if (frogs [i].f > fB)
    {
      fB = frogs [i].f;
      ArrayCopy (cB, frogs [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  int cnt = 0;

  //if the last loop=========================================================
  if (numbCyclesCNT >= numbCycles)
  {
    //4.2.0 reset the memeplex cycle counter-----------------------------------
    numbCyclesCNT = 0;

    //4.2.1 generate random indices--------------------------------------
    for (int i = 0; i < frogsNumber; i++) indexes [i] = i;

    Shuffle (indexes, frogsNumber);

    //4.2.2 copy to memeplexes accidentally------------------------------------
    for  (int m = 0; m < numbMems; m++)
    {
      mems [m].fBest = -DBL_MAX;

      for (int frgs = 0; frgs < memsFrogs; frgs++)
      {
        mems [m].frogs [frgs] = frogs [indexes [cnt]];
        cnt++;

        //4.2.3 determine the best one in each memeplex---------------------------
        if (mems [m].frogs [frgs].f > mems [m].fBest)
        {
          mems [m].fBest = mems [m].frogs [frgs].f;
          ArrayCopy (mems [m].cBest, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
        }

        //4.2.4 reset frogs' fitness and step------------------------
        mems [m].frogs [frgs].f        = -DBL_MAX;
        mems [m].frogs [frgs].fPrev    = -DBL_MAX;
        mems [m].frogs [frgs].frogStep = 0;
      }
    }
  }
  //if NOT the last cycle======================================================
  else
  {
    for  (int m = 0; m < numbMems; m++)
    {
      for (int frgs = 0; frgs < memsFrogs; frgs++)
      {
        mems [m].frogs [frgs].frogStep++;

        //4.3.1 copy the fitness and coordinates of frogs from the population to the
        //corresponding frog memeplexes
        mems [m].frogs [frgs].f = frogs [cnt].f;
        ArrayCopy (mems [m].frogs [frgs].c, frogs [cnt].c, 0, 0, WHOLE_ARRAY);

        //4.3.2 determine the best one in each memeplex---------------------------
        if (frogs [cnt].f > mems [m].fBest)
        {
          mems [m].fBest = frogs [cnt].f;
          ArrayCopy (mems [m].cBest, frogs [cnt].c, 0, 0, WHOLE_ARRAY);
        }

        //4.3.3 determine the direction of the next jump------------------------
        if (mems [m].frogs [frgs].frogStep <= frogStepsToLocalMax)
        {
          if (mems [m].frogs [frgs].f > mems [m].frogs [frgs].fPrev)
          {
            mems [m].frogs [frgs].fPrev = mems [m].frogs [frgs].f;
            ArrayCopy (mems [m].frogs [frgs].cPrev, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
            mems [m].frogs [frgs].frogStep = 0;
          }
        }
        else
        {
          if (mems [m].frogs [frgs].frogStep >= frogStepsToLocalMax + 1)
          {
            if (mems [m].frogs [frgs].f > mems [m].frogs [frgs].fPrev)
            {
              mems [m].frogs [frgs].fPrev = mems [m].frogs [frgs].f;
              ArrayCopy (mems [m].frogs [frgs].cPrev, mems [m].frogs [frgs].c, 0, 0, WHOLE_ARRAY);
              mems [m].frogs [frgs].frogStep = 0;
            }
          }
          else
          {
            mems [m].frogs [frgs].f        = -DBL_MAX;
            mems [m].frogs [frgs].fPrev    = -DBL_MAX;
            mems [m].frogs [frgs].frogStep = 0;
          }
        }

        cnt++;
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

No algoritmo de otimização SFL, precisaremos misturar os sapos entre os memplexos de forma aleatória. A tarefa de embaralhamento aleatório é interessante porque sua solução algorítmica não é trivial, no entanto, graças a Ronald Fisher e Frank Yates, o mundo recebeu um algoritmo eficaz e rápido. Anteriormente, não usávamos tal conceito em artigos, pois não havia necessidade. Ele é amplamente utilizado em ciências da computação, especialmente nas áreas de algoritmos genéticos, criptografia e estatística.

As principais vantagens do algoritmo Fisher-Yates são:
1. Simplicidade de implementação: O algoritmo de Fisher-Yates é facilmente implementável em qualquer linguagem de programação. Não requer cálculos matemáticos complexos ou bibliotecas especiais.
2. Eficiência: O algoritmo de Fisher-Yates opera em tempo linear, ou seja, o tempo de execução depende do número de elementos que precisam ser reorganizados. Isso o torna muito eficiente para grandes conjuntos de dados.
3. Aleatoriedade: O algoritmo de Fisher-Yates proporciona uma alta aleatoriedade nas permutações. Isso é importante para muitas aplicações, como testes aleatórios, criptografia e simulações.
4. Independência dos dados de entrada: O algoritmo de Fisher-Yates pode ser aplicado a qualquer conjunto de dados sem a necessidade de conhecer sua estrutura ou propriedades. Isso o torna uma ferramenta universal para muitas tarefas.
5. Pseudoaleatoriedade: O algoritmo de Fisher-Yates gera permutações pseudoaleatórias que podem ser usadas em muitas aplicações onde a aleatoriedade é requerida, mas não necessariamente a verdadeira aleatoriedade.

Em geral, o algoritmo de Fisher-Yates é interessante por sua simplicidade, eficiência e universalidade. Ele é uma ferramenta útil para muitas tarefas que envolvem aleatoriedade e permutações de dados.

//——————————————————————————————————————————————————————————————————————————————
void Shuffle (int & arr [], int size)
{
  int index, temp;
  for (int i = size - 1; i > 0; i--)
  {
    index = MathRand () % (i + 1);
    temp = arr [i];
    arr [i] = arr [index];
    arr [index] = temp;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultados dos testes

Impressão do desempenho do salto de sapo embaralhado na bancada de teste:

C_AO_SFL:50;25;15;5;0.7
=============================
5 Rastrigin's; Func runs 10000 result: 66.52578871476199
Score: 0.82429
25 Rastrigin's; Func runs 10000 result: 52.38937199890908
Score: 0.64913
500 Rastrigin's; Func runs 10000 result: 44.5591163558836
Score: 0.55211
=============================
5 Forest's; Func runs 10000 result: 0.5762718670482314
Score: 0.32597
25 Forest's; Func runs 10000 result: 0.16329693292687839
Score: 0.09237
500 Forest's; Func runs 10000 result: 0.04968320483668511
Score: 0.02810
=============================
5 Megacity's; Func runs 10000 result: 3.1599999999999997
Score: 0.26333
25 Megacity's; Func runs 10000 result: 1.016
Score: 0.08467
500 Megacity's; Func runs 10000 result: 0.3004
Score: 0.02503
=============================
All score: 2.84501

Ao observar a animação do funcionamento do algoritmo SFL, não se detecta nenhum agrupamento por memes individuais, embora o contrário fosse esperado. Os agentes (pontos) de otimização estão distribuídos pelo campo de forma caótica, e não há padrões no movimento das partículas. É imediatamente aparente a baixa qualidade de convergência do algoritmo, que, infelizmente, se manifesta em ficar preso em extremos locais, o que pode ser identificado por longos trechos suaves no gráfico de convergência. No entanto, com o aumento no número de parâmetros otimizados, a "degrau" diminui.

  SFL na função de teste Rastrigin.

  SFL na função de teste Forest.

  SFL na função de teste Megacity.

Vamos às conclusões. Ao analisar a tabela com os resultados dos testes dos algoritmos, pode-se notar que o algoritmo SFL mostra resultados abaixo da média em termos de otimização. Embora na função suave de Rastrigin o SFL tenha alguma vantagem, ela não é suficiente para recomendá-lo como o algoritmo preferencial para funções suaves. Nas funções com descontinuidades Forest e Megacity, o algoritmo salto de sapo embaralhado demonstra resultados piores em comparação com as funções suaves. Isso pode ser explicado pelo fato de que, em trechos suaves da função otimizada, os saltos dos sapos não melhoram sua posição, e elas constantemente retornam ao ponto de partida, sem ter a oportunidade de "se agarrar" ao relevo.

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	saplings sowing and growing	1.00000	1.00000	0.55665	2.55665	0.72740	0.94522	1.00000	2.67262	0.76364	0.85977	1.00000	2.62340	100.000
HS	harmony search	0.99676	0.95282	0.48178	2.43136	1.00000	0.98931	0.44806	2.43736	1.00000	1.00000	0.41537	2.41537	92.329
ACOm	ant colony optimization M	0.34611	0.17985	0.17044	0.69640	0.86888	1.00000	0.77362	2.64249	1.00000	0.88930	0.05606	1.94536	65.347
IWO	invasive weed optimization	0.95828	0.67083	0.29807	1.92719	0.70773	0.46349	0.31773	1.48896	0.80000	0.42067	0.33289	1.55356	61.104
COAm	cuckoo optimization algorithm M	0.92400	0.46794	0.26004	1.65199	0.58378	0.34034	0.16526	1.08939	0.72727	0.33025	0.17083	1.22835	47.612
FAm	firefly algorithm M	0.59825	0.33980	0.17135	1.10941	0.51073	0.42299	0.49790	1.43161	0.34545	0.28044	0.35258	0.97847	41.537
ABC	artificial bee colony	0.78170	0.32715	0.20822	1.31707	0.53837	0.21455	0.13344	0.88636	0.56364	0.26569	0.13926	0.96858	36.849
GSA	gravitational search algorithm	0.70167	0.45217	0.00000	1.15384	0.31660	0.36416	0.33204	1.01280	0.59395	0.35054	0.00000	0.94448	36.028
BA	bat algorithm	0.40526	0.63761	0.84451	1.88738	0.20841	0.17477	0.25989	0.64308	0.29698	0.09963	0.17371	0.57032	35.888
BFO	bacterial foraging optimization	0.67203	0.30963	0.11813	1.09979	0.39702	0.26623	0.20652	0.86976	0.52122	0.33211	0.18932	1.04264	34.693
EM	electroMagnetism-like algorithm	0.12235	0.46278	1.00000	1.58513	0.00000	0.03498	0.34880	0.38377	0.00000	0.00000	0.10924	0.10924	22.091
SFL	shuffled frog-leaping	0.40072	0.23739	0.26548	0.90360	0.20153	0.04147	0.02652	0.26952	0.27273	0.05535	0.06639	0.39446	15.203
MA	monkey algorithm	0.33192	0.33451	0.14644	0.81287	0.10012	0.07891	0.08932	0.26836	0.21818	0.04243	0.10720	0.36781	13.603
FSS	fish school search	0.46812	0.25337	0.11302	0.83451	0.12840	0.05013	0.06516	0.24369	0.16971	0.04796	0.08283	0.30050	12.655
PSO	particle swarm optimisation	0.20449	0.08200	0.07160	0.35809	0.18895	0.10486	0.21738	0.51119	0.23636	0.05903	0.01957	0.31496	10.031
RND	random	0.16826	0.09743	0.08019	0.34589	0.13496	0.04810	0.04715	0.23021	0.16971	0.03875	0.04922	0.25767	5.302
GWO	grey wolf optimizer	0.00000	0.00000	0.02256	0.02256	0.06570	0.00000	0.00000	0.06570	0.32727	0.07378	0.02557	0.42663	1.000

Considerações finais

O SFL é mais uma "camada adicional" para outros algoritmos de otimização, que pode ser usada como lógica de movimentação dos agentes nos memplexos. O SFL foi originalmente inventado como uma metodologia para melhorar a qualidade da otimização de algoritmos já existentes. Como um algoritmo de otimização independente, o SFL mostra resultados abaixo da média entre os algoritmos populacionais analisados anteriormente. O SFL oferece amplas oportunidades para experimentação com a combinação de etapas lógicas no algoritmo, melhorando tanto a pesquisa quanto a explotação. O SFL possui alta flexibilidade e adaptabilidade, tornando-o adequado para uso especializado em tarefas de otimização específicas.

O histograma dos resultados dos testes dos algoritmos na Figura 3 (na escala de 0 a 100, quanto maior, melhor, no arquivo o script para calcular a tabela de classificação pelo método neste artigo).

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

Prós e contras do algoritmo salto de sapo embaralhado (SFL):

Prós:
1. Pequeno número de parâmetros externos.
2. Originalidade da arquitetura do algoritmo, possibilidade de usar em memes outros algoritmos de otimização.

Contras:
1. Alta complexidade computacional.
2. Resultados não muito altos em funções suaves e discretas.
3. Tendência a ficar preso em funções com plataformas horizontais planas.

A cada artigo, anexo um arquivo contendo versões atualizadas e relevantes dos códigos dos algoritmos descritos nos artigos anteriores. Os artigos são baseados na experiência acumulada do autor e em sua opinião pessoal, e as conclusões e julgamentos são baseados nos resultados dos experimentos realizados.