Sofia IA

Inteligência artificial para jogos

Algoritmos Genéticos

with 6 comments

Algoritmo genético é um tipo de algoritmo da categoria dos algoritmos de busca estocástica. Ele baseia-se na genética para realizar pesquisa. É muito útil quando você não tem nem idéia de onde a solução possa estar, mas é capaz de avaliar a qualidade de uma determinada resposta, seja ela qual for.

Darei como exemplo um problema que meus alunos estão tentando resolver: encontrar a placa de um veículo numa foto. A única coisa que nós sabemos de antemão é que a placa está lá. Não sabemos o tamanho que ela aparecerá e nem em que posição da foto.

Entretanto, não é muito complicado montar um algoritmo que diga se uma determinada região da imagem é uma placa ou não, desde que ele receba de entrada o “retângulo” correspodente a essa região. Poderíamos testar se esse retângulo é quase totalmente branco, com algum percentual de preto no meio (para as letras).

Notamos aí duas características:

  1. Temos uma série infinita de retângulos possíveis numa imagem, de tamanhos diferentes;
  2. Temos uma forma de dar uma nota num desses retângulo.

Todo algoritmo genético se baseia em quatro fases, aplicada sobre uma população (no caso, um conjunto desses retângulos). Ao final das quatro fases, temos uma nova população.

  • Avaliação (Fitness): Dada uma população, damos um escore para cada um deles. O de melhor escore estará mais próximo da possível solução;
  • Seleção (Selection): Escolhemos alguns indivíduos dessa população. Geralmente, indivíduos de melhor score tem mais chance de serem escolhidos, como seria na natureza.
  • Cruzamento (Crossover): Cruzamos alguns desses indivíduos, combinando seus genes. Outros, deixamos intocados para a próxima geração (como se tivessem “sobrevivido”). O ideal é que as taxas de cruzamento sejam altas, em torno de 70%;
  • Mutação (Mutation): Alguns dos indivíduos sofrem mutações aleatórias. As taxas de mutação recomendadas giram em torno de 1%.

Genoma em bits

Antes de iniciar as fases e o trabalho sobre os indivíduos, precisamos representar de alguma forma as suas características. Como programadores, logo nos vem a cabeça as variáveis.

Entretanto, assim como na genética, poderíamos guardar as características de um desses retângulos através de um genoma. No caso do corpo humano, esse genoma é o DNA. No caso da informática, podemos usar um std::bitset, um std::vector<bool> ou qualquer outra estrutura para representar o genoma (até mesmo uma árvore). Hoje, me concentrei em montar uma estrutura adequada para representar um genoma na forma de bits.

Ok, vamos supor que nossa imagem tenha no máximo 1024×1024 pixels. É um bom tamanho. Os retângulos podem iniciar em qualquer ponto da imagem, então poderíamos organizar nosso genoma com 40 bits: 10 para o x, 10 para y, 10 para a altura e 10 para largura.

Não é difícil perceber que é necessário uma classe conveniente para manipular esses bits. Ao olhar a STL me deparei com 2 opções:

  1. A classe BitSet, que representa um mapa de bits de tamanho fixo;
  2. A classe vector<bool> que representa um mapa de bits de tamanho variável.

A vantagem do BitSet sobre o vector é o fato dele ocupar um pouco menos espaço e de ter métodos mais específicos mais convenientes para a manipulação de bits. A do vector é o fato de cada bit poder ser acessado em tempo linear, próximo de 0, além de ser considerado um container padrão.

Como a IA é famosa por ser pesada, e os algoritmos genéticos não são exceção a essa regra, optei pela classe vector, que tem maior performance. Montei então uma classe chamada BitGenome, que permitiria que um programador facilmente lesse e gravasse tipos inteiros na estrutura:

A classe também tem métodos para fazer a mutação e a cruza, baseado em algoritmos fornecidos externamente. Explicarei esses algoritmos na sequência. Ela está situada no namespace sofia::genetic::bit, omitirei aqui as declarações de namespace para melhorar a formatação para o blog:

