Genetische Algorithmen zur Findung von Trading Rules

Grabowski, Markus

Genetische Algorithmen zur Findung von Trading Rules

Zusammenfassung

Inhaltsangabe:Zusammenfassung:
Zitate wie von Mark Twain Für Börsenspekulationen ist der Februar einer der gefährlichsten Monate. Die anderen sind Juli, Januar, September, April, November, Mai, März, Juni, Dezember, August und Oktober. sind sinnbildlich für die Schwierigkeit oder sogar vielleicht Unmöglichkeit der Vorhersage von Kursverläufen an den Börsen dieser Welt. Das Ziel aber vieler Börsenanleger, bspw. fast aller Kleinaktionäre, ist es durch steigende Kurse (und Dividenden) möglichst hohe Gewinne an der Börse mitzunehmen, dieses würde durch ein Wissen über die Verläufe der zukünftigen Aktienkurse ermöglicht werden. Danach kann das Ziel als ein Maximierungsproblem des Gewinns dargestellt werden. Diese Arbeit versucht eine bereits kommerziell genutzte Idee zur Vorhersage von Verläufen und damit zur Maximierung näher zu bringen: die Genetischen Algorithmen. Dieses sind Optimierungsverfahren, die einen Suchprozess intelligent lenken.
Im Speziellen wird zunächst ein Einblick in die Vielfalt von Börsenanlagestrategien gegeben, hierbei werden u.a. die Buy-and-Hold-Strategie, verschiedene Technische und Fundamentalstrategien erläutert und beurteilt. Nachfolgend wird eine Einführung in die naturanalogen Optimierungsverfahren gegeben, wobei zum einen sämtliche Begrifflichkeiten geklärt werden und zum anderen ein historischer Überblick der Entstehung derartiger Verfahren gegeben wird. Anschließend werden die drei wichtigsten Vertreter der naturanalogen Optimierungsverfahren das Evolutionary Programming, die Evolutionsstrategien, die Genetischen Algorithmen näher gebracht. Nach einer theoretischen Vertiefung vor allem in die Thematik der Genetischen Algorithmen wird ein Modell, dass dieses Verfahren zur Findung von Anlagestrategien verwendet, dargestellt. Weiterhin wird die Programmierung des Verfahrens in der Programmiersprache Java zum Teil erläutert und eine Auswertung der durch die Implementierung gefundenen Daten vorgenommen. Im Speziellen wurden der Untersuchung die Aktienwerte der vergangenen 10 Jahre der Bayer AG, der Bayrischen Motorenwerke AG und der Siemens AG zugrunde gelegt. Die abschließenden Seiten beschäftigen sich mit der Beurteilung sowohl der allgemeinen Genetischen Algorithmen, wie auch mit dem direkt implementierten Modell.
Neben der schriftlichen Ausarbeitung beinhaltet die Arbeit das oben bereits genannte und auf jedem Rechner verwendbare Programm und eine Vielzahl von Dateien, in denen die zur Auswertung betrachteten […]

Leseprobe

Inhaltsverzeichnis

ID 7035

Grabowski, Markus: Genetische Algorithmen zur Findung von Trading Rules

Hamburg: Diplomica GmbH, 2003

Zugl.: Fachhochschule Südwestfalen, Universität, Diplomarbeit, 2003

Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,

insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von

Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der

Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,

bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung

dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen

der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik

Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich

vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des

Urheberrechtes.

Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in

diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,

dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei

zu betrachten wären und daher von jedermann benutzt werden dürften.

Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können

Fehler nicht vollständig ausgeschlossen werden, und die Diplomarbeiten Agentur, die

Autoren oder Übersetzer übernehmen keine juristische Verantwortung oder irgendeine

Haftung für evtl. verbliebene fehlerhafte Angaben und deren Folgen.

Diplomica GmbH

http://www.diplom.de, Hamburg 2003

Printed in Germany

Genetische Algorithmen zur Findung von Trading Rules

Inhaltsverzeichnis

Inhaltsverzeichnis ... I

Abbildungsverzeichnis... III

Tabellenverzeichnis ... III

Quelltextverzeichnis ... III

Verzeichnis der Variablen und Konstanten ... IV

Abkürzungsverzeichnis...V

1. Einleitung...1

2. Problemstellung und Trading Rules...2

3. Naturanaloge Meta-Strategien ...6

3.1. Evolutionär motivierte Verfahren ...7

3.2. Grundlagen...8

3.3. Die wichtigsten evolutionär motivierte Verfahren ...13

3.3.1. Evolutionary Programming...14

3.3.2. Evolutionsstrategien...16

3.3.3. Genetische Algorithmen ...19

3.3.3.1. Die Arbeitsweise Genetischer Algorithmen ...20

3.3.3.2. Genetische Programmierung...24

3.3.4. Konvergenzeigenschaften der Verfahren...26

4. Der verwendete Algorithmus zur Findung von Trading Rules...28

4.1. Konstruktion der Regeln...29

4.2. Fitness und Selektion der Regeln...36

5. Implementierung des Algorithmus in Java ...42

5.1. Aufgabe und Anwendung des Programms ...42

5.2. Bestandteile der Implementierung ...44

5.3. Beispiele spezieller Problemimplementierungen...45

5.3.1. Ziehung der Elterngeneration ...45

5.3.2. Die Ziehung der Eltern- und Ersetztenregeln ...48

5.3.3. Die Durchführung des crossover ...52

6. Programmergebnisse...55

Genetische Algorithmen zur Findung von Trading Rules

7. Beurteilung...60

7.1. Allgemeine Beurteilung Genetischer Algorithmen ...60

7.1.1. Vorteile Genetischer Algorithmen...60

7.1.2. Nachteile Genetischer Algorithmen...61

7.2. Beurteilung des Modells von Allen und Karjalainen...62

8. Abschluss ...64

Anhang A: Quellcode der Implementierung in Java...65

A.1. Die Klasse ,,Genetischer Algorithmus" ...68

A.2. Die Klasse ,,TradingRulefinden" ...78

A.3. Die Klasse ,,Berechnen"...81

A.4. Die Klasse ,,ExcelReader" ...95

A.5. Die Klasse ,,Verzoegerung" ...100

A.6. Die Klasse ,,Evolution"...105

A.7. Die Klasse ,,ExcelWriter" ...111

Anhang B: Installationsanleitung und Änderung für wiederholte Programmläufe 115

Anhang C: Roulette-Auswahl-Verfahren: Problemfall ...117

Anhang D: Formel eines Linearen Rankings...118

Anhang E: Herleitung des Schemata-Theorems ...119

Anhang F: Testfunktionen ...122

Anhang G: Herleitung der Anweisung ,,average" ...124

Literaturverzeichnis ...125

Genetische Algorithmen zur Findung von Trading Rules

III

Abbildungsverzeichnis

Abbildung.1: crossover Verfahren... 11

Abbildung 2: Ablaufschema des Evolutionary Programming... 15

Abbildung 3: Ablaufschema einer (

/,)-Evolutionsstrategie...18

Abbildung 4: Ablaufschema des kanonischen Genetischen Algorithmus... 20

Abbildung 5: Graphische Darstellung der LISP-Ausdrücke +(3,2) und +(-(1,2),3) 25

Abbildung 6: Beispiel einer Regel zur Visualisierung ... 34

Abbildung 7: crossover im Algorithmus... 39

Abbildung 8: Flussdiagramm des Algorithmus ... 40

Abbildung 9: Desktop der Implementierung ... 43

Abbildung 10: Aufgeteilter Chart des Aktienwertes der Bayer AG ... 57

Abbildung 11: ODBC Microsoft Excel Setup ... 116

Tabellenverzeichnis

Tabelle 1: Liste der programmierten Klassen und Methoden... 44

Tabelle 2: Kennzahlen der Anweisungen ... 46

Tabelle 3: Exemplarische Ausgabe für die Testperiode ... 56

Quelltextverzeichnis

Quelltext 1: Ziehung der ersten Ebene... 46

Quelltext 2: Ziehung der zweiten bis neunten Ebene ... 47

Quelltext 3: Ziehung der zehnten Ebene... 48

Quelltext 4: Sortierung... 49

Quelltext 5: Ziehung der Eltern und des Ersetzen ... 51

Quelltext 6: Durchführung des crossover ... 53

Genetische Algorithmen zur Findung von Trading Rules

Verzeichnis der Variablen und Konstanten

Allgemein

Populationsgröße

Position in Lösungsvektoren

Anzahl an Nachkommen

selektiver Druck, selection pressure

u = 1,...,N

Position im nach Fitness sortierter Individuenrangfolge

x Entscheidungsvariablen-Vektor

[0,1]

Zufallszahl

Weiterhin für

Evolutionary Pro-

gramming

