Algoritmos Genéticos com Raspberry Pi – Parte 14 – Codificação da Reprodução

Acessado 203 vezes.
Como citar esse artigo: VERTULO, Rodrigo. Algoritmos Genéticos com Raspberry Pi – Parte 14 – Codificação da Reprodução. Disponível em: <http://labdeeletronica.com.br/inteligencia-artificial/algoritmos-geneticos-com-raspberry-pi-parte-14-codificacao-da-reproducao/>. Acessado em: 22/11/2019.


Após ter compreendido a lógica do algoritmo responsável pela etapa de reprodução é possível iniciar a codificação do mesmo. Será adicionado ao código do algoritmo genético um método chamado “reproducao”, além de serem adicionadas duas novas propriedades à classe GARV chamadas “taxaCrossover” e “corteSimetrico”. Essas duas propriedades serão inicializadas por meio do construtor da classe GARV. A seguir são apresentadas as alterações feitas no construtor da classe GARV.

class GARV:
    def __init__(self, 
                 maiorValor = 999999, 
                 elitismo = 0.1,
                 corteSimetrico = False,
                 taxaCrossover = 1):
 
        self.maiorValor = maiorValor
        self.elitismo = elitismo
        self.corteSimetrico = corteSimetrico
        self.taxaCrossover = taxaCrossover

A função da propriedade “corteSimetrico” é indicar se a divisão dos cromossomos durante a etapa de reprodução deverá ser feita a partir do ponto central dos mesmos (corteSimetrico = True), ou se o ponto da divisão será escolhido de forma aleatória (corteSimetrico = False). A propriedade “taxaCrossover” tem a função de dar ao algoritmo genético a capacidade do mesmo realizar a operação de “cross over” (que nada mais é do que a reprodução explicada no artigo anterior) de acordo com uma certa probabilidade. Desse modo, com a “taxaCrossover” definida por padrão com o valor um, em 100% das vezes a operação de “cross over” ocorrerá, por outro lado, supondo que essa propriedade tivesse sido definida com o valor 0.3, o “cross over” ocorreria em 30% das vezes. Trata-se de mais um parâmetro que poderá ser ajustado para cada problema a ser resolvido pelo algoritmo genético de modo a tentar otimizar sua operação.

O método “reproducao” deve ser adicionado à classe GARV com a seguinte implementacao.

def reproducao(self, cromossomo1, cromossomo2):
    if(random.random() <= self.taxaCrossover):
        if(len(cromossomo1) == len(cromossomo2)):
 
            if(self.corteSimetrico == False):
                corte = random.randint(0, len(cromossomo1))
            else:
                corte = int(len(cromossomo1) / 2)
 
            cromossomo1Parte1 = cromossomo1[0:corte]
            cromossomo1Parte2 = cromossomo1[corte:len(cromossomo1)]
 
            cromossomo2Parte1 = cromossomo2[0:corte]
            cromossomo2Parte2 = cromossomo2[corte:len(cromossomo2)]
 
            filho1 = cromossomo1Parte1 + cromossomo2Parte2
            filho2 = cromossomo2Parte1 + cromossomo1Parte2
 
            return [filho1, filho2]
        else:
            return -1
    else:
        return [cromossomo1, cromossomo2]

O método recebe dois parâmetros, “cromossomo1” e “cromossomo2”, que são os indivíduos que sofrerão a operação de “cross over”, ou seja, eles serão os “pais” de dois novos herdeiros. A primeira estrutura condicional do método faz um sorteio de acordo com o valor da propriedade “self.taxaCrossover” para determinar se a reprodução deverá ou não ocorrer. No caso da reprodução ocorrer, verifica-se se os dois cromossomos possuem a mesma quantidade de genes, característica obrigatória, para logo em seguida ser identificado o ponto de divisão dos cromossomos para a realização do “cross over”. Se a propriedade “corteSimetrico” for “True” o ponto de divisão é definido com sendo o centro dos cromossomos, caso contrário, é feito um sorteio para que o ponto de divisão seja definido de forma aleatória.

Depois das operações descritas a reprodução, ou “cross over”, é realizada de acordo com a lógica da operação já apresentada anteriormente.

Ao final da execução do método, os dois novos indivíduos gerados (filhos) são retornados pelo mesmo. A seguir é possível verificar como a classe GARV ficará após as novas implementações apresentadas.

class GARV:
    def __init__(self, 
                 maiorValor = 999999, 
                 elitismo = 0.1,
                 corteSimetrico = False,
                 taxaCrossover = 1):
 
        self.maiorValor = maiorValor
        self.elitismo = elitismo
        self.corteSimetrico = corteSimetrico
        self.taxaCrossover = taxaCrossover
 
    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
 
def reproducao(self, cromossomo1, cromossomo2):
    if(random.random() <= self.taxaCrossover):
        if(len(cromossomo1) == len(cromossomo2)):
 
            if(self.corteSimetrico == False):
                corte = random.randint(0, len(cromossomo1))
            else:
                corte = int(len(cromossomo1) / 2)
 
            cromossomo1Parte1 = cromossomo1[0:corte]
            cromossomo1Parte2 = cromossomo1[corte:len(cromossomo1)]
 
            cromossomo2Parte1 = cromossomo2[0:corte]
            cromossomo2Parte2 = cromossomo2[corte:len(cromossomo2)]
 
            filho1 = cromossomo1Parte1 + cromossomo2Parte2
            filho2 = cromossomo2Parte1 + cromossomo1Parte2
 
            return [filho1, filho2]
        else:
            return -1
    else:
        return [cromossomo1, cromossomo2]

Com a realização da reprodução, a transmissão de características dos cromossomos “pais” para os cromossomos “filhos” gerados é realizada. O próximo passo consiste em aplicar o processo de mutação nos indivíduos gerados, conforme é descrito no fluxograma do algoritmo genético, mas isso é assunto para um novo artigo.

Comentários

error: Conteúdo Protegido!