Sofia IA

Inteligência artificial para jogos

Algoritmos Genéticos – Parte 4

with 4 comments

Hoje me reuni com a equipe que está desenvolvendo um algoritmo genético para identificação de placas. Participou da reunião o prof. dr. Roberto Raittz, com grande experiência no assunto. Entre as discussões, falamos sobre os algoritmos de seleção e o professor mostrou um algoritmo muito interessante, que ele mesmo idealizou.

Procurei na Internet sobre o algoritmo e não encontrei. Então, chamei-o de Asymptotic Selection (pois o comportamento de sua função é mesmo uma assíntota) e criei uma implementação, que foi adicionada ao SofiaIA. Os passos para o algoritmo são os seguintes:

  1. Escolha um número aleatório no intervalo [0 e 1);
  2. Eleve esse número por uma constate dada, normalmente entre 0,8 e 1,2. Note que, por ser um número menor que zero, uma constante maior que um tenderá a resultados pequenos, mais próximos ao zero, enquanto uma constante menor que um tenderá a resultados próximos de 1.
  3. Multiplique esse resultado pelo tamanho da população. O resultado obtido será o índice do elemento a ser selecionado. A população deve estar ordenada em ordem decrescente.

Simples não? Abaixo, a implementação do algoritmo em C++:

template <typename Individual>
class AsymptoticSelection : public SelectionFunction<Individual>
{
   private:
      private double exponent;
      sofia::util::Random random;

   public:
      explicit AsymptoticSelection(double _exponent = 1.1)
        : exponent(_exponent) {}
      explicit AsymptoticSelection(double _exponent = 1.1, unsigned seed)
        : exponent(_exponent), random(seed) {}

      virtual ScoredPopulation select(const ScoredPopulation& population, int amount)
      {
         ScoredPopulation selected = new ScoredPopulation();
         for (int i = 0; i < amount; i++)
         {
            //Generate a number from 0 to size()-1
            int index = static_cast<int>(
              population.size() * pow(random.nextDouble(), exponent));
            selected.push_back(population[index];
         }
         return selected;
      }
}; 

O algoritmo ainda tem algumas propriedades interessantes. A escolha do índice permite-nos definir o quão elitista o algoritmo será. Quanto mais alto, maior o elitismo. Um índice exatamente igual a 1 torna ele totalmente aleatório.

Um índice grande demais é também problemático. Um índice de 2, por exemplo, pode levar a Convergência Prematura, já discutida. Um índice pequeno demais pode levar a estagnação. O professor recomenda índices os índices entre 1,1 e 1,2.

Para demonstrar melhor esse comportamento, considere o seguinte gráfico que mostra a relação entre o valor sorteado e o expoente. O ponto plotado nada mais é do que o valor sorteado elevado ao expoente.

Seleção Assintótica

Seleção Assintótica

Podemos observar claramente que expoentes menores que 1 tenderão a resultados próximos 1, portanto, a selecionar elementos próximos do final da lista, de baixo score. Já os expoentes maiores que 1, por outro lado, obtém resultados próximos de 0, que representam indivíduos do início da lista, ou seja, na elite.

Agora, observe que para o expoente 1, os resultados distribuem-se linearmente. Afinal, o número sorteado elevado a 1 não se alterará. Isso quer dizer que, desde que o gerador de números aleatórios tenha uma distribuição uniforme (que é o caso da SofiaIA), todos os indivíduos terão a mesma chance de serem escolhidos.

Outra grande vantagem do algoritmo é que ele dispensa qualquer algoritmo de escala que não altere a ordem da lista. Isso porque a seleção baseia-se apenas nos índices (o que é equivalente a uma escala por ranking), e não nos scores, para escolha dos indivíduos. O que pode representar um bom ganho de performance.

O professor Raittz e eu publicamos esse algoritmo inédito na SBGames, num artigo chamado “A Framework for Genetic Algorithms in Games”.

Written by Vinícius Godoy

17 \17UTC julho \17UTC 2008 at 02:28:30

Algoritmos Genéticos – Parte 3

with one comment

Números aleatórios

Antes de falarmos sobre o algoritmo genético, devo citar que produzi uma classe para a geração de números aleatórios. Ela utiliza internamente algoritmos da boost, mas fornece uma interface muito mais fácil e intuitiva de usar. A classe chama-se Random, e sua interface é similar a classe de mesmo nome do Java. A classe foi adicionada no namespace sofia::util

//------ Random.h
class Random
{
   private:
      boost::mt19937 rng;

   public:
      explicit Random();
      explicit Random(unsigned seed);

      void seed(unsigned seed);
      unsigned nextInt(unsigned max);

