Execução de Teste

Otimização de algoritmo Firefly

James McCaffrey

Baixar o código de exemplo(VB)

No aprendizado de máquina, um algoritmo de otimização numérica geralmente é usado para localizar um conjunto de valores de variáveis, normalmente chamado de pesos, que minimizar algumas medidas de erro. Por exemplo, a classificação de regressão logística usa uma equação matemática na qual, se houver n variáveis de previsão, há n + 1 valores de peso que devem ser determinados. O processo de determinação dos valores dos pesos é chamado de treinamento do modelo. A ideia é usar uma coleção de dados de treinamento que tem valores de saída corretos conhecidos. Um algoritmo de otimização é usado para localizar os valores dos pesos que minimizam o erro, que é a diferença entre os valores de saída computados e os valores de saída corretos.

Há muitos algoritmos de otimização diferentes. Este artigo explica uma técnica relativamente nova (publicada pela primeira vez em 2009) denominada otimização de algoritmo firefly (Firefly Algorithm - FA). A otimização FA modela livremente o comportamento de um enxame de vagalumes.

A melhor maneira de ter uma noção do que é a otimização FA e ver onde quero chegar com esse artigo é examinar o programa de demonstração na Figura 1. O objetivo do programa de demonstração é usar a otimização FA para encontrar o valor mínimo da função Michalewicz com cinco variáveis de entrada. A função Michalewicz é uma função de parâmetro de comparação padrão usada para avaliar a eficácia dos algoritmos de otimização numérica. Com cinco valores de entrada, a função tem um valor mínimo de z = -4.6877 localizado em x = (2.2029 1.5707, 1.2850, 1.9231, 1.7205).

Figura 1 A otimização de algoritmo Firefly em ação

A função Michalewicz é difícil para a maioria dos algoritmos de otimização porque ela tem vários valores mínimos locais e várias áreas simples (onde todos os valores de z são quase iguais). Não é possível visualizar facilmente a função Michalewicz com cinco valores de entrada, mas você pode ter uma ideia das características da função examinando um gráfico da função para dois valores de entrada, mostrado na Figura 2. A definição da função em termos matemáticos é mostrada na parte inferior da figura.

Figura 2 A função Michalewicz de duas variáveis

O programa de demonstração define o número de vagalumes para 40. Cada vagalume tem uma posição virtual que representa uma possível solução para o problema de minimização. Mais vagalumes aumentam as chances de encontrar a solução ideal verdadeira às custas do desempenho. A otimização FA normalmente usa de 15 a 40 vagalumes.

A demonstração define a dimensão do problema como 5 porque há cinco valores de entrada. O FA é um processo iterativo e requer um valor de contador de loop máximo. Uma variável de contador de loop na otimização de aprendizado de máquina é geralmente nomeada época e os conjuntos de demonstração definem o valor máximo para 1.000 iterações. O número máximo de iterações variam de acordo com o problema, mas 1.000 é um valor inicial razoável. O FA tem um elemento de aleatoriedade e a demonstração define o valor de semente para o gerador de números aleatórios para um valor arbitrário de 0.

Na demonstração executada na Figura 1, o melhor (menor) erro associado à melhor posição encontrada até o momento foi exibido a cada 100 épocas. Após o término do algoritmo, a melhor posição encontrada para qualquer vagalume era x = (2.2033, 1.5711, 1.2793, 1.1134, 2.2216). Essa solução é aproximada, mas não muito igual à solução ideal de x = (2.2029 1.5707, 1.2850, 1.9231, 1.7205). O valor da função Michalewicz na solução encontrada pelo FA era -4.45, que é quase o verdadeiro valor mínimo de -4.69. O erro da solução FA é 0.0561.

Este artigo pressupõe que você tem pelo menos habilidades de programação intermediárias, mas não pressupõe que conheça nada sobre otimização numérica ou o algoritmo firefly. Codifiquei o algoritmo de demonstração usando a linguagem C#, mas você não deve ter muita dificuldade para refatorar o código em outra linguagem, como JavaScript ou Python.

O código de demonstração completo, com algumas pequenas edições para economizar espaço, é apresentado neste artigo. A demonstração também está disponível no download do código que acompanha este artigo. O código de demonstração tem a verificação de erros normais removida para manter as ideias principais tão claras quanto possível e o tamanho do código pequeno.

