- Il s’agit d’une simulation HTML5 visible dans le navigateur, où des formes à deux roues générées aléatoirement sont sélectionnées et mutées au fil des générations pour devenir des voitures capables d’aller plus loin
- Le projet suit librement l’idée de BoxCar2D, mais le code a été réécrit, et les calculs physiques utilisent box2d
- Il est possible de modifier les conditions d’évolution en ajustant le taux de mutation, l’ampleur des mutations, les conditions du sol, la gravité et le nombre de clones d’élite
- On peut générer le même circuit avec la même seed, ce qui facilite la comparaison des résultats, mais la simulation elle-même n’est pas entièrement déterministe
- Le génome contient la forme, la position et la densité du châssis et des roues, et comme le terrain devient plus complexe à mesure que l’on avance, le simple record maximal ne garantit pas forcément la stabilité
Comment les voitures évoluent
- Le programme est une simulation simple d’algorithme génétique qui fait évoluer, génération après génération, des formes aléatoires à deux roues pour produire des individus capables de rouler comme des voitures
- L’idée est librement inspirée de BoxCar2D, mais le code a été écrit depuis zéro
- Le moteur physique utilisé est box2d
- seedrandom.js a été écrit par David Bau
Commandes et réglages de l’évolution
- Les fonctions d’enregistrement et de restauration permettent de reprendre l’état d’une expérience
- Save Population enregistre localement la population actuelle
- Restore Saved Population restaure une population précédemment enregistrée
- Il est aussi possible de modifier directement la manière dont la simulation s’exécute
- Suprise active ou désactive le dessin afin d’accélérer la simulation
- New Population redémarre entièrement la population de voitures tout en conservant le circuit généré
- View top replay met en pause la simulation actuelle et affiche la voiture la plus performante ; un nouveau clic relance la simulation
- Create new world with seed permet de retrouver exactement le même circuit avec la même seed, ce qui permet de se mesurer à d’autres personnes sur une seed identique
- Les paramètres d’évolution déterminent l’ampleur des changements entre les générations
- Mutation rate est la probabilité que chaque gène de chaque individu soit muté vers une valeur aléatoire à la naissance d’une nouvelle génération
- Mutation size est l’amplitude possible de variation de chaque gène ; plus la valeur est faible, plus la mutation reste proche de la valeur d’origine
- Elite clones définit le nombre des n meilleures voitures qui seront copiées telles quelles dans la génération suivante
Évolution des performances sur le graphique
- Les couleurs du graphique montrent les performances de chaque génération selon différents critères
- Rouge indique le meilleur score de chaque génération
- Vert indique la moyenne des 10 meilleures voitures de chaque génération
- Bleu indique la moyenne de l’ensemble de la génération
Structure de la voiture représentée par le génome
- Le génome de la voiture est divisé en plusieurs gènes qui définissent le châssis et les roues
- Shape: 1 gène par sommet, soit 8 gènes au total
- Wheel size: 1 gène par roue, soit 2 gènes au total
- Wheel position: 1 gène par roue, soit 2 gènes au total
- Wheel density: 1 gène par roue, soit 2 gènes au total ; des roues plus sombres indiquent une densité plus élevée
- Chassis density: 1 gène ; un châssis plus sombre indique une densité plus élevée
Limites et publication du code
- La simulation n’est pas aussi déterministe qu’espéré, si bien que la meilleure voiture peut ne pas reproduire exactement ses performances précédentes
- Le terrain devient plus complexe à mesure que la distance augmente
- Comme le chargement des scripts n’est pas vérifié séparément, si le comportement semble anormal il faut recharger la page
- Le code est disponible dans le GitHub repository et accepte des contributions
- Le projet a d’abord été créé sur rednuht.org, puis enrichi ensuite par des contributeurs sur GitHub
1 commentaires
Avis sur Hacker News
J’ai créé ça pour la première fois il y a presque 20 ans, et ça me fait plaisir de voir que ça remonte encore ici de temps en temps
Grâce à Ruffle, ça fonctionne encore dans le navigateur :
https://peteshadbolt.co.uk/posts/ga/
Le site est vraiment génial. À chaque fois qu’il remonte, j’y passe beaucoup trop de temps
Avec un ami, on le laissait tourner pendant la pause déjeuner, puis on revenait voir qui avait gagné
On dirait toujours qu’un modèle réussit par chance, puis domine à chaque génération, et que les mutations suivantes se retrouvent dans une impasse, sans même approcher un niveau fonctionnel
Même après des centaines de générations, le top 10 ne change pas, par exemple. C’est peut-être une caractéristique des algorithmes génétiques. Ils trouvent assez vite une solution plutôt correcte, puis restent bloqués dans un maximum local ; ou alors il faudrait ajuster davantage la probabilité de mutation et l’amplitude des mutations
Une probabilité de mutation élevée atteint vite un optimum local mais en sort difficilement ; une probabilité faible demande beaucoup plus de générations, mais mène généralement à une meilleure adaptation
Dans les heuristiques génétiques, c’est une très mauvaise approche précisément à cause de ce phénomène
Mais pour l’instant, la puissance et la vitesse ne changent pas, et après quelques générations seule la forme semble varier très légèrement. En descendant plus bas, on trouve la description du génome : 8 gènes pour la forme, 2 pour la taille des roues, 2 pour la position des roues, 2 pour la densité des roues, 1 pour la densité du châssis. Au final, ça converge vers deux roues et une forme de châssis moyenne, puis il ne semble plus y avoir de progrès notable. Ce serait intéressant d’ajouter aussi la puissance et la vitesse comme paramètres mutables
C’est amusant. En revanche, le réglage de la vitesse n’est pas très intuitif. En cliquant sur « Surprise », ça accélère et permet de passer rapidement plusieurs itérations
La probabilité de mutation, c’est-à-dire la probabilité que g change, et l’amplitude de mutation Δg sont de bons hyperparamètres à ajuster tout en observant l’évolution de la population au fil du temps. Ce serait intéressant d’avoir un gène de « compliance » pour que la voiture développe une sorte de suspension. Dans la plupart des essais que j’ai lancés, elles ont presque toutes évolué vers une forme de moto de Tron
Une forme avec une grande roue et une petite roue attachée, qui rebondit et franchit tous les obstacles
Anciennes discussions :
https://news.ycombinator.com/item?id=5942757 (664 points | juin 2013 | 169 commentaires)
https://news.ycombinator.com/item?id=10600486 (162 points | nov. 2015 | 57 commentaires)
C’est boxcar2d sans Flash
https://news.ycombinator.com/item?id=2196747
La simulation physique utilise manifestement des collisions inélastiques, ce qui est assez irréaliste, et c’est pourquoi beaucoup de voitures qui ont l’air suffisamment correctes n’arrivent pas à passer le parcours. Le coefficient de frottement semble aussi très faible. La plupart des voitures que j’ai créées n’ont même pas réussi à monter une pente en deux sections
https://web.archive.org/web/20240428203838/http://boxcar2d.c...
Il y a un petit bug. Après environ 280 m, il n’y a plus de route, donc toutes les voitures tombent dans un gouffre sans fin
Il est écrit « faire évoluer une forme aléatoire à deux roues en voiture sur plusieurs générations », mais là où j’habite, on appelle une voiture à deux roues une moto
Cela dit, la simulation est vraiment chouette !
Donc, comme une voiture traditionnelle à quatre roues, ils ne tombent pas même à vitesse nulle. Rien que cette propriété me fait penser que leur comportement est plus proche d’une voiture à quatre roues que d’une moto
J’aime beaucoup cette visualisation, très visuelle et amusante
Elle m’a donné envie d’expérimenter les algorithmes génétiques dans « Self-parking car evolution » :
https://trekhleb.dev/self-parking-car-evolution/
Ça me rappelle l’excellente application Android Cell Lab. On pouvait y créer des organismes multicellulaires ou unicellulaires destinés à vivre dans une boîte de Petri
Si on le voulait, on pouvait aussi augmenter le niveau de radiation pour provoquer des mutations et de l’évolution
Si vous aimez ce genre de choses, venez voir https://old.reddit.com/r/WatchMachinesLearn/