Inhaltsverzeichnis

1.  Einleitung  3

2.  Grundbegriffe der Genetik  4

3.  Der genetische Algorithmus  5

3.1.  Elementaroperationen  5

3.1.1.  Kreuzung  5

3.1.2.  Mutation  6

3.1.3.  Selektion  6

4.  Das Schema-Theorem  7

4.1.  Definiton des Begriffes Schema“  7

4.2.  Herleitung des Schema-Theorems  7

4.2.1.  Das Theorem  9

4.2.2.  Selektion  9

4.2.3.  Kreuzung  9

4.2.4.  Mutation  11

4.3.  Interpretation  12

5.  Eine Anwendung genetischer Algorithmen : Das n-Damen Problem  13

6.  Fazit  14

A.  Literatur  15

B.  Abbildungen  16

C.  Abbildungsverzeichnis  17

D.  Testreihe der Anwendung  18

E.  Quellcode der Anwendung  20

2

1. Einleitung

Die Evolution ist der leistungsf¨ ahigste Prozess der Natur. Lebewesen passen sich - scheinbar von selbst - von Generation zu Generation immer besser den Bedingungen ihrer Umgebung an. Die Idee der st¨ andigen 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¨ aher zu bringen. Die Arbeit ist wie folgt aufgebaut: Das zweite Kapitel erl¨ autert Grundbegriffe der Genetik und ihre Bedeutung in der Informatik. Im dritten Kapitel wird die generelle Struktur genetischer Algorithmen vorgestellt. Hierzu z¨ ahlen 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¨ at genetischer Algorithmen nachweisen. Im f¨ unften Kapitel demonstrieren wir eine praktische Anwendung genetischer Algorithmen. Wir zeigen, wie genetische Algorithmen zur L¨ osung des n-Damen Problems beitragen k¨ onnen. Abschließend fassen wir im sechsten Kapitel die in dieser Arbeit gewonnenen Erkenntnisse zusammen und betrachten M¨ oglichkeiten und Begrenzungen genetischer Algorithmen bei der praktischen Umsetzung.

Bevor wir mit der eigentlichen Arbeit beginnen, sollten wir zun¨ achst Optimierungsprobleme als Einsatzgebiet genetischer Algorithmen betrachten. Optimierungsprobleme zeichnen sich dadurch aus, dass sie mehr als eine richtige L¨ osung besitzen, wobei unterschiedliche L¨ osungen ebenfalls unterschiedlich gut sein k¨ onnen. Bei dieser Art von Problem ist es meist schwer, einen Algorithmus zu finden, der die beste L¨ osung in einer akzeptablen Zeit ermittelt. Genau hier setzen genetische Algorithmen an. Sie erzeugen zun¨ achst eine Menge aus zuf¨ alligen L¨ osungen und lassen diese Menge nach den Prinzipien der Evolution weiterentwickeln (und somit optimieren), bis sich eine gen¨ ugend gute L¨ osung herausstellt. Durch genetische Algorithmen ist es oftmals m¨ oglich, sogenannte NP-Schwere - also nicht effizient l¨ osbare - Probleme in kurzer Zeit mit einem zufriedenstellenden Ergebnis zu berechnen. Als Literatur wird unter anderem verwendet:

• Das Buch Evolution¨ are Algorithmen von I. Gerdes, F. Klawonn und R. Kruse [GKK04] und die darauf basierende Vorlesung von R. Kruse [Kru08], welche einen umfassenden ¨ Uberblick ¨ uber genetische Algorithmen geben.

• Das Buch Genetische Algorithmen von J. Heistermann [Hei94], welches ausf¨ uhrlich verschiedene Varianten genetischer Elementaroperationen gegen¨ uberstellt und analysiert.

• Das Buch Handbook of Genetic Algorithms von L. Davis [Dav91], welches eine Vielzahl von Anwendungsgebieten genetischer Algorithmen pr¨ asentiert.

3

2. Grundbegriffe der Genetik

Bevor in dieser Arbeit auf die Funktionsweise genetischer Algorithmen eingegangen wird, werden in diesem Abschnitt zun¨ achst Begriffe definiert, die f¨ ur das weitere Verst¨ andnis notwendig sind. Diese Begriffe stammen aus der Genetik und k¨ onnen auf genetische Algorithmen ubertragen 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¨ asentiert, welches verschiedene Zust¨ ande annehmen kann.

• Chromosom: Ein Chromosom entspricht einer Kette aus Genen, also einer Kombination verschiedener Eigenschaften, die ein Lebewesen eindeutig kennzeichnen. Diese Abfolge l¨ asst sich als Zeichenkette oder Liste von Bits darstellen und repr¨ asentiert damit eine L¨ osung f¨ ur ein Problem.

• Allel: Ein Allel beschreibt die Auspr¨ agung eines Gens. Das Gen f¨ ur die Haarfarbe kann demnach in verschiedenen Allelen vorkommen, die entweder f¨ ur 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¨ ankt man sich auf die Menge von Chromsomen, also L¨ osungskandidaten f¨ ur ein Problem.

• Fitness: Je ” fitter“ ein Lebewesen ist, desto h¨ oher ist dessen Chance, zu ¨ uberleben

bzw. sich zu vermehren. Bezogen auf genetische Algorithmen ist die Fitness also ein Maß f¨ ur die G¨ ute eines Chromosoms.

• Generation: Unter einer Generation versteht man sowohl in der biologischen Evolution 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.

4

3. Der genetische Algorithmus

Wie bereits zu Beginn dieser Facharbeit erl¨ autert, 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¨ autert werden. Jede der Operationen ist notwendig, um schnell eine optimale L¨ osung f¨ ur ein Problem zu finden.

Zun¨ achst muss eine Anfangspopulation generiert werden, auf welche man die genannten Operationen anwenden kann. Hierf¨ ur muss man ein gegebenes Optimierungsproblem als eine Menge von Eigenschaften (Genen) modellieren, die nachfolgend mit zuf¨ alligen Allelen belegt werden. Die Anzahl der L¨ osungskandidaten pro Generation ist nicht festgelegt und kann je nach Problem variiert werden.

3.1. Elementaroperationen

Hat man die zuf¨ allige Population generiert, werden die Elementaroperationen auf sie an-gewandt. Jeder Durchlauf der Operationen erh¨ oht die Generationszahl der Population. Die Operationen werden so lange wiederholt, bis eine ausreichend gute L¨ osung erzeugt wird, oder die Generationszahl einen bestimmten Grenzwert ¨ uberschreitet.

3.1.1. Kreuzung

Bei der Kreuzung werden zwei zuf¨ allige Indiviuden aus der Population ausgew¨ ahlt, die als Eltern f¨ ur ein neues Chromosom fungieren. Dieses ¨ ubernimmt sowohl vom Vater- als auch

vom Mutterchromosom einige Eigenschaften. F¨ ur den genauen Prozess der Kreuzung existieren diverse Ans¨ atze. Im Rahmen dieser Facharbeit wird auf das bekannteste Verfahren, dem One-Point-Crossover, eingegangen.

Beim One-Point-Crossover wird zun¨ achst ein zuf¨ alliger Punkt p ∈ {1, ..., l − 1} gew¨ ahlt, wobei l der L¨ ange 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¨ ogliche Ergebnisse einer Ein-Punkt-Kreuzung 1 .

1 Der Verst¨ andlichkeit halber wurden Bitstrings zur Darstellung verwendet, die vorgestellten Operationen sind allerdings auch auf jede andere Art von Chromosom-Modell anwendbar

5

