Algoritmos Genéticos com Raspberry Pi – Parte 12 – Implementando o Elitismo
Acessado 2948 vezes.Como citar esse artigo: VERTULO, Rodrigo Cesar. Algoritmos Genéticos com Raspberry Pi – Parte 12 – Implementando o Elitismo. Disponível em: <http://labdeeletronica.com.br/algoritmos-geneticos-com-raspberry-pi-parte-12-implementando-o-elitismo/>. Acessado em: 11/09/2024.
No final do artigo anterior desta série foi mencionada a necessidade da implementação de um mecanismo que permitisse que os melhores indivíduos da população atual pudessem “sobreviver” para que os mesmos continuassem presentes na nova população gerada. Isso é necessário pelo fato da geração na nova população ser baseada em métodos probabilísticos, de modo que os melhores indivíduos, apesar de estatisticamente terem mais chances de serem mantidos na nova população, poderem ser eliminados simplesmente pelo fato de terem tido “azar”.
Para evitar o problema descrito anteriormente faz-se uso de uma técnica chamada “Elitismo”. Essa técnica consiste em separar os melhores cromossomos da população atual e, após a criação na nova população, inserir esses melhores indivíduos na nova população substituindo aleatoriamente um indivíduo existente na mesma por um indivíduo que foi escolhido no processo de elitismo.
A implementação desta técnica consistirá em fazer uma alteração no método “sorteia” adicionando as seguintes linhas de programação ao final do mesmo. Veja a seguir:
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] qtdElementosParaElitismo = int(self.elitismo * len(listapopulacao)) for i in range(qtdElementosParaElitismo): indiceParaSubstituicao = random.randint(0, len(cromossomosEscolhidos) - 1) cromossomosEscolhidos[indiceParaSubstituicao] = listapopulacao[len(listapopulacao)-i-1][0] self.populacao = cromossomosEscolhidos |
A definição da quantidade dos melhores indivíduos que serão separados da população atual é feita por meio da variável “qtdElementosParaElitismo”. Essa variável faz uso de da propriedade “self.elitismo” que ainda não foi criada em nosso código e que estará presente no construtor da classe “GARV” conforme pode ser visto a seguir:
class GARV: def __init__(self, maiorValor = 999999, elitismo = 0.1): self.maiorValor = maiorValor self.elitismo = elitismo |
A propriedade “self.elitismo” indica em porcentagem a quantidade de elementos da população atual que deverá ser preservada. Sendo assim, se o elitismo for definido, por exemplo, em 0.1 e a população atual possuir 100 indivíduos, serão preservados 10 elementos, ou seja, 10% da população.
O novo laço “for” adicionado ao final do método “sorteia” define aleatoriamente quais são os elementos da nova população que deverão ser substituídos por aqueles que foram preservados pelo elitismo. Lembre-se que a “listapopulacao” possui os indivíduos ordenados do melhor para o pior de acordo com a nota que foi atribuída a cada um pela função fitness. O novo laço “for” separa os “n” melhores indivíduos da “listapopulacao” e escolhe aleatoriamente indivíduos de “cromossomosEscolhidos” para que sejam substituídos pelos que foram preservados.
Com as novas implementações, a classe GARV ficará conforme é mostrado a seguir:
class GARV: def __init__(self, maiorValor = 999999, elitismo = 0.1): self.maiorValor = maiorValor self.elitismo = elitismo 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] qtdElementosParaElitismo = int(self.elitismo * len(listapopulacao)) for i in range(qtdElementosParaElitismo): indiceParaSubstituicao = random.randint(0, len(cromossomosEscolhidos) - 1) cromossomosEscolhidos[indiceParaSubstituicao] = listapopulacao[len(listapopulacao)-i-1][0] self.populacao = cromossomosEscolhidos |
Depois que o elitismo é aplicado chegou o momento de realizar a etapa de “reprodução” conforme é apresentada no fluxograma do algoritmo. Esta etapa será implementada no próximo artigo dessa série.
Comentários