Entwicklung von Handelssystemen mittels genetischer Programmierung anhand eines Fallbeispiels

Inhaltsverzeichnis

1  Einführung  1

1.1  Motivation  1

1.2  Ziel und Aufbau  2

2  Grundlagen und Stand der Technik  5

2.1  Genetische Programmierung  5

2.1.1  Aufbau eines Programms  5

2.1.2  Initialisierung der GP Population  6

2.1.3  Die Genetischen Operatoren  7

2.1.4  Fitness Funktion  8

2.1.5  Selektion  9

2.1.6  Ablauf des GP Algorithmus  10

2.1.7  Crossover Building Blocks und Schemata  11

2.1.8  Ansätze gegen Makromutation  12

2.1.9  Modularisierung  14

2.1.10  Weitere Verbesserungsansätze  16

2.2  Künstliche Neuronale Netze  16

2.2.1  Bestandteile neuronaler Netze  17

2.2.2  Netztopologien  18

2.2.3  Lernmethoden  18

2.3  Handelssysteme  20

2.3.1  Tape Reader  21

2.3.2  Market Timing  22

2.3.3  Position Sizing  24

2.3.4  Vergleich von Handelssystemen  27

2.3.5  Fundamentale versus Technische Analyse  30

2.3.6  Der Währungsmarkt  34

2.3.7  Entwicklungsansätze für Handelssysteme in der Literatur  35

  i  

3 Entwurf 39

3.1 Überblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2 Anforderungen an die Software . . . . . . . . . . . . . . . . . . . 39

3.3 Konzeption der Software . . . . . . . . . . . . . . . . . . . . . . . 42

3.3.1 Der Evolutionäre Algorithmus . . . . . . . . . . . . . . . 42

3.3.2 Die Fitness-Funktion . . . . . . . . . . . . . . . . . . . . . 45

4 Implementierung 49

4.1 Komponenten der entwickelten Software . . . . . . . . . . . . . 49

4.2 Klassen des Kursdatenservers . . . . . . . . . . . . . . . . . . . . 50

4.3 Klassen des Evolutionären Algorithmus . . . . . . . . . . . . . . 51

4.4 Übersicht über das Framework ECJ . . . . . . . . . . . . . . . . . 54

4.5 Probleme während der Experimente . . . . . . . . . . . . . . . . 55

5 Versuchsergebnisse 57

5.1 Resultate mit Knotengewichten . . . . . . . . . . . . . . . . . . . 57

5.1.1 Resultate des Trainingszeitraums . . . . . . . . . . . . . . 58

5.1.2 Resultate des Validierungszeitraums . . . . . . . . . . . . 58

5.1.3 Resultate des Testzeitraums . . . . . . . . . . . . . . . . . 59

5.1.4 Resultate als Monatsrenditen . . . . . . . . . . . . . . . . 60

5.1.5 Erzeugte Handelsregeln . . . . . . . . . . . . . . . . . . . 61

5.2 Resultate ohne Knotengewichte . . . . . . . . . . . . . . . . . . . 64

5.2.1 Resultate des Trainingszeitraums . . . . . . . . . . . . . . 64

5.2.2 Resultate des Validierungszeitraums . . . . . . . . . . . . 64

5.2.3 Resultate des Testzeitraums . . . . . . . . . . . . . . . . . 65

5.2.4 Resultate als Monatsrenditen . . . . . . . . . . . . . . . . 66

5.2.5 Erzeugte Handelsregeln . . . . . . . . . . . . . . . . . . . 67

5.3 Bestimmung und Anwendung von Optimal f . . . . . . . . . . . 67

6 Diskussion und Bewertung 77

6.1 Ausblick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78

7 Zusammenfassung 81

Abbildungsverzeichnis 86

Literaturverzeichnis 92

Glossar 93

Kapitel 1

Einführung

1.1 Motivation

Die natürliche Evolution hat sich zur Erzeugung und Anpassung von Lebewesen an eine sich ändernde Umgebung als höchst erfolgreicher Mechanismus herausgestellt. Ohne bestimmte Anweisungen oder auch nur genaue Zieldefinitionen zu erhalten, ist es ihr gelungen, raffinierte Lösungen für Probleme der realen Welt zu finden.

Ein Ansatz, die in der natürlichen Evolution steckende kreative Kraft zur automatischen Entwicklung von ComputerProgrammen zu verwenden, ist die Genetische Programmierung (GP) (vgl. (Koz92, Kapitel 16)). Mit ihr wird versucht, Mechanismen der natürlichen Evolution nachzuahmen, um automatisch Programme zu erzeugen, die ein gegebenes Problem lösen. GP ist in einer Reihe von Anwendungen sowohl zum Lösen mathematischer Proble-me als auch zum Beheben von Problemen der realen Welt erfolgreich ange-wandt worden. Hierzu zählen z.B. Symbolische Regression (Koz92, S. Kapitel 10), Klassifikation (Koz92, Kapitel 17), Synthese Künstlicher Neuronaler Net-ze (Gru94, Kapitel 2f), Muster Erkennung (Tac93, S. 2-10), Roboter Steuerung (BNO97, S. 2-10) und Generierung von Bildern (GH97, S. 2-7).

Das maschinelle Lernen mittels GP kann als ein heuristischer Suchalgorithmus interpretiert werden, der in der Menge aller möglichen Programme diejenigen sucht, die das gegebene Problem am besten lösen. Da der Suchraum je nach gegebenem Problem sehr groß und oft weder stetig noch differenzierbar ist, eignet sich der Suchraum aller möglichen Programme schlecht für klassische Suchalgorithmen (vgl. (LP02, S. 2f)).

Das Anwendungsgebiet der GP in dieser Arbeit ist die Erzeugung von Handelssystemen für den Finanzmarkt, insbesondere für den Währungsmarkt. An den Finanzmärkten handeln erfolgreiche spekulative Händler gewöhnlich aufgrund gewisser Regelwerke. Diese Regelwerke sind jedoch relativ starker individueller Interpretation unterworfen. Bei genauer Betrachtung fällt auf, dass Händler die Regeln, nach denen sie zu handeln meinen, in entscheidenden Situationen beugen und gewissermaßen nach ihrem „Bauchgefühl“ handeln. Evtl. unterscheidet dieser Anteil an intuitivem Handeln einen erfahrenen profitablen Händler von einem unerfahrenen unprofitablen Händler, auch

