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

7

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

    die Grammatik

-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

Kaostias
quelle
1
In Ihrem Titel wird gefragt, wie Sie feststellen können, ob Sie sich im lokalen Optimum befinden. Nach einigen Iterationen gibt es keine Änderungen mehr. Der Körper fragt jedoch, was zu tun ist. Fügen Sie eine globale optimale Technik hinzu. Habe ich richtig verstanden
Evil
@EvilJS Ja, das ist richtig, mein Algorithmus läuft weiter, aber es gibt keine relevanten Änderungen.
Kaostias
Sie verfolgen also die Anzahl der Iterationen ohne Änderung, und wenn diese größer als der angegebene Schwellenwert ist, beenden Sie die Berechnung. In Ihrem Fall können Sie anstelle des Stopps die Mutationsrate erhöhen und es erneut versuchen. Wenn Sie nur die Lösung versuchen, um die Mutationsrate zu erhöhen, geben Sie einige Iterationen ein und setzen Sie sie auf den Standardwert.
Evil
Ich habe den Eindruck, dass Sie die Reihenfolge der Operationen verwechseln.
Auberon
Ein zufälliges Genom in jeder Charge
t123

Antworten:

9

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 , ...

Auberon
quelle
Nun, der Begriff " lokales Optimum" wurde in Artikeln und Büchern verwendet, z. B. hier vor langer Zeit. Der Begriff ist etwas überladen, aber er wird verwendet und ist sinnvoll.
Evil
Ich werde versuchen, die Dummy-Lösungen ein wenig länger zu überleben (ich habe sie sofort zerstört, als ich im Zufallsturnier mit einem besseren konfrontiert wurde). Welches wäre ein gutes Überholverhältnis für die schlechte Lösung?
Kaostias
@Kaostias Können Sie Ihre Antwort bearbeiten und Ihre genetischen Operationen kurz beschreiben (Auswahl, Rekombination, Mutation, Ersatz, ...)? Auf diese Weise können wir eine mögliche Ursache für vorzeitige Konvergenz erkennen.
Auberon
@Auberon fertig, sorry für das schlechte Englisch, ich habe einen großen Mangel an Synonims.
Kaostias
@ Kaostias Ich habe meine Antwort dahingehend geändert, was meiner Meinung nach für Sie am interessantesten ist.
Auberon
1

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.

Böse
quelle