      int nextInt(int min, int max);
      double nextDouble();

      float nextFloat();
      bool nextBool();
};

//------ Random.cpp
Random::Random() : rng(static_cast<int>(std::time(0))) {}

Random::Random(unsigned seed) : rng(seed) {}

void Random::seed(unsigned seed)
{
   rng.seed(seed);
}

unsigned Random::nextInt(unsigned range)
{
   if (range == 0)
      return 0;

   boost::uniform_int<unsigned> interval(0,range-1);
   boost::variate_generator<boost::mt19937&, boost::uniform_int<unsigned> >
      die(rng, interval);
   return die();
}

int Random::nextInt(int min, int max)
{
   boost::uniform_int<> interval(min,max);
   boost::variate_generator<boost::mt19937&, boost::uniform_int<> >
      die(rng, interval);
   return die();
}

double Random::nextDouble()
{
   boost::uniform_real<> realInterval(0,1);
   boost::variate_generator<boost::mt19937&, boost::uniform_real<> >
      realRandom(rng, realInterval);
   return realRandom();
}

float Random::nextFloat()
{
   boost::uniform_real<float> realInterval(0,1);
   boost::variate_generator<boost::mt19937&, boost::uniform_real<float> >
      realRandom(rng, realInterval);
   return realRandom();
}

bool Random::nextBool()
{
   return nextInt(100) % 2 == 0;
}

Seleção

Selecionar indivíduos para que se reproduzam é uma das principais necessidades do algoritmo genético. Indivíduos com o maior score devem ter maior chance de serem selecionados, mas indivíduos com score baixo não devem ser totalmente excluídos da seleção.

O SofiaIA disponibiliza 3 tipos de algoritmos de seleção, todos baseados na seguinte interface:

template <typename Individual>
class SelectionFunction
{
    virtual ScoredPopulation select(ScoredPopulation& population, int amount) = 0;
    virtual ~SelectionFunction() {};
};

Alterei o ScoredMultiset para ScoredPopulation e agora, ao invés de usar um MultiSet estou usando um std::vector. Isso porque o multiset não se mostrou prático na hora de fazer o cruzamento, conforme será visto adiante.

O primeiro tipo de seleção é chamado Seleção em Torneio. Basicamente, sorteamos dois indivíduos e adicionamos o de maior score na lista. O único indivíduo que nunca terá chance de ser escolhido é o de menor score. Veja a implementação do algoritmo:

template <typename Individual>
class TournamentSelection : public SelectionFunction<Individual>
{
   private:
      sofia::util::Random random;

   public:
      explicit TournamentSelection() {}
      explicit TournamentSelection(unsigned seed) : random(seed) {}

      virtual ScoredPopulation select(const ScoredPopulation& population, int amount)
      {
        ScoredPopulation selected = new ScoredPopulation();

        for (int i = 0; i < amount; i++)
        {
            ScoredIndividual one = population.get(random.nextInt(population.size()));
            ScoredIndividual two = population.get(random.nextInt(population.size()));
            population.push_back(one > two ? one : two);
        }
        return selected;
      }
};

O segundo e o terceiro algoritmo são de uma categoria chamada de algoritmo de roleta. Para entender a analogia do nome, imagine uma roleta, iguais aquelas do programa do Silvio Santos. Um grande círculo dividido em várias faixas, onde cada uma tem a largura proporcional ao score após a aplicação da escala.

Abaixo, está um exemplo de roleta feita a partir de uma população de 20 indíviduos. Observe que os scores sofreram a escala por ranking:

Roleta

Roleta

A forma que o algoritmo trabalha é a seguinte. Primeiro, pega-se um número entre 0 e a soma de todos os scores. Depois, percorre-se os elementos um-a-um, somando seus scores. Quando um indivíduo tiver seu score somado e esse valor se tornar maior que a soma fornecida inicialmente, ele será adicionado a lista.

Por exemplo, vamos supor que sorteassemos o número 43. Na roleta acima, pegaríamos o terceiro elemento, pois 20 < 43, 20+19=39 < 43, mas 20+19+18=57 e 57 >=43. É dessa forma que “giramos” a roleta.

A classe AbstractWheelSelection implementa essa lógica:

template <typename Individual>
class AbstractWheelSelection : public SelectionFunction<Individual>
{
   protected:
      virtual std::deque<int> generateSums(const ScoredPopulation& population,
          int amount, double sum) = 0;