1

KAPITEL 1. EINFÜHRUNG

2

wenn beide meinen, nach dem gleichen Regelwerk zu arbeiten. Das Definieren eines Handelssystems durch einen Menschen ist mit Schwierigkeiten verbunden, da er nicht alle Regeln eindeutig wiedergeben kann. Daher hat sich die Übertragung von Regelwerken zum Handeln auf einen Rechner als nicht erfolgreich herausgestellt.

Ein anderer Ansatz ist, den Rechner die Handelsregeln selbst lernen zu lassen. Hierzu werden z.B. Künstliche Neuronale Netze (KNN) erfolgreich eingesetzt (vgl. (Ska01, S. 2-5), (MK, S. 2-7)). Es ist jedoch nicht ohne weiteres möglich, die einzelnen Regeln in einfach deutbarer Weise aus dem Netz zu extrahieren. Diese „Black-Box“ Eigenschaft von KNN wird von Anwendern kritisiert.

GP bietet sich als Alternative zu KNN an, da sie direkt Regeln erzeugen kann

und sich diese trotz einiger Komplexität besser deuten lassen (vgl. (YCK05, S. S. 23f)). Was die Fähigkeit zur Lösung schwieriger Probleme angeht, sind beide Ansätze vergleichbar (vgl. (BB98, S. 13)).

1.2 Ziel und Aufbau

Ziel dieser Arbeit ist es, GP anzuwenden, um Handelssysteme zu erzeugen und auf Profitabilität im Rahmen einer historischen Simulation zu untersuchen. Ein Softwaresystem, das diese Aufgabe löst, wird entworfen und interessante Implementierungsaspekte dargestellt.

Um Handelssysteme mit GP entwickeln zu können, muss die zu entwickelnde Software einer Reihe von Anforderungen genügen. Die Entwicklung der Handelssysteme soll basierend auf historischen Kurszeitreihen vorgenommen werden. Es wird angenommen, dass sich der Markt mit der Zeit ändert und daher ehemals profitable Handelssysteme an Profitabilität verlieren. Daher ist es nötig, das Entwicklungssystem der Handelssysteme so zu konzipieren, dass im Laufe der Zeit neue, an die geänderten Marktbedingungen angepasste Handelssysteme erzeugt werden können. Um die Versorgung mit aktuellen Kursdaten sicherzustellen, müssen die relevanten Marktdaten kontinuierlich erfasst und dem Entwicklungssystem zur Verfügung gestellt werden. Die Entwicklung profitabler Handelssysteme wird unterstützt, indem Vorverarbeitungen der Kursdaten, die bei Wertpapierhändlern verbreitet sind, dem System zur Verfügung gestellt werden. Zur visuellen Überprüfung sollen die Kursdaten, die Vorverarbeitungen sowie die Transaktionen der Handelssysteme grafisch dargestellt werden. Überoptimierung bei der Entwicklung der Handelssysteme soll verhindert werden, indem die vorhandene Kurshistorie in Trainings, Validierung und Testzeitraum unterteilt wird. Um ein Handelssystem für den Testzeitraum zu erhalten, werden die besten Handelssysteme des Trainingszeitraums auf den Validierungszeitraum angewandt. Das beste Handelssystem während der Validierung wird für den Handel im Testzeitraum ausgewählt. Der Entwicklungsprozess soll reproduzierbar und durch Log-Dateien der Zwischenergebnisse transparent sein. Handelssysteme zu großer Komplexität erwecken bei Anwendern Mißtrauen, da sich die Entschei-dungen des Systems schwer nachvollziehen lassen. Auch wenn sich mit kom-plexeren Handelssystemen eine höhere Rendite erzielen ließe, ist eine gewisse

1.2. ZIEL UND AUFBAU

3

Nachvollziehbarkeit der Handelssysteme erstrebenswert. Zusätzlich zur Begrenzung der Größe der Handelssysteme wird die StandardGP mittels sog. Knotengewichte erweitert. Dadurch wird versucht, einerseits die Makromutation durch den CrossoverOperator zu verringern und andererseits die In-terpretierbarkeit der generierten Handelssysteme zu vereinfachen (vgl. Kapi-tel 3.3.1 auf Seite 43).

Aufbau der Arbeit Zunächst werden in Kapitel 2.1 auf Seite 5 die Grundlagen und der Stand der Technik der Genetischen Programmierung und der Künstlichen Neutronalen Netze dargestellt. Aufbau und Arbeitsweise von

KNN wird betrachtet, da dieser Ansatz im Kontext der Entwicklung von Han-

delssystemen stark verbreitet ist. Im Anschluss daran werden ab Kapitel 2.3 auf Seite 20 die Grundlagen von technischen Handelssystemen dargestellt. Es wird einerseits die Technische Analyse als Instrument zum Finden von günstigen Handelszeitpunkten dargestellt, andererseits ein Ansatz zur Bestimmung der optimalen Positionsgröße für einen Handel aufgezeigt.

Über beide vorgestellte Ansätze des maschinellen Lernens sind im Anwendungsgebiet von verschiedenen Autoren Erfolge berichtet worden. Einige dieser erfolgreichen Anwendungen werden in Kapitel 2.3.7 auf Seite 35 beschrieben.

Ab Kapitel 3 auf Seite 39 wird der Entwurf eines Systems beschrieben, das mittels GP Handelssysteme generiert, optimiert und mit historischen Kursdaten testet. Nach einem Überblick über das System werden die Anforderungen präzisiert dargestellt und ein Konzept für die Software entwickelt. Die Eigenschaften des für die Genetische Programmierung zuständigen Evolutionären Algorithmus werden definiert. Die Implementierungsdetails der Komponenten der entwickelten Software sind ab Kapitel 4 auf Seite 49 dargestellt. Die Resultate der Experimente mit dem System sind ab Kapitel 5 auf Seite 57 aufgeführt.

Anschließend findet eine Diskussion und Bewertung der Ergebnisse sowie ein Ausblick auf mögliche zukünftige Weiterentwicklungen des Systems in Kapitel 6 auf Seite 77 statt. Die Arbeit schließt mit einer Zusammenfassung in Kapitel 7 auf Seite 81.

