Auswahl nur der oberen x% für die Auswahl in einem genetischen Algorithmus

Question

Ich arbeite derzeit an einer StringEvolver und ich bin mir nicht ganz sicher über einen bestimmten Begriff, der in GAs verwendet werden kann.

In genetischen Algorithmen, Elitismus bezieht sich auf die Teilmenge der Bevölkerung, die direkt zur nächsten Generation befördert werden; richtig?

Aber gibt es einen spezifischen Begriff für die Verwendung nur zum Beispiel, die oberen 75% der aktuellen Bevölkerung für die Auswahl, Crossover und Mutation Prozess statt die gesamte Bevölkerung? Im Grunde, wie heißt diese x% -Rate?

Was ich meine ist, dass anstatt die gesamte Bevölkerung der Verwendung für etwa ein Roulette-Auswahlprozess, ich nur die Top-x% verwenden (dh züchten nur unter den besten x% der Bevölkerung)

---

Der Grund, warum ich frage, ist, weil ich bemerkenswerte Leistungsverbesserungen (schnellere Konvergenz) festgestellt habe, wenn zum Beispiel die oberen 10-25% der Population für die Selektion, Crossover und Mutationsprozesse zur Weiterentwicklung der Generation verwendet wurden Population.

Answer 1

Eine naive Selektionsstrategie, bei der Sie einfach die schwächeren Kandidaten verwerfen, wird manchmal Trunkation Selection genannt. Für viele Probleme führt es zu einer vorzeitigen Konvergenz, obwohl ich festgestellt habe, dass es für das Problem des Traveling Salesman recht gut funktioniert.

Klingt wie Sie haben eine zweiphasige Strategie, erstens mit Trunkierung Auswahl, um die schwachen Kandidaten zu beseitigen und dann eine ausgefeiltere Strategie (Roulette-Rad?), Um die Auswahl zu finalisieren.

Anstatt die Möglichkeit des Überlebens schwacher Kandidaten vollständig zu eliminieren, ist es möglicherweise besser, eine Auswahlstrategie zu wählen, mit der Sie diese Wahrscheinlichkeit optimieren können. Zum Beispiel können Sie bei der Turnierauswahl den Schwellenwert anpassen, um zu bestimmen, wie wahrscheinlich es ist, dass ein schwacher Kandidat anstelle eines stärkeren überlebt.

Answer 2

Es klingt, als würden Sie nur über eine bestimmte Auswahlmethode sprechen. Sie könnten ungefähr dasselbe tun, indem Sie Ihre Fitnessfunktion so skalieren, dass sie mit höheren Raten anstatt linear ansteigt.

Das sagte, ich würde davor warnen, die unteren Teile Ihrer Bevölkerung jedes Mal zu werfen. Bei kleineren GA's können Sie schneller konvergieren, aber für reale Probleme führt dies oft zu lokalen Minima, die die Qualität Ihrer Lösungen beeinträchtigen.

Das heißt, es gibt einen Begriff namens Dezimierung. Dies ist, wenn Sie die unteren X% Ihrer Bevölkerung vor Crossover und Mutation werfen. Dies wird in der Regel nicht bei jeder Generation gemacht. Sie werden typischerweise mit einer unfassbar großen Population beginnen, um einen größeren Suchraum abzudecken und dann nach X Generationen zu dezimieren, da GAs oft ihre größten Gewinne in den ersten 100 gens machen. Sie fahren dann mit der kleineren, leichter zu handhabenden Bevölkerung fort.

Hoffe, das hilft.

Answer 3

Es gibt keinen speziellen Begriff, der die Auswahl auf die oberen x% -Elemente beschränkt. Dies ist nur einer der Faktoren, die Sie bei der Implementierung einer Auswahlstrategie einstellen müssen.

Sie können in einigen Fällen eine schnellere Konvergenz erzielen, indem Sie diese x% -Figur einschränken, aber ich würde vorschlagen, Strings mit unterschiedlicher Länge zu verwenden und zu sehen, wie dies die Konvergenz beeinflusst. Ich habe das schon einmal gemacht (siehe this und this Projekte, beide auf sich entwickelnden Strings), und wenn Sie den Genpool bei der Auswahl von Individuen zu klein machen, kann die Wahrscheinlichkeit, stecken zu bleiben, im Verhältnis zur Länge der Zeichenkette explodieren dass du ernsthaft die Vielfalt kompromittierst.