Jedes Chromosom der Population erh¨ alt die M¨ oglichkeit zu einer Kreuzung. Hierf¨ ur werden jeweils 2 Chromosomen aus der Population gew¨ ahlt und mit einer Wahrscheinlichkeit p c 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¨ urden keine neuen L¨ osungsans¨ atze entstehen, da alle durch Kreuzung entstehenden Chromosomen nur aus ihren Vorg¨ angern bestehen. Mithilfe der Mutation einer so kombinierten L¨ osung kann hingegen eine g¨ anzlich neue L¨ osung entstehen, die unter Umst¨ anden eine bessere Fitness aufweist, als die nicht mutierte L¨ osung. Bei der Mutation wird jedes Gen des Chromosoms durchlaufen und mit einer gewissen Wahrscheinlichkeit mutiert. Diese Wahrscheinlichkeit p m liegt in der Regel bei p m ≈ 1 ,

l

wobei l der L¨ ange des Chromosoms entspricht[GKK04, S.40].

3.1.3. Selektion

Die dritte Elementaroperation eines genetischen Algorithmus ist die Selektion. Sie dient dazu die Population, die in ihrer Gr¨ oße durch Rekombination und Mutation stark angestiegen ist, wieder auf ihre Ausgangsgr¨ oße zu reduzieren. Hierbei muss sichergestellt sein, dass sich die Population mit jeder Generation im Durchschnitt verbessert. Ein bekanntes Selektionsverfahren, welches nun n¨ aher erl¨ autert wird, ist die Roulette Wheel Selection. Bei dieser verteilt man alle Chromosomen der Population auf einem ” Gl¨ ucksrad“. Hierbei

erhalten Chromosomen mit einer besseren Fitness einen gr¨ oßeren Anteil am Rad. Anschließend wird das Rad gedreht und an einem zuf¨ alligen Punkt angehalten. Das Chromosom, auf das dabei gezeigt wird, gelangt in die n¨ achste Generation. Diesen Vorgang wiederholt man so lange, bis man die gew¨ unschte Populationsgr¨ oße erreicht hat. Die Chance eines Chromosoms in die n¨ achste Generation zu gelangen steigt proportional mit seiner Fitness. Durch den Zufall ist es allerdings nicht ausgeschlossen, dass jedes mal das jeweils schlechteste Chromosom gezogen wird. Die Wahrscheinlichtkeit f¨ ur so einen Fall ist allerdings sehr gering und somit zu vernachl¨ assigen [Dav91, S.13f] .

6

4. Das Schema-Theorem

Warum funktionieren genetische Algorithmen? Ziel des Kapitels ist es, diese Frage zu be-antworten. Bereits 1975 ver¨ offentlichte John Henry Holland in seinem Buch Adaptation in Natural and Artificial Systems das ” Schema-Theorem”, welches eine Aussage ¨ uber die Verbreitung von Chromosomen mit einem bestimmten Schema in einer Population trifft [Kru08, 3. Teil, S.18].

Im Zuge der Herleitung geben wir zun¨ achst ben¨ otigte 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¨ ur eine bestimmte Menge von Chromosomen ansehen. Es gleicht dem Aufbau eines Chromosoms, kann allerdings als Allele neben den vorgegebenen Werten (z.B. 1 und 0 bei Bin¨ ar-Genen) auch ein ” Don’t care“-Symbol annehmen. Dies wird angedeutet durch einen Stern (*). Chromosomen entsprechen einem Schema, wenn ihre Allele an allen Stellen bis auf den nicht fest definierten ¨ ubereinstimmen. Entspricht

ein Chromosom c einem Schema H, so schreiben wir c H.

4.2. Herleitung des Schema-Theorems

Die folgende Herleitung orientiert sich haupts¨ achlich an [GKK04, S.47-56] sowie [Kru08, 3. Teil, S.17-34]. Sie beschr¨ ankt sich auf Chromosomen, die nur bin¨ are 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¨ ucke sind f¨ ur das Verst¨ andnis der Herleitung notwendig:

H Schema

popsize Gr¨ oße der Population

f it Fitnessfunktion zur Bewertung eines Chromosoms p m Mutationswahrscheinlichkeit eines Gens p c Wahrscheinlichkeit einer Kreuzung P (t) Population zum Zeitpunkt t

N (H, t) Anzahl an Chromosomen des Schemas H in der Population zum Zeitpunkt t

7

Definition 4.1 (Relative Fitness): Unter der relativen Fitness eines Chromosoms c verstehen wir den Anteil, den das Chromosom durch seine Fitness an der Gesamtpopulation besitzt. Es ist

Definition 4.2 (Mittlere relative Fitness eines Schemas): Die mittlere relative Fitness gibt den Durchschnitt der relativen Fitness aus (4.1) f¨ ur die Menge der zu einem Schema H passenden Chromosomen an. Es ist

Definition 4.3 (Durchschnittliche Fitness der Population): Die Funktion

beschreibt die mittlere absolute Fitness aller Chromosomen in der Population.

Definition 4.4 (Durchschnittliche Fitness eines Schemas): Im Gegensatz zu (4.3) gibt

die mittlere absolute Fitness aller einem Schema H zugeh¨ origen 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¨ ort oder nicht. Es ist

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

Definition 4.7 (Definierende L¨ ange): Die definierende L¨ ange eines Schemas H gibt die Differenz der Positionen des letzten und des ersten definierten Allels an. Es ist

4.2.1. Das Theorem

Das Schema-Theorem gibt Aufschluss ¨ uber 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¨ asst sich beschreiben durch

N (H, t + 1) = N (H, t) ·

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¨ achste Generation gew¨ ahlt 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¨ oher. Desweiteren wird der Selektions-operator popsize-mal durchgef¨ uhrt, 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 ∆t sel ) ist durch

N (H, t + ∆t sel ) = N (H, t) · f it rel (H) · popsize (4.9)

definiert, wobei f it rel (H) · popsize der Proportionalit¨ atsfaktor ist.

4.2.3. Kreuzung

Das Ausf¨ uhren des Kreuzungsoperators auf die gesamte Population unterteilt diese in zwei Segmente:

Zum einen existiert ein Segment n unv , der nicht durch die Kreuzung ver¨ andert wurde. Zum anderen beschreibt n cross das Segment der gekreuzten Chromosomen. Die Gr¨ oßen der beiden Segmente sind abh¨ angig von der Kreuzungswahrscheinlichkeit p c und werden im Folgenden erl¨ autert. Insgesamt ergibt sich f¨ ur die Anzahl der zu einem Schema passenden Chromosme

9

nach Ausf¨ uhrung der Selektion und Kreuzung (nach einer Zeit ∆t sel + ∆t cross )

Die Gr¨ oße des unver¨ anderten Teils n unv resultiert aus der Differenz der gesamten Population und des Anteils, der gekreuzt wird, also 1 − p c .

Beim anderen Teil, der die Gr¨ oße p c besitzt, wird eine Kreuzung auf die Chromosomen ausgef¨ uhrt. Dabei k¨ onnen sowohl neue, zum Schema passende Chromosomen entstehen (gain) als auch verloren gehen. Die Wahrscheinlichkeit p loss f¨ ur den Verlust von Chromosomen ist abh¨ angig von bestimmten Gr¨ oßen und kann mit

berechnet werden. Der Faktor A gibt die Wahrscheinlichkeit an, mit der der Kreuzungspunkt 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¨ at halber vernachl¨ assigt. 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 ∆t sel + ∆t cross ) dem Schema H entsprechen, betr¨ agt

N (H, t + ∆t sel + ∆t cross )

≥ (1 − p c ) · N (H, t + ∆t sel )

= N (H, t + ∆t sel ) ·

= N (H, t + ∆t sel ) ·

= N (H, t) · f it rel (H) · popsize ·

4.2.4. Mutation

Bei der Mutation von Chromosmen wird ein Gen mit einer Mutationswahrscheinlichkeit p m mutiert. Im Umkehrschluss bedeutet dies, dass Gene mit einer Wahrscheinlichkeit (1 − p m ) 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 − p m ) 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¨ andigen Generationsschritt) zum Schema passen, errechnet sich somit durch

N (H, t + 1) = N (H, t + ∆t sel + ∆t cross ) · (1 − p m ) ord(H) . (4.13)

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 ∆t sel + ∆t cross + ∆t mut = 1) dem Schema H entsprechen, betr¨ agt