KAPITEL 1. EINFÜHRUNG

4

Kapitel 2

Grundlagen und Stand der

Technik

In diesem Kapitel werden die Grundlagen Evolutionärer Algorithmen und Künstlicher Neuronaler Netze dargestellt und auf den aktuellen Stand der Technik eingegangen. Anschließend werden die relevanten Grundlagen des Anwendungsgebietes, der technischen Handelssysteme, besprochen.

2.1 Genetische Programmierung

Bei der Genetischen Programmierung (GP) handelt es sich um einen Algorithmus aus der Familie der Evolutionären Algorithmen. In der Natur hat sich die Evolution als sehr erfolgreiches System zur Weiterentwicklung und Optimierung aller Lebewesen erwiesen. Evolutionäre Algorithmen bilden mittels einfacher Modelle die wesentlichen erfolgreichen Merkmale des natürlichen evolutionären Prozesses nach. Sie ermöglichen dadurch, auch bei Problemen mit großem Suchraum mit relativ geringem Aufwand gute Lösungen zu finden. Datenstrukturen und Algorithmen werden durch die Evolutionären Algorithmen erzeugt und optimiert, um gegebene Probleme zu lösen. Diese Ein-führung in die GP orientiert sich an Banzhaf et al. (BNKF98, Kapitel 1-8) sowie Koza, der in (Koz92) GP erstmalig beschrieben hat.

Im Folgenden wird kurz dargestellt, wie ein Programm in der GP aufgebaut ist und wie die Evolution funktioniert. Anschließend wird auf bestehende Probleme des Verfahrens sowie deren Lösungsansätze eingegangen.

2.1.1 Aufbau eines Programms

Die Individuen, die während der GP evolutionär entwickelt werden, sind Programme. Diese Programme sind aus Funktionen und Terminalen aufgebaut (vgl. (BNKF98, S. 109-118)).

Die Wahl der verwendeten Funktionen innerhalb eines genetischen Programms hängt vom jeweiligen Anwendungsgebiet ab. Eine wesentliche An-forderung an die Auswahl der Funktionen, die dem genetischen Programm

5

KAPITEL 2. GRUNDLAGEN UND STAND DER TECHNIK

6

zur Verfügung gestellt werden, ist, dass sich aus ihnen eine Lösung für das Anwendungsproblem zusammensetzen lässt. Um den Suchraum nicht unnötig zu vergrößern, sollten jedoch nicht zu viele Funktionen zur Verfügung gestellt werden. Wie auch Banzhaf et al. in (BNKF98, S. 111f) bemerken, ist es nicht sinnvoll, gleich zu Beginn einer Anwendung exakt auf das gegebene Problem zugeschnittene Funktionen zu entwickeln. Da GP sehr kreativ in der Kombination von Funktionen ist, kann es bereits ausreichend sein, einfache Funktionen wie die Boolschen und Arithmetischen Funktionen zur Verfügung zu stellen, um erstaunliche Resultate zu erzielen.

Die Argumente der verwendeten Funktionen sind die Terminale. Sie bestehen zum einen aus den Eingabedaten, mit deren Hilfe das System trainiert, zum anderen aus Konstanten, die im Laufe der Evolution verändert werden. Diese Konstanten nennt man „ephemeral random constants“ (ERC) (vgl. (Koz92, S. 242f)).

Die Abgeschlossenenheit der Funktionen bezüglich der Terminale ist wesentliche Voraussetzung für das fehlerfreie Ablaufen der erzeugten Programme. Die verwendeten Funktionen müssen so entworfen sein, dass sie mit allen möglichen Eingabewerten zurechtkommen, z.B wird häufig die Division angepasst, damit das Programm nicht bei Divisionen durch Null beendet wird. Damit festgelegt ist, in welcher Reihenfolge die Funktionen eines Programms ausgewertet werden, werden die Funktionen und Terminale eines Programms in einer entsprechenden Datenstruktur gespeichert. Am häufigsten werden hierzu Bäume verwendet. Aber auch lineare Strukturen sowie allgemeine Graphen werden als Organisationsform verwendet.

Im Fall von Bäumen ist die übliche Reihenfolge der Evaluation von links nach rechts: Es wird der am weitesten links im Baum stehende Knoten ausgeführt, für den alle Eingaben zur Verfügung stehen.

Der prominenteste Vertreter einer linearen Strukturierung der Funktionen und Terminale ist die Simulation einer Registermaschine. Sie verfügt über mehrere Register, einen linearen Speicher für Zuweisungen von Terminalen an die Register sowie Funktionen, welche die Register für Ein/Ausgabe verwenden. Eine relativ neue Variante der Strukturierung sind gerichtete Graphen, die Zy-klen enthalten dürfen (vgl. (BNKF98, S. 116f)). Interessant an dieser Struktur ist, dass sich Schleifen und Rekursion im Laufe der Evolution ergeben und nicht erst durch spezielle Funktionen zur Verfügung gestellt werden müssen. Problematisch könnten überflüssige Zyklen werden, die den Programmablauf unnötig verlängern.

2.1.2 Initialisierung der GP Population

Da der Baum als Datenstruktur für die Individuen am weitesten verbreitet ist und auch für das Anwendungsbeispiel verwendet wird, wird im Folgenden nur diese Datenstruktur berücksichtigt.

Die von Koza in (Koz92, S. 9194) eingeführten Methoden zur Initialisierung der einzelnen Individuen der Population werden als „Full“ bzw. „Growth“ be-zeichnet. Für die gesamte Population ist die maximale Größe eines einzelnen Programms durch die maximale Tiefe der einzelnen Bäume festgelegt. Im Falle

2.1. GENETISCHE PROGRAMMIERUNG

7

der „Full“ Methode zur Initialisierung eines Individuums wird ein Baum maximaler Tiefe angelegt, bei dem alle Knoten zufällig aus der Menge der Funktionen gewählt werden bis auf die Knoten maximaler Tiefe, die zufällig aus der Menge der Terminale gewählt werden. Bei der Methode „Growth“ wird der Baum von der Wurzel her aufgebaut, wobei für jeden Knoten zufällig ein Element aus Funktion bzw. Terminal ausgewählt wird. Wird ein Terminal gewählt, ist der Aufbau für diesen Ast beendet und es wird beim letzten Knoten des Astes fortgefahren, der kein Terminal ist. Für die Knoten der maximalen Tiefe des Baumes wird die zufällige Auswahl auf die Menge der Terminale eingeschränkt.