F` optimale

Fitness

Konstante

Anzahl der Kontrahenten

Evolutionsstrategie

Konstanten

Vektor der Standartabweichungen

Anzahl der für crossover benötigten Individuen

Schemata-Theorem

()

definierte Länge eines Schemas

Länge eines Schemas

()

Ordnung eines Schemas

Wahrscheinlichkeit eines crossover

Wahrscheinlichkeit einer Mutation

Schema

Modell von Allen &

Karjalainen

Länge des Zeitfensters

Fitnessfunktion

(t)

Signalindikator für Zeitpunkt t

(t)

Signalindikator für Zeitpunkt t

Schlusspreis einer risikobehafteten Anlage zum Zeitpunkt t

einperiodige Verzinsungsrate

r stetige

Verzinsung

Rendite der risikofreien Anlage

Genetische Algorithmen zur Findung von Trading Rules

Abkürzungsverzeichnis

AG Aktiengesellschaft

AGe

Anzahl an Gewinnen

Aufl. Auflage

bspw. beispielsweise

bzgl. bezüglich

bzw.

beziehungsweise

DAX

Deutscher Aktien Index

d. h.

das heißt

Diss. Dissertation

EMH

efficient market hypothesis

engl. englisch

EP Elternpopulation

et al.

Et alii (und andere)

GA Genetischer

Algorithmus

ggf. gegebenenfalls

Hrsg. Herausgeber

LISP List

Processing

MS Microsoft

Min. Minute

NG neue

Generation

NK Nachkomme

Nr. Nummer

o.ä. oder

ähnliches

PMX

partially matched crossover

POI

Poor Obfuscation Implementation

RWH

random walk hypothesis

S. Seite

S&P

Standard and Poor's

Std. Stunde

u.a. unter

anderem

usw.

und so weiter

u.v.a.m.

und vieles anderes mehr

vgl. vergleiche

Vol. Volume

WS Wintersemester

z.B. zum

Beispiel

zugl. zugleich

Einleitung

1. Einleitung

Zitate wie von Mark Twain ,,Für Börsenspekulationen ist der Februar einer

der gefährlichsten Monate. Die anderen sind Juli, Januar, September, April, No-

vember, Mai, März, Juni, Dezember, August und Oktober."

sind sinnbildlich für

die Schwierigkeit oder sogar vielleicht Unmöglichkeit der Vorhersage von Kursver-

läufen an den Börsen dieser Welt. Das Ziel aber vieler Börsenanleger, bspw. fast

aller Kleinaktionäre, ist es durch steigende Kurse (und Dividenden) möglichst hohe

Gewinne an der Börse mitzunehmen

, dieses würde durch ein Wissen über die Ver-

läufe der zukünftigen Aktienkurse ermöglicht werden. Danach kann das Ziel als ein

Maximierungsproblem des Gewinns dargestellt werden. Diese Arbeit versucht eine

Idee zur Vorhersage von Verläufen und damit zur Maximierung näher zu bringen:

die Genetischen Algorithmen. Dieses sind Optimierungsverfahren, die einen Such-

prozess intelligent lenken.

Diese Arbeit besitzt zwei prägnant formulierte Ziele:

Den Einstieg in die so genannten naturanalogen Optimierungsverfahren, zu denen

die Genetischen Algorithmen gehören, und die Anwendung eines Genetischen Al-

gorithmus zur Findung einer Anlagestrategie

an der Börse.

Speziell wird zunächst ein weiterer Einblick in die Problemstellung gege-

ben, danach wird kurz auf einige Verfahren von Aktienanlagestrategien eingegan-

gen. Nachfolgend wird ein Einstieg in die naturanalogen Verfahren gegeben und

jeweils ein grundlegender Algorithmus der drei verbreitesten Methoden Evolutio-

nary Programming, Evolutionsstrategien, Genetische Algorithmen angegeben.

Anschließend wird ein Modell von Franklin Allen und Risto Karjalainen zur Fin-

dung von Trading Rules vorgestellt, welches einen Genetischen Algorithmus ver-

wendet, und dessen Implementierung in Java teilweise erläutert. Abschließend wer-

den einige Ergebnisse von Versuchsläufen betrachtet und die Arbeit durch ein Fazit

abgerundet.

Twain.

Es kann auch Ziele wie Machtgewinn oder Firmenübernahme geben.

Poddig et al. (2000); S. 453-456.

Engl. Trading Rule.

Problemstellung und Trading Rules

2. Problemstellung und Trading Rules

Der historische Beginn des Handels mit Aktien an der Börse lässt sich bis zu

der Gründung der ,,holländischen ostindischen Kompanie" im Jahr 1602 zurückver-

folgen.

Und seit je her können mehr oder weniger regelmäßige Auf- und Abbewe-

gungen der Börsennotierungen beobachtet werden. Diese teilweise täglich in entge-

gengesetze Richtung laufenden Schwankungen der Aktienbewertungen forderten

Versuche einer profitablen Nutzung heraus.

Zu diesem Zweck wurden verschiede-

ne Theorien und Modelle zur Darstellung der Börse und Voraussage von

Börsennotierungen aufgestellt.

Eine Vielfach in der theoretischen Literatur vorgeschlagene Börsenstrategie

ist die so genannte Buy-and-Hold-Strategie: die Daueranlagestrategie.

Danach wird

eine Anlage gekauft und gehalten. Der Wert einer Aktie wird sich danach in Zeitin-

tervallen von genügender Größe steigern.

Die Idee wird nach der ,,efficient market

hypothesis" (EMH) vorgeschlagen, welche besagt, dass auf einem (informations-)

effizienten Markt die Preise jederzeit alle verfügbaren Informationen widerspiegeln.

Diese wird für Wertpapiermärkte noch pointierter durch die ,,random walk hypothe-

sis" (RWH) dargestellt, wonach vor allem die kurzfristigen Kursschwankungen

keinerlei Zusammenhang erkennen lassen. Nach diesen Gedanken lassen Kurswerte

aus der Vergangenheit keinerlei Rückschlüsse auf zukünftige Wertentwicklungen

zu und somit wäre es vollkommen unsinnig zu versuchen zukünftige Kursverläufe

vorhersagen zu wollen, weil es nicht möglich wäre. Es wäre damit lediglich Zeit-

verschwendung eine Trading Rule zu suchen.

Die reale Welt stellt sich oft anders da, als die Kapitalmarktheoretiker sie

modellieren. Daher wurden trotz starker empirischer Beweise

für die Richtigkeit

von EMH und RWH Verfahren entwickelt so genannte Trading Rules , die dem

Börsianer nach konsequenter Befolgung eine überlegende Marktstrategie liefern

Vgl. Loistl (1991); S. 34.

Vgl. Stöttner (1992); S. 266.

Vgl. Stöttner (1989); S. 5-6 & S. 84-89; Stöttner (1992); S. 266 & S. 269-271; Schwanfelder

(2000); S. 99-100.

Vgl. Schwanfelder (2000); S. 100.

Vgl. Stöttner (1989); S. 3-6; Stöttner (1992); S. 266; Tsibouris; Zeidenberg (1995); S. 128-129;

Uhlig (1999); S. 202.

Vgl. Stöttner (1989); S. 5-6.

Problemstellung und Trading Rules

sollten.

In diesem Zusammenhang gibt es eine Vielzahl von Formulierungen. Die-

ses sind zum Teil einfache kurze Leitsätze, mit oft wenig Aussagekraft. Beispiele

sind ,,Don´t follow the crowd They are usually wrong"

, ,,Don´t buy something

because it is low priced"

oder auch ,,Gewinner bleiben Gewinner"

.Weiterhin

existieren unterschiedliche anwendbare Modelle bzw. Systeme.

Eine der wichtigsten deutlich formulierten Anwendungen ist die Portfolio-

strategie

, wonach die Portfolioentscheidung hauptsächlich auf einer subjektiven

und einer objektiven Grundlage beruht. Die objektive Grundlage ist durch die bei-

den Maße Ertrag, zu dem gezahlte Dividenden und realisierte Kursgewinne zählen,

und Risiko, wofür häufig die statistische Varianz oder auch die Standartabweichung

der historischen Erträge verwendet werden, gegeben. Die subjektive Komponente

kommt durch die notwendige Entscheidung für eine Ertrag-Risiko-Kombination

hinzu. Ein Ergebnis dieser Theorie ist, dass durch die Mischung unterschiedlicher

Aktien in der Regel das Gesamtrisiko reduziert werden kann (Diversifikationsprin-

zip).

Zwei bekannte entgegengesetzte Prinzipien sind die Fundamentalstrategien

und die Technischen Strategien. Die Fundamentalstrategen gehen davon aus, dass

der wahre Wert einer Aktie eines Unternehmens durch einen ,,inneren Wert" be-

stimmt ist.

Zur Bestimmung dieses ,,inneren Wertes" sind sowohl betriebswirt-

schaftliche unternehmensspezifische Größen wie bspw. Umsatz- und Gewinnent-

wicklung, Konkurrenzfähigkeit und Qualität des Managements zu beachten, wie

auch gesamt- und weltwirtschaftliche Rahmenbedingungen wie Zinsentwicklung,

politische Tendenzen, Gesetzgebungen u.v.a.m..

Als Grundlage verwenden die

Fundamentalisten bspw. die theoretischen Verfahren des Barwertansatzes oder auch

Der Grund, dass überhaupt Modelle oder auch klar formulierte Prinzipien zur Vorhersage aufge-

stellt werden, kann darin gesehen werden, dass Modelle jederzeit verlässlich die aus ihnen hervorge-

henden Ergebnisse liefern. Sie unterliegen nicht unterschiedlichen Bewertungskriterien aufgrund von

bspw. Gefühlsschwankungen. Vgl. Bauer (1994); S. 116; Eng (1996); S. 241-244; O´Shaughnessy

(1999); S. 36-37; Pereira (2000); S. 2.

Vgl. Eng (1990); S. 107-115.

Vgl. Eng (1990); S. 83-91.

Vgl. O'Shaughnessy (1999); S. 257-278.

Vgl. Stöttner (1992); S. 269.

Liegt der Kurs unterhalb (oberhalb) dieses Wertes, wird die Aktie erworben bzw. gehalten (veräu-

ßert bzw. nicht erworben).

Vgl. Mühlbradt et al. (1988); S. 63-132; Stöttner (1992); S. 267; Jang; Lai (1994); S. 83-84;

Schwanfelder (2000); S. 105-114.

Problemstellung und Trading Rules

Verhältniswerte wie das Kurs-Gewinn-Verhältnis.

Ein erheblicher Kritikpunkt an

diesem Ansatz kann in der Praktikabilität gesehen werden. Es muss eine Vielzahl

von Daten, die zum Teil erst im Nachhinein zur Verfügung stehen, ermittelt und

richtig gewichtet werden.

Als Ursprung der Technischen Strategien

ist die Chartstrategie zu sehen.

Diese benötigt zur Vorhersage der Börsenkurse lediglich die Kursgraphiken

(Charts). Anhand der Abbildung sollen Trends und Verlaufswiederholungen er-

kannt werden. Als Kritikpunkt an diesem Verfahren kann das Fehlen von konzepti-

onell klaren und operablen Analyseinstrumente genannt werden. Allen Technischen

Strategien sind die Annahmen gemeinsam, dass sich historische Verläufe wiederho-

len und dass sich alle marktrelevanten Schwankungen aus dem Marktpreis oder

Kurs unter Umständen mit den dazugehörigen Volumina herleiten lassen. Mo-

delle zur Ermittlung von Trading Rules, die dieser Verfahrensart zuzuordnen sind,

finden sich bspw. bei G. W. Kuo

, dessen Artikel sich mit so genannten moving-

average Trading Rules beschäftigt, bei G. S. Jang und F. Lai

, die in ihrer Arbeit

ein Modell mit neuronalen Netzen entwickeln, bei Z. Ye und L. Gu

, die ein hybri-

des System aus einem künstlichen neuronalem Netz und einem Fuzzy-System ver-

wenden oder auch bei R. Stöttner

, der die Markttechnische Analyse beschreibt.

Ein System, dass mit Hilfe der Verfahren zur Untersuchung von Zeitreihen eine

Normalbandbreite der Bewertung von Aktien unter der Berücksichtigung der Vo-

latilität als Grundlage für strategische Überlegungen herzustellen versucht.

Innerhalb dieser Arbeit wird ein von F. Allen und R. Karjalainen stammen-

des Modell zur Findung von Trading Rules, dass das Prinzip der Genetischen Algo-

rithmen verwendet, ausführlich bearbeitet.

Dieses gehört ebenfalls zu den Techni-

schen Strategien, da es als Datenmaterial lediglich die Tagesschlusspreise von Akti-

en an den Börsen verwendet. Dass diese Zugehörigkeit nicht bei allen Handelsstra-

tegiemodellen, die Genetische Algorithmen verwenden, der Fall ist, zeigt sich

Vgl. O'Shaughnessy (1999); S. 83-102 & S. 147-169; Wellhöfer; S. 12-21.

Vgl. Stöttner (1992); S. 267.

Vgl. Stöttner (1992); S. 268-269; Wellhöfer; S. 8-12.

Vgl. Kuo (1998); S. 81-102; Bei der Formulierung wird sowohl das Prinzip des arithmetic mo-

ving-average, wie auch des geometric moving average verwendet und getestet.

Vgl. Jang; Lai (1994); S. 80-101.

Vgl. Ye; Gu (1994); S. 207-214; Fuzzy-Systeme strukturieren Wissen in numerischer Form.

Vgl. Stöttner (1989); S. 111-175; Stöttner (1992); S. 271-264.

Vgl. Kapitel 4..

Problemstellung und Trading Rules

bspw. in dem Santa Fe Artificial Stock Market. Hierbei werden sowohl Prinzipien

der Fundamentalstrategien wie der Technischen Strategien verwendet.

Weitere

Handelsstrategiemodelle für die Börse, die die oben genannte Art von Algorithmen

verwenden, sind in der Literatur u.a. von A. Noble

oder auch R. J. Bauer

vor-

handen.

Mit welcher Begründung sollten überhaupt Genetischer Algorithmen inner-

halb des finanzwirtschaftlichen Themenbereichs verwendet werden?

Grundlegend

sei gesagt, dass die Verwendung derartiger Algorithmen aufgrund der Vielzahl an

Berechnungen erst seit dem Computerzeitalter möglich ist. Einer der Hauptgründe,

wieso diese Verfahren zur Maximierung des Börsengewinnes verwendet werden

sollten, liegt in der Flexibilität. Algorithmen dieser Art sind zumindest innerhalb

eines Themenbereiches oft ohne Veränderungen für verschiedene Daten oder Zeit-

intervalle zu verwenden. Ihre allgemeine Flexibilität zeigt sich z.B. darin, dass sie

in den verschiedensten Themengebieten anwendbar sind.

Weitere Gründe wie

die Durchsuchung eines großen Lösungsraumes sind in einer ausführlicheren Be-

trachtung der allgemeinen Vor- und Nachteile der Genetischen Algorithmen in Ka-

pitel 7.1. zu finden. Die Wahl des Modells von F. Allen und R. Karjalainen als

Schwerpunkt dieser Arbeit und Grundlage der Implementierung begründet sich zum

einen durch die Verständlichkeit der Modellierung und zum anderen durch die Tat-

sache, dass es im Jahre 1999 veröffentlicht wurde und damit das jüngste in der Re-

cherche gefundene Verfahren dieser Art ist.

Vgl. Palmer et al. (1993); S. 5-16; Joshi; Bedau (1998); S. 1-5; Dawid (1999); S. 33.

Vgl. Noble (1990).

Vgl. Bauer (1994); S. 103-287.

Vgl. Bauer (1994); S. 115-119.

Bspw. zur Beurteilung von Versicherungsaufträgen (vgl. Gammack et al. (1991)), zur Entwick-

lung von 3D-Modellen (vgl. Nguyen; Huang (1994)), zur Lösung von Stundenplanproblemen (vgl.

Colorni et al. (1991)), zur Lösung des iterativen Gefangenendilemmas (vgl. Axelrod (1987)), zur

Lösung des Travelling Salesman Problems (vgl. Grefenstette et al. (1985)) oder auch zur Findung

von Trading Rules auf dem foreign exchange market (vgl. Levich; Thomas (1993)).

Naturanaloge Meta-Strategien

3. Naturanaloge Meta-Strategien

Nachdem im vorherigen Kapitel verschiedene Möglichkeiten der Ausgestal-

tung von Trading Rules genannt wurden, dient dieser Abschnitt als Einführung in

die naturanalogen Verfahren zur Lösung von Optimierungsproblemen, wobei das

Hauptaugenmerk auf die im späteren Modell angewandten Genetischen Algorith-

men gelegt wird. Alle in diesem Kapitel erläuterten Verfahren zählen zu den Meta-

Strategien, da sie ohne direkten Bezug zu einer gegebenen Problemstellung oder

einer konkreten Ausprägung der Zielvorgabe beschreibbar sind. Jede Meta-Strategie

repräsentiert demnach eine Gruppe von Verfahren, die zwar einem gemeinsamen

Prinzip folgen, aber gleichermaßen offen für Modifikationen und Erweiterungen

sind.

Die wichtigste Gemeinsamkeit naturanaloger Meta-Strategien ist - neben der

Orientierung an der Natur - der gesteuerte Einsatz von Zufälligkeiten, wodurch sie

der Klasse der stochastischen Verfahren zuzuordnen sind.

In der praktischen Re-

levanz derartiger Algorithmen zeigt sich wiederum, dass sich zwar Bedingungen

angeben lassen, unter denen das globale Optimum gefunden wird, aber diese in der

Praxis nicht erreichbar sind, wie bspw. unendlicher Laufzeit.

Die Entdeckung von

,,deceptive-functions", einer Klasse von Problemen, bei der das globale Optimum in

seinem Aufbau keinerlei Ähnlichkeit mit anderen als hoch bewerteten Lösungen

hat, zeigt sogar, dass im Speziellen Genetische Algorithmen dabei lediglich eine

Annäherung an das globale Optimum möglich ist. Dadurch ist gegeben, dass zu-

mindest für diesen Bereich kein vollständiger Konvergenzbeweis existieren kann.

Daher kann insgesamt gesagt werden, dass ein naturanaloges Verfahren eine Heu-

ristik ist

- ein Verfahren, dass zwar zweckmäßig ist, aber nicht das Erreichen der

optimalen Lösung garantieren kann - , die ,,ihre steuernden und (oder) informati-

onsauswertenden Prinzipien der Natur entlehnt".

Die naturanalogen Verfahren wiederum lassen sich in drei Unterklassen ein-

teilen, den neuronal, physikalisch und evolutionär motivierten Verfahren. Die neu-

ronal motivierten Verfahren versuchen die Funktionsweise des Gehirns zu imitieren

Vgl. Bjorndahl et al. (1995); S. 255-256.

Vgl. Feldmann (1999); S. 6.

Vgl. Feldmann (1999); S. 28-30.

Vgl. Nissen (1994); S. 119-128.

Def. Heuristiken: Heuristiken sind ,,Verfahren, die mit vertretbarem Aufwand Lösungen generie-

ren, die im Mittel gut sind, ohne dass es möglich ist, deren Optimalität nachzuweisen."; Kistner

(2001); S.141.

Feldmann (1999); S. 31.

Naturanaloge Meta-Strategien

und zu nutzen. Hierbei stehen im Speziellen die Begriffe lernen, erinnern und ver-

gessen im Mittelpunkt des Interesses. Ein dieser Unterklasse zugehörender Bereich

sind die neuronalen Netze, welche versuchen die Spannungsänderungen und Neu-

ronenbewegungen in Synapsen nachzubilden.

Die physikalisch motivierten Ver-

fahren nutzen Gesetzmäßigkeiten als Vorbild, die in der Thermodynamik den

Selbstorganisationsprozessen zur Erreichung energieminimaler Kristallstrukturen zu

Grunde liegen. Hier sein als Hauptvertreter das 1982 u.a. durch S. Kirkpatrick ver-

öffentlichte

,,Simulated Annealing" (Simuliertes Abkühlen) und die u.a. durch G.

Dueck entwickelte ,,Threshold Acceptance" (Schwellenakzeptanz)

genannt. Beide

Methoden beginnen mit einer Anfangslösung, modifizieren diese, bewerten die

Ausprägungen und wählen nach verschiedenen Kriterien den Ursprung oder die

Modifikation als nächste Anfangslösung.

Die ersten beiden Verfahrenstypen sind

hiermit innerhalb dieser Ausarbeitung abgeschlossen, der interessierte Leser kann

neben den in den Fußnoten genannten Texten eine Vielzahl von Literatur zu diesen

Themenkomplexen zu Rate ziehen.

Die dritte und innerhalb dieser Ausarbeitung am intensivsten behandelte Un-

terklasse der naturanalogen Verfahren sind die evolutionär Motivierten. Der Grund

dafür liegt in der Tatsache, dass der im später erläuterten Modell verwendete Gene-

tische Algorithmus dieser Klasse von Verfahren zuzuordnen ist.

3.1. Evolutionär motivierte Verfahren

In diesem sich speziell mit den evolutionär motivierten Verfahren beschäfti-

genden Kapitel werden zunächst die grundlegenden Begriffe und Zusammenhänge

genannt und erläutert. Daraufhin werden die drei wichtigsten Vertreter bearbeitet

und abschließend wird über die Konvergenzeigenschaften berichtet. Bei sämtlichen

Formulierungen wird von einem Maximierungsproblem ausgegangen.

Vgl. Kinnebrock (1994); S. 137-140; Beasley et al. (1993a); S.59. Eine umfassende Bearbeitung

der Thematik neuronaler Netze ist zu finden in: Heistermann (1994); S. 180-242.

Vgl. Kirkpatrick et al. (1983); S. 671-680.

Erläuterung: Vgl. Dueck et al. (1993); S. 42-51.

Vgl. Kinnebrock (1994); S. 46-51; Kistner (2001); S. 157-159.

Naturanaloge Meta-Strategien

3.2. Grundlagen

Alle evolutionär motivierten Verfahren beruhen auf den durch das Schlag-

wort ,,survival of the fittest" bekannten Evolutionsgedanken. Wonach sich alle Le-

bewesen über lange Zeiträume hinweg aus primitiven Arten durch Überleben und

Weitergabe des Erbgutes der besser angepassten Lebewesen an die Folgegeneration

entwickelt haben. Der Entstehung des heute von keinem angesehenen

Wissenschaftler bezweifelten Kredos ging eine Jahrhunderte lange Beschäftigung

mit der Entwicklung der Lebensformen voraus. Diese begann mit dem 1740 von

Carl van Linne veröffentlichtem Werk ,,systema naturae", in dem er neben einer

vollständigen Auflistung aller zu der Zeit ihm bekannten Pflanzen und Tiere auch

die Erklärung abgab, dass alle Lebewesen einmal geschaffen wurden und sich

danach kaum veränderten. Nachdem sich eine Vielzahl von anderen

Wissenschaftlern

diesem Thema widmete, wurde erstmals der Evolutionsgedanke

in Ansätzen im Jahr 1850 von R. Chambers in seinem Werk ,,Vestiges of natural

History and Creation" verbreitet. Im Jahr 1855 erschien der Artikel ,,Über das

Gesetz, welches die Einführung neuer Arten reguliert" von A. R. Wallace. U.a.

dessen Manuskripte, aber auch Einflüsse von Mathematikern wie Malthaus

oder

Philosophen wie Spencer

, regten C. Darwin dazu an seine eigenen Gedanken und

Thesen zu untersuchen und zu veröffentlichen. Durch ihn wurde erstmals im Jahr

1859 mit seinem Werk ,,On the Origin of Species by Means of Natural Selection"

der Evolutionsgedanke in seiner heute bekannten Form formuliert und u.a. durch

sein ihn bekannt machendes Spätwerk ,,The Descent of Man" - in dem er klar

formulierte, dass Mensch und Affe die gleichen Vorfahren besitzen im Jahr 1871

weiter entwickelt.

In den folgenden Zeilen werden biologische Grundbegriffe gemäß ihrer

Handhabung in dieser Ausarbeitung erläutert.

Es werden biologisch gesehen nur

Lebewesen mit haploiden Chromosomensätzen betrachtet. Dieses bedeutet, dass

Hier seien auszugsweise die Naturforscher G. Baron de Cuvier und J. P. de Lamarck, der Zoologe

B. Bonnet und F. de Buffon genannt.

Vor allem durch sein Werk ,,Essay on the Principle of Population" aus dem Jahr 1798, in dem

Malthaus ein mathematisches Modell über die Ausbreitung von Populationen entwickelte.

Von dem im 19. Jahrhundert lebenden Philosophen Spencer wurden Begriffe wie ,,Evolution"

oder auch die Redewendung ,,survival of the fittest" geprägt.

Gesamten Absatz: Vgl. Schöneburg et al. (1994); S. 28-46.

Es sei hier darauf hingewiesen, dass die Begriffe in verschiedenen Werken zu naturanalogen Ver-

fahren zum Teil leicht unterschiedlich verwendet werden.

Naturanaloge Meta-Strategien

immer nur ein Chromosom der Träger der genetischen Information

vorhanden

ist. Hieraus ergibt sich, dass allgemein bekannte Begriffe wie rezessiv und domi-

nant keine Bedeutung haben

, da sie nur bei diploiden Chromosomensätzen, d. h.

bei paarweise auftretenden Chromosomen, ihre Wichtigkeit haben, weil dann meh-

rere Merkmalsträger für gleiche Merkmale vorhanden sind.

Zur Vereinfachung

können daher im Folgenden die Begriffe Individuum und Chromosom als Synony-

me verwendet werden.

Jedes Individuum besteht aus einem Genotypen und einem

Phänotypen. Der Genotyp beschreibt dabei biologisch gesehen alle Erbanlagen ei-

nes Individuums. Diese umfassen sowohl die Lage, die auch als Locus

bezeichnet

wird, als auch die Ausprägung eines Bestandteiles, der im Folgenden Gen genannt

wird.

Bei naturanalogen Verfahren umfasst der Genotyp ,,die kodierten Informati-

onen, mit denen eine Lösung des Optimierungsproblems generiert werden kann"

Dieses können die optimalen Parameter zur Lösung eines Systems oder der Aufbau

einer Berechnungsvorschrift sein, welche ein System optimal löst.

Im Unterschied

dazu gibt der Phänotyp eines Individuums das gesamte wahrnehmbare Erschei-

nungsbild eines Individuums an. In einem naturanalogen Verfahren ist hiermit eine

konkrete Lösung des Optimierungsproblems bzw. die durch eine dem Problem an-

gepasste Bewertungsfunktion berechnete Fitness gemeint.

Es sei hier explizit ge-

schrieben, dass ein identischer Phänotyp aus unterschiedlichen Genotypen hervor-

kommen kann, aber gleiche Genotypen im gleichen Bewertungsbereich immer den

gleichen Phänotypen bewirken.

Weitere wichtige Begriffe sind Selektion, Mutation und Vererbung. Im bio-

logischen Kontext kann Selektion zweierlei bedeuten. Zum einen eine natürliche

Auslese zwischen den Arten, die dadurch gegeben ist, dass zur gleichen Zeit leben-

de Organismen sich durch ständige Konkurrenz um Nahrung und Lebensraum - sei

es durch direkten Kampf oder Vorteile bei der Nahrungssuche gegenseitig dezi-

mieren. Zum anderen ist eine Selektion innerhalb einer Art dadurch gegeben, dass

Vgl. Bruns (1996); S 164.

Für den interessierten Leser sei gesagt, dass sich die Wichtigkeit, ob Merkmalsträger dominant

oder rezessiv gegenüber einem konkurrierenden Merkmalsträger sind, u.a. in den Mendelschen Ge-

setzen ausdrückt. Dazu vgl. Schöneburg et al. (1994); S. 44-46.

Vgl. Michalewicz (1999); S. 15.

Vgl. Bruns (1996); S. 164 & 167.

Im Plural loci.

Vgl. Schöneburg et al. (1994); S. 74; Michalewicz (1996); S. 15.

Feldmann (1999); S. 5.

Vgl. Kinnebrock (1994); S. 101.

Vgl. Schöneburg et al. (1994); S. 74; Feldmann (1999); S. 5-6.

Naturanaloge Meta-Strategien

die der Umwelt besser angepassten Lebewesen sich an der Paarung häufiger beteili-

gen und daher eher ihre Genkombinationen an die folgende Generation weiterge-

ben.

Es ist dabei auffällig, dass eine vom Phänotyp abhängende Auslese sich zu-

nächst auf den Genotypen eines Individuums der nächsten Generation auswirkt.

Die unterschiedlichen Ausprägungen sind in den im Kapitel 3.3. erläuterten Verfah-

ren zu erkennen. Das Evolutionary Programming versucht die erste Sichtweise

nachzubilden und die Verfahren der Genetische Algorithmen und Evolutionsstrate-

gien die Zweite.

Mit Mutation

ist die zufallsgesteuerte plötzliche Änderung des Genotypen

eines Individuums gemeint, wobei in den später vorgestellten Verfahren entweder

nur ein einziges Gen oder der gesamte Genotyp betroffen sein kann. Andere in der

Natur vorkommende Mutationsarten wie z.B. die Genommutation, bei der die An-

zahl an Chromosomen verändert wird, werden in den hier vorgestellten Algorith-

men nicht weiter betrachtet. Die Mutation ist ein wichtiger Bestandteil der Evoluti-

on, weil sie sich ohne sie ,,festfahren" könnte.

Es könnten die vorhandenen Gen-

kombinationen optimal ausgenutzt worden sein, aber eine Verbesserung durch eine

nicht vorhandene Variation ermöglicht werden. Im Sinne des Optimierungsverfah-

rens wäre das ,,festfahren" mit dem stehen bleiben in einem lokalen Optimum

gleichzusetzen.

Unter dem Begriff der Vererbung ist innerhalb der evolutionär motivierten

Verfahren die geschlechtliche Vererbung (Meiose) zu verstehen. Dabei findet ein

Austausch von Bestandteilen, der durch eine Selektion gefundenen elterlichen

Chromosomen, statt.

Dieses geschieht in naturanalogen Verfahren durch crosso-

ver. Es werden jeweils zwei vorhandene Chromosomen verwendet, aus denen neue

Individuen für die Folgegeneration generiert werden. Jetzt ist die Frage zu klären,

wie dieses vonstatten gehen soll. Hier seien vier wichtige crossover-Varianten ge-

Vgl. Feldmann (1999); S. 59-120.

Vgl. Schöneburg et al. (1994); S. 468.

Vgl. Bauer (1994); S. 10; Michalewicz (1996); S. 15-18.

In der von C. Darwin formulierten Theorie waren Mutationen lediglich Mechanismen, die der

Selektion eine Auswahl ermöglichen. Sie sind danach für die Weiterentwicklung der Lebensformen

nicht verantwortlich. Dass die Evolution sich ohne die Mutation ,,festfahren" könnte, wurde erst

später durch den dänischen Botaniker Johannsen ins Verständnis der Wissenschaft gerückt. Vgl.

Schöneburg et al. (1994); S. 76.

Vgl. Schöneburg et al. (1994); S. 76-80.

Vgl. Feldmann (1999); S. 67-69.

Naturanaloge Meta-Strategien

Abbildung 1: crossover Verfahren

nannt: Der Ein-Punkt-crossover, Zwei-Punkt-crossover

, PMX

und Uniform-

crossover.

Bei den in der Literatur verwendeten Genetischen Algorithmen wird

Mutterchromosom: 4 3 5 2 1

Vaterchromosom:

3 2 4 1 5

Ein-Punkt-crossover: 4 3 | 5 2 1 Zwei-Punkt-crossover: 4 3 | 5 2 | 1

3 2 | 4 1 5

3 2 | 4 1 | 5

4 3 4 1 5

4 3 4 1 1

PMX:

4 3 | 5 2 | 1

3 2 | 4 1 | 5

5 3 4 1 2

Uniform-crossover: Maske: 1 1 0 1 0 {1 für Mutter; 0 für Vater.}

4 3 4 2 5

der Ein-Punkt-crossover bevorzugt.

Bei diesem wird ab einer in beiden Eltern

identischen zufällig gewählten Position dem crossover Punkt innerhalb des Ge-

notypen eine Ersetzung der Genkombination des jeweils anderen Elternindividuums

vorgenommen.

Hierbei bildet das Mutterchromosom jeweils die Grundlage. Beim

Zwei-Punkt-crossover und PMX werden jeweils zwei crossover-Punkte gesucht,

wobei zum einen eine dem Ein-Punkt-crossover entsprechende Ersetzung im Mittel-

teil vorgenommen wird

und diese zum anderen durch eine vom Mittelteil vorge-

gebene Ersetzung der Gene im gesamten Genotyp erweitert wird.

Beim Uniform-

crossover wird eine binär codierte crossover-Maske in der Länge des Genotypen

zufällig generiert, dann bei einer 1 das Gen des einen Elternindividuums gesetzt und

Dieses lässt sich bis zum k-Punkt crossover weiterführen. Vgl. Stützle (2001); S. 11.

PMX steht für ,,partially matched crossover", es wird vor allem bei Reihenfolgeproblemen ver-

wendet.

Weitere Verfahren: Order-crossover, Edge-crossover u.a., oder auch die Mittelbildung beider

Eltern je Komponente. Vgl. Feldmann (1999); S. 95-96 & 214-227. Diskussion zum Thema, welches

crossover Verfahren zu bevorzugen ist. Vgl. Beasley et al. (1993b); S. 170-172.

Vgl. Bäck et al. (1997); S.20.

Vgl. Kistner (2001); S. 161.

Vgl. Kistner (2001); S. 162.

Vgl. Goldberg (1989); S. 171-172.

Nach dem Zwei-Punkt-crossover

wird - durch den Mittelteil vor-

gegeben - die 4 außerhalb des

Tauschbereiches durch eine 5 und

die 1 durch eine 2 ersetzt.

Naturanaloge Meta-Strategien

bei einer 0 das des anderen.

Alle vier Verfahren sind in Abbildung 1 anhand zwei-

er Vektoren dargestellt, wobei ,,|" für den crossover-Punkt steht.

Weiterhin ist zu klären, wie die Eltern gewählt werden sollen, wie also die

Selektion innerhalb einer Art dargestellt werden soll. Hierbei gilt grundsätzlich,

dass Eltern mit größerer Wahrscheinlichkeit aus den Individuen mit einer hohen

Fitness stammen sollen. Auch hierzu stehen verschiedene Verfahren zur Verfügung.

Hier seien das Roulette-Verfahren, das Lineare Ranking und das (N,

µ)-Verfahren

genannt.

Das Roulette-Verfahren ist innerhalb einer Problembehandlung für die

Implementierung in Anhang C erläutert, es folgt grundsätzlich dem Prinzip, dass

jedem Individuum eine Trefferwahrscheinlichkeit proportional zu dessen Fitness

zugestanden wird. Beim Linearen Ranking werden die Chromosomen nach ihren

Phänotypen sortiert und anschließend jeder Position in dieser Reihe (i = 1,2,...,N)

eine Wahrscheinlichkeitsdichte in bspw. einer der folgenden Formen zugewiesen.

Hierbei muss die Sortierung bei der ersten Variante mit dem schlechtesten und bei

der Zweiten mit dem besten Phänotypen beginnen.

( )

(

)

( )

,,SP" gibt den selektive Druck (selection pressure) an, die Wahrscheinlichkeit des

besten Individuums ausgewählt zu werden, verglichen mit der durchschnittlichen

Wahrscheinlichkeit der Selektion aller Individuen. Dann wird ein Verteilungsfunk-

tionswert

( )

zugewiesen. Daraufhin wird eine gleichverteilte Zufalls-

zahl z

[0,1] ermittelt und das Chromosom mit der Nr. j, für die F(j-1) z < F(j)

gilt, gewählt. Dadurch werden die Individuen mit den höheren (bzw. niedrigeren)

Nummern, also mit dem größeren Phänotypen, häufiger gewählt. Beim (N,

µ)-

Verfahren wird ebenfalls eine Sortierung vorgenommen, anschließend können aber

nur die

µ-besten Chromosomen durch eine Zufallszahl z zwischen 1 und µ gewählt

Vgl. Beasley et al. (1993b); S.171.

Vgl. Kinnebrock (1994); S. 70-75.

Vgl. Pohlmann (1995); S. 129-130. Der Verteilungsfunktionswert kann bei diese Variante durch

die Annahme eines selektive Drucks von 2 stark vereinfacht werden. Siehe Anhang D.

Vgl. Neely (1999); S. 13.

Naturanaloge Meta-Strategien

werden. Dieses war ein kurzer und ungenauer Einblick in die Wahlverfahren der

Elternindividuen. Als grundlegendes gilt lediglich festzuhalten, dass die Eltern aus

den guten Phänotypen stammen müssen um das Prinzip des ,,survival of the fittest"

darzustellen, im Speziellen das Prinzip der Selektion bei der Wahl der Vererbungs-

partner.

Weiterhin ist zu klären, welche Individuen durch die neu gefundenen Lö-

sungen in der Folgegeneration ersetzt werden sollen. Hier seien das Generational

Replacement genannt, bei dem die alte Population komplett durch die Neue ersetzt

wird, der Elitismus, bei dem die n besten Individuen der alten Generation grund-

sätzlich übernommen werden und das delete-n-last, bei dem die n schlechtesten

Chromosomen der aktuellen Population durch n Nachkommen ersetzt werden.

3.3. Die wichtigsten evolutionär motivierte Verfahren

Die Idee, die evolutionär motivierten Verfahren zur Optimierung zu ver-

wenden, kann bis in die späten 1950er Jahre zurückverfolgt werden. Seitdem kris-

tallisierten sich als wichtigste Ansätze drei verschiedene Richtungen heraus, deren

Ursprünge in den 1960ern liegen und seitdem in einer Vielzahl von Werken modifi-

ziert und verarbeitet wurden.

Ihre ersten öffentlichen Erwähnungen fanden dabei

das Evolutionary Programming durch L. J. Fogel im Jahr 1962

, die erste ausführ-

liche Beschreibung in dessen Dissertation im Jahr 1964 ,,On the organization of

intellect". Die Evolutionsstrategien wurden durch I. Rechenberg im Jahr 1965 und

die erste komplette Beschreibung im gleichnamigen Werk ,,Evolutionsstrategien"

im Jahre 1973 veröffentlicht. Die Genetischen Algorithmen ihrerseits wurden durch

J. Holland im Jahr 1962

entwickelt und erstmals umfassend in dessen Werk ,,A-

daptation in Natural and Artificial Systems" aus dem Jahre 1975 beschrieben. Ne-

ben Erläuterungen der Muster dieser Verfahren wird ein Überblick über eine Erwei-

terung der Genetische Algorithmen, der im Modell direkt angewandten Genetischen

Weitere Ersetzungsschemata sind bspw. der schwache Elitismus, das X mit Alterung, das X mit

Kindergarten. Diese und die im Text genannten Verfahren vgl. Schöneburg et al. (1994); S. 205-210.

Vgl. Bäck et al. (1997); S. 15.

Vgl. Fogel (1962).

Vgl. Holland (1962).

Naturanaloge Meta-Strategien

Programmierung, gegeben.

Diese wurde erstmals durch den US Amerikaner J. R.

Koza im Jahre 1992 umfassend der Öffentlichkeit vorgestellt.

3.3.1. Evolutionary Programming

Um die Funktionsweise des Evolutionary Programming näher zu bringen

wird die Formulierung von Lawrence J. Fogel erläutert

, welche für später veröf-

fentlichte Erweiterungen die Grundlage bildet. Dieses Prinzip versucht die Selekti-

on der Arten zu imitieren. Das Prinzip der Vererbung und damit des crossover wird

vollkommen abgelehnt

, zur Evolution werden lediglich Mutationen verwendet.

Weiterhin ist festzuhalten, dass für die Fitnessfunktion und die Kodierungsform

keinerlei Einschränkungen gelten.

Der Ablauf dieses Verfahrens beginnt damit, dass

verschiedene Genoty-

pen zufällig gebildet werden, dieses können bspw. reellwertige Vektoren sein. Dar-

aufhin wird jedes Individuum anhand der Funktion FP bewertet. Die endgültig Zu-

weisung der Fitness wird durch OP = F' FP erreicht. Wobei F' für die optimale

Lösung des Problems steht. Hier wird eine Schwierigkeit des Verfahrens deutlich,

es findet nicht die optimale Lösung, sondern die Parameter mit denen diese Lösung

erreicht wird.

Daraufhin werden

Nachkommen je Individuum durch die Muta-

tionsformel

( )

(

)

(

)

In der Literatur herrscht keine Einigkeit, ob die Genetischen Programmierung als Erweiterung der

Genetischen Algorithmen oder als eigenständiges Verfahren gesehen werden kann. Bspw. Unter-

schied zwischen Kinnebrock (vgl. Kinnebrock (1994); S. 101) und Allen und Karjalainen (vgl. Al-

len; Karjalainen (1999); S. 249). Der Autor dieser Arbeit hat sich der Ansicht des Entwicklers der

Genetischen Programmierung angeschlossen, wonach es sich um eine Erweiterung handelt. (vgl.

Koza (1992); S. 18) Dieses begründet sich auch dadurch, dass alle bei Genetischen Algorithmen

vorgenommenen Operationen gleichermaßen gelten.

Vgl. Bäck et al. (1997); S. 22. Das Werk an sich: Koza (1992).

Kapitel: Vgl. Fogel et al. (1966); S. 11-27 & S. 138-143; Bäck (1996); S. 91-106; Feldmann

(1999); S. 8 & S. 110-123.

Crossover werden von Vertretern dieses naturanalogen Verfahrens als Defektfilter interpretiert.

Statt der optimalen kann eine relaxierte Lösung als obere Schranke verwendet werden. Vgl. Feld-

mann (1999); S. 112.

Weiterhin ist die Fitnessfunktion so zu skalieren oder zu transformieren, dass sie ihr Optimum im

Wert 0 annimmt. (vgl. Bäck (1996); S. 94) (Ist hier geschehen.) Dieses begründet sich wohl dadurch,

dass bei der im Folgenden genannten Mutationsformel bei üblicher Konstantensetzung nur eine

sichere Standartabweichung von 0 erreicht wird, wenn auch OP = 0 ist. Und damit nur in diesem Fall

gesichert ist, dass beim Erreichen des Optimums dieses nicht mehr durch Mutationen verlassen wird.

Naturanaloge Meta-Strategien

Abbildung 2: Ablaufschema des Evolutionary Programming

gebildet. Hierbei steht x

für den Lösungsvektor des Individuums i. Jede Komponen-

te k des neu erzeugten Chromosoms i+1 wird durch eine Addition einer aus einer

Normalverteilung gezogenen Zahl erreicht. Diese hat einen Erwartungswert von

Null und eine Standartabweichung, die von der Fitness des Elternindividuums ab-

hängt. Dadurch wird erreicht, dass sich Lösungen in der Nähe des Optimums weni-

ger verändern als andere. Denn je geringer die - jetzt etwas unpassend bezeichnete -

Fitness, also je geringer der Abstand zum globalen Optimum ist, desto kleiner ist

die Standartabweichung. Die Komponenten

und

können prinzipiell für jedes k

separat angegeben werden. Es wird jedoch in der Literatur vorgeschlagen grund-

sätzlich

= 1 und

.= 0 zu setzen, um zum einen eine geringere Zahl der festzule-

genden Parameter zu bekommen und zum anderen die Mutationsformel zu

vereinfachen.

Die Erzeugerpopulation und die Nachkommen bilden zusammen die

neue Generation NG. Die durch Mutation erreichten Nachkommen werden eben-

falls anhand von OP bewertet und abschließend eine Sortierung anhand der Fitness

beginnend mit der Besten vorgenommen. Danach werden zufällig q verschiede-

Vgl. Nissen (1994); S.171; Bäck (1996); S. 94.

Ermittle optimalen Zielfunktionswert F'.

Beginn

Wähle zufällig

Genotypen für Elterngeneration EP.

Ermittle Werte anhand der Funktion FP(i)

i EP.

Bewerte Individuen mit OP(i) = F' FP(i)

i EP.

Wiederhole bis Abbruchbedingung erreicht:

Beginn

Erzeuge

Individuen EP durch die Mutationsvorschrift zufällig

erzeugte Nachkommen NK.

Bewerte die Nachkommen durch OP.

Setze Neue Generation NG = {EP

NK}.

Setze Anzahl der Gewinne AGe

i NG auf 0.

Sortiere NG gemäß OP(i), beginnend mit dem besten Wert.

Wähle

i NG q verschiedene Kontrahenten aus NG.

Beginn

Führe

i NG Vergleiche mit seinen q Kontrahenten durch.

Wenn OP(i)

OP(Kontrahent):

Setze AGe(i) = AGe(i) + 1.

Ende

Reduziere NG auf

Individuen von vorne nach hinten durch Ausschluss

nach dem AGe Kriterium.

Setze EP := NG.

Ende

Naturanaloge Meta-Strategien

ne Kontrahenten je Chromosom aus NG gezogen. Jedes Individuum wird mit seinen

q Kontrahenten in der Art verglichen, dass es einen Sieg zugeschrieben bekommt,

wenn es eine bessere oder gleichgroße Fitness hatte. Dieses Prinzip stellt den Evo-

lutionskampf zwischen Arten dar, jedes Individuum entspricht demnach einer eige-

nen Art. Dass ein Individuum mit schlechterer Fitness mehr Siege als eins mit Bes-

serer erreichen kann, spiegelt bspw. das Leben in unterschiedlichen Erdteilen oder

auch das Prinzip der wandernden Arten wieder, die sich mit immer anderen Geg-

nern messen müssen. Nach den Zweikämpfen wird die Population wieder auf

Chromosomen verkleinert. Es werden die Individuen mit den meisten gewonnenen

Zweikämpfen behalten, von vorne nach hinten durch die Reihenfolge laufend.

Durch die vorherige Sortierung wird erreicht, dass bei gleicher Anzahl an gewon-

nenen Zweikämpfen das Individuum mit der besseren Fitness zurückbleibt. Der

gesamte Algorithmus ist in Form eines Ablaufschemas in Abbildung 2 dargestellt.

3.3.2. Evolutionsstrategien

Ein weiteres naturanaloges Verfahren sind die vom Deutschen Ingo Rechen-

berg stammenden Evolutionsstrategien, welche vor allem durch H.-P. Schwefel

erweitert wurden.

Bei diesem Verfahren werden - gegenüber dem Vorherigen -

crossover verwendet, wobei die Mutationen weiterhin größere Wichtigkeit besitzen.

Die Individuen sind hierbei als zwei reellwertige Vektoren zu codieren, wobei der

Vektor x aus k Entscheidungsvariablen besteht und der Vektor

aus Standartab-

weichungen für jede der k Komponenten, welche zur Mutation verwendet werden.

Die ursprüngliche Formulierung war die (1+1)-Evolutionsstrategie, bei der ein In-

dividuum einen zufällig veränderten Nachkommen durch Mutation hervorbringt

und das fitteste Individuum der Beiden überlebt. Diese lässt sich verallgemeinert als

eine (

+)-Strategie darstellen, bei der Eltern mutierte Nachkommen produzie-

ren und die besten

Individuen aller die nächste Generation stellen. In diesem

Prinzip wurde das Problem erkannt, dass das in der Natur vorkommende Altern

nicht modelliert wurde, es also möglich ist, dass dominante Strategien für immer in

Kapitel: Vgl. Kinnebrock (1994); S. 95-99; Rechenberg (1994); S. 45-50 & S. 81-100; Schöne-

burg et al. (1994); S. 141-184; Bäck (1996); S. 66-90; Feldmann (1999); S. 91-109.

,,Das Mitführen der Strategieparameter hat sich in Experimenten als konvergenzsteigernd heraus

gestellt, allerdings fehlt bisher eine fundierte Theorie, welche Aussagen dieser Art untermauern

könnte."; Kinnebrock (1994); S. 97.

Naturanaloge Meta-Strategien

der Population bleiben und somit den Prozess in seinem Erkunden neuer Regionen

behindern.

Dadurch motiviert wurde im Jahr 1975 die (

,)-Strategie durch H.-P.

Schwefel veröffentlicht. Bei dieser wird die Selektion der

besten Individuen le-

diglich auf die

neuen Individuen beschränkt, wodurch die Lebensdauer maximal

eine Generation betragen kann.

Dieses entspricht einem Generational Replace-

ment. Eine weitere und im Folgenden erläuterte Variante ist die (

/,)-Strategie,

bei der durch crossover von je

Individuen der möglichen Eltern Nachkommen

produziert werden, wobei wiederum die

besten der Nachkommen die Eltern der

nächsten Generation bilden.

Die folgenden allgemeinen Aussagen sind üblich und gelten für alle genann-

ten Strategiearten. Hierbei zunächst die Mutation: Ein x-Vektor eines Individuums

wird im Verlauf durch eine Addition einer normalverteilten Zufallszahl mutiert.

Dieses geschieht in der Form, dass aus einem Vektor x

für den neuen Vektor x

bzw. für den Vektor

aus

gilt:

( )

(

)

(

)

mit

und

(

)

ist weiterhin die Populationsgröße

und

bzw.

sind Konstanten. Für die Vererbung stehen die bereits genannten

crossover Verfahren zur Verfügung

, wobei für zusammengehörende Entschei-

dungsvariablen-Vektoren und Vektoren der Standartabweichungen jeweils die glei-

che Rekombination vorgenommen wird.

Der eigentliche Ablauf beginnt hierbei mit der Erzeugung von

zufällig ge-

funden Regeln inklusive der Strategievektoren, die die Elternpopulation EP darstel-

len. Daraufhin wird die durch die Fitnessfunktion FP bewertete beste Lösung ge-

Ob dieses im eigentlichen Suchvorgang einen Nachteil für den Optimierungprozess darstellt, sei

hier vom Autor bezweifelt. In Kapitel 3.3.4. zeigt sich, dass das Behalten von den bisher besten

Lösungen durchaus positive Eigenschaften haben kann.

Es gibt auch Mischformen dieser beiden Ansätze, die [

+`(,)]-Strategie, bei der es auf der

