Algoritmos de otimização populacionais: algoritmo de otimização de forrageamento bacteriano (BFO)

Conteúdo

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

1. Introdução

O algoritmo de otimização forrageamento bacteriano (BFO) é uma técnica fascinante que pode ser utilizada para encontrar soluções aproximadas para problemas extremamente complexos ou impossíveis de maximização ou minimização de funções numéricas. Reconhecido amplamente como um algoritmo global de otimização de grande interesse para otimização e controle distribuído, o BFO se inspira no comportamento social de busca de alimento da Escherichia coli. O BFO tem atraído a atenção dos pesquisadores devido à sua eficácia na resolução de problemas de otimização do mundo real que surgem em diversas áreas de aplicação. A biologia por trás da estratégia de forrageamento da E. coli é emulada de forma original e utilizada como um algoritmo de otimização simples.

Bactérias como a E. coli ou a salmonela estão entre os organismos mais bem-sucedidos do planeta. Essas bactérias móveis possuem apêndices semirrígidos chamados flagelos, com os quais se impulsionam por meio de um movimento de torção. Quando todos os flagelos giram no sentido anti-horário, cria-se um efeito de hélice e a bactéria se move em uma direção mais ou menos reta. Nesse caso, a bactéria realiza um movimento chamado natação (swims), em que todos os flagelos giram na mesma direção.

Os flagelos desempenham um papel fundamental na locomoção da bactéria E. coli, permitindo que ela role ou nade durante o processo de forrageamento. Quando os flagelos giram no sentido horário, cada um deles impulsiona a célula. Por outro lado, quando os flagelos giram em direções opostas, a bactéria realiza um movimento de cambalhota (tumble). Esse comportamento permite que a bactéria role com menos frequência em um ambiente favorável, enquanto em um ambiente prejudicial, ela realiza cambalhotas com mais frequência para buscar gradientes de nutrientes. O movimento dos flagelos no sentido anti-horário ajuda as bactérias a nadarem em alta velocidade.

No algoritmo mencionado, o comportamento das bactérias é determinado por um mecanismo chamado quimiotaxia bacteriana, que consiste na resposta motora desses microrganismos a estímulos químicos do ambiente. Esse mecanismo permite que a bactéria se mova em direção a atraentes (geralmente nutrientes) e se afaste de repelentes (substâncias potencialmente prejudiciais à bactéria). Os receptores responsáveis pela detecção de atraentes e repelentes estão localizados nos polos da bactéria.

Devido ao tamanho reduzido da bactéria, ela não consegue perceber a diferença de concentração de substâncias benéficas e prejudiciais entre os polos. As bactérias determinam os gradientes dessas substâncias medindo as alterações em suas concentrações durante o movimento. A velocidade desse movimento pode atingir várias vezes o comprimento da própria bactéria por segundo. Por exemplo, a bactéria Escherichia coli geralmente se move a uma velocidade de 10-20 vezes o seu próprio comprimento por segundo.

Figura 1. Replicação: divisão em bactérias originais (preservação do vetor de movimento) e clonadas (alteração do vetor de movimento).
Cambalhota - mudança no vetor de movimento da bactéria.

Se a direção de movimento escolhida pela bactéria corresponder a um aumento na concentração do atraente (uma diminuição na concentração do repelente), o tempo até a próxima cambalhota é prolongado. Devido ao pequeno tamanho da bactéria, o movimento browniano exerce uma forte influência em seu movimento. Como resultado, a bactéria se move, em média, na direção de substâncias benéficas e se afasta de substâncias nocivas.

O mecanismo considerado de movimentação bacteriana não é o único. Algumas bactérias possuem um único flagelo. Nesses casos, as variações de movimento da bactéria proporcionam diferentes modos de rotação e parada. No entanto, em todos os casos, se a bactéria se mover na direção correta, a duração desse movimento aumenta. Dessa forma, em geral, a quimiotaxia bacteriana pode ser definida como uma combinação complexa de natação e cambalhotas, permitindo que as bactérias permaneçam em áreas com alta concentração de nutrientes e evitem concentrações inaceitáveis de substâncias nocivas.

