Kurs:Genetische Algorithmen/Kapitel 3

Dieses Kapitel gehoert zum Kurs Genetische Algorithmen des Fachbereichs Informatik.

Übersicht

Im letzten Kapitel haben wir die Operatoren eines genetischen Algorithmus' kennengelernt. In diesem Kapitel schauen wir uns die Mutation im Detail an: wie sie in der Natur funktioniert und wie wir sie für einen genetischen Algorithmus anwenden können. Einige wichtige Eigenschaften der Mutation und deren Bedeutung werden erläutert. Es werden Mutationsoperatoren für unsere Beispielprobleme vorgestellt.

Lernziele

• Sie wissen, wie die Mutation auf der Stufe der DNS funktioniert und was sie bewirkt.
• Sie wissen, worauf bei der Mutation zu achten ist und kennen deren wichtigsten Eigenschaften und Funktionen.
• Sie können Mutationsoperatoren für verschiedene Optimierungsprobleme formulieren.

Die Mutation

Wir erinnern uns an unseren Hasen, der mit etwas längeren Ohren als seine Artgenossen geboren wurde. Die Mutation, die zu den längeren Ohren führte, war das Produkt einer zufälligen Veränderung der DNS des Hasen.

Die DNS (Desoxiribonuclein Säure, engl. DNA) ist eine lange Doppelhelix bestehend aus einer Verkettung der Basen Adenin, Thymin, Guanin und Cytosin, besser bekannt durch ihre Anfangsbuchstaben T, G, C und A. Diese lange Sequenz wird in Proteine übersetzt, welche die Bausteine der Zelle bilden. Die DNS bildet somit einen Bauplan der Zelle und des Organismus -- in unserem Fall den Hasen.

Die DNS wird bei jeder Zellteilung kopiert damit jede neue Zelle auch eine Kopie dieses Bauplanes enthält. Geschieht bei diesem Kopiervorgang -- Replikation genannt -- ein Fehler oder wird die DNS sonst irgendwie beschädigt, wird diese Veränderung bei jeder weiteren Zellteilung weitervererbt (vgl.~Abbildung~\ref{fig:genetik}).

Die DNS wird bei jeder Zellteilung kopiert und jede neue Zelle nimmt eine Kopie mit. Entsteht irgendwo eine Mutation in der DNS, wird diese an die Nachkommen weitervererbt.

Die Mutationen geschehen zufällig an zufälligen Stellen in der DNS. Es wird dabei ein zufälliges Gen in einer zufälligen Art und Weise verändert.

Beispiel:

Unsere parametrisierten Hasen von vorhin haben keine Gene. Trotzdem lässt sich die Darstellung der Parameter wie ein DNS-Strang mutieren: Wir wählen eine zufällige Position aus und verändern den Wert an dieser Position:

$h=[\ell _{\mathsf {Ohr}}=15,{\color {Red}\ell _{\mathsf {Bein}}=22},\ell _{\mathsf {Hals}}=8,\ell _{\mathsf {Zahn}}=2,\ell _{\mathsf {Nase}}=1,{\mbox{usw}}\dots ]$

Das dies nicht immer gut gehen muss, kann man sich gut vorstellen, wenn man bedenkt, was kleine, zufällige Veränderungen zum Beispiel in einem Auto, in den Schaltkreisen eines Computers oder den Buchstaben eines Aufsatzes bewirken können.

Was entscheidet, ob eine Mutation beibehalten wird oder nicht, ist deren Auswirkung auf die Zielfunktion, in unserem Falle das Nichtgefressenwerden. Verursacht eine Mutation nicht grössere sondern gar keine Ohren, hat diese kaum Chancen auf Erfolg und wird mit sehr grosser Wahrscheinlichkeit am Nichtgefressenwerden scheitern. Es ist also die Selektion, die aus der ganzen Menge von Mutationen die verwirft, die das Problem nicht besser lösen und somit auch diejenigen weiter gedeihen lässt, die das Problem besser lösen.

Mutationen, welche zu gar keiner Veränderung der Zielfunktion führen, werden natürlich auch beibehalten. Da sie aber dem Hasen keinen Vorteil verschaffen, gibt es keinen Grund, warum sie sich in der Bevölkerung durchsetzen müssen und können somit auch genau so schnell verschwinden, wie sie aufgetaucht sind.

