Kurs:Genetische Algorithmen/Kapitel 5

Dieses Kapitel gehoert zum Kurs Kurs:Genetische Algorithmen/Kapitel 5 des Fachbereichs Informatik.

Übersicht

In diesem Kapitel schauen wir uns zuerst an, wie die Selektion in der Natur funktioniert und beschreiben deren wichtigste Merkmale. Diese Merkmale werden dann auf Selektionsoperatoren für genetische Algorithmen angewendet und wir beschreiben zwei Selektionsoperatoren mit ihren Eigenschaften.

Lernziele

• Sie wissen, welche Rolle die Selektion in der Natur spielt.
• Sie wissen, wie die Selektion in der Natur funktioniert.
• Sie kennen zwei verschiedene Selektionsoperatoren und ihre Eigenschaften.
• Sie können einen Selektionsoperator im Rahmen eines genetischen Algorithmus' anwenden.

Die Selektion

Die Lösungen des Nichtgefressenwerden-Problems werden bei unseren Hasen durch den Wolf ausgewertet. In regelmässigen Abständen schnappt er sich einen Hasen aus der Bevölkerung und verhindert somit dessen Weiterbestehen.

Dadurch, dass sich ein Hase nicht weiter fortpflanzen kann -- es wurde ja gefressen und steht somit zur Paarung nicht mehr zur Verfügung -- werden auch seine Eigenschaften nach und nach aus der Bevölkerung eliminiert. Umgekehrt dazu pflanzen sich die Hasen fort, die nicht gefressen wurden und verbreiten so ihre Eigenschaften in der Bevölkerung. Die Bevölkerung wird also gegenüber dem Nichtgefressenwerden dadurch optimiert, dass der Wolf gelegentlich schlechtere Lösungen verspeist.

Der Wolf könnte dies auf unterschiedliche Art und Weise machen: Trifft er zum Beispiel auf einer Lichtung auf zwei Hasen welche sich von der Bevölkerung entfernt haben und hat er zufällig gerade Hunger, wird er den Hasen fressen, der sich am wenigsten schnell aus dem Staub macht.

Welche zwei Hasen aus der Bevölkerung er auf seinem Weg trifft ist eigentlich zufällig und so ist es auch möglich, dass er nie mit allen Bekanntschaft macht. Diese zufällige Komponente erlaubt es einigen Hasen, welche ihren Kollegen im Nichtgefressenwerden eigentlich unterlegen wären, trotzdem zu überleben.

Eine andere Strategie des Wolfs könnte sein, sich mit einzelnen Hasen anzulegen. Er pickt zufällig einen Hasen aus und versucht diesen zu fangen. Die Wahrscheinlichkeit, mit der dem Hasen die Flucht gelingt, hängt direkt von seinen Eigenschaften ab. Ein Hase mit kräftigeren Hinterbeinen wird demzufolge mit einer geringeren Wahrscheinlichkeit gefressen als einer mit normalen Hinterbeinen. Auch mit dieser Strategie ist es möglich, dass ein Hase, der seinen Artgenossen eigentlich unterlegen wäre, trotzdem überlebt. Sei es, weil er nie dem Wolf gegenüberstehen musste oder weil er dabei ganz einfach Glück hatte.

Wichtig ist bei beiden Strategien, dass auch einzelne Individuen, die weniger gut sind als ihre Artgenossen, trotzdem eine Überlebenschance haben. Aber warum ist dies wichtig?

Auf dem ersten Blick würde es sinnvoll erscheinen, eine elitäre Selektion durchzuführen, bei der ausschliesslich die "besten" Hasen überleben. Obwohl dies verlockend und sogar vielversprechend klingt, birgt es einen bedeutenden Nachteil: Stellen wir uns mal den ersten Hasen vor, der etwas längere Hinterbeine hatte. Die Beine wurden länger, aber die Muskulatur vielleicht noch nicht. Längere aber nicht kräftigere Hinterbeine sind nicht unbedingt ein Vorteil -- sie sind eher ein Nachteil. Wenn aber der Wolf immer nur ausschliesslich die schwächeren Hasen fressen würde, hätte unser langbeiniger Hase keine Chance, im Laufe der Generationen auch die passende Beinmuskulatur zu entwickeln. Die Zwischenlösungen, die vielleicht zu einer besseren Lösung führen, müssen nicht zwangsläufig gut oder optimal sein. Es ist deswegen wichtig, dass diese auch eine Chance haben und nicht sofort der Selektion zum Opfer fallen.