Estrutura geral do programa

A estrutura geral do programa é apresentada na Figura 3. Para criar o programa de demonstração, iniciei o Visual Studio e criei um novo aplicativo do console C# denominado FireflyAlgorithm. A demonstração não tem dependências significativas do Microsoft .NET Framework, portanto, funcionará em qualquer versão relativamente recente do Visual Studio.

Figura 3 A estrutura do programa de demonstração firefly

using System;
namespace FireflyAlgorithm
{
  class FireflyProgram
  {
    static void Main(string[] args)
    {
      Console.WriteLine("Begin firefly demo");
      // Code here
      Console.WriteLine("End firefly demo");
      Console.ReadLine();
    }
    static void ShowVector(double[] v, int dec, bool nl)
    {
      for (int i = 0; i < v.Length; ++i)
        Console.Write(v[i].ToString("F" + dec) + " ");
      if (nl == true)
        Console.WriteLine("");
    }
    static double[] Solve(int numFireflies, int dim,
      int seed, int maxEpochs) { . . }
    static double Distance(double[] posA,
      double[] posB) { . . }
    static double Michalewicz(double[] xValues) { . . }
    static double Error(double[] xValues) { . . }
  } // Program
  public class Firefly : IComparable<Firefly>
  {
    // Defined here
  }
}

Depois que o código de modelo carregado no editor do Visual Studio, na janela do Gerenciador de Soluções, renomeei o arquivo Program.cs para o mais descritivo FireflyProgram.cs e o Visual Studio automaticamente renomeou a classe Program para mim. Na parte superior do código-fonte, excluí tudo que não era necessário usando instruções, deixando apenas a referência ao sistema.

Codifiquei a demonstração usando uma técnica de método estático principalmente em vez de usar uma abordagem de programação completa orientada a objeto. A demonstração tem toda a lógica de controle em Main. O método Main começa exibindo a finalidade da demonstração:

Console.WriteLine("Goal is to solve the Michalewicz benchmark function");
Console.WriteLine("The function has a known minimum value of -4.687658");
Console.WriteLine("x = 2.2029 1.5707 1.2850 1.9231 1.7205");

Em seguida, os parâmetros necessários para FA são definidos:

int numFireflies = 40;
int dim = 5;
int maxEpochs = 1000;
int seed = 0;

Os valores de parâmetro são exibidos com estas instruções:

Console.WriteLine("Setting numFireflies = " + numFireflies);
Console.WriteLine("Setting problem dim = " + dim);
Console.WriteLine("Setting maxEpochs = " + maxEpochs);
Console.WriteLine("Setting initialization seed = " + seed);

O algoritmo firefly é invocado desta forma:

Console.WriteLine("Starting firefly algorithm");
double[] bestPosition = Solve(numFireflies, dim, seed, maxEpochs);
Console.WriteLine("Finished");

O método Main conclui exibindo os resultados do FA:

Console.WriteLine("Best solution found: ");
Console.Write("x = ");
ShowVector(bestPosition, 4, true);
double z = Michalewicz(bestPosition);
Console.Write("Value of function at best position = ");
Console.WriteLine(z.ToString("F6"));
double error = Error(bestPosition);
Console.Write("Error at best position = ");
Console.WriteLine(error.ToString("F4"));

O algoritmo firefly é realmente mais um meta-heurístico do que um algoritmo prescritivo. Com isso quero dizer que o FA é um conjunto de diretrizes de design que podem ser adaptadas para diferentes tipos de problemas de otimização.

Noções básicas sobre o algoritmo Firefly

O algoritmo firefly apresentado neste artigo baseia-se no trabalho de pesquisa de 2009, "Firefly Algorithms for Multimodal Otimization", por Xin-She Yang. O processo do algoritmo firefly é ilustrado no gráfico da Figura 4. O gráfico representa um problema de minimização fictício simplificado no qual há apenas dois valores de entrada, X e Y, e o valor mínimo global está em X = 0 e Y = 0. Há três vagalumes. O vagalume[0] está em (2, 1) e, portanto, é o mais próximo para a solução correta. O vagalume[1] está em (-4, -4). O vagalume[2] está em (-8, 8) e é o mais distante da solução.

Figura 4 O algoritmo Firefly