Um eine möglichst hohe Vielfalt innerhalb der Population zu erreichen, werden die beiden beschriebenen Aufbauverfahren häufig kombiniert ange-wandt. Diese Methode heißt „Ramped Half-and-Half“. Bei einer gegebenen maximalen Tiefe von N wird die Population zu gleichen Teilen in Bäume mit maximalen Tiefen von 2,3...N aufgeteilt. Jede dieser Gruppen wird zur Hälfte nach der „Growth“ und zur Hälfte nach der „Full“ Methode initialisiert.

2.1.3 Die Genetischen Operatoren

Die Genetischen Operatoren sind die Werkzeuge, die dem Evolutionären Algorithmus zur Verfügung stehen, um die Fitness der Population im Laufe der Evolution zu verbessern. Die am häufigsten verwendeten Operatoren sind Crossover, Mutation und Reproduktion. Der einfachste Operator ist die Reproduktion, der abhängig von der Fitness ein Individuum selektiert und eine identische Kopie in die nächste Generation überträgt. Der Crossover Operator kombiniert das genetische Material von zwei Individuen miteinander, indem er Teilbäume gegeneinander austauscht und so zwei neue Individuen erzeugt. Häufig geschieht dies so, dass Funktionen mit einer höheren Wahrscheinlichkeit ausgewählt werden als Terminale. Auch die Erzeugung nur eines Nach-kommen ist gebräuchlich (vgl. (BNKF98, S. 241)).

Mutation wird auf ein einzelnes Individuum angewandt. Häufig geschieht dies im Anschluss an den Crossover Operator. Mit einer geringen Wahrscheinlichkeit wird ein zufälliger Knoten aus dem Individuum ausgesucht und der Unterbaum ab diesem Knoten durch neue, zufällige Knoten ersetzt, wie es bei der Initialisierung geschehen ist. Daneben sind auch eine Reihe anderer Genetischer Operatoren verbreitet. Banzhaf et al. etwa führen in (BNKF98, S. 242) folgende Operatoren für Mutation auf:

• Point Mutation: Ein einzelner Knoten wird gegen einen zufälligen Knoten der gleichen Klasse ausgetauscht.

• Permutation: Die Positionen von Argumenten einer Funktion werden vertauscht.

• Hoist: Ein neues Individuum wird aus einem Unterbaum erzeugt.

• Expansion Mutation: Ein Terminal wird gegen zufälligen Unterbaum ausgetauscht.

KAPITEL 2. GRUNDLAGEN UND STAND DER TECHNIK

8

• Collapse Subtree Mutation: Ein Unterbaum wird gegen ein zufälliges Terminal ausgetauscht.

• Subtree Mutation: Ein Unterbaum wird gegen einen zufälligen Unterbaum ausgetauscht.

• Gene Duplication: Ein Unterbaum wird durch ein zufälliges Terminal ersetzt.

Als Alternativen für den Standard Crossover Operator führt Banzhaf an gleicher Stelle folgende Operatoren auf:

• Subtree Exchange Crossover: Austausch von Unterbäumen zwischen Individuen

• Self Crossover: Austausch von Unterbäumen innerhalb eines Individuums

• Module Crossover: Austausch zweier Module zwischen Individuen

• ContextPreserving Crossover: Austausch von Unterbäumen zweier Individuen, wenn deren Koordinaten exakt übereinstimmen oder minde-stens ähnlich sind.

2.1.4 Fitness Funktion

In Anlehnung an die in der natürlichen Evolution stattfindende Auslese findet in der GP ein Selektionsprozeß anhand eines Fitnesswertes statt, der jeweils einem Individuum der Population zugeordnet ist. Der Fitnesswert eines Individuums wird durch die Evaluation des Individuums durch die Fitnessfunktion ermittelt. Hierzu wird meist das genetische Programm des Individuums mit Eingaben aus einem Trainingsdatensatz ausgeführt und aufgrund der Ausgabe des Programms ein Fitnesswert bestimmt. Um ähnlich der natürlichen Evolution einen Selektionsdruck hin zu besseren Lösungen des gegebenen Problems aufzubauen, wird mittels eines Selektionsverfahrens basierend auf der Fitness der Individuen bestimmt, welche Individuen sich in die nächste Generation fortpflanzen. Eine wesentliche Anforderung sowohl an das zu lösende Problem als auch die Gestaltung der Fitnessfunktion ist die Stetigkeit der Fitnessfunktion (vgl. (BNKF98, S. 127)). Dies bedeutet, dass die Verbesserung eines Individuums bezogen auf das Problem einer entsprechenden Verbesserung des Fitnesswertes gegenüberstehen sollte. Stetigkeit der Fitnessfunktion ist wesentliche Voraussetzung dafür, dass die Individuen iterativ verbessert werden können. Eine häufig verwendete Fitnessfunktion ist die FehlerFitness-Funktion. Sie kann angewandt werden, wenn ein zu erreichen-des Optimum bekannt ist und der noch bestehende Fehler der erreichten Lö-sung zu diesem Optimum bestimmt werden kann. Ein Beispiel hierfür ist etwa die symbolische Regression. Hierbei wird z.B. ein Polynom vorgegeben und das GP System soll diese Funktion so genau wie möglich durch Kombination der zur Verfügung gestellten Funktionen approximieren (vgl. (Koz92, Kapitel 10)). Mit kleiner werdender Abweichung vom vorgegebenen Polynom, steigt der Fitnesswert des Individuums.

2.1. GENETISCHE PROGRAMMIERUNG

9

2.1.5 Selektion

Die Selektion bestimmt, welche Individuen einer Population verbleiben bzw. sich fortpflanzen und so ihr Erbmaterial erhalten oder sogar verbreiten können. Je nach Art und Parametereinstellung des SelektionsAlgorithmus kann der Selektionsdruck gesteuert werden. Ein hoher Selektionsdruck verteilt die Eigenschaften der überlegenen Individuen schnell innerhalb der Population. Dies kann dazu führen, dass der Evolutionäre Algorithmus nur eine suboptimale Lösung findet, da die vorhandene Lösung die Population dominiert und sich keine besseren Eigenschaften mehr durchsetzen können. Ein zu geringer Selektionsdruck zieht den Ablauf des Algorithmus unnötig in die Länge. Da-bei kann es passieren, dass gute Eigenschaften sich nicht ausreichend schnell in der Population verbreiten können und durch die Genetischen Operatoren wieder zerstört werden.

