Die Evolution ist der leistungsfähigste Prozess der Natur. Lebewesen passen sich - scheinbar von selbst - von Generation zu Generation immer besser den Bedingungen ihrer Umgebung an. Die Idee der ständigen Weiterentwicklung wurde in der Informatik aufgenommen und in Form von genetischen Algorithmen realisiert. Ziel dieser Arbeit ist es, dem Leser die Gruppe der genetischen Algorithmen näher zu bringen. Die Arbeit ist wie folgt aufgebaut:
Das zweite Kapitel erläutert Grundbegriffe der Genetik und ihre Bedeutung in der Informatik. Im dritten Kapitel wird die generelle Struktur genetischer Algorithmen vorgestellt. Hierzu zählen die Elementaroperationen, die auch bei der biologischen Evolution stattfinden. Das vierte Kapitel bildet den Schwerpunkt dieser Arbeit. Es befasst sich mit den theoretischen Grundlagen, die die Funktionalität genetischer Algorithmen nachweisen. Im fünften Kapitel demonstrieren wir eine praktische Anwendung genetischer Algorithmen. Wir zeigen, wie genetische Algorithmen zur Lösung des n-Damen Problems beitragen können. Abschließend fassen wir im sechsten Kapitel die in dieser Arbeit gewonnenen Erkenntnisse zusammen und betrachten Möglichkeiten und Begrenzungen genetischer Algorithmen bei der praktischen Umsetzung.
Bevor wir mit der eigentlichen Arbeit beginnen, sollten wir zunächst Optimierungsprobleme als Einsatzgebiet genetischer Algorithmen betrachten. Optimierungsprobleme zeichnen sich dadurch aus, dass sie mehr als eine richtige Lösung besitzen, wobei unterschiedliche Lösungen ebenfalls unterschiedlich gut sein können. Bei dieser Art von Problem ist es meist schwer, einen Algorithmus zu finden, der die beste Lösung in einer akzeptablen Zeit ermittelt. Genau hier setzen genetische Algorithmen an. Sie erzeugen zunächst eine Menge aus zufälligen Lösungen und lassen diese Menge nach den Prinzipien der Evolution weiterentwickeln (und somit optimieren), bis sich eine genügend gute Lösung herausstellt. Durch genetische Algorithmen ist es oftmals möglich, sogenannte NP-Schwere - also nicht effizient lösbare - Probleme in kurzer Zeit mit einem zufriedenstellenden Ergebnis zu berechnen.
Inhaltsverzeichnis
1. Einleitung
2. Grundbegriffe der Genetik
3. Der genetische Algorithmus
3.1. Elementaroperationen
3.1.1. Kreuzung
3.1.2. Mutation
3.1.3. Selektion
4. Das Schema-Theorem
4.1. Definiton des Begriffes ”Schema“
4.2. Herleitung des Schema-Theorems
4.2.1. Das Theorem
4.2.2. Selektion
4.2.3. Kreuzung
4.2.4. Mutation
4.3. Interpretation
5. Eine Anwendung genetischer Algorithmen : Das n-Damen Problem
6. Fazit
A. Literatur
B. Abbildungen
C. Abbildungsverzeichnis
D. Testreihe der Anwendung
E. Quellcode der Anwendung
1. Einleitung
Die Evolution ist der leistungsfähigste Prozess der Natur. Lebewesen passen sich - scheinbar von selbst - von Generation zu Generation immer besser den Bedingungen ihrer Umgebung an. Die Idee der ständigen Weiterentwicklung wurde in der Informatik aufgenommen und in Form von genetischen Algorithmen realisiert. Ziel dieser Arbeit ist es, dem Leser die Gruppe der genetischen Algorithmen näher zu bringen. Die Arbeit ist wie folgt aufgebaut:
Das zweite Kapitel erläutert Grundbegriffe der Genetik und ihre Bedeutung in der Infor- matik. Im dritten Kapitel wird die generelle Struktur genetischer Algorithmen vorgestellt. Hierzu zählen die Elementaroperationen, die auch bei der biologischen Evolution stattfinden. Das vierte Kapitel bildet den Schwerpunkt dieser Arbeit. Es befasst sich mit den theoreti- schen Grundlagen, die die Funktionalität genetischer Algorithmen nachweisen. Im fünften Kapitel demonstrieren wir eine praktische Anwendung genetischer Algorithmen. Wir zei- gen, wie genetische Algorithmen zur Lösung des n-Damen Problems beitragen können. Ab- schließend fassen wir im sechsten Kapitel die in dieser Arbeit gewonnenen Erkenntnisse zusammen und betrachten Möglichkeiten und Begrenzungen genetischer Algorithmen bei der praktischen Umsetzung.
Bevor wir mit der eigentlichen Arbeit beginnen, sollten wir zunächst Optimierungsproble- me als Einsatzgebiet genetischer Algorithmen betrachten. Optimierungsprobleme zeichnen sich dadurch aus, dass sie mehr als eine richtige Lösung besitzen, wobei unterschiedliche Lösungen ebenfalls unterschiedlich gut sein können. Bei dieser Art von Problem ist es meist schwer, einen Algorithmus zu finden, der die beste Lösung in einer akzeptablen Zeit ermit- telt. Genau hier setzen genetische Algorithmen an. Sie erzeugen zunächst eine Menge aus zufälligen Lösungen und lassen diese Menge nach den Prinzipien der Evolution weiterent- wickeln (und somit optimieren), bis sich eine genügend gute Lösung herausstellt. Durch genetische Algorithmen ist es oftmals möglich, sogenannte NP-Schwere - also nicht effizient lösbare - Probleme in kurzer Zeit mit einem zufriedenstellenden Ergebnis zu berechnen.
Als Literatur wird unter anderem verwendet:
- Das Buch Evolutionäre Algorithmen von I. Gerdes, F. Klawonn und R. Kruse [GKK04] und die darauf basierende Vorlesung von R. Kruse [Kru08], welche einen umfassenden Überblick über genetische Algorithmen geben.
- Das Buch Genetische Algorithmen von J. Heistermann [Hei94], welches ausführlich ver- schiedene Varianten genetischer Elementaroperationen gegenüberstellt und analysiert.
- Das Buch Handbook of Genetic Algorithms von L. Davis [Dav91], welches eine Vielzahl von Anwendungsgebieten genetischer Algorithmen präsentiert.
2. Grundbegriffe der Genetik
Bevor in dieser Arbeit auf die Funktionsweise genetischer Algorithmen eingegangen wird, werden in diesem Abschnitt zunächst Begriffe definiert, die für das weitere Verständnis notwendig sind. Diese Begriffe stammen aus der Genetik und können auf genetische Algorithmen übertragen werden. Die folgende Auflistung ist angelehnt an [GKK04, S.34]
- Gen: Unter einem Gen versteht man eine spezielle Eigenschaft eines Organismus. Die Haarfarbe eines Menschen ist zum Beispiel durch ein Gen definiert. Diese Eigenschaft wird in der Algorithmik durch ein Zeichen oder ein Bit repräsentiert, welches verschiedene Zustände annehmen kann.
- Chromosom: Ein Chromosom entspricht einer Kette aus Genen, also einer Kombination verschiedener Eigenschaften, die ein Lebewesen eindeutig kennzeichnen. Diese Abfolge lässt sich als Zeichenkette oder Liste von Bits darstellen und repräsentiert damit eine Lösung für ein Problem.
- Allel: Ein Allel beschreibt die Ausprägung eines Gens. Das Gen für die Haarfarbe kann demnach in verschiedenen Allelen vorkommen, die entweder für eine blonde oder eine braune Haarfarbe verantwortlich sind. Es bezeichnet also den genauen Wert eines Gens respektive den Wert des Zeichens oder der Zahl.
- Population : Der Begriff Population beschreibt die Menge aller Lebewesen im Prozess der Evolution. Im Bereich der genetischen Algorithmen beschränkt man sich auf die Menge von Chromsomen, also Lösungskandidaten für ein Problem.
- Fitness: Je ”fitter“einLebewesenist,destohöheristdessenChance,zuüberleben bzw. sich zu vermehren. Bezogen auf genetische Algorithmen ist die Fitness also ein Maß für die Güte eines Chromosoms.
- Generation: Unter einer Generation versteht man sowohl in der biologischen Evo- lution als auch in der Algorithmik eine Population zu einem bestimmten Zeitpunkt.
- Reproduktion: Die Reproduktion ist der Prozess der Bildung eines Nachkommens aus einem oder mehreren Individuen der Population respektive die Bildung von neuen Chromosmen aus einem oder mehreren vorhandenen Chromosomen.
3. Der genetische Algorithmus
Wie bereits zu Beginn dieser Facharbeit erläutert, orientiert sich ein genetischer Algorithmus an dem Evolutionsprozess der Natur. Dieser Prozess besteht im Wesentlichen aus drei Elementaroperationen, Kreuzung, Mutation und Selektion. Sie arbeiten nach verschiedenen Prinzipien, die in diesem Kapitel erläutert werden. Jede der Operationen ist notwendig, um schnell eine optimale Lösung für ein Problem zu finden.
Zunächst muss eine Anfangspopulation generiert werden, auf welche man die genannten Operationen anwenden kann. Hierfür muss man ein gegebenes Optimierungsproblem als eine Menge von Eigenschaften (Genen) modellieren, die nachfolgend mit zufälligen Allelen belegt werden. Die Anzahl der Lösungskandidaten pro Generation ist nicht festgelegt und kann je nach Problem variiert werden.
3.1. Elementaroperationen
Hat man die zufällige Population generiert, werden die Elementaroperationen auf sie angewandt. Jeder Durchlauf der Operationen erhöht die Generationszahl der Population. Die Operationen werden so lange wiederholt, bis eine ausreichend gute Lösung erzeugt wird, oder die Generationszahl einen bestimmten Grenzwert überschreitet.
3.1.1. Kreuzung
Bei der Kreuzung werden zwei zufällige Indiviuden aus der Population ausgewählt, die als Eltern für ein neues Chromosom fungieren. Dieses übernimmt sowohl vom Vater- als auch vom Mutterchromosom einige Eigenschaften. Für den genauen Prozess der Kreuzung existieren diverse Ansätze. Im Rahmen dieser Facharbeit wird auf das bekannteste Verfahren, dem One-Point-Crossover, eingegangen.
Beim One-Point-Crossover wird zunächst ein zufälliger Punkt p ∈ {1, ..., l − 1} gewählt, wobei l der Länge des Chromosoms entspricht. Anschließend erhalten alle Gene links von und einschließlich p die Allele des Vaterchromosoms, sowie alle Gene rechts von p die Allele des Mutterchromosoms und umgekehrt. Abbildung 1 demonstriert zwei mögliche Ergebnisse einer Ein-Punkt-Kreuzung1.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 1: One-Point-Crossover
Jedes Chromosom der Population erhält die Möglichkeit zu einer Kreuzung. Hierfür werden jeweils 2 Chromosomen aus der Population gewählt und mit einer Wahrscheinlichkeit pc gekreuzt. Diesen Schritt wiederholt man so lange, bis alle Chromosomen der Population betrachtet wurden.
3.1.2. Mutation
Die Mutation von Chromosomen ist ein wichtiger Bestandteil des genetischen Algorithmus. Ohne die Mutation würden keine neuen Lösungsansätze entstehen, da alle durch Kreuzung entstehenden Chromosomen nur aus ihren Vorgängern bestehen. Mithilfe der Mutation einer so kombinierten Lösung kann hingegen eine gänzlich neue Lösung entstehen, die unter Umständen eine bessere Fitness aufweist, als die nicht mutierte Lösung.
Bei der Mutation wird jedes Gen des Chromosoms durchlaufen und mit einer gewissen Wahrscheinlichkeit mutiert. Diese Wahrscheinlichkeit pm liegt in der Regel bei pm wobei l der Länge des Chromosoms entspricht[GKK04, S.40].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 2: Mutation
3.1.3. Selektion
Die dritte Elementaroperation eines genetischen Algorithmus ist die Selektion. Sie dient dazu die Population, die in ihrer Größe durch Rekombination und Mutation stark angestiegen ist, wieder auf ihre Ausgangsgröße zu reduzieren. Hierbei muss sichergestellt sein, dass sich die Population mit jeder Generation im Durchschnitt verbessert. Ein bekanntes Selektionsverfahren, welches nun näher erläutert wird, ist die Roulette Wheel Selection.
Bei dieser verteilt man alle Chromosomen der Population auf einem ”Glücksrad“.Hierbei erhalten Chromosomen mit einer besseren Fitness einen größeren Anteil am Rad. Anschlie- ßend wird das Rad gedreht und an einem zufälligen Punkt angehalten. Das Chromosom, auf das dabei gezeigt wird, gelangt in die nächste Generation. Diesen Vorgang wiederholt man so lange, bis man die gewünschte Populationsgröße erreicht hat. Die Chance eines Chromosoms in die nächste Generation zu gelangen steigt proportional mit seiner Fitness. Durch den Zu- fall ist es allerdings nicht ausgeschlossen, dass jedes mal das jeweils schlechteste Chromosom gezogen wird. Die Wahrscheinlichtkeit für so einen Fall ist allerdings sehr gering und somit zu vernachlässigen [Dav[91], S.[13]f] .
4. Das Schema-Theorem
Warum funktionieren genetische Algorithmen? Ziel des Kapitels ist es, diese Frage zu be- antworten. Bereits 1975 veröffentlichte John Henry Holland in seinem Buch Adaptation in Natural and Artificial Systems das ”Schema-Theorem”,welcheseineAussageüberdieVer- breitung von Chromosomen mit einem bestimmten Schema in einer Population trifft [Kru[08], [3]. Teil, S.[18]].
Im Zuge der Herleitung geben wir zunächst benötigte Variablen und Funktionen an. Anschließend wird das Theorem kurz dargestellt und daraufhin der Einfluss der Selektion, der Kreuzung und der Mutation auf die Verbreitung eines Schemas betrachtet.
4.1. Definiton des Begriffes
”Schema“
Ein Schema kann man als eine Vorlage für eine bestimmte Menge von Chromosomen an- sehen. Es gleicht dem Aufbau eines Chromosoms, kann allerdings als Allele neben den vorgegebenen Werten (z.B. 1 und 0 bei Binär-Genen) auch ein ”Don’tcare“-Symbolanneh- men. Dies wird angedeutet durch einen Stern (*). Chromosomen entsprechen einem Schema, wenn ihre Allele an allen Stellen bis auf den nicht fest definierten übereinstimmen. Entspricht ein Chromosom c einem Schema H, so schreiben wir c - H.
Abbildung in dieser Leseprobe nicht enthalten
4.2. Herleitung des Schema-Theorems
Die folgende Herleitung orientiert sich hauptsächlich an [GKK04, S.47-56] sowie [Kru08, 3. Teil, S.17-34]. Sie beschränkt sich auf Chromosomen, die nur binäre Gene enthalten, sowie auf die Verwendung des One-Point-Crossovers (vgl. 3.1.1), der einfachen Mutation (vgl. 3.1.2) und der Roulette Wheel Selection (vgl. 3.1.3).
Folgende Ausdrücke sind für das Verständnis der Herleitung notwendig:
Abbildung in dieser Leseprobe nicht enthalten
Definition 4.1 (Relative Fitness): Unter der relativen Fitness eines Chromosoms c ver- stehen wir den Anteil, den das Chromosom durch seine Fitness an der Gesamtpopulation besitzt. Es ist
Abbildung in dieser Leseprobe nicht enthalten
Definition [4].[2] (Mittlere relative Fitness eines Schemas): Die mittlere relative Fitness gibt den Durchschnitt der relativen Fitness aus ([4].[1]) für die Menge der zu einem Schema H passenden Chromosomen an. Es ist
Abbildung in dieser Leseprobe nicht enthalten
Definition 4.3 (Durchschnittliche Fitness der Population): Die Funktion
Abbildung in dieser Leseprobe nicht enthalten
beschreibt die mittlere absolute Fitness aller Chromosomen in der Population.
Definition 4.4 (Durchschnittliche Fitness eines Schemas): Im Gegensatz zu (4.3) gibt
Abbildung in dieser Leseprobe nicht enthalten
die mittlere absolute Fitness aller einem Schema H zugehörigen Chromosomen an.
Definition 4.5 (Charakteristische Funktion einer Menge): Unter der charakteristischen Funktion char einer Menge B verstehen wir eine Funktion, die angibt, ob ein Element a zu einer Menge B gehört oder nicht. Es ist
Abbildung in dieser Leseprobe nicht enthalten
Definition 4.6 (Ordnung eines Schemas): Die Ordnung eines Schemas gibt die Anzahl der definierten Gene mit Hilfe der charakteristischen Funktion (4.5) der Menge {1, 0} an. Es ist
Abbildung in dieser Leseprobe nicht enthalten
Definition 4.7 (Definierende Länge): Die definierende Länge eines Schemas H gibt die
Differenz der Positionen des letzten und des ersten definierten Allels an. Es ist
Abbildung in dieser Leseprobe nicht enthalten
4.2.1. Das Theorem
Das Schema-Theorem gibt Aufschluss über die quantitative Entwicklung eines Schemas pro Generationsschritt. Aus diesem Theorem lassen sich Bedingungen ableiten, unter denen genetische Algorithmen besonders gut funktionieren.
Definition 4.8 (Schema-Theorem): Die Verbreitung von Schemen pro Generationsschritt lässt sich beschreiben durch
Abbildung in dieser Leseprobe nicht enthalten
Jede in Kapitel 3 vorgestellte Elementaroperation besitzt einen Einfluss auf die Schemenverbreitung, welche im Folgenden untersucht wird.
4.2.2. Selektion
Bei der Roulette-Wheel-Selection steigt die Wahrscheinlichkeit, dass ein Chromosom in die nächste Generation gewählt wird, proportional zu dessen Fitness in Relation zur Population. Da in der Regel mehrere Chromosomen der Population zu einem Schema passen, ist die Wahrscheinlichkeit einer Selektion dementsprechend höher. Desweiteren wird der Selektionsoperator popsize-mal durchgeführt, was bedeutet, dass die Wahrscheinlichkeit der Selektion eines zum Schema passenden Chromosoms um ebendiesen Faktor steigt.
Definition 4.9: Die Anzahl an zu einem Schema passenden Chromosomen nach einer Selektion (nach einer Zeit Δtsel) ist durch
Abbildung in dieser Leseprobe nicht enthalten
definiert, wobei f itrel(H) · popsize der Proportionalitätsfaktor ist.
4.2.3. Kreuzung
Das Ausführen des Kreuzungsoperators auf die gesamte Population unterteilt diese in zwei Segmente:
Zum einen existiert ein Segment nunv , der nicht durch die Kreuzung verändert wurde. Zum anderen beschreibt ncross das Segment der gekreuzten Chromosomen. Die Größen der beiden Segmente sind abhängig von der Kreuzungswahrscheinlichkeit pc und werden im Folgenden erläutert. Insgesamt ergibt sich für die Anzahl der zu einem Schema passenden Chromosme nach Ausführung der Selektion und Kreuzung (nach einer Zeit [Abbildung in dieser Leseprobe nicht enthalten])
Abbildung in dieser Leseprobe nicht enthalten
Die Größe des unveränderten Teils nunv resultiert aus der Differenz der gesamten Population und des Anteils, der gekreuzt wird, also 1 − pc.
Beim anderen Teil, der die Größe pc besitzt, wird eine Kreuzung auf die Chromosomen ausgeführt. Dabei können sowohl neue, zum Schema passende Chromosomen entstehen (gain) als auch verloren gehen. Die Wahrscheinlichkeit ploss für den Verlust von Chromosomen ist abhängig von bestimmten Größen und kann mit
Abbildung in dieser Leseprobe nicht enthalten
berechnet werden. Der Faktor A gibt die Wahrscheinlichkeit an, mit der der Kreuzungs- punkt innerhalb des definierten Teils des Schemas gekreuzt wird. Dagegen beschreibt B den relativen Anteil der Chromosomen, die nicht zum Schema H passen. Ein Verlust findet nur dann statt, wenn innerhalb des definierten Teils gekreuzt wird und der Kreuzungspartner nicht zum Schema passt. Die Verlustwahrscheinlichkeit ist allerdings in der Regel kleiner, da gelegentlich ein Chromosom entsteht, dass weiterhin dem Schema H entspricht, obwohl beide Bedingungen zutreffen. Man bezeichnet diesen Prozess als Erhaltung.
Der Gewinnfaktor gain wird im weiteren Verlauf der Simplizität halber vernachlässigt. Verwenden wir die vorhin definierten Gleichungen, so erhalten wir insgesamt:
Definition 4.10: Die Anzahl der Chromosomen, die nach der Selektion und Kreuzung (nach einer Zeit[Abbildung in dieser Leseprobe nicht enthalten]) dem Schema H entsprechen, beträgt
Abbildung in dieser Leseprobe nicht enthalten
4.2.4. Mutation
Bei der Mutation von Chromosmen wird ein Gen mit einer Mutationswahrscheinlichkeit pm mutiert. Im Umkehrschluss bedeutet dies, dass Gene mit einer Wahrscheinlichkeit (1 − pm) nicht mutiert werden. In Hinsicht auf das Schema-Theorem bleibt ein Chromosom nur dann zu einem Schema passend, wenn kein definiertes Gen mutiert wird. Aus diesem Grund wird die Wahrscheinlichkeit (1 − pm) mit der Ordnung (4.6) des Schemas potenziert, da bei der einfachen Mutation jedes Gen eines Chromosoms durchlaufen wird. Die Anzahl der Chromosmen, die nach der Selektion, Kreuzung und Mutation (und somit nach einem vollständigen Generationsschritt) zum Schema passen, errechnet sich somit durch
Abbildung in dieser Leseprobe nicht enthalten
Verwenden wir nun (4.12), so erhalten wir:
Definition 4.11: Die Anzahl der Chromosomen, die nach der Selektion, Kreuzung und Mutation (nach einer Zeit Abbildung in dieser Leseprobe nicht enthalten) dem Schema H entsprechen, beträgt
Abbildung in dieser Leseprobe nicht enthalten
Um nun die zu Beginn dargestellte Gleichung zu erhalten, ersetzt man f itrel(H) · popsize durch das sogenannte Fitnessverhältnis. Es ist das Verhältnis zwischen der mittleren Fit- ness des Schemas und der mittleren Fitness der Population. Diese Ersetzung kann man durchführen, da
Abbildung in dieser Leseprobe nicht enthalten
Es ergibt sich demzufolge insgesamt
Abbildung in dieser Leseprobe nicht enthalten
4.3. Interpretation
Betrachten wir nun die Gleichung des Schema-Theorems, so lässt sich erkennen, dass die Anzahl der zu einem Schema passenden Chromosomen direkt abhängig von der vorangehenden Generation ist, die mit 3 Wichtungsfaktoren multipliziert wird. Diese sind
Abbildung in dieser Leseprobe nicht enthalten
Es stellt sich nun die Frage, welche Bedingungen das Schema erfüllen muss, damit das Produkt der Faktoren A, B und C möglichst groß ist.
Betrachten wir zunächst das Fitnessverhältnis A. Damit die Chromosomenzahl steigt, muss A > 1 sein. Dies ist genau dann der Fall, wenn Abbildung in dieser Leseprobe nicht enthalten it ist. Das bedeutet, dass die dem Schema entsprechenden Choromosmen im Mittel fitter sein müssen, als die gesamte Population im Durchschnitt. Weitehin gilt für Faktor B, dass er zu keinem Zeitpunkt größer oder gleich 1 ist. Um den Gewinn von Faktor A nicht zu beeinträchtigen, sollte B.1 möglichst klein sein. Dies wird erreicht, wenn das Schema eine kleine definierende Länge besitzt. Die für das Schema relevanten Gene befinden sich dann in einem kleinen Paket. Dieses Paket bezeichnet man auch als Building-Block. Der Faktor C zeigt ähnliche Eigenschaften wie Faktor B. Damit C nicht zu klein wird, muss der Exponent und damit die Ordnung des Schemas möglichst gering sein.
Fassen wir die Erkenntnisse zusammen: Bei einem genetischen Algorithmus werden immer die Lösungsraume mit den besten Lösungen durchsucht, da Schemen mit einer hohen Fitness am weitesten in der Population verbreitet sind. Außerdem sagt die Building-Block-Hypothese aus, dass sich die Gesamtlösung für ein Problem aus einzelnen Building-Blocks, also Schemen mit geringer Ordnung und definierender Länge zusammensetzt [GKK04, S.55]. Diese Building-Blocks werden ebenfalls bevorzugt in der Population verbreitet.
5. Eine Anwendung genetischer Algorithmen : Das n-Damen Problem
Die Dame ist beim Schachspiel ”diemächtigsteSchachfigur. Sie kann in Reihen und Spalten ziehen. Zusätzlich kann sie sich auf den Diagonalen bewegen“ [mat]. Bereits [1848] er- schien das Rätsel, ob man [8] Damen auf einem [8] x [8] Schach- brett (oder verallgemeinert n Damen auf einem n x n Feld) anordnen kann, sodass sich diese nicht gegenseitig bedrohen.
Diese Frage repräsentiert ein typisches Optimierungspro- blem. Ziel ist es, die Anzahl der Kollisionen zwischen den Figuren zu minimieren. Aus diesem Grund verwendet der implementierte genetische Algorithmus die Zahl der Kolli- sionen (also Bedrohungen) als Fitness Funktion. Die Chro- mosomen bestehen aus einer Kette mit n Elementen, wobei jedes Element i die vertikale Position einer Dame in der Abbildung [3]: Startansicht des iten Spalte angibt. Als Elementaroperationen wurden das Programms One-Point-Crossover, die einfache Mutation und die Tour- nament Selection (näheres zu dieser Selektionsart in [GKK[04], S.[84]]) eingesetzt.
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 3: Start-ansicht cies Programms
Parallel dazu wurde der im Unterricht besprochene Backtracking Algorithmus implementiert, um einen Vergleich der Laufzeiten durchführen zu können. Er arbeitet nach dem Prinzip der Tiefensuche und setzt so lange eine weitere Dame auf das Spielfeld, bis entweder keine freie Position mehr existiert oder die Anzahl n erreicht wurde.
Die Bedienung des Programms beschränkt sich auf zwei Aktionen. Zum einen kann die Feldgröße mit Hilfe der ”+“und ”-“Tastevariiertwerden,zumanderenkannentweder der genetische Algorithmus oder das Backtracking für das eingestellte Feld gestartet werden. Finden die Verfahren eine Lösung, so wird diese auf dem Schachfeld angezeigt. Rote Felder bedeuten hierbei, dass dort eine Dame platziert wird. Zusätzlich wird im Textfeld die benötigte Zeit und die Anzahl der Generationen (genetischer Algorithmus) beziehungsweise die Anzahl der Versuche (Backtracking) angezeigt. Eine mögliche Ausgabe für den genetischen Algorithmus bei einer Feldgröße n = [15] zeigt Abbildung [4].
Abbildung in dieser Leseprobe nicht enthalten
Abbildung [4]: Ergebnis des genetischen Algorithmus bei n = [15]
Abbildung [5] demonstriert ein exemplarisches Ergebnis bei der Größe n = [30]. In Anhang D befindet sich eine ausführliche Testreihe, die mit Hilfe der Anwendung erstellt wurde. Anhang E zeigt den Quellcode der Anwendung.
6. Fazit
Wie wir in dieser Arbeit feststellen konnten, arbeiten genetische Algorithmen nach simplen Prinzipien, die in der richtigen Komibnation effizient NP-schwere Probleme lösen können. Dies wurde zum Beispiel bei dem n-Damen Problem ersichtlich (siehe Kapitel 5). Da das Backtracking Verfahren ein exponentielles Laufzeitverhalten aufweist [HS05, S.9], ist bei ei- ner Feldgröße n = 30 die benötigte Zeit mit ungefähr 34 Minuten bereits sehr hoch, während der genetische Algorithmus im Mittel nach 12 Sekunden eine Lösung hat. Über das Laufzeit- verhalten genetischer Algorithmen lässt sich keine genaue Aussage treffen. Die praktischen Tests (siehe Anhang D) zeigen allerdings, dass der genetische Algorithmus selbst bei n = 100 nur wenige Minuten benötigt.
Das größte Problem bei genetischen Algorithmen liegt in der Modellfindung. Es ist oftmals schwer, für ein gegebenes Optimierungsproblem eine passende Darstellung in Form eines Chromosom-Modells zu finden.
Hat man ein passendes Modell gefunden, so ist die Implementierung des genetischen Al- gorithmus simpel und lässt sich in kurzer Zeit erledigen. Dies ist der Vorteil genetischer Algorithmen. Sie sind flexibel und können leicht auf verschiedene Probleme adaptiert wer- den. Man muss allerdings beachten, dass der Algorithmus nicht immer eine Lösung liefert.
Blicken wir zurück auf das Schema-Theorem (siehe Kapitel 4), so müssen wir beachten, dass selbiges streng genommen nur dann funktioniert, wenn man von einer unendlich großen Population ausgeht. Dies hat zum einen mit den häufig verwendeten Zufallswerten zu tun. Das Theorem setzt vorraus, dass diese Werte auf dem gesamten Wertebereich gleichmäßig verteilt sind, was allerdings nur bei besagter unendlich großer Population erfüllt. Zum anderen sind in einer begrenzten Populationsgröße häufig nicht alle Schemen vertreten, wodurch manche (bessere) Schemen keine Möglichkeit besitzen, sich durchzusetzen.
Schlussendlich kann man sagen, dass genetische Algorithmen - trotz ihrer Einschränkungen - eine große Bereicherung für die Informatik darstellen. So werden Genetische Algorith- men beispielsweise dazu verwendet, ”Zweiphasen-Überschalldüsen“zuoptimieren[Hei[94], S.[165]f.]. Hierbei handelt es sich um Triebwerke , die mit ihren [330] Segmenten ohne genetische Algorithmen nicht in einer akzeptablen Zeit in eine, maximalen Schub liefernde Form gebracht werden könnten. Dieses Beispiel stellt nur eines der Probleme dar, bei denen genetische Algorithmen entscheidend zur Lösung beigetragen haben. Folglich ist das Prinzip der Evolution nicht nur in der Biologie ein voller Erfolg.
A. Literatur
Die Literaturangaben sind alphabetisch nach den Namen der Autoren sortiert. Bei mehreren Autoren wird nach dem ersten Autor sortiert.
Abbildung in dieser Leseprobe nicht enthalten
B. Abbildungen
Abbildung in dieser Leseprobe nicht enthalten
Abbildung 5: Testreihe des Programms bei der Größe n = 30. Die Fenster 1 bis 3 wurden durch den genetischen Algorithmus generiert (durchschnittl. 14 Sekunden), Fenster 4 durch den Backtracking Algorithmus (≈ 34 Minuten).
C. Abbildungsverzeichnis
1. One-Point-Crossover
2. Mutation
3. Startansicht des Programms
4. Ergebnis des genetischen Algorithmus bei n = 15
5. Testreihe des Programms bei der Größe n = 30
D. Testreihe der Anwendung
Abbildung in dieser Leseprobe nicht enthalten
E. Quellcode der Anwendung
Die Anwendung ”n-Damen“,welchesichaufderbeiliegendenCDimOrdnernDamenbefin- det, wurde mit der Programmiersprache Delphi erstellt. In dem Ordner befinden sich die Quellcode-Dateien (*.pas), die ausführbare Anwendung (*.exe), die Projektdatei für die Enticklungsumgebung CodeGear Delphi [2007] (*.dproj), sowie einige Hilfsdateien.
uMain.pas Die Unit uMain beinhaltet die Oberfläche und die damit verbundene Verwal- tung der Threads. Die Hauptklasse TfrmMain erbt von der Klasse TForm und implementiert das Interface IOutput, welches in der Unit uGlobal definiert ist. Durch das Interface wird ermöglicht, dass die Klassen der Suchalgorithmen einen Zugriff auf die Anzeigefunktionen des Fensters besitzen.
Listing [1]: uMain.pas
Abbildung in dieser Leseprobe nicht enthalten
uGlobal.pas Die Unit uGlobal besitzt Strukturen, die von mehreren Klassen benutzt wer- den. Hierzu gehört das Interface IOutput sowie die Klassen TIntArray sowie TIntArray2D, die eine Objektorientierte Version einer Ein- beziehungsweise Zwei-Dimensionalen Liste dar- stellen.
Listing 2: uGlobal.pas
Abbildung in dieser Leseprobe nicht enthalten
uStack.pas Die Unit uStack beinhaltet den abstrakten Datentyp TStack, wie er bereits im Unterricht besprochen wurde.
Listing 3: uStack.pas
Abbildung in dieser Leseprobe nicht enthalten
uObjectPointStack.pas Der in dieser Unit definierte Datentyp TObjectPointStack stellt eine spezielle Version des Stacks dar. Er verwaltet nur Objekte des Typs TObjectPoint und besitzt zusätzlich die Funktion, den aktuellen Stack in eine Liste des Typs TIntArray zu kopieren.
Listing 4: uObjectPointStack.pas
Abbildung in dieser Leseprobe nicht enthalten
uRingList.pas In der Unit uRingList wird der abstrakte Datentyp TRingList implementiert. Diese im Ring verkettete Liste wird für die Verwaltung der Population des genetischen Algorithmus verwendet.
Listing 5: uRingList.pas
Abbildung in dieser Leseprobe nicht enthalten
uBacktracking.pas Die Unit uBacktracking beinhaltet die Klasse TBacktracker, welche von der Klasse TThread erbt. Die Klasse implementiert den Backtracking Algorithmus für das n-Damen Problem.
Listing 6: uBacktracking.pas
Abbildung in dieser Leseprobe nicht enthalten
uGenetic.pas Die Unit uGenetic beinhaltet die Klasse TGeneticSearch, welche von der Klasse TThread erbt. Die Klasse implementiert den genetischen Algorithmus für das n-Damen Problem.
Listing 7: uGenetic.pas
Abbildung in dieser Leseprobe nicht enthalten
[...]
Häufig gestellte Fragen
Was ist das Inhaltsverzeichnis des Dokuments?
Das Inhaltsverzeichnis umfasst: 1. Einleitung, 2. Grundbegriffe der Genetik, 3. Der genetische Algorithmus (mit Unterpunkten zu Elementaroperationen: Kreuzung, Mutation, Selektion), 4. Das Schema-Theorem (mit Unterpunkten zu Definition des Begriffs "Schema", Herleitung des Schema-Theorems, dem Theorem selbst, Selektion, Kreuzung, Mutation, und Interpretation), 5. Eine Anwendung genetischer Algorithmen: Das n-Damen Problem, 6. Fazit, A. Literatur, B. Abbildungen, C. Abbildungsverzeichnis, D. Testreihe der Anwendung, E. Quellcode der Anwendung.
Worum geht es in der Einleitung?
Die Einleitung beschreibt genetische Algorithmen als eine von der Evolution inspirierte Methode der Informatik. Sie umreißt den Aufbau der Arbeit: Grundbegriffe der Genetik, Struktur genetischer Algorithmen (Elementaroperationen), theoretische Grundlagen (Schema-Theorem), eine praktische Anwendung (n-Damen Problem) sowie Fazit zu Möglichkeiten und Grenzen.
Welche Grundbegriffe der Genetik werden definiert?
Es werden folgende Begriffe definiert: Gen, Chromosom, Allel, Population, Fitness, Generation und Reproduktion.
Was sind die Elementaroperationen eines genetischen Algorithmus?
Die Elementaroperationen sind: Kreuzung (One-Point-Crossover wird beschrieben), Mutation und Selektion (Roulette Wheel Selection wird beschrieben).
Was ist das Schema-Theorem?
Das Schema-Theorem ist eine theoretische Grundlage, die die Funktionalität genetischer Algorithmen nachweist. Es beschreibt, wie sich Schemen (Vorlagen für Chromosomen) in einer Population verbreiten.
Was sind wichtige Definitionen im Zusammenhang mit dem Schema-Theorem?
Definiert werden: Relative Fitness, Mittlere relative Fitness eines Schemas, Durchschnittliche Fitness der Population, Durchschnittliche Fitness eines Schemas, Charakteristische Funktion einer Menge, Ordnung eines Schemas, Definierende Länge.
Wie beeinflussen Selektion, Kreuzung und Mutation die Schemenverbreitung?
Die Selektion bevorzugt Chromosomen mit höherer Fitness. Die Kreuzung kombiniert Eigenschaften von Elternchromosomen. Die Mutation führt zu neuen Lösungsansätzen. Alle drei Operationen beeinflussen quantitativ die Verbreitung von Schemen pro Generationsschritt. Die Gleichungen zur quantifizierung werden aufgestellt.
Was ist das n-Damen Problem und wie wird es mit einem genetischen Algorithmus gelöst?
Das n-Damen Problem besteht darin, n Damen so auf einem n x n Schachbrett zu platzieren, dass sie sich nicht gegenseitig bedrohen. Der genetische Algorithmus minimiert die Anzahl der Kollisionen (Bedrohungen) zwischen den Figuren. One-Point-Crossover, einfache Mutation und Tournament-Selection werden eingesetzt.
Wie schneidet der genetische Algorithmus im Vergleich zum Backtracking-Algorithmus beim n-Damen Problem ab?
Der genetische Algorithmus ist bei größeren Problemstellungen (z.B. n = 30) deutlich schneller als der Backtracking-Algorithmus, der ein exponentielles Laufzeitverhalten zeigt.
Was sind die Vor- und Nachteile genetischer Algorithmen laut Fazit?
Vorteile: Effiziente Lösung NP-schwerer Probleme, flexible Anpassung an verschiedene Probleme, einfache Implementierung. Nachteile: Schwierige Modellfindung (Darstellung des Problems als Chromosom-Modell), keine Garantie für eine Lösung, Schema Theorem setzt unendlich große Population voraus.
Was befindet sich im Anhang?
Der Anhang enthält: A. Literaturverzeichnis, B. Abbildungen, C. Abbildungsverzeichnis, D. Testreihe der Anwendung, E. Quellcode der Anwendung (Delphi).
Welche Dateien sind im Anhang E im nDamen Ordner zu finden?
uMain.pas, uGlobal.pas, uStack.pas, uObjectPointStack.pas, uRingList.pas, uBacktracking.pas, uGenetic.pas
- Quote paper
- Martin Matysiak (Author), 2009, Genetische Algorithmen zur Lösung von Optimierungsproblemen, Munich, GRIN Verlag, https://www.grin.com/document/126236
