Algoritmos Genéticos com Raspberry Pi – Parte 11 – O Código do Sorteio
Acessado 3076 vezes.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/>. Acessado em: 16/02/2025.
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) < 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