Algoritmo do Bisão: Bison Algorithm (BIA)

Conteúdo

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

Introdução

Em nossa busca pelo melhor método de otimização, neste artigo conheceremos o Algoritmo do Bisão (Bison Algorithm, BIA), um algoritmo populacional de otimização inspirado no comportamento de enxame e destinado a problemas contínuos com uma única função objetivo. O BIA se baseia em dois princípios fundamentais observados no comportamento dos bisões: a capacidade de deslocamento dinâmico e a estratégia defensiva. O algoritmo foi desenvolvido por pesquisadores tchecos em 2017 e publicado na série Lecture Notes in Computer Science, da Springer, em 2019. 

Os bisões são animais impressionantes, dotados de enorme resistência e força. Eles conseguem atingir altas velocidades e mantê-las por até meia hora. Quando são cercados por predadores, costumam formar um círculo, no qual os indivíduos mais fortes ocupam o perímetro, enquanto o restante do rebanho procura permanecer no interior para ficar em segurança.

Esses dois padrões de comportamento foram modelados no Algoritmo do Bisão e aplicados como técnicas de otimização. O primeiro aspecto, "velocidade e resistência", permite que os agentes se desloquem por todo o espaço de busca, explorando regiões novas e potencialmente ótimas. O segundo aspecto, "círculo defensivo", representa um mecanismo de busca local e estabilização, no qual os agentes se agrupam em torno das soluções mais promissoras, evitando que os agentes se afastem prematuramente dessas soluções e refinando suas posições. Agora, vejamos como isso funciona no algoritmo.

Implementação do algoritmo

Imagine que você esteja observando um rebanho de bisões em uma pradaria. Eles precisam encontrar o melhor pasto, com grama suculenta e água limpa. Mas a pradaria é imensa! Como conseguem fazer isso? Vamos dividir o rebanho em dois grupos.

Rebanho principal (80% dos bisões): são os bisões cautelosos. Eles permanecem juntos e se deslocam lentamente em grupo. "Juntos somos mais fortes!" é o lema deles.

Exploradores (20% dos bisões): são os bisões jovens e corajosos. Eles correm à frente na mesma direção, em busca de novos territórios. "O que será que há do outro lado da colina?", pensam eles.

Formam-se dois grupos: 40 bisões do rebanho principal se dispersam pela área já conhecida, enquanto 10 corredores se reúnem perto do bisão mais bem alimentado, que claramente sabe onde está a melhor grama, e se preparam para correr. Quando um bisão do rebanho principal se dirige a um novo local, primeiro memoriza a posição em que estava. Em seguida, dá alguns passos, de 0 a 3,5 metros, e experimenta a grama. Caso a nova grama seja pior, ele retorna à posição anterior. "Mais vale um pássaro na mão..." Quando um dos corredores encontra um local melhor que o ocupado pelo pior bisão do rebanho, os dois trocam de lugar. Todos os dias, os corredores alteram ligeiramente a direção, desviando 10% para a esquerda ou para a direita. Assim, aumentam as chances de encontrar algo novo. Quando o rebanho se reúne em torno dos melhores bisões, seus integrantes não se posicionam simplesmente no centro. O líder, o bisão mais bem-nutrido, recebe um "peso" de 100; o segundo recebe 90; o terceiro, 80; e assim por diante, até o décimo, que recebe 10. 

Agora, imagine que:

• Pasto = espaço de busca de soluções
• Qualidade da grama = valor da função objetivo
• Posição do bisão = solução potencial
• Melhor pasto = solução ótima

O diagrama abaixo mostra a fase de inicialização, na qual a população é dividida entre o grupo do rebanho (80%) e o grupo dos corredores (20%). O laço principal de iterações é composto por quatro etapas: definição do alvo do rebanho, com a escolha entre o melhor corredor e o centro da elite; deslocamento do grupo do rebanho em direção ao centro da elite, calculado pela média ponderada das posições das melhores soluções; deslocamento dos corredores na direção de diversificação; e verificação e atualização dos resultados.

Figura 1. Esquema de funcionamento da estratégia do algoritmo BIA

Principais parâmetros do algoritmo. Esquema de cores: verde para o grupo do rebanho, laranja para o grupo dos corredores, roxo para a fase de verificação e atualização e azul-claro para o deslocamento do rebanho. Na ilustração, as setas indicam o fluxo de execução e as direções de deslocamento dos grupos.

Vamos começar a escrever o pseudocódigo do algoritmo DIA.

INICIALIZAÇÃO:
1. Criar uma população de N bisões
2. Dividir em grupos:
   - Grupo do rebanho (80%): distribuir aleatoriamente por todo o espaço de busca
   - Grupo dos corredores (20%): distribuir ao redor do melhor bisão do grupo do rebanho
3. Definir uma direção de corrida aleatória para os exploradores

LAÇO PRINCIPAL (repetir até a convergência):
  
  SELEÇÃO DO ALVO DO DESLOCAMENTO:
  - SE a melhor solução do grupo dos corredores for melhor que a pior solução do rebanho:
      Alvo = posição do melhor indivíduo do grupo dos corredores
  - CASO CONTRÁRIO:
      Alvo = centro ponderado dos 10 melhores bisões do rebanho
  
  DESLOCAMENTO DO GRUPO DO REBANHO:
  - Para cada bisão do rebanho:
    1. Salvar a posição atual
    2. Calcular a direção até o alvo
    3. Dar um passo em direção ao alvo, com comprimento aleatório entre 0 e 3,5
    4. Verificar os limites do espaço de busca
  
  DESLOCAMENTO DO GRUPO DOS CORREDORES:
  - Alterar ligeiramente a direção da corrida (×0,9–1,1)
  - Para cada indivíduo:
    1. Deslocar-se na direção da corrida
    2. Verificar os limites do espaço de busca
  
  AVALIAÇÃO E ATUALIZAÇÃO:
  1. Verificação do grupo do rebanho:
     - SE a nova posição for pior que a anterior:
         Restaurar a posição anterior
  
  2. Troca entre os grupos:
     - SE o melhor indivíduo do grupo dos corredores for melhor que o pior bisão do rebanho:
         Substituir o pior bisão do rebanho pelo melhor indivíduo
  
  3. Ordenação:
     - Ordenar o grupo do rebanho pela qualidade das soluções
  
  4. Atualização:
     - Armazenar a melhor solução encontrada
     - Armazenar a pior solução

