Aprendizado Evolutivo
Uma jornada pelos Algoritmos Genéticos
Introdução
O que você sabe sobre �evolução biológica�dos seres vivos?
Evolução Biológica
A evolução biológica indica que as espécies dos seres vivos mudam ao longo do tempo.
E se uma mudança ajudar na sobrevivência, então se torna mais comum na espécie.
Evolução Biológica
O que é a teoria da evolução de Charles Darwin e o que inspirou suas ideias revolucionárias
Evolução Biológica
Evolução Artificial na IA
A computação buscou
inspiração na evolução biológica para
solucionar problemas usando Algoritmos Genéticos!�
Computação Bioinspirada
Evolução Artificial
Seu funcionamento para um problema é simples:
Algoritmo Genético
Exemplo
Vários pacotes com pesos diferentes e valores diferentes precisam ser colocados em um caminhão que tem um limite de peso que pode transportar. Quais pacotes escolher para ter o maior valor transportado?
Algoritmo Genético
Cada solução poderia ser uma lista de pacotes escolhidos:� {A, C, F, G} com 1000kg e R$21mil
{B, C, G, P, T} com 1050kg e R$25mil
{D, F, G, T} com 950kg e R$20mil
Algoritmo Genético
Se a capacidade do caminhão é de 1000kg então só podemos aceitar estas soluções� {A, C, F, G} com 1000kg e R$21mil
{D, F, G, T} com 950kg e R$20mil
que poderiam ter pequenas mudanças (trocar um pacote) para tentar buscar uma solução melhor.
Algoritmo Genético
E é assim que funciona um algoritmo genético!
Uma população de soluções é gerada,
depois avaliada para selecionar as melhores,
que irão gerar novas soluções…
Algoritmo Genético
Algoritmo Genético
Este é um algoritmo de Inteligência Artificial que tem sido usado para resolver muitos problemas:
Selecionar pacotes para transporte, definir rotas entre pontos geográficos, otimizar linhas de produção de uma fábrica, otimizar investimentos financeiros…
Algoritmo Genético
Encontrar rotas entre cidades, saindo de uma cidade, passando por todas cidades e voltando para a cidade inicial.
Vamos formar equipes de 3 a 5 alunos.
Vamos tentar resolver um problema!
Marque cinco pontos em uma folha de papel, indicando local de cidades. Faça uma rota partindo de uma cidade, passando por todas demais cidades e voltando para a primeira.
Não pode repetir cidade.
Vamos tentar resolver um problema!
Use uma régua para medir a distância total da rota, somando a distância entre cidades que estão em rota.
Vamos tentar resolver um problema!
Solicite para outro colega tentar fazer outra rota (use caneta de outra cor) e meça a distância total desta outra rota.
Qual foi a rota mais curta?
Vamos tentar resolver um problema!
Qual foi a estratégia usada para escolher a rota entre as cidades?
Discussão entre grupos.
Vamos tentar resolver um problema!
Vamos tentar agora com 10 cidades?
Foi mais difícil?
Conseguiu usar a mesma estratégia?
Vamos tentar resolver um problema!
E se fossem 30 cidades?
Ou 100 cidades?
Ficaria muuuito difícil?
Algoritmos Genéticos
podem ajudar!
Vamos tentar resolver um problema!
Um algoritmo genético pode gerar uma população com várias soluções (sequências de cidades a serem visitadas em ordem).
As melhores soluções (rotas mais curtas) são selecionadas.
Algoritmo Genético
Algoritmo Genético
Vitória da Conquista
[Salvador → Vitória da Conquista → Feira de Santana → Jequié → Ilhéus]
Feira de Santana
Salvador
Ilhéus
Jequié
Algoritmo Genético
Vitória da Conquista
A rota é mais curta é selecionada.
Feira de Santana
Salvador
Ilhéus
Jequié
[Salvador → Feira de Santana → Vitória da Conquista → Jequié → Ilhéus]
Algoritmo Genético
A rota selecionada passa por uma pequena mudança e neste caso gera uma solução melhor, uma rota ainda mais curta.
Vitória da Conquista
Feira de Santana
Salvador
Ilhéus
Jequié
[Salvador → Feira de Santana → Vitória da Conquista → Ilhéus → Jequié]
As soluções (mais curtas) selecionadas podem ser recombinadas entre si (trechos de rota) e/ou ter pequenas mudanças na ordem das cidades, gerando nova população de soluções.
Isto se repete por algum tempo, e ao final teremos uma boa solução para o problema.
Algoritmo Genético
Exemplo
A baiana resolveu utilizar Algoritmo Genético para escolher os melhores combos promocionais na sua barraca combinando os seguintes itens:�
Algoritmo Genético
Cada item tem um tempo (minutos) de preparo e produz diferentes pontos de satisfação nos clientes. Os clientes não gostam de esperar muito, então cada combo precisa ficar pronto em, no máximo, 12 minutos!
Item | Tempo | Pontos |
Acarajé | 5 | 6 |
Abará | 6 | 7 |
Bolinho de Estudante | 3 | 4 |
Cocada | 2 | 3 |
Passarinha | 4 | 5 |
Algoritmo Genético
No Algoritmo Genético, cada combo é um indivíduo.
O combo abaixo demora 10 minutos para ficar pronto e tem 13 pontos.
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha |
Combo | ✅ | ❌ | ✅ | ✅ | ❌ |
Algoritmo Genético
1 - O Algoritmo Genético começa criando uma geração inicial de indivíduos (diferentes combos)
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha | Tempo | Pontos |
Combo 1 | ✅ | ❌ | ✅ | ✅ | ❌ | 10 | 13 |
Combo 2 | ❌ | ✅ | ✅ | ❌ | ✅ | 13 | ❌ |
Combo 3 | ✅ | ❌ | ❌ | ✅ | ✅ | 11 | 14 |
Combo 4 | ❌ | ❌ | ✅ | ✅ | ✅ | 9 | 12 |
Algoritmo Genético
2 - No próximo passo, 2 combos serão sorteados para a próxima geração de soluções. Indivíduos com mais pontos têm mais chance de serem selecionados.
Atenção! O Combo 2 não pode ser selecionado por estourar o tempo máximo!
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha | Tempo | Pontos |
Combo 1 | ✅ | ❌ | ✅ | ✅ | ❌ | 10 | 13 |
Combo 2 | ❌ | ✅ | ✅ | ❌ | ✅ | 13 | ❌ |
Combo 3 | ✅ | ❌ | ❌ | ✅ | ✅ | 11 | 14 |
Combo 4 | ❌ | ❌ | ✅ | ✅ | ✅ | 9 | 12 |
Algoritmo Genético
3 - Supondo que os Combos 1 e 3 tenham sido selecionados, o próximo passo é gerar filhos combinando as características (genes) dos pais!
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha |
Combo 1 | ✅ | ❌ | ✅ | ✅ | ❌ |
Combo 3 | ✅ | ❌ | ❌ | ✅ | ✅ |
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha |
Combo 5 | ✅ | ❌ | ✅ | ✅ | ✅ |
Combo 6 | ✅ | ❌ | ❌ | ✅ | ❌ |
Pais
Filhos
Algoritmo Genético
4 - Alguns genes podem sofrer mutações. Por exemplo, a cocada será removida do Combo 5!
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha |
Combo 1 | ✅ | ❌ | ✅ | ✅ | ❌ |
Combo 3 | ✅ | ❌ | ❌ | ✅ | ✅ |
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha |
Combo 5 | ✅ | ❌ | ✅ | ❌ | ✅ |
Combo 6 | ✅ | ❌ | ❌ | ✅ | ❌ |
Algoritmo Genético
5 - Uma nova geração é formada com esses combos!
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha | Tempo | Pontos |
Combo 1 | ✅ | ❌ | ✅ | ✅ | ❌ | 10 | 13 |
Combo 3 | ✅ | ❌ | ❌ | ✅ | ✅ | 11 | 14 |
Combo 5 | ✅ | ❌ | ✅ | ❌ | ✅ | 12 | 15 |
Combo 6 | ✅ | ❌ | ❌ | ✅ | ❌ | 7 | 9 |
Algoritmo Genético
Esse processo pode ser repetido por várias gerações!
No nosso exemplo, finalizando na 2a geração, a melhor solução é o Combo 5!
Opções | Acarajé | Abará | Bolinho de estudante | Cocada | Passarinha | Tempo | Pontos |
Combo 1 | ✅ | ❌ | ✅ | ✅ | ❌ | 10 | 13 |
Combo 3 | ✅ | ❌ | ❌ | ✅ | ✅ | 11 | 14 |
Combo 5 | ✅ | ❌ | ✅ | ❌ | ✅ | 12 | 15 |
Combo 6 | ✅ | ❌ | ❌ | ✅ | ❌ | 7 | 9 |
Atividade e Discussão
Atividade: O vídeo a seguir mostra como Algoritmo Genético pode ajudar a controlar um carro 2D! Apesar de estar em inglês é possível revisar os conceitos abordados nesta aula!
Genetic algorithms - evolution of a 2D car in Unity https://www.youtube.com/watch?v=FKbarpAlBkw
Referências
Faceli, K., Lorena, A. C., Gama, J., Almeida, T. A. D., & Carvalho, A. C. P. D. L. F. D. (2021). Inteligência artificial: uma abordagem de aprendizado de máquina.
Computação Evolucionária parte 1/4 - Profa. Gisele Papa (UFMG) https://www.youtube.com/watch?v=lIG7Bqe1L-c&list=PLSYlxYDtRmwFacpFdNdkTTUgjool9eWdB&index=2
CASTRO, L. N. D. (2010). Computação natural–uma jornada ilustrada. São Paulo: Editora Livraria da Física.
https://brasilescola.uol.com.br/biologia/evolucao.htm
O que é a teoria da evolução de Charles Darwin e o que inspirou suas ideias revolucionárias? BBC News Brasil https://www.youtube.com/watch?v=ambANBIHjCI
37
Produção do Material
38
Apoio
Apoio
40