Populationsebene zu einer (

+)-Strategie und innerhalb einer Population zu einer (,)-Strategie

kommt.

Dieses Verfahren wurde gewählt, da es bei

= 2 der sexuellen Vererbung entspricht und so ein

weiterer Hinweis auf die Nachahmung der Natur und auf die Ähnlichkeit der drei Verfahren gegeben

ist. Weiterhin ist es ein verbreitetes Prinzip.

Wobei die im oberen Kapitel genannten Verfahren für den Fall zweier Eltern dargestellt wurden,

was bei

= 2 gegeben ist.

Naturanaloge Meta-Strategien

Beginn

Wähle zufällig

Lösungen inklusive Strategievariablen für Elterngeneration

EP.

Ermittle Phänotypen anhand der Fitnessfunktion FP()

i EP.

Setze BesteLösung := max(FP(i))

i EP.

Wiederhole bis Abbruchbedingung erreicht:

Beginn

Setze

neue Generation NG := leere Menge.

Wiederhole

mal:

Beginn

Wähle

Eltern zufällig aus EP.

Erzeuge Nachkommen NK durch Kombination der Vektoren

der Eltern (Variablen und Standartabweichungen).

Erzeuge Mutationen der beiden Vektoren.

Bewerte NK gemäß FP.

Wenn FP(NK) > FP(BesteLösung).