No contexto de um problema de otimização de mecanismo de busca, a quimiotaxia bacteriana também pode ser interpretada como um mecanismo para otimizar o uso de recursos alimentares conhecidos por uma bactéria e procurar novas áreas potencialmente mais valiosas.  Uma população de bactérias com abundância suficiente pode formar estruturas espaço-temporais complexas - um efeito conhecido como formação de estruturas em populações bacterianas. Esse efeito pode ser causado tanto pela quimiotaxia quanto por diversos outros motivos.

Para algumas bactérias, a formação dessas estruturas é explicada pelas propriedades reguladoras de seus produtos metabólicos. Um efeito semelhante pode ocorrer com base em fenômenos como magnetotaxia (sensibilidade a campos magnéticos), bioconvecção, geotaxia negativa (movimento preferencial de microorganismos contra a direção da gravidade) e outros. Geralmente, as bactérias percorrem uma distância maior em um ambiente favorável. Quando recebem alimento em quantidade suficiente, elas crescem em comprimento e, na temperatura adequada, se dividem ao meio, resultando em uma réplica exata de si mesmas.

Esse fenômeno inspirou Passino a introduzir o evento de reprodução no BFO. Devido à ocorrência de mudanças abruptas no ambiente ou a um ataque, o processo quimiotático pode ser interrompido, levando o grupo de bactérias a se deslocar para outra área. Isso representa um evento de eliminação e dispersão em uma população bacteriana real, onde todas as bactérias da região morrem ou o grupo se dispersa para uma nova parte do ambiente Além disso, os procedimentos considerados de quimiotaxia e reprodução são geralmente insuficientes para encontrar o máximo global de uma função objetivo multi-extremo, uma vez que esses procedimentos não permitem que as bactérias saiam dos máximos locais encontrados. O procedimento de eliminação e dispersão foi projetado para superar essa limitação. De acordo com a seleção natural (sobrevivência do mais apto), as bactérias com menor adaptação serão eliminadas, enquanto as bactérias com maior adaptação reproduzir-se-ão.

2. Descrição do algoritmo

A versão canônica do BFO inclui as seguintes etapas chave:

1. Inicialização da colônia de bactérias.
2. Quimiotaxia.
3. Enxameamento.
4. Reprodução.
5. Eliminação.

      
1. Inicialização do parâmetro.
As bactérias podem formar padrões espaço-temporais complexos e estáveis em alguns nutrientes semissólidos e podem sobreviver no ambiente se forem inicialmente colocadas juntas no centro dele. Além disso, sob certas condições, elas secretam sinais de atração intercelular, de modo que se agrupam e se protegem mutuamente.
2. Quimiotaxia.
As características das bactérias que se movem em busca de alimento podem ser encontradas de duas maneiras, isto é, na forma de natação e cambalhotas, que são conhecidas como quimiotaxia. Diz-se que uma bactéria "nada" se ela se move na direção certa e "dá cambalhotas" se ela se move em direção a um ambiente em deterioração.

3. Enxameamento.
Para que as bactérias alcancem o local mais rico em alimentos, é desejável que a bactéria ideal tente atrair outras bactérias antes do período de busca, de modo que, juntas, elas convirjam mais rapidamente em direção ao local desejado. Para isso, uma função de penalidade é adicionada à função de custo original, baseada na distância relativa de cada bactéria em relação à bactéria mais adaptada a esse período de pesquisa. Finalmente, quando todas as bactérias convergem para um ponto de decisão, essa função de penalidade se torna zero. O efeito de enxameamento ocorre quando as bactérias se reúnem em grupos e se movem em padrões concêntricos com uma alta densidade de bactérias.

4. Reprodução.
O conjunto inicial de bactérias, depois de passar por vários estágios quimiotáticos, chega ao estágio de multiplicação. Aqui, o melhor conjunto de bactérias é dividido em dois grupos. A metade mais saudável é substituída pela outra metade das bactérias, que são eliminadas porque têm menos capacidade de encontrar alimentos. Isso torna a população bacteriana constante ao longo do processo evolutivo.

5. Eliminação e dispersão.
Durante a evolução, pode ocorrer um evento súbito e imprevisto que pode alterar drasticamente a suavidade do processo de evolução e fazer com que uma grande quantidade de bactérias seja eliminada e/ou dispersa em um novo ambiente. Ironicamente, em vez de interromper o crescimento quimiotático normal de um conjunto de bactérias, esse evento desconhecido pode colocar um novo conjunto de bactérias mais próximo do local do alimento. Em uma perspectiva ampla, a eliminação e a dispersão são partes do comportamento da população em longas distâncias. Quando aplicados à otimização, isso ajuda a reduzir a estagnação frequentemente observada em algoritmos de busca paralela desse tipo.

Minha implementação do BFO difere um pouco da versão canônica; vamos nos aprofundar nas diferenças ao considerar seções específicas do código, com a justificativa para essas alterações. Em geral, as alterações na implementação não podem ser consideradas significativas, portanto, não atribuirei um "m" (versão modificada) ao nome do algoritmo. Friso apenas que os resultados melhoraram depois de fazer alterações no algoritmo.

Em seguida, veremos o algoritmo e o código da minha implementação.

Etapas do algoritmo:

1. Inicialização da colônia de bactérias.
2. Avaliação da saúde das bactérias (adaptação).
3. Replicação?
3.1. Sim. Fazemos replicação.
3.2. Não. p4.
4. Velho (limite de vida atingido)?
4.1. Sim. Damos uma cambalhota (mudança no vetor de movimento).
4.2. Não. p5.
5. Movimento na direção certa?
5.1. Sim. Continuação do movimento com o mesmo vetor.
5.2. Não. Damos uma cambalhota (mudança no vetor de movimento).
6. Avaliação da saúde das bactérias (adaptação).
7. Continuamos a partir do passo 3 até que o critério de parada seja atingido.

O diagrama do algoritmo é mostrado na Fig.1.

Figura 2. Diagrama de blocos da lógica do algoritmo BFO.

Comecemos com o código.

A descrição mais adequada para uma bactéria envolve a utilização de matrizes de coordenadas e vetores de movimento. Também abrange os valores de saúde atual e anterior da bactéria, bem como um contador de vidas. O contador de vidas é necessário para limitar a quantidade de movimentos consecutivos na mesma direção. Ao contrário da versão original, na qual a bactéria é destruída e uma nova é criada em um local aleatório do espaço de busca ao atingir o limite de vidas, é mais sensato criar um novo agente no local da melhor solução ou continuar movendo-se a partir da posição atual, mas alterando o vetor de direção. A segunda variante apresentou melhores resultados.

Na versão canônica, é utilizado um vetor de movimento constante, e com um grande número de vidas, isso resultaria no movimento retilíneo das bactérias ao longo de uma linha reta no espaço de busca, a menos que essa linha coincida com algum ponto extremo favorável. Nesse caso, o processo de movimento retilíneo ocorreria indefinidamente. No entanto, o contador desempenha o papel de uma cambalhota forçada, permitindo que a bactéria evite movimentos retilíneos ao longo de sua vida. Em funções que não possuem gradiente em determinadas áreas, eventualmente a bactéria chegará a um local onde poderá começar a aprimorar sua adaptação.

//——————————————————————————————————————————————————————————————————————————————
struct S_Bacteria
{
  double c  [];   //coordinates
  double v  [];   //vector
  double f;       //current health
  double fLast;   //previous health
  double lifeCNT; //life counter
};
//——————————————————————————————————————————————————————————————————————————————

Vamos declarar a classe do algoritmo BFO como C_AO_BFO. Essa classe inclui a definição da colônia de bactérias, os limites do espaço de busca, o valor da melhor solução e a matriz de coordenadas da melhor solução. Também vamos declarar os valores constantes dos parâmetros do algoritmo.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_BFO
{
  //----------------------------------------------------------------------------
  public: S_Bacteria b     []; //bacteria
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates

  public: void Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP);   //life counter

  public: void Swimming   ();
  public: void Evaluation ();

  //----------------------------------------------------------------------------
  private: double NewVector (int paramInd);
  private: S_Bacteria bT []; //bacteria
  private: double v      [];
  private: int    ind    [];
  private: double val    [];
  private: int    populationSize; //population size
  private: int    parameters;     //number of optimized parameters
  private: double lambda;         //lambda
  private: double reproduction;   //probability of reproduction
  private: int    lifeCounter;    //life counter
  private: bool   evaluation;

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

