Algoritmos Genéticos com Raspberry Pi – Parte 3 – Indivíduos

Como citar esse artigo: VERTULO, Rodrigo Cesar. Algoritmos Genéticos com Raspberry Pi – Parte 3 – Indivíduos. Disponível em: <http://labdeeletronica.com.br/algoritmos-geneticos-com-raspberry-pi-parte-3-individuos/>. Acesso em: 24/08/2019.


A cor do seu cabelo, a cor dos seus olhos, seu tipo sanguíneo e até muitas das doenças que você terá ao longo de sua vida foram determinadas antes de você nascer. Estas e outras características que determinam boa porte do que você é estão registradas em seus Cromossomos!

Não é nosso objetivo nos aprofundarmos nos aspectos biológicos dos Cromossomos, basta sabermos que cada um é formado por uma longa sequência de DNA contendo diversos Genes que determinam, entre outras, as características de um ser vivo que apresentei no parágrafo anterior.

A base do funcionamento dos Algoritmos Genéticos depende de nossa capacidade de representarmos um Cromossomo dentro do nosso código de programação. Diversos artigos acadêmicos que lidam com Algoritmos Genéticos apresentam muitas formas de representa-los, contudo, sem dúvida a mais comum é a representação como uma cadeia de bits, ou seja, por uma cadeia de valores que podem ser 0 ou 1. Cada bit da cadeia é chamado de Gene e a cadeia completa de Cromossomo. A seguir é exemplificada a representação de um Cromossomo utilizando uma cadeia de bits.

 
 





11011000101101110110111011011101

 

No exemplo acima temos representado um Cromossomo contendo 32 Genes, ou seja, 32 bits. É de fundamental importância compreender qual é o papel de nosso “cromossomo digital” na resolução de problemas utilizando Algoritmos Genéticos, pois toda a lógica de funcionamento dessa técnica depende disso.

Em computação qualquer problema que deseja-se resolver, apesar de muitas vezes não parecer, depende de encontrarmos ou calcularmos valores numéricos que atendam aos requisitos de cada problema a ser resolvido. Não podemos nos esquecer de que computadores são máquinas especializadas em calcular e que tudo o que eles são capazes de fazer se resume a resolverem contas de forma extremamente rápida.

É importante sempre ter em mente o que foi dito acima, pois uma tarefa primordial no momento de criar um Algoritmo Genético é determinar como um Cromossomo pode ser utilizado para representar números que resolvem um problema específico.

Suponha que tenhamos sido contratados por uma indústria de automóveis para que encontremos a solução, por meio de um algoritmo computacional, para a necessidade da empresa de aumentar o lucro de cada unidade de automóvel fabricada e vendida por eles. Tudo o que eles nos forneceram foi uma equação matemática que representa o Custo de fabricação por unidade e o valor desejado para o custo final do automóvel. Digamos que a equação seja a seguinte:

 

Custo = 3*(0.5x / 8y) + yˆ3 – sqrt(z) * (x / (z + 2y)) / log z

 

Eles também passaram uma série de restrições para os valores que as variáveis x, y e z podem assumir e, caso essas restrições não sejam atendidas, a solução torna-se inviabilizada. Além disso, eles disseram que precisam que o Custo seja algo próximo a $22.570,00.

Evidentemente, a equação acima eu inventei e não faço a mínima ideia do que ela representa. O importante aqui é que você consiga visualizar que trata-se de um problema complicado de ser resolvido e que existem três valores a serem encontrados, x, y e z.

Um Algoritmo Genético é um bom candidato para resolver esse problema, pois ele é especializado em buscar soluções ótimas ou quase ótimas para problemas que estão sujeitos a uma série de restrições, exatamente como esse que acabei de descrever. O primeiro passo para a criação de um Algoritmo Genérico para esse caso é determinar como um Cromossomo poderia ser definido para representar a solução desse problema, isto é, como ele poderia ser capaz de armazenar os valores possíveis para as variáveis x, y e z.

Vamos imaginar que a indústria de automóveis nos tenha dito que as três variáveis do problema podem assumir valores inteiros entre 0 e 1000. De posse dessa informação poderíamos definir que nossos Cromossomos serão formados por 30 Genes, ou 30 bits. Cada grupo de 10 bits armazenaria o valor de uma variável, como é mostrado a seguir:

 

110101101010111000111010101101
xyz

 

Cada bloco de 10 bits representaria o valor, em formato binário, que cada variável poderia assumir. No exemplo acima, x seria igual a 858, y igual a 739 e z igual a 685, que em nosso Cromossomo seriam representados como 110101101010111000111010101101.

A forma de representação de Cromossomos apresentada é apenas uma das possíveis. Nessa série de artigos será utiliza outra forma. Suponha que nosso objetivo seja criar um Cromossomo capaz de armazenar dois valores numéricos entre 0 e 99, por exemplo, os números 12 e 09. No código que criaremos para nosso Algoritmo Genético cada digito desses números será convertido para uma cadeia binária de 4 bits. Desse modo, nossos Cromossomos armazenarão os dígitos 1, 2, 0 e 9 respectivamente, com cada um possuindo quatro bits, ou seja:

 

0001001000001001
1209

 

Sendo assim, nosso Cromossomo de exemplo para armazenar os números 12 e 09 será 0001001000001001.

É muito importante que você compreenda exatamente a forma como utilizaremos nossos Cromossomos para armazenar os valores que desejarmos, pois todo o restante do aprendizado sobre Algoritmos Genéticos dependerá disso.

A partir do próximo artigo da série começaremos a colocar a mão na massa para criarmos o código em Python que nos permitirá criarmos os Cromossomos do nosso Algoritmo Genético.

Comentários