Entwicklung von Handelssystemen mit der Genetischen Programmierung: Grundlagen und Fallbeispiel


Diplomarbeit, 2007

99 Seiten, Note: 1,7


Leseprobe

Inhaltsverzeichnis

1 Einführung
1.1 Motivation
1.2 Ziel und Aufbau

2 Grundlagen und Stand der Technik
2.1 Genetische Programmierung
2.1.1 Aufbau eines Programms
2.1.2 Initialisierung der GP Population
2.1.3 Die Genetischen Operatoren
2.1.4 Fitness Funktion
2.1.5 Selektion
2.1.6 Ablauf des GP Algorithmus
2.1.7 Crossover, Building Blocks und Schemata .
2.1.8 Ansätze gegen Makromutation
2.1.9 Modularisierung
2.1.10 Weitere Verbesserungsansätze
2.2 Künstliche Neuronale Netze
2.2.1 Bestandteile neuronaler Netze
2.2.2 Netztopologien
2.2.3 Lernmethoden
2.3 Handelssysteme
2.3.1 Tape Reader
2.3.2 Market Timing
2.3.3 Position Sizing
2.3.4 Vergleich von Handelssystemen
2.3.5 Fundamentale versus Technische Analyse . .
2.3.6 Der Währungsmarkt
2.3.7 Entwicklungsansätze für Handelssysteme in der Literatur

3 Entwurf
3.1 Überblick
3.2 Anforderungen an die Software
3.3 Konzeption der Software
3.3.1 Der Evolutionäre Algorithmus
3.3.2 Die Fitness-Funktion

4 Implementierung
4.1 Komponenten der entwickelten Software . .
4.2 Klassen des Kursdatenservers
4.3 Klassen des Evolutionären Algorithmus . .
4.4 Übersicht über das Framework ECJ
4.5 Probleme während der Experimente

5 Versuchsergebnisse
5.1 Resultate mit Knotengewichten
5.1.1 Resultate des Trainingszeitraums . .
5.1.2 Resultate des Validierungszeitraums .
5.1.3 Resultate des Testzeitraums
5.1.4 Resultate als Monatsrenditen
5.1.5 Erzeugte Handelsregeln
5.2 Resultate ohne Knotengewichte
5.2.1 Resultate des Trainingszeitraums . .
5.2.2 Resultate des Validierungszeitraums .
5.2.3 Resultate des Testzeitraums
5.2.4 Resultate als Monatsrenditen
5.2.5 Erzeugte Handelsregeln
5.3 Bestimmung und Anwendung von Optimal f

6 Diskussion und Bewertung
6.1 Ausblick

7 Zusammenfassung

Abbildungsverzeichnis

Literaturverzeichnis

Glossar

Kapitel 1 Einführung

1.1 Motivation

Die natürliche Evolution hat sich zur Erzeugung und Anpassung von Lebewe-sen an eine sich ändernde Umgebung als höchst erfolgreicher Mechanismus herausgestellt. Ohne bestimmte Anweisungen oder auch nur genaue Zielde-finitionen 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 au-tomatischen Entwicklung von Computer-Programmen zu verwenden, ist die Genetische Programmierung (GP) (vgl. (Koz92, Kapitel 1-6)). Mit ihr wird ver-sucht, Mechanismen der natürlichen Evolution nachzuahmen, um automa-tisch 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 Han-delssystemen 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 entscheiden-den Situationen beugen und gewissermaßen nach ihrem „Bauchgefühl“ han-deln. Evtl. unterscheidet dieser Anteil an intuitivem Handeln einen erfahre-nen profitablen Händler von einem unerfahrenen unprofitablen Händler, auch wenn beide meinen, nach dem gleichen Regelwerk zu arbeiten. Das Definieren eines Handelssystems durch einen Menschen ist mit Schwierigkeiten verbun-den, da er nicht alle Regeln eindeutig wiedergeben kann. Daher hat sich die Übertragung von Regelwerken zum Handeln auf einen Rechner als nicht er-folgreich 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 entwickeln-de 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 angepas-ste Handelssysteme erzeugt werden können. Um die Versorgung mit aktu-ellen Kursdaten sicherzustellen, müssen die relevanten Marktdaten kontinu-ierlich erfasst und dem Entwicklungssystem zur Verfügung gestellt werden. Die Entwicklung profitabler Handelssysteme wird unterstützt, indem Vorver-arbeitungen 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 Handelssys-teme 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 Handels-system 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 Testzeit-raum 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

