Algoritmos de otimização populacionais: enxame de pássaros (Bird Swarm Algorithm, BSA)

Conteúdo:

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

1. Introdução

As aves são seres fascinantes que desempenham um papel importante na natureza e no ecossistema. Acredita-se que elas tenham evoluído dos dinossauros, seus parentes mais próximos. Um exemplo famoso é o Archaeopteryx, a ave mais antiga conhecida, que viveu cerca de 150 milhões de anos atrás. Muitas vezes, as aves são vistas como indicadores do estado do ambiente, já que mudanças em suas populações e comportamentos podem sinalizar problemas no ecossistema, como poluição, perda de habitat e mudanças climáticas. Existem mais de 10.000 espécies de aves conhecidas no mundo, e cada uma delas possui adaptações únicas ao seu modo de vida.

Algumas aves conseguem voar por longas distâncias, outras são capazes de mergulhar em grandes profundidades, e algumas têm habilidades vocais incríveis. Elas desempenham um papel essencial no ecossistema, espalhando sementes, controlando populações de insetos e outros animais, além de serem uma importante fonte de alimento para predadores. Muitas espécies de aves migram por longos períodos, convivendo com outros membros da sua espécie em bandos, e atravessam milhares de quilômetros em busca de comida ou locais para se reproduzir. Esse fenômeno destaca as impressionantes habilidades de navegação, resistência, interação e cooperação em grupo. As aves são uma parte extremamente diversa e vital do nosso planeta.

O Bird Swarm Algorithm (BSA) é um algoritmo evolutivo fascinante, inspirado na biologia e que utiliza a inteligência de enxame, baseado nas interações sociais e no comportamento de bandos de aves. Criado por Meng e sua equipe em 2015, o BSA traz uma abordagem única para otimização, unindo três aspectos principais do comportamento das aves: voo, busca por alimento, vigilância. Nos enxames eletrônicos, cada "ave" tem suas próprias táticas e estratégias, criando um sistema de interação coletiva cheio de inteligência algorítmica e criatividade. Aqui, o que conta não são apenas os esforços individuais, mas também a capacidade de colaborar, trocar informações e apoiar uns aos outros na busca por um objetivo comum de otimização.  

Indivíduos diferentes no BSA podem adotar diferentes estratégias de busca. As aves podem alternar aleatoriamente entre comportamento de voo, vigilância e busca por alimento. O algoritmo de design biônico inclui a busca por alimento com base na aptidão global e individual. As aves também tentam se deslocar para o centro da população, o que pode levar à competição com outras aves ou ao afastamento do bando. O comportamento das aves envolve voos regulares e migrações, além de alternar entre os papéis de "produtor" e "pedinte". No contexto do BSA, cada indivíduo em uma determinada iteração segue sua própria estratégia de busca, o que torna o algoritmo versátil e eficiente.

No entanto, como muitos algoritmos de inteligência de enxame, o BSA pode enfrentar problemas de convergência prematura e acabar preso em soluções subótimas. Para garantir uma convergência mais rápida e precisa, várias técnicas foram desenvolvidas para equilibrar a exploração e o uso prático durante o processo de otimização.

O BSA se inspira no comportamento das aves e se baseia na interação coletiva dos bandos, que é o coração do algoritmo:

• Comportamento de bando. Muitas aves, como estorninhos, andorinhas e gansos, voam em bandos. Isso ajuda a diminuir a resistência do ar e a economizar energia durante as migrações ou na busca por alimento.

• Comunicação. As aves se comunicam de várias maneiras, como por meio de sons, gestos e posturas. Isso permite que elas coordenem suas ações, alertem sobre perigos e organizem a busca por alimento.

• Adaptabilidade. As aves são altamente adaptáveis às mudanças no ambiente. Elas conseguem reagir rapidamente a ameaças, alterações climáticas e variações na disponibilidade de alimentos, ajustando seu comportamento e rotas de migração conforme necessário.

• Liderança e seguimento. Em um bando de aves, geralmente há um líder que define a direção do voo, e as outras o seguem. Esse princípio de liderança e seguimento é incorporado no BSA para tornar a busca por soluções ótimas mais eficiente.

O BSA usa esses princípios do comportamento das aves para desenvolver uma metodologia de otimização eficiente, imitando o comportamento coletivo dos bandos na solução de diferentes problemas de otimização. O BSA não é apenas um algoritmo; é uma jornada fascinante pelo mundo da otimização, onde as interações sociais das aves servem como inspiração para resolver problemas complexos de maneira eficaz.

2. Descrição do algoritmo

