Genetische Programmierung

Die Genetische Programmierung (GP) ist wie der Genetische Algorithmus (GA) und die Evolutionsstrategie (ES) ein heuristisches Optimierungsverfahren und gehört in die Klasse der Evolutionären Algorithmen (EA).

GP wird wie andere EA verwendet, um Probleme zu lösen, die auf klassischem Wege nicht oder nur schwer lösbar sind, etwa wegen hoher Komplexität, Nichtlinearität oder zu großem Suchraum. Wie in EA üblich, werden nach dem Vorbild der biologischen Evolution vom Algorithmus initiale Individuen erzeugt, welche eine mögliche Lösung für das bearbeitete Problem darstellen und im folgenden problemspezifisch durch Bewertung, Selektion und Variation verbessert werden. Im Gegensatz zu GA und ES wird ein Individuum als eigenes Programm interpretiert, als Suchraum dient ein Raum ganzer Programme. Einerseits ist dieser Ansatz allgemeiner als bei anderen evolutionären Algorithmen, da weniger Annahmen über die potentielle Lösung vorweg genommen werden, andererseits ist jedoch die Größe des Suchraums in der Regel weit größer.

Eine typische Anwendung von GP ist die symbolische Regression. Im Gegensatz zu den klassischen Formen der Regression, wie etwas lineare oder logistische, kann die symbolische Regression für Probleme unbekannter Form eingesetzt werden. So können mittels GP Funktionen für die näherungsweise Lösung von Problemen gefunden werden, für die es keine analytische Lösung gibt, wie z.b. der Bewertung von amerikanischen Put-Optionen.

Die zwar nicht erste, aber grundlegende Arbeit zu GP verfasste John Koza. Als Individuen verwendete er Programme in der syntaktisch einfachen funktionalen Programmiersprache LISP, die in einer Baumstruktur vorliegen. Bei anderen Ansätzen wird auf linearen Programmen (z. B. direkt auf Assembler) oder Graphen operiert. Zuletzt wurden diese Möglichkeiten auch zu den so genannten Linear-Graphen-GP kombiniert.

Literatur

• John R. Koza: Genetic Programming.
• Riccardo Poli, William B. Langdon: Foundations of Genetic Programming.
• Christian Keber: Option Valuation with the Genetic Programming Approach

Siehe auch

• Optimierungsproblem

Weblinks

• http://www.genetic-programming.com
• JAGA - Flexible und erweiterbare Open-Source API für Erstellung von Java-Anwendungen, die auf Genetischer Programmierung oder auf Genetischen Algorithmen basieren. Enthält viele Beispiele und Analysewerkzeuge. (www.jaga.org)
• [1] Genetische Programmierung einer Turingmaschine Umfangreicher, gut dokumentierter Sourcecode mit ausführlicher Dokumentation(SOURCE+PDF+TEX, Tar.gz)
• DGPF einfaches Framework für Genetische Programmierung (Java, LGPL)
• JGAP Open-Source Java-Framework, das sowohl Genetische Programmierung als auch Genetische Algorithmen unterstützt