So vermeiden Sie, dass Sie bei genetischen Algorithmen am lokalen Optimum hängen bleiben

Ich programmiere einen genetischen Algorithmus unter Verwendung der grammatikalischen Evolution. Mein Problem ist, dass ich lokale optimale Werte erreiche (vorzeitige Konvergenz) und wenn das passiert, weiß ich nicht, was ich tun soll. Ich denke darüber nach, das Mutationsverhältnis zu erhöhen (5% ist der Standardwert), aber ich weiß nicht, wie ich entscheiden soll, wann es notwendig ist.

Die Daten, die ich zu jeder Generation habe, sind zweidimensionale Arrays, deren erste Spalte die Fitness ist

adn[i][0] ← fitness 
row → is the values of the Grammar
column ↓ Each indiviual result

Wenn Sie eine Klärung benötigen, fragen Sie bitte und ich werde gerne Änderungen vornehmen. Beachten Sie, dass dies nicht meine Muttersprache ist und entschuldigen Sie die Fehler und die Unannehmlichkeiten.

Bei der Beantwortung einer Anfrage sind meine Operationen wie folgt und genau in dieser Reihenfolge:

• Ich generiere eine zufällige Population (Eine Matrix mit Zufallszahlen)
• Ich generiere eine Matrix, die das gewünschte Ergebnis enthält. Zu diesem Zweck habe ich einige Funktionen implementiert, die zusätzlich eine Abweichung von + -5% aufweisen, zum Beispiel: fun (x) = (2 * cos (x) + sen (x) - 2X) * (0,95+) (eine Zahl, die zwischen 0 und 0,1 oszilliert) , das x enthält jedes f (x) mit einer Sequenz von 0 bis N (da N die Größe der Zeile ist), das y enthält genau das gleiche (mehr Ergebnisse)
• Startet den Algorithmus (Generationen beginnen sich zu ändern

Die Aktionen, die jede Generation ausmachen, sind:

• Mutation: Eine Zufallszahl jedes Cromosoms kann auf jedem Gen mutieren → adn [i] [zufällig] = Zufallszahl (mit einer Wahrscheinlichkeit von 5%, dass dies geschieht)
• Crossover: Ich kreuze jedes adn mit einem anderen adn (80% ist die Wahrscheinlichkeit einer Mutation für jedes Paar). Für die Paarung wähle ich eine Zufallszahl und sehe adn [i] und adn [(i + j) mod NumADNs].

• Übersetzen. Ich erhalte eine Matrix, die die Werte f (0 bis N) enthält, die in einem Schritt transkribiert und die Grammatik auf das Bild übertragen

  

-Fitness: Ich vergleiche die erhaltenen Werte mit den erwarteten und aktualisiere die Fitness.

-Elitismus: Danach wähle ich die besten 4 Adns aus und bringe sie nach oben, sie werden ausgewählt

-Auswahl: Jede nicht-elitäre ADN wird einer völlig zufälligen ADN gegenüberstehen, und wenn ihre Fitness geringer ist (niedriger ist besser), wird sie sich durchsetzen, was eine Möglichkeit für das schlechtere Überleben darstellt

Es sieht so aus, als hätten Sie es mit vorzeitiger Konvergenz zu tun .

Mit anderen Worten, Ihre Bevölkerung füllt sich mit Personen, die die suboptimale Lösung darstellen, und / oder Personen, die dieser Lösung (zu) nahe stehen.

Das Grundgerüst eines genetischen Algorithmus lautet wie folgt:

P <- Population of size N with N random individuals.
evaluate fitness of all individuals in P
while (stopping criteria not met) {
    C <- empty Child set of size M
    while (size of C is not M) {
        parent1 <- select an individual from P
        parent2 <- select an individual from P

        child1, child2 <- combine parent1 and parent2 somehow.
        child1, child2 <- mutate children by chance
        evaluate fitness of child1, child2
        C <- C + child1 + child2
    }
    P <- combine P and C. (P remains size N)
}
return individual with best fitness

Beachten Sie, dass die ( zum Beispiel) die Größe der Bevölkerung / Kinder nicht konstant sein muss per se . Oder Sie kombinieren eine variable Anzahl von Eltern zu einer variablen Anzahl von Kindern (z. B. eine Überkreuzung zwischen 5 Eltern, die zu 7 Kindern führt). Aber ich würde es zunächst einfach halten.

Wie Sie sehen können, sind die Hauptoperatoren in einem genetischen Algorithmus in der richtigen Reihenfolge

• Auswahl : Wählen Sie Personen aus der Population aus, die kombiniert werden sollen. Beispiele: Turnierauswahl , proportionale Auswahl , Kürzungsauswahl , ...
• Crossover : Kombinieren Sie ausgewählte Personen (Eltern) mit neuen Personen (Kindern). Beispiele: Einpunkt-Frequenzweiche , N-Punkt-Frequenzweiche , gleichmäßige Frequenzweiche , Schnitt und Spleiß , ...
• Mutation : Mutieren Sie zufällig ein Individuum (nicht), indem Sie das Individuum leicht verändern.
• Rekombination : Fügen Sie die Kinder irgendwie in die Gruppe der Eltern ein. Beispiele: Fügen Sie alle Kinder zur Bevölkerung hinzu, sortieren Sie die Sache nach Fitness und entfernen Sie die schlimmsten Personen, damit Ihre Bevölkerung wieder die Größe N hat. Sortieren Sie Ihre Bevölkerung und lassen Sie die schlimmsten M Personen fallen und fügen Sie alle Kinder hinzu; Oft werden die gleichen Techniken verwendet, die in der Auswahlphase vorgestellt werden.

In Ihrer Beschreibung verwechseln Sie mehrere Schritte, als ob es einer wäre (z. B. überspringen Sie den Auswahlschritt , aber Sie machen ihn im Crossover- Schritt unübersichtlich ). Sie beschreiben Techniken auch so, als wäre es ein Schritt des Algorithmus (z. B. Elitismus ist eine Technik, die im Rekombinationsschritt verwendet wird , um sicherzustellen, dass zumindest die besten Personen nicht sterben).

Ein Beispiel, bei dem eine vorzeitige Konvergenz auftreten kann / wird, ist, wenn Sie nur die besten Personen als Eltern auswählen und nur die besten Personen überleben lassen (im Rekombinationsschritt ).

Einige mögliche Methoden, um dies zu beheben:

• Erhöhen Sie die Mutationsrate . Eine Mutation ist jedoch normalerweise ein sehr zufälliger Prozess. Sie würden "reines" Glück brauchen, um der suboptimalen Lösung zu entkommen.
• Gestalten Sie Ihre genetischen Operationen neu . z. B. Personen / Nachkommen mit schlechter Fitness erlauben, die Generation häufiger zu überleben. Es kann sein, dass Sie derzeit zu viele gute Personen auswählen, um zu überleben. Lassen Sie jedoch nicht zu viele schlechte Personen überleben, sonst konvergiert Ihr Algorithmus niemals zu etwas Gutem.
• (...)

Das Ziel ist es, Ihre genetischen Operationen so zu tweeken, dass in jeder nächsten Generation die durchschnittliche Fitness Ihrer Bevölkerung (vorzugsweise) gestiegen ist, während eine ausreichend große Fitnessvariation beibehalten wird. Das ist nicht einfach.

Es gibt verschiedene andere Methoden, um vorzeitige Konvergenz zu vermeiden, wenn Ihnen die oben genannten Methoden nicht helfen. Ich empfehle jedoch dringend, zuerst mit der Veränderung Ihrer genetischen Operationen zu experimentieren, bevor Sie dies tun. Suchbegriffe: Vorauswahl , Gedränge , Fitness-Sharing , Inzestprävention , ...

Wenn Sie die Mutationsrate erhöhen, können Sie vom lokalen Optimum abprallen, nach mehr Möglichkeiten suchen, aber es gibt einen Kompromiss - bei einer höheren Mutationsrate ändert sich die Konvergenzrate und bei einer zu hohen Rate hört die Konvergenz auf.
Wenn die Ergebnisse für eine bestimmte Anzahl von Iterationen nicht mehr geändert werden - dies ist der Zeitpunkt, an dem Sie aufhören, ist es auch der Moment, die neue Suche zu starten.
Ich würde vorschlagen, GA mit SA zu mischen , um ein globales Optimum zu finden.
Eine funktionierende Hacky-Lösung besteht darin, sich an lokale Optima zu erinnern und neu zu starten (mutieren oder neu initialisieren), aber nachdem die Attraktor-Drop-Mutationsrate verworfen wurde.