Algoritmos de otimização populacionais: Busca por cardume de peixes (FSS - Fish School Search)

Conteúdo

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

1. Introdução

Um cardume de peixes é um termo geral para qualquer grupo de peixes reunidos em um local específico. Os cardumes podem ser classificados como estruturados ou não estruturados. Cardumes não estruturados podem consistir em indivíduos de diferentes espécies e tamanhos, reunidos aleatoriamente próximo a recursos locais, como alimentos ou locais de nidificação.

Por outro lado, um grupo de peixes que se mantém unido por motivos sociais constitui um cardume. A maioria dos indivíduos se encontra na mesma fase do ciclo de vida, mantém contato ativo uns com os outros e, a qualquer momento, pode exibir atividades biologicamente ativas e organizadas benéficas para os membros do grupo.
Diferentemente do comportamento individual, o estilo de vida gregário é um equilíbrio entre a vantagem de viver em grupo, em termos de maior proteção contra predadores, e o aumento da competição na busca por alimento.

Na natureza, os peixes formam cardumes com base em vários critérios. Em geral, preferem cardumes maiores, compostos exclusivamente por indivíduos de sua própria espécie. Qualquer membro do cardume que se destaque em sua aparência ou apresente diferenças se tornará um alvo preferencial para os predadores. Esse fato explica por que os peixes preferem cardumes formados por indivíduos idênticos. Dessa forma, é estabelecida a completa homogeneidade do cardume.

Um cardume é organizado de maneira bastante rígida quando os peixes nadam sincronizadamente, com a mesma velocidade e na mesma direção. Isso ocorre não apenas com peixes da mesma espécie, mas também da mesma idade e tamanho, que se movem a uma certa distância uns dos outros. Os cardumes de peixes são capazes de realizar manobras complexas, como se possuíssem uma inteligência coletiva e uma mente compartilhada.
As nuances da formação de cardumes estão longe de ser totalmente compreendidas, especialmente no que diz respeito aos aspectos de movimentação e métodos de alimentação dos peixes.

Diversas hipóteses foram propostas para explicar o comportamento dos cardumes, incluindo melhor orientação, sincronização da caça, confusão de predadores e redução do risco de ser capturado. Os peixes em cardumes parecem compartilhar informações entre si, controlando o comportamento uns dos outros de perto. O comportamento alimentar de um peixe estimula rapidamente a busca ativa por comida nos outros indivíduos. Peixes em cardumes nadam em formações organizadas, muitas vezes realizando subidas e descidas rápidas e girando em torno de seu próprio eixo. Enquanto isso, eles mudam a forma do cardume, evitando colisões entre si. Para realizar tais manobras, é necessária uma resposta rápida e eficiente. Um estilo de vida gregário pressupõe que os peixes possuam sistemas sensoriais capazes de responder instantaneamente a pequenas mudanças em sua posição em relação aos vizinhos.

Para obter uma compreensão mais abrangente, utiliza-se a modelagem matemática desse comportamento de cardume. Os modelos matemáticos mais comuns pressupõem que os animais individuais em um cardume sigam três regras básicas:

1. Mover-se na mesma direção que seu vizinho
2. Permanecer próximo aos vizinhos
3. Evitar colisões com indivíduos próximos

Ainda não se resolveu a questão de como os peixes em cardumes escolhem a direção na qual nadam. Durante as migrações, parece que a maioria dos membros do cardume sabe para onde se dirigir.  Se todos os membros do cardume estiverem igualmente cientes da disponibilidade de alimento, ainda haverá líderes no grupo que serão mais ousados do que seus parentes. Esse comportamento de agrupamento inspirou muitos pesquisadores a desenvolver não apenas modelos matemáticos, mas também algoritmos para resolver diversos problemas de otimização.

2. Descrição do algoritmo

