Algoritmos Genéticos – Parte 4

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 desenvolveu.

Procurei na Internet sobre o algoritmo e não encontrei. Então, chamei-o de RaittzSelection e adicionei 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 RaittzSelection : public SelectionFunction<Individual>
{
   private:
      private double exponent;
      sofia::util::Random random;

   public:
      explicit RaittzSelection(double _exponent = 1.1)
         : exponent(_exponent) {}
      explicit TournamentSelection(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 de Raiitz

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.