//BitGenome.h
class BitGenome
{
   private:
      std::vector<bool> genes;

   public:
      explicit BitGenome(int _size);

      void setUnsigned(int pos, unsigned long number, int bits);
      void setSigned(int pos, long number, int bits);

      unsigned long getUnsigned(int pos, int bits) const;
      long getSigned(int pos, int bits) const;

      void set(int bit, bool value);
      bool get(int bit) const;
      bool operator[](int bit) const;

      void mutate(BitMutationMethod& mutationMethod);
      std::pair<BitGenome, BitGenome> crossover(const BitGenome& other,
         BitCrossoverMethod& crossoverFunctor) const;

      int size() const;
};

//BitGenome.cpp
BitGenome::BitGenome(int _size)
: genes(_size) {}

void BitGenome::setUnsigned(int pos, unsigned long number, int bits)
{
   unsigned long max = ((2 << bits - 1) - 1);

   if (number > max)
   {
       std::stringstream ss;
       ss << "Invalid number " << number << "! ";
       ss << "Maximum value for " << bits << " bits is " << max << "!";
       throw std::out_of_range(ss.str());
   }

   for (int i = pos + bits - 1; i >= pos; i--)
   {
      genes[i] = (number & 1) == 1;
      number = number >> 1;
   }
}

void BitGenome::setSigned(int pos, long number, int bits)
{
   if (number < 0)
   {
      setUnsigned(pos + 1, -number, bits - 1);\
      genes&#91;pos&#93; = true;
      return;
   }

   setUnsigned(pos + 1, number, bits - 1);
   genes&#91;pos&#93; = 0;
}