Agora, vamos mergulhar na lógica do BSA, que pode parecer um pouco complexa e confusa à primeira vista. Antes de começar a implementar o código, é útil criar um pseudocódigo para o algoritmo, que servirá como base para sua execução. Isso vai facilitar bastante entender os princípios que guiam o BSA.

Aqui está o pseudocódigo para o Bird Swarm Algorithm (BSA), que oferece uma visão geral do algoritmo, modelando o comportamento de um bando de aves:

1. Inicializar N soluções e os parâmetros associados
2. Gerar novas soluções:
3. Se a ave está voando:
    4. Se a ave é uma "produtora":
        5. Procurar uma nova área com alimento
    6. Caso contrário:
        7. A ave "pedinte" segue a produtora
8. Caso contrário:
    9. Se a ave está se alimentando:
        10. A ave se alimenta
    11. Caso contrário:
        12. A ave permanece em estado de alerta (vigilante)
13. Avaliar a adequação das novas soluções
14. Atualizar as soluções
15. Se o critério de parada for atingido:
    16. Encerrar o algoritmo
17. Caso contrário:
    18. Retornar ao passo 2

Fórmula do passo 5, para a ave que busca uma nova área com alimento:

 xn = RNDg (min, max, producerPower)

onde:

• xn é o novo valor da coordenada
• RNDg é um número aleatório com distribuição normal centrado na coordenada atual
• min e max são os limites da distribuição
• producerPower é o desvio padrão para a produtora

Essa fórmula indica que a ave produtora pode migrar em qualquer direção dentro do espaço de busca, com maior probabilidade nas proximidades de sua posição atual. Isso garante que as aves explorem novas áreas em busca de alimento.

Fórmula do passo 7, para a ave pedinte que segue a produtora:

xn = x + (xK - x) * FL * RNDg (-1.0, 1.0, scroungerPower)

onde:

• xn é o novo valor da coordenada
• x é a melhor coordenada histórica da pedinte
• xK é a melhor coordenada histórica da produtora, sendo a produtora uma ave aleatória na posição K na população
• RNDg é um número aleatório com distribuição normal centrado em 0, com limites "-1.0" e "1.0"
• scroungerPower é o desvio padrão para a pedinte

Essa fórmula mostra que a ave pedinte se orienta pelas suas melhores coordenadas e pelas melhores coordenadas da melhor ave no bando (a produtora se guia pelas coordenadas atuais, não pelas melhores). Isso modela o comportamento de seguir o líder no bando.

Fórmula do passo 10, aplicável à ave durante a alimentação fora do voo:

xn = x + (p - x) * C * r1 + (g - x) * S * r2

onde:

• xn é o novo valor da coordenada
• x é a coordenada atual
• p é a melhor coordenada histórica da ave que está se alimentando
• g são as melhores coordenadas históricas da população (a melhor solução global)
• r1 é um número aleatório uniforme no intervalo [0.0 ... 1.0]
• r2 é um número aleatório uniforme no intervalo [0.0 ... 1.0]
• C é o coeficiente cognitivo, parâmetro externo
• S é o coeficiente social, parâmetro externo

Essa fórmula descreve o momento de alimentação, onde o comportamento da ave se baseia em sua própria experiência (posição atual e melhor posição passada) e na experiência do bando.

Fórmula do passo 12, para a ave em estado de alerta:

xn = x + A1 * (mean [c] - x) * r1 + A2 * (xK - x) * r2

onde:

• xn é o novo valor da coordenada
• x é a melhor coordenada histórica da ave vigilante
• r1 é um número aleatório uniforme no intervalo [0.0 ... 1.0]
• r2 é um número aleatório uniforme no intervalo [-1.0 ... 1.0]
• mean [c] é o valor médio da coordenada c, baseado nas melhores coordenadas de todas as aves no bando
  

A1 é o coeficiente de ajuste que considera a influência das coordenadas médias do centro do bando:

A1 = a1 * exp (-pFit * N / (sumFit + e))

onde:

• a1 é o coeficiente, parâmetro externo
• e é um valor mínimo para evitar divisão por 0
• pFit é a melhor adequação da ave vigilante
• sumFit é a soma das melhores adequações das aves no bando
• N é o número de aves no bando

A2 é o coeficiente de ajuste que leva em conta a influência da posição da ave observada (aquela que está no campo de visão da ave vigilante) no comportamento da vigilante. Fórmula para A2:

A2 = a2 * exp (((pFit - pFitK) / (|pFitK - pFit| + e)) * (N * pFitK / (sumFit + e)))

onde:

• a2 é o coeficiente, parâmetro externo
• e é um valor mínimo para evitar divisão por 0
• pFit é a melhor adequação da ave vigilante
• pFitK é a melhor adequação da ave aleatoriamente escolhida na população K (a ave observada pela vigilante)
• sumFit é a soma das melhores adequações das aves no bando
• N é o número de aves no bando

