Uma breve introdução aos algoritmos genéticos
Nota: uma versão em inglês deste artigo pode ser encontrada em “A brief introduction to Genetic Algorithms”
Um algoritmo genético é uma metaheurística inspirada pelo processo de seleção natural, pertencente à uma grande classe de algoritmos evolucionários. Eles funcionam bem para problemas de otimização e busca.
Assim como a seleção natural de Darwin diz:
Indivíduos cujo traços são adequados para sobreviver à luta por recursos locais, devem a contribuir em mais decendentes na próxima geração. Por causa disso, traços úteis tendem à serem mais comuns e a população se torna mais adaptada ao ambiente.
Nos algoritmos genéticos, esses traços podem ser medidos por uma pontuação de fitness. Ela basicamente mede o quão perto uma população está de chegar ao seu objetivo. Quanto mais perto, melhor.
Conceitos como Crossing over e Mutação são relevantes para a geração de indivíduos da população. Com o Crossing over, garantimos que os genes do indivíduos mais adaptados permaneçam na população, e a Mutação bloqueia a estagnação antes de atingir o objetivo.
Vamos ver como isso funciona na prática:
Macaco infinito
Existe um teorema chamado de Macaco Infinito. Ele diz que um número ilimitado de macacos deve, eventualmente, escrever um texto como Hamlet de Shakespeare, disponibilizadas máquinas e tempo suficiente. Podemos modelar ele como um algoritmo genético.
Como os possíveis genes, utilizamos os caracteres do alfabeto, números e sinais de pontuação.
Como o alvo, vamos utilizar um trecho de um livro famoso:
Eu não sou propriamente um autor defunto, mas um defunto autor.
Você pode ver o código aqui ou clicando no link no final do post.
Inicialização e pontuação de Fitness
Primeiramente, vamos precisar de uma população inicial. Ela será gerada aleatoriamente, selecionando os genes definidos, e a pontuação de fitness será calculada para cada indivíduo.
No algoritmo, queremos gerar um texto. A pontuação de fitness pode ser modelada como a diferença entre os caracteres:
Seleção
Como dito antes, os indivíduos com traços bons devem contribuir mais com decendentes. Para isso, ordenamos de acordo com a pontuação de fitness.
A parte menos adaptada não deve deixar decendentes e seus genes devem sumir.
Crossing Over e Mutação
Com os pais selecionados, a fase de crossing over pode começar. Iremos selecionar os genes aleatoriamente de algum dos pais. Além disso, uma taxa de mutação é aplicada, gerando genes aleatórios, quando devido.
Exceto a inicialização, todas as fases vão ocorrer nas gerações seguintes. A população de uma geração é o retorno da geração passada.
Vamos rodar o programa🤞
Funciona! 🎉 🎉
Algoritmos genéticos em Redes Neurais? Bem-vindo NEAT
E se pudéssemos aplicar o conceito em Redes Neurais? Isso é exatamente o que o algoritmo NEAT (Neuroevolution of Augmenting Topologies) faz. Em vez de usar redes de tamanho fixo, ele evolui o modelo para se adequar.
Chamamos de genótipo a coleção de genes de uma Rede Neural. Ela pode ter genes nó ou genes de conexão. Eventualmente, o genótipo será mapeado para um fenótipo, que é a representação física da rede.
Nós de entrada e saída não evoluem. Nós ocultos podem ser adicionados ou removidos. A conexão carrega a informação de onde parte e para onde vai, o peso e uma marca histórica.
Competing Conventions e a marca histórica
Quando combinamos 2 genótipos, existe um problema: isso pode resultar em redes piores, especialmente quando o crossing over é feito sem nenhuma regra. Isso é chamado de Competing Conventions.
Para evitar isso, a marca histórica foi introduzida. Com ela, podemos alinhar os genes compatíveis, assim como ocorre na biologia, gerando melhores resultados.
IA de jogo com NEAT 🕹
Existe uma biblioteca Python chamada de neat-python que implementa o algoritmo. Usando com o retro, é possível treinar uma IA e jogar um jogo
Eu treinei um modelo para passar uma fase do jogo Sonic the Hedgehog 2. Você pode ver o código aqui ou clicando no link do GitHub.
Como você pode notar, ele não faz muita coisa em gerações iniciais. Depois de algumas gerações (no meu caso, 7) o resultado é o seguinte:
Resumindo
Algoritmos genéticos são uma classe de algoritmos evolucionários, inspirados pela seleção natural de Darwin. Funcionam bem para problemas de otimização e busca.
A base do funcionamento se deve aos conceitos biológicos, como o crossing over e a mutação. Além disso, uma pontuação chamada de fitness é usada para ver o quão adaptada está a população.
O algoritmo NEAT é uma aplicação de algoritmos genéticos em redes neurais. Seu funcionamento se baseia na evolução dos genes, os quais são parte da rede.