Nachvollziehbarkeit der Handelssysteme erstrebenswert. Zusätzlich zur Be-grenzung der Größe der Handelssysteme wird die Standard-GP mittels sog. Knotengewichte erweitert. Dadurch wird versucht, einerseits die Makromu-tation durch den Crossover-Operator 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 Grund-lagen 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ünsti-gen 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 Anwen-dungsgebiet von verschiedenen Autoren Erfolge berichtet worden. Einige die-ser erfolgreichen Anwendungen werden in Kapitel 2.3.7 auf Seite 35 beschrie-ben.

Ab Kapitel 3 auf Seite 39 wird der Entwurf eines Systems beschrieben, das mittels GP Handelssysteme generiert, optimiert und mit historischen Kursda-ten testet. Nach einem Überblick über das System werden die Anforderungen präzisiert dargestellt und ein Konzept für die Software entwickelt. Die Eigen-schaften des für die Genetische Programmierung zuständigen Evolutionären Algorithmus werden definiert. Die Implementierungsdetails der Komponen-ten 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 auf-gefü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 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 Algorith-mus aus der Familie der Evolutionären Algorithmen. In der Natur hat sich die Evolution als sehr erfolgreiches System zur Weiterentwicklung und Opti-mierung 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 fin-den. Datenstrukturen und Algorithmen werden durch die Evolutionären Al-gorithmen 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 Pro-gramms hängt vom jeweiligen Anwendungsgebiet ab. Eine wesentliche An-forderung an die Auswahl der Funktionen, die dem genetischen Programm zur Verfügung gestellt werden, ist, dass sich aus ihnen eine Lösung für das An-wendungsproblem 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 Kombina-tion 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 wesent-liche 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 an-gepasst, 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 Gra-phen 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 Re-gister 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. 91-94) 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 der „Full“ Methode zur Initialisierung eines Individuums wird ein Baum ma-ximaler Tiefe angelegt, bei dem alle Knoten zufällig aus der Menge der Funk-tionen 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 ge-wä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 Al-gorithmus 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 Re-produktion, 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 Wahrscheinlich-keit 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.
- 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 In-dividuen
- Self Crossover: Austausch von Unterbäumen innerhalb eines Individu-ums
- Module Crossover: Austausch zweier Module zwischen Individuen
- Context-Preserving Crossover: Austausch von Unterbäumen zweier Individuen, wenn deren Koordinaten exakt übereinstimmen oder mindestens ähnlich sind.

2.1.4 Fitness Funktion

In Anlehnung an die in der natürlichen Evolution stattfindende Auslese fin-det in der GP ein Selektionsprozeß anhand eines Fitnesswertes statt, der je-weils einem Individuum der Population zugeordnet ist. Der Fitnesswert ei-nes Individuums wird durch die Evaluation des Individuums durch die Fit-nessfunktion ermittelt. Hierzu wird meist das genetische Programm des In-dividuums mit Eingaben aus einem Trainingsdatensatz ausgeführt und auf-grund 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 ba-sierend 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 entsprechen-den Verbesserung des Fitnesswertes gegenüberstehen sollte. Stetigkeit der Fit-nessfunktion ist wesentliche Voraussetzung dafür, dass die Individuen itera-tiv verbessert werden können. Eine häufig verwendete Fitnessfunktion ist die Fehler-Fitness-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.5 Selektion

