Die vorgestellte Applikation nutzt genetische Algorithmen zur Approximation von Funktionen. Es wird dabei das sog. "Gene Expression Programming" - Verfahren angewendet. Es zeichnet sich dadurch aus, dass es kaum Einschränkungen bei den zu generierenden Funktionen gibt. Die Besonderheit dabei ist die lineare Codierung der Individuen in den Chromosomen. Diese lineare Codierung wird bei der Interpretierung der Chromsomen in eine Baumstruktur überführt, die besonders gut zur Darstellung von mathematischen Formel geeignet ist.

Im folgenden wird nähre auf den benutzten Algorithmus eingegangen und es wird erklärt, wie Kreuzung, Mutation und Rekombination realisiert wird.
Der "Gene Expression Programming" - Ansatz (im folgenden kurz: GEP) wurde erstmals von Angra do Heroismo, Portugal vorgestellt. GEP nutzt lineare Gene, die durch Zeichensequenzen repräsentiert sind und in Head und Tail unterteilt sind.

• Organisation und Aufbau des Genoms:
  Das Genom besteht aus einer festen Länge von Zeichen, die ein oder mehrere Gene repräsentieren. Trotz dieser festen Länge der Gene, wird später schnell klar werden, das die erzeugten Phänotypen durchaus in Länge und Struktur variieren können. Ein Beispiel soll den Aufbau von Genotyp und Phänotyp erklären:
  
  
  Als Ausgangspunkt dient die Formel:
  
  Diese Formel kann auch als Baum dargestellt werden ("Q" repräsentiert die Quadratwurzel):
  
  Diese Formel läßt sich leicht in den Genotyp übersetzen:
  
  01234567
Q*+-abcd

  Diese Darstellungsform läßt sich durch einfaches Lesen des Funktionsbaumes von links nach rechts und von oben nach unten ereichen ("breadth first enumeration" des Baumes). Der Vorteil dieser Darstellungsform liegt auf der Hand: Er läßt sich als lineare Zeichenkette darstellen und ist bestens zum Einsatz in genetischen Algorithmen geeignet.
  
• Länge des Genoms:
  Wie schon weiter oben erwähnt, besteht ein Gen aus Head und Tail. Im Head wird die Funktion und die Struktur der generierten Formel beschrieben und im Tail werden Konstanten hinterlegt. Die benötigte Länge des Tails läßt sich mit der Formel
  
  t = h * ( n - 1 ) + 1
  
  berechnen. Dabei ist:
  
  • t... die Länge des Tails
    
  • n... die Anzahl der Argumente der Funktion, die die meisten Argumente hat
    
  • h... die Länge des Head
    
    
• Mutation, Rekombination und Kreuzung:
  Die genetischen Operatoren funktionieren wie üblich. Es ist nur nur zu beachten, dass sich im Head nur Variable und Funktionen und im Tail nur Konstanten befinden. Wird diese Regel eingehalten, so werden auch immer mathematisch korrekte Funktionen generiert.
  
  
• Weitergehende Informationen:
  Eine detailierte Beschreibung, sowie weitere Variationen des Gene Expression Programming befinden sich auf http://www.gene-expression-programming.com.
  

Das Programm gliedert sich in 3 Bereiche:

• Berechnung & Resultat

In diesem Bereich kann die Berechnung gestartet werden. Nach jeweils 5 Generationen erfolgt eine Ausgabe der besten Individuen, der benötigten Rechenzeit, der Mittleren Fitness, sowie der Summierten Fitness aller Individuen. Auf der linken Seite des befinden sich 2 Buttons. Der obere Button öffnet ein Fenster das die aktuell zu approximierende Funktion sowie das beste Individuum anzeigt. Der untere Button öffnet ein Fenster in dem die Individuen graphisch dargestellt werden. Bei der graphischen Darstellung der Individuen ist gut zu sehen das diese sich im Anfang sehr stark unterscheiden und gegen mit fortschreitender Evolution immer mehr einander angleichen und nur noch in wenigen Punkten variieren.


• Settings

In diesem Fenster lassen sich diverse Parameter einstellen. Im Abschnitt Operatoren, sowie im Abschnitt Funktionen läßt sich eine Auswahl an Funktionen und Operatoren treffen, die dem genetischen Algorithmus zur Generierung von Funktionen zur Verfügung stehen. Es ist zu beachten, das eine Begrenzung der Funktionen die Lösungsfindung extrem beschleunigen kann und meistens zu besseren und genaueren Ergebnissen führt.
Im Abschnitt Wahrscheinlichkeiten lassen sich die üblichen Wahrscheinlichkeiten für Genetische Algorithmen einstellen. Die Prozentwerte für Operatoren, Funktionen, Variablen und Kosntanten müssen in der Summe 1.0 ergeben. Sie bestimmen die Wahrscheinlichkeit mit der Operatoren, Funktionen usw. erzeugt werden. Über diese Werte läßt sich also die grobe Struktur (d.h. die Verhältnisse zwischen den elementaren Bestandteilen) der erzeugten Formeln einstellen.
• Eingabe Fitnesswerte

In diesem Fenster läßt sich die zu approximierende Funktion angeben. Nach Eingabe der Funktion in der oberen Textbox und Bestätigung der Funktion mit <>, erscheint diese im unteren Koordinatensystem. Wird die Funktion nicht dargestellt, so ist ein Fehler vorhanden. Erlaubt sind alle Grundrechenarten, alle üblichen Funktionen (sqrt, sin, cos, ...), sowie Konstanten und die Variable x.
Nachdem die Funtion dargestellt wurde, lassen sich mit Mausklick die Punkte setzen, die zur Fitnessberechnung eingesetzt werden. Danach muss der Button <> geklickt werden um die Punkte zu bestätigen.

Gute Beispiele sind z.B. folgende Funktionen
• -(x*x*x*x-2*x*x*x-14*x*x)/4
• x*x*x*x-7*x*x*x-14*x*x
• sin(x)*cos(x)*x*10

Die Approximation funktioniert umso besser, je mehr Beispielpunkte gegeben sind. Außerdem lohnt es sich, die zur Verfügung stehenden Funktionen und die Länge der Chromosomen zu variieren.