Warum ist Crossover ein Teil genetischer Algorithmen?

Genetische Algorithmen sind mir kürzlich aufgefallen, als ich versuchte, Computergegner für rundenbasierte Strategie-Computerspiele zu korrigieren / zu verbessern.

Ich habe einen einfachen genetischen Algorithmus implementiert, der keine Überkreuzung verwendet, sondern nur eine zufällige Mutation. In diesem Fall schien es zu funktionieren, und so begann ich zu denken:

Warum ist Crossover ein Teil genetischer Algorithmen? Wäre Mutation nicht genug?

_{Dies ist aus einem Datendump auf einer alten AI-Site. Der Fragesteller hatte die UID von 7.}

Mutation wird normalerweise als globaler Operator definiert, dh iterierte Mutation kann (schließlich) jeden Punkt im durch das Genom definierten Vektorraum erreichen. In diesem Sinne ist Mutation allein sicherlich „genug“.

Zur Motivation für Crossover - aus den Grundlagen der Metaheuristik , S. 42:

Crossover basierte ursprünglich auf der Prämisse, dass sehr gesunde Personen häufig bestimmte Merkmale, sogenannte Bausteine , gemeinsam haben. Zum Beispiel könnte in der booleschen Person 10110101 *** 101 * 1 ein Baustein sein

(wobei * "entweder 0 oder 1" bedeutet)

Die Idee ist also, dass Crossover funktioniert, indem Bausteine ​​schnell in der Bevölkerung verteilt werden.

Crossover-Methoden gehen auch davon aus, dass ein gewisser Grad an Verknüpfung zwischen Genen auf dem Chromosom besteht: Das heißt, Einstellungen für bestimmte Gene in Gruppen korrelieren stark mit der Verbesserung der Fitness. Zum Beispiel können die Gene A und B nur dann zur Fitness beitragen, wenn beide auf 1 gesetzt sind: Wenn eines auf 0 gesetzt ist, bewirkt die Tatsache, dass das andere auf 1 gesetzt ist, nichts.

Beachten Sie auch, dass Crossover kein globaler Operator ist . Wenn der einzige Operator Crossover ist, dann (auch ab S. 42):

Schließlich wird die Bevölkerung zu Kopien desselben Individuums konvergieren und oft (leider) vorzeitig konvergieren. Zu diesem Zeitpunkt gibt es kein Entrinnen: Wenn ein Individuum mit sich selbst übergeht, wird nichts Neues erzeugt.

Aus diesem Grund wird Crossover im Allgemeinen zusammen mit einem globalen Mutationsoperator verwendet.

Crossover ermöglicht die Kombination von zwei Elternteilen (im Gegensatz zur Mutation, bei der nur ein Elternteil verwendet wird). In einigen Fällen ist es nützlich (z. B. wenn Sie einen FPS-Bot trainieren, wenn ein Elternteil gut schießen kann und ein anderer Elternteil sich gut bewegen kann, ist es sinnvoll, sie zu kombinieren). In einigen anderen Fällen ist dies nicht der Fall.

Wenn Sie an Crossover denken, ist es wichtig, an die Fitnesslandschaft zu denken.

Stellen Sie sich ein hypothetisches Szenario vor, in dem wir einen genetischen Algorithmus anwenden, um eine Lösung zu finden, die bei zwei Aufgaben gut funktioniert. Dies könnte aus Francks Beispiel (Bewegen und Schießen) für eine KI stammen, oder es könnten 2 Ausgaben in einem genetischen Szenario für maschinelles Lernen vorhergesagt werden, aber die meisten Szenarien, in denen GAs angewendet werden, sind synonym (selbst bei der Lösung einer einzelnen Aufgabe kann dies der Fall sein) verschiedene Aspekte der zu behandelnden Aufgabe sein).

Angenommen, wir hatten eine Person 1, die bei beiden Aufgaben einigermaßen gute Leistungen erbrachte, und wir fanden eine Reihe von Mutationen, die 2 neue Personen 2 und 3 hervorbrachten, die bei Aufgabe 1 bzw. 2 eine bessere Leistung zeigten als Person 1. Obwohl beide Verbesserungen sind, möchten wir im Idealfall eine allgemein gute Lösung finden und die Funktionen kombinieren, die sich als vorteilhaft erwiesen haben.

Hier kommt die Frequenzweiche ins Spiel. Durch die Kombination der Genome der Individuen 2 und 3 können wir ein neues Individuum finden, das eine Mischung ihrer Leistungen hervorbringt. Während es möglich ist, dass ein solches Individuum durch eine Reihe von Mutationen erzeugt wird, die auf Individuum 2 oder Individuum 3 angewendet werden, passt die Landschaft möglicherweise einfach nicht dazu (es kann zum Beispiel keine günstigen Mutationen in dieser Richtung geben).

Sie haben also teilweise recht; Es kann manchmal vorkommen, dass die Vorteile von Crossover mit einer Reihe von Mutationen repliziert werden. Manchmal ist dies nicht der Fall und Crossover kann die Fitnesslandschaft Ihres GA glätten, die Optimierung beschleunigen und Ihrem GA helfen, lokalen Optima zu entkommen.