Kurs:Genetische Algorithmen/Kapitel 5

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen 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.

Aufgabe:

Stellen Sie sich andere Jagdstrategien der Wölfe vor. Diskutieren Sie mit Ihrem Nachbarn, welche Hasen effektiv gefressen werden. Sind es immer nur die weniger angepassten im Nichtgefressenwerden oder haben diese immer noch eine Chance zu entkommen?

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.

Beispiel:

Wir betrachten folgende Funktion $f(x)$, die es zu minimieren gilt:

Wir fangen bei $x=1$ an und wollen das Minimum bei $x=3$ erreichen. Wenn wir nur kleine Schritte machen, ist es unmöglich $x=3$ zu erreichen, ohne eine Verschlechterung des Funktionswertes $f(x)$ in Kauf zu nehmen.

Definition:

Wichtig bei der Selektion ist, dass die Bevölkerung auf eine vorgegebene Grösse reduziert wird. Die Auswahl der Individuen erfolgt gemäss ihrer Zielfunktion, jedoch auch mit einer zufälligen Komponente, damit auch nicht-optimale Individuen noch Teil der Bevölkerung bilden.

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.

Aufgabe:

Nehmen Sie zehn Zettelchen und schreiben Sie darauf die Zahlen 1 bis 10. Falten Sie die Zettel zusammen und legen Sie sie in einen Hut. Ziehen Sie dann zwei Zettel heraus und schauen Sie sich die Zahlen an. Die höhere Zahl legen Sie wieder in den Hut, die kleinere legen Sie beiseite.

Wiederholen Sie diesen Vorgang 5 mal. Sie sollten im Hut nun 5 Zettel haben. Sind Zahlen kleiner als 5 noch drin? Warum?

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.

Aufgabe:

Nehmen Sie 6 Zettel und schreiben Sie darauf die Zahlen von 1 bis 6. Falten Sie die Zettel und legen Sie sie in einen Hut. Ziehen Sie dann zufällig einen Zettel heraus und schauen Sie sich die Zahl an. Nehmen Sie dann einen Würfel und würfeln Sie eine Zahl zwischen 1 und 6. Ist die Zahl auf dem Zettel grösser oder gleich der gewürfelten Zahl, legen Sie den Zettel wieder in den Hut. Ist die Zahl auf dem Zettel kleiner, legen Sie den Zettel weg.

Wiederholen Sie diesen Vorgang bis nur 3 Zettel im Hut liegen. Sind die Zahlen 1 bis 3 noch drin? Warum?

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.

Genetische Algorithmen/Kapitel 5

Aufgabe:

Wir suchen das Minimum der Funktion aus dem obigen Beispiel

$f(x)=2-\exp(-(x-1)^{2})-2\exp(-(x-3)^{2}).$

Wir verwenden dazu einen einfachen genetischen Algorithmus:

• Wir fangen mit 3 Lösungen an, alle gleich null:

  $x_{1}=0,\quad x_{2}=0,\quad x_{3}=0$

• In jedem Durchlauf werden alle drei Lösungen kopiert und um 0.5 erhöht oder um 0.5 verkleinert. Ob eine Lösung erhöht oder verkleinert wird entscheidet ein Münzenwurf. Es entstehen daraus die Lösungen $x_{4}$, $x_{5}$ und $x_{6}$.
• Mittels eines Selektionsoperators wird dann die Bevölkerung wieder auf 3 Lösungen reduziert. Sie können eine Taschenrechner benutzen, um die Funktion auszuwerten oder den Funktionswert aus der Zeichnung im letzten Beispiel ablesen.

Führen Sie obigen Algorithmus mehrmals aus mit folgenden Selektionsoperatoren:

1. Einem elitären Selektionsoperator, der nur die besten Lösungen auswählt (sprich die $x$, die den kleinsten Wert der Zielfunktion ergeben).
2. Einem Turnier-Selektionsoperator, der zwei Lösungen zufällig auswählt und die schlechtere der beiden (sprich die Lösung, welche den höheren Wert der Zielfunktion ergibt) eliminiert. Benutzen Sie für die zufällige Wahl einen Würfel.

Welche Lösungen werden für beiden Selektionsoperatoren erreicht? Was stellen Sie fest?

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.