Algoritmos Genéticos com Raspberry Pi – Parte 10 – Lógica do Sorteio
Acessado 4228 vezes.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/>. Acessado em: 27/04/2025.
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
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
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
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
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