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

Acessado 3600 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: 05/12/2023.

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!