Algoritmos de otimização populacionais: algoritmo de vaga-lumes

Conteúdo

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

1. Introdução

A natureza sempre foi, é e continuará sendo uma fonte de inspiração para a criação de muitos algoritmos metaheurísticos. Ela encontrou soluções para problemas sem orientação, baseando-se na experiência individual. A seleção natural e a sobrevivência dos mais aptos foram as principais motivações para a criação dos primeiros algoritmos metaheurísticos. Na natureza, os animais se comunicam de diversas maneiras. Os vaga-lumes, por exemplo, utilizam sua habilidade de emitir luz intermitente para se comunicarem. Existem aproximadamente 2 000 espécies de vaga-lumes, cada uma com seus próprios padrões específicos de emissão de luz. Eles geralmente emitem um flash breve com um padrão específico, e a luz e sua intensidade são resultado de processos bioquímicos conhecidos como bioluminescência. Acredita-se que a principal função desses flashes seja atrair indivíduos do sexo oposto e potenciais presas. Alguns vaga-lumes tropicais podem sincronizar suas emissões de luz, demonstrando assim um exemplo de auto-organização biológica. A intensidade da luz, como função da distância de sua fonte, obedece à lei do inverso do quadrado, fazendo com que a luz emitida por um vaga-lume provoque reações nos vaga-lumes ao seu redor, dentro do alcance visual do flash.

Existem duas variações de algoritmos de otimização populacional inspirados no comportamento dos vaga-lumes: o algoritmo de vaga-lumes (Firefly Algorithm) e a otimização de enxame de pirilampos (Glowworm Swarm Optimization, GSO). A principal diferença entre vaga-lumes e pirilampos reside no fato de que os últimos não possuem asas. Neste artigo, abordaremos o primeiro tipo de algoritmo de otimização.

2. Descrição do algoritmo

O algoritmo dos vagalumes (algoritmo F) foi proposto na Universidade de Cambridge (Reino Unido) em 2007 por Yang (X-Sh. Yang) e atraiu imediatamente a atenção de pesquisadores na área de otimização. O algoritmo de vaga-lume faz parte de uma família de algoritmos de inteligência de enxame, que recentemente têm demonstrado resultados impressionantes na resolução de problemas de otimização. Especificamente, o algoritmo de vaga-lumes é usado para resolver problemas de otimização contínua e discreta.

O algoritmo de vaga-lumes possui três regras baseadas nas características de cintilação dos vaga-lumes reais. São elas:

1. Todos os vaga-lumes se moverão em direção aos mais atraentes e brilhantes.
2. O grau de atração de um vaga-lume é proporcional ao seu brilho, que diminui à medida que a distância de outro vaga-lume aumenta devido à absorção da luz pelo ar. Portanto, entre dois vaga-lumes piscando, o menos brilhante se moverá em direção ao mais brilhante. Se não houver um vaga-lume mais brilhante ou atraente que um específico, ele se moverá aleatoriamente.
3. O brilho ou intensidade luminosa do vaga-lume é determinado pelo valor da função objetivo do problema.

No início do algoritmo, todos os vaga-lumes são distribuídos aleatoriamente por todo o espaço de busca. Em seguida, o algoritmo determina as divisões ideais com base em duas fases:

1. Mudança na intensidade da luz - o brilho do vaga-lume em sua posição atual é refletido no seu valor de adaptação, movendo-se em direção a um vaga-lume atraente.
2. O vaga-lume altera sua posição, observando a intensidade da luz dos vaga-lumes vizinhos.

Agora é possível se aprofundar nas complexidades da otimização de vaga-lumes com mais detalhes. A essência do algoritmo é claramente representada na Figura 1.

Figura 1. Vaga-lumes no espaço de busca. Diminuição da visibilidade com o aumento da distância.

A ideia principal por trás do princípio de busca é a diminuição não linear na visibilidade conforme a distância entre os vagalumes aumenta. Sem essa relação não linear, cada vaga-lume se moveria de forma determinística em direção a uma fonte de luz mais brilhante. No entanto, como podemos ver na Figura 1, o vaga-lume não escolhe o seu parente mais brilhante, pois sua luz é menos perceptível devido à absorção de luz pelo ambiente; em vez disso, ele escolhe um vaga-lume menos brilhante, mas o mais brilhante em seu entorno. Essa característica explica a boa capacidade do algoritmo de se dividir em enxames menores, e isso ocorre naturalmente apenas devido à função não linear de absorção de luz em função da distância. Na Figura 2 abaixo, podemos ver a função de visibilidade versus distância para o algoritmo com diferentes valores do coeficiente de absorção gama do ambiente, que é um dos parâmetros do algoritmo.

