Algoritmos Genéticos com Raspberry Pi – Parte 6 – Gerando População

Se você observar o fluxograma apresentado na Parte 2 desta série notará que o primeiro bloco funcional do nosso Algoritmo Genético foi chamado de “População Inicial”, ou seja, é um bloco responsável pela geração de uma população inicial de Cromossomos.

Compreender a necessidade e a importância deste bloco é algo bastante intuitivo, afinal de contas, os Algoritmos Genéticos têm seu funcionamento baseado na teoria da evolução das espécies. Desse modo, é preciso que exista um conjunto de indivíduos da mesma espécie pertencentes a uma população para que a evolução ocorra.

No contexto dos Algoritmos Genéticos, os indivíduos da população que precisaremos gerar são os Cromossomos que aprendemos a criar no artigo anterior. Dentro de nossa população existirão muitos Cromossomos, cada um representando uma possível solução para um determinado problema e que se combinarão de formas que aprenderemos mais tarde com o objetivo de se encontrar uma resposta ótima, ou quase ótima, para o problema a ser resolvido.

Ao criarmos uma população de Cromossomos devemos determinar a quantidade de indivíduos que farão parte da mesma, ou seja, precisamos informar o tamanho da população. Além disso, precisaremos definir as características dos indivíduos (Cromossomos) que farão parte da população. Será necessário informar quantos números estarão armazenados dentro de cada Cromossomo, bem como o menor e maior valor possível para cada um desses números. Restringir o universo de valores possíveis dentro de um Cromossomo é muito importante; em um mundo “perfeito”, e se fosse possível, poderíamos armazenar dentro deles uma quantidade infinita de números para tentarmos prever todas as respostas possíveis para um problema a fim de garantirmos que a solução ótima fosse encontrada. Contudo, isso faria com que o tempo de processamento do algoritmo também tendesse ao infinito, tornando seu uso inviável.

Vamos iniciar o trabalho de codificação expandindo a classe GARV adicionando a ela dois novos métodos, o “setNovaPopulacao” e o “geraPopulacao” conforme pode ser observado a seguir:

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)

Iniciarei a explicação pelo método “geraPopulacao” por ele fazer uso do “setNovaPopulacao”, de modo que o entendimento do segundo se dará naturalmente a partir do entendimento do primeiro.

O “geraPopulacao” é definido com 4 parâmetros cujos valores padrão determinam uma configuração básica para os Cromossomos da população. O parâmetro “tamanhoPopulacao” informa que inicialmente existirão 30 indivíduos na população; “qtdValores” define que por padrão cada Cromossomo armazenará 2 valores numéricos inteiros. Os parâmetros “menorValor” e “maiorValor” informam a faixa de valores permitidos para cada número armazenado pelos Cromossomos e, por padrão, poderão ser armazenados números entre 0 e 99. É importante observar que o parâmetro “maiorValor” também indica que os números armazenados pelos Cromossomos possuirão 2 dígitos (veja a importância disso no artigo anterior), pois o número 99 possui essa quantidade de dígitos.

Evidentemente, todos os valores padrão apresentados no parágrafo anterior poderão ser alterados no momento em que o Algoritmo Genético for utilizado em situações práticas.

A primeira instrução do método “geraPopulacao” cria uma lista inicialmente vazia, chamada “populacao”. É nessa lista que os Cromossomos da população serão armazenados de forma temporária enquanto a população estiver sendo gerada.

Logo em seguida existe uma estrutura “if” que garantirá que o tamanho da população que será gerada possua uma quantidade par de elementos. Em artigos futuros você aprenderá que em um determinado momento dois Cromossomos serão sorteados dentro da população para que eles se reproduzam a fim de gerarem herdeiros. Se o tamanho da população for impar sobrará um Cromossomo sem parceiro para a reprodução e não desejamos isso. Por esse motivo estamos forçando a criação de uma população com um número par de elementos.

A laço “for” que surge logo abaixo será executado de acordo com o “tamanhoPopulacao”, pois é nele onde cada Cromossomo da população será gerado. Se, por exemplo, o “tamanhoPopulacao” possuir o valor 30 esse laço rodará por esse número de vezes para que a mesma quantidade de Cromossomos seja gerada. A primeira tarefa executada dentro do “for” consiste em criar uma lista chamada “listaValores”. Nela serão guardados os valores que serão armazenados no Cromossomo que será criado. Note que existe outro laço “for” dentro do atual que é executado de acordo com a “qtdValores” definida. Desse modo, se nosso objetivo for criar Cromossomos que armazenem, por exemplo, 2 valores esse “for” interno será executado duas vezes.

Observe atentamente que os valores numéricos armazenados em “listaValores” são gerados de forma aleatória com números compreendidos entre “menorValor” e “maiorValor”. É preciso que os valores armazenados inicialmente em cada Cromossomo da população sejam aleatórios para que o Algoritmo Genético, ao realizar seu trabalho de buscar a solução para o problema que ele estiver tentando resolver, seja capaz de realizar essa tarefa em um amplo espaço de buscas.

Depois que os valores inteiros aleatórios a serem armazenados no Cromossomo são gerados é preciso converte-los para uma cadeia binária de acordo com as regras que definimos no artigo anterior e utilizando o método “geraCromossomo” também criado nele.

Com o novo Cromossomo gerado, ele pode ser inserido na lista temporária “populacao”, criada na primeira linha do método, para que a criação do próximo possa ser iniciada. Assim que todos os Cromossomos são gerados o método “setNovaPopulacao” é chamado, passando como parâmetro a lista temporária “populacao” que será finalmente atribuída a um atributo também chamado “populacao” (self.populacao), mas dessa vez pertencente à classe GARV.

Com a população inicial definida, estamos prontos para realizarmos a próxima etapa do Algoritmo Genético que é a seleção dos Cromossomos mais aptos. Assunto do nosso próximo artigo.

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.