Algoritmos Genéticos com Raspberry Pi – Parte 14 – Codificação da Reprodução
Acessado 3026 vezes.Como citar esse artigo: VERTULO, Rodrigo Cesar. 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: 10/02/2025.
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) < 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