N (H, t + 1) =N (H, t) · f it rel (H) · popsize ·

Um nun die zu Beginn dargestellte Gleichung zu erhalten, ersetzt man f it rel (H) · popsize durch das sogenannte Fitnessverh¨ altnis. Es ist das Verh¨ altnis zwischen der mittleren Fitness des Schemas und der mittleren Fitness der Population. Diese Ersetzung kann man durchf¨ uhren, da

f it rel (H) · popsize =

Es ergibt sich demzufolge insgesamt

N (H, t + 1) = N (H, t) · f it rel (H) · popsize ·

4.3. Interpretation

Betrachten wir nun die Gleichung des Schema-Theorems, so l¨ asst sich erkennen, dass die Anzahl der zu einem Schema passenden Chromosomen direkt abh¨ angig von der vorangehenden Generation ist, die mit 3 Wichtungsfaktoren multipliziert wird. Diese sind

N (H, t + 1) = N (H, t) ·

Es stellt sich nun die Frage, welche Bedingungen das Schema erf¨ ullen muss, damit das Produkt der Faktoren A, B und C m¨ oglichst groß ist.

Betrachten wir zun¨ achst das Fitnessverh¨ altnis A. Damit die Chromosomenzahl steigt, muss A > 1 sein. Dies ist genau dann der Fall, wenn f it(H) > f it ist. Das bedeutet, dass die dem Schema entsprechenden Choromosmen im Mittel fitter sein m¨ ussen, als die gesamte Population im Durchschnitt. Weitehin gilt f¨ ur Faktor B, dass er zu keinem Zeitpunkt gr¨ oßer oder gleich 1 ist. Um den Gewinn von Faktor A nicht zu beeintr¨ achtigen, sollte B.1 m¨ oglichst klein sein. Dies wird erreicht, wenn das Schema eine kleine definierende L¨ ange besitzt. Die f¨ ur das Schema relevanten Gene befinden sich dann in einem kleinen Paket. Dieses Paket bezeichnet man auch als Building-Block. Der Faktor C zeigt ¨ ahnliche Eigenschaften wie Faktor B. Damit C nicht zu klein wird, muss der Exponent und damit die Ordnung des Schemas m¨ oglichst gering sein.

Fassen wir die Erkenntnisse zusammen: Bei einem genetischen Algorithmus werden immer die L¨ osungsraume mit den besten L¨ osungen 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¨ osung f¨ ur ein Problem aus einzelnen Building-Blocks, also Schemen mit geringer Ordnung und definierender L¨ ange zusammensetzt [GKK04, S.55]. Diese Building-Blocks werden ebenfalls bevorzugt in der Population verbreitet.

12

5. Eine Anwendung genetischer Algorithmen : Das

n-Damen Problem

Die Dame ist beim Schachspiel ” die m¨ achtigste Schachfigur.

Sie kann in Reihen und Spalten ziehen. Zus¨ atzlich kann sie sich auf den Diagonalen bewegen“ [mat]. Bereits 1848 erschien das R¨ atsel, ob man 8 Damen auf einem 8 x 8 Schachbrett (oder verallgemeinert n Damen auf einem n x n Feld) anordnen kann, sodass sich diese nicht gegenseitig bedrohen. Diese Frage repr¨ asentiert ein typisches Optimierungsproblem. Ziel ist es, die Anzahl der Kollisionen zwischen den Figuren zu minimieren. Aus diesem Grund verwendet der implementierte genetische Algorithmus die Zahl der Kollisionen (also Bedrohungen) als Fitness Funktion. Die Chromosomen 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 Tournament Selection (n¨ aheres zu dieser Selektionsart in [GKK04, S.84]) eingesetzt. Parallel dazu wurde der im Unterricht besprochene Backtracking Algorithmus implementiert, um einen Vergleich der Laufzeiten durchf¨ uhren zu k¨ onnen. 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¨ ankt sich auf zwei Aktionen. Zum einen kann die Feldgr¨ oße mit Hilfe der ” +“ und ” -“ Taste variiert werden, zum anderen kann entweder

der genetische Algorithmus oder das Backtracking f¨ ur das eingestellte Feld gestartet werden. Finden die Verfahren eine L¨ osung, so wird diese auf dem Schachfeld angezeigt. Rote Felder bedeuten hierbei, dass dort eine Dame platziert wird. Zus¨ atzlich wird im Textfeld die ben¨ otigte Zeit und die Anzahl der Generationen (genetischer Algorithmus) beziehungsweise die Anzahl der Versuche (Backtracking) angezeigt. Eine m¨ ogliche Ausgabe f¨ ur den genetischen Algorithmus bei einer Feldgr¨ oße n = 15 zeigt Abbildung 4.

Abbildung 5 demonstriert ein exemplarisches Ergebnis bei der Gr¨ oße n = 30. In Anhang D befindet sich eine ausf¨ uhrliche Testreihe, die mit Hilfe der Anwendung erstellt wurde. Anhang E zeigt den Quellcode der Anwendung.

13

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¨ osen k¨ onnen. 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 einer Feldgr¨ oße n = 30 die ben¨ otigte Zeit mit ungef¨ ahr 34 Minuten bereits sehr hoch, w¨ ahrend der genetische Algorithmus im Mittel nach 12 Sekunden eine L¨ osung hat. ¨ Uber das Laufzeitverhalten genetischer Algorithmen l¨ asst 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¨ otigt.

Das gr¨ oßte Problem bei genetischen Algorithmen liegt in der Modellfindung. Es ist oftmals schwer, f¨ ur 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¨ asst sich in kurzer Zeit erledigen. Dies ist der Vorteil genetischer Algorithmen. Sie sind flexibel und k¨ onnen leicht auf verschiedene Probleme adaptiert werden. Man muss allerdings beachten, dass der Algorithmus nicht immer eine L¨ osung liefert. Blicken wir zur¨ uck auf das Schema-Theorem (siehe Kapitel 4), so m¨ ussen 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¨ aufig verwendeten Zufallswerten zu tun. Das Theorem setzt vorraus, dass diese Werte auf dem gesamten Wertebereich gleichm¨ aßig verteilt sind, was allerdings nur bei besagter unendlich großer Population erf¨ ullt. Zum anderen sind in einer begrenzten Populationsgr¨ oße h¨ aufig nicht alle Schemen vertreten, wodurch manche (bessere) Schemen keine M¨ oglichkeit besitzen, sich durchzusetzen. Schlussendlich kann man sagen, dass genetische Algorithmen - trotz ihrer Einschr¨ ankungen - eine große Bereicherung f¨ ur die Informatik darstellen. So werden Genetische Algorith-Zweiphasen- ¨ men beispielsweise dazu verwendet, ” Uberschalld¨ usen“ zu optimieren [Hei94,

S.165f.]. 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¨ onnten. Dieses Beispiel stellt nur eines der Probleme dar, bei denen genetische Algorithmen entscheidend zur L¨ osung beigetragen haben. Folglich ist das Prinzip der Evolution nicht nur in der Biologie ein voller Erfolg.

14

A. Literatur

Die Literaturangaben sind alphabetisch nach den Namen der Autoren sortiert. Bei mehreren Autoren wird nach dem ersten Autor sortiert.

[Dav91] Davis, L. Handbook of Genetic Algorithms. Van Nostrand Reinhold, New York 1991. ISBN 978-0442001735.

[GKK04] Gerdes, I., Klawonn, F. & Kruse, R. Evolution¨ are Algorithmen. Friedr. Vieweg & Sohn Verlag/GWV Fachverlage GmbH, Wiesbaden 2004. ISBN 978-3528055707.

[Hei94] Heistermann, J. Genetische Algorithmen. B. G. Teubner Verlagsgesellschaft, Stuttgart, Leipzig 1994. ISBN 978-3815420571.

