Observando o processo de evolução de carros com algoritmo genético

• Programa de simulação da evolução de carros usando algoritmo genético

  • O objetivo é fazer formas aleatórias de 2 rodas evoluírem para carros ao longo de gerações usando algoritmo genético
  • É baseado no BoxCar2D, mas foi reescrito do zero, usando apenas o mesmo motor de física (box2d)
  • Usa a biblioteca seedrandom.js de David Bau

• Controles e configurações

  • Há uma função Save/Restore Population que permite salvar e restaurar localmente a população atual
  • O toggle Surprise permite desligar e ligar o desenho para acelerar a simulação
  • New Population reinicia apenas a população de carros, mantendo a pista
  • A mesma seed sempre gera a mesma pista, permitindo competir com amigos
  • Mutation rate é a probabilidade de cada gene de cada indivíduo sofrer mutação para um valor aleatório quando uma nova geração nasce
  • Mutation size é o intervalo em que cada gene pode sofrer mutação; quanto menor o número, mais próximo do valor original
  • Elite clones significa os n melhores carros que serão copiados para a próxima geração
  • View top replay pausa a simulação atual e mostra o carro de melhor desempenho

• Gráfico

  • Vermelho: melhor pontuação de cada geração
  • Verde: média dos 10 melhores carros de cada geração
  • Azul: média geral de todas as gerações

• Composição do genoma

  • Forma (1 por vértice, total de 8 genes)
  • Tamanho da roda (1 por roda, total de 2 genes)
  • Posição da roda (1 por roda, total de 2 genes)
  • Densidade da roda (1 por roda, total de 2 genes) - quanto mais escuro, maior a densidade
  • Densidade do chassi (1 gene) - quanto mais escuro, maior a densidade

• Observações adicionais

  • Como a simulação não é determinística, o melhor carro pode não apresentar desempenho consistente
  • A complexidade do terreno aumenta conforme a distância
  • Agora o código está disponível no GitHub com contribuições da comunidade

[GN⁺]

Comentários do Hacker News

Em resumo:

• Este projeto foi criado há 20 anos e, graças ao Ruffle, ainda pode ser executado no navegador
• Pela natureza dos algoritmos genéticos, quando um design superior aparece em certo momento, ele tende a continuar dominante nas gerações seguintes. Pode ser necessário ajustar as configurações da taxa e da magnitude de mutação
• Há um pequeno bug após 280 m: não existe mais estrada, então os carros caem em um poço sem fim
• É possível passar rapidamente por várias gerações clicando no botão "Surprise". É interessante observar o processo de evolução ao longo do tempo enquanto se ajustam a taxa e a magnitude de mutação
• Seria interessante se o veículo tivesse um gene de "compliance", permitindo implementar suspensão. Na maioria das execuções, há uma tendência de convergir para um formato parecido com a moto de Tron
• O terreno não muda mesmo quando a geração muda
• Já foi apresentado várias vezes em discussões anteriores no HN (boxcar2d é semelhante, mas implementado sem Flash)
• Isso traz de volta lembranças de passar horas brincando com Boxcar 2D quando era criança
• Fico curioso se algo assim seria possível também em um ambiente de simulação baseado em física 3D. Seria interessante saber se algoritmos genéticos poderiam ser usados para descobrir novas formas aerodinâmicas, como drones, em simulações