Algoritmo Genético

Definição

Um Algoritmo Genético é um algoritmo que busca encontrar as melhores características para uma dada população dado um objetivo, simulando o processo de seleção natural, onde cada geração de uma dada população é avaliada considerando um valor de fitness e os "melhores" dessa geração tem maior probabilidade de passar suas características para a próxima geração. Sempre que ocorre uma mudança de geração, as características dos indivíduos tem uma probabilidade de sofrer mutação. A mutação é importante, pois permite que a população tenha diversidade.

Em resumo, para que um algoritmo seja considerado um algoritmo genético, ele precisa obedecer 3 princípios:

1. Hereditariedade: as características de uma geração precisam ser passadas para a próxima geração.
2. Variação: os indivíduos de uma mesma geração precisam ter características diferentes.
3. Seleção: os “melhores” indivíduos de uma geração devem ter maior probabilidade de passar suas características para a próxima geração.

Passos para criar um algoritmo genético

1. Crie um conjunto de N elementos com características aleatórias.

2. Verifique o fitness de cada elemento (quanto melhor o fitness, maior as chances desse elemento ser utilizado no próximo passo).

3. De acordo com o fitness, selecione dois elementos e crie um novo elemento misturando as características dos dois elementos selecionados. Faça isso até criar uma nova geração completa de novos elementos (os elementos anteriores são descartados).

4. Aplique algumas mutações considerando uma probabilidade de mutação (geralmente algo em torno de 1%).

5. Verifique o fitness dos novos elementos.

6. Volte para o passo 3 até que determinada condição seja satisfeita. 

Por exemplo:

• Pelo menos um dos elementos alcançou um fitness desejado.

• A média do fitness do conjunto chegou em um valor aceitável.

Genes

Os genes de cada elemento de uma população são as características que fazem ele se comportar de determinada forma no ambiente onde está inserido. São eles que são usados no processo de hereditariedade e na mutação.

Os genes podem ser diversas coisas:

• Lista de movimentos pré-gerados (não levam em consideração informações do ambiente).

• Pesos para cada input (levam em consideração informações do ambiente).

• etc.

Hereditariedade

Uma das características fundamentais desse tipo de algoritmo, ela garante que exista a evolução da população. Ela consiste em misturar os genes de dois elementos de uma geração para gerar um elemento da próxima geração. 

Existem várias formas de executar essa ação, mas a mais comum é pegar metade dos genes de um elemento e juntar com a outra metade do outro elemento.

Exemplo:

genes_filho = elemento1.crossover(elemento2)

##
def crossover(elemento2):

    meio = len(self.genes) // 2

    return self.genes[:meio] + elemento2.genes[meio:]

Variação

Para que a população consiga chegar em um resultado satisfatório, é necessário que os elementos tenham genes variados, para que se comportem das mais diversas formas e seja possível sempre observar qual a melhor forma de alcançar o objetivo.

A variação ocorre em três momentos:

• Na criação dos primeiros elementos, onde são gerados genes aleatórios.

• Na mistura dos genes para criação da próxima geração.

• Na mutação dos genes dos elementos da nova geração.

Mutação

A mutação consiste em alterar os genes de um elemento considerando uma taxa de mutação. 

Funciona mais ou menos da seguinte forma:

• gera um número aleatório;

• verifica se o número aleatório é menor do que a taxa de mutação;

• se sim, adiciona um gene aleatório;

• se não, mantém o gene atual.

Exemplo:

import random
##
def muta_genes(self, taxa_de_mutacao):

    for i in range(self.genes):

        numero_aleatorio = random.random()

        if numero_aleatorio < taxa_de_mutacao:
            self.genes[i] = self.__gera_gene_aleatorio()

Seleção

Os seguintes passos devem ser executados para a seleção e criação de uma nova geração.

1. Calculo do fitness

São calculados os fitness de cada elemento. O valor do fitness deve ser definido conforme o objetivo do algoritmo. 

Por exemplo, caso o objetivo do algoritmo seja formar uma determinada frase a partir de letras aleatórias, o fitness pode ser a quantidade de letras corretas.

Exemplo:

for elemento in self.elementos:
    elemento.calcula_fitness(target)

##

def calcula_fitness(self, target):

    self.fitness = 0

    

    for index in range(len(self.genes)):

        if self.genes[index] == target[index]:

            self.fitness += 1

    self.fitness = self.fitness / len(self.genes) # faz com que o fitness fique entre 0 e 1

2. Geração da lista de pais

É gerada uma lista de "pais", onde os elementos com maior fitness estão mais presentes e os com menor fitness estão menos presentes. 

Existem várias formas de gerar essa lista. Uma delas é calcular a quantidade de vezes que um elemento será inserido considerando o fitness dele em relação ao maior fitness da população. 

Imagine que o melhor elemento da população tenha um fitness de 10, enquanto um outro elemento qualquer tenha um fitness de 5. Isso significa que o melhor elemento tem duas vezes mais chances de ser obtido da lista do que esse outro elemento qualquer.

Exemplo:
maior_fitness = max(elemento.fitness for elemento in self.populacao)

lista_pais = []

for elemento in self.populacao:
    numero_de_vezes = int(elemento.fitness * 10 / maior_fitness)
    lista_pais += [elemento] * numero_de_vezes

3. A lista da população é limpa

Para a mudança de geração, é preciso esvaziar a lista contendo a população atual. Como já guardamos os elementos da geração anterior na lista_pais, não tem problema esvaziar essa lista.

self.populacao = []

4. Iteração para população da nova geração

Agora que a lista de população está vazia, precisamos preenche-la com os novos elementos. Para isso, é criado um loop até que o número de elementos na lista esteja de acordo com o tamanho da população especificado.

for i in range(tamanho_da_populacao):

4.1. Obtenção dos pais

São obtidos dois elementos da lista de pais considerando um número gerado aleatoriamente. Como os elementos com maior fitness estão mais presentes na lista, eles tem maior probabilidade de serem obtidos do que os com menor fitness.

Exemplo:

index_aleatorio = random.randrange(0, len(lista_pais))
pai1 = lista_pais[index_aleatorio]

index_aleatorio = random.randrange(0, len(lista_pais))
pai2 = lista_pais[index_aleatorio]

4.2. Geração do filho

É gerado um elemento filho fazendo a mistura de genes dos elementos pai, conforme descrito na sessão Hereditariedade.

Exemplo:

genes_filho = pai1.crossover(pai2)
filho = Element()
filho.genes = genes_filho

4.3. O filho sofre mutação

Os genes do elemento filho sofrem mutação de acordo com a taxa de mutação, conforme descrito na sessão Mutação.

Exemplo:

filho.muta_genes(taxa_de_mutacao)

4.4. O elemento filho é adicionado à lista da população da próxima geração

self.populacao += [filho]

Conclusão

O algoritmo genético é um dos mais simples quando o assunto é machine learning, mas pode trazer ótimos resultados para situações repetitivas ou quando combinado com algum outro algoritmo (como redes neurais, por exemplo).