O método público Init() é responsável por inicializar as variáveis constantes, ajustar os tamanhos das matrizes, redefinir os sinalizadores e o valor da melhor solução.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO::Init (const int    paramsP,         //number of opt. parameters
                     const int    populationSizeP, //population size
                     const double lambdaP,         //lambda
                     const double reproductionP,   //probability of reproduction
                     const int    lifeCounterP)    //life counter
{
  fB = -DBL_MAX;
  evaluation = false;

  parameters      = paramsP;
  populationSize  = populationSizeP;
  lambda          = lambdaP;
  reproduction    = reproductionP;
  lifeCounter     = lifeCounterP;

  ArrayResize (rangeMax,  parameters);
  ArrayResize (rangeMin,  parameters);
  ArrayResize (rangeStep, parameters);
  ArrayResize (v,         parameters);

  ArrayResize (ind,       populationSize);
  ArrayResize (val,       populationSize);

  ArrayResize (b,  populationSize);
  ArrayResize (bT, populationSize);

  for (int i = 0; i < populationSize; i++)
  {
    ArrayResize (b [i].c,  parameters);
    ArrayResize (b [i].v,  parameters);
    b [i].f  = -DBL_MAX;
    b [i].fLast = -DBL_MAX;

    ArrayResize (bT [i].c,  parameters);
    ArrayResize (bT [i].v,  parameters);
  }

  ArrayResize (cB, parameters);
}
//——————————————————————————————————————————————————————————————————————————————

O primeiro método público que deve ser chamado em cada iteração é o Swimming (), que engloba toda a lógica principal do algoritmo.

void C_AO_BFO::Swimming ()
{}

Vamos analisar o método em detalhes. Na primeira iteração, quando a flag de avaliação é falsa, espalhamos as bactérias aleatoriamente por todo o espaço de busca, com distribuição uniforme. Nesta fase, as informações de saúde (adaptação) atual e anterior não são conhecidas, então atribuímos o valor DBL_MAX às variáveis correspondentes. Verificamos se as coordenadas obtidas aleatoriamente estão dentro dos limites e aplicamos a etapa de ajuste dos parâmetros otimizados. Nesta iteração, é necessário definir um vetor de movimento individual para cada bactéria usando o método privado NewVector () (que será discutido posteriormente). Todas as bactérias nadam uniformemente, em linha reta, com seu próprio vetor de movimento individual até que as condições para a sua alteração sejam atendidas.

//----------------------------------------------------------------------------
if (!evaluation)
{
  fB = -DBL_MAX;

  for (int s = 0; s < populationSize; s++)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);

      v [k] = rangeMax [k] - rangeMin [k];

      b [s].v [k] = NewVector (k);

      b [s].f  = -DBL_MAX;
      b [s].fLast = -DBL_MAX;

      b [s].lifeCNT = 0;
    }
  }

  evaluation = true;
}

Nas iterações subsequentes, são realizadas as operações de natação, cambalhota, replicação e destruição de bactérias quando o limite de vidas é atingido. A primeira operação na lógica é a reprodução (com probabilidade definida nos parâmetros), o que implica que a colônia de bactérias seja ordenada na iteração anterior em ordem decrescente de valor de saúde.

A reprodução desempenha um papel importante no algoritmo, acelerando a convergência ao melhorar a "constituição genética" da colônia bacteriana. Essa operação envolve uma divisão imaginária das bactérias em duas partes, permitindo que apenas a primeira metade da colônia se divida. A primeira metade é dividida ao meio, com a versão original dos pais sendo colocada na segunda metade da colônia. A bactéria progenitora continua seu movimento com o mesmo vetor, ao contrário do seu clone. O clone permanece no seu lugar na colônia e recebe um novo vetor de movimento. O pai e seu clone continuam a se mover a partir do ponto onde ocorreu a divisão.

r = RNDfromCI (0.0, 1.0);

//==========================================================================
if (r < reproduction)
{
  int st = populationSize / 2;
  for (int s = 0; s < st; s++)
  {
    //bacterium original--------------------------------------------------
    for (int k = 0; k < parameters; k++)
    {
      b [st + s].v [k] = b [s].v [k];
      b [st + s].c [k] = b [s].c [k] + b [s].v [k];
      b [st + s].c [k] = SeInDiSp (b [st + s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [st + s].fLast = b [s].f;
      b [st + s].lifeCNT++;
    }

    //bacterium clone-------------------------------------------------------
    for (int k = 0; k < parameters; k++)
    {
      b [s].v [k] = NewVector (k);
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT = 0;
    }
  }
}

Além disso, se a probabilidade de replicação não for realizada, verificamos se a bactéria atingiu o limite de vida. Na versão canônica do algoritmo, a "bactéria antiga" é destruída e uma nova bactéria é criada em um local aleatório do espaço de busca. No entanto, em casos mais gerais, as operações de reprodução e quimiotaxia não são suficientes para encontrar o máximo global de uma função de adaptação multi-extremo,
pois esses procedimentos não permitem que as bactérias escapem de mínimos locais que encontraram. O procedimento de eliminação é projetado para superar essa limitação. No entanto, como demonstrado por experimentos práticos com este e outros algoritmos, é mais eficaz simplesmente alterar o vetor de movimento nesses casos. O contador de vida é redefinido. O contador funciona como um gatilho para alterar a direção do movimento após um certo número de etapas (vidas). O número total de bactérias resultantes da replicação e eliminação permanece constante.

if (b [s].lifeCNT >= lifeCounter)
{
  for (int k = 0; k < parameters; k++)
  {
    b [s].v [k] = NewVector (k);
    b [s].c [k] = b [s].c [k] + b [s].v [k];
    b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    b [s].fLast = b [s].f;
    b [s].lifeCNT = 0;
  }
}

Se o limite de vida não tiver sido atingido, realizamos uma verificação para determinar se a bactéria está se movendo em direção a uma melhoria no gradiente da função de adaptação. Isso significa que verificamos os valores de saúde atual e anterior. Se a saúde melhorou, o vetor de movimento é mantido; caso contrário, a bactéria precisa fazer uma mudança de direção (alterar o vetor de movimento).

Na versão canônica, é realizada uma verificação rigorosa de "maior" entre a saúde atual e a anterior, enquanto na minha versão utilizo a verificação de "maior ou igual". Isso permite que a bactéria continue se movendo mesmo em uma região completamente "horizontal" da superfície de busca, onde não há gradiente na função de adaptação. Caso contrário, a bactéria ficaria girando infinitamente no mesmo lugar (sem alteração na saúde, o que significa que não há direção para nadar). Nessa fase, também é importante verificar se as novas coordenadas obtidas estão dentro dos limites do espaço de busca.

else
{
  if (b [s].f >= b [s].fLast)
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT++;
    }
  }
  else
  {
    for (int k = 0; k < parameters; k++)
    {
      b [s].v [k] = NewVector (k);
      b [s].c [k] = b [s].c [k] + b [s].v [k];
      b [s].c [k] = SeInDiSp (b [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      b [s].fLast = b [s].f;
      b [s].lifeCNT++;
    }
  }
}

O método NewVector () é um método privado para alterar o vetor de movimento (rolamento). O método é aplicado a cada coordenada. O conceito aqui é simples: multiplicamos a diferença entre os limites de busca para a coordenada v por um número aleatório r no intervalo [-1.0; 1.0] e, em seguida, multiplicamos pelo fator de escala lambda (um dos parâmetros do algoritmo). A bactéria utiliza o vetor de movimento sem alterações até que o limite de vidas seja atingido (nesse momento, uma nova bactéria é criada no mesmo local, mas com um novo vetor de movimento), durante a replicação (o clone recebe um novo vetor) e quando a saúde se deteriora (tentativa de encontrar um ambiente mais favorável).  

//——————————————————————————————————————————————————————————————————————————————
double C_AO_BFO::NewVector (int paramInd)
{
  double r = RNDfromCI (-1.0, 1.0);
  return lambda * v [paramInd] * r;
}
//——————————————————————————————————————————————————————————————————————————————

O segundo método público obrigatório a ser executado a cada iteração é o Evaluation (). Ele chama o método de classificação, verifica se há atualizações para a solução global, comparando a saúde da melhor bactéria na colônia classificada com a melhor solução encontrada.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_BFO::Evaluation ()
{
  Sorting ();

  if (b [0].f > fB)
  {
    fB = b [0].f;
    ArrayCopy (cB, b [0].c, 0, 0, WHOLE_ARRAY);
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultado dos testes

Esses são os resultados da bancada de testes para o BFO:

2023.01.21 12:52:46.501    Test_AO_BFO (.US500Cash,M1)    C_AO_BFO:50;0.01;0.8;100
2023.01.21 12:52:46.501    Test_AO_BFO (.US500Cash,M1)    =============================
2023.01.21 12:52:48.451    Test_AO_BFO (.US500Cash,M1)    5 Rastrigin's; Func runs 10000 result: 72.94540549092933
2023.01.21 12:52:48.451    Test_AO_BFO (.US500Cash,M1)    Score: 0.90383
2023.01.21 12:52:51.778    Test_AO_BFO (.US500Cash,M1)    25 Rastrigin's; Func runs 10000 result: 54.75744312933767
2023.01.21 12:52:51.778    Test_AO_BFO (.US500Cash,M1)    Score: 0.67848
2023.01.21 12:53:21.197    Test_AO_BFO (.US500Cash,M1)    500 Rastrigin's; Func runs 10000 result: 40.668487609790404
2023.01.21 12:53:21.197    Test_AO_BFO (.US500Cash,M1)    Score: 0.50391
2023.01.21 12:53:21.197    Test_AO_BFO (.US500Cash,M1)    =============================
2023.01.21 12:53:23.211    Test_AO_BFO (.US500Cash,M1)    5 Forest's; Func runs 10000 result: 0.8569098398505888
2023.01.21 12:53:23.211    Test_AO_BFO (.US500Cash,M1)    Score: 0.48471
2023.01.21 12:53:26.878    Test_AO_BFO (.US500Cash,M1)    25 Forest's; Func runs 10000 result: 0.37618151461180294
2023.01.21 12:53:26.878    Test_AO_BFO (.US500Cash,M1)    Score: 0.21279
2023.01.21 12:54:22.339    Test_AO_BFO (.US500Cash,M1)    500 Forest's; Func runs 10000 result: 0.08748190028975696
2023.01.21 12:54:22.339    Test_AO_BFO (.US500Cash,M1)    Score: 0.04948
2023.01.21 12:54:22.339    Test_AO_BFO (.US500Cash,M1)    =============================
2023.01.21 12:54:28.849    Test_AO_BFO (.US500Cash,M1)    5 Megacity's; Func runs 10000 result: 4.8
2023.01.21 12:54:28.849    Test_AO_BFO (.US500Cash,M1)    Score: 0.40000
2023.01.21 12:54:40.089    Test_AO_BFO (.US500Cash,M1)    25 Megacity's; Func runs 10000 result: 2.216
2023.01.21 12:54:40.089    Test_AO_BFO (.US500Cash,M1)    Score: 0.18467
2023.01.21 12:55:24.640    Test_AO_BFO (.US500Cash,M1)    500 Megacity's; Func runs 10000 result: 0.4232
2023.01.21 12:55:24.640    Test_AO_BFO (.US500Cash,M1)    Score: 0.03527

Olhando para a saída dos resultados da bancada de teste, é muito cedo para tirar conclusões definitivas, é necessário analisar os resultados em relação a outros participantes do teste.

  BFO na função de teste Rastrigin.

BFO na função de teste Forest.

BFO na função de teste Megacity.

Vamos prestar atenção ao resultado visual do teste. A animação confirmou a substituição do sinal "maior que" por "maior ou igual a" em nosso algoritmo, isso permitiu que as bactérias continuassem se movendo nas seções horizontais das funções de teste, veja, por exemplo, as funções Forest e Megacity, onde as bactérias tentam se mover mesmo onde não há nenhum gradiente de função. Também é necessário observar a capacidade de uma colônia bacteriana de se dividir em várias colônias separadas, visualmente divididas territorialmente em extremos locais separados, o que pode ser considerado uma característica positiva, embora o algoritmo não contenha nenhum método lógico para a formação de subcolônias. Em geral, é perceptível um movimento uniforme de bactérias no espaço de busca, sem tentativas de dar um salto brusco em qualquer uma das direções, o que é explicado por um movimento uniforme - quimiotaxia.

AO	Description	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
		10 params (5 F)	50 params (25 F)	1000 params (500 F)		10 params (5 F)	50 params (25 F)	1000 params (500 F)		10 params (5 F)	50 params (25 F)	1000 params (500 F)
IWO	otimização invasiva de ervas daninhas	1,00000	1,00000	0,33519	2,33519	0,79937	0,46349	0,41071	1,67357	0,75912	0,44903	0,94088	2,14903	100,000
ACOm	otimização de colônia de formigas M	0,36118	0,26810	0,17991	0,80919	1,00000	1,00000	1,00000	3,00000	1,00000	1,00000	0,10959	2,10959	95,996
COAm	algoritmo de otimização de cuco M	0,96423	0,69756	0,28892	1,95071	0,64504	0,34034	0,21362	1,19900	0,67153	0,34273	0,45422	1,46848	74,204
FAm	algoritmo de vaga-lumes M	0,62430	0,50653	0,18102	1,31185	0,55408	0,42299	0,64360	1,62067	0,21167	0,28416	1,00000	1,49583	71,024
BA	algoritmo do morcego	0,42290	0,95047	1,00000	2,37337	0,17768	0,17477	0,33595	0,68840	0,15329	0,07158	0,46287	0,68774	59,650
ABC	colônia artificial de abelhas	0,81573	0,48767	0,22588	1,52928	0,58850	0,21455	0,17249	0,97554	0,47444	0,26681	0,35941	1,10066	57,237
BFO	otimização de forrageamento bacteriano	0,70129	0,46155	0,11627	1,27911	0,41251	0,26623	0,26695	0,94569	0,42336	0,34491	0,50973	1,27800	55,516
FSS	busca por cardume de peixes	0,48850	0,37769	0,11006	0,97625	0,07806	0,05013	0,08423	0,21242	0,00000	0,01084	0,18998	0,20082	20,109
PSO	otimização de enxame de partículas	0,21339	0,12224	0,05966	0,39529	0,15345	0,10486	0,28099	0,53930	0,08028	0,02385	0,00000	0,10413	14,232
RND	aleatório	0,17559	0,14524	0,07011	0,39094	0,08623	0,04810	0,06094	0,19527	0,00000	0,00000	0,08904	0,08904	8,142
GWO	otimizador lobo-cinzento	0,00000	0,00000	0,00000	0,00000	0,00000	0,00000	0,00000	0,00000	0,18977	0,04119	0,01802	0,24898	1,000

A análise dos resultados do teste revela que o BFO está posicionado no meio da tabela de classificação, com uma pontuação geral um pouco acima de 55 entre os algoritmos participantes. Os resultados não são impressionantes, mas também não são ruins. Especificamente, obteve-se um bom desempenho na função Rastrigin com 10 variáveis, porém os resultados foram visivelmente piores com 50 e 1000 variáveis. Além disso, o algoritmo não se saiu bem na função Forest. Surpreendentemente, o comportamento foi relativamente bom na função Megacity discreta, mesmo sem mecanismos específicos para lidar com esse tipo de função no algoritmo. Também observou-se boa escalabilidade em comparação com outros algoritmos (teste com parâmetros de 1000 Megacity).

O BFO é um campo científico com amplas possibilidades. Existem vários aspectos do forrageamento bacteriano e animal que podem ser modelados para melhorar o desempenho da otimização. Para o algoritmo BFO, a adaptação automática dos parâmetros de controle pode ser especialmente importante, dada a quantidade de parâmetros envolvidos, e pode aprimorar o desempenho, o que justifica a realização de experimentos adicionais.

O BFO possui várias vantagens, como baixa sensibilidade aos valores iniciais das coordenadas durante a inicialização e escolha dos parâmetros, confiabilidade, lógica simples, facilidade de implementação, possibilidade de paralelização e capacidade de busca global. Portanto, o algoritmo BFO é amplamente utilizado para resolver uma variedade de problemas de otimização. No entanto, o BFO também apresenta algumas desvantagens, incluindo convergência lenta, limitação para superar ótimos locais em certos casos e um comprimento de passo fixo. O BFO é uma meta-heurística, o que significa que é uma estrutura conceitual que pode ser utilizada para desenvolver modificações em um algoritmo. A versão do BFO apresentada aqui é apenas uma das muitas possibilidades e deve ser vista como um ponto de partida para experimentação, não como a palavra final sobre o assunto.

Histograma apresentando os resultados do teste de algoritmo, Figura 3.

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

Conclusões sobre as características do algoritmo BFO:

Prós:
1. Rápido.
2. Lógica simples.
3. Embora lento, ele continua a convergir ao longo das iterações.

Contras:
1. Convergência lenta.
2. Nenhum método é fornecido para escapar dos extremos locais.