Algoritmos Genéticos com Raspberry Pi – Parte 10 – Lógica do Sorteio

Como citar esse artigo: VERTULO, Rodrigo Cesar. Algoritmos Genéticos com Raspberry Pi – Parte 10 – Lógica do Sorteio. Disponível em: <http://labdeeletronica.com.br/algoritmos-geneticos-com-raspberry-pi-parte-10-logica-do-sorteio/>. Acesso em: 20/02/2019.


Continuando com o desenvolvimento de nosso Algoritmo Genético, depois que a avaliação de cada Cromossomo da população é realizada, o resultado será uma lista contendo todos os indivíduos com suas respectivas notas. Nosso próximo passo será a implementação de um mecanismo de sorteio que seja capaz de gerar uma nova população que privilegie a escolha dos Cromossomos que obtiveram as melhores avaliações.

Para facilitar a explicação dessa etapa do Algoritmo Genético, vamos supor que após o cálculo da aptidão de cada Cromossomo o resultado seja uma lista como a mostrada a seguir:

populacaoAvaliada = [ [“000111010110”, 7], [“110111100001”, 3], [“001010100011”, 12], [“111101110101”, 1] ]

Observe que na população existem Cromossomos com suas respectivas notas de aptidão que foram obtidas após a aplicação da função de Fitness.





É importante ressaltar que existem diversas formas de implementar-se um algoritmo de sorteio e a que será apresentada aqui é apenas uma delas, nem melhor, nem pior que qualquer outra. Em outras palavras, sempre há pontos positivos e negativos ao se escolher uma abordagem específica; para a maioria dos casos, o método que será apresentado que é conhecido como “Roleta Viciada” funciona bem. Vamos iniciar a explicação visualizando nossa população de Cromossomos em forma de tabela.


Cromossomo Nota (aptidão)
000111010110 7
110111100001 3
001010100011 12
111101110101 1

 

O método da “Roleta Viciada” consiste em dar maiores chances de serem escolhidos aos Cromossomos que possuírem as maiores notas de aptidão e o primeiro passo do algoritmo deve ser a ordenação dos indivíduos com base em suas notas. Após a realização da ordenação, a tabela ficará assim:


Cromossomo Nota (aptidão)
111101110101 1
110111100001 3
000111010110 7
001010100011 12

 

Em seguida aplicamos uma nota relativa para cada indivíduo, dividindo cada nota de aptidão pela soma das notas de todos os Cromossomos. É simples, veja a seguir:


Cromossomo Nota (aptidão) Nota Relativa (Somatória / Aptidão)
111101110101 1 0.043
110111100001 3 0.130
000111010110 7 0.304
001010100011 12 0.522
Somatória 23

1

 

Finalizaremos a “preparação” dos dados para o sorteio criando uma nova coluna na tabela que conterá, para cada Cromossomo, a Soma Acumulada das Notas Relativas. Esse cálculo consiste em somar o valor da Nota Relativa de cada Cromossomo com a Soma Acumulada do Cromossomo anterior. Veja a seguir:


Cromossomo Nota Nota Relativa Soma Acumulada
111101110101 1 0.043 0.043
110111100001 3 0.130 0.173
000111010110 7 0.304 0.477
001010100011 12 0.522 1
Somatória 23

1

 

 

Note que 100% dos Cromossomos possuem uma Nota (aptidão) menor ou igual a doze; 47,7% menor ou igual a sete; 17,3% menor ou igual a três e apenas 4,3% dos indivíduos possuem uma nota menor ou igual a um. Essas porcentagens correspondem às probabilidades de cada um ser escolhido durante o sorteio.

Agora é preciso fazer uso de números aleatórios para que possamos escolher os indivíduos mais aptos de nossa população. Será preciso que sejam realizados 4 sorteios, pois o tamanho da população utilizada nesse exemplo é formada por 4 Cromossomos. Serão sorteados 4 números aleatórios compreendidos entre 0 e 1 e o Cromossomo a ser escolhido deverá possuir uma Soma Acumulada imediatamente superior ou igual ao valor aleatório atual.

Por exemplo, suponha que tenham sido sorteados os seguintes números aleatórios entre zero e um: 0.94, 0.25, 0.78, 0.61. Veja na tabela a seguir cada Cromossomo escolhido para cada um dos valores aleatórios sorteados.


Cromossomo Escolhido Soma Acumulada Valor Aleatório
001010100011 1 0.94
000111010110 0.477 0.25
001010100011 1 0.78
001010100011 1 0.61

 

Repare que foram realizados 4 sorteios e que entre os Cromossomos escolhidos 3 correspondem ao indivíduo com maior aptidão na população inicial, ou seja, aquele cuja aptidão recebeu nota 12. A nova população gerada após o sorteio terá a seguinte configuração:

novaPopulacao = [“001010100011”, “000111010110”, “001010100011”, “001010100011”]

Agora a nova população é formada pelos Cromossomos com alta aptidão para a resolução do problema que está sendo trabalhado e o processo de reprodução para a geração de herdeiros ainda melhores poderá ser iniciado.

No próximo artigo transformaremos tudo o que foi explicado aqui em código Python.

Até breve!

Comentários

  • Renan Teodoro
    Responder

    Parabéns pelos artigos, estou acompanhando e realmente é muito didático. Não sou programador mas me interesso por phyton e com certeza utilizarei seus artigos para algum projeto futuro. Mais uma vez parabéns.

    • rvertulo

      Fico feliz em saber que meu trabalho o está ajudando Renan. Obrigado por suas palavras!

      Abraços