So funktioniert der genetische Algorithmus
Überblick über den Algorithmus
Die Funktionsweise des genetischen Algorithmus lässt sich wie folgt zusammenfassen:
Der Algorithmus beginnt mit der Erstellung einer zufälligen Anfangspopulation.
Der Algorithmus erstellt dann eine Sequenz neuer Populationen. Bei jedem Schritt verwendet der Algorithmus die Individuen der aktuellen Generation, um die nächste Population zu erstellen. Um die neue Population zu erstellen, führt der Algorithmus die folgenden Schritte aus:
Bewertet jedes Mitglied der aktuellen Population, indem sein Fitnesswert berechnet wird. Diese Werte werden als Rohfitnesswerte bezeichnet.
Skaliert die Rohfitnesswerte, um sie in einen besser nutzbaren Wertebereich umzuwandeln. Diese skalierten Werte werden Erwartungswerte genannt.
Wählt Mitglieder, sogenannte Eltern, auf Grundlage ihrer Erwartungen aus.
Einige der Individuen der aktuellen Population, die eine geringere Fitness aufweisen, werden als Elite ausgewählt. Diese Eliteindividuen werden an die nächste Population weitergegeben.
Erzeugt aus den Eltern Kinder. Kinder entstehen entweder durch zufällige Veränderungen an einem einzelnen Elternteil – Mutation – oder durch die Kombination der Vektoreinträge eines Elternpaars – Crossover.
Ersetzt die aktuelle Population durch die Kinder, um die nächste Generation zu bilden.
Der Algorithmus stoppt, wenn eines der Stoppkriterien erfüllt ist. Siehe Abbruchbedingungen für den Algorithmus.
Der Algorithmus führt modifizierte Schritte für lineare und ganzzahlige Einschränkungen aus. Siehe Ganzzahlige und lineare Einschränkungen.
Für nichtlineare Einschränkungen wird der Algorithmus weiter modifiziert. Siehe Nichtlineare Constraint-Solver-Algorithmen für genetische Algorithmen.
Ursprüngliche Population
Der Algorithmus beginnt mit der Erstellung einer zufälligen Anfangspopulation, wie in der folgenden Abbildung dargestellt.
In diesem Beispiel enthält die Anfangspopulation 20 Individuen. Beachten Sie, dass alle Individuen der ursprünglichen Population im oberen rechten Quadranten des Bildes liegen, das heißt, ihre Koordinaten liegen zwischen 0 und 1. In diesem Beispiel lautet die Option InitialPopulationRange [0;1].
Wenn Sie ungefähr wissen, wo der Minimalpunkt einer Funktion liegt, sollten Sie InitialPopulationRange so einstellen, dass der Punkt nahe der Mitte dieses Bereichs liegt. Wenn Sie beispielsweise glauben, dass der Minimalpunkt der Rastrigin-Funktion in der Nähe des Punkts [0 0] liegt, können Sie InitialPopulationRange auf [-1;1] setzen. Wie dieses Beispiel jedoch zeigt, kann der genetische Algorithmus das Minimum auch bei einer nicht optimalen Wahl für InitialPopulationRange finden.
Die nächste Generation schaffen
Bei jedem Schritt verwendet der genetische Algorithmus die aktuelle Population, um die Kinder zu erschaffen, die die nächste Generation bilden. Der Algorithmus wählt eine Gruppe von Individuen in der aktuellen Population aus, die sogenannten Eltern, die ihre Gene – die Einträge ihrer Vektoren – an ihre Kinder weitergeben. Als Eltern wählt der Algorithmus in der Regel Individuen aus, die über bessere Fitnesswerte verfügen. In der Option SelectionFcn können Sie die Funktion angeben, die der Algorithmus zur Auswahl der Eltern verwendet. Siehe Selection Options.
Der genetische Algorithmus schafft drei Arten von Kindern für die nächste Generation:
Elite-Kinder sind die Individuen der aktuellen Generation mit den besten Fitnesswerten. Diese Individuen überleben automatisch die nächste Generation.
Crossover-Kinder entstehen durch die Kombination der Vektoren eines Elternpaares.
Mutations-Kinder entstehen durch die Einführung zufälliger Änderungen oder Mutationen bei einem einzelnen Elternteil.
Das folgende schematische Diagramm veranschaulicht die drei Kindertypen.
Mutation und Crossover erklärt, wie die Anzahl der vom Algorithmus generierten untergeordneten Elemente jedes Typs angegeben wird und welche Funktionen er zum Durchführen von Crossover und Mutation verwendet.
In den folgenden Abschnitten wird erläutert, wie der Algorithmus Crossover- und Mutationskinder erstellt.
Crossover-Kinder
Der Algorithmus erstellt Crossover-Kinder durch die Kombination von Elternpaaren in der aktuellen Population. An jeder Koordinate des Kindvektors wählt die Standard-Crossover-Funktion zufällig einen Eintrag oder ein Gen an derselben Koordinate von einem der beiden Eltern aus und weist es dem Kind zu. Bei Problemen mit linearen Einschränkungen erstellt die Standard-Crossover-Funktion das Kind als zufälligen gewichteten Durchschnitt der Eltern.
Mutationskinder
Der Algorithmus erzeugt Mutationskinder, indem er die Gene einzelner Eltern zufällig verändert. Bei Problemen ohne Einschränkungen fügt der Algorithmus dem übergeordneten Element standardmäßig einen Zufallsvektor aus einer Gauß-Verteilung hinzu. Bei beschränkten oder linear eingeschränkten Problemen bleibt das Kind durchführbar.
Die folgende Abbildung zeigt die Kinder der Ausgangspopulation, also der Population der zweiten Generation, und gibt an, ob es sich dabei um Elite-, Crossover- oder Mutationskinder handelt.
Handlungen späterer Generationen
Die folgende Abbildung zeigt die Populationen bei den Iterationen 60, 80, 95 und 100.
|
|
|
|
|
|
Mit zunehmender Generationenzahl rücken die Individuen der Population näher zusammen und nähern sich dem Minimumpunkt [0 0].
Abbruchbedingungen für den Algorithmus
Der genetische Algorithmus verwendet die folgenden Optionen, um zu bestimmen, wann aufgehört werden soll. Die Standardwerte für die einzelnen Optionen können Sie durch Ausführen von opts = optimoptions('ga') anzeigen.
MaxGenerations– Der Algorithmus stoppt, wenn die Anzahl der GenerationenMaxGenerationserreicht.MaxTime– Der Algorithmus wird nach einer Laufzeit vonMaxTimein Sekunden angehalten.FitnessLimit– Der Algorithmus stoppt, wenn der Wert der Fitnessfunktion für den besten Punkt in der aktuellen Population kleiner oder gleichFitnessLimitist.MaxStallGenerations– Der Algorithmus stoppt, wenn die durchschnittliche relative Änderung des Fitnessfunktionswerts überMaxStallGenerationskleiner alsFunction toleranceist.MaxStallTime– Der Algorithmus wird angehalten, wenn sich die Zielfunktion während eines Zeitintervalls in Sekunden, dasMaxStallTimeentspricht, nicht verbessert.FunctionTolerance– Der Algorithmus wird ausgeführt, bis die durchschnittliche relative Änderung des Fitnessfunktionswerts überMaxStallGenerationskleiner alsFunction toleranceist.ConstraintTolerance— DasConstraintTolerancewird nicht als Abbruchkriterium verwendet. Es wird verwendet, um die Machbarkeit im Hinblick auf nichtlineare Einschränkungen zu bestimmen. Außerdem bestimmtmax(sqrt(eps),ConstraintTolerance)die Machbarkeit im Hinblick auf lineare Einschränkungen.
Der Algorithmus stoppt, sobald eine dieser Bedingungen erfüllt ist.
Auswahl
Die Auswahlfunktion wählt die Eltern für die nächste Generation auf Grundlage ihrer skalierten Werte aus der Fitness-Skalierungsfunktion aus. Die skalierten Fitnesswerte werden Erwartungswerte genannt. Ein Individuum kann mehr als einmal als Elternteil ausgewählt werden und gibt in diesem Fall seine Gene an mehr als ein Kind weiter. Mit der Standardauswahloption @selectionstochunif wird eine Zeile erstellt, in der jedes übergeordnete Element einem Zeilenabschnitt mit einer Länge entspricht, die proportional zu seinem skalierten Wert ist. Der Algorithmus bewegt sich in gleich großen Schritten entlang der Linie. Bei jedem Schritt ordnet der Algorithmus dem Abschnitt, auf dem er landet, ein übergeordnetes Element zu.
Eine deterministischere Auswahloption ist @selectionremainder, die zwei Schritte ausführt:
Im ersten Schritt wählt die Funktion die Eltern deterministisch entsprechend dem ganzzahligen Teil des skalierten Wertes für jedes Individuum aus. Wenn der skalierte Wert einer Person beispielsweise 2,3 beträgt, wählt die Funktion diese Person zweimal als Elternteil aus.
Im zweiten Schritt wählt die Auswahlfunktion zusätzliche Eltern unter Verwendung der Bruchteile der skalierten Werte aus, wie bei der stochastischen gleichmäßigen Auswahl. Die Funktion legt eine Linie in Abschnitten an, deren Länge proportional zum Bruchteil des skalierten Werts der Individuen ist, und bewegt sich in gleichen Schritten entlang der Linie, um die Eltern auszuwählen.
Beachten Sie, dass die Auswahl völlig deterministisch ist, wenn die Bruchteile der skalierten Werte alle 0 ergeben, wie dies bei der
Top-Skalierung vorkommen kann.
Details und weitere Auswahlmöglichkeiten finden Sie unter Selection Options.
Reproduktionsoptionen
Die Reproduktionsoptionen steuern, wie der genetische Algorithmus die nächste Generation erschafft. Die Optionen sind
EliteCount– Die Anzahl der Individuen mit den besten Fitnesswerten in der aktuellen Generation, die garantiert bis in die nächste Generation überleben. Diese Personen werden als Elitekinder bezeichnet.Wenn
EliteCountmindestens 1 ist, kann der beste Fitnesswert von einer Generation zur nächsten nur abnehmen. Dies ist, was Sie erreichen möchten, da der genetische Algorithmus die Fitnessfunktion minimiert. Wenn Sie fürEliteCounteinen hohen Wert festlegen, dominieren die fittesten Individuen die Population, was die Suche weniger effektiv machen kann.CrossoverFraction– Der Anteil der Individuen in der nächsten Generation, die durch Crossover entstehen (mit Ausnahme der Elitekinder). Das Thema „Festlegen des Crossover-Anteils“ in Vary Mutation and Crossover beschreibt, wie sich der Wert vonCrossoverFractionauf die Leistung des genetischen Algorithmus auswirkt.
Da Eliteindividuen bereits bewertet wurden, bewertet ga die Fitnessfunktion von Eliteindividuen während der Reproduktion nicht erneut. Dieses Verhalten setzt voraus, dass die Fitnessfunktion eines Individuums nicht zufällig, sondern eine deterministische Funktion ist. Um dieses Verhalten zu ändern, verwenden Sie eine Ausgabefunktion. Siehe EvalElites in The State Structure.
Mutation und Crossover
Der genetische Algorithmus verwendet die Individuen der aktuellen Generation, um die Kinder zu erschaffen, die die nächste Generation bilden. Neben Elitekindern, die den Individuen der aktuellen Generation mit den besten Fitnesswerten entsprechen, erstellt der Algorithmus
Crossover-Kinder werden gebildet, indem Vektoreinträge oder Gene von einem Paar von Individuen der aktuellen Generation ausgewählt und zu einem Kind kombiniert werden.
Mutationskinder durch die Anwendung zufälliger Änderungen an einem einzelnen Individuum in der aktuellen Generation, um ein Kind zu erzeugen
Beide Prozesse sind für den genetischen Algorithmus wesentlich. Durch Crossover ist der Algorithmus in der Lage, die besten Gene verschiedener Individuen zu extrahieren und sie zu potenziell überlegenen Kindern neu zu kombinieren. Durch Mutation wird die Diversität einer Population erhöht und damit die Wahrscheinlichkeit, dass der Algorithmus Individuen mit besseren Fitnesswerten generiert.
Ein Beispiel dafür, wie der genetische Algorithmus Mutation und Crossover anwendet, finden Sie unter Die nächste Generation schaffen.
Sie können wie folgt angeben, wie viele untergeordnete Elemente jedes Typs der Algorithmus erstellt:
EliteCountgibt die Anzahl der Elite-Kinder an.CrossoverFractiongibt den Anteil der Population an, der Crossover-Kinder sind (mit Ausnahme der Elite-Kinder).
Wenn beispielsweise PopulationSize 20, EliteCount 2 und CrossoverFraction 0.8 ist, lauten die Zahlen der einzelnen Kindertypen in der nächsten Generation wie folgt:
Es gibt zwei Elitekinder.
Es gibt 18 Individuen, die keine Elite-Kinder sind, deshalb rundet der Algorithmus 0,8*18 = 14,4 auf 14, um die Anzahl der Crossover-Kinder zu erhalten.
Die restlichen vier Individuen, mit Ausnahme der Elite-Kinder, sind Mutationskinder.
Ganzzahlige und lineare Einschränkungen
Wenn ein Problem ganzzahlige oder lineare Einschränkungen (einschließlich Grenzen) aufweist, ändert der Algorithmus die Entwicklung der Population.
Wenn das Problem sowohl ganzzahlige als auch lineare Einschränkungen aufweist, ändert die Software alle generierten Individuen so, dass sie im Hinblick auf diese Einschränkungen durchführbar sind. Sie können jede beliebige Erstellungs-, Mutations- oder Crossover-Funktion verwenden, und die gesamte Population bleibt im Hinblick auf ganzzahlige und lineare Einschränkungen durchführbar.
Wenn das Problem nur lineare Einschränkungen aufweist, ändert die Software die einzelnen Elemente nicht so, dass sie im Hinblick auf diese Einschränkungen durchführbar sind. Sie müssen Erstellungs-, Mutations- und Crossover-Funktionen verwenden, die die Machbarkeit hinsichtlich linearer Einschränkungen beibehalten. Andernfalls kann die Populationsgröße undurchführbar werden und das Ergebnis kann undurchführbar sein. Die Standardoperatoren behalten die lineare Machbarkeit bei:
gacreationlinearfeasibleodergacreationnonlinearfeasiblefür die Erstellung,mutationadaptfeasiblefür die Mutation undcrossoverintermediatefür Crossover.
Die internen Algorithmen für ganzzahlige und lineare Machbarkeit ähneln denen für surrogateopt. Wenn ein Problem ganzzahlige und lineare Einschränkungen aufweist, erstellt der Algorithmus zunächst linear mögliche Punkte. Anschließend versucht der Algorithmus, ganzzahlige Beschränkungen zu erfüllen, indem er linear realisierbare Punkte mithilfe einer Heuristik, die versucht, die Punkte linear realisierbar zu halten, auf ganze Zahlen rundet. Wenn dieser Prozess nicht erfolgreich ist und nicht genügend mögliche Punkte zum Aufbau einer Population erhält, ruft der Algorithmus intlinprog auf, um zu versuchen, weitere Punkte zu finden, die hinsichtlich Grenzen, linearer Einschränkungen und ganzzahliger Einschränkungen möglich sind.
Wenn später durch Mutation oder Crossover neue Populationsmitglieder entstehen, stellen die Algorithmen durch ähnliche Schritte sicher, dass die neuen Mitglieder ganzzahlig und linear realisierbar sind. Jedes neue Mitglied wird bei Bedarf geändert, um möglichst nahe an seinem ursprünglichen Wert zu liegen und gleichzeitig die ganzzahligen und linearen Einschränkungen und Grenzen einzuhalten.
