Observando a evolução de carros com algoritmo genético
(rednuht.org)- Uma simulação em HTML5 que permite ver no navegador como formas aleatórias de dois pneus são selecionadas e sofrem mutações ao longo das gerações para se tornarem carros que vão cada vez mais longe
- Segue de forma livre a ideia do BoxCar2D, mas o código foi reescrito do zero e usa box2d para os cálculos de física
- É possível ajustar taxa de mutação, tamanho da mutação, condições do chão, gravidade e a quantidade de clones de elite para mudar as condições da evolução
- É possível criar a mesma pista com a mesma seed, facilitando a comparação de resultados, mas a simulação em si não é totalmente determinística
- O genoma inclui forma, posição e densidade da carroceria e das rodas, e como o terreno fica mais complexo quanto mais longe se vai, apenas o recorde máximo não garante estabilidade
Como os carros evoluem
- O programa é uma simulação simples de algoritmo genético que evolui, geração após geração, formas aleatórias de dois pneus para criar indivíduos que se movem como carros
- A ideia foi inspirada livremente em BoxCar2D, mas o código foi escrito do zero
- O motor de física usado é o box2d
- seedrandom.js foi escrito por David Bau
Controles e configurações da evolução
- Os recursos de salvar e restaurar permitem continuar um experimento depois
- Save Population salva localmente a população atual
- Restore Saved Population restaura uma população salva anteriormente
- Também é possível alterar diretamente a forma como a simulação avança
- Suprise alterna o desenho na tela para acelerar a simulação
- New Population reinicia toda a população de carros mantendo a pista gerada
- View top replay pausa a simulação atual e mostra o carro de melhor desempenho; ao clicar novamente, a simulação continua
- Create new world with seed permite competir com outras pessoas usando a mesma seed, já que a mesma seed sempre gera a mesma pista
- Os parâmetros de evolução determinam o quanto a nova geração muda
- Mutation rate é a probabilidade de cada gene de cada indivíduo sofrer uma mutação para um valor aleatório quando a nova geração nasce
- Mutation size é o intervalo em que cada gene pode variar ao sofrer mutação; quanto menor o valor, mais próximo ele fica do valor original
- Elite clones define quantos dos melhores carros serão copiados diretamente para a próxima geração
Mudança de desempenho no gráfico
- As cores do gráfico mostram o desempenho de cada geração com critérios diferentes
- vermelho indica a maior pontuação de cada geração
- verde indica a média dos 10 melhores carros de cada geração
- azul indica a média de toda a geração
Estrutura do carro representada pelo genoma
- O genoma do carro é dividido em vários genes que compõem a carroceria e as rodas
- Shape: 1 gene por vértice, total de 8 genes
- Wheel size: 1 gene por roda, total de 2 genes
- Wheel position: 1 gene por roda, total de 2 genes
- Wheel density: 1 gene por roda, total de 2 genes; rodas mais escuras indicam maior densidade
- Chassis density: 1 gene; carroceria mais escura indica maior densidade
Limitações e código aberto
- A simulação não é tão determinística quanto se esperaria, então o melhor carro pode não repetir o mesmo desempenho de antes
- O terreno fica mais complexo à medida que a distância aumenta
- Como não há uma checagem separada para o carregamento dos scripts, se algo funcionar de forma estranha, é preciso recarregar a página
- O código está disponível no GitHub repository e pode receber contribuições
- O projeto foi criado originalmente em rednuht.org e depois contou com contribuições de colaboradores no GitHub
1 comentários
Opiniões no Hacker News
Criei isto pela primeira vez há quase 20 anos, e fico feliz em ver que ainda aparece por aqui de vez em quando
Graças ao Ruffle, ainda roda no navegador:
https://peteshadbolt.co.uk/posts/ga/
O site é realmente incrível. Sempre que aparece, acabo ficando tempo demais preso nele
Eu e um amigo deixávamos rodando durante o horário de almoço e voltávamos para ver quem tinha vencido
Parece que um projeto sempre dá sorte, tem sucesso e depois domina a cada geração, enquanto as mutações seguintes caem em um beco sem saída e nem chegam perto de funcionar direito
Mesmo depois de centenas de gerações, os 10 melhores continuam os mesmos, por exemplo. Talvez seja uma característica dos algoritmos genéticos. Pode ser um caso de encontrar rapidamente uma solução razoavelmente boa e depois ficar preso em um máximo local, ou talvez seja preciso ajustar mais a probabilidade de mutação e o tamanho das mutações
Uma probabilidade alta de mutação chega rápido a um ótimo local, mas dificulta sair dele; uma probabilidade baixa exige muito mais gerações, mas normalmente leva a uma adaptação melhor
Em heurísticas genéticas, esse é um método muito ruim exatamente por causar esse fenômeno
Mas, por enquanto, a potência e a velocidade não mudam, e depois de algumas gerações parece que só o formato muda um pouquinho. Descendo a página, há uma descrição do genoma: 8 genes de formato, 2 de tamanho das rodas, 2 de posição das rodas, 2 de densidade das rodas e 1 de densidade da carroceria. No fim, ele converge para duas rodas e um formato de carroceria mediano, e depois parece não haver grande progresso. Seria interessante incluir também potência e velocidade como elementos sujeitos a mutação
É divertido. Mas o controle de velocidade não é muito intuitivo. Ao clicar em "Surprise", ele acelera e permite passar rapidamente por várias iterações
A probabilidade de mutação, isto é, a chance de g mudar, e o tamanho da mutação Δg são hiperparâmetros bons de ajustar enquanto se observa a população evoluir ao longo do tempo. Seria interessante haver um gene de "compliance" para que o carro desenvolvesse algum tipo de suspensão. Na maioria das execuções que testei, quase todos evoluíram para algo parecido com motos do Tron
Um deles tinha uma roda grande com uma roda pequena presa a ela, e ia quicando por cima de todos os obstáculos
Discussões antigas:
https://news.ycombinator.com/item?id=5942757 (664 points | Jun 2013 | 169 comments)
https://news.ycombinator.com/item?id=10600486 (162 points | Nov 2015 | 57 comments)
É o boxcar2d sem Flash
https://news.ycombinator.com/item?id=2196747
A simulação física claramente parece usar colisões inelásticas, o que é bastante irrealista, e por isso muitos carros que parecem bons o suficiente não conseguem completar o percurso. O coeficiente de atrito também parece muito baixo. A maioria dos carros que criei nem conseguiu subir uma rampa de duas seções
https://web.archive.org/web/20240428203838/http://boxcar2d.c...
Há um pequeno bug. Depois de cerca de 280 m, não há mais estrada, então todos os carros caem em um poço sem fim
Está escrito que ele “evolui uma forma aleatória de duas rodas para um carro ao longo de várias gerações”, mas, onde eu moro, chamamos carro de duas rodas de motocicleta
Ainda assim, a simulação é muito legal!
Por isso, como um carro tradicional de quatro rodas, ele não tomba mesmo quando a velocidade é 0. Acho que só essa propriedade já faz seu comportamento ficar mais próximo de um carro de quatro rodas do que de uma motocicleta
Gosto por ser uma visualização muito visual e divertida
Foi isso que me levou a experimentar algoritmos genéticos em "Self-parking car evolution":
https://trekhleb.dev/self-parking-car-evolution/
Isso me lembra um ótimo app Android chamado Cell Lab. Nele, era possível criar organismos multicelulares ou unicelulares para viver em uma placa de Petri
Se quisesse, você também podia aumentar o nível de radiação para provocar mutações e evolução
Se você gosta desse tipo de coisa, venha para https://old.reddit.com/r/WatchMachinesLearn/