Die Selektion bestimmt, welche Individuen einer Population verbleiben bzw. sich fortpflanzen und so ihr Erbmaterial erhalten oder sogar verbreiten kön-nen. Je nach Art und Parametereinstellung des Selektions-Algorithmus 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 subopti-male 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 Translations-Invarianz: Während die Fitnesswerte eins bzw. zehn noch einen großen Unterschied in der Selektionswahrscheinlichkeit 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 Individu-en 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 Reihen-folge der Individuen, die durch die Fitnesswerte definiert ist. Man unterschei-det lineares und exponentielles Ranking. Beim linearen Ranking hängt die Wahrscheinlichkeit, dass ein Individuum selektiert wird, linear von seinem 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 Turnier-Selektion 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 vorge-stellt worden sind, folgt eine Darstellung des Ablaufes des Algorithmus. Man unterscheidet die Generationale GP und die Steady-State GP. In der Ge-nerationalen 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 Steady-State 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 Genetischen 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
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 In-dividuums liegt gewöhnlich im Bereich von 90% (vgl. (Koz92, S. 114-116)). Die starke Verwendung von Crossover in der GP wird gestützt durch die natürli-che Evolution im Rahmen der biologischen sexuellen Reproduktion. Entspre-chend 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 ar-beitet als andere Verfahren, die auf rein zufälligen Veränderungen der Lö-sungskandidaten basieren. Wie Koza in (Koz92, S. 116-119) 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 Ar-gumentation 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 Templa-tes, die eine ganze Gruppe von ähnlichen Code-Abschnitten 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)).

Den ersten Versuch, dieses Schema-Theorem auf GP zu übertragen, unter-nimmt Koza in (Koz92, S. 116-119). Wie Langdon in (LP02, S. 27) ausführt, wurde das Schema-Theorem von vielen Autoren inzwischen kritisiert und von einigen sogar als völlig nutzlos eingestuft. Langdon geht jedoch davon aus, dass die Überinterpretation des Schema-Theorems das Problem darstellt, nicht das Theorem an sich. Es gibt eine Reihe von Ansätzen, das Schema-Theorem auf GP zu übertragen. Eine Übersicht und eingehende Diskussion der ver-schiedenen 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 er-stellte 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, Schutzmechanis-men 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 gerin-ger, dass die Building Blocks zerstört werden. Diesen Vorgang kann man auch beim natürlichen Vorbild beobachten. Über 90% des Genoms höherer Lebewe-sen bestehen aus sog. Introns, die weder Gene kodieren noch Kontrollsequen-zen enthalten. Während der EA läuft, kann man beobachten, dass die Menge an auswirkungsfreiem Code exponentiell zunimmt (BNKF98, S. 191-193). Die-ses 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- 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 Auswirkun-gen 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 Nachkom-men zu erzeugen, wird eine ganze Reihe von Nachkommen generiert. Für die-se 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ün-det die Legitimität dieses Vorgehens damit, dass es das Ziel ist, die untaug-lichen 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 Brut-Selektion bei den durchgeführten Ver-suchen tatsächlich eingetreten ist.

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

Strong Context-Preserving Crossover D’haeseleer entwickelt in (D’h94) den „strong context-preserving 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 Fitness-Komponentenvon einer Teilmenge vorhandener Gene beeinflusst werden. Während der Evolution wird periodisch versucht, ein neues Gen hin-zuzufü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- 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 Makro-mutation durch den Crossover Operator gehört unter anderem der Ansatz „explicitly defined introns“ (EDI). Zwischen je zwei Knoten eines GP Bau-mes 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 Crossover-Ereignisses 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. Hier-durch 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) ei-ne Reihe von Tests durch, die den Schluss nahelegen, dass EDIs eine wichtige Rolle im Auffinden von Individuen hoher Fitness spielen. Was Fitness, Gene-ralisation 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 1-Punkt 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 zu-sammenzufassen und diese Module an anderer Stelle zu verwenden. Modula-risierung dient der Abstraktion, dem Aufteilen eines Problems in Unterpro-bleme 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 speziel-le Crossover Operatoren, welche die Module berücksichtigen und so der Ma-kromutation verbeugen. Modularisierung wurde in der GP von verschiedenen Autoren untersucht. Eine Auswahl verschiedener Techniken wird im Folgen-den dargestellt.

