Kurs:Genetische Algorithmen/Kapitel 2

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht

Wir wissen nun, was ein Optimierungsproblem ist. Ein gutes Beispiel eines kontinuierlichen Optimierungsproblems ist die Natur. Durch fortlaufende Mutation, Rekombination und Selektion werden Individuen (Pflanzen oder Tiere) erzeugt, welche sich immer besser ihrer Umgebung anpassen. Wir werden uns diese Mechanismen anhand vom Beispiel des Hasen anschauen und verallgemeinern. Die gleichen Mechanismen lassen sich für Optimierungsprobleme anwenden.

Lernziele

• Nach dem Bearbeiten dieses Kapitels kennen Sie die Hauptkomponenten eines genetischen Algorithmus.
• Sie wissen, wie diese Mechanismen in der Natur funktionieren und können diese auch in anderen Optimierungsvorgängen wiedererkennen.
• Sie wissen, was die wichtigsten Operatoren sind und was sie für eine Funktion haben.

Generelles Schema

Optimierungsprobleme sind in der Natur allgegenwärtig. Viele Waldtiere zum Beispiel, sehen sich ständig mit dem Problem konfrontiert, nicht von Wölfen gefressen zu werden. Eine der interessanteren Lösungen dieses Problems ist der Hase.

Als "Hasen" bezeichnen wir eine Menge unterschiedlicher Individuen (ja, wie bei den Menschen ist jeder Hase anders). Obwohl sich diese Individuen unterscheiden, bilden sie zusammen eine Bevölkerung.

Definition:

Eine Bevölkerung ist, im Kontext der genetischen Algorithmen, eine Menge von Lösungen. In unserem Beispiel sind die Lösungen die einzelnen Hasen. Die Bevölkerung ist die Menge dieser individuellen Lösungen, welche wir der Spezies Hase zuordnen.

Hasen sind mit einer Vielzahl an Eigenschaften ausgestattet, welche ihnen erlauben, dem Gefressenwerden durch Wölfe möglichst zu entgehen. Mit ihren langen Ohren hören sie den Wolf zum Beispiel schon von weitem kommen. Ist der Hase gerade beschäftigt oder sonst irgendwie abgelenkt und er verpasst die frühzeitige Flucht, hilft ihm oft sein Fell, welches meist seiner Umgebung ähnlich gefärbt ist. Sitzt er zufällig noch in der falschen Umgebung oder hat sonst irgendwie dummerweise den Wolf auf sich aufmerksam gemacht, so kann er immer noch mit seinen langen, kräftigen Hinterbeinen davonrennen.

Diese drei Eigenschaften -- die langen Ohren, das an die Umgebung angepasste Fell und die kräftigen Hinterbeine -- sind alle im Laufe der Jahrmillionen entstanden und zwar durch Mutation, Rekombination und Selektion.

Beispiel:

Wir können unsere Hasen zwecks der Optimierung mal ganz anders darstellen, und zwar als einen Satz von Werten,

$[\ell _{\mathsf {Ohr}}=\dots ,\ell _{\mathsf {Bein}}=\dots ,\ell _{\mathsf {Hals}}=\dots ,\ell _{\mathsf {Zahn}}=\dots ,\ell _{\mathsf {Nase}}=\dots ,{\mbox{usw}}\dots ]$

welche die Eigenschaften unseres Hasen darstellen (z.B. wäre $\ell _{\mathsf {Ohr}}$ die Länge der Ohren). Im folgenden werden wir zwei Hasen begleiten:

$h_{1}\quad =\quad [\ell _{\mathsf {Ohr}}=15,\ell _{\mathsf {Bein}}=21,\ell _{\mathsf {Hals}}=9,\ell _{\mathsf {Zahn}}=2,\ell _{\mathsf {Nase}}=1,{\mbox{usw}}\dots ]$

$h_{2}\quad =\quad [\ell _{\mathsf {Ohr}}=12,\ell _{\mathsf {Bein}}=19,\ell _{\mathsf {Hals}}=7,\ell _{\mathsf {Zahn}}=2,\ell _{\mathsf {Nase}}=1,{\mbox{usw}}\dots ]$