A busca por cardume de peixes (FSS - Fish School Search) é uma subfamília de algoritmos de inteligência de enxame pertencente à classe dos algoritmos meta-heurísticos, proposta por Bastos Filho e Lima Neto em 2008 e publicada pela primeira vez em 2009. No FSS, os agentes simples são chamados de peixes, e cada peixe possui um peso que representa o "sucesso" alcançado durante a busca. Os valores e variações dos pesos afetam os movimentos individuais e coletivos. Mecanismos integrados de alimentação e ações coordenadas fazem com que o cardume se mova na direção do gradiente positivo para ganhar peso e encontrar os melhores pontos nos níveis local e global. O FSS foi desenvolvido para problemas de otimização contínua em espaços de busca multimodais. Isso também motivou outros pesquisadores a propor soluções para outros problemas, como otimização em problemas binários e otimização multiobjetivo.

No algoritmo FSS, pode-se simplificar imaginando que os peixes nadam em um aquário hipotético, cujas paredes representam os limites do domínio de definição da função em análise. O peso dos peixes caracteriza seu sucesso na busca por alimento (soluções) e atua como a memória do peixe. A presença do peso nos peixes é a ideia principal do algoritmo e a distingue de um enxame de partículas. Essa característica do algoritmo FSS elimina a necessidade de encontrar e fixar as melhores soluções globalmente, como ocorre em um enxame de partículas.

Os operadores do algoritmo FSS são agrupados em dois grupos:
- operador de alimentação que estabelece o sucesso das áreas de estudo
- operadores de natação que implementam algoritmos de migração para cada peixe e para o cardume

O operador de alimentação corresponde ao cálculo do peso do peixe. A ideia principal é fazer com que os peixes "nadem" em direção a um gradiente positivo para "comer" e "ganhar peso". Coletivamente, os peixes mais pesados exercem uma maior influência no processo geral de busca, levando o centro de massa do cardume a se deslocar em direção a melhores localizações no espaço de busca ao longo das iterações. O incremento de peso em uma determinada iteração é proporcional à diferença normalizada nos valores da função de adaptação, ou seja:

fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);

Onde:

• weight - peso do peixe
• delta_fitness - diferença entre os valores da função de adaptação
  
• max_delta_fitness - valor máximo da diferença na função de adaptação entre todos os peixes

Os operadores de natação são divididos em três tipos, de acordo com o tipo de movimento:

- Individual;

- Instintivo-coletivo;

- Coletivo-voluntário;

A natação individual pode ser interpretada como uma busca local nas proximidades da posição atual do peixe. O vetor de movimento de cada indivíduo é direcionado aleatoriamente e possui magnitudes diferentes.

fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;

Onde:

• new_position - nova posição na coordenada correspondente
• current_position - posição atual na coordenada correspondente
• step_ind - passo de movimento individual, calculado como

initial_step_ind * (rangeMax[d] - rangeMin[d]);

Onde:

• initial_step_ind - parâmetro de algoritmo para movimento individual
• rangeMax e rangeMin - intervalos de valores de argumentos a serem otimizados
  
• r - número aleatório no intervalo [-1,0;1,0]

Esquematicamente, a natação individual é ilustrada na Figura 1.

Figura 1. Natação individual. O vetor de deslocamento de cada peixe é direcionado aleatoriamente e possui um valor escalar diferente.

Após a natação individual, a função de adaptação é medida. Se, como resultado do movimento individual, a posição do peixe não melhorou, consideramos que esse peixe em particular não teve nenhum movimento e permanece no lugar. Ou seja, apenas os peixes que melhoraram suas funções de adaptação se moverão para uma nova posição.

Após a natação individual, o operador do movimento instintivo-coletivo é executado. Vamos observar primeiro a Figura 2.

Figura 2. Natação instintiva-coletiva. O movimento é caracterizado para todos os peixes pelo mesmo vetor de direção e magnitude em relação ao centro de massa G.

A natação instintiva-coletiva serve para corrigir a posição geral do cardume, levando em consideração a mudança na função de aptidão de cada peixe na iteração anterior. As novas coordenadas são calculadas da seguinte forma:

fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];

Onde:

• new_position - nova posição do peixe na coordenada correspondente
• current_position - posição atual do peixe na coordenada correspondente
• collective_instinct - quantidade de movimento ao longo da coordenada correspondente, calculada como:

collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

Onde:

• delta_position - diferença entre as coordenadas atuais e as anteriores, obtida na etapa de natação individual
• delta_fitness - mudança na função de aptidão da posição atual e da anterior na fase de natação individual

