- Im Flug
- Ziel erreicht
- Abgestürzt
- Bester Flug der letzten Generation
- Ziel erreicht
- Abgestürzt
Spielwiese für genetische Algorithmen
Ein genetischer Algorithmus löst ein Problem so, wie die Evolution Lebewesen formt: viele zufällige Antworten ausprobieren, die besseren behalten, sie mischen, ein paar Stellen zufällig ändern und alles wiederholen. Hier sind die Antworten Raketen. Jede folgt einer Liste zufälliger Schübe und sonst nichts, und anfangs taumeln sie ziellos umher. Klicken Sie auf „Starten“ und sehen Sie zu, wie die Population sich von Generation zu Generation verbessert, bis die meisten Raketen um die Wände herum zum Ziel schwingen, ohne dass ihnen jemand sagt, wohin sie fliegen sollen. Klicken Sie auf „Starten“ und sehen Sie zu, wie eine Population von Raketen versucht, das grüne Ziel zu erreichen. Jede Rakete folgt nur ihren Genen, einer Liste kleiner Schübe, einer für jeden Moment ihres Flugs. Nach jedem Flug werden die Raketen, die dem Ziel am nächsten gekommen sind, und vor allem die, die angekommen sind, am ehesten zu Eltern der nächsten Generation; ihre Gene werden gemischt und einige zufällig verändert. „Nächste Generation“ überspringt den Rest eines Flugs. Ziehen Sie auf dem Feld, um eine Wand zu zeichnen, und klicken Sie auf eine Wand, um sie zu entfernen.
Wie es funktioniert
- Wählen Sie Hindernisse oder ziehen Sie auf dem Feld, um eigene Wände zu zeichnen, und stellen Sie Population, Mutationsrate und Lebensdauer ein.
- Klicken Sie auf „Starten“ und sehen Sie jeder Generation beim Fliegen zu; „Nächste Generation“ überspringt den Rest eines Flugs.
- Verfolgen Sie in den Kacheln und im Diagramm den Anteil, der das Ziel erreicht, und probieren Sie andere Mutationsraten und Selektionsverfahren aus.
Wie sich die Raketen entwickeln
Jede Rakete trägt Gene: einen kleinen Schub für jeden Moment ihres Flugs. Die Gene der ersten Generation sind zufällig. Nach dem Flug erhält jede Rakete eine Fitness, die für eine frühe Ankunft am höchsten ist, dann umso höher, je näher sie dem Ziel gekommen ist, und die nach einem Absturz durch zehn geteilt wird. Die Eltern der nächsten Generation werden zufällig ausgewählt, aber fittere Raketen werden mit größerer Wahrscheinlichkeit gewählt. Jedes Kind übernimmt den ersten Teil seiner Gene von einem Elternteil und den Rest vom anderen, und einige Gene werden durch zufällige Schübe ersetzt: Mutationen. Über die Generationen verbreiten und verbessern sich gute Flugpläne.
Was die Einstellungen bewirken
Eine größere Population erkundet mehr Flugpläne gleichzeitig und bleibt seltener stecken, aber jede Generation dauert länger. Die Mutationsrate wägt zwischen Erkunden und Bewahren des Bewährten ab: Ohne Mutation gehen der Population schnell die neuen Ideen aus, mit zu viel Mutation vergisst sie gute Flüge schneller, als sie sie finden kann. Die Glücksrad-Selektion wählt Eltern im Verhältnis zu ihrer Fitness, während ein Turnier die beste von drei zufälligen Raketen nimmt, was weniger davon abhängt, wie die Fitness skaliert ist. Elitismus übernimmt die beste Rakete unverändert in die nächste Generation, sodass das beste Ergebnis nie schlechter wird.
Häufig gestellte Fragen
Warum bleiben die Raketen hinter den versetzten Wänden stecken?
Ihre Fitness misst den Luftlinienabstand zum Ziel, daher schneidet eine Rakete, die in die Wand unter dem Ziel fliegt, besser ab als eine, die wegfliegt, um die Lücke zu finden. Die Population sammelt sich in dieser Sackgasse, einem lokalen Optimum. Größere Populationen, mehr Mutation oder Turnierselektion helfen ihr zu entkommen, und eine Fitness, die den tatsächlichen Weg um die Wände misst, würde die Falle vermeiden. Eine gute Fitnessfunktion zu wählen ist der schwierigste Teil beim Einsatz eines genetischen Algorithmus.
Funktioniert so die Evolution in der Natur?
In groben Zügen: Variation durch Mutation und Rekombination, Vererbung der Gene und Selektion der Fittesten sind Darwins Zutaten. Die Unterschiede sind allerdings groß. Die Natur hat kein Ziel und keine Fitnessformel, nur Überleben und Fortpflanzung, und echte Genome bauen Körper durch Entwicklung auf, statt Aktionen aufzulisten.
Wofür werden genetische Algorithmen eingesetzt?
Für Probleme mit einem riesigen Raum möglicher Antworten und einer einfachen Möglichkeit, einen Kandidaten zu bewerten: zum Formen von Antennen, Tragflächen und Autoteilen, zum Erstellen von Stundenplänen, zum Abstimmen der Einstellungen anderer Algorithmen, zum Entwerfen neuronaler Netze und zum Erzeugen von Kunst und Spielstrategien. Die evolvierte Antenne der NASA auf den ST5-Satelliten von 2006 ist ein bekanntes Beispiel.
Warum fliegt die beste Rakete in der nächsten Generation manchmal schlechter?
Ohne Elitismus wird die beste Rakete nicht kopiert: Ihre Gene überleben nur gemischt mit anderen und womöglich mutiert, sodass die nächste Generation ihren genauen Flug verlieren kann. Mit eingeschaltetem Elitismus bleibt die beste Rakete unverändert erhalten und das beste Ergebnis wird nie schlechter.
Wird etwas an einen Server gesendet?
Nein. Die Raketen fliegen und entwickeln sich in Ihrem Browser, und die Wände, die Sie zeichnen, bleiben im lokalen Speicher dieses Browsers.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Zum Editor