Os vagalumes reais são insetos voadores que brilham usando bioluminescência, presumivelmente para atrair parceiros. Cada vagalume pode brilhar com uma intensidade diferente. No FA, os vagalumes que são melhores, ou seja, têm um erro menor, têm maior intensidade. Na Figura 4, o vagalume[0] tem a intensidade mais alta, o vagalume[1] tem intensidade intermediária e o vagalume[2] tem intensidade fraca.

A ideia básica do FA é que um vagalume sejam atraídos a outros vagalumes que tem maior intensidade e que a capacidade de atração (a distância movida em direção a um vagalume mais intenso) é mais forte se a distância entre os dois vagalumes for menor. Então, na Figura 4, o vagalume[0] tem a mais alta intensidade e não será movido. O vagalume[1] e o vagalume[2] serão atraídos para e se moverão em direção ao vagalume[0]. Como o vagalume[1] está mais próximo do que o vagalume[2] em relação ao vagalume[0], o vagalume[1] se moverá uma distância maior que o vagalume[2].

Expressa em pseudocódigo de alto nível, o algoritmo firefly é apresentado na Figura 5. À primeira vista, o algoritmo parece muito simples. No entanto, é bastante sutil, como você verá quando a implementação do código for apresentada.

O primeiro grande problema é definir a intensidade de um vagalume. Como o FA é um meta-heurístico, você está livre para definir a intensidade da maneira que desejar, desde uma maior intensidade esteja associada uma melhor solução/posição. A próxima questão importante é definir atração para que os vagalumes mais próximos se movam em direção a um alvo mais intenso que os vagalumes mais distantes se moverão.

Figure 5 Firefly Algorithm

initialize n fireflies to random positions
loop maxEpochs times
  for i := 0 to n-1
    for j := 0 to n-1
      if intensity(i) < intensity(j)
        compute attractiveness
        move firefly(i) toward firefly(j)
        update firefly(i) intensity
      end for
    end for
  sort fireflies
end loop
return best position found

Implementando o Algoritmo Firefly

A definição do método Solve começa como:

static double[] Solve(int numFireflies, int dim, int seed, int maxEpochs)
{
  Random rnd = new Random(seed);
  double minX = 0.0;
  double maxX = 3.2;
  double B0 = 1.0;
  double g = 1.0;
  double a = 0.20;
  int displayInterval = maxEpochs / 10;
...

As variáveis locais minX e maxX estabelecem limites para a posição de cada vagalume. Os valores usados aqui, 0.0 e 3.2 (aproximadamente Pi) são específicos para a função Michalewicz. Para otimização com dados normalizados de aprendizagem de máquina, os valores de -10.0 e +10.0 são comuns.

As variáveis locais B0 (base beta), g (gama) e a (alfa) controlam a capacidade de atração de um vagalume em relação ao outro. Os valores usados (1.0, 1.0 e 0.20) foram recomendados pelo artigo de pesquisa de origem. A variável local displayInterval controla a frequência de exibir uma mensagem de progresso.

Em seguida, um enxame de vagalumes vazio é criado:

double bestError = double.MaxValue;
double[] bestPosition = new double[dim]; // Best ever
Firefly[] swarm = new Firefly[numFireflies]; // All null

Um objeto Firefly é definido pelo programa e encapsula uma posição, um erro associado e a intensidade correspondente. Inicialmente, todos os vagalumes são objetos nulos. A definição da classe Firefly será apresentada na próxima seção deste artigo. Em seguida, o enxame é instanciado e colocado em posições aleatórias. Para cada vagalume, o construtor Firefly é chamado:

for (int i = 0; i < numFireflies; ++i)
{
  swarm[i] = new Firefly(dim);
  for (int k = 0; k < dim; ++k) // Random position
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
...

O construtor define implicitamente a posição de (0.0, 0.0, 0.0, 0.0, 0.0) e o erro associado e a intensidade como valores fictícios de 0.0. Em seguida, cada componente da matriz de posição é definido como um valor aleatório entre minX e maxX (0.0 e 3.2). Em seguida, o erro e a intensidade do vagalume atual são calculados:

swarm[i].error = Error(swarm[i].position);
  swarm[i].intensity = 1 / (swarm[i].error + 1);
...

A função de erro será apresentada em breve. Aqui, a intensidade do vagalume é definida para ser o inverso do erro para que os valores de erro pequeno terão alta intensidade e valores de erro grande terá baixa intensidade. O 1 no denominador impede a divisão por zero quando o erro é zero. A inicialização termina verificando o vagalume recém-criado para ver se ele tem a melhor posição encontrada:

...
  if (swarm[i].error < bestError)
  {
    bestError = swarm[i].error;
    for (int k = 0; k < dim; ++k)
      bestPosition[k] = swarm[i].position[k];
  }
} // For each firefly

O loop de processamento principal começa com estas instruções:

int epoch = 0;
while (epoch < maxEpochs)
{
  if (epoch % displayInterval == 0 && epoch < maxEpochs)
  {
    string sEpoch = epoch.ToString().PadLeft(6);
    Console.Write("epoch = " + sEpoch);
    Console.WriteLine(" error = " + bestError.ToString("F14"));
  }
...

Uma alternativa para um número fixo de iterações será interrompido quando o valor bestError cai abaixo de um valor de limite pequeno (0,00001 é comum). Cada vagalume é comparado com todos os outros vagalumes usando loops aninhados:

for (int i = 0; i < numFireflies; ++i) // Each firefly
{
  for (int j = 0; j < numFireflies; ++j) // Others
  {
    if (swarm[i].intensity < swarm[j].intensity)
    {
      // Move firefly(i) toward firefly(j)
...

Observe que, como cada índice de loop inicia em 0, cada par de vagalumes é comparado duas vezes em cada iteração do while loop. Para mover um vagalume em direção ao outro vagalume com maior intensidade, primeiro a atratividade deve ser calculada:

double r = Distance(swarm[i].position, swarm[j].position);
double beta = B0 * Math.Exp(-g * r * r);
...

A variável beta define a atração e será usado em alguns instantes para mover o vagalume[i]. Seu valor depende do quadrado da distância entre os vagalumes[i] e [j], que é calculado usando o método auxiliar Distance. O método Distance retorna a distância Euclidiana entre duas posições. Por exemplo, se o vagalume[i] em duas dimensões estiver em (3.0, 4.0) e vagalume[j] estiver em (5.0, 9.0), a distância entre eles é sqrt((5-3)^2 + (9-4)^2) = sqrt (4 + 25) = sqrt(29) = 5,4. Observe que beta usa distância ao quadrado, que é o inverso da operação de raiz quadrada, para que o cálculo do beta pode ser simplificado, às custas de flexibilidade, se você decidiu usar uma medida diferente de distância.

O movimento real é realizado com estas instruções:

for (int k = 0; k < dim; ++k)
{
  swarm[i].position[k] += beta *
    (swarm[j].position[k] - swarm[i].position[k]);
  swarm[i].position[k] += a * (rnd.NextDouble() - 0.5);
  if (swarm[i].position[k] < minX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
  if (swarm[i].position[k] > maxX)
    swarm[i].position[k] = (maxX - minX) * rnd.NextDouble() + minX;
}
...

O componente enésimo da posição do vagalume[i] é movido uma fração de beta da distância entre o vagalume[i] e o vagalume[j] na direção do vagalume[j]. Em seguida, um termo aleatório pequeno é adicionado à cada componente da enésima posição. Isso ajuda a impedir que o algoritmo fique preso em soluções não ideais. Cada componente de posição é verificado para ver se ele saiu do intervalo e, nesse caso, um valor no intervalo aleatório é atribuído.

O código de movimentação de loops aninhados termina com a atualização do erro e a intensidade do vagalume recém-movido:

swarm[i].error = Error(swarm[i].position);
      swarm[i].intensity = 1 / (swarm[i].error + 1);
    } // If firefly(i) < firefly(j)
  } // j
} // i each firefly
...

O método Solve conclui com estas instruções:

...
   Array.Sort(swarm); // low error to high
    if (swarm[0].error < bestError)
    {
      bestError = swarm[0].error;
      for (int k = 0; k < dim; ++k)
        bestPosition[k] = swarm[0].position[k];
    }
    ++epoch;
  } // While
  return bestPosition;
} // Solve

Depois de cada par de vagalume ser comparado e os vagalumes menos intensos de moveram em direção aos vagalumes mais intensos, a matriz de objetos Firefly é classificada a partir do erro mais baixo ao erro mais alto para que seja melhor de forma que o melhor está no enxame[0]. Esse objeto é verificado para ver se uma nova solução melhor foi encontrada. A classificação da matriz de objetos Firefly também tem o efeito importante de alterar seu local dentro da matriz para que os objetos sejam processados em uma ordem diferente cada vez que passarmos o while loop.

Os métodos auxiliares

O método Solve chama métodos auxiliares Distance e Error, que por sua vez chama o método auxiliar Michalewicz. Método auxiliar Distance é definido como:

static double Distance(double[] posA, double[] posB)
{
  double ssd = 0.0; // sum squared diffrences
  for (int i = 0; i < posA.Length; ++i)
    ssd += (posA[i] - posB[i]) * (posA[i] - posB[i]);
  return Math.Sqrt(ssd);
}

O método auxiliar Distance é definido como:

static double Michalewicz(double[] xValues)
{
  double result = 0.0;
  for (int i = 0; i < xValues.Length; ++i) {
    double a = Math.Sin(xValues[i]);
    double b = Math.Sin(((i+1) * xValues[i] * xValues[i]) / Math.PI);
    double c = Math.Pow(b, 20);
    result += a * c;
  }
  return -1.0 * result;
}

Se você se referir à definição da função Michalewicz na parte inferior da Figura 2, você verá que a função tem um expoente de 2m. No entanto, o valor de m geralmente é definido como 10, portanto, no código, é usado um valor constante de 20. O método auxiliar Error é definido como:

static double Error(double[] xValues)
{
  int dim = xValues.Length;
  double trueMin = 0.0;
  if (dim == 2)
    trueMin = -1.8013; // Approx.
  else if (dim == 5)
    trueMin = -4.687658; // Approx.
  double calculated = Michalewicz(xValues);
  return (trueMin - calculated) * (trueMin - calculated);
}

O método de erro retorna apenas o produto da diferença de quadrados entre o valor mínimo conhecido da função Michalewicz e o valor calculado. Essa função fictícia pode ser calculada muito rapidamente, mas na máquina a maioria dos cenários de aprendizado, a função de erro pode ser muito demorada.

A classe Firefly

A definição de classe Firefly começa com:

public class Firefly : IComparable<Firefly>
{
  public double[] position;
  public double error;
  public double intensity;
...

A classe herda da interface IComparable para que as matrizes e listas que contém o objeto possam ser classificadas automaticamente. Os campos de dados são definidos com escopo público para simplificar. Porque não há um mapeamento individual entre erros e intensidade, esses dois campos podem ser descartados. O construtor da classe é:

public Firefly(int dim)
{
  this.position = new double[dim];
  this.error = 0.0;
  this.intensity = 0.0;
}

Existem diversas alternativas de design que você pode considerar. Aqui o construtor simplesmente aloca espaço para a matriz de posição. O único outro método público é CompareTo:

public int CompareTo(Firefly other)
  {
    if (this.error < other.error) return -1;
    else if (this.error > other.error) return +1;
    else return 0;
  }
} // Class Firefly

O método CompareTo ordena os objetos Firefly de baixo erro para alto. Uma alternativa equivalente é a ordem de intensidade alta para baixa.

Alguns comentários

A implementação do algoritmo firefly apresentado neste artigo baseia-se no na pesquisa de 2009. O algoritmo original gerou diversas variações. O artigo de pesquisa apresenta alguns dados que sugerem que FA é superior a otimização por nuvem de partículas, pelo menos em alguns problemas de otimização de benchmark fictício. Sou um pouco cético. No entanto, na minha opinião, um cenário no qual FA é muito útil é quando a função objetiva a ser minimizada tem várias soluções. Embora seja não totalmente óbvio, na verdade, o FA automaticamente se organiza em sub-enxames que podem encontrar várias soluções simultaneamente.

Dr. James McCaffrey trabalha para a Microsoft Research em Redmond, Wash. Ele trabalhou em vários produtos da Microsoft, incluindo Internet Explorer e Bing. O Dr. McCaffrey pode ser contatado em jammc@microsoft.com.

Agradecemos aos seguintes especialistas técnicos da Microsoft pela revisão deste artigo: Todd Bello, Marciano Moreno Diaz Covarrubias e Alisson Sol