A natação instintiva-coletiva formaliza o movimento sincrônico grupal do cardume para um novo local, proporcionando a busca de novos locais de alimentação, enquanto o movimento individual permite melhorar a situação localmente.

A seguir, vamos considerar a natação coletiva-volitiva. Ela, por sua vez, é dividida em dois tipos:

- a partir do centro de massa, isto é, se não houver melhoria na posição geral do cardume em relação à posição anterior, os peixes se espalham para os lados, simbolizando a busca contínua por alimento (Figura 3)

- movimento em direção ao centro de massa, se houver melhoria. Nesse caso, os peixes se movem em direção ao centro de massa, apertando o anel e simbolizando o ataque à presa. Algoritmicamente, isso significa refinar a solução do problema de otimização (Figura 4).

Figura 3. Natação coletiva-volitiva. Os vetores diretores têm como origem o centro de massa G e são direcionados a partir dele.

Figura 4. Natação coletiva-volitiva. Os vetores diretores são direcionados em direção ao centro de massa G.

Para o cálculo da natação coletiva-volitiva, é utilizado o conceito de centro de massa. A partir daí, a fórmula para calcular a natação coletiva-volitiva ficará da seguinte forma:

fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);

Onde:

• pos - current_positionl (posição atual)
• search_operator - 1 se o movimento anterior resultou em uma melhoria de posição e -1 se não
  
• 
  
• step_vol [d] - passo do movimento coletivo, calculado como:

step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);

Onde:

• initial_step_vol - parâmetro de algoritmo para movimento coletivo
• 
  
• barycenter [d] - centro de massa, que é calculado como a soma dos pesos dos peixes multiplicada pela coordenada:

barycenter [d] += fishes [f].weight * fishes [f].current_position [d];

e dividido pelo peso total do cardume:

barycenter [d] /= current_total_weight;

Pseudocódigo do algoritmo:

1) Inicializar as posições dos peixes com números aleatórios.

2) Movimentos individuais.

3) Cálculo da função de aptidão.

4) Redefinir os pesos para cada peixe.

5) Movimento instintivo-coletivo.

6) Movimento volitivo-coletivo.

7) Recalcular o peso total.

8) Recalcular a função de adaptação.

9) Repetir a partir do passo 2) até que o critério de parada seja atingido.

Figura 5. Diagrama de blocos do algoritmo FSS.

Vamos começar descrevendo o código.

A unidade lógica mais simples do algoritmo, como se pode imaginar, é a estrutura que descreve o peixe. Como precisaremos inicializar o peixe várias vezes, é aconselhável "zerar" essa estrutura, devido ao seu tamanho relativamente grande, no método especial Init(), o que permitirá otimizar um pouco o código. Essa estrutura inclui matrizes de coordenadas para a posição atual, nova posição e a diferença nas coordenadas desde o último movimento. Há também uma variável de peso, que por padrão é igual a 1000 unidades arbitrárias - em princípio, esse valor pode ser qualquer. O peixe também é caracterizado pelo valor do fitness atual, o anterior e a diferença entre eles. No método Init(), o fitness é inicializado com o menor valor possível para um número double, e a diferença de fitness é igual a zero, já que o peixe ainda não se moveu.

//——————————————————————————————————————————————————————————————————————————————
struct S_Fish
{
  void Init (int dimensions)
  {
    ArrayResize (current_position, dimensions);
    ArrayResize (new_position,     dimensions);
    ArrayResize (delta_position,   dimensions);
    weight        = 1000.0;
    fitness       = -DBL_MAX;
    delta_fitness = 0.0;
  }

  double current_position [];
  double new_position     [];
  double delta_position   [];
  double weight;
  double fitness;
  double new_fitness;
  double delta_fitness;
};
//——————————————————————————————————————————————————————————————————————————————

Vamos declarar a classe C_AO_FSS, que é um cardume de peixes, representando matematicamente um modelo de comunidade natural. Não há nada incomum aqui; também existem dois métodos públicos necessários para interagir com o programa do usuário, os intervalos de valores da função a ser otimizada - necessários para levar em consideração as coordenadas dos peixes e a interação no cardume - e os arrays.