Encapsulation Die Idee der Encapsulation (Einkapselung) beschreibt Koza in (Koz92, S. 110-112). 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 Funktionsknoten enthält. Das erzeugte Terminal kann nun auch in anderen In-dividuen angewandt werden. Der eingekapselte Unterbaum kann durch den Crossover Operator nicht mehr verbessert oder zerstört werden. Wenn der er-setzte 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. 2-4)), um wiederverwendbare Module 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, Kapi-tel 4-16). Um ADFs in der GP zu verwenden, werden die Programmbäume in zwei Teile aufgeteilt: einen Ast, der zur Berechnung der Fitness ausgewer-tet wird und einen Ast, der die Funktionsdefinitionen der ADFs enthält. Bei-de Äste nehmen an der Evolution teil. Der Crossover Operator muss dabei die spezifischen Besonderheiten der Äste und ihre Beziehung miteinander be-rücksichtigen. Die Definition einer ADF im Funktionsdefinitionsast des Pro-grammbaumes besteht aus drei Teilen: Dem Funktionsnamen, einer Argumen-tenliste sowie einem Ast, der den Körper der Funktionsdefinition enthält. Der Funktionsname der ADF wird Teil der Funktionenmenge des Resulate erzeu-genden 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, λ Abstrak-tionen, basierend auf dem λ Kalkül, in der GP anzuwenden. Jede λ Abstrak-tion 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. Cros-sover 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 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 manuel-len Programmierung eine enorme Bedeutung haben, ist ihre Anwendung in der GP mit Schwierigkeiten verbunden. Lange Schleifen, insbesondere End-losschleifen, können die Evolution eines Programmes zum Erliegen bringen. Eine mögliche Herangehensweise beschreibt Kinnear in (Kin93b, S. 5) im Rah-men 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 Po-pulation ü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 Finanzmarkt-Transaktionen wer-den Künstliche Neuronale Netze (KNN) verbreitet eingesetzt. Ihr Einsatz reicht von Trendprognose-Systemen, wie z.B. in (MK, S. 2-7) 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.

Künstliche Neuronale Netze (KNN) sind motiviert durch das natürliche Gehirn. Dabei steht nicht die biologisch korrekte Simulation eines Gehirns im Vordergrund, sondern die Simulation der mathematisch relevanten Elemente auf einer abstrakten Ebene.

Die wesentlichen Teile, die für eine Simulation eines KNN zu definieren sind, sind die Neuronen, die Verbindungen zwischen den Neuronen sowie die Me-thode, nach der das Netz trainiert wird. Diese Komponenten und häufig ver-wendete Netztopologien werden im Folgenden vorgestellt. Diese Ausführun-gen orientieren sich an der Schilderung von Zell (Zel94, Kapitel 5-8).

2.2.1 Bestandteile neuronaler Netze

Neuronen Die Neuronen sind charakterisiert durch:

- den Aktivierungszustand, der den aktuellen Grad der Aktivierung des Neurons angibt.
- den Schwellwert, der in die Aktivierungsfunktion zur Berechnung des nächsten Aktivierungszustandes eingeht. Er gibt in vielen Modellen die Schwelle an, ab der ein Neuron stark aktiviert ist. In biologischen Neu-ronen entspricht dies der Reizschwelle, die erreicht werden muss, damit das Neuron feuert.
- die Aktivierungsfunktion, die einen neuen Aktivierungszustand berechnet aus dem aktuellen Aktivierungszustand, der Eingabe durch andere Neuronen sowie dem Schwellwert des Neurons.
- die Ausgabefunktion, die aus der aktuellen Aktivierung des Neurons einen Ausgabewert ermittelt.

