🧬 Genetischer Algorithmus — Evolution

Ein genetischer Algorithmus ist eine Such- und Optimierungstechnik, die die natürliche Selektion nachahmt. Er hält eine Population von Kandidatenlösungen vor, bewertet jede mit einer Fitnessfunktion und kreuzt wiederholt die besten Leistungsträger mittels Crossover und Mutation. Über viele Generationen konvergiert die Population tendenziell zu Lösungen mit hoher Fitness.

Er entwickelt einen zufälligen Buchstabenstring hin zu einer Zielphrase, standardmäßig METHINKS IT IS LIKE A WEASEL. Die Fitness ist einfach der Anteil der Zeichenpositionen, die mit dem Ziel übereinstimmen. Dies rekonstruiert Richard Dawkins' berühmtes Weasel-Programm, das zeigt, wie kumulative Selektion ein Ziel weit schneller erreicht als blindes zufälliges Mischen.

Die Rastrigin-Funktion ist ein Standard-Testfall für Optimierung, definiert über ein 2D-Gitter von minus fünf bis fünf auf jeder Achse. Sie hat ein einziges globales Optimum im Ursprung, umgeben von vielen trügerischen lokalen Optima in einem regelmäßigen Gitter. Ihre buckelige Oberfläche macht sie zu einem harten Prüfstein dafür, wie eine Population Fallen vermeidet.

Um einen Elternteil auszuwählen, wählt der Algorithmus fünf zufällige Individuen aus der Population und behält das mit der höchsten Fitness. Die Wiederholung dieses Vorgangs bevorzugt fittere Individuen, gibt aber schwächeren gelegentlich eine Chance, was die Diversität erhält. Der Selektionsdruck steigt mit der Turniergröße, die hier fest auf fünf gesetzt ist.

Crossover kombiniert zwei Eltern zu einem Kind. Im String-Modus wird ein einzelner zufälliger Schnittpunkt verwendet, der den Anfang von einem Elternteil und den Rest vom anderen übernimmt. Mutation ersetzt dann zufällig Zeichen mit einer Wahrscheinlichkeit, die der Mutationsrate entspricht. Im Landschaftsmodus ist das Kind eine gewichtete Mischung der Elternkoordinaten plus ein kleiner zufälliger Jitter, skaliert mit der Mutationsrate.

Die Mutationsrate, einstellbar von 1 bis 30 Prozent, legt fest, wie oft jedes Gen bei der Erzeugung von Nachkommen zufällig verändert wird. Niedrige Raten lassen die Population schnell konvergieren, riskieren aber, in einem lokalen Optimum steckenzubleiben. Hohe Raten bringen mehr Vielfalt und helfen, Fallen zu entkommen, aber zu viel Mutation macht die Suche zu einem ineffizienten Zufallslauf.

Das nennt man Elitismus. Die beiden Individuen mit der höchsten Fitness werden direkt und ohne Crossover oder Mutation in die nächste Generation kopiert. Elitismus garantiert, dass die bisher beste gefundene Lösung nie verloren geht, sodass die Kurve der besten Fitness nie sinkt. Die restlichen Plätze werden durch Selektion, Crossover und Mutation gefüllt.

Im String-Modus wird die Diversität als durchschnittliche Anzahl unterschiedlicher Zeichen gemessen, die an jeder Position über die gesamte Population erscheinen. Hohe Diversität zu Beginn bedeutet, dass die Population noch breit exploriert; wenn sie sich dem Ziel annähert, sinkt die Diversität gegen eins, was zeigt, dass die meisten Individuen nun dieselben Buchstaben teilen.

Es ist ein getreues Modell des Kernmechanismus — Selektion, die auf vererbbarer Variation wirkt —, aber bewusst vereinfacht. Die reale Evolution hat kein festes Ziel, keine globale Fitnessfunktion und weit reichhaltigere Genetik. Die Weasel-Aufgabe ist insbesondere eine didaktische Illustration kumulativer Selektion, keine Aussage darüber, wie Organismen sich entwickeln.

Sie werden überall dort eingesetzt, wo der Suchraum riesig und Gradienten nicht verfügbar oder unzuverlässig sind, etwa bei Flugzeug- und Antennendesign, Fabrik- und Stundenplanung, Schaltkreis-Layout, Hyperparameter-Tuning im maschinellen Lernen und der Optimierung von Finanzstrategien. Die NASA hat berühmt gewordene, evolvierte Antennendesigns für Raumsonden mit unkonventionellen, aber hochwirksamen Formen verwendet.