Optimierung

Definieren Sie den evolutionären Algorithmus

Bei der Erörterung, wie cBots optimiert werden können, haben wir erwähnt, dass cBots mit der Methode des evolutionären Algorithmus verfeinert werden können. In diesem Leitfaden erklären wir genau, was das ist und wie es funktioniert.

Die Methode des evolutionären Algorithmus basiert auf der Theorie der natürlichen Selektion. Diese Theorie besagt, dass nur die am besten angepassten Individuen für die nachfolgende Fortpflanzung überleben.

Bei der cBot-Optimierung wird jeder Optimierungsdurchlauf als ein Individuum betrachtet. Um einzelne Durchläufe zu bewerten, berechnet der evolutionäre Algorithmus eine bestimmte Fitnesswertung für jeden Durchlauf und vergleicht diese Wertung mit allen anderen Durchläufen.

Damit er funktioniert, benötigt der evolutionäre Algorithmus eine Ausgangspopulation. Um diese zu erzeugen, führt der Optimierer mehrere verschiedene Durchläufe mit randomisierten Parametern aus. Nach der Erstellung seiner Ausgangspopulation beginnt der Algorithmus mit dem Prozess der Suche nach dem am besten angepassten Optimierungsdurchlauf. Dieser Prozess wird fortgesetzt, bis die Fitnesswertungen der untergeordneten Durchläufe zu stagnieren und zu konvergieren beginnen. An diesem Punkt wird der Algorithmus gestoppt.

Phasen des evolutionären Algorithmus

Jeder evolutionäre Algorithmus hat die folgenden Phasen.

graph TB
  B([Selektion]) ==> C([Crossover]);
  C ==> D([Mutation]);
  D ==> B;

Die Phasen werden wie folgt erklärt.

Selektion

Während dieser Phase findet der Algorithmus die zwei am besten angepassten Optimierungsdurchläufe anhand ihrer jeweiligen Fitnesswertungen.

Crossover

Nachdem die zwei am besten angepassten Optimierungsdurchläufe gefunden wurden, verwendet der Algorithmus sie, um neue untergeordnete (oder Nachkommen-)Durchläufe zu erstellen, indem er Kombinationen der Parameterwerte beider übergeordneten Durchläufe verwendet.

Mutation

In dieser Phase mutiert der Algorithmus die Nachkommendurchläufe, indem er einen oder mehrere Parameterwerte zufällig modifiziert.

Nach der Mutationsphase führt der Optimierer einen neuen Nachkommen-Optimierungsdurchlauf aus. Anschließend wiederholt er alle Phasen, aber nur, wenn die Fitnesswertung eines Nachkommendurchlaufs höher war als die des letzten am besten angepassten Optimierungsdurchlaufs. Ein solches Ergebnis würde bedeuten, dass es Raum für Verbesserungen gibt, was darauf hinweist, dass die Optimierung fortgesetzt werden sollte.

Andernfalls erhöht der Algorithmus seinen Stagnationszähler. Wenn der Stagnationszähler den Wert des Parameters für die Stagnationsperiode des Algorithmus erreicht, wird der Optimierungsprozess automatisch gestoppt.

Parameter des evolutionären Algorithmus

Der evolutionäre Algorithmus hat mehrere Parameter, die er während seiner Laufzeit verwendet. Diese Parameter können nicht geändert werden.