Beobachtung der Evolution von Autos mithilfe genetischer Algorithmen

• Eine HTML5-Simulation, in der man im Browser beobachten kann, wie zufällig erzeugte zweirädrige Formen über Generationen hinweg ausgewählt und mutiert werden, bis sie als Autos weiter fahren
• Folgt lose der Idee von BoxCar2D, der Code wurde jedoch neu geschrieben; für die Physikberechnungen wird box2d verwendet
• Evolutionsbedingungen lassen sich ändern, indem Mutationsrate, Mutationsgröße, Bodenbedingungen, Schwerkraft und die Anzahl der Elite-Klone angepasst werden
• Mit demselben Seed lässt sich dieselbe Strecke erzeugen, was Vergleiche erleichtert; die Simulation selbst ist jedoch nicht vollständig deterministisch
• Das Genom enthält Form, Position und Dichte von Karosserie und Rädern; je weiter das Auto kommt, desto komplexer wird das Terrain, sodass ein bloßer Bestwert Stabilität nur schwer garantiert

---

Wie Autos evolvieren

• Das Programm ist eine einfache Simulation eines genetischen Algorithmus, der zufällige zweirädrige Formen über Generationen hinweg evolvieren lässt und so Individuen hervorbringt, die wie Autos fahren
• Die Idee ist lose von BoxCar2D inspiriert, der Code wurde jedoch von Grund auf neu geschrieben
• Als Physik-Engine kommt box2d zum Einsatz
• seedrandom.js wurde von David Bau geschrieben

Steuerung und Evolutionseinstellungen

• Mit Speicher- und Wiederherstellungsfunktionen lässt sich der Zustand eines Experiments fortsetzen
  • Save Population speichert die aktuelle Population lokal
  • Restore Saved Population stellt eine zuvor gespeicherte Population wieder her
• Auch die Art, wie die Simulation abläuft, kann direkt geändert werden
  • Suprise schaltet das Zeichnen um und macht die Simulation schneller
  • New Population startet die gesamte Autopopulation neu, während die erzeugte Strecke erhalten bleibt
  • View top replay pausiert die aktuelle Simulation und zeigt das leistungsstärkste Auto; ein weiterer Klick setzt die Simulation fort
• Create new world with seed erzeugt bei gleichem Seed immer dieselbe Strecke, sodass man mit anderen auf Basis desselben Seeds konkurrieren kann
• Die Evolutionsparameter bestimmen, wie stark sich eine neue Generation verändert
  • Mutation rate ist die Wahrscheinlichkeit, mit der jedes Gen jedes Individuums beim Entstehen einer neuen Generation zu einem zufälligen Wert mutiert
  • Mutation size ist der Bereich, in dem ein Gen mutieren kann; niedrigere Werte bleiben näher am ursprünglichen Wert
  • Elite clones legt die Anzahl der besten n Autos fest, die unverändert in die nächste Generation kopiert werden

Leistungsentwicklung im Diagramm

• Die Farben im Diagramm zeigen die Leistung je Generation nach unterschiedlichen Kriterien
  • Rot steht für die höchste Punktzahl jeder Generation
  • Grün steht für den Durchschnitt der 10 besten Autos jeder Generation
  • Blau steht für den Durchschnitt der gesamten Generation

Fahrzeugstruktur, die das Genom beschreibt

• Das Genom eines Autos ist in mehrere Gene unterteilt, die Karosserie und Räder bilden
  • Shape: 1 Gen pro Scheitelpunkt, insgesamt 8 Gene
  • Wheel size: 1 Gen pro Rad, insgesamt 2 Gene
  • Wheel position: 1 Gen pro Rad, insgesamt 2 Gene
  • Wheel density: 1 Gen pro Rad, insgesamt 2 Gene; dunklere Räder bedeuten eine höhere Dichte
  • Chassis density: 1 Gen; eine dunklere Karosserie bedeutet eine höhere Dichte

