Algoritmo Genético na prática com Python!
A gente só aprende mesmo quando põe a mão na massa.
Na primeira parte desse estudo, aprendemos como funciona a teoria de um algoritmo genético. Se você tiver caído de paraquedas nesse post e não leu a parte teórica, basta acessar o link abaixo.
Se você chegou até aqui, deve estar interessado em como ver como funciona a evolução artificial na prática. Vamos nessa?
Premissas e Limitações do Projeto
Premissas
Buscamos, através desse projeto, desenvolver um algoritmo genético de propósito geral, flexível e do zero absoluto.
Propósito geral para que o algoritmo funcione tanto para problemas de minimização e maximização;
Flexível para que o algoritmo possa ter seus parâmetros ajustáveis conforme cada aplicação, incluindo quantidade de variáveis, número de bits, etc;
Do zero absoluto, sem a utilização de frameworks ou pacotes prontos para computação genética. Essa decisão foi tomada para que tenhamos controle total do algoritmo, favorecendo o aprendizado e ajustes futuros. Dessa forma, utilizamos apenas bibliotecas básicas do Python:
- Numpy: operações matriciais, similar ao que faz o MatLab;
- Random: geração de números aleatórios;
- Matplotlib: gráficos;
- Math: utilizamos operações trigonométricas em algumas funções de teste.
Limitações
Como o principal objetivo do projeto é de cunho didático, há espaço para otimizações no código, visando ganho de performance computacional. O desempenho não foi o foco do projeto nesse primeiro momento, mas estamos abertos a sugestões de melhoria e colaborações.
Não implementamos todas as variações dos algoritmos genéticos. Existem diversas formas de fazer seleções, cruzamentos e mutações. Fizemos o básico, arroz com feijão, para fins didáticos. Novamente, estamos abertos a colaborações para fortalecimento do algoritmo.
Finalmente, desenvolvemos o algoritmo apenas para funções de otimização irrestritas. Um passo de cada vez :)
Partes e peças do nosso algoritmo genético
Funções Básicas e Auxiliares
No primeiro trecho do código, desenvolvemos um grupo de funções básicas, responsáveis pelos processos de criação dos intervalos das variáveis e conversão entre binários e decimais.
Ao receber do usuário os intervalos e seus respectivos números de bits, são criados dois dicionários. Estes são utilizados para a conversão entre números decimal e binário e vice-versa. Os dicionários possuem os números binários em strings como chaves.
As demais funções desse grupo também fazem parte do processo de conversão, mas recebem arrays em suas entradas e fazem as transformações para strings e vice-versa. Implementamos também funções auxiliares utilizadas no algoritmo genético. Essas incluem funções para transposição de matrizes, plots, etc.
População Inicial
Essa função cria um array com a seguinte configuração:
população_por_variavel = [[indivíduos_variavel_1], [indivíduos_variavel_2], […], [indiviuos_variavel_n]]
Seleção
Implementamos os seguintes métodos de seleção:
- Torneio
- Roleta
- Roleta modificada: foi aplicado um logaritmo para o “achatamento” dos resultados da função. Dessa forma, reduz-se as probabilidades de seleção de indivíduos com melhor desempenho e aumenta as chances daqueles com pior. A abordagem visa garantir a diversidade da população, fundamental para algoritmos genéticos.
Cruzamento
- Cruzamento em um ponto: cada cruzamento foi realizado em um ponto diferente, inclusive para uma mesma geração.
Mutação
- Mutação em um ponto: cada mutação foi realizada em um ponto diferente, inclusive para uma mesma geração.
Elitismo
- Em nossa implementação do elitismo, optamos pela variação SSGA (Steady State Genetic Algorithm).
E será que funciona? Aplicando funções de teste!
As funções de teste para algoritmos de otimização são funções que possuem tanto seu ponto ótimo quanto seus respectivos argumentos conhecidos. Isso permite com que seu código tenha sua performance validada. Em nosso repositório, implementamos várias funções. Aqui, apresentamos a performance de algumas delas:
Função Esfera
- Descrição da função:
- Performance do algoritmo:
- Tá, resultado legal…mas essa função não é fácil demais?
- Que tal vermos o comportamento do algoritmo com a função Rosenbrock com 4 variáveis?
Função Rosenbrock
- Descrição da função:
- Performance do algoritmo:
- E se tivermos uma função mais complexa ou mais variáveis?
- Vamos ver como nosso algoritmo se comporta com a função Rastringin e 10 variáveis.
Função Rastringin
- Descrição da função:
- Performance do algoritmo:
É possível perceber que, com a adição de mais variáveis, o algoritmo sofre um pouco mais para convergir. Certamente com mais recursos computacionais ou tempo disponível será possível atingir o ótimo. Acreditamos que os parâmetros do problema a ser resolvido ajudem a dar uma direção nesse sentido. Podemos concluir também que há um tradeoff entre complexidade do problema, precisão e tempo computacional.
Que tal brincar com o algoritmo?
O Evolutionary Algorithm Playground é um aplicativo da web totalmente baseado em Python que permite aos usuários realizar o ajuste de vários parâmetros e ver como algoritmos bio-inspirados (Algoritmo Genético e Otimização por Exame de Partículas) funcionam. Os algoritmos foram construídos do zero usando Numpy. O aplicativo foi desenvolvido usando Streamlit.
Finalizamos aqui os nossos estudos sobre algoritmos genéticos. Esperamos ter fornecido uma introdução interessante sobre o assunto e que tenha sido divertido, porque do lado de cá foi bastante!
Se você tiver interesse em brincar com nosso algoritmo e contribuir com seu desenvolvimento, comece pelo repositório no Github:
Caso você tenha algum problema de otimização que queira resolver, dúvidas e contribuições, não hesite em me procurar. Até logo!
Veja meus outros posts aqui no Medium sobre Redes Neurais, Machine Learning e tudo aquilo que gira em torno do universo da Inteligência Artificial:
