Genetischer Algorithmus - neue Generationen werden schlechter

Question

Ich habe einen einfachen genetischen Algorithmus implementiert, um Kurzgeschichten basierend auf Aesop Fabeln zu generieren. Hier sind die Parameter, die ich verwende:

Mutation: Single-Word-Swap-Mutation mit getesteten Rate mit 0,01.

Crossover: Tauschen Sie die Geschichte Sätze an einem bestimmten Punkt. Rate - 0,7

Auswahl: Roulette-Rad Auswahl - https://stackoverflow.com/a/5315710/536474

Fitness-Funktion: 3 verschiedene Funktion. die höchste Punktzahl ist 1,0. Der höchste Fitnesswert ist 3,0.

Populationsgröße: Da bin ich mit 86 Fabeln Aesop, testete ich Populationsgröße 50.

Anfangspopulation: Alle 86 Fabel Satz Aufträge gemischt werden, um einen vollständigen Unsinn zu machen. Und mein Ziel ist es, aus diesen strukturverlorenen Fabeln etwas Sinnvolles zu generieren (zumindest auf einer bestimmten Ebene).

Stoppbedingung: 3000 Generationen. Und die Ergebnisse sind unten:

Dies ist jedoch nach wie vor ein günstiges Ergebnis nicht produzierten. Ich habe die Handlung erwartet, die über die Generationen hinweg geht. Irgendwelche Ideen, warum meine GA schlechtere Ergebnisse erzielt?

Update: Wie Sie alle vorgeschlagen, habe ich Elitismus von 10% der aktuellen Generation auf die nächste Generation kopiert. Ergebnis bleibt gleich:

Wahrscheinlich sollte ich Turnierauswahl verwenden.

Answer 1

Sie verlieren möglicherweise die besten Kombinationen, Sie sollten das Beste aus jeder Generation behalten, ohne zu kreuzen (Elite). Auch scheint Ihre Funktion ziemlich stabil zu sein, versuchen Sie andere Arten von Mutationen, die sich verbessern sollten.

Answer 2

Lassen Sie 5% bis 10% Ihrer Bevölkerung ausscheiden, damit Sie nicht das Beste verlieren, was Sie haben.

Stellen Sie sicher, dass Ihr Auswahlprozess gut eingerichtet ist. Wenn schlechte Kandidaten sehr oft durchgehen, ruiniert dies Ihre Entwicklung. Sie könnten auch in einem lokalen Optimum feststecken, müssen Sie möglicherweise andere Sachen in Ihr Genom einführen, sonst werden Sie nicht weit bewegen.

Das Verschieben von Sätzen und Wörtern wird Sie wahrscheinlich nicht sehr weit bringen, neue Sätze oder Wörter könnten interessant sein.

Wenn Sie die Geschichte als Punkt x, y und Ihre Bewertungsfunktion als f (x, y) betrachten, und Sie versuchen, das Maximum für f (x, y) zu finden, aber Ihre Mutation und Kreuz- Über sind begrenzt auf x -> y, y -> y, es macht Sinn, dass Sie sich nicht weit bewegen werden. Zugegeben, in Ihrem Problem gibt es viel mehr Variablen, aber ohne etwas Neues einzuführen, glaube ich nicht, dass Sie Lokalität vermeiden können.

Answer 3

Wie @GettnDer sagte, könnte Elitismus viel helfen.

Was ich vorschlagen würde, ist eine andere Auswahlstrategie zu verwenden. Die Auswahl des Roulette-Rades hat ein großes Problem: Stellen Sie sich vor, dass die beste Eignung des Individuums z. 90% der Summe aller Fitness. Dann ist es unwahrscheinlich, dass das Rouletterad die anderen Individuen auswählt (siehe z. B. here). Die Auswahlstrategie, die ich am meisten mag, ist die tournament selection. Es ist viel robuster gegenüber großen Unterschieden in den Fitnesswerten und der Selektionsdruck kann sehr einfach gesteuert werden.

Neuheit Suche

ich auch einen Versuch zu Novelty Search geben würde. Es ist ein relativ neuer Ansatz in der evolutionären Berechnung, wo Sie nicht die Auswahl basierend auf der tatsächlichen Fitness, sondern basierend auf Neuheit, die ein Metrik von wie ein Individuum ist in seinem Verhalten von den anderen (aber Sie berechne noch die Fitness, um die Guten zu fangen). Von besonderem Interesse könnten Kombinationen von klassischen fitness-getriebenen Algorithmen und neuheitsgetriebenen sein, wie die this one von J.-B. Mouret.

Answer 4

Alle oben genannten Antworten sind großartig und ich würde in sie schauen. Ich füge meine Gedanken hinzu.

Mutation

Ihre Mutationsrate scheint in Ordnung, obwohl mit genetischen Algorithmen Mutationsrate eine Menge Probleme verursachen kann, wenn es nicht richtig ist. Ich würde sicherstellen, dass Sie viele andere Werte testen, um sicher zu gehen.

Mit Mutation würde ich vielleicht zwei Arten von Mutation verwenden. Eine, die Wörter durch andere aus Ihrem Wörterbuch ersetzt, und eine, die zwei Wörter innerhalb eines Satzes tauscht. Dies würde die Diversifizierung der Bevölkerung als Ganzes und das Mischen von Wörtern fördern.

Crossover

ich nicht genau wissen, wie Sie dies aber ein-Punkt-Crossover scheint nicht, wie es das wirksam sein werden in dieser Situation implementiert haben. Ich würde versuchen, einen n-Punkt-Crossover zu implementieren, der Ihre Sätze viel besser mischen wird. Auch hier bin ich mir nicht sicher, wie es umgesetzt wird, aber nur das Tauschen ist vielleicht nicht die beste Lösung. Wenn zum Beispiel ein Wort am ersten Punkt ist, gibt es jemals eine Möglichkeit, es an eine andere Position zu verschieben, oder wird es immer das erste Wort sein, wenn es durch Auswahl ausgewählt wird?

Wenn die Wortfolge für das gewählte Problem wichtig ist, ist eine einfache Frequenzweiche möglicherweise nicht ideal.

Selection

Auch dies scheint in Ordnung, aber ich würde sicherstellen, dass Sie andere Optionen prüfen. In der Vergangenheit habe ich festgestellt, dass die rangbasierte Rouletteauswahl viel erfolgreicher ist.

Fitness

Dies ist immer das Wichtigste in jedem genetischen Algorithmus und mit der Komplexität des Problems Sie ich muss zu bedenken, würde doppelt sicher machen es funktioniert. Haben Sie getestet, dass es mit "bekannten" Problemen funktioniert?

Populationsgröße

Ihr Wert scheint klein, aber ich habe genetische Algorithmen gesehen arbeiten erfolgreich mit kleinen Populationen. Wiederum würde ich mit viel größeren Populationen experimentieren, um zu sehen, ob Ihre Ergebnisse besser sind.

Der beliebteste Vorschlag ist Elitismus zu implementieren und ich würde es definitiv empfehlen. Es muss nicht viel sein, sogar nur das beste Paar Chromosomen in jeder Generation (obwohl ich mit allem anderen verschiedene Werte ausprobieren würde).

Ein anderer manchmal nützlicher zu implementierender Operator ist Culling. Zerstöre einen Teil deiner schwächsten Chromosomen oder einen, der anderen (oder beiden) ähnlich ist und ersetze sie durch neue Chromosomen. Dies sollte dazu beitragen, dass Ihre Population "altbacken" wird, was aus Ihrer Grafik so aussieht, als ob sie passieren könnte. Mutation tut nur so viel zur Diversifizierung der Bevölkerung.

Answer 5

Wenn Sie mit genetischen Algorithmen arbeiten, ist es eine gute Methode, Ihr Chromosom zu strukturieren, um das tatsächliche Wissen über den zu optimierenden Prozess zu reflektieren.

In Ihrem Fall, da Sie Geschichten generieren wollen, die aus Sätzen bestehen, könnte es Ihre Ergebnisse verbessern, wenn Sie Ihre Chromosomen in strukturierte Phrasen umgewandelt haben, Linie <adjectives>* <subject> <verb> <object>* <adverbs>* (große Vereinfachung hier).

Jedem Wort könnte dann eine Klasse zugewiesen werden. Zum Beispiel, Fox = Subjekt, Aussehen = Verb, Trauben = Objekt und dann würde Ihr Crossover-Operator Elemente aus der gleichen Kategorie zwischen Chromosomen austauschen. Außerdem könnte Ihr Mutationsoperator nur neue Elemente einer richtigen Kategorie (z. B. ein Adjektiv vor dem Betreff) einfügen oder ein Wort für ein zufälliges Wort in derselben Kategorie ersetzen.

Auf diese Weise würden Sie die Anzahl der unsinnigen Chromosomen (wie Fox schöne Trauben Tag Himmel) minimieren und die Diskursgenerationsmacht für Ihre GA verbessern.

Außerdem stimme ich allen vorherigen Kommentaren zu: Wenn Sie Elitismus verwenden und die beste Leistung abnimmt, dann implementieren Sie es falsch (beachten Sie, dass es in einer pathologischen Situation für eine lange Zeit konstant bleiben kann).

Ich hoffe es hilft.