   public:
      virtual ScoredPopulation select(const ScoredPopulation& population,
          int amount, double sum)
      {
         int sum = 0;
         BOOST_FOREACH(ScoredIndividual individual, population)
         {
            sum += individual.getScore();
         }
         std::deque<int> rouletteResults =
            generateSums(population, amount, sum);
         std::sort(rouletteResults.begin(), rouletteResults.end());

         ScoredPopulation selected = new ScoredPopulation();
         sum = 0;
         BOOST_FOREACH (ScoredIndividual individual, population)
         {
            sum += individual.getScore();
            while (rouletteResults.size() > 0 && rouletteResults.front() < sum)
            {
                selected.push_back(individual);
                rouletteResults.pop_front();
            }
         }
         return selected;
      }
};
&#91;/sourcecode&#93;

Esse algoritmo tem uma otimização, em relação a versão descrita inicialmente. Ele recebe um array ordenado, com o número de somas igual ao número de elementos a serem selecionados. Assim, ele é capaz de pegar todos os indivíduos percorrendo a lista uma única vez.

As variações do algoritmo baseiam-se em diferentes formas de "girar a roleta", ou seja, de se fornecer a soma inicial. E é por isso que o método generateSums permanece virtual puro.

A primeira versão é mais próxima dos talk-shows. Efetivamente giramos a roleta sem saber onde ela vai parar, ou seja, utilizamos valores de soma aleatórios. Esse algoritmo é descrito a seguir:

&#91;sourcecode language="cpp"&#93;
template <typename Individual>
class RouletteWheelSelection : public AbstractWheelSelection<Individual>
{
   public:
      RouletteWheelSelection() {}
      RouletteWheelSelection(unsigned seed) : random(seed) {}

   private:
      sofia::util::Random random;

   protected:
      virtual std::deque<int> generateSums(const ScoredPopulation& population,
          int amount, double sum)
      {
         std::deque<int> rouletteResults;

         while (rouletteResults.size() < amount)
            rouletteResults.push_back(random.nextInt(0, amount));
         return rouletteResults;
      }
};
&#91;/sourcecode&#93;

A segunda versão do algoritmo gira a roleta em uma quantidade fixa. Imagine a roleta dividida nas fatias proporcionais ao score. Em seguida, imagine que colocamos marcadores, usando uma divisão equalitária, igual ao número de elementos desejados. Então pegamos os elementos das fatias que estiverem em cima dos marcadores. É isso que ocorre no algoritmo conhecido como "Seleção Estocástica Universal":

&#91;sourcecode language="cpp"&#93;
template <typename Individual>
class StochasticUniversalSelection : public AbstractWheelSelection<Individual>
{
   protected:
      virtual std::deque<int> generateSums(const ScoredPopulation& population,
          int amount, double sum)
      {
         double division = sum / (double)amount;
         std::deque<int> sums;
         for (int i = 0; i < amount; i++)
             sums.push_back(static_cast<int>(i*division));

         return sums;
      }
};

Gerações

Finalmente, chegou a hora de criar uma classe que agrupe todos esses conceitos. É a classe Generation. Ela representa uma geração.O usuário do SofiaIA deve construir a primeira geração de indivíduos. Geralmente, 20 ou 30 indivíduos são suficientes. Então, basta chamar o método next() quantas vezes achar necessário.

Logo que uma geração é criada, ela é completamente avaliada pela função de fitness. O usuário pode já saber quem é o seu melhor indivíduo e qual seu score. A cada chamada ao next, os indivíduos passam pela escala, reprodução e mutação.

Outro conceito que a geração implementa é o de elitismo. Elitismo é um percentual de indivíduos de melhor score que serão transportados de uma geração para outra, sem qualquer tipo de modificação. Ou seja, garantimos que a elite esteja sempre na próxima geração. Isso permite uma convergência mais rápida. Um percentual ideal de elitismo gira em torno de 5%, elitismo alto demais pode levar ao problema da Convergência Prematura, citado ontem.

A geração também aplicará as taxas de cruzamento e uma nova taxa de mutação.

Caso os indivíduos não cruzem, eles são diretamente adicionados na próxima geração. Se tiverem que cruzar, seus filhos é que entrarão na geração seguinte. Uma boa taxa de cruzamento gira em torno de 70 até 80%. O padrão da biblioteca é 75%.

O método de mutação aleatório, descrito no primeiro artigo, podia ter percentuais baixos de mutação. Entretanto, existem outros métodos, que podem ser garantidos. Então, considerei uma boa política também aplicar uma chance de mutação aqui. Se a mutação não ocorrer, o individuo selecionado é diretamente adicionado na próxima geração. Caso contrário, seu método mutate() é chamado e seu resultado entra na próxima geração. Uma boa taxa de mutação deve ser 1% por bit. A SofiaIA usa como padrão 100%, pois assume-se que o usuário utilizará o RandomMutation com 1%.

Eis a implementação da classe:

template <typename Individual>
class Generation
{
   private:
      unsigned count;