[HS05] Hilpold, T. & Stritzinger, A. Vorlesung - Backtracking Algorithmen (WS 2004/05). http://www.swe.uni-linz.ac.at/teaching/lva/ws04-05/algo2_ uebung/uebungen/ue3/Backtracking1.folien.pdf (Abgerufen am 23.02.2009), Ver¨ offentlicht 2005.

[Kru08] Kruse, R. Vorlesung - Evolution¨ are Algorithmen (SS 2008). http://fuzzy.cs. uni-magdeburg.de/wiki/pmwiki.php?n=Lehre.EvolAlg2008#Unterlagen (Abgerufen am 29.01.2009), Ver¨ offentlicht 2008.

[mat] Mathe-Online: Schachbrettaufgaben (Kap. 3.1). http://www.mathe-online.at/ materialien/matroid/files/schach/schachbrett.html#3.1 (Abgerufen am 22.02.2009).

15

B. Abbildungen

Abbildung 5: Testreihe des Programms bei der Gr¨ oße n = 30. Die Fenster 1 bis 3 wurden

C.  Abbildungsverzeichnis  

1.  One-Point-Crossover  5

2.  Mutation  6

3.  Startansicht des Programms  13

4.  Ergebnis des genetischen Algorithmus bei n 15  13

5.  Testreihe des Programms bei der Gr oße n 30  16

17

D.  Testreihe der Anwendung  

n  Ben otigte Generationen Ben otigte Zeit s Backtracking  

5  1 0,031 15 Versuche  

1  0,031 in 0,001s  

1   0,031

1   0,031

1   0,047

10  31 0,608 975 Versuche  

41  0,78 in 0,015s  

23   0,452

29   0,546

42   0,796

15  60 1,248 20.280 Versuche  

88  1,81 in 0,016s  

55   1,138

  120  2,481

45   0,936

20  71 1,685  3.992.510

  210 4,882 Versuche  

77  1,875 in 2,371s  

  360  8,268

  427  9,75

25  96 2,652  1.216.775

  265 7,145 Versuche  

  209 5,662 in 1,046s  

  602  16,349

  142  3,869

18

n  Ben otigte Generationen Ben otigte Zeit s Backtracking  

30  541 17,956  1.692.888.135

  554 17,831 Versuche  

  174 5,585 in 2101,506s  

  257 8,315 ( 34 Minuten)  

  339  10,779

35  356 12,995  8.244.234.495

  243 9,282 Versuche  

  285 10,608 in 12946,304s  

  273 10,109 ( 216 Minuten)  

  164  6,178

  100 1068 201,428 Nicht  

  2302 440,422 berechnet  

19

E. Quellcode der Anwendung

Die Anwendung ” n-Damen“, welche sich auf der beiliegenden CD im Ordner nDamen befindet, wurde mit der Programmiersprache Delphi erstellt. In dem Ordner befinden sich die Quellcode-Dateien (*.pas), die ausf¨ uhrbare Anwendung (*.exe), die Projektdatei f¨ ur die Enticklungsumgebung CodeGear Delphi 2007 (*.dproj), sowie einige Hilfsdateien.

uMain.pas Die Unit uMain beinhaltet die Oberfl¨ ache und die damit verbundene Verwaltung 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¨ oglicht, dass die Klassen der Suchalgorithmen einen Zugriff auf die Anzeigefunktionen des Fensters besitzen.

Listing 1: uMain.pas

unit uMain ;

i n t e r f a c e

5 uses

Windows , Messages , S y s U t i l s , V a r i a n t s , C l a s s e s , Graphics , C o n t r o l s , Forms ,

D i a l o g s , E x t C t r l s , S t d C t r l s , uGlobal , u B a c k t r a c k i n g , u G e n e t i c ;

type

TfrmMain = c l a s s (TForm , IOutput ) 10

i m g F i e l d : TImage ;

b t n B a c k t r a c k : TButton ;

b t n G e n e t i c : TButton ;

memOutput : TMemo;

btnDecN : TButton ; 15

btnIncN : TButton ;

l b l S i z e : TLabel ;

i m g S o l u t i o n : TImage ;

panButtons : TPanel ;

procedure FormCreate ( Sen der : TObject ) ;

procedure b t n I n c N C l i c k ( Se nd er : TObject ) ;

procedure btnDecNClick ( S en der : TObject ) ;

procedure b t n G e n e t i c C l i c k ( S en der : TObject ) ;

procedure b t n B a c k t r a c k C l i c k ( Se nde r : TObject ) ;

procedure FormResize ( S end er : TObject ) ;

private

f S i z e : i n t e g e r ;

public

procedure d r a w F i e l d ( p S o l u t i o n : Array of i n t e g e r ) ;

procedure drawText ( pText : String ) ; 30

end ;

var

frmMain : TfrmMain ; 35

implementation

{$R ∗ . dfm}

40 { Events }

procedure TfrmMain . FormCreate ( S en der : TObject ) ;

20

begin

// Z u f a l l s g e n e r a t o r und O b e r f l ¨ a c h e i n i t a l i s i e r e n 45 f S i z e := 4 ; d r a w F i e l d ( [ ] ) ; s e l f . D o u b l e B u f f e r e d := t r u e ; end ; 50

procedure TfrmMain . FormResize ( S en der : TObject ) ; begin

// M i n d e s t g r ¨ o ß e vom F e n s t e r e i n h a l t e n

i f frmMain . C l i e n t W i d t h <= 316 then

frmMain . C l i e n t W i d t h := 3 1 6 ; 55

i f frmMain . C l i e n t H e i g h t <= 413 then

frmMain . C l i e n t H e i g h t := 4 1 3 ;

60

// Elemente mitwachsen l a s s e n

i m g F i e l d . Width := frmMain . Cl i e n t W i d t h − 2 ∗ i m g F i e l d . L e f t ;

i m g F i e l d . H e i g h t := frmMain . C l i e n t H e i g h t − 2 ∗ i m g F i e l d . Top − panButtons . H e i g h t ;

panButtons . Top := i m g F i e l d . H e i g h t + i m g F i e l d . Top ; 65

panButtons . L e f t := i m g F i e l d . L e f t ;

panButtons . Width := i m g F i e l d . Width ;

//Im Unteren Panel d i e T e x t f l ¨ a c h e wachsen l a s s e n

memOutput . Width := frmMain . C l ie n t W i d t h − 2 5 6 ; 70

b t n B a c k t r a c k . L e f t := memOutput . L e f t + memOutput . Width + 8 ;

b t n G e n e t i c . L e f t := memOutput . L e f t + memOutput . Width + 8 ;

//Neu Z e i c h n e n

i m g F i e l d . P i c t u r e := n i l ; 75

d r a w F i e l d ( [ ] ) ;

end ;

procedure TfrmMain . b t n B a c k t r a c k C l i c k ( Se nde r : TObject ) ;

80 begin

// Thread e r s t e l l e n , g i b t s i c h s e l b e r f r e i wenn b e e n d e t

TBack tracker . C r e a t e ( s e l f , f S i z e ) ;

end ;

85 procedure TfrmMain . btnDecNClick ( Se nd er : TObject ) ;

begin

dec ( f S i z e ) ;

// Gr¨ oße b e t r ¨ a g t m i n d e s t e n s 4

i f f S i z e < 4 then

f S i z e := 4 ; 90

l b l S i z e . Caption := ’ n = ’ + IntToStr ( f S i z e ) ;

d r a w F i e l d ( [ ] ) ;

end ; 95

procedure TfrmMain . b t n G e n e t i c C l i c k ( S end er : TObject ) ;

begin

// Thread e r s t e l l e n , g i b t s i c h s e l b e r f r e i wenn b e e n d e t

T G e n e t i c S e a r c h . C r e a t e ( s e l f , f S i z e ) ;

100 end ;

procedure TfrmMain . b t n I n c N C l i c k ( S en der : TObject ) ;

begin

inc ( f S i z e ) ;

