Algoritmos Genéticos com Raspberry Pi – Parte 11 – O Código do Sorteio

Como citar esse artigo: VERTULO, Rodrigo Cesar. Algoritmos Genéticos com Raspberry Pi – Parte 11 – O Código do Sorteio. Disponível em: <http://labdeeletronica.com.br/algoritmos-geneticos-com-raspberry-pi-parte-11-o-codigo-do-sorteio/>. Acesso em: 24/08/2019.


Agora que compreendemos a lógica de funcionamento do processo de sorteio dos cromossomos, partiremos para a sua codificação. Para guiar nossos passos, vamos recordar o que precisaremos fazer:

  • Ordenar em ordem crescente a população de cromossomos de acordo com a nota de avaliação de cada um.
  • Determinar a nota relativa de cada cromossomo da população.
  • Calcular a soma acumulada das notas relativas dos cromossomos.
  • Sortear indivíduos da população privilegiando aqueles que possuem maior aptidão.
  • Gerar uma nova população de indivíduos mais aptos.

Cada um dos cinco passos mostrados acima foram detalhados no artigo anterior e nosso foco a partir de agora será apenas em “traduzir” isso para código Python.

Para iniciar, veja que nosso código fonte da classe GARV possui dois novos métodos, o “__sort” e o “sorteia”.

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)
 
 
    def __sort(self,elem):
        return elem[1]
    def sorteia(self):
        listapopulacao = sorted(self.populacao, key = self.__sort)
        avaliacoes = [n for c, n in listapopulacao]
        somatoria = sum(avaliacoes)        
        probabilidades = [n/somatoria for n in avaliacoes]
 
        indicesEscolhidos = []
        for s in range(len(avaliacoes)):
            sorteio = random.random()
            aux = probabilidades[0]
            i = 1
 
            while(aux <= sorteio):
                aux = aux + probabilidades[i]
                i = i + 1
 
            indicesEscolhidos.append(i - 1)
 
        cromossomosEscolhidos = [listapopulacao[i][0] for i in indicesEscolhidos]
 
        self.populacao = cromossomosEscolhidos




O método “__sort(self, elem)” é um método auxiliar que será utilizado dentro do “sorteia(self)”, de modo que sua função e funcionamento ficarão claros conforme o segundo método for sendo explicado.

Observe que a primeira instrução do método “sorteia(self)” consiste na criação de uma variável chamada “listapopulacao”. Nesta variável é armazenada a lista de cromossomos da população atual ordenada em ordem crescente de acordo com a nota de cada cromossomo calculada na função fitness. Essa ordenação é feita utilizando-se o método “sorted” do Python que é capaz de ordenar listas segundo um critério determinado pelo parâmetro “key”. No nosso caso, como desejamos ordenar em ordem crescente de nota os cromossomos armazenados em “self.populacao”, é preciso informar no parâmetro “key” que o critério de ordenação será o elemento de índice 1 (justamente a nota de cada cromossomo contido em “self.populacao”) de cada cromossomo de nossa população. Quando “sorted” é executado, cada cromossomo de “self.populacao” é passado como parâmetro para “__sort(self, elem)” e o retorno é justamente o item de índice 1 do cromossomo considerado.

Depois que os cromossomos da população estão ordenados deve-se calcular a nota relativa de cada um. Para fazer isso uma nova lista chamada “avaliacoes” é criada, contendo somente as notas de cada cromossomo da população. A lista “avaliacoes” é utilizada logo em seguida para obter-se a somatória de todas as notas dos cromossomos, cujo valor é armazenado em “somatoria”.

De posse do valor da somatória das notas, é criada uma lista chamada “probabilidades” que contém as notas relativas de cada cromossomo, sendo cada uma calculada a partir da divisão da nota do cromossomo pela somatória de notas.

Agora é preciso calcular-se a soma relativa das notas dos indivíduos da população e realizar uma série de sorteios para que uma nova população de cromossomos seja gerada com os indivíduos mais aptos. A quantidade de sorteios a ser realizada equivale à quantidade de indivíduos da população. Desse modo, se por exemplo a população possuir 10 cromossomos, serão realizados 10 sorteios.

O laço “for” do método “sorteia(self)” é executado de acordo com a quantidade de indivíduos da população. Lembre-se que a lista “avaliacoes” possui todas as notas de cada cromossomo da população. Sendo assim, se existirem 10 notas dentro de “avaliacao” significa que existem 10 cromossomos na população. O laço “for” baseia-se nisso para saber quantas vezes ele deverá ser executado.

Dentro do “for” é realizado o sorteio de um número entre 0 e 1 e em seguida, no laço “while” é feita a soma acumulada das notas dos indivíduos da população enquanto o valor sorteado é menor ou igual a essa soma acumulada. Quando o valor acumulado torna-se maior que o valor sorteado o laço “while” é interrompido. A variável “i” do laço “while” armazena o índice da lista “avaliacoes” onde a interrupção ocorreu para que seja possível identificar qual é o cromossomo que deverá ser obtido da “listapopulacao”. A cada vez que o laço “while” é interrompido, um novo cromossomo é sorteado e adicionado à lista “cromossomosEscolhidos” que armazena todos os cromossomos sorteados.

Depois que o laço “for” executa todas as suas iterações, a população de cromossomos, representada por “self.populacao” é atualizada passando a conter os “cromossomosEscolhidos”.

Agora uma nova população de indivíduos mais aptos foi gerada, mas é preciso lembrar-se que a escolha dos indivíduos foi baseada em um sorteio, ou seja, por meio de um processo probabilístico. Pode ocorrer dos melhores indivíduos por “azar” não terem sido escolhidos e a nova população, apesar de potencialmente possuir os melhores elementos, pode ficar sem aqueles que eram realmente muito bons. Para resolver esse problema utiliza-se uma técnica chamada de “elitismo”, mas isso é assunto para o próximo artigo.

Comentários