No método público da classe de inicialização Init(), é necessário redefinir as variáveis para seus valores originais e alocar memória para os arrays. É importante prestar atenção especial às variáveis init e SwimmingRegime. Ocorre que, conforme o pseudocódigo que analisamos, o cálculo da função de adaptação é realizado duas vezes: a primeira após um movimento individual e a segunda após dois tipos de movimentos coletivos. Isso contradiz o esquema de vinculação de aplicativo de algoritmo adotado por nós, no qual, a cada iteração, deve haver uma sequência: first_method -> calculate_fitness_functions -> second_method. Para corrigir isso e alterar a sequência de ações no algoritmo canônico, essas duas variáveis servem justamente. A variável init, no início do algoritmo, deve ser falsa. Esse é um sinalizador que indica a necessidade de inicializar o peixe, calcular a função de adaptação e realizar o movimento novamente, já que toda a lógica do algoritmo utiliza a diferença entre o valor atual e o anterior das coordenadas e da função de adaptação. Caso contrário, não conseguiríamos obter a diferença entre os valores. O segundo sinalizador importante é o SwimmingRegime, que nos permite redefinir a ordem de chamada dos métodos que descrevem o movimento dos peixes, de modo a corresponder ao nosso esquema. O valor 1 corresponde à chamada de natação "individual"; caso contrário, a sequência de movimentos em grupo, conforme analisamos anteriormente.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Init (const int    dimensionsP,
                     const int    fishSchSizeP,
                     const double initial_step_indP,
                     const double initial_step_volP)
{
  MathSrand (GetTickCount ());
  init = false;
  swimmingRegime = 1;

  dimensions     = dimensionsP;

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

  num_of_individuos = fishSchSizeP;

  ArrayResize (fishes, num_of_individuos);

  for (int i = 0; i < num_of_individuos; i++)
  {
    fishes [i].Init (dimensions);
  }

  global_best = -DBL_MAX;
  ArrayResize (global_best_position, dimensions);

  total_weight     = num_of_individuos;

  initial_step_ind = initial_step_indP;
  ArrayResize (step_ind, dimensions);

  initial_step_vol = initial_step_volP;
  ArrayResize (step_vol, dimensions);

  ArrayResize (collective_instinct, dimensions);
  ArrayResize (barycenter, dimensions);
}
//——————————————————————————————————————————————————————————————————————————————

