Genetische Programme (GP)


(Contents)(Previous)(Next)

Genetische Programme sind sehr ähnlich wie genetische Algorithmen. Dabei werden lediglich die Bitstrings durch Funktionen bzw. (Unter-)Programme ersetzt. Grundgedanke ist dabei, dass zwar jedes Programm im Computer durch einen Bitstring beschrieben wird, dass es aber praktisch vernünftiger ist, die Programme über verständliche Programmiersprachen und Compiler zu erzeugen. Stellt man sich alle möglichen Programme endlicher Länge, welche in einer Programmiersprache geschrieben werden können auf, so ergibt sich einer riesige Zahl, also ein riesiger Suchraum. Die zugehörigen Bitstrings haben ebenfalls eine endliche Länge, es gibt aber viele Bitstrings derselben Länge, welche nicht durch die gewählte Programmiersprache und den entsprechenden Compiler erzeugt werden können. Die meisten dieser Bitstrings entsprechen unsinnigen Programmen, welche den Suchraum unnötig vergrössern. Durch den Übergang von GA zu GP kann man also den Suchraum eventuell drastisch verkleinern und haufenweise sinnlose Programme von vornherein ausschliessen, was natürlich die Suche beschleunigt. Man kann sagen, dass GP eine Art Vorselektion macht. Obwohl dies bei manchen Aufgaben hilfreich ist, wird dadurch die direkte Parameteroptimierung wie schon bei EP ausgeschlossen. Bei der Parameteroptimierung beinhaltet überdies meist jeder Bitstring einen möglichen Ort im Suchraum, so dass es gar keine "sinnlosen" Bitstrings gibt, welche von der Suche ausgeschlossen werden könnten.

Je nach Programmiersprache kann der Genotyp eines GP aus einem sehr langen Characterstring bestehen. Dies führt zu viel Redundanz, d.h. viele verschiedene Strings erzeugen dann dasselbe Programm, also denselben Phänotyp. Um dies zu vermeiden, beschränkt man sich normalerweise auf Formeln für den Genotyp, welche sich aus einem relativ bescheidenen Vorrat an elementaren Operatoren und Funktionen zusammensetzen lassen. Sind beispielsweise lediglich die vier Grundoperationen +,-,*,/ zugelassen, so ist f(x)=((1.2-3.8)*(x/2.5))+0.1 eine mögliche Formel. Nun wird die Architektur der Formeln gerne durch ein baumartiges Schema dargestellt. Darin entspricht jede Operation bzw. jede elementare Funktion einem Knoten, von dem eine bestimmte Anzahl Äste ausgehen. Die Anzahl Äste ist gleich der Anzahl Argumente der betreffenden elementaren Funktion. Jeder Ast führt entweder zu einem andern Knoten oder zu einem Terminalpunkt. In der obigen Formel sind die Terminalpunkte entweder vorgegebene Zahlen oder aber die Variable x. Natürlich kann man so auch kompliziertere Formeln mit mehreren Variablen erzeugen.

width="294"

Figur: Einfache Formel und zugehöriger Baum.

Wichtig ist zu bemerken, dass die Redundanz selbst bei einfachen Formeln mit kleinen Baumdarstellungen extrem gross ist. Damit ergeben sich verschiedene Probleme. Offenbar ist der Suchraum trotz allem viel grösser als nötig und das verlangsamt die Suche.

Übungsaufgabe: Suche verschiedene Bäume welche f(x)=1+x ergeben, wenn die Bäume bis zu 3 Knoten haben dürfen.

Ein womöglich gravierenderes Problem ergibt sich aus der Tatsache, dass der GP Suchraum normalerweise sehr ungeordnet ist bzw. sich schlecht ordnen lässt. So können sehr verschiedenartige Formeln d.h. Individuen mit sehr unterschiedlichem Genotyp, zu ähnlichen oder gar identischen Resultaten führen, d.h. der Phänotyp der entsprechenden Individuen ist kaum oder gar nicht unterscheidbar. Andererseits bringt eine Nachbarschaft des Genotyps keine Nachbarschaft des Phänotyps mit sich. Angesichts dieser unangenehmen Struktur des Suchraums ist es schon fast erstaunlich, dass ein Suchalgorithmus deutlich effizienter als die reine Zufallssuche sein kann.

Übungsaufgabe: Konkretisiere das GP Verfahren in Analogie zu GA. Beantworte insbesondere folgende Fragen: Wie können zwei Eltern Kinder zugeordnet werden? Welche Arten der Mutation gibt es?

Übungsaufgabe: Da GP für die Parameteroptimierung schlecht geeignet ist, wende man GP auf das Problem der symbolischen Regression einer gegebenen Funktion f(x) an. Dabei ist f(x) in I Punkten f(xi) gegeben. Gesucht ist eine möglichst einfache Formel fk(x), für welche fk(xi)=f(xi)+ei gilt. Dabei soll die Norm des Fehlervektors e mit den Komponenten ei minimiert werden. Welche Definition der Fitness ist wohl sinnvoll? Welche elementaren Funktionen oder Operatoren sollen verwendet werden?

Übungsaufgabe: Überlege was bei der symbolischen Regression passiert, wenn die Werte f(xi) fehlerbehaftete Messwerte sind.

Ein wichtiges Problem bei GP ist, dass die von GP erzeugten Funktionen nicht immer numerisch ausgewertet werden können, z.B. wenn sich bei der Auswertung eine Division durch Null ergibt. Damit dies zu keinem Programmabbruch führt, müssen alle elementaren Operationen und Funktionen sehr robust implementiert werden. Dabei kann man gezwungen sein Fehler in Kauf zu nehmen und beispielsweise immer dann wenn eine numerische Auswertung unmöglich ist, einfach willkürliche Werte zuzuweisen.

Übungsaufgabe: Ein typisches Beispiel einer nicht immer numerisch auswertbaren Operation ist die Division a/b. Wann ergeben sich numerische Probleme? Wie lassen sich diese (unter Verzicht auf „richtige" Resultate) vermeiden?


(Contents)(Previous)(Next)