Grenzen und Veröffentlichung des Codes

• Die Simulation ist nicht so deterministisch wie erwartet, daher kann es sein, dass das beste Auto nicht dieselbe Leistung wie zuvor erzielt
• Das Terrain wird mit zunehmender Entfernung komplexer
• Da das Laden der Skripte nicht separat überprüft wird, sollte die Seite neu geladen werden, wenn das Verhalten ungewöhnlich ist
• Der Code ist in einem GitHub repository veröffentlicht und nimmt Beiträge an
• Ursprünglich wurde er auf rednuht.org erstellt, später kamen Mitwirkende auf GitHub hinzu

[GN⁺]

Meinungen auf Hacker News

• Ich habe das ursprünglich vor fast 20 Jahren gebaut, und es freut mich, dass es hier immer noch ab und zu auftaucht.
  Dank Ruffle läuft es weiterhin im Browser:
  https://peteshadbolt.co.uk/posts/ga/

  • Ich habe damals im Adobe-Flash-Player-Team gearbeitet und erinnere mich, dass wir diesen Flash-Film als Testfall verwendet haben :)
  • Gibt es Beispielergebnisse, wenn man es ein paar Tage laufen lässt? Oder vielleicht sogar 20 Jahre lang? ;-)
  • In Firefox scheint es abzustürzen, wenn man die Option „Save Local Population“ anklickt. Hast du eine Vermutung, woran das liegen könnte?
    Die Seite ist wirklich großartig. Jedes Mal, wenn sie auftaucht, hält sie mich viel zu lange fest.
  • Was würde wohl passieren, wenn man die Kollisionserkennung nicht nur auf die Last legt, sondern auch auf Strukturen oder Federn ausweitet?
  • Unter den Zeitfressern im Internet gehört das Original für mich zu den einprägsamsten.
    Ein Freund und ich ließen es während der Mittagspause laufen und schauten danach, wer gewonnen hatte.

• Es scheint immer so zu laufen, dass ein Design mit etwas Glück erfolgreich ist und dann über Generationen hinweg dominiert, während spätere Mutationen in einer Sackgasse landen und nicht einmal annähernd funktionsfähig werden.
  Selbst nach Hunderten Generationen ändern sich die Top 10 nicht. Vielleicht liegt das in der Natur genetischer Algorithmen. Es könnte sein, dass sie recht schnell eine ziemlich gute Lösung finden und dann in einem lokalen Maximum stecken bleiben; vielleicht müsste man auch die Mutationswahrscheinlichkeit und die Mutationsstärke weiter anpassen.

  • Im Allgemeinen ist es besser, die Mutationswahrscheinlichkeit sehr niedrig zu halten, damit sich die Population mit der Zeit langsam verändert.
    Eine hohe Mutationswahrscheinlichkeit erreicht lokale Optima schnell, kommt dort aber schwer wieder heraus; eine niedrige Mutationswahrscheinlichkeit braucht deutlich mehr Generationen, führt aber meist zu besserer Anpassung.
  • Das klingt, als würde es mit nur einem einzigen Elite-Klonindividuum laufen.
    Bei genetischen Heuristiken ist das genau wegen dieses Effekts ein sehr schlechter Ansatz.
  • Es müssten wohl mehr Faktoren variieren als nur die Form. Ein langsameres Auto mit stärkerem Antrieb würde vielleicht seltener in Rillen stecken bleiben.
    Im Moment scheinen sich Antrieb und Geschwindigkeit aber nicht zu ändern, und nach ein paar Generationen variiert nur noch die Form minimal. Weiter unten sehe ich die Beschreibung des Genoms: 8 Gene für die Form, 2 für Radgröße, 2 für Radposition, 2 für Raddichte und 1 für Karosseriedichte. Am Ende konvergiert es auf zwei Räder und eine ungefähr mittlere Karosserieform, danach scheint es keine großen Fortschritte mehr zu geben. Es wäre interessant, auch Antrieb und Geschwindigkeit als veränderliche Faktoren aufzunehmen.

• Macht Spaß. Allerdings ist die Geschwindigkeitssteuerung nicht besonders intuitiv. Wenn man „Surprise“ drückt, wird es schneller, sodass man rasch durch viele Iterationen kommt.
  Die Mutationswahrscheinlichkeit, also die Wahrscheinlichkeit, dass sich g ändert, und die Mutationsstärke Δg sind gute Hyperparameter, an denen man drehen kann, während man beobachtet, wie sich die Population über die Zeit entwickelt. Ein „compliance“-Gen, das dem Auto eine Art Federung verleiht, wäre interessant. In den meisten Läufen, die ich ausprobiert habe, entwickelten sich die Fahrzeuge fast alle zu so etwas wie Tron-Bikes.

  • Ich habe es mit sehr hoher Mutationswahrscheinlichkeit lange im Hintergrund laufen lassen und dabei kamen auch ziemlich andere Formen heraus.
    Eine Form mit einem großen Rad und einem kleinen Rad daran, die über alle Hindernisse hüpft.

• Frühere Diskussionen:
  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)

• Das ist boxcar2d ohne Flash.
  https://news.ycombinator.com/item?id=2196747

  • Außerdem scheinen seltsamerweise alle Federungsparameter zu fehlen.
    Die Physiksimulation scheint eindeutig unelastische Kollisionen zu verwenden; das ist ziemlich unrealistisch, und deshalb schaffen viele Autos, die optisch völlig brauchbar wirken, den Kurs nicht. Auch der Reibungskoeffizient sieht sehr niedrig aus. Die meisten meiner Autos kamen nicht einmal eine Steigung mit zwei Segmenten hinauf.
  • Wie sich herausstellt, funktioniert boxcar2d perfekt in Ruffle, und das Internet Archive lädt Ruffle automatisch :)
    https://web.archive.org/web/20240428203838/http://boxcar2d.c...
  • Ich dachte doch, ich hätte so etwas schon vor über zehn Jahren gesehen — offenbar stimmte das.

• Es gibt einen kleinen Bug. Nach ungefähr 280 m gibt es keine Straße mehr, sodass alle Autos in eine endlose Grube fallen.

• Es heißt: „Zufällige Zweiradformen werden über viele Generationen zu Autos weiterentwickelt“, aber dort, wo ich lebe, nennt man zweirädrige Autos Motorräder.
  Die Simulation ist trotzdem sehr cool!

  • In der Simulation, in der diese Autos fahren, gibt es keine dritte Dimension, in der das Fahrzeug umkippen könnte, und auch keinen Platz für ein weiteres Radpaar.
    Deshalb fallen sie selbst bei Geschwindigkeit 0 nicht um, wie ein klassisches vierrädriges Auto. Allein diese Eigenschaft reicht meiner Meinung nach, um ihr Verhalten eher einem vierrädrigen Auto als einem Motorrad zuzuordnen.

• Mir gefällt es sehr, weil es eine sehr visuelle und unterhaltsame Visualisierung ist.
  Dadurch bin ich dazu gekommen, mit genetischen Algorithmen in „Self-parking car evolution“ zu experimentieren:
  https://trekhleb.dev/self-parking-car-evolution/

• Das erinnert mich an eine großartige Android-App namens Cell Lab. Man konnte darin mehrzellige oder einzellige Organismen erschaffen, die in einer Petrischale leben.
  Wenn man wollte, konnte man die Strahlungsstärke erhöhen, damit Mutationen und Evolution stattfinden.

• Wenn ihr so etwas mögt, schaut bei https://old.reddit.com/r/WatchMachinesLearn/ vorbei.

  • Das Thema ist cool, aber es scheint kein besonders aktiver Subreddit zu sein. Der neueste Beitrag ist 3 Jahre alt :-/