Die Zielfunktion $f_{\mathsf {NGW}}$, welche das Nichtgefressenwerden quantifiziert, könnten wir dann schreiben als

$f_{\mathsf {NGW}}(\ell _{\mathsf {Ohr}},\ell _{\mathsf {Bein}},\ell _{\mathsf {Hals}},\ell _{\mathsf {Zahn}},\ell _{\mathsf {Nase}},{\mbox{usw}}\dots )=\dots$

Diese Funktion liefert einen Wert, welcher von den verschiedenen Eigenschaften des Hasen abhängt, zum Beispiel

$f_{\mathsf {NGW}}(h_{1})\quad =\quad 35$

$f_{\mathsf {NGW}}(h_{2})\quad =\quad 32$

Aufgabe:

Hasen sind nicht die einzigen Lebewesen, die das Problem des Nichtgefressenwerdens optimieren. Wie wird dieses Problem von anderen Tierarten, zum Beispiel dem Elefanten oder der Fruchtfliege, gelöst?

Mutationen haben zum Beispiel bei kurzohrigen Ur-Hasen dazu geführt, dass beim einen oder anderen Artgenossen durch eine zufällige Veränderung des Erbgutes längere Ohren gewachsen sind. Parallel dazu gab es sicher auch Hasen mit längeren Zungen, Nasen oder Hälse jedoch haben es irgendwie nur die Hasen mit längeren Ohren geschafft, obwohl diese vielleicht im Vergleich zu ihren anderen Artgenossen ziemlich blöd ausgesehen haben mögen.

Definition:

Eine Mutation ist eine zufällige Veränderung innerhalb eines der Merkmale eines Individuums. Bei unseren natürlichen Hasen ist eine Mutation eine zufällige Veränderung der DNS. Bei unseren parametrisierten Hasen ist es eine zufällige Veränderung eines der Parameter.

Beispiel:

Bei unseren parametrisierten Hasen ist eine Mutation eine beliebige Veränderung eines der Parameter aus

$[\ell _{\mathsf {Ohr}}=\dots ,\ell _{\mathsf {Bein}}=\dots ,\ell _{\mathsf {Hals}}=\dots ,\ell _{\mathsf {Zahn}}=\dots ,\ell _{\mathsf {Nase}}=\dots ,{\mbox{usw}}\dots ]$

Zum Beispiel wird dann die Zahnlänge $\ell _{\mathsf {Zahn}}$ um 10% erhöht oder die Beinlänge $\ell _{\mathsf {Bein}}$ um 5% verkürzt. So könnte unser Hase

$h_{1}=[\ell _{\mathsf {Ohr}}=15,\ell _{\mathsf {Bein}}=21,\ell _{\mathsf {Hals}}=9,\ell _{\mathsf {Zahn}}=2,\ell _{\mathsf {Nase}}=1,{\mbox{usw}}\dots ]$

nach einer Mutation zum Beispiel wie folgt aussehen:

$h_{1}^{\star }=[{\color {Red}\ell _{\mathsf {Ohr}}=17},\ell _{\mathsf {Bein}}=21,\ell _{\mathsf {Hals}}=9,\ell _{\mathsf {Zahn}}=2,\ell _{\mathsf {Nase}}=1,{\mbox{usw}}\dots ]$

Die veränderten Parameter ergeben dann einen anderen Wert der Zielfunktion $f_{\mathsf {NGW}}$.

Der Grund warum Hasen heute lange Ohren und nicht lange Zungen haben liegt in der Selektion: Die Hasen mit längeren Ohren und deren Nachkommen konnten die Wölfe von weither kommen hören und früher fliehen als ihre mit weniger grosszügigen Hörorganen ausgestatteten Kollegen. Weswegen sie auch weniger oft gefressen wurden. Längere Zungen, Nasen oder Hälse brachten keinen solchen Vorteil, setzten sich also nie wirklich durch (abgesehen davon, dass sie wahrscheinlich auch unheimlich blöd ausgesehen haben).

