Genetische Algorithmen - Fortgeschrittene Themen
In diesem Abschnitt stellen wir einige fortgeschrittene Themen in genetischen Algorithmen vor. Ein Leser, der nur eine Einführung in GAs sucht, kann diesen Abschnitt überspringen.
Eingeschränkte Optimierungsprobleme
Eingeschränkte Optimierungsprobleme sind solche Optimierungsprobleme, bei denen wir einen bestimmten Zielfunktionswert maximieren oder minimieren müssen, der bestimmten Einschränkungen unterliegt. Daher sind nicht alle Ergebnisse im Lösungsraum realisierbar, und der Lösungsraum enthält realisierbare Bereiche, wie in der folgenden Abbildung gezeigt.
In einem solchen Szenario könnten Crossover- und Mutationsoperatoren Lösungen liefern, die nicht realisierbar sind. Daher müssen zusätzliche Mechanismen in der GA eingesetzt werden, wenn eingeschränkte Optimierungsprobleme behandelt werden.
Einige der häufigsten Methoden sind -
Verwenden von penalty functions Dies verringert die Eignung von nicht realisierbaren Lösungen, vorzugsweise so, dass die Eignung proportional zur Anzahl der verletzten Einschränkungen oder zum Abstand von der realisierbaren Region verringert wird.
Verwenden von repair functions die eine nicht realisierbare Lösung nehmen und sie so modifizieren, dass die verletzten Einschränkungen erfüllt werden.
Not allowing infeasible solutions überhaupt in die Bevölkerung eintreten.
Verwenden ein special representation or decoder functions das stellt die Machbarkeit der Lösungen sicher.
Grundlegender theoretischer Hintergrund
In diesem Abschnitt werden wir das Schema und den NFL-Satz zusammen mit der Bausteinhypothese diskutieren.
Schemasatz
Forscher haben versucht, die Mathematik hinter der Arbeit genetischer Algorithmen herauszufinden, und Hollands Schemasatz ist ein Schritt in diese Richtung. Im Laufe des Jahres wurden verschiedene Verbesserungen und Vorschläge am Schemasatz vorgenommen, um es allgemeiner zu gestalten.
In diesem Abschnitt beschäftigen wir uns nicht mit der Mathematik des Schemasatzes, sondern versuchen, ein grundlegendes Verständnis des Schemasatzes zu entwickeln. Die grundlegende Terminologie ist wie folgt:
EIN Schemaist eine "Vorlage". Formal ist es eine Zeichenfolge über dem Alphabet = {0,1, *},
wo * ist egal und kann jeden Wert annehmen.
Daher könnte * 10 * 1 01001, 01011, 11001 oder 11011 bedeuten
Geometrisch ist ein Schema eine Hyperebene im Lösungssuchraum.
Order eines Schemas ist die Anzahl der angegebenen festen Positionen in einem Gen.
Defining length ist der Abstand zwischen den beiden am weitesten entfernten festen Symbolen im Gen.
Das Schemasatz besagt, dass dieses Schema mit überdurchschnittlicher Fitness, kurzer Definitionslänge und niedrigerer Ordnung eher Crossover und Mutation überlebt.
Bausteinhypothese
Bausteine sind Schemata niedriger Ordnung mit geringer definierter Länge mit der oben angegebenen durchschnittlichen Fitness. Die Bausteinhypothese besagt, dass solche Bausteine als Grundlage für den Erfolg und die Anpassung von GAs in GAs dienen, indem sie fortlaufend solche „Bausteine“ identifizieren und neu kombinieren.
No Free Lunch (NFL) Theorem
Wolpert und Macready veröffentlichten 1997 einen Artikel mit dem Titel "No Free Lunch Theorems for Optimization". Es heißt im Wesentlichen, dass, wenn wir über den Raum aller möglichen Probleme mitteln, alle nicht wiederkehrenden Black-Box-Algorithmen die gleiche Leistung aufweisen.
Je besser wir ein Problem verstehen, desto problemspezifischer wird unsere GA und desto besser ist die Leistung. Dies wird jedoch durch eine schlechte Leistung bei anderen Problemen ausgeglichen.
GA-basiertes maschinelles Lernen
Genetische Algorithmen finden auch Anwendung im maschinellen Lernen. Classifier systems sind eine Form von genetics-based machine learning(GBML) -System, das häufig im Bereich des maschinellen Lernens eingesetzt wird. GBML-Methoden sind ein Nischenansatz für maschinelles Lernen.
Es gibt zwei Kategorien von GBML-Systemen:
The Pittsburg Approach - Bei diesem Ansatz codierte ein Chromosom eine Lösung, sodass den Lösungen Fitness zugewiesen wird.
The Michigan Approach - Eine Lösung wird normalerweise durch viele Chromosomen dargestellt, sodass die Teillösungen fit sind.
Es sollte beachtet werden, dass das Standardproblem wie Crossover, Mutation, Lamarckian oder Darwinian usw. auch in den GBML-Systemen vorhanden ist.