Muss bei einem genetischen Algorithmus bei der Auswahl von Mitgliedern für Crossover mit der Rouletteradauswahlmethode zuerst die Population nach Fitnessrang sortiert werden?
Die Möglichkeiten scheinen zu sein:
Ich denke, dass das Sortieren in beide Richtungen keinen Effekt hat - ein zufällig auf einem Rad mit unterschiedlich großen (durch Fitness) Scheiben landender Kieselstein wird genau die gleiche Ergebnischance haben, egal ob die größeren Scheiben gruppiert sind oder nicht. Aber ich bin nicht 100% überzeugt.
Was denkst du?
Die Notwendigkeit, jede Generation zu sortieren, wirkt sich auch auf die Geschwindigkeit des Algorithmus aus. Daher würde ich es vorziehen, dies nicht zu tun (ich würde eine Sortierung durchführen, wenn ich Elitismus verwende, aber in diesem Fall nicht). Danke, wenn Sie wissen, da ich keine definitive Antwort via Google etc finden kann.
Nein, Sie müssen sie nicht sortieren. Sie sind genau richtig, dass es keinen Effekt hat, wenn die höher eingestuften Mitglieder zusammen gruppiert sind oder nicht (zumindest mit einem guten Zufallsgenerator :)).
Ihre Intuition ist hier tot - statistisch wird es keinen Effekt haben zu sortieren, und wie Sie erwähnen, müssen Sie nicht eine Menge Zeit und Mühe verschwenden, Dinge zu sortieren!
Sie müssen die Population nicht sortieren, wenn Sie eine solche Auswahl verwenden.
Und Sie haben auch Recht bezüglich der Komplexität, eine Art ist n * log (n), was den genetischen Algorithmus wesentlich langsamer macht (aber trotzdem bleibt die Komplexität polynomial, ein kritisches Merkmal eines genetischen Algorithmus).
So würde ich es machen (und dafür extra Punkte in der Schule bekommen):
implementieren eine allgemeinere Lösung mit Haken - vor der Mutation, nach der Auswahl usw. usw.
misst die Anzahl der Iterationen und die Geschwindigkeit des Algorithmus / jeder Iteration
Sortiere in einem Haken. messen. jetzt lass den Haken leer sein und messen und so weiter.
Sie werden einige schöne Daten erhalten und experimentell überprüfen, was Ihre Intuition Ihnen sagt.
Tags und Links genetic-algorithm roulette-wheel-selection