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.
Bei der Genetischen Programmierung (GP) handelt es sich um einen Algorithmus aus der Familie der Evolutionären Algorithmen. In der Natur hat sich die Evolution als sehr erfolgreiches System zur Weiterentwicklung und Optimierung aller Lebewesen erwiesen. Evolutionäre Algorithmen bilden mittels einfacher Modelle die wesentlichen erfolgreichen Merkmale des natürlichen evolutionären Prozesses nach. Sie ermöglichen dadurch, auch bei Problemen mit großem Suchraum mit relativ geringem Aufwand gute Lösungen zu finden. Datenstrukturen und Algorithmen werden durch die Evolutionären Algorithmen erzeugt und optimiert, um gegebene Probleme zu lösen. Diese Einfü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.
Die Individuen, die während der GP evolutionär entwickelt werden, sind Programme. Diese Programme sind aus Funktionen und Terminalen aufgebaut (vgl. (BNKF98, S. 109-118)).
Die Wahl der verwendeten Funktionen innerhalb eines genetischen Programms hängt vom jeweiligen Anwendungsgebiet ab. Eine wesentliche Anforderung 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 Anwendungsproblem zusammensetzen lässt. Um den Suchraum nicht unnötig zu vergrößern, sollten jedoch nicht zu viele Funktionen zur Verfügung gestellt werden. Wie auch Banzhaf et al. in (BNKF98, S. 111f) bemerken, ist es nicht sinnvoll, gleich zu Beginn einer Anwendung exakt auf das gegebene Problem zugeschnittene Funktionen zu entwickeln. Da GP sehr kreativ in der Kombination von Funktionen ist, kann es bereits ausreichend sein, einfache Funktionen wie die Boolschen und Arithmetischen Funktionen zur Verfügung zu stellen, um erstaunliche Resultate zu erzielen.
Die Argumente der verwendeten Funktionen sind die Terminale. Sie bestehen zum einen aus den Eingabedaten, mit deren Hilfe das System trainiert, zum anderen aus Konstanten, die im Laufe der Evolution verändert werden. Diese Konstanten nennt man „ephemeral random constants" (ERC) (vgl. (Koz92, S. 242f)).
Die Abgeschlossenenheit der Funktionen bezüglich der Terminale ist wesentliche Voraussetzung für das fehlerfreie Ablaufen der erzeugten Programme. Die verwendeten Funktionen müssen so entworfen sein, dass sie mit allen möglichen Eingabewerten zurechtkommen, z.B wird häufig die Division angepasst, damit das Programm nicht bei Divisionen durch Null beendet wird. Damit festgelegt ist, in welcher Reihenfolge die Funktionen eines Programms ausgewertet werden, werden die Funktionen und Terminale eines Programms in einer entsprechenden Datenstruktur gespeichert. Am häufigsten werden hierzu Bäume verwendet. Aber auch lineare Strukturen sowie allgemeine Graphen werden als Organisationsform verwendet.
Im Fall von Bäumen ist die übliche Reihenfolge der Evaluation von links nach rechts: Es wird der am weitesten links im Baum stehende Knoten ausgeführt, für den alle Eingaben zur Verfügung stehen.
Der prominenteste Vertreter einer linearen Strukturierung der Funktionen und Terminale ist die Simulation einer Registermaschine. Sie verfügt über mehrere Register, einen linearen Speicher für Zuweisungen von Terminalen an die Register sowie Funktionen, welche die Register für Ein-/Ausgabe verwenden. Eine relativ neue Variante der Strukturierung sind gerichtete Graphen, die Zyklen 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.
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" bezeichnet. 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 maximaler Tiefe angelegt, bei dem alle Knoten zufällig aus der Menge der Funktionen gewählt werden bis auf die Knoten maximaler Tiefe, die zufällig aus der Menge der Terminale gewählt werden. Bei der Methode „Growth" wird der Baum von der Wurzel her aufgebaut, wobei für jeden Knoten zufällig ein Element aus Funktion bzw. Terminal ausgewählt wird. Wird ein Terminal gewählt, ist der Aufbau für diesen Ast beendet und es wird beim letzten Knoten des Astes fortgefahren, der kein Terminal ist. Für die Knoten der maximalen Tiefe des Baumes wird die zufällige Auswahl auf die Menge der Terminale eingeschränkt.
Um eine möglichst hohe Vielfalt innerhalb der Population zu erreichen, werden die beiden beschriebenen Aufbauverfahren häufig kombiniert angewandt. 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.
Die Genetischen Operatoren sind die Werkzeuge, die dem Evolutionären Algorithmus zur Verfügung stehen, um die Fitness der Population im Laufe der Evolution zu verbessern. Die am häufigsten verwendeten Operatoren sind Crossover, Mutation und Reproduktion. Der einfachste Operator ist die Reproduktion, der abhängig von der Fitness ein Individuum selektiert und eine identische Kopie in die nächste Generation überträgt. Der Crossover Operator kombiniert das genetische Material von zwei Individuen miteinander, indem er Teilbäume gegeneinander austauscht und so zwei neue Individuen erzeugt. Häufig geschieht dies so, dass Funktionen mit einer höheren Wahrscheinlichkeit ausgewählt werden als Terminale. Auch die Erzeugung nur eines Nachkommen 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 Individuen
Self Crossover: Austausch von Unterbäumen innerhalb eines Individuums
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.
In Anlehnung an die in der natürlichen Evolution stattfindende Auslese findet in der GP ein Selektionsprozeß anhand eines Fitnesswertes statt, der jeweils einem Individuum der Population zugeordnet ist. Der Fitnesswert eines Individuums wird durch die Evaluation des Individuums durch die Fitnessfunktion ermittelt. Hierzu wird meist das genetische Programm des Individuums mit Eingaben aus einem Trainingsdatensatz ausgeführt und aufgrund der Ausgabe des...
