Uma Introdução aos Algoritmos Genéticos – Parte 2

Continuando nossos estudos em Algoritmos Genéticos, podemos lembrar que em Uma Introdução aos Algoritmos Genéticos – Parte 1, nós iniciamos estudos sobre o que são algoritmos genéticos e como pode ser elaborado um cromossomo para um algoritmo genético.

Agora, vamos estudar cada um dos passos necessários em um algoritmo genético a fim de que o mesmo possa reproduzir e selecionar os seres.

Criação da população inicial

A criação da população inicial não deve ser tão complexa, uma vez que seus valores são aleatórios, entretanto, se houver alguma regra quanto a como os parâmetros devem ser distribuídos, é bom atentar-se a eles.
Tomemos como exemplo nossos NPCs da seção anterior. Quando criamos os personagens para combate e queremos que eles estejam bem balanceados, é necessário que eles sejam criados em condições de equilíbrio, e este equilíbrio pode ser encontrado distribuindo-se uma mesma quantidade (via de regra, personagens no sistema 3D&T são criados inicialmente com 12 pontos distribuídos entre suas características). Isso evita que criemos um personagem muito bom não pela correta combinação das habilidades, mas sim porque o mesmo fora construído com mais pontos, desfazendo o equilíbrio exigido.

A criação de cada ser corresponde, então, à criação de um cromossomo qualquer, e a população inteira poderá ser armazenada na estrutura de dados que melhor convier: um array, uma lista dinâmica, etc.

Simulação e Pontuação

A simulação deve ser executada a fim de testar como cada ser (cujo comportamento e características estão determinados pelo seu cromossomo) se comporta em ação real e, portanto, saber se ele será uma boa escolha ou não.
A simulação deve ser feita de acordo com aquilo para o qual aquele ser foi projetado: se se trata de um carro de corrida, a simulação será uma corrida, se se trata de um personagem de luta, a simulação seria uma luta.
Além disso, é necessário criar boas regras para pontuar cada ser. No caso do nosso jogo de luta, podemos estimar que em primeiro lugar mereça mais pontuação aquele que derrota um inimigo, em segundo lugar aquele que consegue golpear um inimigo e, por fim, aquele que sobrevive mais tempo no combate.
Desta forma, podemos agora criar uma função que será invocada o tempo todo em nossa simulação a fim de pontuar cada cromossomo da seguinte forma:

  • Derrotar inimigo – 50 pontos;
  • Golpear inimigo – 10 pontos;
  • Para cada cinco segundos vivo em arena – 1 ponto.

Outra forma de pontuar é fazendo a avaliação e atribuindo a pontuação em um dado momento da “vida” de cada ser. Neste caso, no momento em que um personagem morresse calcular-se-ia sua pontuação e, quando acabasse o tempo de luta, calcular-se-ia dos sobreviventes.
O que importa é que devemos ter algum meio de simular a ação e contabilizá-la em pontos a fim de mais tarde poder determinar quem são os “cromossomos vencedores”.

Seleção de cromossomos

Após a simulação e pontuação dos cromossomos, precisamos selecionar os cromossomos que melhor servirão como “pais” e “mães” para os novos cromossomos a serem criados (ou como resposta para o nosso problema, caso tenhamos atingido a condição de parada).
Um jeito óbvio seria selecionar sempre os melhores. Mas podemos encontrar aqui um problema conhecido como “máximo local” (ou mínimo local, como é conhecido em alguns livros, como é o caso do “AI Techniques for Game Programming”).
O máximo local trata-se de um valor que, quando comparado com a sua vizinhança, parece ser o melhor de todos. Imagine então que temos um cromossomo que, pareça ser o melhor dentre os demais que guardem características similares a ele (ou seja, cromossomos que sofreram crossover e mutações para serem criados a partir dele), mas que não seja efetivamente a melhor solução.
Eis que, caso peguemos tal cromossomo como pai e criemos os filhos, na próxima geração ele continuará sendo o melhor e, portanto, nossa solução não convergirá na melhor resposta.
Para evitar isso, pode-se utilizar métodos para seleção que não obrigatoriamente pegarão o melhor cromossomo, como é o caso do método de seleção “roda da roleta” (do inglês, roulette wheel), onde se atribui a cada cromossomo uma probabilidade de ser selecionado de acordo com a sua pontuação obtida.
Suponha que a soma da pontuação de todos os cromossomos seja 2000 e que um dado cromossomo tenha conseguido 200 pontos. Neste caso, a probabilidade de seleção deste cromossomo é 200 / 2000 = 0.1 ou 10%.
Após isso, dispondo todos os cromossomos em alguma ordem, podemos dizer que, ao sortear um número fracionário aleatório entre 0 e 1, o cromossomo selecionado será o primeiro se o número for entre 0 e 0.35 (para um cromossomo com 35% de chances), ou o cromossomo será o segundo se o número estiver entre 0.35 e 0.45 (para um cromossomo com 10% de chances), e assim por diante até completar a “roda”.
Após a seleção de dois ou mais cromossomos para serem os pais, podemos começar o processo de reprodução, que pode ser feito da seguinte forma:

  • Escolha dois cromossomos;
  • Faça o crossover se necessário;
  • Faça mutações nos genes em que for necessário.

Com isso, obtêm-se dois novos cromossomos. Vejamos agora o que queremos dizer com crossover e mutações.
Obs: Lembre-se de que estamos REPRODUZINDO um novo cromossomo e não somente alterando os cromossomos pai e mãe, sendo assim, lembre-se de, no início do estágio de reprodução, criar cópias com as informações necessárias.

Crossover

Crossover trata-se do cruzamento (termo como pode ser encontrado na literatura brasileira) entre dois cromossomos.
Para efetuarmos este cruzamento, precisamos de duas coisas:

  • Saber se realmente devemos fazer o cruzamento por meio de uma taxa de crossover;
  • Saber em que ponto dos cromossomos fazer o crossover.

Vamos supor que tenhamos uma taxa de crossover de 70% (ou 0.7 se representado de 0 a 1). Se ao tirarmos um número aleatório de 0 a 1 encontrarmos um número maior ou igual a 0.7, então nós não faremos crossover entre os cromossomos (eles permanecerão do jeito que estão); agora, caso o valor seja menor que 0.7, então devemos efetuar um “corte de cruzamento” e, para tal, basta sortearmos uma posição no cromossomo e, então, trocar o pedaço de um cromossomo com o respectivo do outro. Graficamente, o resultado de um crossover seria o seguinte:

Exemplo de crossover em algoritmo genético

Exemplo de crossover em algoritmo genético

Mutações

Uma mutação é a alteração de uma informação genética que, na Biologia, pode ser ocasionada por diferentes agentes externos e internos do organismo em questão e, na Computação, geralmente é realizada a fim de garantir a diversidade da infomação.
Enquanto que o crossover cuida do cruzamento, isto é, da troca de informações entre dois cromossomos, as mutações cuidam de alteração da informação dos genes de um cromossomo sem relacioná-la com outro cromossomo.
Há diversos tipos de mutações e eles recebem, aqui, os mesmos nomes que recebem na área biológica de acordo com a forma como mutação altera os genes do cromossomo. Dois dos diversos tipos são a inversão, processo no qual a informação em um gene é invertida, e a permutação, processo no qual a informação de mais de um gene é trocado entre si. Vale lembrar que a permutação pode ser executada mesmo com genes não-consecutivos no cromossomo.
A fim de executar uma mutação em um cromossomo, deve-se usar uma taxa de mutação (deve ser testada da mesma forma que foi feita com a taxa de crossover), testando cada gene para saber se ele deverá sofrer mutação ou não.

Na terceira e última parte do nosso estudo sobre algoritmos genéticos, compreenderemos os principais parâmetros que influenciam o sucesso de um algoritmo, cuidados e aplicações na área de jogos.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS
 

One comment

  1. […] Uma Introdução aos Algoritmos Genéticos – Parte 2 […]

Leave a Reply

Your email address will not be published. Required fields are marked *

Email
Print