Algoritmos Genéticos com Raspberry Pi – Parte 7 – Avaliando Aptidão

Seguindo o nosso fluxograma, após a criação da População Inicial do Algoritmo Genético precisaremos desenvolver o método responsável pela Seleção dos Mais Aptos, ou seja, o código que será capaz de avaliar quais Cromossomos da população terão mais chances de serem escolhidos para se reproduzirem gerando herdeiros potencialmente melhores que seus genitores.

A principal ideia por trás dessa etapa dos Algoritmos Genéticos, derivada da teoria da evolução de Darwin, é a de que os indivíduos de uma população que estiverem mais adaptados ao meio onde vivem terão mais chances de sobreviverem e de se reproduzirem, gerando filhos com Cromossomos formados por partes dos Cromossomos de seus pais. Como, potencialmente, os pais são indivíduos bem adaptados ao ambiente, espera-se que os filhos também o sejam e, melhor ainda, a expectativa é a de que os filhos sejam melhores que seus pais por possuírem Cromossomos derivados de dois indivíduos que já possuem uma “boa” carga genética.

A codificação em linguagem de programação da Seleção dos Mais Aptos envolve duas tarefas: 1) Calcular a aptidão de cada Cromossomo da população e 2) Dar as maiores chances de serem escolhidos aos indivíduos que possuírem melhores aptidões a partir do cálculo feito na tarefa 1.

Nesse artigo, nosso foco será o desenvolvimento da primeira tarefa e para isso é preciso esclarecermos uma questão conceitual importante. As bibliotecas para a criação de Algoritmos Genéticos geralmente são construídas de forma genérica a fim de que muitos tipos diferentes de problemas possam ser resolvidos com elas, e esse também será nosso objetivo. Estamos desenvolvendo a classe GARV de modo que codifiquemos uma única vez todas as etapas do Algoritmo Genético para que ao final possamos reutiliza-la para inúmeras situações distintas. Isso é possível por que quase todo o código do Algoritmo Genético se mantém o mesmo independentemente do problema que está sendo atacado, com uma única exceção: a função de Fitness!

Fazendo uma analogia com a natureza, a função de Fitness é como se fosse os desafios à sobrevivência existentes no ambiente onde os indivíduos de uma população vivem, o local onde suas habilidades são testadas a todo instante para que os mais aptos possam se sobressair, sobreviverem e se reproduzirem. Se estivéssemos nos referindo a uma população de peixes, o habitat deles seria o lago onde vivem e os desafios que o mesmo oferece à sobrevivência dos indivíduos seriam a “função de Fitness”. Se nossa população fosse formada por aves, a região onde elas vivem e sobrevoam seria o habitat dos indivíduos da população e os desafios impostos pelo mesmo seriam a “função de Fitness” desse ambiente. Desse modo, de acordo com a população e os desafios existentes no habitat da mesma, a “função de Fitness” se altera, ou seja, todas as etapas apresentadas no fluxograma de nosso Algoritmo Genético são sempre iguais, com exceção da função de Fitness, que varia de acordo com o problema que se deseja resolver.

Compreendendo a analogia feita anteriormente, fica claro que precisaremos prever para a classe GARV uma forma de se permitir alterar a função de Fitness quando desejarmos sem que seja preciso alterar quaisquer outras partes do código do Algoritmo Genético. Não se preocupe se o conceito de função Fitness ainda está obscuro para você, pois no próximo artigo esse tema será detalhado exaustivamente.

Para conseguirmos deixar a função Fitness independente do código base do Algoritmo Genético, criaremos três novos métodos na classe GARV, chamados “getPopulacaoAtual”, “avaliaPopulacao” e “funcaoFitness”.

O primeiro método é muito simples e sua única função é retornar a lista contendo a população atual de Cromossomos criada pelo método “geraPopulação” explicado no artigo anterior.

O método “avaliaPopulacao” terá a função de capturar cada indivíduo da população de Cromossomos direcionando-os em seguida para o método “funcaoFitness”. Finalmente, o terceiro método ficará responsável pelo cálculo da “adaptabilidade” do Cromossomo ao problema que estiver sendo resolvido. Observe no código a seguir a criação dos três novos métodos com a explicação detalhada dos mesmos.

class GARV:
    def __init__(self):
        pass
 
 
    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

Como já foi mencionado, o método “getPopulacaoAtual” não realiza qualquer tipo de processamento sendo apenas uma rotina auxiliar para que consigamos capturar a lista da população atual de forma mais apropriada.

O método “avaliaPopulacao” é iniciado com a criação de uma lista vazia chamada “populacaoAvaliada” que conterá todos os Cromossomos da população atual já avaliados pela função Fitness. Repetindo, logo mais você verá exatamente como essa avaliação funciona, portanto não se preocupe. A próxima etapa do método consiste em executar um laço “for” cujo número de iterações corresponde ao total de Cromossomos existentes na população atual, para que todos possam ter sua aptidão calculada. Dentro do “for” obtemos o próximo indivíduo da população e logo em seguida vem o “pulo do gato”… observe a criação da variável “cromossomoAvaliado” que tem atribuído a si o resultado da execução do método “self.funcaoFitness” com o Cromossomo atual sendo passado como parâmetro. Como pode ser verificado no código, “funcaoFitness” trata-se de um método vazio e logo mais, quando formos utilizar a classe GARV em uma situação prática, eu lhe mostrarei como “rechea-lo” de acordo com o problema que se deseja resolver sem que precisemos alterar qualquer outra parte da classe. Isso significa que sempre que formos utilizar o Algoritmo Genético para resolvermos qualquer problema, o único código que precisaremos criar será aquele contido dentro da função Fitness.

As próximas instruções do laço “for” são intuitivas; o Cromossomo cuja aptidão foi calculada é inserido na lista “populacaoAvaliada” e depois que todos os indivíduos são processados a população atual é substituída por outra contendo os mesmos indivíduos, porém agora com cada um tendo sido processado pela função Fitness. No próximo artigo veremos que após a execução do método “avaliaPopulacaoAtual” o formato da lista contendo a população de Cromossomos mudará um pouco. Também veremos uma forma de realizar o sorteio dos indivíduos melhores avaliados para que eles possam se reproduzir para a criação de uma nova população potencialmente mais apta.

Eletrônica Simples Para Projetos Complexos

Deixe de ser alguém que fica copiando e colando circuitos da Internet e passe a ser um projetista capaz de criar soluções inovadoras com esse poderoso componente.