Setzte BesteLösung := NK.

Setze NG := {NG

NK}.

Ende

Ersetze EP durch

beste Individuen aus NG.

Passe Abbruchkriterium an.

Ende

Abbildung 3: Ablaufschema einer (

/,)-Evolutionsstrategie

sucht und gespeichert. Als Nächstes beginnt ein Kreislauf, der bis zu einem auch

in den anderen beiden naturanalogen Verfahren geltendem Abbruchkriterium

durchlaufen wird. Dieses lässt bspw. den Kreislauf solange wiederholen, bis j Gene-

rationen lang keine Verbesserung der besten Lösung erreicht wurde, wodurch ein

Beispiel der in Abbildung 3 zu erkennenden Anpassung des Kriteriums gegeben ist.

Die Schleife setzt zunächst die neue Generation auf die leere Menge. Daraufhin

wird die innere Schleife erreicht und

-mal durchlaufen. In dieser werden zunächst

Eltern aus einer Gleichverteilung aus EP gezogen. Daraufhin werden neue Indivi-

duen durch crossover der jeweiligen Vektoren gebildet und anschließend durch den

am Anfang dieses Unterkapitels erläuterten Mechanismus mutiert. Dann werden die

Individuen ebenfalls gemäß FP bewertet. Folgend wird für jeden Nachkommen