Assim, a ave vigilante monitora o ambiente ao redor, alertando seus companheiros sobre perigos oportunamente. Esse é o comportamento mais complexo descrito no algoritmo, por considerar a adaptabilidade de todas as aves da população, além da própria ave vigilante e da ave que está observando. Basicamente, a ave vigilante se move na direção da adaptabilidade geral da população, considerando também a posição da ave que está sob sua vigilância.

O texto destacado em cores no pseudocódigo corresponde aos elementos lógicos do BSA, representados no diagrama da Figura 1.

Figura 1. Diagrama lógico do algoritmo BSA.

O diagrama na Figura 1 é uma visualização do algoritmo BSA, que modela o comportamento de um bando de aves. As principais características desse algoritmo incluem:

1. Inicialização das soluções. O algoritmo começa com a inicialização de um conjunto de soluções e dos parâmetros associados. Isso inclui a distribuição inicial das aves (ou soluções) no espaço de busca.
2. Comportamento de voo. Durante a execução do algoritmo, cada ave pode estar "voando" ou "não voando". Esse estado afeta a capacidade da ave de descobrir novas soluções. 
3. Comportamento de busca por alimento. Se a ave está "voando", ela pode se tornar uma "produtora" e iniciar a busca por um novo local com alimento, ou se tornar uma "pedinte", seguindo a produtora.
4. Comportamento de alimentação. Se a ave "não está voando", ela ou se alimenta ou permanece vigilante. Isso pode representar um estado de espera ou de observação do ambiente ao redor.
5. Avaliação e atualização das soluções. Após a geração de novas soluções, é feita a avaliação de sua adaptabilidade ou qualidade.
6. Critério de parada. O algoritmo continua o ciclo de geração e atualização de soluções até que seja alcançado um critério de parada. Isso pode ser um número específico de iterações, a obtenção de um nível de qualidade da solução definido ou outro critério.

Gostaria de destacar que o BSA é um algoritmo dinâmico, que se adapta e evolui durante o processo de busca pela solução ótima.

Agora, vamos escrever o código do algoritmo BSA. Para cada agente, definiremos uma estrutura chamada "S_BSA_Agent", que representará uma solução individual do problema de otimização e descreverá uma ave no bando.

A estrutura contém os seguintes campos:

• cBest[] - um array para armazenar as melhores coordenadas do agente.
• fBest - uma variável para armazenar a melhor avaliação de adaptabilidade do agente.
• Init - um método da estrutura "S_BSA_Agent", que inicializa os campos da estrutura. Ele recebe um argumento inteiro “coords” - o número de coordenadas, usado para redimensionar o array “cBest” usando a função “ArrayResize”.

A variável "fBest" é inicialmente configurada com o menor valor possível para um número do tipo double, o que significa a pior adaptabilidade possível.

//——————————————————————————————————————————————————————————————————————————————
struct S_BSA_Agent
{
    double cBest []; //best coordinates
    double fBest;    //best fitness

