Genetische Programmierung: Unterschied zwischen Roulette-Rang und Turnierauswahl

Question

Ich lese eine Folie über genetische Programmierung. In dieser Folie heißt es, dass es einige Methoden in der Auswahlphase wie Roulette, Rank oder Tournament ohne Erklärung gibt. Ich habe Google ausprobiert, aber nirgends wird klar über diese Begriffe gesprochen.

Bitte sagen Sie mir, was ist der Unterschied zwischen ihnen.

Answer 1

Rouletterad Auswahl (aka Fitness proportionate selection)

Die Brauchbarkeit wird verwendet, um jede einzelne eine Auswahlwahrscheinlichkeit zu assoziieren.

Wenn f _i die Brauchbarkeit der einzelnen i in der Bevölkerung ist, ist die Wahrscheinlichkeit, ausgewählt zu werden:

p _i = f _i/Σ _j (f _j) für j = 1 & hellip; N (N ist die Anzahl der Individuen in der Population)

Es Roulette-Rad genannt wird, weil sie als Roulette-Rad in einem Casino zu sehen sind:

Dies kann durch die folgenden simuliert werden (naive) Algorithmus:

1. Berechnen Sie die Summe aller Anpassungen in der Population (Summe S).
2. Generieren Sie eine Zufallszahl r im Intervall [0; S].
3. Gehen Sie durch die Bevölkerung und Summe Fitness. Wenn die Summe s größer als r ist, halte die Person an, wo du bist.

Für mögliche Implementierungen sehen:

• Roulette wheel selection algorithm
• Roulette Selection in Genetic Algorithms

---

Rang Selection ähnlich ist Roulette-Rad Auswahl der Ausnahme, dass Auswahlwahrscheinlichkeit auf die relative Fitness proportional anstatt abs olute Fitness.

Es macht keinen Unterschied, ob der fitteste Kandidat zehnmal fitter ist als der nächste fittest oder 0,001% fitter. In beiden Fällen wären die Auswahlwahrscheinlichkeiten gleich.

Alles, was zählt, ist das Ranking im Vergleich zu anderen Personen.

Rang Auswahl ist einfach zu implementieren, wenn Sie bereits auf Roulette Radauswahl kennen. Anstatt die Fitness als Wahrscheinlichkeit für auszuwählen, verwenden Sie den Rang.Also für eine Population von N Lösungen die beste Lösung bekommt Rang N, den zweitbeste Rang N-1, usw. Das schlechteste Einzel hat Rang 1.

(Ranking Selection in Genetic Algorithm code)

---

Tournament selection

1. wählen Sie wenige Individuen zufällig aus der Bevölkerung (ein Turnier).
2. Die Person mit der besten Fitness (der Gewinner) ist für Crossover ausgewählt.

Wie Sie sehen können, ist es effizient zu programmieren. Es funktioniert auch auf parallelen Architekturen und erlaubt es, den Selektionsdruck leicht anzupassen (Änderung der Anzahl der Personen in einem Turnier).

Natürlich gibt es viele Varianten dieser Algorithmen.

Für einen Vergleich Sie lesen konnte:

Comparison of Performance between Different Selection Strategies on Simple Genetic Algorithms (Jinghui Zhong, Xiaomin Hu, Min Gu Jun Zhang - 2005)