Aufgabe:

Wie wir gesehen haben, können Mutationen überall ansetzen und unterschiedliche Auswirkungen haben. \"Uberlegen Sie sich, was für Mutationen am Bauplan einen Autos möglich wären und was diese für positive Auswirkungen hätten. Vergleichen Sie Ihre Mutationen mit denen Ihres Nachbarn und versuchen Sie, Nachteile dieser Mutationen zu finden.

Auf den ersten Blick würde es sinnvoller erscheinen, wenn man die Mutationen nicht zufällig in die DNS streuen, sondern gezielt die Gene verändern würde, die zu einem Erfolg führen könnten. Dies würde aber voraussetzen, dass die Mutation selber etwas über das Optimierungsproblem weiss. Im Falle unseres Hasen müsste sie wissen, dass es um das Nichtgefressenwerden durch Wölfe geht. Sie müsste auch wissen, dass man mit grösseren Ohren die Wölfe viel besser hören kann. Zudem müsste sie wissen, welche Gene das Wachstum oder die Grösse der Ohren steuern. Zuletzt müsste die Mutation auch noch wissen, wie man diese DNS verändern muss, damit die Ohren grösser und nicht kleiner, breiter oder dicker werden. Die Mutation müsste also sehr viel über das Problem wissen, was sie sehr komplex werden liesse.

Ein grosser Vorteil der zufälligen Mutation ist, nebst der Einfachheit, dass wirklich alle möglichen Lösungen probiert werden, egal wie unwahrscheinlich sie erscheinen. Was würde zum Beispiel passieren, wenn wir eine nur bedingt zufällige Mutation hätten, die wüsste, dass man irgendwas mit den Ohren machen muss? Sicherlich würden die Ohren viel schneller, viel effizienter werden. Leider würden aber alternative Lösungen, zum Beispiel die kräftigeren Hinterbeine oder das angepasste Fell, nie in Betracht gezogen werden. Durch die Zufälligkeit entstehen also auch ungeahnte und vorallem unkonventionelle Lösungen.

Definition:

Zusammenfassend kann man sagen, dass die Mutation eine zufällige Veränderung einer Lösung darstellt. Die Veränderung ist zufällig, weil wir a priori nicht wissen, welche Veränderungen zum Erfolg führen werden. Würden wir dies wissen, dann bräuchten wir das Problem nicht mit einem genetischen Algorithmus zu lösen. Die Zufälligkeit erlaubt es uns zudem, unvoreingenommen verschiedene Lösungsansätze zu erforschen.

Im folgenden werden wir sehen, wie sich die Mutation in unseren Beispielproblemen realisieren lässt.

Das Problem des Handelsreisenden

Die Lösungen dieses Problems bestehen aus Reihenfolgen der 6 Städte. Wir werden also nur Mutationen anschauen, welche diese Reihenfolge verändern. Wir wollen also Mutationen vermeiden, in der Städte aus der Tour verschwinden oder dann doppelt aufgeführt werden. Reihenfolgen, die nicht vollständig sind oder Städte doppelt enthalten sind keine gültigen Lösungen des Problems und sollten somit nicht erzeugt werden können.

Die einfachste, gültige Mutation besteht darin, zwei Städte in der Reihenfolge zu vertauschen. Dazu wählen wir zwei Zufallszahlen $i$ und $j$ zwischen 1 und 6 und vertauschen die Städte an diesen Stellen in der Reihenfolge (vgl.~Abbildung~\ref{fig:swap} oben). Die daraus entstehende Reihenfolge ist immer noch gültig, da sie alle Städte ohne Verdopplung enthält.

Verschiedene Mutationsoperatoren für das Problem des Handelsreisenden. Im oberen Beispiel werden die Städte an den zufällig gewählten Stellen $i$ und $j$ vertauscht. Im unteren Beispiel wird die Reihenfolge der Städte zwischen den zufällig gewählten stellen $i$ und $j$ vertauscht.