21

l b l S i z e . Caption := ’ n = ’ + IntToStr ( f S i z e ) ; 105 d r a w F i e l d ( [ ] ) ; end ;

{ P r o z e d u r e n }

110

procedure TfrmMain . d r a w F i e l d ( p S o l u t i o n : Array of i n t e g e r ) ; var x , y : i n t e g e r ; xStep , yStep : i n t e g e r ; xOff , y O f f : i n t e g e r ; 115

begin

// B i l d f l ¨ a c h e f ¨ u l l e n

i m g F i e l d . Canvas . Pen . C o l o r := c l B t n F a c e ; i m g F i e l d . Canvas . Brush . C o l o r := c l B t n F a c e ; 120

i m g F i e l d . Canvas . R e c t a n g l e ( 0 , 0 , i m g F i e l d . Width , i m g F i e l d . H e i g h t ) ;

// S c h r i t t w e i t e n e r m i t t e l n

xStep := i m g F i e l d . Width div f S i z e ; yStep := i m g F i e l d . H e i g h t div f S i z e ; 125

// Abstand vom l i n k e n und o b e r e n Rand e r m i t t e l n ( Z e n t r i e r e n ) x O f f := ( i m g F i e l d . Width − xStep ∗ f S i z e ) div 2 ; y O f f := ( i m g F i e l d . H e i g h t − yStep ∗ f S i z e ) div 2 ; 130

// F e l d e r z e i c h n e n

f o r x := 0 to f S i z e −1 do begin f o r y := 0 to f S i z e −1 do begin

// A l t e r n i e r e n d e s Schwarz−Weiß Muster e r z e u g e n 135

i f (Odd( x ) xor Odd( y ) ) then begin

i m g F i e l d . Canvas . Pen . C o l o r := c l W h i t e ;

i m g F i e l d . Canvas . Brush . C o l o r := c l W h i t e ;

end e l s e begin

i m g F i e l d . Canvas . Pen . C o l o r := c l B l a c k ; 140

i m g F i e l d . Canvas . Brush . C o l o r := c l B l a c k ;

end ;

i m g F i e l d . Canvas . R e c t a n g l e ( x O f f + x ∗ xStep , y O f f + y ∗ yStep , x O f f + ( x+1) ∗ xStep , y O f f + ( y+1) ∗ yStep ) ;

end ; 145

end ;

// L¨ osung e i n z e i c h n e n ( wenn vorhanden )

i f Length ( p S o l u t i o n ) > 0 then begin 150

i m g F i e l d . Canvas . Pen . C o l o r := clRed ;

i m g F i e l d . Canvas . Brush . C o l o r := clRed ;

f o r x := 0 to Length ( p S o l u t i o n ) do begin

i m g F i e l d . Canvas . R e c t a n g l e ( x O f f + x ∗ xStep , y O f f + p S o l u t i o n [ x ] ∗ yStep , 155

x O f f + ( x+1) ∗ xStep , y O f f + ( p S o l u t i o n [ x ] + 1 ) ∗ yStep ) ;

end ;

end ;

end ; 160

procedure TfrmMain . drawText ( pText : s t r i n g ) ;

begin

// I s t d e r Text l e e r , wird das gesamte F e ld g e l e e r t ,

22

memOutput . C l e a r e l s e

memOutput . L i n e s . Add( pText ) ; 170 end ;

end .

uGlobal.pas Die Unit uGlobal besitzt Strukturen, die von mehreren Klassen benutzt werden. Hierzu geh¨ ort 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

unit uG lo ba l ;

i n t e r f a c e

5 const

SOLPERGEN = 1 0 0 0 ; // Anzahl an L¨ osungen pro G e n e r a t i o n

type

IOutput = i n t e r f a c e

procedure d r a w F i e l d ( p S o l u t i o n : Array of i n t e g e r ) ; 10

procedure drawText ( pText : String ) ;

end ;

TIntArray = c l a s s ( TObject )

private 15

f S i z e : i n t e g e r ;

public

Data : Array of I n t e g e r ;

constructor C r e a t e ( p S i z e : i n t e g e r ) ;

procedure s e t S i z e ( p S i z e : i n t e g e r ) ; 20

procedure s e t D a t a ( pIndex : i n t e g e r ; pData : i n t e g e r ) ;

property Count : i n t e g e r read f S i z e write s e t S i z e ;

end ;

TIntArray2D = c l a s s ( TObject ) 25

public

Data : Array of Array of I n t e g e r ;

constructor C r e a t e ( pSizeX , pSizeY , p F i l l W i t h : i n t e g e r ) ;

end ; 30

implementation

constructor TIntArray . C r e a t e ( p S i z e : I n t e g e r ) ;

begin

s e t S i z e ( p S i z e ) ; 35

end ;

procedure TIntArray . s e t S i z e ( p S i z e : I n t e g e r ) ;

begin

S e t L e n g t h ( Data , p S i z e ) ; 40

f S i z e := p S i z e ;

end ;

procedure TIntArray . s e t D a t a ( pIndex : i n t e g e r ; pData : i n t e g e r ) ;

// I s t g e w ¨ u n s c h t e r Index a u ß e r h a l b d e r a k t . L i s t e , s e l b i g e // a u t o m a t i s c h v e r g r ¨ o ß e r n i f pIndex > High ( Data ) then S e t S i z e ( pIndex + 1 ) ; 50

Data [ pIndex ] := pData ;

end ;

constructor TIntArray2D . C r e a t e ( pSizeX : I n t e g e r ; pSizeY : I n t e g e r ;

p F i l l W i t h : I n t e g e r ) ; 55 var

i : I n t e g e r ;

j : I n t e g e r ;

begin

S e t L e n g t h ( Data , pSizeX ) ; 60

// F e l d e r mit Vorgabewert f ¨ u l l e n

f o r i := 0 to pSizeX − 1 do begin

S e t L e n g t h ( Data [ i ] , pSizeY ) ; f o r j := 0 to pSizeY − 1 do

Data [ i ] [ j ] := p F i l l W i t h ; 65

end ;

end ;

70 end .

uStack.pas Die Unit uStack beinhaltet den abstrakten Datentyp TStack, wie er bereits

im Unterricht besprochen wurde.

Listing 3: uStack.pas

unit uStack ;

i n t e r f a c e

5 uses Types ;

type

TStackItem = c l a s s

private

FNext : TStackItem ; 10

FData : TObject ;

public

constructor C r e a t e ( pData : TObject ) ; o v e r l o a d ;

constructor C r e a t e ( pData : TObject ; pNext : TStackItem ) ; o v e r l o a d ;

property Next : TStackItem read FNext write FNext ; 15

property Data : TObject read FData write FData ;

destructor D e s t r o y ; override ;

end ;

TStack = c l a s s 20

protected

t o s : TStackItem ;

public

constructor C r e a t e ( ) ;

function pop ( ) : TObject ; 25

function top ( ) : TObject ;

function isEmpty ( ) : b o o l e a n ;

procedure push ( pData : TObject ) ;

end ;

24

30 implementation

// TStackItem

constructor TStackItem . C r e a t e ( pData : TObject ) ; 35 begin FData := pData ; FNext := n i l ; end ;

40 constructor TStackItem . C r e a t e ( pData : TObject ; pNext : TStackItem ) ; begin FData := pData ; FNext := pNext ; end ; 45

destructor TStackItem . D e s t r o y ; begin FData . D e s t r o y ; inherited D e s t r o y ( ) ; 50 end ;

// TStack

constructor TStack . C r e a t e ( ) ; begin t o s := n i l ; 55 end ;

function TStack . pop ( ) : TObject ;

var tmpTos : TStackItem ; 60

begin

r e s u l t := t o s . Data ; tmpTos := t o s ; t o s := t o s . Next ; 65 tmpTos . D e s t r o y ; end ;

function TStack . top ( ) : TObject ;

70 begin r e s u l t := t o s . Data ; end ;