    void Init (int coords)
    {
      ArrayResize (cBest, coords);
      fBest = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Vamos definir a classe "C_AO_BSA" para o algoritmo BSA, que é derivada da classe base de algoritmos populacionais "C_AO" e contém os seguintes campos e métodos:

1. Campos públicos:

• ao_name - nome do algoritmo de otimização.
• ao_desc - descrição do algoritmo de otimização.
• popSize - tamanho da população.
• params - array de parâmetros do algoritmo.
• flyingProb - probabilidade de voo.
• producerProb - probabilidade de produção.
• foragingProb - probabilidade de coleta.
• a1 - constante a1 [0...2].
• a2 - constante a2 [0...2].
• C - coeficiente cognitivo.
• S - coeficiente social.
• FL - constante FL [0...2].
• producerPower - desvio padrão no comportamento do produtor.
• scroungerPower - desvio padrão no comportamento do pedinte.

2. Métodos:

• C_AO_BSA - construtor da classe, que inicializa os campos da classe.
• SetParams - método para definir os parâmetros do algoritmo.
• Init - método para inicializar o algoritmo. Recebe os limites mínimo e máximo do espaço de busca, o passo de busca e o número de épocas.
• Moving - método para movimentar os agentes.
• Revision - método para revisar os agentes.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BSA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_BSA () { }
  C_AO_BSA ()
  {
    ao_name = "BSA";
    ao_desc = "Bird Swarm Algorithm";

    popSize        = 20;  //population size

    flyingProb     = 0.8;  //Flight probability
    producerProb   = 0.25; //Producer probability
    foragingProb   = 0.55; //Foraging probability
    a1             = 0.6;  //a1 constant [0...2]
    a2             = 0.05; //a2 constant [0...2]
    C              = 0.05; //Cognitive coefficient
    S              = 1.1;  //Social coefficient
    FL             = 1.75; //FL constant [0...2]
    producerPower  = 7.05; //Producer power
    scroungerPower = 2.60; //Scrounger power

    ArrayResize (params, 11);

    params [0].name = "popSize";         params [0].val  = popSize;

    params [1].name  = "flyingProb";     params [1].val  = flyingProb;
    params [2].name  = "producerProb";   params [2].val  = producerProb;
    params [3].name  = "foragingProb";   params [3].val  = foragingProb;
    params [4].name  = "a1";             params [4].val  = a1;
    params [5].name  = "a2";             params [5].val  = a2;
    params [6].name  = "C";              params [6].val  = C;
    params [7].name  = "S";              params [7].val  = S;
    params [8].name  = "FL";             params [8].val  = FL;
    params [9].name  = "producerPower";  params [9].val  = producerPower;
    params [10].name = "scroungerPower"; params [10].val = scroungerPower;
  }

  void SetParams ()
  {
    popSize        = (int)params [0].val;

    flyingProb     = params [1].val;
    producerProb   = params [2].val;
    foragingProb   = params [3].val;
    a1             = params [4].val;
    a2             = params [5].val;
    C              = params [6].val;
    S              = params [7].val;
    FL             = params [8].val;
    producerPower  = params [9].val;
    scroungerPower = params [10].val;
  }

  bool Init (const double &rangeMinP  [], //minimum search range
             const double &rangeMaxP  [], //maximum search range
             const double &rangeStepP [], //step search
             const int     epochsP = 0);  //number of epochs

  void Moving   ();
  void Revision ();
  void Injection (const int popPos, const int coordPos, const double value);

  //----------------------------------------------------------------------------
  double flyingProb;      //Flight probability
  double producerProb;    //Producer probability
  double foragingProb;    //Foraging probability
  double a1;              //a1 constant [0...2]
  double a2;              //a2 constant [0...2]
  double C;               //Cognitive coefficient
  double S;               //Social coefficient
  double FL;              //FL constant [0...2]
  double producerPower;   //Producer power
  double scroungerPower;  //Scrounger power

  S_BSA_Agent agent [];


  private: //-------------------------------------------------------------------
  double mean [];  //represents the element of the average position of the whole bird’s swarm
  double N;
  double e;        //epsilon

  void BirdProducer  (int pos);
  void BirdScrounger (int pos);
  void BirdForaging  (int pos);
  void BirdVigilance (int pos);
};
//——————————————————————————————————————————————————————————————————————————————

O método "Init" da classe "C_AO_BSA" é usado para inicializar as variáveis da classe com base nos parâmetros fornecidos. Este método executa a inicialização padrão usando o método "StandardInit", que aceita os limites mínimo e máximo do espaço de busca, bem como o passo de busca.

Se a inicialização padrão for bem-sucedida, o método continua com a inicialização das variáveis "N" e "e". O valor de "N" é definido como igual ao tamanho da população "popSize", e "e", o epsilon, é inicializado com o menor valor possível para um número do tipo double.

Em seguida, o método redimensiona o array "agent" para o tamanho de "popSize". Para cada elemento em "agent", o método "Init" é chamado com o parâmetro "coords". O tamanho do array "mean" também é ajustado para o tamanho de "coords", sendo que este array é usado para armazenar as coordenadas médias das aves na população.

O método retorna "true" se a inicialização for bem-sucedida e "false" caso contrário.

Este método realiza a configuração inicial do algoritmo de otimização BSA com os parâmetros fornecidos e o prepara para executar a otimização.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_BSA::Init (const double &rangeMinP  [], //minimum search range
                     const double &rangeMaxP  [], //maximum search range
                     const double &rangeStepP [], //step search
                     const int     epochsP = 0)  //number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  ArrayResize (agent, popSize);
  for (int i = 0; i < popSize; i++) agent [i].Init (coords);

  ArrayResize (mean, coords);

