Algoritmos Genéticos com Raspberry Pi – Parte 5 – Criando Cromossomos

Já sabemos criar Genes a partir de números inteiros e nosso trabalho rumo à criação de Cromossomos para nosso Algoritmo Genético se tornou um pouco mais simples. Porém, antes de mergulharmos na codificação precisaremos entender como criaremos os Cromossomos de forma um pouco mais conceitual.

Nosso objetivo é sermos capazes de armazenar um conjunto de valores numéricos representados em forma de uma cadeia binária dentro dos Cromossomos. Desse modo, pelo o que já fizemos até agora, se fossemos armazenar, por exemplo, os números 5 e 328 teríamos algo como o mostrado a seguir:

sendo assim, o Cromossomo resultante seria:

0101001100101000

O problema é que se agora desejarmos fazer o caminho inverso, ou seja, a partir da cadeia binária voltarmos aos números em notação decimal, e sabendo que cada dígito ocupa 4 bits, o resultado seria o mostrado a seguir:

5328

e é aí que está o problema! Como saberemos se os dois números que foram armazenados no Cromossomo foram o 5 e o 328 e não o 53 e 28? Também poderia ter sido o 532 e 8, ou somente o 5328. Percebeu o problema?

Um forma de resolver essa questão é definindo previamente a quantidade de dígitos que o maior número que será armazenado no Cromossomo possuirá. No exemplo acima, como o maior número é o 328, sabemos que ele possui 3 dígitos e todos os outros valores menores que ele também serão armazenados utilizando essa mesma quantidade de dígitos. No caso apresentado, o número 5 seria armazenado como sendo 005. Utilizando essa técnica teríamos o seguinte:

O Cromossomo resultante passaria a ser: 000000000101001100101000

Fica claro que o lado negativo dessa técnica é que serão necessários mais bits no Cromossomo, contudo, fica simples recuperarmos os valores originais, pois agora além de sabermos que cada dígito é formado por um grupo de 4 bits, também sabemos quantos grupos de 4 dígitos formam cada número armazenado. Veja a seguir:

Sabendo a estratégia que será utilizada para criarmos os Cromossomos, podemos iniciar a codificação de um método para isso em nossa classe GARV. Adicionaremos o método “geraCromossomo” da forma mostrada a seguir:

class GARV:
    def __init__(self):
        pass
 
 
    def converteINT2BIN(self, valor):
        n = str(valor)
        digitos = list(n)
        nbin = ""
        binariofinal = ""
 
        for d in digitos:
            nbin = "{0:b}".format(int(d))
            if(len(nbin) < 4):
                nbin = ((4 - len(nbin)) * "0") + str(nbin)
            binariofinal += nbin
 
        return binariofinal
 
 
    def geraCromossomo(self, listaValores, maiorValor):
        cromossomo = ""
        qtdDigitos = len(str(maiorValor)) * 4
 
        for g in listaValores:
            valorConvertido = self.converteINT2BIN(g)
            multiplicador = qtdDigitos - len(str(valorConvertido))
            valorConvertido = (multiplicador * "0") + str(valorConvertido)
 
            cromossomo = cromossomo + valorConvertido
 
        return cromossomo

O método “geraCromossomo” recebe dois parâmetros, sendo o primeiro “listaValores”, que é a lista de valores que serão armazenados no Cromossomo, e o segundo “maiorValor” contendo o maior número entre aqueles presentes na “listaValores”. No exemplo que estamos utilizando teríamos o seguinte:

listaValores = [5, 328]
maiorValor = 328

Perceba que é fundamental sabermos quantos dígitos serão utilizados para representar cada número. No exemplo atual serão 3 dígitos, pois é essa a quantidade de dígitos existentes no número 328 (que é o maior valor), e por meio do parâmetro “maiorValor” poderemos ter essa informação.

Dentro do método criamos a variável “cromossomo” que será utilizada para armazenar a cadeia de bits do Cromossomo que será gerado e logo em seguida criamos a variável “qtdDigitos” que possuirá a quantidade de dígitos que serão utilizados para representar cada número. Observe que obtém-se a quantidade de dígitos do maior valor da lista de valores utilizando-se a rotina “len” com o parâmetro “maiorValor” convertido para string. A rotina “len” é capaz de nos dizer quantos caracteres existem em uma string e por isso foi preciso transformar o “maiorValor” em string. Como cada dígito possui 4 bits, para sabermos a quantidade de bits que precisaremos para cada número basta multiplicar o número de dígitos do “maiorValor” por 4. No nosso exemplo, 328 possui 3 dígitos e serão necessários 12 bits para representa-lo, pois 3 * 4 = 12.

Agora precisaremos converter cada número inteiro da “listaValores” em sua representação em forma de cadeia binária e para isso está sendo utilizado o laço “for” que aparece logo em seguida. Esse laço será executado de acordo com a quantidade de números presentes em “listaValores” e a cada execução um número da lista será armazenado na variável “g” criada pelo laço “for”. Não me pergunte por que usei o nome “g” para essa variável, analisando agora realmente não faço a mínima ideia… 😉

A primeira instrução do laço “for” é uma chamada ao método “converteINT2BIN” que analisamos e criamos no artigo anterior. Ele receberá um número da “listaValores” (representado pela variável “g” a cada iteração do laço) e devolverá uma string com cada dígito do número passado para ele em forma de uma cadeia de 4 bits. No exemplo atual, na primeira execução do laço “for” o número 5 será convertido para “0101” e essa cadeia de bits será atribuída à variável “valorConvertido”.

Nós sabemos que cada dígito é formado por uma cadeia de 4 bits e no nosso exemplo precisaremos de 12 bits para sermos capazes de armazenar cada número, pois o “maiorValor” é 328 e esse número possui 3 dígitos. Contudo, como acabamos de ver, a conversão do número 5 gerou uma cadeia binária de 4 bits, ou seja, faltam 8 bits para completar os 12 desejados. As próximas duas instruções resolverão esse problema.

A variável “multiplicador” nos diz quantos dígitos faltam para que a cadeia binária atual possua os 12 dígitos que o nosso exemplo exige. Pegamos a quantidade de dígitos desejados (12 para esse exemplo) e subtraímos da quantidade de dígitos existentes na cadeia binária atribuída à “valorConvertido” (4 bits). Esse cálculo resulta em 8 para o caso do número 5 que foi convertido. Sabendo disso, logo em seguida adicionamos a quantidade de zeros que faltam ao lado esquerdo da cadeia binária armazenada em “valorConvertido”. Depois disso tudo o resultado do processamento para o número 5 será:

000000000101

O mesmo processo é realizado para cada número existente em “listaValores”. No exemplo considerado, o próximo valor é o número 328 e o resultado da conversão será:

001100101000

A cada nova conversão a cadeia gerada é concatenada à cadeia anterior por meio da instrução

cromossomo = cromossomo + valorConvertido

O resultado final da execução do método “geraCromossomo” para o nosso exemplo em que “listaValores” possui [5, 328] será:

000000000101001100101000

ou seja, uma cadeia binária de 24 bits sendo 12 bits para cada valor existente em “listaValores”.

Finalmente somos capazes de criar Cromossomos e podemos começar a implementar a geração da População Inicial apresentada no fluxograma do Algoritmo Genético que você conheceu na Parte 2 de nossa série. Mas isso faremos somente no próximo artigo.

Eletrônica Simples Para Projetos Complexos

Deixe de ser alguém que fica copiando e colando circuitos da Internet e passe a ser um projetista capaz de criar soluções inovadoras com esse poderoso componente.