überprüft, ob die Fitness besser war als die bisher Beste, was im zutreffenden Falle

eine Speicherung der gefundenen Lösung als beste Lösung nach sich zieht. Die

neue Generation wird durch die Vereinigung von EP und den Nachkommen sukzes-

siv vergrößert. Hierdurch ist die innere Schleife beendet und die Aufgabe der äuße-

ren Schleife liegt darin, die vorhandene Population auf die

besten Individuen zu

reduzieren. Ein Ablaufschema der gesamten (

/,)-Strategie befindet sich in Ab-

bildung 3.

Naturanaloge Meta-Strategien

3.3.3. Genetische Algorithmen

Als drittes naturanaloges Verfahren wird das Prinzip der Genetischen Algo-

rithmen vorgestellt. Wie bei den vorherigen beiden Verfahren gilt wiederum, dass

zunächst die Grundform vorgestellt werden soll, wobei in diesem Falle eine Erwei-

terung - die Genetischen Programmierung - näher betrachtet und zusätzlich ein Ein-

blick in die theoretische Fundierung vorgenommen wird. Dieser größere Aufwand

erklärt sich durch die Anwendung dieser Idee im direkt verwendeten Modell dieser

Arbeit.

Dieses von John Holland veröffentlichte und durch David E. Goldberg wei-

terentwickelte

Verfahren wird in seiner Grundform als kanonischer genetischer

Algorithmus bezeichnet. Diese Grundform geht von binärer Codierung der Indivi-

duen, Ein-Punkt-crossover, Bit-Mutation

, einer Selektion nach der relativen Fit-

ness mit dem Roulette-Verfahren und einem Generational Replacement aus.

Diese

Einschränkungen wurden in einer Vielzahl von Varianten bereits relativiert.

Wei-

ter ist zu vermerken, dass bei Genetischen Algorithmen die crossover in den Vor-

dergrund rücken. Mutationen treten in den Hintergrund

und dienen lediglich dem

Zweck zur Verhinderung einer zu frühzeitigen Konvergenz und sorgen dadurch für

eine gewisse Divergenz und Inhomogenität innerhalb der Populationen, wodurch

ansonsten ein ,,rutschen" in ein lokales Optimum begünstigt werden könnte.

Aber zunächst der grundlegende kanonische genetische Algorithmus:

werden

zufällig gesetzte Lösungen gewählt, welche in der Form eines binären

Strings codiert werden, und als Elternpopulation EP gespeichert. Dann wird die

Vgl. Goldberg (1989); S. 1-18.

Bit-Mutation bedeutet, dass immer nur ein Bit des verwendeten Strings zur gleichen Zeit mutieren

kann.

Vgl. Goldberg (1989); S. 11; Feldmann (1999); S. 79.

Das Modell von Allen und Karjalainen benutzt bspw. lediglich nur noch die Ein-Punkt-crossover

von den genannten Vorgaben. Vgl. Allen; Karjalainen (1999).

Neben den beiden Verfahren Mutation und crossover zur Findung neuer Lösungen bzw. neuer

Individuen hat John Holland einen dritten so genannten Operator dieser Art genannt: Die Inversion.

Bei dieser wird die Reihenfolge von Elementen eines Chromosoms innerhalb zweier zufällig ge-

wählter Punkte umgekehrt. Da dieser Operator sich in praktischen Arbeiten als nicht nützlich zeigte

und daher nur sehr selten verwendet wurde, wird er in dieser Ausarbeitung nicht weiter betrachtet.

(vgl. Davis (1991); S. 21) Weitere der Nachahmung der Natur entliehene Operatoren sind die Dupli-

kation, die Deletion, die Translation, die Segretion und die sexuelle Differenzierung. Diese haben

alle ebenfalls nur geringe Bedeutung und werden daher nur der Vollständigkeit halber genannt. Vgl.

Goldberg (1989); S. 148-184; Nissen (1994); S. 72.

Schöneburg et al. (1994); S. 200-203.

Vgl. Goldberg (1989); S. 1-18; Schöneburg et al. (1994); S. 185-210; Feldmann (1999); S. 79-83.

Naturanaloge Meta-Strategien

Abbildung 4: Ablaufschema des kanonischen Genetischen Algorithmus

Beginn

Wähle zufällig

Genotypen für Elterngeneration EP.

Ermittle Phänotypen anhand der Fitnessfunktion FP()

i EP.

Setze BesteLösung = max(FP(i))

i EP.

Wiederhole bis Abbruchbedingung erreicht:

Beginn

Bestimme F

FP(i) i EP.

Erzeuge neue Generation NG aus n Individuen durch Ein-Punkt-crossover.

Wähle dabei jeweils Eltern aus den fittesten Individuen gemäß FP(i)/F

Erzeuge zufällige Mutationen in Genotypen.

Setze Beste = max(FP(i))

i NG.

Wenn Beste > BesteLösung:

Setze BesteLösung = Beste.

Ersetze EP durch NG.

Ende

beste Lösung im Sinne der Fitnessfunktion FP gesucht. Daraufhin wird für das Rou-

lette-Verfahren die Summe der Fitnesswerte über alle Individuen berechnet und

anschließend werden mit Hilfe von durch das Auswahlverfahren gefundenen Eltern

n Individuen für die neue Generation rekombiniert. Dafür wird zufällig für jede

Rekombination ein crossover-Punkt gewählt und um ihn ein Ein-Punkt-crossover

durchgeführt. Als letztes wird mit einer geringen Wahrscheinlichkeit bei wenigen

Individuen eine Komponente durch eine Mutation variiert. Abschließend wird in-

nerhalb der neu gefundenen Generation NG die fitteste Lösung gesucht und in dem

Falle, dass sie die bisher beste Lösung innerhalb des gesamten Algorithmuslaufes

übertrifft, eine Überspeicherung der bisher besten Lösung durch jene vorgenom-

men. Am Ende des großen Kreislaufes wird NG zur neuen EP. Der gesamte Ablauf

ist wiederum in Abbildung 4 in einem Schema dargestellt.

3.3.3.1. Die Arbeitsweise Genetischer Algorithmen

,,G[enetic] A[lgorithms] combines both exploration and exploitation in the

same time in an optimal way"

lautet eine Aussage von John Holland. Genetische

Algorithmen erreichen demnach die optimale Kombination von der Untersuchung

des gesamten Lösungsraumes (exploration) und der Benutzung des Wissens von

Beasley et al. (1993a); S. 65.

Naturanaloge Meta-Strategien

bisher gefundenen und verarbeiteten Lösungen (exploitation). Ob und inwieweit

diese Aussage bereits theoretisch gezeigt wurde ist der Inhalt des Folgenden. Hierzu

wird zunächst das Schemata-Theorem erläutert und anschließend die von John Hol-

land benutzte Analogie des k-armigen Banditen genannt.

Die erste und bis heute wichtigste Erklärung des Suchfortschrittes innerhalb

Genetischer Algorithmen ist das Schemata-Theorem, welches John Holland bereits

1975 für kanonische Genetische Algorithmen formulierte.

Es ist zunächst zu klä-

ren was unter einem Schema zu verstehen ist. Ein Schema

ist eine Ähnlichkeits-

schablone der Länge l, welche eine Serie von l Genen bezeichnet, wobei die Loci

auch mit dem don`t care-Symbol ,,*" besetzt werden können.

Dieses kann dazu

benutzt werden Ähnlichkeiten zwischen verschiedenen Individuen zu zeigen. Bspw.

das Schema {00*10*} mit l = 6 verkörpert die Sequenzen {000100}, {001100},

{000101} und {001101} bei unterstellter binärer Codierung. Logischer Weise ist

die Anzahl der durch ein Schema erfassten Sequenzen umso höher, wenn mehr

don`t care-Symbole enthalten sind. Insgesamt gilt, dass ein String der Länge l bei

binärer Codierung gleichzeitig Instanz von 2

verschiedenen Schemata ist.

Dieses

bedeutet bspw., dass das Kombination {01} gleichzeitig Instanz der Schemata {01},

{*1}, {0*} und {**} ist. Weiterhin können in einer Sequenz der Länge l und der

Kardinalität k des verwendeten Alphabets insgesamt (k+1)

Schemata auftreten.

Dieses bedeutet bei binärer Codierung (2+1)

, wobei sich der Zusatz ,,+1" durch das

don´t care-Symbol erklärt.

100

101

Unter der definierten Länge eines Schemas

: ()

versteht man die Differenz der Positionen der äußeren nicht mit den don`t care-

Symbol besetzten Gene.

102

103

Im vorherigen Beispiel ist

({00*10*}) = 4. Die

Ordnung eines Schemas

104

: () bezeichnet die Anzahl an nicht mit dem don´t

care-Symbol besetzten Positionen. Im Beispiel ist

({00*10*})= 4. Das Schemata-

Theorem gibt kurz formuliert an, wie groß die Überlebenschancen von Schemata

Vgl. Feldmann (1999); S. 243.

Vgl. Goldberg (1989); S. 19-20.

Vgl. Feldmann (1999); S. 245-246.

100

Vgl. Schöneburg et al. (1994); S. 210-212; Feldmann (1999); S. 245-246.

101

Ein Beispiel: Eine Sequenz bei binärer Codierung der Länge 2 besitzt 3² = 9 potenzielle Schema-

ta: {00}; {11}; {01}; {10}; {0*}; {1*}; {*0}; {*1}; {**}.

102

Vgl. Michalewicz (1996); S. 46.

103

Ist nur eine Position von ,,*" verschiedenen ist

() = 0 per Definition. Vgl. Schöneburg et al.

(1994); S. 212; Goldberg (1989); S. 29.

104

Vgl. Schöneburg et al. (1994); S. 212.

Naturanaloge Meta-Strategien

sind.

105

Es wird angegeben, wie häufig ein Schema

im Zeitpunkt t+1 in der Fol-

gegeneration im Verhältnis zum Zeitpunkt t der aktuellen Generation in der

gesamten Population vorkommt. Die durchschnittliche Fitness der gesamten Popu-

lation zum Zeitpunkt t wird dabei mit

( )

angegeben Die mittlere Fitness der In-

dividuen, die Instanzen des Schemas

sind, oder kürzer, die mittlere Fitness des

Schemas

zum Zeitpunkt t, wird mit

( )

bezeichnet. Die auf ein Chromosom

bezogene Wahrscheinlichkeit eines crossover bzw. einer Mutation seien mit p

bzw. p

bezeichnet.

106

Das fundamentale Theorem der Genetischen Algorithmen ist

dann durch

(

) ( ) ( ) ( )

( )

107

gegeben. Die Herleitung ist in Anhang E zu finden. Die formale Darstellung der

exploitation ist dabei durch den Teil vor der eckigen Klammer gegeben, weil da-

durch das Behalten der bereits bestehenden überdurchschnittlich fitten Schemata

dargestellt wird. Die exploration wird durch die Betrachtung der Mutation und cros-

sover modelliert, weil dadurch neue Individuen aus anderen Gebieten des Lösungs-

raumes gefunden werden.

108

Einfach formuliert sagt das Theorem aus, dass Sche-

mata mit überdurchschnittlicher Fitness, kurzer definierter Länge und niedriger

Ordnung in der folgenden Generation steigende Chancen haben sich zu reproduzie-

ren, sich also (exponentiell) auszubreiten. Dieses ist bereits intuitiv zu erklären, da

zum einen fittere Individuen eher für die Rekombination verwendet werden und

andererseits die Wahrscheinlichkeit für ein Schema, dass es durch einen crossover

oder eine Mutation zerstört wird, höher ist, wenn es weiter auseinander gezogen ist

bzw. aus mehr definierten Positionen besteht.

109

Durch das Schemata-Theorem ist

gegeben, dass Befürworter der Genetischen Algorithmen ,,gezwungen" werden die

Eigenschaften der Building-Block Hypothese als positiv für Such- und Optimie-

rungsverfahren zu akzeptieren. Diese Hypothese besagt, dass das Nebeneinander-

stellen von kurzen, überdurchschnittlich fitten und von niederer Ordnung seienden

105

Vgl. Schöneburg et al. (1994); S. 214.

106

Vgl. Schöneburg et al. (1994); S. 212.

107

Vgl. Goldberg (1989); S. 33; Heistermann (1994); S. 47; Schöneburg et al. (1994); S. 214; Bäck

(1996); S. 126; Michalewicz (1996); S. 52; Dawid (1999); S. 50-52; Feldmann (1999); S. 254.

108

Vgl. Kinnebrock (1994); S. 80; Feldmann (1999); S. 251.

109

Vgl. Schöneburg et al. (1994); S. 213.

Naturanaloge Meta-Strategien

Schemata, den so genannten Building-Blocks, für Such- und Optimierungsverfah-

ren sinnvoll und in der Regel effizient ist.

110

111

Um die Sinnhaftigkeit des Vorgehens Genetischer Algorithmen zu zeigen,

verwendete John Holland eine Analogie zu einem k-armigen Banditen: einem

Spielautomaten.

112

Hierbei steht ein Spieler vor dem Dilemma, dass er das optimale

Ergebnis bei mehrmaligem Spielen an derartigen Automaten (ein Spiel ist dabei das

Ziehen an einem der Hebel) erreichen möchte, ohne dass er etwas über die durch-

schnittlichen Gewinne oder die Varianzen weiß. Es ist ihm demnach lediglich mög-

lich jeden Arm auszuprobieren. Dieses ist in dem Sinne zu verstehen, dass Schema-

ta mit den gleichen definierten Loci einen Banditen darstellen und die Anzahl an

möglichen Belegkombinationen der Variablen die Anzahl an Armen des Banditen

darstellt.

113

Jedes dieser Schemata wird implizit mit den Individuen bewertet und

verbreitet sich dann dem Schemata-Theorem entsprechend in der nächsten Genera-

tion und wird dann ggf. nochmals getestet, was einem weiteren Ziehen an dem ent-

sprechenden Arm gleich kommt. Während jeder Generation und in jedem Indivi-

duum werden mehrere Schemata getestet, also mehrere k-armige Banditenprobleme

parallel betrachtet, wodurch sich direkt der Implizite Parallelismus der Genetischen

Algorithmen zeigt. Allgemein ist zu sagen, dass zwar die Banditenprobleme simul-

tan betrachtetet, aber in unterschiedlichen Phasen des Algorithmus Banditen unter-

schiedlicher Länge bearbeitet werden. Am Anfang sind es große Längen, die durch

Operationen zerstört werden, im Verlauf setzen sich kurze Schemata durch und

werden zu Längeren, es werden also Banditenprobleme mittlerer Länge betrachtet.

Am Ende werden Banditen der vollen Länge begutachtet, wobei die kleineren Prob-

leme kaum noch Beachtung finden. Diese Analogie zeigt insgesamt, in welcher Art

und Weise Genetische Algorithmen prinzipiell vorgehen.

Die oben genannten Ergebnisse mögen theoretisch korrekt sein für diese Al-

gorithmen, für die praktische Benutzung ergeben sich nur die Probleme

114

, dass die

110

Vgl. Schöneburg et al. (1994); S. 215-216; Michalewicz (1996); S. 53.

111

Goldberg nennt in diesem Zusammenhang der schrittweisen Zusammensetzung der Lösung eine

Metapher: ,,Just as a child creates magnificent fortress through the arrangement of simple blocks of

wood, so does a genetic algorithm seek near optimal performance through the juxtaposition of short,

low-order, high-performance Schemata, or building blocks." Vgl. Goldberg (1989); S. 41.

112

Banditenproblem gesamt: Vgl. Goldberg (1989); S. 36-39; Heistermann (1994); S. 54-62.

113

Ein Beispiel: Bei den Schemata {*00**}, {*10**}, {*01**} und {*11**} sind immer die glei-

chen Positionen definiert, es wird also eine Maschine betrachtet. Es gibt bei unterstellter binärer

Codierung vier unterschiedliche Belegkombinationen, demnach hat die Maschine vier Arme.

114

Vgl. Beasley et al. (1993a); S. 65.

Details

Seiten
Erscheinungsform: Originalausgabe
Jahr: 2003
ISBN (eBook): 9783832470357
ISBN (Paperback): 9783838670355
DOI: 10.3239/9783832470357
Dateigröße: 1 MB
Sprache: Deutsch
Institution / Hochschule: Universität Bielefeld – Wirtschaftswissenschaften
Erscheinungsdatum: 2003 (Juli)
Note: 1,0
Schlagworte: börse anlagestrategien java evolution optimierungsverfahren

Autor

Markus Grabowski (Autor:in)

Genetische Algorithmen zur Findung von Trading Rules

Zusammenfassung

Leseprobe

Inhaltsverzeichnis

Details

Autor

Markus Grabowski (Autor:in)