function TStack . isEmpty ( ) : b o o l e a n ;

75 begin r e s u l t := t o s = n i l ; end ;

procedure TStack . push ( pData : TObject ) ;

80 begin

t o s := TStackItem . C r e a t e ( pData , t o s ) ; end ;

end .

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¨ atzlich die Funktion, den aktuellen Stack in eine Liste des Typs TIntArray zu

25

kopieren.

Listing 4: uObjectPointStack.pas

unit u O b j e c t P o i n t S t a c k ;

i n t e r f a c e

5 uses uStack , uGlobal , t y p e s ;

type

TObjectPoint = c l a s s ( TObject ) public X, Y : i n t e g e r ; 10

constructor C r e a t e (pX , pY : i n t e g e r ) ; end ;

T O b j e c t P o i n t S t a c k = c l a s s ( TStack )

public 15

function pop ( ) : TObjectPoint ; function top ( ) : TObjectPoint ; function t o I n t A r r a y ( ) : TIntArray ; end ; 20 implementation

constructor TObjectPoint . C r e a t e (pX , pY : i n t e g e r ) ;

begin X := pX ; 25 Y := pY ; end ;

function T O b j e c t P o i n t S t a c k . pop ( ) : TObjectPoint ;

30 begin

r e s u l t := inherited pop ( ) as TObjectPoint ; end ;

function T O b j e c t P o i n t S t a c k . top ( ) : TObjectPoint ;

35 begin

r e s u l t := inherited top ( ) as TObjectPoint ; end ;

function T O b j e c t P o i n t S t a c k . t o I n t A r r a y ( ) : TIntArray ;

40 var pnt : TStackItem ;

begin

r e s u l t := TIntArray . C r e a t e ( 1 ) ; 45

pnt := t o s ;

while pnt <> n i l do begin

r e s u l t . s e t D a t a ( ( pnt . Data as TObjectPoint ) . X, ( pnt . Data as TObjectPoint ) . Y ) ;

pnt := pnt . Next ; 50

end ;

end ;

end .

26

uRingList.pas In der Unit uRingList wird der abstrakte Datentyp TRingList implementiert. Diese im Ring verkettete Liste wird f¨ ur die Verwaltung der Population des genetischen Algorithmus verwendet.

Listing 5: uRingList.pas

unit u R i n g L i s t ;

i n t e r f a c e

5 type

TRingListItem = c l a s s private FNext : TRingListItem ; FData : TObject ; 10

constructor C r e a t e ( pData : TObject ) ; o v e r l o a d ; constructor C r e a t e ( pData : TObject ; pNext : TRingListItem ) ; o v e r l o a d ; property Next : TRingListItem read FNext write FNext ; property Data : TObject read FData write FData ; destructor D e s t r o y ; override ; 15 end ;

TRingList = c l a s s

protected

p r e P o s i t i o n : TRingListItem ;

l a s t P o s l a s t P r e P o s public 25 constructor C r e a t e ; function isEmpty : b o o l e a n ; function g e t I t e m : TObject ; procedure add ( pData : TObject ) ; procedure n e x t ; o v e r l o a d ; 30

procedure n e x t ( p S t e p s : i n t e g e r ) ; o v e r l o a d ; procedure remove ; procedure removeLast ; // Wird f ¨ u r den S e l e k t i o n s m o d u s b e n ¨ o t i g t ,

destructor D e s t r o y ; override ; //um d i e RAM A u s l a s t u n g g e r i n g zu h a l t e n end ; 35

implementation