Für unsere genetische Algorithmen werden wir folgende zwei Formen der Selektion verwenden:

Der Turnier-Selektionsoperator

Der Turnier-Selektionsoperator entspricht dem ersten Beispiel mit den Hasen und dem Wolf. Es werden zufällig zwei Lösungen aus der Bevölkerung gewählt. Beide Lösungen werden anhand der Zielfunktion ausgewertet. Die mit dem schlechteren Resultat wird aus der Bevölkerung genommen und die andere wandert zurück in die Bevölkerung. Dieser Vorgang wird mehrmals wiederholt, bis die Bevölkerung eine vorgeschriebene Zielgrösse erreicht hat.

Bei diesem Selektionsoperator ist zu bemerken, dass die "beste" Lösung einer Bevölkerung niemals ausscheiden kann. Wird sie zufällig für einen Vergleich gewählt, gewinnt sie immer.

Es gibt aber keine Garantie, dass die schlechteren Lösungen aus der Bevölkerung verschwinden. Es ist nämlich auch möglich, dass sie zufällig nie für einen Vergleich aus der Bevölkerung gezogen werden oder nur für Vergleiche mit noch schlechteren Lösungen. Analog dazu kann auch die zweit- oder drittbeste Lösung ausscheiden, wenn sie zufälligerweise mit der besten Lösung gezogen wurde.

Der Zufalls-Selektionsoperator

Beim Zufalls-Selektionsoperator wird, analog dem zweiten Beispiel mit den Hasen und dem Wolf, immer eine Lösung zufällig ausgesucht und mit einer gewissen Wahrscheinlichkeit aus der Bevölkerung genommen. Diese Wahrscheinlichkeit hängt vom Wert der Zielfunktion dieser Lösung ab. Sie sollte so gewählt werden, dass bessere Lösungen eine höhere Wahrscheinlichkeit haben zu entkommen als schlechtere.

Eine Möglichkeit, diese Wahrscheinlichkeit zu wählen ist, den Wert der Zielfunktion für die beste und für die schlechteste Lösung der Bevölkerung zu nehmen. Nennen wir diese $z_b$ und $z_s$. Wir wählen nun eine Lösung aus der Bevölkerung und eine Zufallszahl zwischen $z_s$ und $z_b$. Ist diese Zufallszahl kleiner als der Wert der Zielfunktion der zufällig ausgewählten Lösung, so scheidet die Lösung nicht aus und bleibt somit in der Bevölkerung. Ist die Zufallszahl hingegen grösser, wird die Lösung aus der Bevölkerung herausgenommen.

Bei dieser Strategie bleibt die beste Lösung erhalten und die schlechteste Lösung wird immer ausscheiden, sofern sie ausgewählt wird. Bei Optimierungsproblemen, in denen die Zielfunktion minimiert werden muss, muss man umgekehrt entscheiden, also die Lösung aus der Bevölkerung nehmen, wenn die Zielfunktion kleiner ist.

Lernkontrolle

1. Was würde bei einer rein zufälligen Selektion passieren, d.h. wenn völlig zufällig Individuen aus der Bevölkerung eliminiert werden?
2. Was ist die wichtigste Eigenschaft einer guten Selektion? Warum ist diese Eigenschaft wichtig?

Kapiteltest

Beschreiben Sie den Selektionsoperator, der während Ihrer Schulzeit angewendet wird. Worin unterscheidet sich dieser von den beschriebenen Selektionsoperatoren?

Lösungen

Lernkontrolle

1. Ist die Selektion zufällig, so werden die "schlechteren" Lösungen nicht bevorzugt eliminiert oder die "besseren" Lösungen bevorzugt. Es findet somit kein Selektionsdruck statt und die Lösungen werden von Generation zu Generation nicht besser.
2. Die Selektion muss eine zufällige Komponente haben, damit auch mögliche suboptimale Zwischenlösungen eine Chance haben.

Kapiteltest

In der Schule wird jede Schülerin/jeder Schüler einzeln ausgewertet, d.h. es kann sich, im Gegensatz zu den vorgestellten Selektionsoperatoren, niemand drücken.

Anderseits wird man nach einem misslungenen Semester nicht sofort aus der Bevölkerung (Schule) geworfen, sondern erhält in der Form des provisorischen Bestehens eine zweite Chance. Somit können schlechtere Semester (Zwischenlösungen) wieder ausgebügelt werden.