      ScoredPopulation scored;
      FitnessFunction<Individual> fitnessFunction;
      scaling::ScalingFunction<Individual> scalingFunction;
      selection::SelectionFunction<Individual> selectionFunction;

      double crossoverRate;
      double ellitismRate;
      double mutationRate;

      explicit Generation(std::vector<Individual> population,
                          const Generation<Individual>& other)
      : count(other.count+1), fitnessFunction(other.fitnessFunction),
         scalingFunction(other.scalingFunction),
         selectionFunction(other.selectionFunction),
         crossoverRate(other.crossoverRate),
         ellitismRate(other.ellitismRate),
         mutationRate(other.mutationRate)
      {
         doCalculations(population);
      }
   private:
      void doCalculations(const std::vector<Individual> population)
      {
         BOOST_FOREACH(Individual individual, population)
         {
            scored.push_back(Scored(individual,
               fitnessFunction.calculateFitness(individual)));
         }
         std::sort(scored.begin(), scored.end(), std::greater<ScoredIndividual >());
      }

   public:
      explicit Generation(std::vector<Individual>& population,
         const FitnessFunction<Individual>& fitness,
         const scaling::ScalingFunction<Individual>& scaling = scaling::NoScaling<Individual>(),
         const selection::SelectionFunction<Individual>& selection = selection::RouletteWheelSelection<Individual>(),
         double _crossoverRate = 0.75,
         double _mutationRate = 1,
         double _ellitismRate = 0.05)
      : count(1), fitnessFunction(fitness), scalingFunction(scaling),
         selectionFunction(selection), crossoverRate(_crossoverRate),
         mutationRate(_mutationRate), ellitismRate(_ellitismRate)
      {
         doCalculations(population);
      }

      const Individual& getBestIndividual() const
      {
         return scored[0].get();
      }

      unsigned getBestScore() const
      {
         return scored[0].getScore();
      }

      unsigned getCount() const
      {
         return count;
      }

      Generation<Individual> next(unsigned seed = 0)
      {
         std::vector<Individual> next;

         //Separate the elite, if any
         int eliteSize = static_cast<int>(ellitismRate * scored.size());
         int i = 0;
         BOOST_FOREACH(ScoredIndividual i, scored)
         {
            if (i >= eliteSize)
               break;
            next.push_back(i.get());
         }

         ScoredPopulation scaled = scalingFunction.scale(scored);

         //Select candidates for crossover
         ScoredPopulation selected = selectionFunction.select(scaled, scaled.size() - eliteSize);

         //For each selected pair
         for (int i = 0; i < selected.size() - 1; i += 2)
         {
            sofia::util::Random random;
            if (seed > 0) random.seed(seed);

            const Individual& p1 = selected[i].get();
            const Individual& p2 = selected[i+1].get();

            //Cross the selection or not, according to the crossover rate
            std::pair<Individual, Individual> children =
               random.nextDouble() < crossoverRate ? p1.crossover(p2) :
                  std::pair<Individual, Individual>(p1, p2);

            //Mutate the children, if need.
            if (random.nextDouble() < mutationRate)
                children.first.mutate();

            if (random.nextDouble() < mutationRate)
                children.second.mutate();

            //Then, add the elements to the return list
            next.add(children.first);
            next.add(children.second);
         }

         return new Generation<Individual>(next, this);
      }
};

Observações

Apesar de toda complicação descrita até aqui, o uso do framework é relativamente simples. O usuário precisaria apenas:

  1. Implementar indivíduo, com os métodos crossover e mutate. Para isso, poderá usar a classe auxiliar BitGenome;
  2. Implementar uma função de fitness;
  3. Criar uma nova geração, com aproximadamente 20 indivíduos aleatórios.
  4. Chamar o método next() quantas vezes achar necessário.

Da mesma forma, usuários avançados poderiam refinar os métodos de seleção e cruzamento, seja escolhendo opções diferentes disponíves, seja implementando seus próprios métodos ou estrutura de genoma.

Além disso, todos os algoritmos que geram números aleatórios aceitam como parâmetro a semente. Isso permite que o usuário, se desejar, torne o comportamento do algoritmo determinístico. Assim, num jogo de rede, por exemplo, duas máquinas remotas rodando o algoritmo genético sobre a mesma massa de dados obteriam exatamente o mesmo resultado, ainda mantendo um comportamento relativamente aleatório para o ser humano que assiste o jogo.

Written by Vinícius Godoy

15 \15UTC julho \15UTC 2008 at 03:32:46

Algoritmos Genéticos – Parte 2

leave a comment »

Individual

Hoje, reforcei o conceito de indíviduo para o meu framework. O indivíduo é o responsável por encapsular qual é o tipo de genoma utilizado. Ele também fornece métodos de alto nível para a função de fitness. Por exemplo, um indivíduo que representa um possível retângulo da imagem teria os métodos getX(), getY(), getWidth() e getHeight() e possivelmente outros métodos utilitários, como intersects. Internamente, ele armazenaria esses valores em alguma estrutura de genoma que convier para o usuário do framework, como o BitGenome demonstrado ontem.

No framework, o indivíduo é apenas um argumento de um template. Todo indivíduo deve ser capaz, no entanto de suportar 2 métodos:

O primeiro é o mutate(). Ele força o indivíduo a sofrer uma mutação. Exatamente como essa mutação ocorre é definido pelo implementador do indivíduo, portanto, o usuário da SofiaIA. Ontem vimos possíveis políticas par ao caso do genoma baseado em bits.

O segundo é o cross. Cada indivíduo deve ser capaz de cruzar com outro indivíduo da mesma espécie e gerar 2 novos indivíduos. O BitGenome também já implementa alguns tipos de cruzamento pré-definidos.

ScoredIndividuals

Todo individuo, cedo ou tarde, receberá um score. Aliás, atribuir scores é uma tarefa muito comum em vários tipos de algoritmos de IA. Portanto, uma classe imutável simples, que contém um elemento qualquer e um score foi criada para facilitar essa tarefa:

Ela se encontra no namespace util, e será usada durante a implementação do genético:

template <typename T>
class Scored
{
   private:
      T elem;
      unsigned score;
   public:
      explicit Scored(const T& _elem, unsigned _score)
      : elem(_elem), score(score) {}

      const T& get() const { return elem; }
      unsigned getScore() const { return score; }
};

Atribuição da nota

Todas as notas são atribuídas através de uma função de fitness. Basicamente, a função de fitness recebe um indivíduo, observa seus atributos, e atribui a ele um escore. Quem implementa a função de fitness integralmente é o usuário da SofiaIA. A função de Fitness, na biblioteca, é definida pela seguinte interface:

template <typename Individual>
class FitnessFunction
{
    virtual unsigned calculateFitness(Individual individual) = 0;
    virtual ~FitnessFunction();
};

Escala das notas

O algoritmo genético baseia-se em aleatoriedade. Pode ocorrer uma situação em que, um determinado indivíduo receba uma nota muito maior do que os demais. Esse indivíduo provavelmente cruzará mais e o algoritmo convergirá rapidamente para indica-lo como possível resposta. Entretanto, outra resposta melhor, em outro ponto, poderia ter sido encontrada. Essa situação é chamada de Convergência Prematura.

Outra situação indesejável ocorre mais ao final do processo, quando muitos indivíduos são parecidos demais e o algoritmo fica estagnado em um único ponto.

Para evitar esses problemas, podemos aplicar uma função de escala em todos os scores. O SofiaIA suporta 3 tipos de escalas possíveis, a partir da seguinte interface:

template <typename Individual>
class ScalingFunction
{
   public:
      virtual ScoredMultiset scale(const ScoredMultiset& population) = 0;
      virtual ~ScalingFunction() {};
};

O ScoredMultiset nada mais é do que uma macro. Ele representa um std::multiset de individuos com escore (usando a classe utilitária citada acima). Outra macro como essa utilizada é a ScoredIndividual. Adotei esse esquema porque não quero incluir o comando using em arquivos .h, mas ainda quero manter a clareza do código. Os leitores devem concordar que é melhor ler:

virtual ScoredMultiset scale(const ScoredMultiset& population) = 0;

do que:

virtual std::multiset<sofia::util::Scored<Individual> > scale(
const std::multiset<sofia::util::Scored<Individual> >& population) = 0;

O primeiro tipo de escala disponível é chamado de RankScaling. Nada mais é do que atribuir ao indivíduo de menor score a nota 0, ao de segundo menor a nota 1 e assim sucessivamente, de modo que o melhor indivíduo terá a nota igual ao tamanho da lista – 1.

template <typename Individual>
class RankScaling : public ScalingFunction<Individual>
{
   public:
    ScoredMultiset scale(const ScoredMultiset& population)
    {
      ScoredMultiset scaled;

      int i = 0;
      BOOST_FOREACH(ScoredIndividual scored, population)
      {
         scaled.add(ScoredIndividual(scored.get(), i++));
      }

      return scaled;
    }
};

Como vocês devem ter notado, optei por usar a biblioteca boost de agora em diante. Porém, para manter a política de que a SofiaIA deve ser fácil de utilizar, vou tentar me ater somente aos trechos da biblioteca que não exigem compilação. O resto do código será remodelado posteriormente para usar mais intensivamente a biblioteca.

O segundo tipo de escala é chamada de SigmaTruncation e usa o cálculo do desvio padrão. Esse tipo de escala é útil quando os escores são muito próximos, e queremos destacar os indivíduos que se distanciaram mais da média. Computacionalmente é a função de escala mais pesada, é famoso por obter bons resultados em populações muito homogêneas.

A constante c permite-nos dizer o quão afastado queremos que os resultados estejam, e é um número que varia usualmente de até 3.

template <typename Individual>
class SigmaTruncation : public ScalingFunction<Individual>
{
   private:
       double c;

