Genetische Algorithmen erklärt
Die Evolution hat Augen, Flügel und Gehirne ohne einen Konstrukteur hervorgebracht, einfach indem sie behält, was funktioniert, und es variiert. Ein genetischer Algorithmus übernimmt diese Idee, um Probleme am Computer zu lösen. Er muss das Problem nicht verstehen, sondern nur eine bessere Antwort von einer schlechteren unterscheiden können. Das macht ihn zu einem mächtigen Werkzeug, wenn der Raum möglicher Antworten zu groß und zu eigenartig ist, um ihn auf andere Weise zu durchsuchen.
Die Idee
In den 1960er- und 1970er-Jahren machte John Holland an der University of Michigan aus Darwins Theorie einen Algorithmus, beschrieben in seinem Buch „Adaptation in Natural and Artificial Systems“ von 1975. Etwa zur selben Zeit entwickelten Ingo Rechenberg und Hans-Paul Schwefel in Deutschland Evolutionsstrategien für die technische Konstruktion. Das gemeinsame Rezept: eine Population von Lösungskandidaten halten, sie bewerten, die besseren sich mit Variation fortpflanzen lassen und das über viele Generationen wiederholen.
Gene und die Population
Jeder Kandidat wird durch ein Chromosom beschrieben, eine Liste von Genen. Auf der Spielwiese sind die Gene einer Rakete ihre Schübe, einer für jeden Moment ihres Flugs; bei anderen Problemen könnten es die Bits einer Zahl, die Reihenfolge der Städte auf einer Route oder die Größen von Bauteilen in einem Entwurf sein. Die erste Generation ist zufällig, das heißt, sie erkundet den Raum der Antworten breit, enthält aber fast keine guten.
Die Fitnessfunktion
Die Fitness ist die eine Zahl, die angibt, wie gut ein Kandidat ist, und sie ist das Einzige, was der Algorithmus über das Problem weiß. Bei den Raketen belohnt sie vor allem eine frühe Ankunft, dann ein Ende nahe am Ziel, und bestraft Abstürze. Eine gut gewählte Fitnessfunktion lenkt die Suche gleichmäßig zu guten Antworten; eine unbedachte belohnt das Falsche, und der Algorithmus nutzt jedes Schlupfloch aus, das sie offen lässt.
Selektion
Die Eltern werden so gewählt, dass fittere Kandidaten mehr Nachkommen haben, schwächere aber trotzdem eine Chance bekommen, denn ihre Gene können nützliche Stücke enthalten. Die Glücksrad-Selektion gibt jedem Kandidaten ein Stück eines Rades im Verhältnis zu seiner Fitness; die Turnierselektion wählt einige zufällig aus und nimmt den besten davon. Stärkere Selektion beschleunigt den Fortschritt, macht die Population aber auch einheitlicher, was die Suche zu früh beenden kann.
Crossover und Mutation
Crossover kombiniert zwei Eltern: Hier übernimmt ein Kind den ersten Teil seiner Gene von einem Elternteil und den Rest vom anderen, sodass die frühen Manöver einer Rakete auf die späten einer anderen treffen können. Mutation ersetzt einige Gene zufällig. Crossover kombiniert neu, was die Population schon hat; Mutation bringt hinein, was sie nie hatte. Hollands Schema-Theorem beschreibt, wie sich kurze Bausteine guter Gene unter dieser Mischung aus Selektion und Rekombination in der Population ausbreiten.
Elitismus, Exploration und Exploitation
Die besten wenigen Kandidaten unverändert in die nächste Generation zu übernehmen, der Elitismus, garantiert, dass die beste Antwort nie verloren geht. Jeder genetische Algorithmus muss Exploration, das Ausprobieren neuer Bereiche des Suchraums, gegen Exploitation, das Verfeinern des bereits Guten, abwägen. Zu wenig Variation, und die Population konvergiert auf eine mittelmäßige Antwort; zu viel, und sie kommt nie zur Ruhe. Populationsgröße, Mutationsrate und Selektionsdruck sind die Regler, die dieses Gleichgewicht einstellen.
Lokale Optima
Ein genetischer Algorithmus folgt nur der Fitness, daher lässt er sich täuschen. Wenn der Weg zur besten Antwort zunächst über schlechtere führt, erklimmt die Population den nächstgelegenen Hügel und bleibt dort: ein lokales Optimum. Hinter den versetzten Wänden auf der Spielwiese schneiden Raketen, die unter dem Ziel abstürzen, besser ab als Raketen, die abdrehen, um die Lücke zu finden, also sammelt sich die Population an der Wand. Abhilfe schaffen größere Populationen, höhere Mutation, eine vielfältig gehaltene Population und vor allem eine bessere Fitnessfunktion.
Probieren Sie es aus
Öffnen Sie die Spielwiese für genetische Algorithmen, um Raketen um eine Wand, eine Lücke, Säulen, versetzte Wände oder selbst gezeichnete Wände herum zu entwickeln. Ändern Sie die Population, die Mutationsrate, die Lebensdauer und das Selektionsverfahren, schalten Sie Elitismus ein und aus und verfolgen Sie im Diagramm, wie schnell der Anteil der Raketen wächst, die das Ziel erreichen, oder warum er es nicht tut.
Häufig gestellte Fragen
Ist ein genetischer Algorithmus eine Form von künstlicher Intelligenz?
Er gehört als Such- und Optimierungsverfahren zum weiteren Feld der KI und des maschinellen Lernens. Er lernt nicht wie ein neuronales Netz aus Beispielen, sondern verbessert Lösungskandidaten durch Ausprobieren und Auslese. Beide werden oft kombiniert, etwa indem man die Struktur oder die Gewichte neuronaler Netze evolviert, ein Ansatz namens Neuroevolution.
Findet ein genetischer Algorithmus immer die beste Antwort?
Nein. Er ist eine Heuristik: Er findet meist gute Antworten auf schwierige Probleme, gibt aber keine Garantie für die beste und keinen Beweis dafür, wie nahe er ihr kommt. Bei Problemen, für die ein exaktes Verfahren schnell genug ist, ist dieses Verfahren besser.
Was ist der Unterschied zwischen einem genetischen Algorithmus und Evolutionsstrategien?
Beide sind evolutionäre Algorithmen. Klassische genetische Algorithmen betonen das Crossover auf zeichenkettenartigen Chromosomen; Evolutionsstrategien arbeiten vor allem mit Mutation auf reellen Zahlen und passen ihre Mutationsschrittweiten oft unterwegs selbst an. Moderne Verfahren mischen Ideen aus beiden.
Warum sind die Raketen anfangs so unbeholfen?
Ihre ersten Gene sind völlig zufällige Schübe, die sich im Mittel aufheben, sodass die Raketen treiben. Erst wenn die Selektion die seltenen Raketen behalten hat, die zufällig ungefähr in die richtige Richtung geschoben haben, und das Crossover ihre guten Abschnitte kombiniert hat, entstehen koordinierte Flüge.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Spielwiese für genetische Algorithmen öffnen