Algoritmos Genéticos com Raspberry Pi – Parte 13 – A Lógica da Reprodução

Acessado 205 vezes.
Como citar esse artigo: VERTULO, Rodrigo. Algoritmos Genéticos com Raspberry Pi – Parte 13 – A Lógica da Reprodução. Disponível em: <http://labdeeletronica.com.br/inteligencia-artificial/algoritmos-geneticos-com-raspberry-pi-parte-13-a-logica-da-reproducao/>. Acessado em: 22/11/2019.


Até o momento todo o desenvolvimento do Algoritmo Genético foi concentrado na criação de uma população de cromossomos e na seleção daqueles mais aptos para a resolução de um determinado problema. Após os melhores indivíduos terem sido escolhidos por meio de uma função de fitness qualquer é necessário gerar uma nova população cruzando as melhores características de cada um com o objetivo de obter-se elementos ainda melhores capazes de resolverem, ou chegarem mais próximos da solução, o problema para o qual o Algoritmo Genético está sendo criado. Essa etapa é chamada de “Reprodução” e é sobre isso que esse artigo tratará.

A etapa de reprodução consiste em dividir toda a população de cromossomos da geração atual em grupos de dois, chamados de “pais”. Esses cromossomos “pais” são utilizados para a geração de um par de “filhos”, cada um contendo uma parte de cada um de seus “pais” por meio do cruzamento dos genes de seus progenitores. O cruzamento dos genes dos “pais” pode ser feito de diversas formas diferentes, sendo as mais comuns o cruzamento simétrico e o cruzamento aleatório.

No cruzamento simétrico cada cromossomo dos “pais” é dividido ao meio originando quatro partes de cromossomos. A seguir, essa primeira etapa do processo é exemplificada. Perceba que cada um dos “pais” foi nomeado como “Ancestral 1” e “Ancestral 2” respectivamente.

 

Ancestral 1: 1101001111 (Parte 1_A1: 11010    –    Parte 2_A1: 01111)

Ancestral 2: 0101110111 (Parte 1_A2: 01011    –    Parte 2_A2: 10111)

 

Note que o cromossomo de cada ancestral foi dividido ao meio, originando um par de genes para o Ancestral 1 (Parte 1_A1 e Parte 2_A2) e um par de genes para o Ancestral 2 (Parte 1_A2 e Parte 2_A2). Cada uma das partes geradas contendo exatamente cinco genes.

A segunda etapa do algoritmo de reprodução simétrica consiste em cruzar os pares de genes para que dois “filhos” sejam gerados. Essa etapa é exemplificada a seguir:

 

Filho 1: Parte 1_A1 + Parte 2_A2 -> (11010 + 10111 = 1101010111)

Filho 2: Parte 1_A2 + Parte 2_A1 -> (01011 + 01111 = 0101101111)

Obs: O sinal de + utilizado representa uma concatenação e não uma soma.

 

É possível verificar no exemplo anterior que os “filhos” gerados possuem tanto genes do Ancestral 1, quanto do Ancestral 2, fazendo com que potencialmente eles possuam o que há de melhor em cada ancestral.

O processo de reprodução utilizando-se o cruzamento aleatório segue exatamente o mesmo princípio do simétrico, exceto pelo fato de que ao invés dos ancestrais serem divididos ao meio, o ponto de “quebra” dos cromossomos ser escolhido aleatoriamente. Veja no exemplo a seguir:

 

Ancestral 1: 1101001111 (Parte 1_A1: 110    –    Parte 2_A1: 1001111)

Ancestral 2: 0101110111 (Parte 1_A2: 010   –    Parte 2_A2: 1110111)

 

Filho 1: Parte 1_A1 + Parte 2_A2 -> (110 + 1110111 = 1101110111)

Filho 2: Parte 1_A2 + Parte 2_A1 -> (010 + 1001111 = 0101001111)

Obs: O sinal de + utilizado representa uma concatenação e não uma soma.

 

No exemplo anterior o ponto de “quebra” foi escolhido aleatoriamente como sendo no terceiro gene dos ancestrais.

Com a lógica da reprodução esclarecida, a próxima tarefa será codificar isso utilizando a linguagem Python. É o que será visto no próximo artigo.

Comentários

error: Conteúdo Protegido!