Definition:

Die Selektion ist ein Vorgang, in dem die Bevölkerung anhand eines bestimmten Kriteriums reduziert wird. Für unsere natürlichen Hasen bedeutet dies, dass jene Hasen, die im Nichtgefressenwerden am wenigsten gut abschneiden vom Wolf gefressen werden und somit nicht mehr zur Bevölkerung gehören. Bei unseren parametrisierten Hasen werten wir deren Zielfunktion aus und verwerfen die Lösungen, die weniger gut abschneiden.

Ein wichtiges Merkmal der Selektion ist, dass sich Hasen, die vom Wolf gefressen wurden, nicht mehr paaren können. Somit werden deren Eigenschaften, welche weniger gut im Nichtgefressenwerden waren, nach und nach aus der Bevölkerung eliminiert.

Beispiel:

Bei unseren parametrisierten Hasen funktioniert die Selektion über die Zielfunktion $f_{\mathsf {NGW}}$. Hasen, welche einen niedrigeren Wert dieser Funktion ergeben, werden eher aus der Bevölkerung genommen. Für unsere zwei Hasen $h_{1}$ und $h_{2}$ aus dem obigen Beispiel bedeutet das, dass $h_{1}$ mit dem höheren Wert der Funktion für das Nichtgefressenwerden bessere Überlebenschancen hat als $h_{2}$.

Aufgabe:

Nicht nur bei den Hasen wurden Körperteile länger: Giraffen haben im Laufe der Zeit längere Hälse und Beine entwickelt. Weswegen könnten sich diese durchgesetzt haben?

Parallel zur ganzen Ohren-Geschichte entwickelten sich auch andere Nager (von denen die Hasen ursprünglich abstammen) nach ähnlichen Kriterien mit angepasstem Fell und längeren Hinterbeinen. Diese hatten einen ähnlichen Vorteil gegenüber ihren Artgenossen und setzten sich auch dementsprechend durch, bis sich eines Tages zwei Hasen ineinander verliebten, die unterschiedliche Merkmale hatten, zum Beispiel er mit langen Ohren und sie mit kräftigen Hinterbeinen. Obwohl die Mehrheit der Kinder dieses ungleichen Paares nur eine oder gar keine der guten Eigenschaften der Eltern mitnahmen, erwischten einige durch Rekombination beide, nämlich sowohl lange Ohren als auch kräftige Hinterbeine. Obwohl sie als Kinder wahrscheinlich von ihren Artgenossen wegen ihres komischen Aussehens gehänselt wurden hörte der Spass auf, als die ersten Wölfe wieder auftauchten, und sie mit doppelten Vorteil davoneilen konnten, während ihre Spielkameraden nach und nach alle gefressen wurden. Irgendwann paarten sich dann diese Hasen mit denen mit dem angepassten Fell und es entstanden die heutigen Hasen.

Definition:

Die Rekombination ist ein Vorgang, welcher aus den Merkmalen zweier Individuen ein neues Individuum erzeugt. Bei den natürlichen Hasen geschieht die Rekombination bei der Paarung zweier unterschiedlicher Hasen, bei der sich die Eigenschaften im neu gezeugten Hasen vermischen. Bei unseren parametrisierten Hasen können wir die Rekombination simulieren, indem wir die Werte zweier Hasen zufällig zu einem neuen Hasen vermischen.

Beispiel:

Bei unseren parametrisierten Hasen kann man sich die Rekombination so vorstellen, dass man aus zwei Hasen

$h_{1}\quad =\quad [{\color {Red}\ell _{\mathsf {Ohr}}=\dots },{\color {Red}\ell _{\mathsf {Bein}}=\dots },{\color {Red}\ell _{\mathsf {Hals}}=\dots },{\color {Red}\ell _{\mathsf {Zahn}}=\dots },{\mbox{usw}}\dots ]$

$h_{2}\quad =\quad [{\color {Blue}\ell _{\mathsf {Ohr}}=\dots },{\color {Blue}\ell _{\mathsf {Bein}}=\dots },{\color {Blue}\ell _{\mathsf {Hals}}=\dots },{\color {Blue}\ell _{\mathsf {Zahn}}=\dots },{\mbox{usw}}\dots ]$

durch zufälliges Vermischen der Werte (zum Beispiel $\ell _{\mathsf {Ohr}}$ von $h_{1}$ und $\ell _{\mathsf {Bein}}$ von $h_{2}$) einen neuen Hasen $h_{\mathsf {neu}}$ erzeugt, zum Beispiel:

$h_{\mathsf {neu}}=[{\color {Red}\ell _{\mathsf {Ohr}}=\dots },{\color {Blue}\ell _{\mathsf {Bein}}=\dots },{\color {Red}\ell _{\mathsf {Hals}}=\dots },{\color {Blue}\ell _{\mathsf {Zahn}}=\dots },{\mbox{usw}}\dots ]$

Das Problem des Nichtgefressenwerdens wird durch einen fortdauernden Zyklus von Mutation, Rekombination und Selektion optimiert (vgl.~Abbildung~\ref{fig:schema}). Dies ist auch das generelle Schema und die Basis der genetischen Algorithmen.

Der Name ruht daher, dass die Information für jede biologische ``Lösung des Nichtgefressenwerdens in den Genen (Orte in der DNS, die die Information für ein bestimmtes Protein enthalten) der Lebewesen verschlüsselt ist. Analog der genetischen Vorgänge wie Mutation und Rekombination werden auch in den genetischen Algorithmen immer andere Lösungen zu einem Problem (nicht zwangsläufig das Gefressenwerden -- es gibt auch andere Probleme) erzeugt.

Das generelle Schema eines genetischen Algorithmus.

Bei einem genetischen Algorithmus wird eine Anfangsbevölkerung von Lösungen (im Beispiel die einzelnen Hasen) mittels Mutation und Rekombination vergrössert. Mittels Selektion werden weniger gute Lösungen aus der Bevölkerung wieder herausgenommen. Am Ende erhält man eine neue, im Durchschnitt bessere Bevölkerung. Jeden Durchlauf dieses Vorgangs nennen wir eine Iteration. Die daraus entstandene Bevölkerung nennen wir eine Generation.

Definition:

Ein Operator ist ein Vorgang, welcher die Bevölkerung der Lösungen verändert. Somit sind die Mutation, die Rekombination und die Selektion -- sowohl bei den natürlichen als auch bei den parametrisierten Hasen -- Operatoren.

Dieser Optimierungsvorgang wurde erstmals 1954 von Nils Aall Barricelli verwendet, um kartenspielende Automata gegeneinander zu optimieren. 1958 stellte der Genetiker Alex Fraser ein Programm vor, welches eine Bevölkerung mit künstlichen Genen nach einer betimmten Zielfunktion optimierte. 1975 schrieb John Holland, ein Professor der Psychologie, Elektrotechnik und der Informatik, das Buch "Adaptation in Natural and Artificial Systems", welches das Fundament der genetischen Algorithmen legte. Heutzutage werden genetische Algorithmen überall dort angewendet, wenn man ein Optimierungsproblem nicht exakt lösen kann. Dies ist bei vielen grossen Logistik-, Budgetierungs-, Planungs- und Klassifikationproblemen der Fall.

Lernkontrolle

1. Was ist ein Operator?
2. Welches sind die Hauptkomponenten eines genetischen Algorithmus'?
3. Welcher Operator hält die Grösse der Bevölkerung mehr oder weniger konstant?
4. Die Lösung eines speziellen parametrisierten Hasen besteht aus 10 Werten. Wieviele verschiedene Rekombinationen aus zwei unterschiedlichen Lösungen sind möglich?
5. Was würde passieren, wenn man bei einer Optimierung die
   • Mutation
   • Rekombination
   • Selektion

   auslassen würde?

6. Grippeviren sind keine Lebewesen, sie schaffen es jedoch, sich jedes Jahr den bestehenden Impfungen anzupassen: Jedes Jahr erscheint ein neuer Grippevirus, der den Impfungen vom letzten Jahr gegenüber resistent wird und die Herzen der Taschentuchhersteller erfreut. Identifizieren Sie für diesen Zyklus die vorhandenen Operatoren!

Kapiteltest

Die Schweizer Super-League kann als Optimierungsproblem verstanden werden, in der die Zielfunktion die Platzierung jeder Mannschaft in der Punktetabelle ist. Benennen Sie darin

1. Die Lösungen
2. Die Bevölkerung
3. Einen möglichen Mutationsoperator
4. Einen möglichen Rekombinationsoperator
5. Einen möglichen Selektionsoperator

Lösungen

Lernkontrolle

1. Ein Operator ist ein Vorgang, welcher die Bevölkerung der Lösungen verändert.
2. Die Hauptkomponenten sind die Mutation, die Rekombination, und die Selektion.
3. Der Selektionsoperator.
4. Bei jedem Parameter können wir entweder den Wert des Vaters oder der Mutter nehmen -- wir haben also zwei Möglichkeiten. Auf 10 Parameter angewendet ergibt das $2^{10}=1024$ mögliche Rekombinationen.
5. 1. Ohne Mutation bleiben die Lösungen immer gleich. Hat man von Anfang an unterschiedliche Lösungen in der Bevölkerung, so werden diese zwar rekombiniert, es entstehen aber keine Änderungen in den einzelnen Unbekannten.
   2. Ohne Rekombination könnte nur eine Verbesserung nach der anderen in der Bevölkerung eintreten). Entstehen zwei Verbesserungen gleichzeitig, vermischen sie sich nie und es können sich zwei gleichwertige aber verschiedene Gruppen in der Bevölkerung bilden, die niemals voneinander profitieren würden. Dies würde die Optimierung wesentlich verlangsamen.
   3. Ohne Selektion werden die schlechten Mutationen und Rekombinationen nicht von den guten unterschieden. Die Bevölkerung würde dann nicht mehr ein Maximum oder Minimum anstreben, sondern sich immer mehr und mehr diversifizieren.
6. Viren haben, obwohl sie keine eigenständigen Lebewesen sind, auch eine DNS. Der Mutationsoperator ist also die gewöhliche DNS-Mutation, wie wir sie bei unseren Hasen kennen. Der Selektionsoperator ist die Grippeimpfung, welche alle Viren aus dem Verkehr zieht, welche nicht immun dagegen sind. Die Rekombination tritt nur selten auf, indem sich ein Mensch mit zwei verschiedenen Viren gleichzeitig infiziert und sich diese auch zu einem neuen Virus vermischen können. Man nimmt an, dass die Vogelgrippe so entstanden ist.

Kapiteltest

1. Die Lösungen sind die einzelnen Mannschaften. Die Unbekannten der Lösungen sind die einzelnen Spieler, aber auch die Taktik und somit auch der Trainer der Mannschaft.
2. Die Bevölkerung sind die Mannschaften, die in der Liga mitspielen.
3. Mutationen sind kleine Veränderungen der Lösung. Diese geschehen, wenn zum Beispiel eine Mannschaft einen Spieler aus der Zweitmannschaft oder den Junioren raufholt, um einen anderen Spieler zu ersetzen. Auch ein Trainerwechsel ist eine Mutation. Nicht zuletzt sind auch die Mannschaften, die am Anfang der Saison in die Super-League aufsteigen, neue Lösungen und stellen auch eine Mutation dar.
4. Eine Rekombination geschieht dann, wenn Mannschaften Spieler oder Trainer austauschen. Eine Lösung übernimmt so Teile einer anderen Lösung. Auch das Zusammenfügen zweier Mannschaften nach einem Bankrott oder einer sonstigen Pleite kann als Rekombination aufgefasst werden.
5. Der Selektionsoperator ist in den letzten zwei Tabellenplätzen zu finden. Die Mannschaften, die am wenigsten Punkte in der Saison erzielt haben, werden relegiert und somit aus der Bevölkerung genommen.