Algoritmos Genéticos com Raspberry Pi – Parte 12 – Implementando o Elitismo

Acessado 228 vezes.
Como citar esse artigo: VERTULO, Rodrigo. 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: 22/11/2019.


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) &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]
 
        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

error: Conteúdo Protegido!