Verbindungsnetzwerk Infolge der Abstraktion vom natürlichen Vorbild werden im KNN nicht die im biologischen Gehirn zu findenden Axons, Den-driten und Synapsen simuliert, sondern die Verbindung zwischen jeweils zwei Neuronen auf einen Wert, das Verbindungsgewicht, reduziert. Insgesamt wird das Verbindungsnetzwerk zwischen den Neuronen häufig durch eine Matrix von Verbindungsgewichten dargestellt. Durch den Wert des Verbindungsge-wichtes zwischen zwei Neuronen wird die Stärke der Verbindung zwischen diesen charakterisiert. Das Gewicht kann je nach Modell in verschiedenen Wertebereichen liegen. Neben positiven Werten der Gewichte steht der Wert 0 für eine nicht vorhandene Verbindung und negative Werte für hemmende Verbindungen, welche die Aktivierung des folgenden Neurons abschwächen. Während der Simulation eines KNN werden die Ausgabewerte aller Neuro-nen, die mit dem betrachteten Neuron verbunden sind, diesem mit den Ver-bindungsgewichten gewichtet als Eingabe zur Verfügung gestellt. Innerhalb des betrachteten Neurons werden diese gewichteten Eingaben in der Aktivie-rungsfunktion verarbeitet. Meist werden während der Lernphase nur die Ver-bindungsgewichte verändert. Das erlernte Wissen ist auf das Netzwerk der Verbindungsgewichte verteilt und es ist nicht ohne weiteres möglich, einzelne Aussagen abzuleiten. Einige Autoren, wie z.B. Gruau in (Gru94, S. 8, S. 22), sehen vor, auch Komponenten des Neurons wie Aktivierungsfunktion oder Schwellwert während der Lernphase änderbar zu halten.

2.2.2 Netztopologien

KNN sind häufig schichtenweise organisiert, mit einer Eingabe-, einer Ausgabe- und mindestens einer Zwischenschicht. Über die Ein- und Aus-gabeschicht erfolgt die Kommunikation mit der Umgebung, während in den internen Schichten die Informationsverarbeitung stattfindet. Beim topologischen Aufbau von KNN wird im Wesentlichen zwischen Netzen mit und ohne Rückkopplung unterschieden. Unter Rückkopplung versteht man, dass es Neuronen gibt, für die ein Pfad durch das Netz existiert, der wieder zu diesem Neuron zurückführt.

2.2.3 Lernmethoden

Nachdem man sich für eine bestimmte Netztopologie für ein gegebenes Pro-blem entschieden hat, werden die Verbindungsgewichte typischerweise mit zufälligen Werten initialisiert. In dieser Ausgangssituation wird das KNN das gegebene Problem in den seltensten Fällen zufriedenstellend lösen. Daher ist es notwendig, die Verbindungsgewichte zu ändern, so dass eine bessere Lö-sung des Problems erreicht wird. Diesen Vorgang nennt man Training. Es gibt verschiedene Lernmethoden, um das Training durchzuführen. In der Literatur finden sich viele verschiedene Ansätze, um ein KNN für die gegebene Aufga-be zu trainieren. Die theoretisch veränderbaren Komponenten eines KNN sind die Verbindungsgewichte, Schwellwert, Aktivierungsfunktion, Ausgabefunk-tion sowie das Hinzufügen oder Löschen von Neuronen. Unter den umfas-sendsten Ansätzen, die alle diese möglichen Änderungen einschließen, findet sich z.B. der von Gruau in (Gru94, Kapitel 2-3). Dort kodieren genetisch ent-wickelte Programme den Aufbau und die Bestandteile des KNN. Wird ein sol-ches Programm auf ein Ausgangsneuron angewandt, entsteht daraus durch die Ausführung der Befehle des Programmes nach und nach das KNN. Zu den Befehlen gehören Anweisungen zur Teilung eines Neurons in zwei Neu-ronen, Löschen von Neuronen, das Erstellen und Löschen von Verbindungen zwischen Neuronen, das Ändern von Verbindungsgewichten und einige Ope-rationen mehr.

Arten des Lernens Viele Anwendungen beschränken sich darauf, ausschließlich die Verbindungsgewichte einer vorgegebenen Netztopologie zu trainieren. Hierbei unterscheidet man Arten des Lernens nach den zur Verfügung gestellten Trainigsdaten:

- Während des überwachten Lernens werden dem KNN gleichzeitig Ein-und Ausgabe-Daten präsentiert und durch das Lernverfahren die Ge-wichte so verändert, dass das Netz nach einigen Durchgängen die As-soziation dieser Datensätze selbstständig vornehmen kann. Ziel ist, dass
geringfügig veränderte Eingabedaten richtig klassifiziert werden und so eine Generalisierung durch das KNN erreicht wird.
- Beim bestärkenden Lernen werden dem KNN nur Eingabedaten zur Verfügung gestellt und nach der Auswertung durch das KNN mitgeteilt, ob die Klassifizierung durch das Netz richtig oder falsch ist.
- Das unüberwachte Lernen zeichnet sich dadurch aus, dass Lernen durch Selbstorganisation geschieht. Das verwendete Lernverfahren sorgt da-für, dass ähnliche Eingabemuster in eine Klasse eingeteilt werden, die durch ein oder mehrere Neuronen dargestellt werden. Bei dieser Art des Lernens werden statistische Eigenschaften der Eingabemuster ex-trahiert und darauf basierend generalisierende Klassen gebildet. Interes-sante Arbeiten aus diesem Bereich sind unter anderem Learning-Vector-Quantisation (LVQ) oder selbstorganisierende Karten von Kohonen (vgl. (Koh89, Kapitel 5)) sowie die wachsenden Zellstrukturen (Fri92) bzw. das wachsende Neuronale Gas (Fri95) von Fritzke.

Hebbsche Lernregel Die Grundlage vieler Lernregeln wurde in ihrer ersten Form bereits 1949 von Donald O. Hebb formuliert und nach ihm die Hebbsche Lernregel benannt: Wenn ein Neuron von einem anderen Neuron eine Eingabe erhält und beide gleichzeitig stark aktiviert sind, so erhöht sich das Gewicht der Verbindung zwischen diesen Neuronen (vgl. (Zel94, S. 84)). Die Größe der Änderung des Gewichts wird Lernrate genannt. Sie wird entweder konstant vorgegeben oder geht aus einer Funktion hervor, die berücksichtigt, dass zu Beginn eines Lernvorganges eine hohe Lernrate vorteilhaft ist, gegen Ende des Trainings die Größe der Änderungen jedoch abnehmen sollte. Hierdurch kann ein Konvergieren des KNN in einen optimalen Zustand herbeigeführt werden.

Backpropagation-Regel Eine weit verbreitete Lernregel für überwachtes oder bestärkendes Lernen ist die Backpropagation-Regel (vgl. (Zel94, S. 99-114)). Sie ist eine Verallgemeinerung der sog. Delta-Lernregel , die nur für einstufige Netze mit linearen Aktivierungsfunktionen verwendbar ist. Netze mit linearen Funktionen als Aktivierungsfunktion können nur lineare Funk-tionen berechnen. Mehrschichtige Netze sind mächtiger als einschichtige Net-ze. Für sie wird üblicherweise das Backpropagation-Verfahren bzw. eine ih-rer Weiterentwicklungen verwendet, da es in der Lage ist, Netze mit semi-linearen Aktivierungsfunktionen und mehreren Schichten zu trainieren. Beim Backpropagation-Verfahren wird nach Anlegen von Eingabe- und Ausgabeda-ten an das Netz der noch vorhandene Fehler zwischen vorgegebener Ausgabe und tatsächlicher Ausgabe bestimmt und gewichtet durch die Verbindungs-gewichte rückwärts durch das Netz gesendet, wobei jeweils die Gewichte der Verbindungen abhängig von der Lernrate so geändert werden, dass der Fehler kleiner wird.

2.3 Handelssysteme

Nachdem die Grundlagen Neuronaler Netze und Evolutionärer Algorithmen erläutert wurden, wird im Folgenden in das Anwendungsgebiet eingeführt. Zunächst wird auf Handelssysteme im Allgemeinen eingegangen, danach be-trachtet, wie mechanische Handelssysteme im Speziellen aufgebaut sind. An-schließend wird die Frage der Positionsgrößen-Bestimmung eines Handels-systems diskutiert und im Anschluss verschiedene Maße für den Vergleich von Handelssystemen dargestellt.

In der Literatur gibt es verschiedene Auffassungen, was ein Handelssystem kennzeichnet. Im Rahmen dieser Arbeit ist unter einem Handelssystem ein Regelwerk zu verstehen, durch das festgelegt ist, unter welchen Umständen der Benutzer des Handelssystems bestimmte Aktionen am Kapitalmarkt ver-anlasst. Hat sich der Benutzer des Systems auf ein Handelssystem festgelegt, ist ihm die Entscheidungsfindung abgenommen und er muss lediglich noch ausführen, was das Handelssystem vorschlägt. Wenn der Benutzer selbst die Regeln überprüfen muss, spricht man von einem manuellen Handelssystem bzw. von einem diskretionären Händler. Neben Handelssystemen, die mehr oder we-niger konkrete Handelsempfehlungen geben, findet man Prognose-Systeme, die versuchen, etwa den Kurs eines Wertpapiers zu einem zukünftigen Zeit-punkt vorauszusagen. Ob und wie der Benutzer aufgrund dieser Prognose handelt, bleibt ihm überlassen. Die Ausführung der Empfehlungen des Han-delssystems durch den Menschen ist fehleranfällig und kostet Zeit. Daher hat sich mit dem Aufkommen leistungsfähigerer Rechner der Handel mittels auto-matisierter Handelssysteme, der „mechanischen Handelssysteme“, die keine Eingriffe des Benutzers erfordern, verbreitet. Dem Benutzer eines automati-sierten Handelssystems, dem sog. „systematischen Händler“, obliegt lediglich noch eine übergeordnete überwachende Funktion. Vince hält den Einsatz ei-nes voll automatisierten Handelssystems sogar für unabdingbar, da sich sonst schwer sicherstellen lässt, dass die optimale Positionsgröße gehandelt wird (vgl. (Vin90, S. 41, S. 116)). Um zu überprüfen, ob ein mechanisches Han-delssystem funktioniert, wird ein sog. Backtesting durchgeführt. Dabei werden dem Handelssystem historische Daten präsentiert und aufgrund der Entschei-dungen des Handelssystems eine Auswertung vorgenommen, ob der reale Einsatz möglich ist.

Bei der Entwicklung eines Handelssystems für ein betrachtetes Wertpapier muss auch die Frage beantwortet werden, wie groß die Position sein soll, die von diesem Wertpapier zu jedem Zeitpunkt gehalten wird. Im Grunde stellt das Handelssystem eine Funktion dar, die für jeden Zeitpunkt z.B. po-sitive Werte für eine entsprechend große Position des Wertpapiers, negative Werte für eine entsprechende leerverkaufte Menge des Wertpapiers oder Null für keine Position in diesem Wertpapier liefert. Das Problem wird in mehre-re Teile unterteilt. Neben der Selektion eines passenden Wertpapiers steht das „Market Timing“, das angibt, wann eine Position eingegangen oder aufgelöst werden soll und das „Position Sizing“, das angibt, wie groß die einzugehen-de Position sein soll. Viele Autoren beschränken sich darauf, das Market Ti-ming zu optimieren und lassen das mindestens ebenso wichtige Position Si- zing fast vollständig außen vor (vgl. (Tha99, S. 6f)). Dabei ist es, wie Vince herausstellt, leicht möglich, trotz eines guten Market Timings wegen schlechten Position Sizings schwere Verluste zu erleiden bzw. kaum Rendite zu erwirtschaften. Demgegenüber ist nur ein Market Timing mit geringfügig positivem Erwartungswert nötig, um auf lange Sicht erhebliche Gewinne zu ermöglichen, wenn das Position Sizing richtig durchgeführt wird. Das zu handelnde Wertpapier wird als gegeben vorausgesetzt. Daher wird die Selektion des zu handelnden Wertpapiers im Folgenden nicht betrachtet.

2.3.1 Tape Reader

In seinem erstmalig 1919 publizierten und 2001 neu aufgelegten Buch (Wyc01, Kapitel 4-12) schildert Wyckoff seine Methode, als Tape Reader an der New Yor-ker Börse Geld zu verdienen. Zu dieser Zeit wurden die aktuellen Kursfestel-lungen und Kauf-/Verkaufgebote noch per sog. Ticker an die Händler weiter-geleitet und dort auf ein Band (engl. Tape) ausgedruckt. Heute ist davon noch die Bezeichnung Tick geblieben als Ausdruck für eine einzelne Kursfestellung. Tape Reader fällten ihre Handelsentscheidungen ausschließlich aufgrund der Kursdaten, die ständig auf ihrem Band einliefen, und waren damit teilwei-se sehr erfolgreich. Wie Levere in (LeF23, Kapitel 2) berichtet, gehörte der zu seiner Zeit sehr bekannte Spekulant Livermore ebenfalls zu den erfolgreichen Anwendern des Tape Reading.

Laut (Wyc01, S. 9) waren Kurs-relevante Meldungen bereits Minuten, Stunden und sogar Tage vorher auf dem Band des Tickers zu lesen, bevor die Mel-dungen in der Presse erschienen. Wyckoff erklärt dies mit dem Handeln von besser informierten Investoren, bevor eine Nachricht an die Öffentlichkeit ge-geben wurde. Voraussetzung war, dass der Tape Reader sich darauf verstand, die Daten des Bandes richtig zu interpretieren. Die Tape Reader stellten allei-ne aufgrund einer Reihe von Preis-Feststellungen einen übergeordneten Trend fest und schlossen sich diesem an. Hierzu bedurfte es einiger Erfahrung sowie des ständigen Beobachtens des Marktes, d.h. einer Vielzahl von Wertpapieren gleichzeitig.

Welche Prozesse genau im Gehirn eines Tape Readers ablaufen und zu Kauf-bzw. Verkaufs-Entscheidungen führen, ist nicht zu sagen. Es ist schwer, aus ei-nem neuronalen Netz Regeln zu extrahieren, ohne das gesamte Netz zu simu-lieren, da die Information über das gesamte Netz verteilt ist. Selbst wenn der Tape Reader nach bestem Gewissen versuchte, die zu Grunde liegenden Re-geln darzustellen, ist es sehr gut denkbar, dass sich jemand, der sich nur nach den Regeln verhält, in einigen Fällen anders entscheidet als der Tape Reader selbst.

Im Gegensatz zu den Tape Readern, welche die gesamte Informationsverarbei-tung der Kurse im Kopf durchführen mussten, stehen heutigen Händlern rech-nergestützte Vorverarbeitungen der Marktdaten zur Verfügung. Sehr verbrei-tet sind verschiedene Formen von Kurs/Zeit-Diagrammen, genannt Charts, an denen z.B. Trends oder Widerstands- und Unterstützungs-Bereiche einer Kursbewegung abzulesen sind. Häufig in diese Charts integriert findet man verschiedene Zeit-Reihen, die aus den Kurs-Daten abgeleitet sind, sog.

[...]

Ende der Leseprobe aus 99 Seiten

Details

Titel
Entwicklung von Handelssystemen mit der Genetischen Programmierung: Grundlagen und Fallbeispiel
Hochschule
Universität Hamburg  (Department Informatik)
Note
1,7
Autor
Jahr
2007
Seiten
99
Katalognummer
V81022
ISBN (eBook)
9783638007795
ISBN (Buch)
9783638913812
Dateigröße
3276 KB
Sprache
Deutsch
Schlagworte
Entwicklung, Handelssystemen, Programmierung, Fallbeispiels
Arbeit zitieren
Diplom Informatiker Holger Hartmann (Autor), 2007, Entwicklung von Handelssystemen mit der Genetischen Programmierung: Grundlagen und Fallbeispiel, München, GRIN Verlag, https://www.grin.com/document/81022

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Entwicklung von Handelssystemen mit der Genetischen Programmierung: Grundlagen und Fallbeispiel



Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden