Wie behebt man vorzeitige Konvergenz in einfachen GA (Python)?

9

Gestern begann ich, die genetischen Algorithmen zu erforschen, und als ich mit einer grundlegenden Theorie endete, versuchte ich, einfache GA über Python zu schreiben, die die Diophantische Gleichung löst. Ich bin neu bei Python und GAs, also bitte, beurteile meinen Code nicht streng.

Problem

Ich kann aufgrund der vorzeitigen Konvergenz keine Ergebnisse erhalten (es gibt einen Punkt ohne Rückkehr, Population [n] == Population [n + i], wobei i eine ganze Zahl ist. Sogar das zufällige Mutationselement kann das nicht ändern, die Generation baut sich sehr schnell ab)

GA verwendet Crossover, um zu züchten und eine gewichtete Auswahl an Eltern.

  • Q1: Gibt es Designfehler in meinem? Code (unten)?
  • Q1.2: Muss ich Elitismus hinzufügen?
  • Q1.3: Muss ich die Rasse wechseln? Logik?
  • F2: Ist wirklich eine Tiefenkopie erforderlich?

Code:

%Vor%

Ich versuchte , die Rasse und die gewichtete Zufallsauswahllogik zu ändern, aber ohne Ergebnisse. Diese GA soll Arbeit sein, ich weiß nicht, was los ist. Ich weiß, dass es auf Python einige GA-Bibliotheken gibt, ich versuche sie im Moment zu verstehen - es scheint, dass sie für mich ziemlich komplex sind. Sorry für Fehler, Englisch ist nicht meine Muttersprache. Danke für Ihr Verständnis.

NECROUPDATE: Speichere Chromosomen in Gray Code, nicht in Integer.

    
Ernado 28.06.2011, 19:49
quelle

1 Antwort

3

Geringfügiger logischer Fehler: parentTwo ist etwas wahrscheinlicher der Vater als die Mutter. Gerade Chancen wären randint (1.100) & lt; = 50, nicht randint (1.100) & lt; 50. Wird nicht sein, was das Problem hier verursacht.

  1. Ihre Bevölkerungsgröße ist ziemlich klein. 40 ist sehr selten für die meisten Probleme. Dadurch wird es schnell konvergieren.
  2. Elitismus wird dazu führen, dass Ihre Population schneller konvergiert, nicht langsamer.
  3. Ihre WeightedChoice-Funktion scheint ziemlich ineffizient zu sein, wenn ich sie richtig lese. Ich habe Python vor kurzem nicht genug benutzt, um wirklich zu verstehen, was dort vor sich geht, aber wenn ich es mir anschaue, fühlt es sich sicherlich etwas ineffizient an. Wenn Sie das verbessern können, sollte es die Verarbeitung beschleunigen, so dass Sie die Populationsgröße erhöhen können (und da ich meinen Algorithmus wahrscheinlich mit mindestens O (n ^ 2) betrachte, wird das sein wirklich wichtig).

Bei einer so kleinen Populationsgröße sind 200-300 Generationen nicht überraschend, um das Problem zu lösen. Wenn Sie die Population erhöhen, sollte es die erforderlichen Generationen reduzieren.

Hinweis: Ich habe einen alten Code gefunden, den ich vor einigen Jahren geschrieben habe, um ein ähnliches Problem zu lösen. Es ist in C und verwendet Turnierauswahl, aber vielleicht kann es dir ein paar Ideen geben:

%Vor%     
Joel Rein 29.06.2011, 02:22
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Kann Identitätswechsel beim Starten eines Nicht-Exe-Prozesses in C # verwendet werden?