  N = popSize;
  e = DBL_MIN;

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

O método "Moving" da classe "C_AO_BSA" é utilizado para mover os agentes durante o processo de otimização. O método executa as seguintes ações:

• Se "revision" for igual a "false", as coordenadas dos agentes "a[i].c[c]" são inicializadas usando valores aleatórios dentro dos limites definidos. Em seguida, o sinalizador "revision" é definido como "true" e o método encerra sua execução.
• Se "revision" não for "false", novas coordenadas são calculadas para cada agente usando as fórmulas e probabilidades estabelecidas.

Nas épocas seguintes, o método chama funções que definem o comportamento de cada ave no bando, com base nas probabilidades calculadas: 

• Se a probabilidade de voo "flyingProb" for atendida, o agente "voa". Nesse caso, há dois possíveis comportamentos:

1. Se a probabilidade for menor que "producerProb", o agente é um "produtor" e busca um novo local para se alimentar.
   
2. Caso contrário, o agente é um "pedinte" e segue o produtor.

• Se o agente "não estiver voando", há duas possíveis ações:
  

1. Se a probabilidade for menor que "foragingProb", o agente "coleta" alimento. 
2. Caso contrário, o agente permanece em estado de "vigilância".

Este método é responsável por atualizar as coordenadas dos agentes no algoritmo de otimização BSA conforme a época atual, os valores aleatórios e as probabilidades.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BSA::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    //bird is flying------------------------------------------------------------
    if (u.RNDprobab () < flyingProb)
    {
      //bird producer
      if (u.RNDprobab () < producerProb) BirdProducer  (i); //bird is looking for a new place to eat
      //bird is not a producer
      else                               BirdScrounger (i); //scrounger follows the  producer
    }
    //bird is not flying--------------------------------------------------------
    else
    {
      //bird foraging
      if (u.RNDprobab () < foragingProb) BirdForaging  (i); //bird feeds
      //bird is not foraging
      else                               BirdVigilance (i); //bird vigilance
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método "BirdProducer" da classe "C_AO_BSA" modela o comportamento do "produtor" no algoritmo BSA. O método executa as seguintes ações:

• Inicializa a variável "x", que será usada para armazenar a posição atual da ave.
• Em seguida, para cada coordenada do agente, são executadas as seguintes etapas:
• O valor de "x" é definido como a coordenada atual do agente.
• O valor de "x" é atualizado usando uma distribuição gaussiana, onde a média é a coordenada atual, e o intervalo e o desvio padrão são determinados pelos valores "rangeMin", "rangeMax" e "producerPower".
• O novo valor da coordenada do agente é definido usando o método "SeInDiSp", que ajusta o valor de "x" conforme o intervalo de busca e o passo.

Esse método modela o comportamento do "produtor" no BSA, que busca novos locais de alimento (ou seja, novas soluções potenciais), utilizando a distribuição gaussiana para explorar o espaço de busca.

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdProducer  (int pos)
{
  double x = 0.0; //bird position

  for (int c = 0; c < coords; c++)
  {
    x = a [pos].c [c];
    x = u.GaussDistribution (x, rangeMin [c], rangeMax [c], producerPower);

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método que modela o comportamento do "pedinte" é a função "BirdScrounger" na classe "C_AO_BSA". Ela realiza as seguintes ações:

• 1. Inicializa as variáveis "K", "x" e "xK". "K" é a posição de uma ave escolhida aleatoriamente no bando, "x" é a melhor posição da ave, e "xK" é a melhor posição atual da ave escolhida aleatoriamente no bando.
• 2. Inicia um loop que percorre todas as coordenadas.
• Escolhe uma ave aleatória que não seja a ave atual.
• Atualiza "x" e "xK" com base nas melhores posições da ave atual e da ave escolhida aleatoriamente.
• Atualiza "x" usando a distribuição gaussiana.
• Finalmente, atualiza a posição atual da ave usando o método "SeInDiSp", ajustando o valor de "x" de acordo com o intervalo de busca e o passo.

Esse método modela o comportamento do "pedinte" no BSA, utilizando a distribuição gaussiana para seguir o "produtor" (ou seja, ajustando sua posição em relação à do produtor).

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdScrounger (int pos)
{
  int    K  = 0;   //position of a randomly selected bird in a swarm
  double x  = 0.0; //best bird position
  double xK = 0.0; //current best position of a randomly selected bird in a swarm

  for (int c = 0; c < coords; c++)
  {
    do K = u.RNDminusOne (popSize);
    while (K == pos);

    x  = agent [pos].cBest [c];
    xK = agent   [K].cBest [c];

    x = x + (xK - x) * FL * u.GaussDistribution (0, -1.0, 1.0, scroungerPower);

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Para a ave que não está voando no momento e que está se alimentando, o método "BirdForaging" na classe "C_AO_BSA" é utilizado. Dentro do loop por todas as coordenadas, o método realiza as seguintes ações:

• Atualiza "x", "p" e "g" com base nas posições atuais e nas melhores posições da ave, bem como na melhor posição global.
• Gera dois números aleatórios "r1" e "r2".
• Atualiza "x" usando esses números aleatórios, além das constantes "C" e "S".
• Ajusta a posição obtida da ave usando a função "SeInDiSp".

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdForaging  (int pos)
{
  double x  = 0.0; //current bird position
  double p  = 0.0; //best bird position
  double g  = 0.0; //best global position
  double r1 = 0.0; //uniform random number [0.0 ... 1.0]
  double r2 = 0.0; //uniform random number [0.0 ... 1.0]

  for (int c = 0; c < coords; c++)
  {
    x = a     [pos].c     [c];
    p = agent [pos].cBest [c];
    g = cB                [c];

    r1 = u.RNDprobab ();
    r2 = u.RNDprobab ();

    x = x + (p - x) * C * r1 + (g - x) * S * r2;

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Por fim, o método mais complexo, que modela o comportamento da ave vigilante, é o "BirdVigilance". Ela realiza as seguintes ações:

• Calcula a soma dos melhores valores de adaptabilidade de todas as aves no bando.
• Calcula o valor médio de cada coordenada para todas as aves do bando.
• Escolhe uma ave aleatória que não seja a ave atual.
• Atualiza "pFit" e "pFitK" com base nos melhores valores de adaptabilidade da ave atual e da ave escolhida aleatoriamente.
• Calcula "A1" e "A2" usando uma função exponencial que depende de "pFit", "pFitK", "N", "sumFit" e "e".
• Inicia um loop por todas as coordenadas: 
• Gera dois números aleatórios "r1" e "r2".
• Atualiza "x" e "xK" com base nas melhores posições da ave atual e da ave escolhida aleatoriamente.
• Atualiza "x" usando "A1", "A2", "r1" e "r2".
• Ajusta a posição atual da ave usando a função "SeInDiSp".

//——————————————————————————————————————————————————————————————————————————————
void  C_AO_BSA::BirdVigilance (int pos)
{
  int    K      = 0;   //position of a randomly selected bird in a swarm
  double sumFit = 0.0; //best birds fitness sum
  double pFitK  = 0.0; //best fitness of a randomly selected bird
  double pFit   = 0.0; //best bird fitness
  double A1     = 0.0;
  double A2     = 0.0;
  double r1     = 0.0; //uniform random number [ 0.0 ... 1.0]
  double r2     = 0.0; //uniform random number [-1.0 ... 1.0]
  double x      = 0.0; //best bird position
  double xK     = 0.0; //best position of a randomly selected bird in a swarm

  ArrayInitialize (mean, 0.0);

  for (int i = 0; i < popSize; i++) sumFit += agent [i].fBest;

  for (int c = 0; c < coords; c++)
  {
    for (int i = 0; i < popSize; i++) mean [c] += a [i].c [c];

    mean [c] /= popSize;
  }

  do K = u.RNDminusOne (popSize);
  while (K == pos);

  pFit  = agent [pos].fBest;
  pFitK = agent   [K].fBest;

  A1 = a1 * exp (-pFit * N / (sumFit + e));
  A2 = a2 * exp (((pFit - pFitK) / (fabs (pFitK - pFit) + e)) * (N * pFitK / (sumFit + e)));

  for (int c = 0; c < coords; c++)
  {
    r1 = u.RNDprobab ();
    r2 = u.RNDfromCI (-1, 1);

    x  = agent [pos].cBest [c];
    xK = agent   [K].cBest [c];

    x = x + A1 * (mean [c] - x) * r1 + A2 * (xK - x) * r2;

    a [pos].c [c] = u.SeInDiSp (x, rangeMin [c], rangeMax [c], rangeStep [c]);
  }
}
//——————————————————————————————————————————————————————————————————————————————

Para concluir, o método "Revision" da classe "C_AO_BSA" é utilizado para atualizar a melhor solução global e as melhores posições dos agentes. O método executa as seguintes ações:

• Atualiza a melhor solução global.
• Atualiza os valores anteriores das melhores funções de adaptabilidade e as coordenadas dos agentes.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BSA::Revision ()
{
  //----------------------------------------------------------------------------
  int ind = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) ind = i;
  }

  if (ind != -1)
  {
    fB = a [ind].f;
    ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY);
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > agent [i].fBest)
    {
      agent [i].fBest = a [i].f;
      ArrayCopy (agent [i].cBest, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultados dos testes

Gostaria de destacar os resultados obtidos pelo algoritmo Bird Swarm Algorithm (BSA) em diferentes conjuntos de funções. A pontuação geral do BSA em todas as funções de teste foi de 4.80947, correspondendo a 53,44% do resultado máximo possível. Esse desempenho indica a eficácia geral do algoritmo e sugere que o Bird Swarm Algorithm tem potencial para resolver com sucesso uma variedade de problemas de otimização em diferentes funções.

BSA|Bird Swarm Algorithm|20.0|0.8|0.25|0.55|0.6|0.05|0.05|1.1|1.75|7.05|2.6|
=============================
5 Hilly's; Func runs: 10000; resultado: 0.8930600046782612
25 Hilly's; Func runs: 10000; resultado: 0.6489975525320968
500 Hilly's; Func runs: 10000; resultado: 0.262496551797822
=============================
5 Forest's; Func runs: 10000; resultado: 0.9241962617798402
25 Forest's; Func runs: 10000; resultado: 0.7112057472851052
500 Forest's; Func runs: 10000; resultado: 0.24938963509983267
=============================
5 Megacity's; Func runs: 10000; resultado: 0.6938461538461538
25 Megacity's; Func runs: 10000; resultado: 0.3261538461538461
500 Megacity's; Func runs: 10000; resultado: 0.1001230769230778
=============================
Pontuação total: 4.80947 (53.44%)

A visualização do desempenho do algoritmo mostra uma variação significativa nos resultados em diferentes funções de teste. Embora o BSA seja eficaz em explorar áreas locais da superfície de busca, ele pode enfrentar dificuldades ao ficar preso em armadilhas locais. Isso pode limitar sua capacidade de alcançar o ótimo global e levar a uma estabilidade insuficiente na busca da solução ideal.

A visualização do algoritmo na função de teste Skin serve apenas como um exemplo de seu funcionamento e não é considerada na tabela de classificação.

  BSA na função de teste Hilly.

  BSA na função de teste Forest.

BSA na função de teste Megacity.

BSA na função de teste Skin.

Vale destacar que, na função de teste suave Hilly com um grande número de variáveis, o algoritmo foi bem ineficiente, obtendo o pior desempenho na tabela de classificação entre todos os algoritmos avaliados. Por outro lado, nas funções Forest e na função discreta de alta dimensionalidade Megacity, o BSA mostrou resultados sólidos, especialmente quando comparado a outros algoritmos, inclusive alguns que estão em posições mais altas na tabela.

№	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	BGA	binary genetic algorithm	0,99992	0,99484	0,50483	2,49959	1,00000	0,99975	0,32054	2,32029	0,90667	0,96400	0,23035	2,10102	6,921	76,90
2	(P+O)ES	(P+O) evolution strategies	0,99934	0,91895	0,56297	2,48127	1,00000	0,93522	0,39179	2,32701	0,83167	0,64433	0,21155	1,68755	6,496	72,18
3	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
4	ESG	evolution of social groups	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
5	SIA	simulated isotropic annealing	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
6	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
7	BSA	bird swarm algorithm	0,90857	0,73661	0,25767	1,90285	0,90437	0,81619	0,16401	1,88457	0,61692	0,54154	0,10951	1,26797	5,055	56,17
8	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
9	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
10	(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
11	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
12	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
13	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
14	MEC	mind evolutionary computation	0,69533	0,53376	0,32661	1,55569	0,72464	0,33036	0,07198	1,12698	0,52500	0,22000	0,04198	0,78698	3,470	38,55
15	IWO	invasive weed optimization	0,72679	0,52256	0,33123	1,58058	0,70756	0,33955	0,07484	1,12196	0,42333	0,23067	0,04617	0,70017	3,403	37,81
16	Micro-AIS	micro artificial immune system	0,79547	0,51922	0,30861	1,62330	0,72956	0,36879	0,09398	1,19233	0,37667	0,15867	0,02802	0,56335	3,379	37,54
17	COAm	cuckoo optimization algorithm M	0,75820	0,48652	0,31369	1,55841	0,74054	0,28051	0,05599	1,07704	0,50500	0,17467	0,03380	0,71347	3,349	37,21
18	SDOm	spiral dynamics optimization M	0,74601	0,44623	0,29687	1,48912	0,70204	0,34678	0,10944	1,15826	0,42833	0,16767	0,03663	0,63263	3,280	36,44
19	NMm	Nelder-Mead method M	0,73807	0,50598	0,31342	1,55747	0,63674	0,28302	0,08221	1,00197	0,44667	0,18667	0,04028	0,67362	3,233	35,92
20	FAm	firefly algorithm M	0,58634	0,47228	0,32276	1,38138	0,68467	0,37439	0,10908	1,16814	0,28667	0,16467	0,04722	0,49855	3,048	33,87
21	GSA	gravitational search algorithm	0,64757	0,49197	0,30062	1,44016	0,53962	0,36353	0,09945	1,00260	0,32667	0,12200	0,01917	0,46783	2,911	32,34
22	BFO	bacterial foraging optimization	0,61171	0,43270	0,31318	1,35759	0,54410	0,21511	0,05676	0,81597	0,42167	0,13800	0,03195	0,59162	2,765	30,72
23	ABC	artificial bee colony	0,63377	0,42402	0,30892	1,36671	0,55103	0,21874	0,05623	0,82600	0,34000	0,14200	0,03102	0,51302	2,706	30,06
24	BA	bat algorithm	0,59761	0,45911	0,35242	1,40915	0,40321	0,19313	0,07175	0,66810	0,21000	0,10100	0,03517	0,34617	2,423	26,93
25	SA	simulated annealing	0,55787	0,42177	0,31549	1,29513	0,34998	0,15259	0,05023	0,55280	0,31167	0,10033	0,02883	0,44083	2,289	25,43
26	IWDm	intelligent water drops M	0,54501	0,37897	0,30124	1,22522	0,46104	0,14704	0,04369	0,65177	0,25833	0,09700	0,02308	0,37842	2,255	25,06
27	PSO	particle swarm optimisation	0,59726	0,36923	0,29928	1,26577	0,37237	0,16324	0,07010	0,60572	0,25667	0,08000	0,02157	0,35823	2,230	24,77
28	MA	monkey algorithm	0,59107	0,42681	0,31816	1,33604	0,31138	0,14069	0,06612	0,51819	0,22833	0,08567	0,02790	0,34190	2,196	24,40
29	SFL	shuffled frog-leaping	0,53925	0,35816	0,29809	1,19551	0,37141	0,11427	0,04051	0,52618	0,27167	0,08667	0,02402	0,38235	2,104	23,38
30	FSS	fish school search	0,55669	0,39992	0,31172	1,26833	0,31009	0,11889	0,04569	0,47467	0,21167	0,07633	0,02488	0,31288	2,056	22,84
31	RND	random	0,52033	0,36068	0,30133	1,18234	0,31335	0,11787	0,04354	0,47476	0,25333	0,07933	0,02382	0,35648	2,014	22,37
32	GWO	grey wolf optimizer	0,59169	0,36561	0,29595	1,25326	0,24499	0,09047	0,03612	0,37158	0,27667	0,08567	0,02170	0,38403	2,009	22,32
33	CSS	charged system search	0,44252	0,35454	0,35201	1,14907	0,24140	0,11345	0,06814	0,42299	0,18333	0,06300	0,02322	0,26955	1,842	20,46
34	EM	electroMagnetism-like algorithm	0,46250	0,34594	0,32285	1,13129	0,21245	0,09783	0,10057	0,41085	0,15667	0,06033	0,02712	0,24412	1,786	19,85

Considerações finais

O Bird Swarm Algorithm (BSA) é uma ferramenta de pesquisa intrigante, que se destaca pela sua lógica rica e pela forma como incorpora diferentes estados e estratégias de comportamento dos bandos de aves. Trabalhar com esse algoritmo foi uma experiência envolvente para mim, especialmente por conta de sua dinâmica complexa, onde as ações individuais e coletivas das aves seguem várias condições e combinações.

A complexidade do BSA também se reflete na abundância de parâmetros, que precisam ser ajustados cuidadosamente para alcançar os melhores resultados. Para otimizar esses parâmetros, desenvolvi um expert para rodar no modo de cálculos matemáticos do testador do MetaTrader 5, o que ajudou a encontrar bons parâmetros externos e garantiu ao algoritmo o 7º lugar no ranking. É possível haver potencial para melhorar ainda mais os resultados, e incentivo quem tiver interesse a experimentar com este algoritmo, pois acredito que ainda há muitas possibilidades inexploradas para alcançar melhores resultados, considerando especialmente as várias combinações e ordens de comportamento das aves (o artigo aborda 4 tipos de comportamento). 

Figura 2. Gradiente de cores dos algoritmos nos respectivos testes. Resultados iguais ou superiores a 0,99 estão destacados em branco.

Figura 3. Histograma dos resultados dos testes dos algoritmos (na escala de 0 a 100,

sendo 100 o resultado teórico máximo possível. O arquivo contém um script para calcular a tabela de classificação).

Prós e contras do Bird Swarm Algorithm (BSA):

Prós:

1. Bons resultados em funções desafiadoras como Forest e na função discreta de alta dimensionalidade Megacity.

Contras:

1. Implementação complexa.
2. Baixa convergência.
3. Escalabilidade limitada em funções suaves, como Hilly (problemas em tarefas de alta dimensionalidade).

No artigo está anexado um arquivo com as versões atualizadas dos códigos. O autor não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, ao serem feitas algumas modificações para melhorar suas capacidades de busca. As conclusões e opiniões apresentadas no artigo são baseadas nos resultados dos experimentos realizados.