Algoritmos Genéticos – Parte 3

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

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

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:

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

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”:

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.