   public:
       SigmaTruncation(double _c) : c(_c)
       {}

       ScoredMultiset scale(const ScoredMultiset& population)
       {
         //Calculate the average
         double sum = 0;
         BOOST_FOREACH(ScoredIndividual scored, population)
         {
            sum += scored.getScore();
         }

         //Calculate the standard deviation (sigma)
         double sum2 = 0;
         double avg = sum / population.size();

         BOOST_FOREACH(ScoredIndividual scored, population)
         {
            double dif = scored.getScore() - avg;
            sum2 += dif * dif;
         }
         double sigma = sqrt(sum2 / (population.size() - 1));

         //Finally, calculate the fitness
         ScoredMultiset scoredPopulation;
         BOOST_FOREACH(ScoredIndividual scored, population)
         {
            int fitness = static_cast<int>(scored.getScore() - (avg - c * sigma));
            scoredPopulation.insert(ScoredIndividual(scored, fitness < 0 ? 0 : fitness));
         }
         return scoredPopulation;
       }
};
&#91;/sourcecode&#93;

O terceiro tipo de escala é a ausência de escala. Sua implementação é bem direta:

&#91;sourcecode language="cpp"&#93;
template <typename Individual>
class NoScaling : public ScalingFunction<Individual>
{
   public:
      virtual ScoredMultiset scale(const ScoredMultiset& population)
      {
         return ScoredMultiset(population);
      };
};

Ele simplesmente copia o multiset de entrada no de resultado. Obviamente é o método mais rápido e é muito útil quando a função de fitness dá resultados precisos.

Obviamente, o usuário ainda é livre para implementar sua própria função de escala, caso queira.

O que falta

  • Melhorar a integração com a boost:
    • Provavelmente será possível reduzir o número de cópias usando shared_ptr.
    • Também é possível usar os geradores de números aleatórios da boost, em substituição ao péssimo gerador do C++;
  • Criar os algoritmos de seleção e representação da população;
  • Elaborar um exemplo de uso e testar as classes.

Written by Vinícius Godoy

14 \14UTC julho \14UTC 2008 at 00:39:10

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/

Written by Vinícius Godoy

13 \13UTC julho \13UTC 2008 at 05:22:19

Máquina de Estados

with 4 comments

Finalmente posso retomar o projeto! Depois de meses parado graças as aulas que dei na escola técnica, decidi voltar implementando uma classe para lidar com máquinas de estados. Na verdade, isso porque recentemente fiz uma muito parecida para Java, num jogo de pong, e vi o quão importante a classe é.

A classe segue a idéia do prof. Pozzer, e usa uma pilha para “memorizar” os estados passados. Assim, um estado pode solicitar o retorno ao estado anterior, o que simplifica drásticamente a construção de máquinas mais complexas, sobretudo de jogos RTS. Em jogos assim, retornar estados é muito comum. Um exemplo disso é o seguinte:

1. Madeireiro está no estado “CortandoLenha”. Chega um soldado inimigo, ele muda para o estado “Fugindo”;
2. Ele se afasta, até que o soldado para de persegui-lo e vai para uma batalha. Decide então voltar ao estado “CortandoLenha”;
3. Mas ele está longe das árvores! Então, empilha o estado “AndarAtéAFloresta”;
4. Após chegar na floresta, desempilha o estado e volta ao “CortandoLenha”.

A grande vantagem desse esquema é que cada estado pode ser modelado através de uma série de pré-condições e ações do estado. Se um estado não satisfaz a pré-condição, um estado que busca essa pré-condição é empilhado. Assim, a entidade pode apenas empilhar o estado final desejado, um “objetivo”. E a própria classe se encarrega de busca-lo.

A classe também segue a sugestão de Mat Buckland e permite a definição de um GlobalState. O GlobalState é processado antes de todos os estados.Alguns exemplos de ações globais são: “Verificar se tem vida, sono, fome, etc”.

#ifndef STATEMACHINE_H_INCLUDED
#define STATEMACHINE_H_INCLUDED

#include <queue>
#include "State.h"

namespace sofia
{
   namespace state
   {
      template <typename EntityType>
      class StateMachine
      {
         private:
            EntityType& owner;
            State<EntityType>* globalState;
            State<EntityType>* currentState;
            std::queue<EntityType*> previousStates;