FIM DO LAÇO

CÁLCULO DO CENTRO PONDERADO:
- Selecionar as 10 melhores soluções
- Atribuir os pesos: a 1ª recebe peso 100, a 2ª recebe 90, ..., a 10ª recebe 10
- Centro = soma(posição × peso) / soma(pesos)

Agora que o funcionamento do algoritmo está mais claro, podemos começar a escrever seu código. A classe implementa o "Bison Algorithm" e herda da classe base "C_AO".

Parâmetros do algoritmo:

• popSize: define o número total de "indivíduos" ou "agentes" da população que participam da execução do algoritmo.
• swarmGroupRate: define a porcentagem da população que formará o "grupo do rebanho".
• eliteGroupSize: define o número dos melhores indivíduos que formam o "grupo de elite" usado no cálculo do centro.
• overstep: define o passo máximo que o "grupo do rebanho" pode dar durante seu deslocamento.

No construtor, são definidos os valores padrão de todos os parâmetros. O método "SetParams" permite atualizar os parâmetros do algoritmo com dados de uma fonte externa, representada pelo array "params".

Funcionalidades:

• Init: método responsável pela inicialização do algoritmo com base nos intervalos de valores dos parâmetros.
• Moving: método responsável pelo deslocamento ou pela atualização do estado dos indivíduos da população.
• Revision: método usado para revisar e ajustar o comportamento dos indivíduos ou os parâmetros do algoritmo.
• ComputeCenter: método privado responsável pelo cálculo do centro do grupo de elite.
• CheckIfRunnerBetter: método privado que verifica se algum indivíduo do grupo dos corredores apresenta um resultado melhor que os demais.

Variáveis internas:

• swarmGroupSize: calculada com base em "popSize" e "swarmGroupRate", define o número efetivo de indivíduos no grupo do rebanho.
• runningGroupSize: tamanho do grupo dos corredores, que constitui um subgrupo da população total.
• runDirection: array que armazena a direção de deslocamento de cada indivíduo.
• center: array que armazena as coordenadas do centro do grupo de elite.

De modo geral, a classe "C_AO_BisonAlgorithm" implementa uma estratégia de busca baseada nos conceitos de população, grupo do rebanho e grupo de elite, além de oferecer parâmetros configuráveis.

class C_AO_BisonAlgorithm : public C_AO
{
  public: //----------------------------------------------------------
  ~C_AO_BisonAlgorithm () { }
  C_AO_BisonAlgorithm ()
  {
    ao_name = "BIA";
    ao_desc = "Bison Algorithm";
    ao_link = "https://www.mql5.com/en/articles/19444";

    popSize          = 50;    // population size
    swarmGroupRate   = 0.8;   // share of swarm group from population (80%)
    eliteGroupSize   = 10;    // size of the elite group for calculating the center (s parameter)
    overstep         = 3.5;   // maximum step of the swarm group

    ArrayResize (params, 4);

    params [0].name = "popSize";        params [0].val = popSize;
    params [1].name = "swarmGroupRate"; params [1].val = swarmGroupRate;
    params [2].name = "eliteGroupSize"; params [2].val = eliteGroupSize;
    params [3].name = "overstep";       params [3].val = overstep;
  }

  void SetParams ()
  {
    popSize        = (int)params [0].val;
    swarmGroupRate = params      [1].val;
    eliteGroupSize = (int)params [2].val;
    overstep       = params      [3].val;
  }

  bool Init (const double &rangeMinP  [],
             const double &rangeMaxP  [],
             const double &rangeStepP [],
             const int     epochsP = 0);

  void Moving   ();
  void Revision ();
  
  private:
  void ComputeCenter ();
  bool CheckIfRunnerBetter ();

  //------------------------------------------------------------------
  public:
  double swarmGroupRate;     // share of swarm group
  int    eliteGroupSize;     // size of the elite group (s parameter)
  double overstep;           // maximum step of the swarm group

  private: //---------------------------------------------------------
  int    swarmGroupSize;     // swarm group size
  int    runningGroupSize;   // running group size
  double runDirection [];    // running direction
  double center [];          // elite group center
};
//————————————————————————————————————————————————————————————————————

O método "Init" da classe "C_AO_BisonAlgorithm" é responsável pela configuração do algoritmo antes de sua execução. Primeiro, ele tenta executar a rotina geral e padronizada de inicialização, usando os intervalos dos parâmetros recebidos e o número de épocas. Caso essa etapa não seja concluída com sucesso, toda a inicialização é interrompida. Em seguida, o número de indivíduos que fará parte do grupo do rebanho é calculado com base no tamanho total da população e na proporção definida. Os indivíduos restantes formam o grupo dos corredores.

Para garantir o funcionamento correto do algoritmo, os tamanhos desses grupos são validados. O grupo do rebanho deve conter pelo menos um indivíduo, mas não pode ocupar toda a população, pois é necessário reservar espaço para o grupo dos corredores. Da mesma forma, o grupo de elite deve conter pelo menos um indivíduo e não pode ser maior que o grupo do rebanho, do qual é um subconjunto.

Em seguida, é alocada memória para os arrays auxiliares. Tanto o array destinado a armazenar a direção de deslocamento dos indivíduos em cada dimensão do espaço de busca quanto o array que armazena as coordenadas do centro do grupo de elite são redimensionados de acordo com o número de dimensões definido no sistema. Quando todas as etapas anteriores são concluídas com sucesso, o método retorna "true", indicando que o algoritmo está pronto para ser executado.

//————————————————————————————————————————————————————————————————————
//--- Initialization
bool C_AO_BisonAlgorithm::Init (const double &rangeMinP  [],
                                const double &rangeMaxP  [],
                                const double &rangeStepP [],
                                const int     epochsP = 0)
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //------------------------------------------------------------------
  // Calculate the sizes of groups
  swarmGroupSize   = (int)MathFloor (popSize * swarmGroupRate);
  runningGroupSize = popSize - swarmGroupSize;
  
  // Adjust group sizes
  if (swarmGroupSize < 1) swarmGroupSize = 1;
  if (swarmGroupSize >= popSize) swarmGroupSize = popSize - 1;
  if (eliteGroupSize < 1) eliteGroupSize = 1;
  if (eliteGroupSize > swarmGroupSize) eliteGroupSize = swarmGroupSize;
  
  // Initialize auxiliary arrays
  ArrayResize (runDirection, coords);
  ArrayResize (center, coords);

  return true;
}
//————————————————————————————————————————————————————————————————————

O método "Moving" da classe "C_AO_BisonAlgorithm" constitui o núcleo do algoritmo e é responsável por executar uma iteração, ou etapa de evolução, da população. Ele é composto por duas fases principais: a inicialização da população, quando o algoritmo é executado pela primeira vez, e as atualizações posteriores das posições dos indivíduos.

Fase 1: Inicialização da população (primeira execução): quando o algoritmo é executado pela primeira vez, com a flag "revision" definida como "false", é realizada a seguinte sequência de operações:

• Geração do grupo do rebanho. Os indivíduos que compõem o grupo do rebanho são inicializados com valores aleatórios dentro dos intervalos definidos para cada parâmetro. Após a geração, esses valores podem ser ajustados para respeitar o passo de variação dos parâmetros.
• Seleção do melhor bisão. Entre todos os indivíduos do grupo do rebanho, é selecionado aquele que apresenta a melhor aptidão, ou seja, o maior valor da função objetivo.
• Geração do grupo dos corredores. Os demais indivíduos da população, que formam o grupo dos corredores, são inicializados ao redor do melhor bisão encontrado. Suas posições são geradas aleatoriamente em uma determinada vizinhança da melhor solução e, em seguida, ajustadas de acordo com os intervalos e os passos dos parâmetros.
• Inicialização do vetor de direção. Para cada dimensão do espaço de busca, é gerado aleatoriamente um componente do vetor de direção. Sua magnitude depende do intervalo total de valores do parâmetro, enquanto o sinal, positivo ou negativo, também é escolhido aleatoriamente.
• Atualização do indicador de inicialização. O indicador "revision" é definido como "true". Com isso, a inicialização é concluída e, nas chamadas seguintes, serão executadas apenas as etapas de atualização.

Fase 2: Laço principal (iterações seguintes): após a conclusão da inicialização, o método executa as seguintes operações a cada iteração:

Definição do alvo do rebanho. O algoritmo verifica se alguma solução do grupo dos corredores é melhor que o alvo atual do rebanho.

• Caso uma solução do grupo dos corredores apresente um resultado melhor, o centroide usado como alvo do rebanho é atualizado com a posição dessa solução.
• Caso contrário, é calculado um novo centroide com base na posição média das melhores soluções da população.

Deslocamento do grupo do rebanho. Cada indivíduo do grupo do rebanho se desloca.

• Primeiro, são armazenadas sua posição atual e sua aptidão.
• Em seguida, a nova posição é calculada deslocando o indivíduo da posição atual em direção ao alvo do rebanho. A magnitude desse deslocamento é determinada por um fator aleatório que controla quanto o indivíduo pode ultrapassar o alvo.
• Depois, a nova posição é ajustada para permanecer dentro dos intervalos permitidos e respeitar o passo dos parâmetros.

Ajuste do vetor de direção. O vetor usado pelo grupo dos corredores é ligeiramente alterado de forma aleatória. Isso introduz alguma variabilidade no deslocamento dos corredores.

Deslocamento do grupo dos corredores. Cada indivíduo desse grupo se desloca usando o vetor de direção ajustado.

• A nova posição é calculada adicionando o vetor de direção à posição atual.
• Em seguida, ela é ajustada para permanecer dentro dos intervalos permitidos e respeitar o passo dos parâmetros.

Assim, o método "Moving" modela o comportamento dos dois grupos de indivíduos: o grupo do rebanho se desloca em direção a um alvo comum, reagindo às melhores soluções encontradas, enquanto o grupo dos corredores segue o vetor de direção ajustado, que pode variar ao longo das iterações.

/————————————————————————————————————————————————————————————————————
//--- Main step of the algorithm
void C_AO_BisonAlgorithm::Moving ()
{
  // Starting initialization of the population
  if (!revision)
  {
    // Generate a swarm group randomly
    for (int i = 0; i < swarmGroupSize; i++)
    {
      for (int j = 0; j < coords; j++)
      {
        a [i].c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]);
        a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
      }
    }
    
    // Find the best solution among the swarm group to initialize the runners
    int bestIdx = 0;
    double bestFit = a [0].f;
    for (int i = 1; i < swarmGroupSize; i++)
    {
      if (a [i].f > bestFit)
      {
        bestFit = a [i].f;
        bestIdx = i;
      }
    }
    
    // Generate a running group around the best bison
    double neighbourhood = (rangeMax [0] - rangeMin [0]) / 15.0;
    for (int i = swarmGroupSize; i < popSize; i++)
    {
      for (int j = 0; j < coords; j++)
      {
        a [i].c [j] = a [bestIdx].c [j] + u.RNDfromCI (-neighbourhood, neighbourhood);
        a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
      }
    }
    
    // Generate run direction = random((ub-lb)/45, (ub-lb)/15)
    for (int j = 0; j < coords; j++)
    {
      double range = rangeMax [j] - rangeMin [j];
      runDirection [j] = u.RNDfromCI (range / 45.0, range / 15.0);
      if (u.RNDprobab () < 0.5) runDirection [j] = -runDirection [j];
    }
    
    revision = true;
    return;
  }

  //------------------------------------------------------------------
  // Main iteration loop
  
  // 1. Define swarming target
  if (CheckIfRunnerBetter ())
  {
    // If runner is better than swarmer, center = runner
    // center is already set in CheckIfRunnerBetter
  }
  else
  {
    // Otherwise, calculate the center of the strongest solutions
    ComputeCenter ();
  }
  
  // 2. Swarm group movement
  for (int i = 0; i < swarmGroupSize; i++)
  {
    // Save old positions in cP and fitness in fP
    ArrayCopy (a [i].cP, a [i].c, 0, 0, coords);
    a [i].fP = a [i].f;
    
    // Calculate a new candidate for the position
    for (int c = 0; c < coords; c++)
    {
      double direction = center [c] - a [i].c [c];
      a [i].c [c] = a [i].c [c] + direction * u.RNDfromCI (0.0, overstep);
      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  
  // 3. Correction of the vector 'run direction'
  for (int j = 0; j < coords; j++)
  {
    runDirection [j] = runDirection [j] * u.RNDfromCI (0.9, 1.1);
  }
  
  // 4. Running group movement
  for (int i = swarmGroupSize; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      a [i].c [c] = a [i].c [c] + runDirection [c];
      a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//————————————————————————————————————————————————————————————————————

O método "Revision" da classe "C_AO_BisonAlgorithm" é responsável por atualizar o estado da população após uma etapa de deslocamento e a avaliação da aptidão dos indivíduos, além de consolidar os resultados da iteração.

Correção do grupo do rebanho. Para cada indivíduo desse grupo, verifica-se se a nova posição, calculada na etapa anterior, é melhor que a posição anterior armazenada. Caso a nova posição seja pior, o indivíduo retorna à posição anterior, que apresentava um resultado melhor. Dessa forma, os indivíduos do grupo do rebanho não pioram seus resultados.

Comparação entre o grupo dos corredores e o grupo do rebanho:

• É identificado o melhor indivíduo do grupo dos corredores, com a maior aptidão, e o pior indivíduo do grupo do rebanho, com a menor aptidão.
• Caso a aptidão do melhor indivíduo do grupo dos corredores seja superior à do pior indivíduo do grupo do rebanho, este último é substituído pelo primeiro. Com isso, as soluções mais promissoras encontradas pelos corredores podem passar a integrar o grupo do rebanho.

Ordenação do grupo do rebanho:

• É criada uma cópia temporária de todos os indivíduos do grupo do rebanho.
• Essa cópia é ordenada por aptidão em ordem decrescente, do melhor para o pior.
• Após a ordenação, os indivíduos da cópia temporária são copiados de volta para a população principal. Isso garante que o grupo do rebanho mantenha as melhores soluções encontradas até o momento.

Atualização das soluções globais:

• Melhor solução global. A aptidão do melhor indivíduo do grupo do rebanho, que após a ordenação representa a melhor solução do grupo, é comparada com a melhor solução global atual. Caso esse indivíduo apresente um resultado superior, a melhor solução global é atualizada.
• Pior solução global. Todos os indivíduos da população, tanto do grupo do rebanho quanto do grupo dos corredores, são examinados para identificar o indivíduo com a menor aptidão. Caso algum indivíduo apresente aptidão inferior à da pior solução global atual, a pior solução global é atualizada.

Assim, o método "Revision" atua como um mecanismo de consolidação dos resultados: seleciona as melhores soluções, mantém o grupo do rebanho ordenado e atualizado e acompanha o progresso geral do algoritmo, armazenando a melhor e a pior solução encontradas.

//————————————————————————————————————————————————————————————————————
//--- Update and check results
void C_AO_BisonAlgorithm::Revision ()
{
  // 1. For a swarm group: update positions only if the new position is better
  for (int i = 0; i < swarmGroupSize; i++)
  {
    // If the new position is worse than the old one, return the old one
    if (a [i].f < a [i].fP)
    {
      ArrayCopy (a [i].c, a [i].cP, 0, 0, coords);
      a [i].f = a [i].fP;
    }
  }
  
  // 2. Let's check if runner has found a better solution than swarmer
  double bestRunnerFitness = -DBL_MAX;
  int bestRunnerIdx = -1;
  double worstSwarmerFitness = DBL_MAX;
  int worstSwarmerIdx = -1;
  
  for (int i = swarmGroupSize; i < popSize; i++)
  {
    if (a[i].f > bestRunnerFitness)
    {
      bestRunnerFitness = a[i].f;
      bestRunnerIdx = i;
    }
  }
  
  for (int i = 0; i < swarmGroupSize; i++)
  {
    if (a[i].f < worstSwarmerFitness)
    {
      worstSwarmerFitness = a[i].f;
      worstSwarmerIdx = i;
    }
  }
  
  // If the runner is better than the worst swarmer, copy the runner to the swarming group
  if (bestRunnerIdx >= 0 && worstSwarmerIdx >= 0 && bestRunnerFitness > worstSwarmerFitness)
  {
    ArrayCopy (a[worstSwarmerIdx].c, a[bestRunnerIdx].c, 0, 0, coords);
    a[worstSwarmerIdx].f = a[bestRunnerIdx].f;
  }
  
  // 3. Sort the swarm group
  // Create a temporary array to sort only the swarm group
  S_AO_Agent swarmTemp [];
  ArrayResize (swarmTemp, swarmGroupSize);
  
  // Copy the swarm group
  for (int i = 0; i < swarmGroupSize; i++)
  {
    swarmTemp[i].Init(coords);
    ArrayCopy (swarmTemp[i].c, a[i].c, 0, 0, coords);
    swarmTemp[i].f = a[i].f;
    ArrayCopy (swarmTemp[i].cP, a[i].cP, 0, 0, coords);
    swarmTemp[i].fP = a[i].fP;
  }
  
  // Sort
  S_AO_Agent tempSorted [];
  ArrayResize (tempSorted, swarmGroupSize);
  u.Sorting (swarmTemp, tempSorted, swarmGroupSize);
  
  // Copy the swarm group sorted back
  for (int i = 0; i < swarmGroupSize; i++)
  {
    ArrayCopy (a[i].c, swarmTemp[i].c, 0, 0, coords);
    a[i].f = swarmTemp[i].f;
    ArrayCopy (a[i].cP, swarmTemp[i].cP, 0, 0, coords);
    a[i].fP = swarmTemp[i].fP;
  }
  
  // 4. Update the global best and worst case solution
  if (a[0].f > fB)
  {
    fB = a[0].f;
    ArrayCopy (cB, a[0].c, 0, 0, WHOLE_ARRAY);
  }
  
  // Find the worst in the entire population
  for (int i = 0; i < popSize; i++)
  {
    if (a[i].f < fW)
    {
      fW = a[i].f;
      ArrayCopy (cW, a[i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//————————————————————————————————————————————————————————————————————

O método "CheckIfRunnerBetter" determina se o grupo dos corredores contém uma solução mais promissora do que as do grupo do rebanho. Quando isso ocorre, essa solução passa a ser o novo alvo do rebanho.

Busca pelo melhor corredor. Primeiro, o método percorre todos os indivíduos do grupo dos corredores, ou seja, aqueles que não fazem parte do grupo do rebanho. Em seguida, identifica o indivíduo com a maior aptidão, correspondente ao maior valor da função objetivo entre todos os corredores, e armazena seu índice e seu valor de aptidão.

Busca pelo pior indivíduo do rebanho. Depois, o método analisa os indivíduos do grupo do rebanho e identifica aquele que apresenta a menor aptidão.

Comparação e definição do alvo. Em seguida, as aptidões encontradas são comparadas:

• Se o melhor "corredor" tiver aptidão superior à do pior indivíduo do rebanho, isso significa que o grupo dos corredores realmente encontrou uma solução de melhor qualidade.
• Nesse caso, a posição, ou seja, as coordenadas, do melhor corredor é atribuída à variável que representa o "centro" ou "alvo do rebanho". O método retorna um valor indicando que o alvo foi atualizado.

Retorno do resultado:

• Se a aptidão do melhor corredor for superior à do pior indivíduo do rebanho, o método sinaliza essa condição retornando "true".
• Caso contrário, isto é, se nenhum corredor superar o pior indivíduo do rebanho, o método retorna "false", e o centro do rebanho permanece inalterado.

Assim, esse método permite alterar dinamicamente a direção da busca: quando surgem soluções mais promissoras no grupo de diversificação dos corredores, elas passam a orientar o grupo de intensificação do rebanho.

//————————————————————————————————————————————————————————————————————
//--- Check whether a runner is better than a swarmer
bool C_AO_BisonAlgorithm::CheckIfRunnerBetter ()
{
  // Find the best runner
  double bestRunnerFitness = -DBL_MAX;
  int bestRunnerIdx = -1;
  
  for (int i = swarmGroupSize; i < popSize; i++)
  {
    if (a[i].f > bestRunnerFitness)
    {
      bestRunnerFitness = a[i].f;
      bestRunnerIdx = i;
    }
  }
  
  // Find the worst swarmer 
  double worstSwarmerFitness = DBL_MAX;
  
  for (int i = 0; i < swarmGroupSize; i++)
  {
    if (a[i].f < worstSwarmerFitness)
    {
      worstSwarmerFitness = a[i].f;
    }
  }
  
  // If the runner is better than the swarmer, set it as the center
  if (bestRunnerIdx >= 0 && bestRunnerFitness > worstSwarmerFitness)
  {
    ArrayCopy (center, a[bestRunnerIdx].c, 0, 0, coords);
    return true;
  }
  
  return false;
}
//————————————————————————————————————————————————————————————————————

O método "ComputeCenter" calcula uma nova posição-alvo, ou centro, para o grupo do rebanho com base nas melhores soluções encontradas. Veja como ele funciona:

• Zeragem da posição-alvo. Primeiro, todos os componentes da futura posição-alvo, ou centro, são definidos como zero. Isso os prepara para o acúmulo dos novos valores.
• Definição do número de melhores soluções. O método determina quantas das melhores soluções serão usadas no cálculo do centro. Para isso, seleciona o menor valor entre dois parâmetros:

• eliteGroupSize: número máximo de soluções de "elite" que podem ser consideradas;
• swarmGroupSize: tamanho atual do grupo do rebanho.
• Isso garante o uso de todas as soluções de elite especificadas ou, caso o grupo do rebanho tenha menos indivíduos, apenas da quantidade disponível nesse grupo.
• Atribuição dos pesos. É atribuído um peso a cada uma das melhores soluções selecionadas. Os pesos são gerados em ordem crescente, como 10, 20, 30, ..., s × 10, mas são associados às soluções em ordem inversa, de modo que a melhor solução receba o maior peso. Mais especificamente, os pesos são definidos como 10, 20, 30, ..., até s × 10, em que s é o número de melhores soluções consideradas. Esses pesos determinam a influência de cada solução no cálculo do centro.
• Cálculo da soma total dos pesos. Todos os pesos calculados são somados. Essa soma total será usada posteriormente na normalização.
• Soma ponderada das posições. Para cada dimensão, ou coordenada, da posição:
• é obtido o valor da coordenada correspondente de cada uma das s melhores soluções;
• esse valor é multiplicado pelo peso associado à respectiva solução. É importante observar que os pesos são aplicados em ordem inversa: a melhor solução, que ocupa a primeira posição na lista ordenada, recebe o maior peso; a segunda recebe o peso seguinte, e assim por diante;
• os resultados dessas multiplicações são somados para cada coordenada considerando todas as s melhores soluções.
• Normalização. A soma ponderada das coordenadas de cada dimensão é dividida pela soma total dos pesos. Com isso, obtém-se uma média ponderada, garantindo que a posição final do centro fique em uma região intermediária entre as melhores soluções encontradas, mas com maior influência das soluções de melhor qualidade.

Como resultado, o método "ComputeCenter" gera uma nova posição-alvo que funciona como uma posição correspondente à média ponderada das melhores soluções, favorecendo as de maior qualidade e ajudando a direcionar as próximas etapas da busca do rebanho.

//————————————————————————————————————————————————————————————————————
//--- Calculate the center of the elite group
void C_AO_BisonAlgorithm::ComputeCenter ()
{
  // Reset the center
  for (int j = 0; j < coords; j++)
  {
    center [j] = 0.0;
  }
  
  // Calculate the weighted center from the s best solutions
  double weights [];
  int s = MathMin(eliteGroupSize, swarmGroupSize);
  ArrayResize (weights, s);
  double totalWeight = 0.0;
  
  // weight = (10, 20, 30, ..., 10*s)
  for (int i = 0; i < s; i++)
  {
    weights[i] = (i + 1) * 10.0;
    totalWeight += weights[i];
  }
  
  // center = sum(weight[i] * position[i]) / sum(weights)
  for (int j = 0; j < coords; j++)
  {
    for (int i = 0; i < s; i++)
    {
      center[j] += (weights[s - 1 - i] * a[i].c[j]) / totalWeight;
    }
  }
}
//————————————————————————————————————————————————————————————————————

Resultados dos testes

Como podemos ver, os resultados são medianos. Na função discreta Megacity, o desempenho é um pouco inferior, pois o algoritmo apresenta maior dificuldade em lidar com problemas discretos.

Bison|Bison Algorithm|50.0|0.8|10|3.5|
=============================
5 Hilly's; Func runs: 10000; result: 0.761847128451914
25 Hilly's; Func runs: 10000; result: 0.4002698460741261
500 Hilly's; Func runs: 10000; result: 0.25201531651422443
=============================
5 Forest's; Func runs: 10000; result: 0.7620992740937584
25 Forest's; Func runs: 10000; result: 0.45225292646780135
500 Forest's; Func runs: 10000; result: 0.19295587559803248
=============================
5 Megacity's; Func runs: 10000; result: 0.48769230769230765
25 Megacity's; Func runs: 10000; result: 0.19876923076923075
500 Megacity's; Func runs: 10000; result: 0.10058461538461608
=============================
All score: 3.60849 (40.09%)

A visualização do funcionamento do algoritmo BIA mostra uma dispersão considerável dos resultados tanto nas funções de baixa dimensionalidade, indicadas pelas linhas verdes, quanto nas de dimensionalidade média, indicadas pelas linhas azul-claras.

BIA na função de teste Hilly

BIA na função de teste Forest

BIA na função de teste Megacity

Na tabela de classificação dos métodos populacionais de otimização, o algoritmo BIA é apresentado apenas para fins de referência.

№	AO	Description	Hilly			Hilly Final	Forest			Forest Final	Megacity (discrete)			Megacity Final	Final Result	% of MAX
			10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)
1	DOAdingom	dingo_optimization_algorithm_M	0,47968	0,45367	0,46369	1,39704	0,94145	0,87909	0,91454	2,73508	0,78615	0,86061	0,84805	2,49481	6,627	73,63
1	ANS	across neighbourhood search	0,94948	0,84776	0,43857	2,23581	1,00000	0,92334	0,39988	2,32323	0,70923	0,63477	0,23091	1,57491	6,134	68,15
2	CLA	code lock algorithm (joo)	0,95345	0,87107	0,37590	2,20042	0,98942	0,91709	0,31642	2,22294	0,79692	0,69385	0,19303	1,68380	6,107	67,86
3	AMOm	animal migration ptimization M	0,90358	0,84317	0,46284	2,20959	0,99001	0,92436	0,46598	2,38034	0,56769	0,59132	0,23773	1,39675	5,987	66,52
4	(P+O)ES	(P+O) evolution strategies	0,92256	0,88101	0,40021	2,20379	0,97750	0,87490	0,31945	2,17185	0,67385	0,62985	0,18634	1,49003	5,866	65,17
5	CTA	comet tail algorithm (joo)	0,95346	0,86319	0,27770	2,09435	0,99794	0,85740	0,33949	2,19484	0,88769	0,56431	0,10512	1,55712	5,846	64,96
6	TETA	time evolution travel algorithm (joo)	0,91362	0,82349	0,31990	2,05701	0,97096	0,89532	0,29324	2,15952	0,73462	0,68569	0,16021	1,58052	5,797	64,41
7	SDSm	stochastic diffusion search M	0,93066	0,85445	0,39476	2,17988	0,99983	0,89244	0,19619	2,08846	0,72333	0,61100	0,10670	1,44103	5,709	63,44
8	BOAm	billiards optimization algorithm M	0,95757	0,82599	0,25235	2,03590	1,00000	0,90036	0,30502	2,20538	0,73538	0,52523	0,09563	1,35625	5,598	62,19
9	AAm	archery algorithm M	0,91744	0,70876	0,42160	2,04780	0,92527	0,75802	0,35328	2,03657	0,67385	0,55200	0,23738	1,46323	5,548	61,64
10	ESG	evolution of social groups (joo)	0,99906	0,79654	0,35056	2,14616	1,00000	0,82863	0,13102	1,95965	0,82333	0,55300	0,04725	1,42358	5,529	61,44
11	SIA	simulated isotropic annealing (joo)	0,95784	0,84264	0,41465	2,21513	0,98239	0,79586	0,20507	1,98332	0,68667	0,49300	0,09053	1,27020	5,469	60,76
12	EOm	extremal_optimization_M	0,76166	0,77242	0,31747	1,85155	0,99999	0,76751	0,23527	2,00277	0,74769	0,53969	0,14249	1,42987	5,284	58,71
13	BBO	biogeography based optimization	0,94912	0,69456	0,35031	1,99399	0,93820	0,67365	0,25682	1,86867	0,74615	0,48277	0,17369	1,40261	5,265	58,50
14	ACS	artificial cooperative search	0,75547	0,74744	0,30407	1,80698	1,00000	0,88861	0,22413	2,11274	0,69077	0,48185	0,13322	1,30583	5,226	58,06
15	DA	dialectical algorithm	0,86183	0,70033	0,33724	1,89940	0,98163	0,72772	0,28718	1,99653	0,70308	0,45292	0,16367	1,31967	5,216	57,95
16	BHAm	black hole algorithm M	0,75236	0,76675	0,34583	1,86493	0,93593	0,80152	0,27177	2,00923	0,65077	0,51646	0,15472	1,32195	5,196	57,73
17	ASO	anarchy society optimization	0,84872	0,74646	0,31465	1,90983	0,96148	0,79150	0,23803	1,99101	0,57077	0,54062	0,16614	1,27752	5,178	57,54
18	RFO	royal flush optimization (joo)	0,83361	0,73742	0,34629	1,91733	0,89424	0,73824	0,24098	1,87346	0,63154	0,50292	0,16421	1,29867	5,089	56,55
19	AOSm	atomic orbital search M	0,80232	0,70449	0,31021	1,81702	0,85660	0,69451	0,21996	1,77107	0,74615	0,52862	0,14358	1,41835	5,006	55,63
20	TSEA	turtle shell evolution algorithm (joo)	0,96798	0,64480	0,29672	1,90949	0,99449	0,61981	0,22708	1,84139	0,69077	0,42646	0,13598	1,25322	5,004	55,60
21	BSA	backtracking_search_algorithm	0,97309	0,54534	0,29098	1,80941	0,99999	0,58543	0,21747	1,80289	0,84769	0,36953	0,12978	1,34700	4,959	55,10
22	DE	differential evolution	0,95044	0,61674	0,30308	1,87026	0,95317	0,78896	0,16652	1,90865	0,78667	0,36033	0,02953	1,17653	4,955	55,06
23	SRA	successful restaurateur algorithm (joo)	0,96883	0,63455	0,29217	1,89555	0,94637	0,55506	0,19124	1,69267	0,74923	0,44031	0,12526	1,31480	4,903	54,48
24	CRO	chemical reaction optimisation	0,94629	0,66112	0,29853	1,90593	0,87906	0,58422	0,21146	1,67473	0,75846	0,42646	0,12686	1,31178	4,892	54,36
25	BIO	blood inheritance optimization (joo)	0,81568	0,65336	0,30877	1,77781	0,89937	0,65319	0,21760	1,77016	0,67846	0,47631	0,13902	1,29378	4,842	53,80
26	DOA	dream_optimization_algorithm	0,85556	0,70085	0,37280	1,92921	0,73421	0,48905	0,24147	1,46473	0,77231	0,47354	0,18561	1,43146	4,825	53,62
27	BSA	bird swarm algorithm	0,89306	0,64900	0,26250	1,80455	0,92420	0,71121	0,24939	1,88479	0,69385	0,32615	0,10012	1,12012	4,809	53,44
28	DEA	dolphin_echolocation_algorithm	0,75995	0,67572	0,34171	1,77738	0,89582	0,64223	0,23941	1,77746	0,61538	0,44031	0,15115	1,20684	4,762	52,91
29	HS	harmony search	0,86509	0,68782	0,32527	1,87818	0,99999	0,68002	0,09590	1,77592	0,62000	0,42267	0,05458	1,09725	4,751	52,79
30	SSG	saplings sowing and growing	0,77839	0,64925	0,39543	1,82308	0,85973	0,62467	0,17429	1,65869	0,64667	0,44133	0,10598	1,19398	4,676	51,95
31	BCOm	bacterial chemotaxis optimization M	0,75953	0,62268	0,31483	1,69704	0,89378	0,61339	0,22542	1,73259	0,65385	0,42092	0,14435	1,21912	4,649	51,65
32	ABO	african buffalo optimization	0,83337	0,62247	0,29964	1,75548	0,92170	0,58618	0,19723	1,70511	0,61000	0,43154	0,13225	1,17378	4,634	51,49
33	(PO)ES	(PO) evolution strategies	0,79025	0,62647	0,42935	1,84606	0,87616	0,60943	0,19591	1,68151	0,59000	0,37933	0,11322	1,08255	4,610	51,22
34	FBA	fractal-based Algorithm	0,79000	0,65134	0,28965	1,73099	0,87158	0,56823	0,18877	1,62858	0,61077	0,46062	0,12398	1,19537	4,555	50,61
35	TSm	tabu search M	0,87795	0,61431	0,29104	1,78330	0,92885	0,51844	0,19054	1,63783	0,61077	0,38215	0,12157	1,11449	4,536	50,40
36	BSO	brain storm optimization	0,93736	0,57616	0,29688	1,81041	0,93131	0,55866	0,23537	1,72534	0,55231	0,29077	0,11914	0,96222	4,498	49,98
37	WOAm	wale optimization algorithm M	0,84521	0,56298	0,26263	1,67081	0,93100	0,52278	0,16365	1,61743	0,66308	0,41138	0,11357	1,18803	4,476	49,74
38	AEFA	artificial electric field algorithm	0,87700	0,61753	0,25235	1,74688	0,92729	0,72698	0,18064	1,83490	0,66615	0,11631	0,09508	0,87754	4,459	49,55
39	AEO	artificial ecosystem-based optimization algorithm	0,91380	0,46713	0,26470	1,64563	0,90223	0,43705	0,21400	1,55327	0,66154	0,30800	0,28563	1,25517	4,454	49,49
40	CAm	camel algorithm M	0,78684	0,56042	0,35133	1,69859	0,82772	0,56041	0,24336	1,63149	0,64846	0,33092	0,13418	1,11356	4,444	49,37
41	ACOm	ant colony optimization M	0,88190	0,66127	0,30377	1,84693	0,85873	0,58680	0,15051	1,59604	0,59667	0,37333	0,02472	0,99472	4,438	49,31
42	CMAES	covariance_matrix_adaptation_evolution_strategy	0,76258	0,72089	0,00000	1,48347	0,82056	0,79616	0,00000	1,61672	0,75846	0,49077	0,00000	1,24923	4,349	48,33
43	DA_duelist	duelist_algorithm	0,92782	0,53778	0,27792	1,74352	0,86957	0,47536	0,18193	1,52686	0,62153	0,33569	0,11715	1,07437	4,345	48,28
44	BFO-GA	bacterial foraging optimization - ga	0,89150	0,55111	0,31529	1,75790	0,96982	0,39612	0,06305	1,42899	0,72667	0,27500	0,03525	1,03692	4,224	46,93
	BIA	bison_algorithm	0,76185	0,40027	0,25201	1,41413	0,76210	0,45225	0,19296	1,40731	0,48769	0,19877	0,10058	0,78704	3,608	40,09
	RW	random walk	0,48754	0,32159	0,25781	1,06694	0,37554	0,21944	0,15877	0,75375	0,27969	0,14917	0,09847	0,52734	2,348	26,09

Conclusões

O Bison Algorithm apresenta uma abordagem interessante ao separar explicitamente os agentes voltados à diversificação daqueles voltados à intensificação, mas, em sua implementação atual, apresenta desempenho inferior ao das meta-heurísticas modernas. Seu principal valor está justamente nessa divisão clara de papéis, que pode ser incorporada com sucesso a abordagens híbridas. 

Os resultados dos testes mostram que o algoritmo apresenta desempenho mediano, sem alcançar o nível das melhores meta-heurísticas, além de enfrentar dificuldades na resolução de problemas discretos. Para ser incluído na tabela de classificação, será necessário aprimorar significativamente os mecanismos de deslocamento e de adaptação dos parâmetros. O algoritmo pode ser útil em problemas nos quais a simplicidade da implementação e a interpretabilidade sejam importantes, mas que não exijam precisão máxima.

Figura 2. Graduação de cores dos algoritmos de acordo com os respectivos testes

Figura 3. Histograma dos resultados dos testes dos algoritmos (em uma escala de 0 a 100, quanto maior, melhor, em que 100 é o resultado teórico máximo possível; o arquivo contém o script para calcular a tabela de classificação)

Pontos fortes e fracos do algoritmo BIA:

Pontos fortes:

1. Implementação simples.
2. Rápido.

Pontos fracos:

1. Dispersão dos valores em funções de baixa e média dimensionalidade.

Foi anexado ao artigo um arquivo com as versões atualizadas dos códigos dos algoritmos. O autor do artigo não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, pois muitos deles foram modificados para melhorar sua capacidade de busca. As conclusões e avaliações apresentadas nos artigos baseiam-se nos resultados dos experimentos realizados.

• github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

Programas utilizados no artigo

#	Nome	Tipo	Descrição
1	#C_AO.mqh	Arquivo de inclusão	Classe base dos algoritmos populacionais de otimização
2	#C_AO_enum.mqh	Arquivo de inclusão	Enumeração dos algoritmos populacionais de otimização
3	TestFunctions.mqh	Arquivo de inclusão	Biblioteca de funções de teste
4	TestStandFunctions.mqh	Arquivo de inclusão	Biblioteca de funções da bancada de testes
5	Utilities.mqh	Arquivo de inclusão	Biblioteca de funções auxiliares
6	CalculationTestResults.mqh	Arquivo de inclusão	Script para calcular os resultados da tabela comparativa
7	Testing AOs.mq5	Script	Bancada de testes unificada para todos os algoritmos populacionais de otimização
8	Simple use of population optimization algorithms.mq5	Script	Exemplo simples de uso de algoritmos populacionais de otimização sem visualização
9	Test_AO_BIA.mq5	Script	Bancada de testes para o BIA