Eine andere, raffiniertere Art und Weise die Reihenfolge zu verändern, ist es, eine Teilstrecke der Route in umgekehrter Reihenfolge zu durchlaufen. Dazu wählen wir zwei Zufallszahlen $i$ und $j$ zwischen 1 und 6 und invertieren die Teilstrecke zwischen den Städten an diesen Stellen (vgl.~Abbildung~\ref{fig:swap} unten). Bildlich erklärt, wäre die Strecke ein Band, würde diese Mutation dieses an zwei Stellen durchschneiden und die Enden verkehrt zusammenfügen. Auch diese Mutation verändert nur die Reihenfolge der Städte und bildet somit gültige Lösungen.

Die Klassifikation

Die Lösungen dieses Problems sind Wertepaare für $a$ und $b$. Da es sich dabei um reellwertige Unbekannte handelt, ist die naheliegendste Mutation die, welche die Werte um

• einen zufälligen Wert erhöht oder senkt, oder
• um ein zufälliges Vielfaches vergrößert oder verkleinert.

Die erste Variante lässt sich ausführen, indem man zum Beispiel eine Zufallszahl zwischen $-0.3$ und $0.3$ wählt und zu $a$ oder $b$ addiert, bzw. davon subtrahiert. Für die zweite Variante wählt man zufällig eine Zahl zwischen $0.7$ und $1.3$ und multipliziert sie mit $a$ oder $b$.

Natürlich könnten wir auch die Werte von $a$ oder $b$ durch Zufallszahlen ersetzen oder vertauschen oder verdoppeln oder halbieren. Dies wären aber ziemlich markante Änderungen der Lösung und wenn wir uns an das Beispiel der zufälligen Mutationen an Autos, Computern und Aufsätzen zurückerinnern, dann machen kleine Schritte mehr Sinn als große Veränderungen.

Lernkontrolle

1. Die DNS eines einfachen Hefepilzes umfasst um die 2.5 Millionen Basen. Wieviele einzelne Mutationen sind auf dieser DNS möglich?
2. In unseren Beispielen haben wir nur Operatoren benutzt, welche gültige Lösungen produzieren. Gibt es in der Natur sowas wie ungültige Lösungen? Wenn ja, wie sehen diese aus und was passiert mit ihnen?
3. Erklären Sie in zwei bis drei Sätzen in Ihren eigenen Worten, warum es wichtig ist, dass die Mutation zufällig ist.
4. Was entscheidet, ob sich eine Mutation, welche gar keinen Einfluss auf die Zielfunktion hat, in der Bevölkerung ausbreitet oder nicht?

Kapiteltest

Schlagen Sie zwei Mutationsoperatoren für das Damenproblem vor.

Lösungen

Lernkontrolle

1. Jede Base der DNS ist einer der Buchstaben A, C, G oder T. Jede Base kann also von einem dieser Werte zu einem der drei anderen Mutieren. Es sind somit $2.5\,M \times 3 = 7.5\,M$ verschiedene Mutationen möglich.
2. Ungültige Lösungen kann es in der Natur auch geben. Dabei handelt es sich um Mutationen, die so schwerwiegend sind, dass das Individuum nicht ``funktioniert. Diese Individuen scheiden dann meisten aus der Bevölkerung aus, bevor sie mit der Zielfunktion in Kontakt kommen, werden also nicht Teil der Bevölkerung.
3. Die Mutation muss zufällig sein, weil wir nicht wissen, welche Werte von welchen Parametern zum Erfolg führen werden. Auch wenn wir dies wüssten, würden wir ohne Zufall etwas suchen, was wir schon kennen, also keine neuen Lösungen herausfinden.
4. Da solche Mutationen weder bevorzugt noch unterdrückt werden, entscheidet nur der Zufall über deren Bestehen.

Kapiteltest

Die Vielfalt an Mutationsoperatoren kennt eigentlich keine Grenzen. Eine einfache Mutation für das Damenproblem wäre es, eine Dame zufällig auszuwählen und sie um 1, 2 oder 3 Felder nach oben oder unten zu verschieben.

Anderseits können wir auch zufällig zwei Spalten wählen und diese vertauschen. ähnlich den Mutationen beim Problem des Handelsreisenden können wir auch ganze Blöcke von Spalten umkehren oder an der Mittelachse des Bretts spiegeln.