            void doTheChange(State<EntityType>* nextState)
            {
               currentState->leave(*this);
               currentState = nextState;
               nextState->enter(*this);
            }

         public:
            StateMachine(EntityType& _owner,
                State<EntityType>* _globalState,
                State<EntityType*> _currentState)
            : owner(_owner), globalState(_globalState), currentState(_currentState)
            {
            }

            EntityType& getOwner() const
            {
               return owner;
            }

            void dropToState(State<EntityType>* nextState)
            {
               assert(nextState != NULL);
               previousStates.clear();
               doTheChange(nextState);
            }

            void changeState(State<EntityType>* nextState)
            {
               assert(nextState != NULL);
               previousStates.push(currentState);
               doTheChange(nextState);
            }

            void changeGlobalState(State<EntityType>* nextGlobalState)
            {
               globalState->leave(*this);
               globalState = nextGlobalState;
            }

            bool rewindState()
            {
               assert(!previousStates.isEmpty());

               doTheChange(previousStates->front());
               previousStates.pop();

               return !previousStates.isEmpty();
            }

            void process()
            {
               if (globalState != NULL)
                  globalState->process();
               if (currentState != NULL)
                  currentState->process();
            }

            bool isInState(const State<EntityType*>& state) const
            {
               return currentState == state;
            }

            State<EntityType>* getCurrentState() const
            {
               return currentState;
            }

            State<EntityType>* getPreviousState() const
            {
               return previousStates.front();
            }
      };
   }
}

#endif // STATEMACHINE_H_INCLUDED

Um estado, dentro desse contexto é uma interface bastante simples. Não vi muitas vantagens em modela-lo integralmente como um template. Aliás, parece-me vantagem que ele tenha uma estrutura formal. Se necessário for, pode-se criar um Adapter que receba três functors e mapeiem-nos para essa interface.

namespace sofia
{
   namespace state
   {
      template <typename EntityType>
      class State
      {
         public:
            virtual void enter(StateMachine<EntityType>& owner) = 0;
            virtual void process(StateMachine<EntityType>& owner) = 0;
            virtual void leave(StateMachine<EntityType>& owner) = 0;
            virtual ~State() {};
      };
   }
}

Agora, poderei aplicar essa classe juntamente com os steering behaviors já programador no Bola Gelada, conforme sugeriu o prof. Fábio Binder.

Uma das idéias é também criar uma classe ScriptedState, que automaticamente delega os métodos enter(), leave() e process() para um script, seja ele Lua ou Squirrel.

Written by Vinícius Godoy

11 \11UTC julho \11UTC 2008 at 21:21:41

Steering Behaviors – Pursuit e Evade

leave a comment »

O comportamento Pursuit faz com que um agente (perseguidor/pursuer) corra atrás de outro (fugitivo/evader), mas usa a posição futura estimada do fugitivo para calcular a trajetória que o perseguidor irá fazer. O evader é o comportamento contrário, ao invés de ir até a posição futura, o fugitivo tenta evita-la.

Pursuit e Evade

Não houve grande mistério na implementação desses algoritmos. O único detalhe é que dessa vez tanto o alvo, quanto o veículo são membros da classe veículo.

Abaixo, segue o código do pursuit:


namespace behavior
{
   class Pursuit : public SteerForce
   {
      private:
         const Vehicle& vehicle;
         const Vehicle& evader;

      public:
         Pursuit(const Vehicle& _vehicle, const Vehicle& _evader)
         : vehicle(_vehicle), evader(_evader)
         {
         }

         virtual math::Vector2D calculate()
         {
            //if the evader is ahead and facing the agent then we can just seek
            math::Vector2D toEvader =
               evader.getPosition() - vehicle.getPosition();

            if ((toEvader.dot(vehicle.getVelocity()) > 0) &&
                (vehicle.getVelocity().dot(evader.getVelocity()) < 0.95))
               return Seek<math::Vector2D>(vehicle, evader.getPosition()).
                        calculate();

            //Not considered ahead, so we predict where the evader will be

            //the look-ahead time is proportional to the distance between the
            //evader and the vehicle; and it's inversely proportional to the
            //sum of the agents velocities.
            double lookAheadTime = toEvader.getSize() /
               (vehicle.getMaxSpeed() + evader.getVelocity().getSize());

            //now seek to the predicted future position of the evader
            return Seek<math::Vector2D>(vehicle, evader.getPosition() +
               evader.getVelocity() * lookAheadTime).calculate();
         }
   };

E do Evade:

namespace behavior
{
   class Evade : public SteerForce
   {
      private:
         const Vehicle& vehicle;
         const Vehicle& pursuer;

      public:
         Evade(const Vehicle& _vehicle, const Vehicle& _pursuer)
         : vehicle(_vehicle), pursuer(_pursuer)
         {
         }

         virtual math::Vector2D calculate()
         {
            math::Vector2D toPursuer =
               pursuer.getPosition() - vehicle.getPosition();

            //the look-ahead time is proportional to the distance between the
            //pursuer and the vehicle; and it's inversely proportional to the
            //sum of the agents velocities.
            double lookAheadTime = toPursuer.getSize() /
               (vehicle.getMaxSpeed() + pursuer.getVelocity().getSize());

            //now flee away from predicted future position of the pursuer
            return Flee<math::Vector2D>(vehicle, pursuer.getPosition() +
               pursuer.getVelocity() * lookAheadTime).calculate();
         }
   };
}

Uma das chaves para esses algoritmos é a função que estima a posição futura.  Uma idéia interessante talvez seja parametrizar essa função, através de um functor e manter como padrão a função acima. Assim, uma implementação mais precisa poderia levar em consideração mais características físicas dos agentes envolvidos; tais como a velocidade de rotação, aceleração e frenagem; ou mesmo características do cenário, para obter-se um comportamento ainda mais convincente.

Written by Vinícius Godoy

05 \05UTC fevereiro \05UTC 2008 at 13:04:30

Steering Behaviors – Wander

with 2 comments

Wander é o Steering Behavior que faz com que um agente passeie aleatoriamente. O algoritmo cria um “alvo”, que é para onde o agente se locomove. Esse alvo desloca-se aleatoriamente sobre um círculo, projetado na frente do agente. O grau de aleatoriedade do movimento do alvo sobre o círculo é chamado jitter. Toda esse complicação é feita para garantir um movimento suave.

Steering behavior - wander

A implementação desse algoritmo, no livro do Buckland, envolvia a função “PointToWorldSpace”, que segundo o autor “sua descrição está fora do escopo do livro”. Estudando um pouco a teoria de sistemas de coordenadas, vi que uma função dessas certamente será necessária futuramente para a SofiaIA. Mas não vou entrar no mérito de multiplicações de matrizes por enquanto.

A idéia da função era clara. Projetar o alvo para frente do veículo. Se assumirmos que o raio do alvo, distância e jitter já se encontram no sistema de coordenadas do mundo, então projetar o alvo para frente do veículo torna-se uma tarefa fácil.

Abaixo, o algoritmo implementado com esses pressupostos:

namespace behavior {
   class Wander : public SteerForce
   {
      private:
         const Vehicle& vehicle;
         const double distance;
         const double radius;
         const double jitter;

         math::Vector2D target;
      public:
         Wander(const Vehicle& wanderVehicle, double wanderDistance,
            double wanderRadius, double wanderJitter)
         : vehicle(wanderVehicle), distance(wanderDistance),
            radius(wanderRadius), jitter(wanderJitter)
         {
            srand ( time(NULL) );
         }

          //Returns a random number between -1 and 1
        inline float randomClamped()
         {
            return (rand() / (RAND_MAX/2.0f))-1;
         }

         virtual math::Vector2D calculate()
         {
            //First, add a small random vector to the target's position
            target += math::Vector2D(randomClamped() * jitter,
                                     randomClamped() * jitter);

            //reproject the target vector to the circle size
            target.setSize(radius);

            //move the target to the front of the vehicle
            target += math::Vector2D(distance,0)
                        .rotate(vehicle.getVelocity().getAngle());

            //In order to move the target to vehicle front, the next operation
            //whould be summing the vehicle position, to the target position.

            //But since to calculate the steering direction we needed to
            //subtract the vehicle position, the two following lines:

            // target += vehicle.position();
            // return target - vehicle.position();

            //where simplified just to:

            return target;
         }
   };
}

Note que o wander não precisa de nenhum parâmetro de templates e, portanto, poderia ter sido implementado em dois arquivos (ao invés de só no .h). Esse algoritmo já foi corrigido e testado em meu protótipo e já funciona.

Written by Vinícius Godoy

04 \04UTC fevereiro \04UTC 2008 at 13:01:23