Figura 2. A função de transparência do meio em relação à distância f(x), onde o coeficiente de transparência gama é igual a 1,0, 0,2, 0,05, 0,01, respectivamente.

Quando o gama tende ao infinito, o ambiente se torna opaco, e quando o gama é igual a zero, o ambiente é completamente transparente, e cada vaga-lume vê o outro a qualquer distância no espaço de busca. O que acontece se gama = 0,0? Resposta: todos os vaga-lumes voarão em direção ao parente mais brilhante, eles convergirão para algum ponto não ideal e o algoritmo não convergirá, ficando preso em um dos extremos locais. O que acontece se o ambiente estiver completamente opaco? Isso significa que os vagalumes não verão ninguém mais atraente do que eles mesmos, mas de acordo com o conceito proposto pelo autor do algoritmo, não vendo ninguém melhor do que eles mesmos, o vaga-lume se moverá aleatoriamente. O algoritmo irá degenerar em uma busca aleatória. Em nossa tabela de classificação de algoritmos, o algoritmo de busca aleatória ocupa o último lugar.  

Vamos nos aprofundar na análise do algoritmo e considerar as fórmulas que descrevem os movimentos dos vaga-lumes. A função visibilidade versus distância fundamenta o cálculo do chamado índice de atratividade:

attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

Onde:
attractiveness - atratividade
gamma - fator de opacidade do meio
distance - distância euclidiana entre vaga-lumes
gamma - intensidade luminosa do k-ésimo vaga-lume

Pela fórmula, é possível perceber que a função de atratividade dependerá diretamente da dimensão do problema e dos limites do valor da distância. Por isso, o autor do algoritmo recomenda ajustar o coeficiente de transparência de acordo com o problema de otimização específico. Acredito que seja inconveniente e trabalhoso ajustar parâmetros sem saber de antemão como o algoritmo se comportará. Por isso, considero necessário normalizar os valores de distância no intervalo de 0 a 20. Para isso, aplicaremos a função Scale(), que utilizamos várias vezes em outros algoritmos. A transformação da distância antes do cálculo da atratividade ficará assim:

distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);

Onde:

distância euclidiana máxima entre um par de vaga-lumes entre todos eles

Neste caso, a atratividade dos vaga-lumes não dependerá da dimensão do problema, eliminando a necessidade de ajustar o coeficiente gama para um problema de otimização específico. A função de atratividade determina que tipo de escolha de parceiro cada vaga-lume fará. Essa escolha é estritamente determinística. A influência da atratividade entre os vaga-lumes determina o coeficiente beta (o segundo parâmetro do algoritmo). Mas como as capacidades de busca do algoritmo são garantidas se a escolha dos vaga-lumes já é determinada antecipadamente em cada iteração correspondente? Para isso, é introduzido um componente vetorial aleatório e o terceiro parâmetro do algoritmo, alfa. As relações comportamentais complexas entre os vaga-lumes ficariam assim:

fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];

Onde:
fireflies [i].c [c] - c-ésima coordenada do i-ésimo vaga-lume
beta - coeficiente de influência da atração dos vaga-lumes uns aos outros
alfa - coeficiente que afeta o componente aleatório do movimento dos vaga-lumes, que dá desvios em relação ao alvo de movimento
r - número aleatório no intervalo [-1,0;1,0]
v[c] - componente vetorial que caracteriza a distância entre os pontos extremos do intervalo de busca pela c-ésima coordenada
Xj - coordenada correspondente da vaga-lume no par, em direção ao qual haverá movimento
Xi - coordenada correspondente do vaga-lume para o qual o movimento é calculado

Agora vamos descrever o código do algoritmo. O código não é muito complexo, é bastante simples. Vamos examinar com mais detalhes.

Os vaga-lumes, maravilhosas criações da natureza, serão descritos por uma estrutura simples chamada S_Firefly, que possui apenas dois componentes com [] - coordenadas e f - o valor da luminosidade do vaga-lume, que também é o valor da função de adaptação. Como para cada vaga-lume há apenas um indivíduo na iteração correspondente, com o qual ele se moverá formando um par, não corremos o risco de sobrescrever as coordenadas ao calcular o próximo movimento, já que introduzimos uma estrutura especial para isso, que consideraremos a seguir.

//——————————————————————————————————————————————————————————————————————————————
struct S_Firefly
{
  double c  []; //coordinates
  double f;     //the value of the fitness function
};
//——————————————————————————————————————————————————————————————————————————————

A estrutura S_Attractiveness tem como objetivo armazenar o valor de atratividade e o número correspondente do vaga-lume como um par. Cada vaga-lume não se move em direção às coordenadas do mais atraente, mas sim em direção às coordenadas onde o objeto de sua atração já se deslocou. Há uma certa discrepância nisso em relação à versão do algoritmo descrita pelo autor, mas é assim que ele funciona melhor.

//——————————————————————————————————————————————————————————————————————————————
struct S_Attractiveness
{
  double a; //attractiveness
  int    i; //index of the most attractive firefly
};
//——————————————————————————————————————————————————————————————————————————————

Descreveremos o algoritmo de vaga-lumes usando a classe C_AO_FA. Há três métodos públicos: um deles é o Init(), para a inicialização inicial, e outros dois métodos públicos, Flight() e Luminosity(), são necessários para serem chamados a cada iteração. Há também métodos auxiliares privados e membros para armazenar constantes de parâmetro.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_FA
{
  //----------------------------------------------------------------------------
  public: S_Firefly fireflies []; //fireflies
  public: double    rangeMax  []; //maximum search range
  public: double    rangeMin  []; //minimum 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    sizeP,    //swarm size
                     const double alphaP,   //alpha, randomness in motion
                     const double betaP,    //beta, effect of attractiveness
                     const double gammaP);  //gamma, transparency of the environment

  public: void Flight ();
  public: void Luminosity ();

  //----------------------------------------------------------------------------
  private: S_Attractiveness att [];
  private: int    swarmSize;
  private: int    params;
  private: double maxDist;
  private: double v [];

  private: double alpha;      //randomness in motion
  private: double beta;       //effect of attractiveness
  private: double gamma;      //transparency of the environment
  private: bool   luminosity;

  private: double SeInDiSp  (double In, double inMin, double inMax, double step);
  private: double RNDfromCI (double min, double max);
  protected: double Scale   (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

O método público Init() é usado para inicialização. Os parâmetros são ajustes para o algoritmo e devem ser chamados antes de iniciar cada otimização. Este método aloca memória para arrays e redefine o valor de luminosidade global e de cada vaga-lume individualmente.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Init (const int    paramsP, //number of opt. parameters
                    const int    sizeP,   //swarm size
                    const double alphaP,  //alpha, randomness in motion
                    const double betaP,   //beta, effect of attractiveness
                    const double gammaP)  //gamma, transparency of the environment
{
  fB = -DBL_MAX;

  params    = paramsP;
  swarmSize = sizeP;
  alpha     = alphaP;
  beta      = betaP;
  gamma     = gammaP;

  ArrayResize (rangeMax,  params);
  ArrayResize (rangeMin,  params);
  ArrayResize (rangeStep, params);
  ArrayResize (v,         params);
  ArrayResize (att,       swarmSize);

  luminosity = false;

  ArrayResize (fireflies, swarmSize);

  for (int i = 0; i < swarmSize; i++)
  {
    ArrayResize (fireflies [i].c,  params);
    fireflies [i].f = -DBL_MAX;
  }

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

Vamos examinar o primeiro método público chamado a cada iteração, Flight(). Neste único método, toda a lógica principal do algoritmo está concentrada. Portanto, é necessário analisá-lo com mais detalhes, dividindo-o em partes. A variável de luminosidade atua como um sinalizador para determinar se o algoritmo está sendo executado na primeira iteração ou nas subsequentes. Se o sinalizador não estiver definido, os vaga-lumes devem ser distribuídos aleatoriamente no espaço de coordenadas de acordo com uma distribuição uniforme. Juntamente com essa ação, estabelecemos o vetor de deslocamento para cada coordenada e calculamos imediatamente a distância euclidiana máxima possível entre os vaga-lumes. Isso é necessário para normalizar as distâncias entre os vaga-lumes, evitando a dependência do coeficiente de transparência do ambiente em relação à dimensão do problema, conforme discutido anteriormente. Após essas operações, ativamos o sinalizador de luminosidade.

if (!luminosity)
{
  fB = -DBL_MAX;

  //--------------------------------------------------------------------------
  double summCoordinates = 0.0;
  for (int c = 0; c < params; c++)
  {
    v [c] = rangeMax [c] - rangeMin [c];
    summCoordinates += pow (v [c], 2.0);
  }
  maxDist = pow (summCoordinates, 0.5);

  //--------------------------------------------------------------------------
  for (int s = 0; s < swarmSize; s++)
  {
    for (int k = 0; k < params; k++)
    {
      fireflies [s].c  [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      fireflies [s].c  [k] = SeInDiSp (fireflies [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
    }
  }

  luminosity = true;
}

A partir da segunda iteração e nas subsequentes, após os vaga-lumes terem sido distribuídos aleatoriamente na primeira iteração e começarem a brilhar (ou seja, a função de adaptação foi calculada para eles), é possível calcular o grau de atratividade de cada vaga-lume. Para isso, precisamos calcular a distância euclidiana entre todos os possíveis pares de vaga-lumes, somando os quadrados das diferenças de coordenadas e extraindo a raiz quadrada do resultado. A distância calculada será usada na fórmula de cálculo da atratividade. Dessa forma, obtemos para cada vaga-lume o único par possível. Ao mesmo tempo, determinamos a luminosidade máxima entre todos os vaga-lumes, o que será necessário para identificar o vaga-lume mais brilhante, que não encontrará um par e vagará solitariamente pelo espaço. Mas tudo bem, na próxima iteração, talvez ele tenha mais sorte.

//measure the distance between all------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  att [i].a = -DBL_MAX;

  for (int k = 0; k < swarmSize; k++)
  {
    if (i == k) continue;

    summCoordinates = 0.0;
    for (int c = 0; c < params; c++) summCoordinates += pow (fireflies [i].c [c] - fireflies [k].c [c], 2.0);

    distance = pow (summCoordinates, 0.5);
    distance = Scale (distance, 0.0, maxDist, 0.0, 20.0, false);
    attractiveness = fireflies [k].f / (1.0 + gamma * distance * distance);

    if (attractiveness > att [i].a)
    {
      att [i].a = attractiveness;
      att [i].i = k;
    }

    if (fireflies [i].f > maxF) maxF = fireflies [i].f;
  }
}

Esta parte do código do método Flight() é responsável pelo voo dos vaga-lumes. Para o vaga-lume mais infeliz, cuja luminosidade é maior do que a de todos os outros, o cálculo é feito de maneira um pouco diferente. Adicionamos o vetor de deslocamento à sua posição atual por meio do coeficiente alfa multiplicado por um número aleatório no intervalo [-1,0; 1,0]. Teoricamente, no algoritmo, isso funciona como um estudo adicional da melhor solução, com a expectativa de que ela seja ainda melhor; no entanto, como veremos adiante, essa abordagem se mostrará inútil. Nesta etapa, estamos considerando a versão clássica do algoritmo.

Para todos os outros vaga-lumes, para os quais um par já foi encontrado, o cálculo do movimento consistirá em deslocar-se em direção ao ponto do par correspondente, adicionando um componente aleatório (que mencionamos anteriormente).

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      fireflies [i].c [c] = fireflies [i].c [c] + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); 
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r  = RNDfromCI (-1.0, 1.0);
      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];
      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Um método público simples é chamado a cada iteração. Aqui, atualizaremos a melhor solução encontrada.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_FA::Luminosity ()
{
  for (int i = 0; i < swarmSize; i++)
  {
    if (fireflies [i].f > fB)
    {
      fB = fireflies [i].f;
      ArrayCopy (cB, fireflies [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Agora, vamos passar à discussão dos testes. Vamos analisar a saída de resultados do algoritmo aplicado às funções de teste:

2022.12.16 13:39:00.102    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:39:05.930    Test_AO_FA (EURUSD,M1)    1 Skin's; Func runs 10000 result: 4.901742065217812
2022.12.16 13:39:05.930    Test_AO_FA (EURUSD,M1)    Score: 0.99603
2022.12.16 13:39:13.579    Test_AO_FA (EURUSD,M1)    20 Skin's; Func runs 10000 result: 3.2208359936020665
2022.12.16 13:39:13.579    Test_AO_FA (EURUSD,M1)    Score: 0.59468
2022.12.16 13:39:53.607    Test_AO_FA (EURUSD,M1)    500 Skin's; Func runs 10000 result: 0.98491319842575
2022.12.16 13:39:53.607    Test_AO_FA (EURUSD,M1)    Score: 0.06082
2022.12.16 13:39:53.607    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:39:59.313    Test_AO_FA (EURUSD,M1)    1 Forest's; Func runs 10000 result: 1.578196881663454
2022.12.16 13:39:59.313    Test_AO_FA (EURUSD,M1)    Score: 0.89271
2022.12.16 13:40:07.274    Test_AO_FA (EURUSD,M1)    20 Forest's; Func runs 10000 result: 0.3101994341994826
2022.12.16 13:40:07.274    Test_AO_FA (EURUSD,M1)    Score: 0.17546
2022.12.16 13:40:49.159    Test_AO_FA (EURUSD,M1)    500 Forest's; Func runs 10000 result: 0.06829102669136165
2022.12.16 13:40:49.159    Test_AO_FA (EURUSD,M1)    Score: 0.03863
2022.12.16 13:40:49.159    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:40:54.895    Test_AO_FA (EURUSD,M1)    1 Megacity's; Func runs 10000 result: 8.2
2022.12.16 13:40:54.895    Test_AO_FA (EURUSD,M1)    Score: 0.68333
2022.12.16 13:41:02.777    Test_AO_FA (EURUSD,M1)    20 Megacity's; Func runs 10000 result: 1.5900000000000003
2022.12.16 13:41:02.777    Test_AO_FA (EURUSD,M1)    Score: 0.13250
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    500 Megacity's; Func runs 10000 result: 0.2892
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    Score: 0.02410
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    =============================
2022.12.16 13:41:43.901    Test_AO_FA (EURUSD,M1)    All score for C_AO_FA: 0.39980648892951776

Os resultados, para dizer o mínimo, não impressionaram. O algoritmo é apenas um pouco melhor do que algoritmos como PSO, FSS e GWO em testes individuais; no entanto, no indicador geral de classificação, ele ocupa a penúltima posição, sendo superior apenas ao algoritmo de busca aleatória. Tendo isso em mente, surgiu a ideia de rever o cálculo dos indicadores de avaliação nos testes. Nos próximos artigos, adotaremos um esquema de cálculo de classificação mais conveniente, e neste artigo incluiremos um histograma dos resultados finais, que mostrará claramente a relação de desempenho entre os algoritmos individuais.

O algoritmo clássico de vaga-lume é simples de implementar. No entanto, pesquisas mostram que ele converge lentamente e facilmente cai na armadilha de extremos locais em problemas multimodais. Além disso, ele não possui coeficientes que dependem parametricamente da iteração atual. Portanto, modificar o algoritmo padrão de vaga-lume para melhorar seu desempenho foi um dos objetivos desta pesquisa.

A própria ideia do algoritmo fascina com sua originalidade, e seria uma pena deixar tudo como está e não tentar melhorar suas características. Por isso, tentei modificar o algoritmo, substituindo o componente aleatório pelo voo de Levy. Vale ressaltar que, para nem todos os algoritmos, o voo de Levy pode melhorar a capacidade de busca. Depois de analisar o algoritmo de otimização de cuco, fiz tentativas de aprimorar outros algoritmos usando esse método, mas isso não trouxe os resultados esperados. Aparentemente, isso deve estar de alguma forma alinhado com a estratégia de busca interna do algoritmo, complementando-o. Neste caso específico, a aplicação do Voo de Levy teve um efeito impressionante, e as capacidades do algoritmo aumentaram drasticamente. Discutiremos isso na parte do artigo sobre os resultados dos testes.

Aqui está, de fato, a parte do código onde a alteração foi feita. Primeiramente, na versão clássica, o vaga-lume com a melhor luminosidade se move em uma direção aleatória a partir de sua posição atual; então, nosso melhor vaga-lume se moverá a partir da melhor posição global, tentando melhorar não apenas sua posição atual, mas a solução como um todo. Adicionamos um número aleatório da distribuição de voo de Levy (distribuição com caudas pesadas) às coordenadas da melhor solução, com o mesmo coeficiente alfa, levando em consideração o vetor de deslocamento. Isso realmente possibilitou melhorar as coordenadas da solução global, refinando a vizinhança.

Como podemos ver, o comportamento dos demais vaga-lumes agora segue as mesmas regras clássicas, porém ajustadas ao componente aleatório do voo de Levy. Essa é toda a modificação que foi feita no algoritmo.

//flight--------------------------------------------------------------------
for (int i = 0; i < swarmSize; i++)
{
  if (fireflies [i].f >= maxF)
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      fireflies [i].c [c] = cB [c] + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
  else
  {
    for (int c = 0; c < params; c++)
    {
      r1 = RNDfromCI (0.0, 1.0);
      r1 = r1 > 0.5 ? 1.0 : -1.0;
      r2 = RNDfromCI (1.0, 20.0);

      Xi = fireflies [i].c [c];
      Xj = fireflies [att [i].i].c [c];

      fireflies [i].c [c] = Xj + beta * (Xi - Xj) + alpha * r1 * pow (r2, -2.0) * v [c];
      fireflies [i].c [c] = SeInDiSp (fireflies [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}

Gráfico da função Voo de Lévy na Figura 3. Como o expoente na fórmula de uma função pode afetar o comportamento do algoritmo? De acordo com minha pesquisa, à medida que o grau aumenta, o número de saltos longos (caudas pesadas) diminui em relação aos curtos, enquanto a capacidade do algoritmo de refinar as coordenadas nas proximidades da melhor solução melhora, mas devido ao fato de haver poucos saltos longos, a probabilidade de ficar preso em extremos locais aumenta. Este efeito será mais pronunciado ao estudar funções discretas, enquanto não será tão pronunciado em funções contínuas. Pelo contrário, com a diminuição do expoente, o número de saltos longos aumenta, as capacidades de busca do algoritmo melhoram, mas a precisão da convergência piora, portanto, é necessário um equilíbrio entre precisão e busca e, além disso, pode ser diferente dependendo do problema de otimização.

Figura 3. Função Voo de Levy, expoentes 0,5...3,0. 

Então, vamos aos resultados da versão modificada do algoritmo na bancada de testes. Abaixo está uma impressão onde você pode ver o quanto o desempenho da versão original melhorou em comparação com a clássica.

2022.12.16 13:07:15.925    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:07:21.544    Test_AO_FAm (EURUSD,M1)    1 Skin's; Func runs 10000 result: 4.854437214435259
2022.12.16 13:07:21.544    Test_AO_FAm (EURUSD,M1)    Score: 0.98473
2022.12.16 13:07:29.518    Test_AO_FAm (EURUSD,M1)    20 Skin's; Func runs 10000 result: 4.588539001298423
2022.12.16 13:07:29.518    Test_AO_FAm (EURUSD,M1)    Score: 0.92124
2022.12.16 13:08:12.587    Test_AO_FAm (EURUSD,M1)    500 Skin's; Func runs 10000 result: 1.981278990090829
2022.12.16 13:08:12.587    Test_AO_FAm (EURUSD,M1)    Score: 0.29872
2022.12.16 13:08:12.587    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:08:18.336    Test_AO_FAm (EURUSD,M1)    1 Forest's; Func runs 10000 result: 1.7665409595127233
2022.12.16 13:08:18.336    Test_AO_FAm (EURUSD,M1)    Score: 0.99924
2022.12.16 13:08:26.432    Test_AO_FAm (EURUSD,M1)    20 Forest's; Func runs 10000 result: 0.6261364994589462
2022.12.16 13:08:26.432    Test_AO_FAm (EURUSD,M1)    Score: 0.35417
2022.12.16 13:09:10.587    Test_AO_FAm (EURUSD,M1)    500 Forest's; Func runs 10000 result: 0.14269062630878
2022.12.16 13:09:10.587    Test_AO_FAm (EURUSD,M1)    Score: 0.08071
2022.12.16 13:09:10.587    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:09:16.393    Test_AO_FAm (EURUSD,M1)    1 Megacity's; Func runs 10000 result: 10.0
2022.12.16 13:09:16.393    Test_AO_FAm (EURUSD,M1)    Score: 0.83333
2022.12.16 13:09:24.373    Test_AO_FAm (EURUSD,M1)    20 Megacity's; Func runs 10000 result: 1.7899999999999998
2022.12.16 13:09:24.373    Test_AO_FAm (EURUSD,M1)    Score: 0.14917
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    500 Megacity's; Func runs 10000 result: 0.5076
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    Score: 0.04230
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    =============================
2022.12.16 13:10:09.298    Test_AO_FAm (EURUSD,M1)    All score for C_AO_FAm: 0.5181804234713119

Como você pode ver, o algoritmo modificado não apenas apresentou melhores resultados, mas também conseguiu ocupar uma posição de liderança na tabela de classificação. Vamos dar uma olhada mais de perto nos resultados na próxima seção. Abaixo está uma animação da versão modificada do algoritmo na bancada de testes.

  Fam na função de teste Skin.

  FAm na função de teste Forest.

  FAm na função de teste Megacity.

3. Resultado dos testes

O algoritmo de vaga-lume modificado (FAm) apresentou um desempenho excelente em todos os testes. Em geral, os resultados dependem das configurações do algoritmo e, com algumas delas, foi alcançada uma convergência de 100% em todas as três funções com duas variáveis. A alta escalabilidade do algoritmo garante liderança nos testes com 40 e 1000 parâmetros. Os parâmetros beta e gama exercem uma forte influência, permitindo alcançar alta convergência e resistência ao ficar preso em extremos locais. Os resultados variam bastante, o que, em geral, pode ser considerado uma desvantagem do algoritmo. Mantendo todas as outras condições iguais, o fato é que, até o momento, o algoritmo é o mais eficiente entre os analisados anteriormente e pode ser recomendado para uso em uma ampla gama de tarefas, incluindo problemas de aprendizado de máquina e inteligência artificial, especialmente no treinamento de redes neurais.

A seguir, é apresentada a tabela de classificação final, na qual o algoritmo de vaga-lume modificado ocupa a posição de líder. O algoritmo clássico, apesar de sua originalidade, infelizmente não obteve bons resultados, e a escolha dos parâmetros de ajuste também não foi bem-sucedida.

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

A partir deste artigo, publicarei um histograma em que o melhor algoritmo no momento do teste terá 100 pontos condicionais e o pior - 1 ponto. Parece-me que isso é o mais conveniente para a percepção visual, onde é possível ver claramente a escala dos resultados finais dos algoritmos na tabela de classificação. Agora é possível observar o quanto o algoritmo aleatório fica atrás do líder.

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

Vale lembrar que os algoritmos meta-heurísticos são métodos aproximados para resolver problemas de otimização, que utilizam a propriedade da aleatoriedade com uma suposição justificada em seu mecanismo de busca e tentam melhorar a qualidade das soluções existentes por meio de iterações a partir de um conjunto gerado aleatoriamente de soluções admissíveis, explorando e utilizando o espaço de soluções. Embora esses algoritmos não garantam a resultados ótimos, eles são testados para fornecer uma solução razoável e aceitável. Além disso, possuem a vantagem de que o comportamento do problema não os afeta significativamente, e é isso que os torna úteis em várias tarefas. A disponibilidade de vários algoritmos possibilita a escolha do mais adequado para resolver um problema, dependendo de seu comportamento.

Desde o surgimento dos algoritmos evolutivos, muitas pesquisas têm sido realizadas sobre algoritmos heurísticos. A implementação de novos algoritmos tem sido uma das principais áreas de estudo. Atualmente, existem mais de 40 algoritmos meta-heurísticos, a maioria dos quais é criada por meio da simulação de cenários da natureza.

Os prós e contras mencionados se referem à versão modificada do algoritmo de vaga-lumes (FAm).

Prós:

• Implementação simples. Fácil de modificar.
• Alta escalabilidade.
• Alta convergência (varia com as configurações do algoritmo).
• Capacidade de agrupar a região do espaço de busca em grupos separados em torno de extremos locais.

Contras:

• Forte influência das configurações nos resultados da otimização.
• É importante considerar que, com algumas configurações, o algoritmo tende a ficar preso em extremos locais.

Para cada artigo, eu anexo um arquivo que contém versões atualizadas dos códigos dos algoritmos para todos os artigos anteriores. Cada novo artigo representa a experiência pessoal acumulada do autor, e as conclusões e julgamentos são baseados nos experimentos realizados em uma bancada de testes especial desenvolvido para essa finalidade.