unsigned long BitGenome::getUnsigned(int pos, int bits) const
{
   unsigned long num = 0;

   for (int i = pos; i < pos + bits; i++)
      num = (num << 1) + (genes&#91;i&#93; ? 1 : 0);

   return num;
}

long BitGenome::getSigned(int pos, int bits) const
{
   long num = getUnsigned(pos + 1, bits - 1);
   return genes&#91;pos&#93; ? -num : num;
}

void BitGenome::set(int bit, bool value)
{
   genes&#91;bit&#93; = value;
}

bool BitGenome::get(int bit) const
{
   return genes&#91;bit&#93;;
}

bool BitGenome::operator&#91;&#93;(int bit) const
{
   return get(bit);
}

void BitGenome::mutate(BitMutationMethod& mutationMethod)
{
   mutationMethod.mutate(*this);
}

std::pair<BitGenome, BitGenome> BitGenome::crossover(const BitGenome& other, 

BitCrossoverMethod& crossoverMethod) const
{
   if (size() != other.size())
      throw std::invalid_argument("Incompatible genomes!");

   return crossoverMethod.crossover(*this, other);
}

int BitGenome::size() const
{
   return genes.size();
}

Note que números signed são armazenados como complementos de 1, não de 2, pois encontrei alguns artigos que faziam essa recomendação. A classe ainda não tem suporte a tipos float ou double. Essa última deficiência pode ser contornada usando aritmética de ponto fixo.

Cruzamentos

Dois individuos sexuados (e no caso desses algoritmos, todos são) podem cruzar e compartilhar genes. Há várias políticas que descrevem como fazer isso. A interface que representa uma política qualquer é a classe CrossoverMethod, descrita abaixo (novamente, namespace foi omitido):

//BitCrossoverMethod.h

class BitGenome;

class BitCrossoverMethod
{
   public:
      virtual std::pair<BitGenome, BitGenome> crossover(const BitGenome& genome1,
          const BitGenome& genome2);
      virtual ~BitCrossoverMethod();
};

Note que cada crossover resulta em 2 filhos. Um deles sendo a aplicação dos genes do pai sobre a mãe, e vice-versa.

Duas políticas já estão implementadas na SofiaIA. A primeira é a chamada PointCrossover. Ela consiste em escolher alguns pontos de corte para a troca dos genes, e alternar os genes dos pais e dos filhos nesses pontos. Por exemplo, suponha os genomas 0000000 e 1111111 e os pontos de corte 2 e 5. Eles resultariam no seguinte:

pai:   00|000|00   mãe: 11|111|11   filho1 – 0011100   filho2 – 1100011

Abaixo a implementação do algoritmo:

//PointCrossover.h
class PointCrossover : public BitCrossoverMethod
{
   private:
      std::set<int> cutSet;

   public:
      explicit PointCrossover(const std::set<int>& _cutSet);

      virtual std::pair<BitGenome, BitGenome> crossover(const BitGenome& genome1,
            const BitGenome& genome2);
};

//PointCrossover.cpp
PointCrossover::PointCrossover(const std::set<int>& _cutSet)
: cutSet(_cutSet) {}

std::pair<BitGenome, BitGenome> PointCrossover::crossover(const BitGenome& genome1,
       const BitGenome& genome2)
{
   std::pair<BitGenome, BitGenome> children(genome1, genome1);

   bool flip = false;

   for (int i = 0; i < genome1.size(); i++)
   {
      if (cutSet.find(i) != cutSet.end())
          flip = !flip;

      children.first.set(i, flip ? genome1.get(i) : genome2.get(i));
      children.second.set(i, flip ? genome2.get(i) : genome1.get(i));
   }

   return children;
}
&#91;/sourcecode&#93;

Amanhã inserirei um segundo construtor, que aceita varargs. Isso deve tornar o uso prático.Alguns autores diferenciam crossovers simples de múltiplos. Note que o algoritmo trata ambos os casos.

Outro método de cruza é o chamado cruza uniforme. Basicamente, escolhe-se uma taxa, que varia de 0 até 1. Então, para cada bit, sorteia-se um número, também de 0 até 1. Se o número for menor que a taxa, aquele bit é trocado. Caso contrário, o bit se mantém. Note que esse algoritmo, se a taxa for suficientemente pequena, pode gerar uma prole igual aos pais.

Abaixo, segue o algoritmo:

&#91;sourcecode language="cpp"&#93;
//UniformCrossover.h
class UniformCrossover : public BitCrossoverMethod
{
   private:
      float ratePerBit;

   public:
      explicit UniformCrossover(float _ratePerBit);
      virtual std::pair<BitGenome, BitGenome> crossover(const BitGenome& genome1,
          const BitGenome& genome2);
};

//UniformCrossover.cpp
UniformCrossover::UniformCrossover(float _ratePerBit)
: ratePerBit(_ratePerBit) {}

std::pair<BitGenome, BitGenome> UniformCrossover::crossover(const BitGenome& genome1,
    const BitGenome& genome2)
{
   std::pair<BitGenome, BitGenome> children(genome1, genome1);
   std::srand(std::time(NULL));

   int minimum = static_cast<int>(ratePerBit * RAND_MAX);

   for (int i = 0; i < genome1.size(); i++)
   {
      if (std::rand() < minimum)
      {
         children.first.set(i, genome2&#91;i&#93;);
         children.second.set(i, genome1&#91;i&#93;);
      }
      else
      {
         children.first.set(i, genome1&#91;i&#93;);
         children.second.set(i, genome2&#91;i&#93;);
      }
   }

   return children;
}
&#91;/sourcecode&#93;

O usuário ainda é livre para esterder diretamente a classe BitCrossover e implementar sua própria política de cruzamento, se quiser.

<strong>Mutação</strong>

Além de cruzar, indivíduos também podem sofrer mutação. Isso permite que o algoritmo teste valores arbitrários, que podem conter um possível resultado. Assim como no crossover, a classe BitMutationMethod representa uma política de mutação qualquer:


class BitMutationMethod
{
   public:
      virtual void mutate(BitGenome& genome) = 0;
      virtual ~BitMutationMethod() {};
};

A mutação no caso de um genoma baseada em bits é muito simples. Basta escolher uma taxa e mudar os bits aleatoriamente, dentro daquela taxa. Mais ou menos como fizemos para alternar os bits no UniformCrossover. Políticas mais específicas geralmente são implementadas dentro do domínio do problema, isso é, pelo usuário da SofiaIA. A política de mutação baseada em random é implementada na classe RandomMutation, descrita abaixo:

//RandomMutation.h
class RandomMutation : public BitMutationMethod
{
   private:
      float ratePerBit;

   public:
      explicit RandomMutation(float _ratePerBit);
      virtual void mutate(BitGenome& genome);
      virtual ~RandomMutation();
};

//RandomMutation.cpp
RandomMutation::RandomMutation(float _ratePerBit)
: ratePerBit(_ratePerBit) {}

void RandomMutation::mutate(BitGenome& genes)
{
   std::srand(std::time(NULL));
   int minimum = static_cast(ratePerBit * RAND_MAX);

   for (int i = 0; i < genes.size(); i++)       if (std::rand() < minimum)          genes.set(i, !genes.get(i)); } [/sourcecode] O que poderia melhorar

  • Como já citado, ainda falta incluir um construtor com varargs na classe PointCrossover;
  • Seria necessário encontrar uma função de randomização melhor. Estou pensando em usar uma das classes da boost, ou implementar uma;
  • É necessário incluir método para manipulação de números de ponto flutuante no BitGenome.
  • É necessário comprovar que trabalhar com complementos de 1 é realmente vantajoso.

Onde obter mais informações

O melhor material que já achei sobre o assunto está no livro do Brian Schwab, AI Game Engine Programming.

O Norvig traz brevemente o tema, mas nada digno de nota.

Outro bom material está nesse site, e que tem tradução para o português!
http://www.obitko.com/tutorials/genetic-algorithms/portuguese/

Anúncios

Written by Vinícius Godoy

13 \13UTC julho \13UTC 2008 às 05:22:19

6 Respostas

Subscribe to comments with RSS.

  1. nao entendi qnd vc disse q unsigned sao armazenados como complemento de 1
    complemento de 1 (ou 2) nao sao apenas usados para representar numeros negativos? mas unsigned so permite valores positivos..

    rafael

    26 \26UTC dezembro \26UTC 2008 at 06:43:05

  2. Foi um engano mesmo, eu quis dizer signed. Já corrigi.

    vinigodoy

    26 \26UTC dezembro \26UTC 2008 at 06:48:05

  3. oi , eu estou com uma duvida em ag que nao consigo entender, acho q vc pode me esclarecer .
    Suponhamos que vai haver n cruzamentos, quando eu faco um cruzamento com 2 individuos,vai gerar 2 novos filhos, certo, para fazer um novo cruzamento eu tenho que pegar esses 2 filhos gerados e colocalos como pai para fazer um novo cruzamento, ou selecionar novamente 2 novos individuos?

    thais

    12 \12UTC abril \12UTC 2010 at 11:39:08

    • Funciona assim:

      Você tem uma geração de N indivíduos. Então, você prepara a próxima geração, que terá o mesmo número de indivíduos:

      1. Se houver elitismo, você irá separar alguns desses indivíduos (geralmente 1 ou 2, de maior score) diretamente, e coloca-los na próxima geração.
      2. Para os indivíduos que sobrarem, você realiza cruzamento, e coloca apenas os filhos na geração.

      Os filhos não cruzam entre si, nem com seus pais, durante esse processo.
      Quando eles vão se cruzar? Quando você processar essa próxima geração.

      vinigodoy

      12 \12UTC abril \12UTC 2010 at 12:56:43

  4. Olá ViniGodoy, estou precisando de um ajuda com Reconhecimento de Placas de Veículos e cheguei até vc. Teria como entrar em contato…

    Obrigado,

    Thiago Hardt

    09 \09UTC outubro \09UTC 2012 at 15:13:17

    • Claro, pode entrar em contato. Por aqui mesmo, ou pelo contato do ponto v. Tentei enviar e-mail para o endereço que você colocou aqui no site, e o e-mail voltou.

      vinigodoy

      09 \09UTC outubro \09UTC 2012 at 16:17:04


Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: