Execução de teste

Algoritmos de otimização evolucionários

James McCaffrey

Baixar o código de exemplo

Um algoritmo de otimização evolucionário é uma implementação de um meta-heurístico modelado com base no comportamento da evolução biológica. Esses algoritmos podem ser usados para encontrar soluções aproximadas para problemas de minimização numérica difíceis ou impossíveis. Talvez esteja interessado em algoritmos de otimização evolucionários por três motivos. Primeiro, saber como codificar esses algoritmos pode ser uma adição prática ao seu conjunto de habilidades de desenvolvedor, gerente e testador. Segundo, algumas das técnicas usadas, como seleção de torneio, podem ser reutilizadas em outros algoritmos e cenários de codificação. E terceiro, muitos engenheiros simplesmente acham esses algoritmos interessantes por si mesmos.

Um algoritmo de otimização evolucionário é, essencialmente, um tipo de algoritmo genético no qual os cromossomas virtuais são feitos de valores reais em vez de alguma forma de representação de bits. A melhor maneira de perceber onde quero chegar é dar uma olhada na Figura 1 e na Figura 2.

Figura 1 Função de Schwefel

Figure 2 Demonstração da otimização evolucionária

O gráfico na Figura 1 mostra a função de Schwefel, um problema de minimização numérica de parâmetro de comparação padrão. A função de Schwefel é definida como:

f(x,y) = (-x * sin(sqrt(abs(x)))) + (-y * sin(sqrt(abs(y))))

A função tem um valor mínimo de 837,9658 quando x = y = 420,9687. Na Figura 1 esse valor mínimo está no canto mais à esquerda do gráfico. A função foi deliberadamente projetada para dificultar a resolução pelos algoritmos de otimização por causa dos numerosos valores mínimos locais falsos.

A captura de tela da Figura 2 mostra a saída de um aplicativo de console em C#. Depois de exibir algumas mensagens informativas, o programa define oito parâmetros e, em seguida, usa um algoritmo evolucionário para procurar a solução ideal. Nesse exemplo, o algoritmo encontrou uma melhor solução de (420,9688, 420,9687), que é extremamente próxima de, mas não muito igual à solução ideal de (420,9687, 420,9687).

Os algoritmos de otimização evolucionários modelam uma solução como um cromossoma em um indivíduo. Em pseudocódigo de alto nível, o algoritmo implementado na Figura 2 é:

initialize a population of random solutions
determine best solution in population
loop
  select two parents from population
  make two children from the parents
  place children into population
  make and place an immigrant into population
  check if a new best solution exists
end loop
return best solution found

Nas seções a seguir, apresentarei todo o código que gerou a captura de tela na Figura 2. É possível acessar o código em archive.msdn.microsoft.com/mag201206TestRun. Este artigo pressupõe que você tenha habilidades de programação intermediárias ou avançadas e pelo menos um entendimento muito básico de algoritmos genéticos. Codifiquei o programa de demonstração usando C#, mas você deve ser capaz de facilmente refatorar o código em outras linguagens como Visual Basic .NET ou IronPython.

Estrutura do programa

A estrutura geral do programa é mostrada na Figura 3. Usei Visual Studio 2010 para criar um novo projeto de aplicativo de console em C# chamado EvolutionaryOptimization. Na janela Gerenciador de Soluções, renomeei Program.cs para EvolutionaryOptimizationProgram.cs, que automaticamente renomeou a classe Program. Também excluí todas as instruções using geradas pelo modelo desnecessárias.

Figura 3 Estrutura geral do programa EvolutionaryOptimization

using System;
namespace EvolutionaryOptimization
{
  class EvolutionaryOptimizationProgram
  {
    static void Main(string[] args)
    {
      try
      {
        int popSize = 100;
        int numGenes = 2;
        double minGene = -500.0; double maxGene = 500.0;
        double mutateRate = 1.0 / numGenes;
        double precision = 0.0001;
        double tau = 0.40;
        int maxGeneration = 8000;
        Evolver ev = new Evolver(popSize, numGenes, 
          minGene, maxGene, mutateRate,
          precision, tau, maxGeneration);
        double[] best = ev.Evolve();
        Console.WriteLine("\nBest solution found:");
        for (int i = 0; i < best.Length; ++i)
          Console.Write(best[i].ToString("F4") + " ");
        double fitness = Problem.Fitness(best);
        Console.WriteLine("\nFitness of best solution = " 
          + fitness.ToString("F4"));
      }
      catch (Exception ex)
      {
        Console.WriteLine("Fatal: " + ex.Message);
      }
    }
  }
  public class Evolver
  {
    // Member fields
    public Evolver(int popSize, int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision, 
      double tau, int maxGeneration) { ... }
    public double[] Evolve() { ... }
    private Individual[] Select(int n) { ... }
    private void ShuffleIndexes() { ... }
    private Individual[] Reproduce(Individual parent1, 
      Individual parent2) { ... }
    private void Accept(Individual child1, 
      Individual child2) { ... }
    private void Immigrate() { ... }
  }
  public class Individual : IComparable<Individual>
  {
    // Member fields
    public Individual(int numGenes, 
      double minGene, double maxGene,
      double mutateRate, double precision) { ... }
    public void Mutate() { ... }
    public int CompareTo(Individual other) { ... }
  }
  public class Problem
  {
    public static double Fitness(double[] chromosome) { ... }
  }
} // NS

Além da classe Program principal, a demonstração EvolutionaryOptimization tem três classes definidas pelo programa. A classe Evolver contém a maior parte da lógica do algoritmo. A classe Individual modela uma possível solução para o problema de minimização. A classe Problem define a função a ser minimizada, a função de Schwefel nesse caso. Um estrutura de projeto alternativa seria colocar a classe Individual dentro da classe Evolver.

A classe Individual

A definição da classe Individual começa:

public class Individual : IComparable<Individual>
{
  public double[] chromosome;
  public double fitness;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  static Random rnd = new Random(0);
...

A classe é herdada da interface IComparable para que as matrizes de objetos Individual possam ser automaticamente classificadas por sua aptidão. A classe tem oito membros de dados. A matriz de cromossomas representa uma solução possível para o problema em questão. Observe que cromossoma é uma matriz de double, em vez de uma matriz com alguma forma de representação de bits, normalmente usada por algoritmos genéticos. Os algoritmos de otimização evolucionários são algumas vezes chamados de algoritmos genéticos de valores reais.

O campo fitness é uma medida de qualidade da solução de cromossoma. Para minimizar problemas, valores menores de fitness são melhores do que valores maiores. Para simplificar, chromosome e fitness são declarados com escopo público para que fiquem visíveis para a lógica na classe Evolver. Um gene é um valor na matriz de cromossomas e o campo numGenes contém o número de valores reais em uma solução possível. Para a função de Schwefel, esse valor será definido como 2. Com muitos problemas de otimização numérica, valores mínimo e máximo de cada gene podem ser especificados e esses valores são armazenados em minGene e maxGene. Se esses valores não são conhecidos, minGene e maxGene podem ser definidos como double.MinValue e double.MaxValue. Explicarei os campos mutateRate e precision quando apresentar o código que os utiliza.

A definição da classe Individual continua com o construtor de classe:

public Individual(int numGenes, double minGene, double maxGene,
  double mutateRate, double precision)
{
  this.numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.chromosome = new double[numGenes];
  for (int i = 0; i < this.chromosome.Length; ++i)
    this.chromosome[i] = (maxGene - minGene) 
    * rnd.NextDouble() + minGene;
  this.fitness = Problem.Fitness(chromosome);
}

O construtor aloca memória para a matriz de cromossomas e atribui valores aleatórios no intervalo (minGene, maxGene) a cada célula de gene. Observe que o valor do campo fitness é definido chamando o método Fitness definido externamente. Como alternativa, você pode passar para o construtor uma referência ao método Fitness via um Delegate. O método Mutate é definido da seguinte forma:

public void Mutate()
{
  double hi = precision * maxGene;
  double lo = -hi;
  for (int i = 0; i < chromosome.Length; ++i) {
    if (rnd.NextDouble() < mutateRate)
      chromosome[i] += (hi - lo) * rnd.NextDouble() + lo;
  }
}

A operação de mutação percorre a matriz de cromossomas, alterando aleatoriamente genes selecionados para valores aleatórios no intervalo (lo, hi). O intervalo de valores a ser atribuído é determinado pelos valores dos membros precision e maxGene. No exemplo da Figura 2, precision é definido como 0,0001 e maxGene é definido como 500. O mais alto valor possível para uma mutação de gene é 0,0001 * 500 = 0,05, o que significa que se um gene sofrer mutação, seu novo valor será o valor antigo mais ou menos um valor aleatório entre -0,05 e +0,05. Observe que o valor precision corresponde ao número de decimais na solução; essa é uma heurística razoável para ser usada no valor precision. O valor da taxa de mutação controla quantos genes no cromossoma serão modificados. Uma heurística para o valor do campo mutateRate é usar 1,0 / numGenes, de modo que na média um gene no cromossoma sofrerá mutação toda vez que Mutate for chamado.

A definição da classe Individual conclui com o método CompareTo:

...
  public int CompareTo(Individual other)
  {
    if (this.fitness < other.fitness) return -1;
    else if (this.fitness > other.fitness) return 1;
    else return 0;
  }
}

O método CompareTo define a ordem de classificação padrão dos objetos Individual, nesse caso do fitness menor (melhor) para o fitness maior.

A classe Problem

A classe Problem encapsula o problema em questão do algoritmo evolucionário:

public class Problem
{
  public static double Fitness(double[] chromosome)
  {
    double result = 0.0;
    for (int i = 0; i < chromosome.Length; ++i)
      result += (-1.0 * chromosome[i]) *
        Math.Sin(Math.Sqrt(Math.Abs(chromosome[i])));
    return result;
  }
}

Como uma matriz de cromossomas representa uma solução possível, ela é passada como um parâmetro de entrada para o método Fitness. Com problemas de minimização arbitrários, a função de destino a ser minimizada é normalmente chamada de função de custo. No contexto de algoritmos evolucionários e genéticos, no entanto, a função é normalmente chamada de função de aptidão. Observe que a terminologia é um pouco estranha, pois valores mais baixos de aptidão são melhores que valores mais altos. Nesse exemplo, a função de aptidão é completamente autossuficiente. Em muitos problemas de otimização, a função de aptidão precisa de parâmetros de entrada adicionais, como uma matriz de dados ou uma referência a um arquivo de dados externo.

A classe Evolver

A definição da classe Evolver começa:

public class Evolver
{
  private int popSize;
  private Individual[] population;
  private int numGenes;
  private double minGene;
  private double maxGene;
  private double mutateRate;
  private double precision;
  private double tau;
  private int[] indexes;
  private int maxGeneration;
  private static Random rnd = null;
...

O membro popSize contém o número de indivíduos na população. Valores maiores de popSize tendem a aumentar a precisão do algoritmo às custas da velocidade. Em geral, algoritmos evolucionários são muito mais rápidos do que algoritmos genéticos comuns, pois algoritmos evolucionários trabalham com números reais e não incorrem na sobrecarga de converter e manipular representações de bits. O coração da classe Evolver é uma matriz de objetos Individual chamada população. Os membros tau e indexes são usados pelo método Selection, como será visto daqui a pouco.

A definição da classe Evolver continua com a definição do construtor, mostrada na Figura 4

Figura 4 Construtor da classe Evolver

public Evolver(int popSize, int numGenes, double minGene, double maxGene,
  double mutateRate, double precision, double tau, int maxGeneration)
{
  this.popSize = popSize;
  this.population = new Individual[popSize];
  for (int i = 0; i < population.Length; ++i)
    population[i] = new Individual(numGenes, minGene, maxGene,
      mutateRate, precision);
  this.numGenes = numGenes;
  this.minGene = minGene;
  this.maxGene = maxGene;
  this.mutateRate = mutateRate;
  this.precision = precision;
  this.tau = tau;
  this.indexes = new int[popSize];
  for (int i = 0; i < indexes.Length; ++i)
    this.indexes[i] = i;
  this.maxGeneration = maxGeneration;
  rnd = new Random(0);
}

O construtor aloca memória para a matriz população e então usa o construtor Individual para preencher a matriz com indivíduos que têm valores de genes aleatórios. A matriz chamada indexes é usada pelo método Select, que seleciona dois pais. Explicarei indexes mais tarde, mas observe que o construtor aloca uma célula por indivíduo e sequencialmente atribui inteiros de 0 a popSize-1.

O método Evolve, listado na Figura 5, é surpreendentemente curto.

Figura 5 O método Evolve

public double[] Evolve()
{
  double bestFitness = this.population[0].fitness;
  double[] bestChomosome = new double[numGenes];
  population[0].chromosome.CopyTo(bestChomosome, 0);
  int gen = 0;
  while (gen < maxGeneration)  {
    Individual[] parents = Select(2);
    Individual[] children = Reproduce(parents[0], parents[1]);
    Accept(children[0], children[1]);
    Immigrate();
    for (int i = popSize - 3; i < popSize; ++i)  {
      if (population[i].fitness < bestFitness)  {
        bestFitness = population[i].fitness;
        population[i].chromosome.CopyTo(bestChomosome, 0);
      }
    }
    ++gen;
  }
  return bestChomosome;
}

O método Evolve retorna a melhor solução encontrada como uma matriz de tipo double. Como alternativa, você poderia retornar um objeto Individual em que o cromossoma contém a melhor solução encontrada. O método Evolve começa inicializando a melhor aptidão e o melhor cromossoma nos primeiros da população. O método é iterado exatamente maxGenerations vezes, usando gen (generation) como um contador de loop. Uma das várias alternativas é parar quando nenhum aperfeiçoamento ocorreu depois de um número de iterações. O método Select retorna dois bons, mas não necessariamente os melhores, indivíduos da população. Esses dois pais são passados para Reproduce, que cria e retorna dois filhos. O método Accept coloca os dois filhos na população, substituindo dois indivíduos existentes. O método Immigrate gera um novo indivíduo aleatório e o coloca na população. A nova população é então verificada para ver se qualquer dos três novos indivíduos na população é uma nova melhor solução.

O método Select é definido como:

private Individual[] Select(int n)
{
  int tournSize = (int)(tau * popSize);
  if (tournSize < n) tournSize = n;
  Individual[] candidates = new Individual[tournSize];
  ShuffleIndexes();
  for (int i = 0; i < tournSize; ++i)
    candidates[i] = population[indexes[i]];
  Array.Sort(candidates);
  Individual[] results = new Individual[n];
  for (int i = 0; i < n; ++i)
    results[i] = candidates[i];
  return results;
}

O método aceita o número de bons indivíduos para selecionar e os retorna em uma matriz do tipo Individual. Para minimizar a quantidade de código, omiti a verificação de erro normal, como verificar que o número de indivíduos solicitado é menor que o tamanho da população. O método Select usa uma técnica chamada seleção de torneio. Um subconjunto de indivíduos candidatos aleatórios é gerado e os n melhores são retornados. O número de candidatos é computado na variável tournSize, que é uma fração, tau, do tamanho da população total. Valores maiores de tau aumenta a probabilidade de que os dois melhores indivíduos sejam selecionados.

Lembre-se de que a classe Evolver tem uma matriz de membros chamada indexes com valores 0..popSize-1. O método auxiliar ShuffleIndexes rearranja os valores na matriz indexes em ordem aleatória. Os n maiores desses indexes aleatórios são usados para selecionar candidatos da população. O método Array.Sort então classifica os indivíduos candidatos da menor aptidão (melhor) à maior. Os n maiores indivíduos dos candidatos classificados são retornados. Há muitos diferentes algoritmos de seleção evolucionários. Uma vantagem da seleção de torneio comparada à maioria de outras técnicas é que a pressão da seleção pode ser ajustada modificando o parâmetro tau.

O método auxiliar ShuffleIndexes usa o algoritmo de ordem aleatória Fisher-Yates padrão:

private void ShuffleIndexes()
{
  for (int i = 0; i < this.indexes.Length; ++i) {
    int r = rnd.Next(i, indexes.Length);
    int tmp = indexes[r];
    indexes[r] = indexes[i];
    indexes[i] = tmp;
  }
}

O método Reproduce está listado na Figura 6. O método começa com a geração de um ponto de crossover aleatório. A indexação é um pouco complicada, mas child1 é criado da parte esquerda de parent1 e da parte direita de parent2. Child2 é criado da parte esquerda de parent2 e da parte direita de parent1. A ideia é ilustrada na Figura 7, onde há dois pais com cinco genes e o ponto de crossover é 2. Uma alternativa de projeto comum é usar vários pontos de crossover. Depois que os objetos filho Individual são criados eles sofrem mutação e sua nova aptidão é computada.

Figura 6 O método Reproduce

private Individual[] Reproduce(Individual parent1, Individual parent2)
{
  int cross = rnd.Next(0, numGenes - 1);
  Individual child1 = new Individual(numGenes, minGene, maxGene,
    mutateRate, precision);
  Individual child2 = new Individual(numGenes, minGene, maxGene,
     mutateRate, precision);
  for (int i = 0; i <= cross; ++i)
    child1.chromosome[i] = parent1.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child2.chromosome[i] = parent1.chromosome[i];
  for (int i = 0; i <= cross; ++i)
    child2.chromosome[i] = parent2.chromosome[i];
  for (int i = cross + 1; i < numGenes; ++i)
    child1.chromosome[i] = parent2.chromosome[i];
  child1.Mutate(); child2.Mutate();
  child1.fitness = Problem.Fitness(child1.chromosome);
  child2.fitness = Problem.Fitness(child2.chromosome);
  Individual[] result = new Individual[2];
  result[0] = child1; result[1] = child2;
  return result;
}

Figura 7 O mecanismo de crossover

O método Accept coloca os dois indivíduos filho, criados por Reproduce, na população:

private void Accept(Individual child1, Individual child2)
{
  Array.Sort(this.population);
  population[popSize - 1] = child1;
  population[popSize - 2] = child2;
}

A matriz população é classificada por aptidão, que coloca os dois piores indivíduos nas duas últimas células da matriz, onde são então substituídos pelos filhos. Há muitas abordagens alternativas para escolher os dois indivíduos que morrem. Uma possibilidade é usar uma técnica chamada seleção por roleta para selecionar por probabilidade os dois indivíduos a serem substituídos, onde os piores indivíduos têm uma mais alta probabilidade de serem substituídos.

O método Immigrate gera um novo indivíduo aleatório e o coloca na população logo acima do local dos dois filhos que acabaram de ser gerados (a imigração ajuda a impedir que algoritmos evolucionários fiquem presos em soluções mínimas locais; alternativas de projeto incluem criar mais de um imigrante e colocá-lo em um local aleatório na população):

private void Immigrate()
{
  Individual immigrant =
    new Individual(numGenes, minGene, maxGene, mutateRate, precision);
  population[popSize - 3] = immigrant;
}

Ponto inicial de experimentação

Neste artigo, a otimização evolucionária é usada para estimar o valor mínimo de uma equação matemática. Embora os algoritmos de otimização evolucionários possam ser usados nessa maneira, com mais frequência eles são usados para encontrar os valores de um conjunto de parâmetros numéricos em um problema de otimização maior para o qual não há nenhum algoritmo determinístico efetivo. Por exemplo, ao usar uma rede neural para classificar dados existentes a fim de se fazer previsões sobre dados futuros, o principal desafio é determinar um conjunto de pesos e tendências de neurônios. Usar o algoritmo de otimização evolucionário é uma abordagem para estimar os valores de peso e tendência ideais. Na maioria dos casos, os algoritmos de otimização evolucionários não são bem adequados para uso em problemas de otimização combinatórios não numéricos como o problema do caixeiro viajante, em que o objetivo é encontrar a combinação de cidades com a mais curta distância total.

Algoritmos evolucionários, como algoritmos genéticos puros, são meta-heurísticos. Isso significa que eles são uma estrutura geral e um conjunto de diretrizes conceituais que podem ser usados para criar um algoritmo específico para resolver um problema específico. Assim, o exemplo apresentado neste artigo pode ser visto mais como um ponto inicial de experimentação e criação de código de otimização evolucionário do que uma base de código estático e fixo.

Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico de engenheiros de software que trabalham no campus de Washington da Microsoft Redmond. Ele trabalhou em vários produtos da Microsoft, como o Internet Explorer e o MSN Busca. Ele é autor de “.NET Test Automation Recipes” (Apress, 2006) e pode ser contatado pelo email jammc@microsoft.com.

Agradecemos ao seguinte especialista técnico da Microsoft pela revisão deste artigo: Anne Loomis Thompson