O primeiro método público chamado a cada iteração, Swimming(), determina a sequência de chamadas para movimentos individuais e coletivos dos peixes. Se o método for chamado pela primeira vez, as etapas de movimento individual e em grupo são inicializadas como parte da faixa possível ao longo da coordenada correspondente, utilizando dois parâmetros do algoritmo: initial_step_ind e initial_step_vol. Alguns autores recomendam definir os valores para 0,01 e 0,001, respectivamente. No entanto, não obtive bons resultados com esses valores e utilizo 0,1 e 0,8. Adicionalmente, na primeira execução do algoritmo, o valor atual das coordenadas da posição dos peixes é inicializado com números aleatórios dentro da faixa dos parâmetros otimizados. Nas chamadas subsequentes ao método, os tipos de movimento correspondentes serão chamados de acordo com o sinalizador SwimmingRegime.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Swimming (int i)
{
  //----------------------------------------------------------------------------
  if (!init)
  {
    global_best    = -DBL_MAX;
    swimmingRegime = 1;

    for (int d = 0; d < dimensions; d++)
    {
      step_ind [d] = initial_step_ind * (rangeMax [d] - rangeMin [d]);
      step_vol [d] = initial_step_vol * (rangeMax [d] - rangeMin [d]);
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      fishes [f].Init (dimensions);

      for (int d = 0; d < dimensions; d++)
      {
        fishes [f].new_position [d] = RNDfromCI (rangeMin [d], rangeMax [d]);
        fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
      }
    }
  }
  //----------------------------------------------------------------------------
  else
  {
    switch (swimmingRegime)
    {
    case 1:
      apply_individual_movement ();            //individual movement
      break;
    default:
      apply_instintive_collective_movement (); //instinctively-collective movement
      apply_collective_volitive_movement ();   //collective-volitional movement
      update_total_weight ();                  //recalculate the total weight
      break;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O segundo método público, chamado a cada iteração - Regrouping(), tem como objetivo principal determinar a ordem de chamadas dos métodos de natação individual, coletivo-instintivo e coletivo-volitivo. A funcionalidade adicional do método para garantir a ordem das chamadas é o sinalizador SwimmingRegime, que assume os valores 1 e 2. Isso é necessário para redefinir a ordem de chamada dos métodos de movimentação dos peixes na versão clássica para o esquema adotado por nós: first_open_method -> calculate_fitness_function -> second_open_method. Dependendo do sinalizador Init, se o algoritmo estiver na primeira iteração, armazenaremos a posição atual das coordenadas e o valor da função de adaptação para cálculos posteriores de suas diferenças, uma vez que se presume que o método seja chamado após o cálculo da função de adaptação. Se o sinalizador Init indicar que o algoritmo está na segunda iteração e nas subsequentes, após um movimento individual, é necessário obter a diferença entre os valores atuais e anteriores da função de adaptação, bem como a diferença entre as coordenadas das posições atuais e anteriores. As diferenças são calculadas sob a condição de que a posição tenha melhorado; caso contrário, consideramos que não houve movimento, redefinimos os valores do peso do peixe para o estado inicial, e as diferenças nos movimentos e nas funções de adaptação são consideradas iguais a zero. Atualizamos imediatamente a melhor solução, se for alcançada, chamando o método updates_optimal_solution() e aplicamos a alimentação do peixe com o método apply_feeding(). Se o sinalizador SwimmingRegime não for igual a 1, então os movimentos coletivos-instintivos e coletivos-volitivos foram aplicados; após sua execução, definimos o SwimmingRegime como 1 e o próximo movimento será individual.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::Regrouping ()
{
  //----------------------------------------------------------------------------
  if (swimmingRegime == 1
  {
    if (!init)
    {
      for (int f = 0; f < num_of_individuos; f++)
      {
        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
        ArrayInitialize (fishes [f].delta_position, 0.0);

        fishes [f].fitness = fishes [f].new_fitness;
        fishes [f].delta_fitness = 0.0;
      }

      init = true;
      return;
    }

    for (int f = 0; f < num_of_individuos; f++)
    {
      //remember the best position for the fish
      if (fishes [f].new_fitness > fishes [f].fitness)
      {
        fishes [f].delta_fitness = fishes [f].new_fitness - fishes [f].fitness; //fabs
        fishes [f].fitness = fishes [f].new_fitness;

        for (int d = 0; d < dimensions; d++)
        {
          fishes [f].delta_position [d] = fishes [f].new_position [d] - fishes [f].current_position [d];
        }

        ArrayCopy (fishes [f].current_position, fishes [f].new_position, 0, 0, WHOLE_ARRAY);
      }
      else
      {
        ArrayInitialize (fishes [f].delta_position, 0.0);
        fishes [f].delta_fitness = 0.0;
      }
    }

    swimmingRegime = 2;
    updates_optimal_solution ();
    apply_feeding ();
    return;
  }

  //----------------------------------------------------------------------------
  swimmingRegime = 1;
  updates_optimal_solution ();
}
//——————————————————————————————————————————————————————————————————————————————

O próximo método privado simples serve para atualizar os melhores resultados do algoritmo, caso sejam alcançados. Para fazer isso, basta comparar os valores da função de aptidão de cada peixe com os valores globais. Se for melhor, o salvamos.

//——————————————————————————————————————————————————————————————————————————————
//обновить лучшее общее решение
void C_AO_FSS::updates_optimal_solution ()
{
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].fitness > global_best)
    {
      global_best = fishes [f].fitness;
      ArrayCopy (global_best_position, fishes [f].current_position, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método privado responsável pelo nado individual tem a fórmula já analisada anteriormente, sendo bastante simples: adicionamos às coordenadas atuais de cada peixe um passo individual multiplicado por um número aleatório no intervalo de -1,0 a 1,0, o que resulta em incrementos tanto na direção positiva quanto na negativa. Se ultrapassar os limites do intervalo dos parâmetros otimizados, atribuímos o valor limite à coordenada.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_individual_movement ()
{
  //передвинем рыб на новые места-----------------------------------------------
  double r = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (-1.0, 1.0);

      fishes [f].new_position [d] = fishes [f].current_position [d] + step_ind [d] * r;
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método de alimentação não deve causar dificuldades de compreensão, uma vez que o peso do peixe é determinado como o quociente entre a diferença da função de aptidão do próprio peixe e o valor máximo de diferença entre todo o cardume. No entanto, pode ocorrer de a diferença máxima entre todos os peixes ser igual a zero. Na descrição da versão clássica do algoritmo, é mencionado que o peso do peixe deve ser sempre positivo, e geralmente são considerados apenas os casos em que a função de aptidão assume valores positivos. Contudo, não há um sentido prático nessa exigência, e é admitido que o peso do peixe possa assumir valores negativos. Sendo assim, se a diferença máxima da função de aptidão (usada para normalizar o peso de cada peixe) for igual a zero entre todos os peixes, o peso do peixe é considerado igual a 1.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_feeding ()
{
  double max_delta_fitness = -DBL_MAX;

  //find the maximum weight among fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (fishes [f].delta_fitness > max_delta_fitness) max_delta_fitness = fishes [f].delta_fitness;
  }

  //feed the fish
  for (int f = 0; f < num_of_individuos; f++)
  {
    if (max_delta_fitness != 0.0)
    {
      fishes [f].weight = fishes [f].weight + (fishes [f].delta_fitness / max_delta_fitness);
    }
    else fishes [f].weight = 1;
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método privado de movimento instintivo-coletivo envolve alterar as coordenadas de cada peixe, incrementando-as com o valor do instinto coletivo, que, por sua vez, consiste no produto da diferença das posições nas iterações atual e anterior pela diferença da função de aptidão alcançada nos movimentos anteriores. Ao ultrapassar os limites dos parâmetros otimizados, atribuímos os valores dos limites.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_instintive_collective_movement ()
{
  double sum_delta_fitness = 0.0;
  for (int f = 0; f < num_of_individuos; f++)
  {
    sum_delta_fitness += fishes [f].delta_fitness;
  }

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      collective_instinct [d] = fishes [f].delta_position [d] * fishes [f].delta_fitness;

      if (sum_delta_fitness != 0.0)
      {
        collective_instinct [d] /= sum_delta_fitness;
      }

      fishes [f].new_position [d] = fishes [f].current_position [d] + collective_instinct [d];
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método privado de natação volitiva coletiva calcula o centro de massa do cardume e o peso total atual. Se o peso total do cardume aumentou, os peixes começam a se mover em direção ao centro de massa; caso contrário, afastam-se do centro. A fórmula foi detalhada anteriormente. O peso total do cardume é atualizado em um método específico para isso, que será abordado a seguir.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::apply_collective_volitive_movement ()
{
  //----------------------------------------------------------------------------
  double current_total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    current_total_weight += fishes [f].weight;
  }

  ArrayInitialize (barycenter, 0.0);

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      barycenter [d] += fishes [f].weight * fishes [f].current_position [d];
    }
  }

  for (int d = 0; d < dimensions; d++)
  {
    barycenter [d] /= current_total_weight;
  }

  //----------------------------------------------------------------------------
  double search_operator = current_total_weight > total_weight ? 1.0 : -1.0;
  double r   = 0.0;
  double pos = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    for (int d = 0; d < dimensions; d++)
    {
      r = RNDfromCI (0.0, 1.0);
      pos = fishes [f].current_position [d];

      fishes [f].new_position [d] = pos + (((pos - barycenter [d]) * step_vol [d] * r) * search_operator);
      fishes [f].new_position [d] = SeInDiSp (fishes [f].new_position [d], rangeMin [d], rangeMax [d], rangeStep [d]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

De fato, este é o método de atualização do peso total dos peixes. A implementação é simples: pegamos o peso de cada peixe e somamos.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FSS::update_total_weight ()
{
  total_weight = 0.0;

  for (int f = 0; f < num_of_individuos; f++)
  {
    total_weight += fishes [f].weight;
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultado dos testes

Vamos para a parte final e mais interessante - os resultados. Abordagens interessantes utilizadas neste algoritmo, como a ausência da necessidade de considerar o ótimo global, a introdução dos conceitos de centro de massa e movimento instintivo-volitivo, implicando convergência ou divergência do centro do cardume, dependendo de se a posição geral foi melhorada, geraram expectativas de um comportamento original do algoritmo nas funções analisadas.

De fato, há originalidade no comportamento na área de busca do espaço, com dispersão dos peixes em áreas distintas, como observado no algoritmo das abelhas, embora uma análise detalhada das fórmulas e do princípio de funcionamento do FSS não sugira a divisão do cardume em grupos separados. Em geral, o algoritmo apresentou um desempenho fraco, superando apenas ligeiramente o algoritmo PSO no resultado geral.

Se considerarmos os testes individuais, em alguns casos, o FSS conseguiu se destacar. Na função Smooth Skin, por exemplo, o algoritmo FSS superou até mesmo o algoritmo Wolf, apresentando resultados bons (embora não os melhores). Isso pode ser explicado pelo uso do gradiente da superfície da função em estudo no algoritmo, levando em conta incrementos em cada coordenada e a mudança na função de aptidão a cada iteração. Como a função Skin é suave, o algoritmo se adapta bem às mudanças de superfície.

Em relação à função Forest, o algoritmo apresentou resultados abaixo da média na tabela. As mudanças suaves na função de teste ajudaram o algoritmo a navegar pelo espaço até certo ponto, mas ele não conseguiu encontrar o máximo global. Ao analisar os resultados obtidos na função Megacity, as deficiências do FSS tornam-se ainda mais evidentes. O algoritmo enfrenta dificuldades quando a função em estudo não apresenta mudanças significativas nas proximidades das posições atuais dos agentes individuais, e o algoritmo não é capaz de realizar saltos mais longos para identificar novos locais potencialmente melhores. Isso resulta em ficar preso em extremos locais sem incrementos na vizinhança.

Embora o teste Megacity seja desafiador para qualquer algoritmo de otimização e os outros participantes na tabela comparativa não superem o FSS de maneira expressiva, é preciso admitir as limitações do algoritmo em problemas discretos. Em alguns testes, a busca aleatória apresentou melhores resultados. Conforme observado na animação e considerando os pontos mencionados, é esperado que não ocorra "clustering" no funcionamento do algoritmo. Vale lembrar que, no artigo anterior, foi descrito o fenômeno da "cristalização" nos algoritmos de otimização.

Saída do algoritmo FSS:

2022.12.08 13:14:06.033    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:14:08.388    Test_AO_FSS (EURUSD,M1)    1 Skin's; Func runs 10000 result: 4.892861444841324
2022.12.08 13:14:08.388    Test_AO_FSS (EURUSD,M1)    Score: 0.99391
2022.12.08 13:14:12.557    Test_AO_FSS (EURUSD,M1)    20 Skin's; Func runs 10000 result: 3.11410005347766
2022.12.08 13:14:12.557    Test_AO_FSS (EURUSD,M1)    Score: 0.56920
2022.12.08 13:14:47.176    Test_AO_FSS (EURUSD,M1)    500 Skin's; Func runs 10000 result: 1.20519552002827
2022.12.08 13:14:47.176    Test_AO_FSS (EURUSD,M1)    Score: 0.11341
2022.12.08 13:14:47.176    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:14:49.498    Test_AO_FSS (EURUSD,M1)    1 Forest's; Func runs 10000 result: 1.5057381856551146
2022.12.08 13:14:49.498    Test_AO_FSS (EURUSD,M1)    Score: 0.85172
2022.12.08 13:14:53.825    Test_AO_FSS (EURUSD,M1)    20 Forest's; Func runs 10000 result: 0.21468156279781656
2022.12.08 13:14:53.825    Test_AO_FSS (EURUSD,M1)    Score: 0.12143
2022.12.08 13:15:31.235    Test_AO_FSS (EURUSD,M1)    500 Forest's; Func runs 10000 result: 0.056970068652984526
2022.12.08 13:15:31.235    Test_AO_FSS (EURUSD,M1)    Score: 0.03223
2022.12.08 13:15:31.235    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:15:34.066    Test_AO_FSS (EURUSD,M1)    1 Megacity's; Func runs 10000 result: 11.0
2022.12.08 13:15:34.066    Test_AO_FSS (EURUSD,M1)    Score: 0.91667
2022.12.08 13:15:38.467    Test_AO_FSS (EURUSD,M1)    20 Megacity's; Func runs 10000 result: 1.03
2022.12.08 13:15:38.467    Test_AO_FSS (EURUSD,M1)    Score: 0.08583
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    500 Megacity's; Func runs 10000 result: 0.31
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    Score: 0.02583
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    =============================
2022.12.08 13:16:16.589    Test_AO_FSS (EURUSD,M1)    All score for C_AO_FSS: 0.4122477188979048

  FSS na função de teste Skin.

  FSS na função de teste Forest.

  FSS na função de teste Megacity.

Segue abaixo a tabela resultante, na qual foram adicionadas colunas adicionais para tornar mais conveniente a avaliação dos algoritmos para cada função de teste separadamente. Isso permite argumentar de maneira mais justa sobre a aplicabilidade de cada algoritmo para determinadas tarefas.

AO	Description	Skin			Skin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
		2 params (1 F)	40 params (20 F)	1000 params (500 F)		2 params (1 F)	40 params (20 F)	1000 params (500 F)		2 params (1 F)	40 params (20 F)	1000 params (500 F)
COAm	algoritmo de otimização de cuco	1,00000	0,85911	0,14316	0,66742	0,99283	0,28787	0,04551	0,44207	1,00000	0,24917	0,03537	0,42818	0,51255778
ACOm	otimização de colônia de formigas	0,98229	0,79108	0,12602	0,63313	1,00000	0,62077	0,11521	0,57866	0,38333	0,44000	0,02377	0,28237	0,49805222
ABCm	colônia artificial de abelhas M	1,00000	0,63922	0,08076	0,57333	0,99908	0,20112	0,03785	0,41268	1,00000	0,16333	0,02823	0,39719	0,46106556
ABC	colônia artificial de abelhas	0,99339	0,73381	0,11118	0,61279	0,99934	0,21437	0,04215	0,41862	0,85000	0,16833	0,03130	0,34988	0,46043000
GWO	otimizador lobo-cinzento	0,99900	0,48033	0,18924	0,55619	0,83844	0,08755	0,02555	0,31718	1,00000	0,10000	0,02187	0,37396	0,41577556
FSS	busca por cardume de peixes	0,99391	0,5692	0,11341	0,55884	0,85172	0,12143	0,03223	0,33513	0,91667	0,08583	0,02583	0,34278	0,41224778
PSO	otimização de enxame de partículas	0,99627	0,38080	0,05089	0,47599	0,93772	0,14540	0,04856	0,37723	1,00000	0,09333	0,02233	0,37189	0,40836667
RND	aleatório	0,99932	0,44276	0,06827	0,50345	0,83126	0,11524	0,03048	0,32566	0,83333	0,09000	0,02403	0,31579	0,38163222

Métodos heurísticos estocásticos (aleatorizados) não garantem uma solução exata, mas geralmente permitem encontrar soluções suficientemente próximas para uso prático em um tempo aceitável. No entanto, na prática, podemos reconhecer que alguns algoritmos demonstram excelentes habilidades de convergência, mas esse não é o caso do FSS. De modo geral, o algoritmo de busca de cardume de peixes é um caso particular de algoritmos baseados em enxame de partículas, herdando tanto vantagens quanto desvantagens. No entanto, surgiram características exclusivas para este algoritmo em comparação com seus "precursores", como a divisão de um cardume de peixes (enxame) em grupos separados, algo não observado no enxame de partículas. Vale destacar as vantagens: o algoritmo lida relativamente bem com funções suaves, embora não haja garantias de que o FSS funcionará bem com funções com múltiplas variáveis.

Prós:
1. Lida razoavelmente bem com funções suaves.
2. Capacidade do cardume de peixes de se dividir em grupos separados, permitindo ao algoritmo explorar ainda mais outros extremos locais potencialmente bons.

Contras:
1. Uma grande dispersão de resultados nos testes individuais indica instabilidade do algoritmo.
2. Convergência muito fraca em funções discretas e com descontinuidades. Praticamente não aplicável para funções discretas.
3. Baixa escalabilidade.