Sofia IA

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;
       }
};

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

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.