Algoritmos Genéticos com Raspberry Pi – Parte 8 – De Binário para Inteiro.

Como citar esse artigo: VERTULO, Rodrigo Cesar. Algoritmos Genéticos com Raspberry Pi – Parte 8 – De Binário para Inteiro.. Disponível em: <http://labdeeletronica.com.br/algoritmos-geneticos-com-raspberry-pi-parte-8-de-binario-para-inteiro/>. Acesso em: 21/05/2019.


No artigo passado, começamos a entender como funciona o bloco responsável pela Seleção dos Mais Aptos do fluxograma do Algoritmo Genético. Avançamos bastante ao compreendermos por que é preciso postergar a codificação da função de Fitness para permitirmos que a classe que estamos criando possa ser reutilizada na resolução de diversos problemas diferentes.

A partir deste artigo nos aprofundaremos ainda mais na explicação da Seleção dos Mais Aptos codificando uma função de Fitness didática, apenas para exemplificar sua utilização. Para que você consiga compreender bem o que será feito a partir de agora é necessário que você tenha noções básicas de programação Orientada a Objetos e eu partirei do princípio de que você possui esse conhecimento.

A Seleção dos Mais Aptos em um Algoritmo Genético é uma de suas partes mais complexas, então, para deixar as coisas mais simples de serem entendidas, vou “quebrar” a explicação em diversos artigos para que possamos evoluir de forma gradativa.

Para iniciar, vamos supor que nosso objetivo seja criar um Algoritmo Genético que seja capaz de encontrar o valor da variável “x” da função x^3 = 15.





Para conseguirmos criar uma função de Fitness que resolva esse problema didático precisaremos inicialmente desenvolver um método que seja capaz de converter a cadeia de bits que forma os Cromossomos em valores inteiros para que possamos realizar algumas operações sobre esses números de forma mais simples. É isso o que faremos neste artigo.

Para refrescar a memória, vamos relembrar como um Cromossomo é formado. Digamos que os Cromossomos de nossa população armazenem dois números cada um, contendo dois dígitos. Por exemplo, um Cromossomo armazenando os números 45 e 12 teria o seguinte formato:

0100010100010010

Sendo 0100 correspondente ao dígito quatro, 0101 correspondente ao dígito cinco, 0001 equivalente ao dígito 1 e finalmente 0010 para representar o dígito dois. Nossa meta neste artigo, rumo ao entendimento da Seleção dos Mais Aptos, será criarmos um método para a classe GARV chamado “converteBIN2INT” que seja capaz de receber Cromossomos parecidos com o do exemplo acima e devolver um valor inteiro relacionado a um dos números armazenados em forma binária no mesmo que se deseja converter.

O método receberá dois parâmetros, sendo o primeiro o Cromossomo que será manipulado e o segundo a posição do número que se deseja converter para inteiro. Para o exemplo descrito anteriormente, caso o objetivo fosse converter o segundo número armazenado no Cromossomo (o número 12), o primeiro parâmetro seria o Cromossomo propriamente dito e o segundo seria o valor 1 (as posições dos números no Cromossomo iniciam em zero), para indicar que deseja-se converter o segundo número armazenado.

Observe o método criado ao final da classe GARV a seguir e sua explicação.

 

class GARV:
    def __init__(self, maiorValor = 999999):
        self.maiorValor = maiorValor
 
 
    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) &lt; 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
 
 
    def setNovaPopulacao(self, novaPopulacao):
        self.populacao = novaPopulacao
 
 
    def geraPopulacao(self,
                      tamanhoPopulacao = 30, 
                      qtdValores = 2, 
                      menorValor = 0, 
                      maiorValor = 99):
        populacao = []
 
        #Garantir um número par de indivíduos
        if(tamanhoPopulacao % 2 != 0):
            tamanhoPopulacao = tamanhoPopulacao + 1
 
        for i in range(tamanhoPopulacao):
 
            listaValores = []
            for v in range(qtdValores):
                listaValores.append(random.randint(menorValor, maiorValor))
 
            cromossomo = self.geraCromossomo(listaValores, maiorValor)
            populacao.append(cromossomo)
 
        self.setNovaPopulacao(populacao)
 
 
    def getPopulacaoAtual(self):
        return self.populacao
 
 
    def avaliaPopulacao(self):
        populacaoAvaliada = []
 
        for c in range(len(self.getPopulacaoAtual())):
            cromossomo = self.getPopulacaoAtual()[c]
            cromossomoAvaliado = self.funcaoFitness(cromossomo)
            populacaoAvaliada.append(cromossomoAvaliado)
 
        self.setNovaPopulacao(populacaoAvaliada)
 
 
    def funcaoFitness(self, cromossomo):
        pass
 
 
    def converteBIN2INT(self, cromossomo, posNumero):
        qtdDigitos = len(str(self.maiorValor))
        bitsNumero = cromossomo[posNumero * 4 * qtdDigitos : (posNumero * 4 * qtdDigitos) + (qtdDigitos * 4)]
        bitsDigito = ""
        strNumero  = ""
        i = 1
 
        for b in bitsNumero:
            bitsDigito += b
 
            if(i % 4 == 0):
                strNumero += str(int(bitsDigito, 2))
                bitsDigito = ""
                i = 1
            else:
                i = i + 1
 
        return int(strNumero)

 

A primeira coisa que você deve observar é o construtor da classe GARV. Note que agora ele recebe um parâmetro chamado “maiorValor” com um valor padrão arbitrário (nesse caso defini como 999999 para que por padrão cada número possua 6 dígitos) e que esse parâmetro é armazenado em um atributo da classe de mesmo nome (self.maiorValor). Isso foi necessário por que no método “converteBIN2INT” precisaremos saber quantos dígitos formam cada número armazenado no Cromossomo.

Em relação especificamente ao método “converteBIN2INT”, veja que ele foi adicionado ao final da classe GARV e que sua assinatura possui os dois parâmetros que já foram explicados anteriormente.

Dentro do método são criadas 5 variáveis, sendo a “qtdDigitos” responsável por receber a quantidades de dígitos que formam cada número armazenado no Cromossomo, “bitsNumero” extrai dele os bits exatos correspondentes à posição passada no parâmetro “posNumero” do método e “bitsDigito”, “strNumero” e “i” que serão utilizadas dentro do laço “for” que aparece logo em seguida.

O objetivo do laço “for” é separar a cadeira binária correspondente ao número desejado em grupos de 4 bits, pois cada dígito utiliza essa quantidade de bits para ser armazenado no Cromossomo. Repare que a cada iteração um bit é concatenado à variável “bitsNumero” e que no momento que 4 bits estiverem presentes nela o bloco condicional “if” é executado para que os bits do número sejam convertidos para seu correspondente inteiro (ainda em formato string) e concatenado na variável “strNumero”.

Depois que todos os dígitos são concatenados em “strNumero” o método é finalizado retornando o valor dessa variável convertido para inteiro.

Com a finalização deste novo método, estamos prontos para codificarmos a função de Fitness que será responsável pela resolução do problema de encontrar o valor da variável “x” que satisfaça a função xˆ3 = 15. Mas isso será tarefa para nosso próximo artigo.

Comentários