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).

Die Genetische Programmierung wird wie andere Evolutionäre Algorithmen 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 bei Evolutionären Algorithmen üblich, werden nach dem Vorbild der biologischen Evolution 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 Genetischen Algorithmen und der Evolutionsstrategie 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 vorweggenommen werden, andererseits ist jedoch die Größe des Suchraums in der Regel weit größer.

Eine typische Anwendung der Genetischen Programmierung ist die symbolische Regression. Im Gegensatz zu den klassischen Formen der Regression, wie etwa lineare oder logistische, kann die symbolische Regression für Probleme unbekannter Form eingesetzt werden. So können mittels Genetischer Programmierung 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 zur Genetischen Programmierung verfasste John Koza. Als Individuen verwendete er Programme in der syntaktisch einfachen 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 in der so genannten Linear-Graphen-GP auch kombiniert.

Literatur

• John R. Koza: Genetic Programming. On the Programming of Computers by Means of Natural Selection, The MIT Press 1992, ISBN 0-262-11170-5
• Wolfgang Banzhaf, Peter Nordin, Robert E. Keller, Frank D. Francone: Genetic Programming - An Introduction
• William B. Langdon, Riccardo Poli: Foundations of Genetic Programming.
• Riccardo Poli, William B. Langdon, Nicholas Freitag McPhee (2008): A Field Guide to Genetic Programming, freely available via Lulu.com.
• Christian Keber: Option Valuation with the Genetic Programming Approach
• Thomas Weise: Global Optimization Algorithms - Theory and Application

Siehe auch

• Optimierungsproblem

Weblinks

• http://www.genetic-programming.com
• Genetische Programmierung einer Turingmaschine, Studienarbeit zum Thema Genetische Programmierung an der HTW Dresden
• JGAP Open-Source Java-Framework, das sowohl Genetische Programmierung als auch Genetische Algorithmen unterstützt
• ECJ A Java-based Evolutionary Computation Research System (ähnlich JGAP) By Sean Luke, Liviu Panait, Gabriel Balan, Sean Paus, Zbigniew Skolicki, Elena Popovici, Keith Sullivan, Joseph Harrison, Jeff Bassett, Robert Hubley, and Alexander Chircop