Information Technology Reference
In-Depth Information
Sitze bekannt sind, benutzt werden. Dazu gehören das Verfahren der größten Reste,
das Hare-Niemeyer-Verfahren, das d'Hondtsche Verfahren, usw.
Will man nicht auf die Glücksradauswahl verzichten, so kann man folgenden
Ansatz wählen: Für jedes Individuum, dass einen Nachkommen erhält, verringert
man seine Fitness um einen bestimmten Betrag f . Wird die Fitness eines Individu-
ums dadurch negativ, so erhält es keine weiteren Nachkommen. Ein Prinzip für die
Wah l von f ist, dass das beste Individuum höchstens eine festgelegte Zahl k von
Nachkommen erhält:
f = 1 / k max{ f ( s ) | s pop( t )}.
11.2.4 Rangbasierte Selektion
Bei einer rangbasierten Selektion werden die Individuen nach ihrer Fitness abstei-
gend sortiert. So erhält jedes Individuum einen Rang in der Population. Die Idee
kommt aus der Statistik, wo verteilungsfreie Verfahren, wie die Rangkorrelation
genutzt werden. Über der Rangskala wird eine Wahrscheinlichkeitsverteilung de-
finiert: Je kleiner die Rangnummer, desto größer die Wahrscheinlichkeit. Anschlie-
ßend wird mit dieser Verteilung eine Glücksradauswahl durchgeführt. Die Vortei-
le dieses Verfahrens sind eine weitgehende Vermeidung des Dominanzproblems,
da der Wert der Fitnessfunktion nicht direkt die Auswahlwahrscheinlichkeit beein-
flusst, sowie eine bequeme Steuerung des Selektionsdrucks über die Wahrscheinlich-
keitsverteilung auf der Rangskala. Der Nachteil ist, dass man sämtliche Individuen
sortieren muss, was einen Aufwand von O (|pop|·log 2 |pop|) bedeutet.
11.2.5 Turnierauswahl
Bei der Turnierauswahl werden für die Auswahl eines Individuums der Zwischen-
population k Individuen zufällig aus der Population gezogen wobei die Turniergrö-
ße k {2, 3, . . . , |pop|}.DiesesSelektionsverfahrenkannmitoderohneZurücklegen
durchgeführt werden. Generell berücksichtigt man bei der Auswahl die Fitnesswer-
te der Individuen nicht. Die Individuen tragen buchstäblich ein Turnier aus, welches
das beste Individuum gewinnt. Der Turniersieger erhält einen Nachkommen in der
Zwischenpopulation. Anschließend legt man alle Individuen des Turniers (auch der
Sieger) in die aktuelle Population zurück. Die Vorteile der Turnierauswahl sind eine
weitgehende Vermeidung des Dominanzproblems, da der Wert der Fitnessfunktion
nicht direkt die Auswahlwahrscheinlichkeit beeinflusst, sowie eine elegante Steue-
rung des Selektionsdrucks über die Turniergröße. Als Modifikation kann man die re-
lative Fitness der Turnierteilnehmer die Gewinnwahrscheinlichkeit bestimmen, was
einer Glücksradauswahl eines Individuums im Turnier entspräche.
11.2.6 Elitismus
Wie wir bereits erwähnt haben, ist nur im Erwartungswertmodell (oder einer sei-
ner Varianten) sichergestellt, dass das beste Individuum in die Zwischenpopulation
Search WWH ::




Custom Search