Fitnessproportionale Selektion Fitnessproportionale Selektion war lange Zeit die am meisten verwendete Methode zur Selektion im Bereich Genetischer Algorithmen, nachdem sie von Holland eingeführt worden war (vgl. (Hol75)). Bei dieser Methode wird ein Individuum der Population per Zufall selektiert. Die Wahrscheinlichkeit ist bestimmt durch das Verhältnis der Fitness des Individuums zur Summe der Fitness aller Individuen. Blickle et al. kommen aus folgenden Gründen zu dem Schluss, dass fitnessproportionale Selektion untauglich ist (vgl. (BT95, S.40-42)):

• Die Reproduktionsrate ist proportional zur Fitness eines Individuums. Wenn die Fitnesswerte nahe beieinander liegen, findet daher quasi nur eine zufällige Selektion statt.

• Es herrscht keine TranslationsInvarianz: Während die Fitnesswerte eins bzw. zehn noch einen großen Unterschied in der Selektionswahrschein-lichkeit bedeuten, verschwindet dieser Unterschied größtenteils, wenn man beide Fitnesswerte um einen relativ großen Wert erhöht.

• Trotz hoher Varianz zu Anfang der Optimierung ist die Selektionsintensität zu gering, manchmal sogar negativ, was zu einer Verschlechterung der durchschnittlichen Fitness der Population führen kann.

Truncation Selection Truncation Selection, auch als (µ, σ)-Selektion bekannt (vgl. (Sch95, 158f)), verwendet µ Individuen als Eltern, um σ neue Individuen zu generieren, von denen µ Individuen als Eltern der nächsten Generation dienen. Die absoluten Fitnesswerte spielen bei dieser Selektion keine Rolle, sondern die Reihenfolge der Individuen aufgrund der Fitnesswerte.

Selektion nach Rang Selektion nach Rang basiert ebenfalls auf der Reihenfolge der Individuen, die durch die Fitnesswerte definiert ist. Man unterscheidet lineares und exponentielles Ranking. Beim linearen Ranking hängt die Wahrscheinlichkeit, dass ein Individuum selektiert wird, linear von seinem

KAPITEL 2. GRUNDLAGEN UND STAND DER TECHNIK

10

Rang innerhalb der Population ab. Beim exponentiellen Ranking steigt die Wahrscheinlichkeit für ein Individuum, selektiert zu werden, mit seinem Rang exponentiell an.

Turnier-Selektion Bei der TurnierSelektion tritt eine zufällig aus der Popu-lation gewählte Gruppe von Individuen gegeneinander an. Die Größe dieser Gruppe heißt die Turnier-Größe. Das Individuum der gewählten Gruppe mit dem größten Fitnesswert wird selektiert und zur Reproduktion verwendet. Der Nachkomme ersetzt die unterlegenen Individuen der Turnier-Gruppe in der Population. Die Turnier-Größe bestimmt den Selektionsdruck, wobei eine Turnier-Größe von zwei einem geringen Selektionsdruck entspricht. In der GP hat sich eine Turnier-Größe von sieben als Standard etabliert.

2.1.6 Ablauf des GP Algorithmus

Nachdem die einzelnen Komponenten des Evolutionären Algorithmus vorgestellt worden sind, folgt eine Darstellung des Ablaufes des Algorithmus. Man unterscheidet die Generationale GP und die SteadyState GP. In der Generationalen GP bildet eine Population zu einem Zeitpunkt eine Generation, die durch die Genetischen Operatoren in die Population der nächsten Genera-tion überführt wird:

1. Initialisierung der Population

2. Evaluation der Individuen der Population und Zuweisung eines Fit-

nesswertes zu jedem Individuum

3. Anwendung von Selektion und Genetischer Operatoren bis die Popula-

tion der nächsten Generation vollständig ist

4. Falls das Abbruch-Kriterium des Algorithmus noch nicht erfüllt ist, fort-

fahren mit Punkt zwei Im SteadyState Algorithmus werden keine Generationen unterschieden. Aus einer zufällig ausgewählten Gruppe von Individuen der Population werden mittels Turnier-Selektion die besten ermittelt. Auf diese werden die Geneti-schen Operatoren angewandt und mit den so entstehenden Nachfahren die Verlierer des Turniers ersetzt:

1. Initialisierung der Population

2. Zufällige Auswahl einer Gruppe von Individuen der Population für die

Turnier-Selektion

3. Evaluation der Fitness der ausgewählten Individuen

4. Anwendung der Genetischen Operatoren auf die Gewinner des Turniers

5. Ersetzen der Verlierer des Turniers mit den erzeugten Nachkommen der

Gewinner

2.1. GENETISCHE PROGRAMMIERUNG

11

6. Falls das Abbruchkriterium des Algorithmus noch nicht erfüllt ist, fort-

fahren mit Punkt zwei

Bei einem Vergleich von Generationaler GP und Steady-State GP anhand eines Sortierproblems kommt Kinnear zu dem Ergebnis, dass Steady-State GP bessere Resultate erzielt (vgl. (Kin93a, S. 6f)).

2.1.7 Crossover, Building Blocks und Schemata

Crossover in seinen unterschiedlichen Ausprägungen ist der hauptsächlich angewandte Genetische Operator in der GP. Die Wahrscheinlichkeit für die Wahl des Crossover Operators für die Erzeugung der Nachkommen eines Individuums liegt gewöhnlich im Bereich von 90% (vgl. (Koz92, S. 114116)). Die starke Verwendung von Crossover in der GP wird gestützt durch die natürliche Evolution im Rahmen der biologischen sexuellen Reproduktion. Entsprechend findet Mutation während der biologischen Reproduktion zwar statt, jedoch nur in geringem Maße. Dies wird in der GP durch eine kleine Wahr-scheinlichkeit für Mutation reflektiert (vgl. (BNKF98, Kapitel 2).

Der Crossover Operator wird als Grund angesehen, warum GP effektiver arbeitet als andere Verfahren, die auf rein zufälligen Veränderungen der Lösungskandidaten basieren. Wie Koza in (Koz92, S. 116119) ausführt, enthält die Population eines GP „Building Blocks“. Gute Building Blocks verbessern die Fitness der Individuen, die sie enthalten. Daher ist es wahrscheinlicher, dass diese Individuen für die Fortpflanzung selektiert werden. So gelingt es den guten Building Blocks, sich in der Population auszubreiten. Mit dieser Argumentation schließt sich Koza der Argumentation von Holland an, der die Building Block Hypothese erstmalig für Genetische Algorithmen formulier-te (vgl. (Hol75)). Aufgrund dieses Ausbreitens von guten Building Blocks ist es der GP möglich, schneller gute Problemlösungen zu kreieren als dies rein mutations-basierten Verfahren möglich ist. Koza zeigt in (Koz92, Kapitel 9), dass GP bis auf sehr einfache Probleme der zufälligen Suche überlegen ist. Goldberg versucht das Funktionieren Genetischer Algorithmen mit der Buil-ding Block Hypothese zu erklären. Demnach kombiniert der Crossover Ope-rator kleine gute Building Blocks zu größeren und besseren Building Blocks, um daraus schließlich nahezu optimale Individuen zu generieren (vgl. (Gol89, S. 41)). Die Building Block Hypothese wird z.B. von Grefenstette in (Gre93, S. 3f) als irreführend kritisiert, da sie das tatsächliche Geschehen während der evolutionären Entwicklung nur unzureichend beschreibe und leicht falsche Schlüsse gezogen werden könnten.

Die Begründung, warum GP besser funktioniert als eine rein zufällige Suche, wird von vielen Autoren mittels Schemata gegeben. Schemata sind Templates, die eine ganze Gruppe von ähnlichen CodeAbschnitten repräsentieren. Ein Schema-Theorem beschreibt Annahmen darüber, wie diese Schemata sich von Generation zu Generation weiterentwickeln, während Crossover, Mutati-on und Selektion auf sie einwirken. Das wohl bekannteste Schema-Theorem hat Holland für Genetische Algorithmen formuliert (vgl. (Hol75, S. 66-88)).

KAPITEL 2. GRUNDLAGEN UND STAND DER TECHNIK

12

Den ersten Versuch, dieses SchemaTheorem auf GP zu übertragen, unternimmt Koza in (Koz92, S. 116119). Wie Langdon in (LP02, S. 27) ausführt, wurde das SchemaTheorem von vielen Autoren inzwischen kritisiert und von einigen sogar als völlig nutzlos eingestuft. Langdon geht jedoch davon aus, dass die Überinterpretation des SchemaTheorems das Problem darstellt, nicht das Theorem an sich. Es gibt eine Reihe von Ansätzen, das SchemaTheorem auf GP zu übertragen. Eine Übersicht und eingehende Diskussion der verschiedenen Ansätze findet sich etwa in (LP02, Kapitel 3-6). Langdon führt in (LP02, Kapitel 6) das „macroscopic exact schema theorem“ ein und zeigt, dass Standard-Crossover Schemata höherer Ordnung zusammengesetzt wer-den aus Schemata niedriger Ordnung. Er räumt jedoch ein, dass der Begriff „Building Block“ für diese Schemata niedriger Ordnung insofern missver-ständlich für GP ist, als er suggeriert, daß Building Blocks Schritt für Schritt zu besseren und größeren Blöcken zusammengesetzt werden. Wie Langdon ausführt, legt sein Schema-Theorem nahe, dass der Auswahl-Prozess der ver-wendeten Schemata nicht reproduzierbar ist und zufällig stattfindet. Des wei-teren werden nicht notwendigerweise nur Schemata ausgewählt, die beson-ders kurz oder überdurchschittlich fit sind.

2.1.8 Ansätze gegen Makromutation

Ein wesentliches Problem des Crossover Operators im Vergleich zu seinem Vorbild in der biologischen Reproduktion ist, dass er zwar einerseits gute Kombinationen schafft, andererseits aber als Makromutation arbeitet und erstellte Building Blocks wieder zerstört. In der biologischen Reproduktion wird viel Energie darauf verwendet, einmal erstellte gute Building Blocks vor den schädlichen Einflüssen des Crossover zu schützen. Biologisches Crossover ist homolog, d.h. das Crossover findet fast ausschließlich auf Gen-Ebene statt. Es kommt kaum vor, das zwei Gene mit vollkommen unterschiedlichem Zweck gegeneinander ausgetauscht werden (vgl. (BNKF98, S. 156f).

Es gibt inzwischen eine Reihe von Ansätzen, zu versuchen, Schutzmechanismen vor der Makromutation in der GP einzuführen. Ein natürlich auftretendes Phänomen ist die Anlagerung von auswirkungsfreiem Code an die Building Blocks im Laufe der Simulation. Hierdurch wird die Wahrscheinlichkeit geringer, dass die Building Blocks zerstört werden. Diesen Vorgang kann man auch beim natürlichen Vorbild beobachten. Über 90% des Genoms höherer Lebewesen bestehen aus sog. Introns, die weder Gene kodieren noch Kontrollsequenzen enthalten. Während der EA läuft, kann man beobachten, dass die Menge an auswirkungsfreiem Code exponentiell zunimmt (BNKF98, S. 191193). Dieses Phänomen wird als „Bloat“ bezeichnet. Neben der Schutzfunktion durch die Introns hat Bloat jedoch das Problem, dass dadurch die Entwicklung ge-hemmt wird und die Ausführungszeit des erzeugten Programms unnötig in die Länge gezogen wird.

Banzhaf identifiziert die Makromutation des Crossover Operators als großen Unterschied zu dem natürlich vorkommenden Crossover bei der biologischen sexuellen Reproduktion. In der Natur sind beinahe alle Crossover erfolgreich, wogegen in der GP ca. 75% nach biologischen Maßstäben als „tödlich“ einzu-

2.1. GENETISCHE PROGRAMMIERUNG

13

stufen wären (vgl. (BNKF98, S. 157)). Die Eindämmung der Makromutation des Crossover Operators in der GP ist daher ein wichtiger Forschungsbereich. Im Folgenden werden einige der Ansätze angesprochen, die zur Verbesserung des Crossover Operators bzw. zur Vermeidung seiner negativen Auswirkungen untersucht wurden.

Brood Recombination Tackett schlägt in (Tac94, Kapitel 5) mit der „brood recombination“ eine Methode vor, die den Crossover Operator zwar nicht verbessert, aber negative Auswirkungen eindämmt. In der Natur haben einige Spezies wesentlich mehr Nachkommen als zum Überleben der Art notwendig wären. Einige Nachkommen sterben bald nach der Geburt aufgrund verschiedener Mechanismen, etwa im Kampf miteinander um Nahrung. Dadurch wird sichergestellt, dass die Eltern die für die Aufzucht notwendige Energie nur in die aussichtsreichsten Nachkommen investieren.

Tackett überträgt diesen Ansatz auf GP. Statt nur ein oder zwei Nachkommen zu erzeugen, wird eine ganze Reihe von Nachkommen generiert. Für diese Gruppe, genannt Brut, werden die Fitnesswerte berechnet und die besten ein oder zwei Nachkommen ausgewählt. Der Rest der Brut wird verworfen. Um den erhöhten Rechenanforderungen dieser Methode entgegenzuwirken, schlägt Tackett vor, die Fitness Berechnung für die Brut nicht mit den gesamten Trainingsdaten vorzunehmen, sondern nur mit einem kleinen Teil. Er begründet die Legitimität dieses Vorgehens damit, dass es das Ziel ist, die untauglichen Individuen auszusortieren und nicht das tatsächlich beste Individuum der Brut zu finden (vgl. (Tac94, S. 87)). Tackett berichtet, dass die erwartete Verbesserung gegenüber GP ohne BrutSelektion bei den durchgeführten Ver-suchen tatsächlich eingetreten ist.

Neben Ansätzen zur Umgehung der schädlichen Auswirkungen von Crossover gibt es zahlreiche Versuche, den Crossover Operator „intelligenter“ zu machen.

Strong Context-Preserving Crossover D’haeseleer entwickelt in (D’h94) den „strong contextpreserving crossover“ (SCPC) Operator, der Crossover nur zwischen Knoten zulässt, die an genau derselben Position zweier Eltern sind. D’haeseleer berichtet, durch Mischung von normalem Crossover und SCPC Verbesserungen erzielt zu haben. Die alleinige Verwendung von SCPC wür-de Probleme erzeugen, da dadurch die Vielfältigkeit innerhalb der Population leiden würde. Einen gewissen Grad an Makromutation hält D’haeseleer für nötig (vgl. (D’h94, S. 2)).

Explicit Multiple Gene Systems Altenberg stellt in (Alt95) ein System vor, in dem FitnessKomponenten von einer Teilmenge vorhandener Gene beeinflusst werden. Während der Evolution wird periodisch versucht, ein neues Gen hinzuzufügen. Dieses wird jedoch nur integriert, wenn dadurch die Fitness steigt. Während der Evolution der Population werden per Crossover Gene zwischen den Individuen ausgetauscht. Die von Altenberg vorgeschlagene „Konstruie-rende Selektion“ (vgl. (Alt95, S. 39)) mit anschließendem Austausch von Ge-

KAPITEL 2. GRUNDLAGEN UND STAND DER TECHNIK

14

nen durch Crossover zeigt eine starke Ähnlichkeit zum homologen biologischen Crossover. Statt zuzulassen, dass durch die Makromutation des Crossover ein großer Teil der guten Building Blocks zerstört wird, wird in diesem Modell das Crossover auf Gene bestehend aus einem oder mehreren Building Blocks beschränkt. Da keine Gefahr besteht, dass Building Blocks zerstört werden, ist Bloat vermutlich kein Problem bei diesem Ansatz.

Explicitly Defined Introns Zu interessanten Maßnahmen gegen die Makromutation durch den Crossover Operator gehört unter anderem der Ansatz „explicitly defined introns“ (EDI). Zwischen je zwei Knoten eines GP Baumes wird ein ganzzahliger Wert gespeichert, der sich auf die Berechnung des Baumes nicht auswirkt. Der Crossover Operator wird verändert, so dass die Wahrscheinlichkeit eines CrossoverEreignisses zwischen zwei Knoten von dem Wert des EDI zwischen ihnen abhängt. Im Laufe der Evolution werden die EDIs genauso wie der Rest des Individuums evolutionär entwickelt. Hierdurch bilden sich Building Blocks, die durch die sie verbindenden EDIs vor dem Crossover geschützt werden. Nordin et al. führen in (NFB95, S. 16) eine Reihe von Tests durch, die den Schluss nahelegen, dass EDIs eine wichtige Rolle im Auffinden von Individuen hoher Fitness spielen. Was Fitness, Generalisation und Rechenzeit angehen, haben Individuen mit EDIs besser abge-schnitten als solche Individuen in Tests ohne EDIs.

GP 1-Point Crossover Operator Poli und Langdon schlagen in (PL98, S. 13-

19) einen 1Punkt Crossover Operator vor, der für die Wahl eines geeigneten Crossover Punktes strukturelle Ähnlichkeiten in den Elternbäumen berück-sichtigt. Ihre Experimente weisen darauf hin, dass sich dadurch im Laufe der Evolution die zerstörerischen Einflüsse des Crossover abschwächen lassen.

2.1.9 Modularisierung

In vielen Programmiersprachen gibt es die Möglichkeit, Programmteile zusammenzufassen und diese Module an anderer Stelle zu verwenden. Modularisierung dient der Abstraktion, dem Aufteilen eines Problems in Unterprobleme und der Wiederverwendbarkeit des Programmcodes. Aber auch im Zusammenhang mit dem Problem der Makromutation durch den Crossover Operator ist Modularisierung interessant. Einige Ansätze verwenden spezielle Crossover Operatoren, welche die Module berücksichtigen und so der Makromutation verbeugen. Modularisierung wurde in der GP von verschiedenen Autoren untersucht. Eine Auswahl verschiedener Techniken wird im Folgenden dargestellt.

Encapsulation Die Idee der Encapsulation (Einkapselung) beschreibt Koza in (Koz92, S. 110112). Es handelt sich dabei um einen asexuellen Geneti-schen Operator, der einen Funktionsknoten eines Individuum auswählt und ihn durch einen Terminalknoten ersetzt, der den Unterbaum des ausgewählten

2.1. GENETISCHE PROGRAMMIERUNG

15

Funktionsknoten enthält. Das erzeugte Terminal kann nun auch in anderen Individuen angewandt werden. Der eingekapselte Unterbaum kann durch den Crossover Operator nicht mehr verbessert oder zerstört werden. Wenn der ersetzte Unterbaum einen nützlichen Code enthält, könnte dies von Vorteil sein.

Module Acquisition Angeline und Pollack schlagen eine „module acquisition“ genannte Technik vor (vgl. (AP92, S. 24)), um wiederverwendbare Modu-le zu erzeugen. In einem ausgewählten Individuum wird dazu ein Unterbaum bis zu einer festgelegten Tiefe als Modul definiert. Die Teile des Unterbaums unter dem Modul werden als Argumente des Moduls betrachtet. Neben der ausschließlichen Verwendung innerhalb des Individuums kann das Modul über eine Funktionsbibliothek der gesamten Population zur Verfügung gestellt werden. Solange mindestens ein Individuum ein Modul verwendet, verbleibt es in der Bibliothek, ansonsten wird es gelöscht.

Genau wie bei der Encapsulation wird bei der Module Acquisition ein einmal definiertes Modul nicht mehr weiter entwickelt und ist vor der Makromutation des Crossover geschützt.

Automatically Defined Functions Koza beschreibt „automatically defined functions“ (ADF) in (Koz92, S. 534ff) und sehr ausführlich in (Koz94, Kapitel 416). Um ADFs in der GP zu verwenden, werden die Programmbäume in zwei Teile aufgeteilt: einen Ast, der zur Berechnung der Fitness ausgewertet wird und einen Ast, der die Funktionsdefinitionen der ADFs enthält. Beide Äste nehmen an der Evolution teil. Der Crossover Operator muss dabei die spezifischen Besonderheiten der Äste und ihre Beziehung miteinander berücksichtigen. Die Definition einer ADF im Funktionsdefinitionsast des Programmbaumes besteht aus drei Teilen: Dem Funktionsnamen, einer Argumentenliste sowie einem Ast, der den Körper der Funktionsdefinition enthält. Der Funktionsname der ADF wird Teil der Funktionenmenge des Resulate erzeugenden Astes. Die in der Argumentliste definierten Variablen werden Teil der Menge der Terminale ihres ADF Funktionskörpers. Die Evolution findet aus-schließlich im Funktionskörper der ADF und in dem Resultate erzeugenden Ast statt. Nur dieser Ast sowie der Funktionskörper der ADFs werden per Zufall erzeugt. Bevor die Evolution beginnen kann, müssen die Anzahl und Namen der ADF sowie die Anzahl und Namen der Funktionsargumente für jedes ADF festgelegt werden.

λ Abstraktion Yu stellt in (Yu99a, Kapitel 6,7) einen Ansatz vor, λ Abstraktionen, basierend auf dem λ Kalkül, in der GP anzuwenden. Jede λ Abstraktion wird dabei innerhalb des GP Baums als unabhängiges Modul betrachtet und als eine Einheit während des evolutionären Prozesses geschützt. Diese Module entwickeln sich auf ähnliche Weise wie der restliche GP Baum. Crossover ist nur zwischen Modulen erlaubt, die gleiche Anzahl und Typ der Ein-und Ausgaben besitzen. Den Erfolg dieses Ansatzes dokumentiert Yu z.B. in (Yu99b). Ein Grund für seinen Erfolg könnte auf den Struktur und Funktion

KAPITEL 2. GRUNDLAGEN UND STAND DER TECHNIK

16

erhaltenden homologen Crossover im Zusammenhang mit der λ Abstraktion zurückzuführen sein.

2.1.10 Weitere Verbesserungsansätze

Weitere interessante Ansätze zur Erweiterung der Standard-GP sind u.a. die folgenden:

Schleifen und Rekursion Obwohl Schleifen und Rekursion in der manuellen Programmierung eine enorme Bedeutung haben, ist ihre Anwendung in der GP mit Schwierigkeiten verbunden. Lange Schleifen, insbesondere Endlosschleifen, können die Evolution eines Programmes zum Erliegen bringen. Eine mögliche Herangehensweise beschreibt Kinnear in (Kin93b, S. 5) im Rahmen der evolutionären Entwicklung eines Sortieralgorithmus: Die verwendete Schleife kann als Parameter nur Start und End-Index einer endlich großen Li-ste erhalten.

Strongly Typed Genetic Programming Die Erweiterung der traditionellen

GP zum stark typisierten GP (STGP) führt Typen für Terminale und Funktio-

nen in die Genetische Programmierung ein (Mon93, S. 7). Diese Erweiterung ist besonders sinnvoll, da sie den Suchraum des Evolutionären Algorithmus erheblich einschränkt. Funktionen werden bestimmten Ein und Ausgabety-pen zugeordnet und können nur noch mit Terminalen des passenden Typs kombiniert werden.

Cultural GP Die Cultural GP, die von Spector und Luke beschrieben wird (SL96), verwendet einen indizierten Speicher, auf den alle Individuen der Population über die Generationen hinweg Zugriff haben. Der Speicher wird am Anfang der evolutionären Entwicklung initialisiert und steht der Population anschließend als Datenspeicher und Kommunikations-Medium zwischen den Generationen zur Verfügung. Die Autoren kommen zu dem Resultat, dass durch den gemeinsam verwendeten Speicher der Berechnungsaufwand bei den betrachteten Problemen im Vergleich zur Standard-GP sinkt.

2.2 Künstliche Neuronale Netze

Im Kontext der Entscheidungsfindung für FinanzmarktTransaktionen werden Künstliche Neuronale Netze (KNN) verbreitet eingesetzt. Ihr Einsatz reicht von TrendprognoseSystemen, wie z.B. in (MK, S. 27) für den Gold-markt beschrieben, über Punktprognosesysteme, wie z.B. in (NM02, S. 501-511) für den Währungsmarkt vorgeschlagen, bis zur Entwicklung von auto-matischen Handelssystemen, wie etwa in (Ska01, S. 2-8) dargestellt. Wegen der weiten Verbreitung und der vielen erfolgreichen Anwendungen werden im Folgenden die Grundlagen von KNN kurz dargestellt.