{ ############ TRingListItem ############ }

40

constructor TRingListItem . C r e a t e ( pData : TObject ) ;

begin FData := pData ; FNext := n i l ; 45 end ;

constructor TRingListItem . C r e a t e ( pData : TObject ; pNext : TRingListItem ) ; begin FData := pData ; 50 FNext := pNext ; end ;

destructor TRingListItem . D e s t r o y ;

//Auch d i e Daten l ¨ o s c h e n FData . D e s t r o y ;

// und dann s i c h s e l b s t

inherited D e s t r o y ( ) ; 60 end ;

{ ############ TRingList ############ }

65 constructor TRingList . C r e a t e ;

begin an ch or := n i l ; p o s i t i o n := n i l ; p r e P o s i t i o n := n i l ; l a s t P o s := n i l ; 70 end ;

function TRingList . isEmpty : b o o l e a n ; begin

r e s u l t := ( an cho r = n i l ) ; 75 end ;

function TRingList . g e t I t e m : TObject ; begin

r e s u l t := p o s i t i o n . Data ; 80 end ;

procedure TRingList . n e x t ;

begin i f not isEmpty then begin 85

p r e P o s i t i o n := p o s i t i o n ; p o s i t i o n := p o s i t i o n . n e x t ; end ; end ; 90

procedure TRingList . n e x t ( p S t e p s : I n t e g e r ) ; var i : i n t e g e r ;

95 begin

l a s t P r e P o s := p r e P o s i t i o n ; l a s t P o s := p o s i t i o n ;

f o r i := 0 to p S t e p s do

100 end ;

procedure TRingList . add ( pData : TObject ) ; begin i f isEmpty then begin 105

an ch or := TRingListItem . C r e a t e ( pData ) ; p o s i t i o n := an cho r ; p r e P o s i t i o n := an ch or ; 110 end e l s e begin

p r e P o s i t i o n := p o s i t i o n ;

p o s i t i o n := TRingListItem . C r e a t e ( pData ) ; 115 end ;

28

p o s i t i o n . Next := p r e P o s i t i o n . Next ; p r e P o s i t i o n . Next := p o s i t i o n ; 120 end ;

procedure TRingList . remove ;

begin

i f p o s i t i o n . Next = p o s i t i o n then begin 125

p o s i t i o n . D e s t r o y ;

an ch or := n i l ; p r e P o s i t i o n := n i l ; p o s i t i o n := n i l ; 130

end e l s e begin

i f p o s i t i o n = anc hor then

an cho r := an ch or . Next ; 135

p o s i t i o n . D e s t r o y ;

p o s i t i o n := p o s i t i o n . Next ; p r e P o s i t i o n . Next := p o s i t i o n ; 140 end ;

end ;

145 procedure TRingList . removeLast ;

begin

l a s t P r e P o s . Next := l a s t P o s . Next ;

l a s t P o s . D e s t r o y ;

// ¨ U b e r p r ¨ u f e n ob k e i n Element mehr da 150

i f l a s t P r e P o s = n i l then begin

an cho r := n i l ;

p o s i t i o n := n i l ;

p r e P o s i t i o n := n i l ;

l a s t P o s := n i l ; 155

end ;

end ;

destructor TRingList . D e s t r o y ;

160 begin

// A l l e Elemente l ¨ o s c h e n

while not isEmpty do remove ;

// und s i c h s e l b s t

inherited D e s t r o y ( ) ; 165

end ;

end .

uBacktracking.pas Die Unit uBacktracking beinhaltet die Klasse TBacktracker, welche

von der Klasse TThread erbt. Die Klasse implementiert den Backtracking Algorithmus f¨ ur

das n-Damen Problem.

Listing 6: uBacktracking.pas

unit u B a c k t r a c k i n g ;

29

i n t e r f a c e

5 uses uGlobal , u O b j e c t P o i n t S t a c k , c l a s s e s , S y s U t i l s , Windows ;

type

TBack tracker = c l a s s ( TThread ) private f I n t e r f a c e : IOutput ; 10

f S i z e f D i s p S o l f T r i e s

function g e t S o l u t i o n ( p S o l u t i o n : TIntArray ; pRow : i n t e g e r ) : b o o l e a n ; function i s C o l l i d i n g ( p S o l u t i o n : TIntArray ; pUpToRow : i n t e g e r ) : b o o l e a n ; 15 protected procedure Execute ; override ; procedure D i s p l a y ; public

constructor C r e a t e ( p I n t e r f a c e : IOutput ; p S i z e : i n t e g e r ) ; 20 end ;

implementation

25

constructor TBack tracker . C r e a t e ( p I n t e r f a c e : IOutput ; p S i z e : i n t e g e r ) ; begin

inherited C r e a t e ( t r u e ) ; // P a u s i e r t e n Thread e r s t e l l e n

f I n t e r f a c e := p I n t e r f a c e ; 30 f S i z e := p S i z e ;

f I n t e r f a c e . drawText ( ’ ’ ) ;

f I n t e r f a c e . drawText ( ’ B a c k t r a c k e r i n i t a l i s i e r t ! ’ ) ; 35

// V a r i a b l e n i n i t a l i s i e r t , j e t z t Thread l o s l a u f e n l a s s e n s e l f . Resume ; end ;

40 function TBack tracker . g e t S o l u t i o n ( p S o l u t i o n : TIntArray ; pRow : i n t e g e r ) : b o o l e a n ; var i : i n t e g e r ;

45 begin

i f pRow = Length ( p S o l u t i o n . Data ) then begin // F e r t i g ! : −) r e s u l t := t r u e ; e x i t ; end ; 50

r e s u l t := f a l s e ;

f o r i := 0 to Length ( p S o l u t i o n . Data ) − 1 do begin

55

p S o l u t i o n . Data [ pRow ] := i ;

inc ( f T r i e s ) ;

i f not i s C o l l i d i n g ( p S o l u t i o n , pRow) then 60

r e s u l t := g e t S o l u t i o n ( p S o l u t i o n , pRow + 1 ) ;

i f r e s u l t = t r u e then e x i t ;

30

65

// H i e r d ¨ u r f t e man e i g e n t l i c h n i c h t s e i n , // a u ß e r e s e x i s t i e r t k e i n e L¨ osung . . . s c h a d e : −( r e s u l t := f a l s e ; 70 end ;

function TBack tracker . i s C o l l i d i n g ( p S o l u t i o n : TIntArray ; pUpToRow : i n t e g e r ) : b o o l e a n ; 75 var i , j : i n t e g e r ;

begin

r e s u l t := f a l s e ; 80

f o r i := 0 to pUpToRow do begin

// F¨ ur j e d e Dame d i e h o r i z o n t a l e n und d i a g o n a l e n Wege ¨ u b e r p r ¨ u f e n

f o r j := 0 to pUpToRow do begin i f i <> j then begin 85

// Check 1 : H o r i z o n t a l e r Pfad

i f p S o l u t i o n . Data [ i ] = p S o l u t i o n . Data [ j ] then

r e s u l t := t r u e ;

// Check 2 : D i a g o n a l e r Pfad von l i n k s −unten nach r e c h t s −oben 90

i f p S o l u t i o n . Data [ i ] = p S o l u t i o n . Data [ j ] − ( i − j ) then

r e s u l t := t r u e ;

// Check 3 : D i a g o n a l e r Pfad von l i n k s −oben nach r e c h t s −unten

i f p S o l u t i o n . Data [ i ] = p S o l u t i o n . Data [ j ] + ( i − j ) then 95

r e s u l t := t r u e ;

// Abbrechen wenn K o l l i s i o n g e f u n d e n

i f r e s u l t = t r u e then 100

end ;

end ;

end ; 105 end ;

procedure TBack tracker . Execute ; var

begin

// V a r i a b l e n i n i t a l i s i e r e n

f T r i e s := 0 ; 115

s t a r t := GetTickCount ; // Z e i t m e s s u n g

s o l u t i o n := TIntArray . C r e a t e ( f S i z e ) ;

// R e k u r s i v e Suche s t a r t e n 120

i f g e t S o l u t i o n ( s o l u t i o n , 0 ) then begin

f D i s p S o l := s o l u t i o n ;

S y n c h r o n i z e ( D i s p l a y ) ; 125

f I n t e r f a c e . drawText ( ’ ’ ) ;

31

f I n t e r f a c e . drawText ( ’ L¨ osung nach ’ + IntToStr ( f T r i e s )

+ ’ Versuchen g e f u n d e n ! ’ ) ;

f I n t e r f a c e . drawText ( ’ B e n ¨ o t i g t e Z e i t : ’ 130 end e l s e begin f I n t e r f a c e . drawText ( ’ ’ ) ;

f I n t e r f a c e . drawText ( ’ Keine L¨ osung g e f u n d e n ! ’ ) ; end ; 135 s e l f . D e s t r o y ; s e l f . Free ; end ;

140 procedure TBack tracker . D i s p l a y ;

begin

i f f D i s p S o l <> n i l then

f I n t e r f a c e . d r a w F i e l d ( f D i s p S o l . Data )

e l s e

f I n t e r f a c e . d r a w F i e l d ( [ ] ) ; 145

end ;

end .

uGenetic.pas Die Unit uGenetic beinhaltet die Klasse TGeneticSearch, welche von der

Klasse TThread erbt. Die Klasse implementiert den genetischen Algorithmus f¨ ur das n-Damen

Problem.

Listing 7: uGenetic.pas

unit u G e n e t i c ;

i n t e r f a c e

5 uses

uGlobal , c l a s s e s , s y s U t i l s , Windows , u R i n g L i s t ;

type

T G e n e t i c S e a r c h = c l a s s ( TThread )

private 10

f I n t e r f a c e : IOutput ;

f S i z e

f D i s p S o l

function G e t F i t n e s s ( p S o l u t i o n : TIntArray ) : I n t e g e r ;

function Mutate ( p S o l u t i o n : TIntArray ) : TIntArray ; 15

function Combine ( pSol1 , p S o l 2 : TIntArray ) : TIntArray ;

protected

procedure Execute ; override ;

procedure D i s p l a y ;

public 20

constructor C r e a t e ( p I n t e r f a c e : IOutput ; p S i z e : i n t e g e r ) ;

end ;

implementation 25

constructor T G e n e t i c S e a r c h . C r e a t e ( p I n t e r f a c e : IOutput ; p S i z e : i n t e g e r ) ;

begin

inherited C r e a t e ( t r u e ) ; // P a u s i e r t e n Thread e r s t e l l e n

f I n t e r f a c e := p I n t e r f a c e ; 30

32

f S i z e := p S i z e ;

f I n t e r f a c e . drawText ( ’ ’ ) ;

f I n t e r f a c e . drawText ( ’ G e n e t i s c h e r A l g o r i t h m u s i n i t a l i s i e r t ! ’ ) ; 35

// V a r i a b l e n i n i t a l i s i e r t , j e t z t Thread l o s l a u f e n l a s s e n s e l f . Resume ; end ;

40 function T G e n e t i c S e a r c h . G e t F i t n e s s ( p S o l u t i o n : TIntArray ) : I n t e g e r ; var

i , j , c o l : i n t e g e r ;

begin

45

// Anzahl d e r K o l l i s i o n e n e r m i t t e l n und z u r ¨ u c k g e b e n c o l := 0 ;

f o r i := 0 to p S o l u t i o n . Count − 1 do begin

// F¨ ur j e d e Dame d i e h o r i z o n t a l e n und d i a g o n a l e n Wege ¨ u b e r p r ¨ u f e n 50

f o r j := 0 to p S o l u t i o n . Count − 1 do begin

i f i <> j then begin

// Check 1 : H o r i z o n t a l e r Pfad

i f p S o l u t i o n . Data [ i ] = p S o l u t i o n . Data [ j ] then

// Check 2 : D i a g o n a l e r Pfad von l i n k s −unten nach r e c h t s −oben

i f p S o l u t i o n . Data [ i ] = p S o l u t i o n . Data [ j ] − ( i − j ) then

inc ( c o l ) ; 60

// Check 3 : D i a g o n a l e r Pfad von l i n k s −oben nach r e c h t s −unten

i f p S o l u t i o n . Data [ i ] = p S o l u t i o n . Data [ j ] + ( i − j ) then

end ;

end ;

end ; 70

//Da b e i e i n e r K o l l i s i o n immer z w e i F i g u r e n b e t e i l i g t s i n d ( und c o l

// s o m i t z w e i mal i n k r e m e n t i e r t wird ) , muss das E r g e b n i s durch z w e i

// d i v i d i e r t werden um a u f d i e Anzahl e i n m a l i g e r K o l l i s i o n e n zu kommen

r e s u l t := c o l div 2 ; 75

end ;

function T G e n e t i c S e a r c h . Mutate ( p S o l u t i o n : TIntArray ) : TIntArray ;

80 var

i : I n t e g e r ;

begin

// U r s p r u n g s o b j e k t i n e i n n e u e s k o p i e r e n

r e s u l t := TIntArray . C r e a t e ( p S o l u t i o n . Count ) ; 85

f o r i := 0 to p S o l u t i o n . Count − 1 do begin

// M u t a t i o n s w a h r s c h e i n l i c h k e i t 1/ l i f Random < 1/ p S o l u t i o n . Count then

r e s u l t . Data [ i ] := Random( r e s u l t . Count ) 90

e l s e

r e s u l t . Data [ i ] := p S o l u t i o n . Data [ i ] ;

33

end ; end ; 95

function T G e n e t i c S e a r c h . Combine ( p S o l 1 : TIntArray ;

p S o l 2 : TIntArray ) : TIntArray ; var

i : I n t e g e r ;

c r o s s : I n t e g e r ; 100

begin

// Kombinieren

r e s u l t := TIntArray . C r e a t e ( Length ( p S o l 1 . Data ) ) ; 105

// Kreuzungspunkt

c r o s s := Random( r e s u l t . Count ) ;

f o r i := 0 to Length ( p S o l 1 . Data ) − 1 do begin 110

// Die l i n k e H ¨ a l f t e e r b t aus pSol1 , d i e r e c h t e aus p S o l 2

i f i <= c r o s s then

r e s u l t . Data [ i ] := p S o l 1 . Data [ i ]

e l s e

r e s u l t . Data [ i ] := p S o l 2 . Data [ i ] ; 115

end ;

end ;

procedure T G e n e t i c S e a r c h . Execute ; 120 var

p o p u l a t i o n : TRingList ;

begin

p o p u l a t i o n := TRingList . C r e a t e ; 130

f i n i s h e d := f a l s e ;

gen := 0 ;

avg := 0 ; s t a r t := GetTickCount ; // Z e i t m e s s u n g 135

// A n f a n g s p o p u l a t i o n g e n e r i e r e n f o r i := 1 to SOLPERGEN do begin

tempSol := TIntArray . C r e a t e ( f S i z e ) ; 140

f o r j := 0 to ( f S i z e − 1 ) do begin

tempSol . Data [ j ] := Random( f S i z e ) ;

end ; 145

p o p u l a t i o n . add ( tempSol ) ;

end ;

f D i s p S o l := n i l ; 150

S y n c h r o n i z e ( D i s p l a y ) ;

while not f i n i s h e d do begin

34

155

f o r i := 1 to SOLPERGEN div 2 do begin

// Mutation

p o p u l a t i o n . n e x t (Random(SOLPERGEN ) ) ; 160

p o p u l a t i o n . add (

mutate (

TIntArray ( p o p u l a t i o n . g e t I t e m ) ) ) ;

// Kombination 165

p o p u l a t i o n . n e x t (Random(SOLPERGEN ) ) ;

tempSol := TIntArray ( p o p u l a t i o n . g e t I t e m ) ;

p o p u l a t i o n . n e x t (Random(SOLPERGEN ) ) ;

tempSol := combine ( tempsol , TIntArray ( p o p u l a t i o n . g e t I t e m ) ) ; 170

p o p u l a t i o n . add ( tempSol ) ;

end ;

// S e l e k t i o n ( B e v ¨ o l k e r u n g p e r Tournament−S e l e k t i o n w i e d e r a u f 175

// e i n e Gr¨ oße von SOLPERGEN b r i n g e n )

f o r i := 1 to SOLPERGEN do begin

// Z u f ¨ a l l i g z w e i L¨ osungen w¨ ahlen , g e g e n e i n e n a d e r ’ a n t r e t e n ’ 180

// l a s s e n ( F i t n e s s w e r t e v e r g l e i c h e n ) und den Gewinner i n // d i e n ¨ a c h s t e G e n e r a t i o n ¨ ubernehmen

p o p u l a t i o n . n e x t (Random(SOLPERGEN ) ) ;

tempSol := TIntArray ( p o p u l a t i o n . g e t I t e m ) ; 185

p o p u l a t i o n . n e x t (Random(SOLPERGEN ) ) ;

i f G e t F i t n e s s ( tempSol )

<= G e t F i t n e s s ( TIntArray ( p o p u l a t i o n . g e t I t e m ) ) then

p o p u l a t i o n . remove 190

e l s e

p o p u l a t i o n . removeLast ;

end ; 195

// L¨ osung g e f u n d e n ? Wenn n e i n , dann w i e d e r nach oben

// ( g l e i c h z e i t i g D u r c h s c h n i t t s f i t n e s s b e r e c h n e n )

avg := 0 ;

j := 0 ;

f o r i := 1 to SOLPERGEN do begin 200

j := G e t F i t n e s s ( TIntArray ( p o p u l a t i o n . g e t I t e m ) ) ;

avg := avg + j ;

i f j = 0 then begin 205

tempSol := TIntArray ( p o p u l a t i o n . g e t I t e m ) ;

f i n i s h e d := t r u e ;

end ;

p o p u l a t i o n . n e x t ; 210

end ;

// A b b r u c h k r i t e r i u m : 5000 G e n e r a t i o n e n ohne E r f o l g

i f gen = 5000 then begin 215

tempSol := n i l ;

35

f i n i s h e d := t r u e ; end ;

i f ( gen mod 10 = 0 ) then begin 220

f I n t e r f a c e . drawText ( ’ ’ ) ;

f I n t e r f a c e . drawText ( ’ G e n e r a t i o n : ’ + IntToStr ( gen ) ) ;

f I n t e r f a c e . drawText ( ’ D u r c h s c h n i t t l . F i t n e s s : ’

+ Format( ’ %.2 f ’ , [ avg / SOLPERGEN ] ) ) ;

end ; 225

inc ( gen ) ;

end ; 230

f D i s p S o l := tempSol ;

S y n c h r o n i z e ( D i s p l a y ) ;

f I n t e r f a c e . drawText ( ’ ’ ) ; 235

i f f D i s p S o l = n i l then begin

f I n t e r f a c e . drawText ( ’ Keine L¨ osung nach 5000 G e n e r a t i o n e n g e f u n d e n ! ’ ) ;

end e l s e begin

f I n t e r f a c e . drawText ( ’ L¨ osung g e f u n d e n ! ’ ) ;

f I n t e r f a c e . drawText ( ’ B e n ¨ o t i g t e G e n e r a t i o n e n : ’ + IntToStr ( gen ) ) ; 240

end ;

f I n t e r f a c e . drawText ( ’ B e n ¨ o t i g t e Z e i t : ’ + FloatToStr ( ( GetTickCount − s t a r t ) / 1 0 0 0 ) + ’ Sekunden ’ ) ;

f I n t e r f a c e . drawText ( ’ L e t z t e d u r c h s c h n i t t l . F i t n e s s : ’ 245

+ Format( ’ %.2 f ’ , [ avg / SOLPERGEN ] ) ) ;

p o p u l a t i o n . D e s t r o y ;

s e l f . D e s t r o y ;

250 end ;

procedure T G e n e t i c S e a r c h . D i s p l a y ;

begin

i f f D i s p S o l <> n i l then

f I n t e r f a c e . d r a w F i e l d ( f D i s p S o l . Data ) 255

e l s e

f I n t e r f a c e . d r a w F i e l d ( [ ] ) ; end ;