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

Acessado 1418 vezes.
Como citar esse artigo: VERTULO, Rodrigo. 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/>. Acessado em: 20/10/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 (Aptidão / Somatória)
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

  • Renato
    Responder

    Muito bom conheci o blog ontem, estava rodando a internet por algo prático sobre o assunto como estudo por conta própria é difícil material bons como o seu. Parabens!

    • rvertulo

      Obrigado, fico contente em saber que meu trabalho está lhe sendo útil. Abraços.

  • Adelson Neto
    Responder

    Bom dia,

    Encontrei seu blog e estou acompanhando a criação desse AG. Gostaria de saber se há continuação arquivada ou você parou com esses conteúdos?
    Procurei em vários lugares uma explanação mais didática e aqui foi o mais didático.

    • rvertulo

      Olá, fico feliz em saber que os artigos estão sendo úteis. Acredito que na próxima semana publicarei uma nova parte sobre a série.

      Abraços

  • grayfbr
    Responder

    Bom dia,

    Não sei se meu comentário anterior foi enviado.
    Eu estou tendo aula sobre AG (matéria de IA), só que estou com muitas dificuldades de desenvolver um. Procurei em vários lugares e o seu blog é o mais didático que encontrei. Me ajudou demais a entender o funcionamento e tradução teoria/código.

    Gostaria de saber se você continuará com o código ou se tem ele para disponibilizar?

    • rvertulo

      Olá, fico feliz em saber que os artigos estão sendo úteis. Acredito que na próxima semana publicarei uma nova parte sobre a série.

      Abraços

error: Conteúdo Protegido!