Die Macht und Grenzen genetischer Algorithmen verstehen

An diesem Punkt unserer Serie zur genetischen Programmierung (GP) haben wir gelernt, was genetische Programmierung ist und wie sie Informationen repräsentiert, wie genetische Operatoren in evolutionären Algorithmen funktionieren, und wir haben die Evolution eines Sortierprogramms durch symbolische Regression durchgearbeitet.

Hier betrachten wir aus übergeordneter Perspektive, was diese Technologie bei ihrer Weiterentwicklung leisten kann.

Praktische Aspekte der genetischen Programmierung

Erinnern wir uns an das XOR-Beispiel aus dem ersten Teil der Serie:

Eine perfekte Lösung für das XOR-Problem, entdeckt durch GP:
(defun program ()
  (AND (OR X1 X2)
  (NOT (AND X1 X2) )
  )
)

Betrachten wir auch das Beispiel der symbolischen Regression aus dem vorherigen Artikel:

Eine Polynomapproximation von sin(x) im Intervall (0 ≤ x ≤ π/2)

(defun program ()
  (+ (* (* (* X X) X)
  (* 0.2283 -0.6535))
  X)
)

Vereinfacht ergibt sich folgende äquivalente Gleichung:

polysin(x) = -0.1492 x³ + x

Ergebnisse:

Sowohl das XOR- als auch das symbolische Regressionsbeispiel liefern bei der Auswertung einen einzelnen Rückgabewert.

Dies muss keine Einschränkung darstellen, da eine Funktion oder ein Terminal bei der Ausführung sehr wohl Nebeneffekte haben kann. Dies ist beim Sortierprogramm der Fall, das eine Funktion mit dem potenziellen Nebeneffekt des Austauschs eines Elementpaars in einem Vektor enthält. In der Praxis sind Nebeneffekte häufig. Weitere nützliche Beispiele sind die Zuweisung einer Variablen an eine andere oder die Änderung der Blickrichtung eines Roboters.

Unser Funktionssatz kann bedingte Funktionen umfassen, die den evolvierten Programmen Entscheidungsfähigkeit verleihen. Bedingte Funktionen evaluieren ihre Argumente selektiv. Beispiel: Eine Funktion mit Arity drei wie (if arg1 arg2 arg3) evaluiert das erste Argument; ist das Ergebnis wahr, wird das zweite Argument evaluiert, andernfalls das dritte. Iterative Konstrukte sind ebenfalls möglich, da eine Funktion eines ihrer Argumente mehrfach evaluieren kann. Zusätzliche Komplexität entsteht durch die Notwendigkeit, Iterationsanzahl und Verschachtelungstiefe zu begrenzen, um übermäßig lange Evaluierungen zu vermeiden. Rekursive Formulierungen wurden ebenfalls erforscht, der Erfolg war jedoch begrenzt.

Obwohl GP-Systeme tendenziell LISP-ähnliche Programme liefern, muss ein GP-System nicht in LISP implementiert sein. Viele Systeme nutzen C oder C++. Eine linearisierte Darstellung des Programmbaums kann eingesetzt werden, um den Overhead von dynamischem Speicher und teurer Garbage Collection zu vermeiden. Der Effizienz der Fitness-Funktion kommt besondere Aufmerksamkeit zu, da sie oft ein Flaschenhals ist – sie wird in jeder Generation sehr häufig aufgerufen. Ein hervorragendes Papier zu Implementierungstechniken findet sich in Advances in Genetic Programming (siehe Literaturhinweise).

Wie bei anderen Machine-Learning-Paradigmen – etwa neuronalen Netzen – besteht die Gefahr des Overfittings an den Trainingsdaten (GP-Testfällen). Overfitting tritt auf, wenn die Lösung die Daten effektiv „auswendig lernt“ und kaum mehr als eine aufwendige Lookup-Tabelle darstellt. Eine einfache Gegenmaßnahme ist der Parsimoniefaktor: ein kleiner Bruch, multipliziert mit der Knotenzahl im Programmbaum, der in die Fitness-Funktion einfließt. Die Idee: kleinere, vermutlich allgemeinere Lösungen werden belohnt. Zudem sollten geeignete Experimentaldesign-Techniken angewendet werden – etwa die Beschränkung der Fitness-Evaluation auf einen Teil der verfügbaren Daten bei Vorhersagemodellen, um die verbleibenden Daten zur Messung der Vorhersageleistung zu nutzen.

Wie bei evolutionären Algorithmen gibt GP keine Garantie für eine exakte oder auch nur akzeptable Lösung. Die Ergebnisse können von Lauf zu Lauf stark variieren. Oft konvergiert der Prozess vorzeitig in ein lokales Minimum. Die Performance hängt stark von der Problemkomplexität, seiner Repräsentation (Wahl von Funktionen und Terminals) und den Eigenschaften der Fitness-Funktion ab.

Anwendungsgebiete der genetischen Programmierung

Genetische Programmierung wurde erfolgreich auf Probleme in folgenden Bereichen angewendet:

• Schaltkreisentwurf
• Kombinatorische Optimierung
• Regelsysteme
• Kurvenanpassung / Regressionsanalyse
• Datenkompression
• Wirtschaftsprognosen / Finanzmodellierung
• Erwerb von Spielstrategien
• Mathematische Folgeninduktion
• Neuronales Netzdisign
• Mustererkennung und Klassifikation
• Zufallszahlengenerierung
• Roboter-Navigation
• Symbolische Integration und Differentiation
• Dreidimensionales Design

Zukünftige Entwicklungsrichtungen

Je nach Problemkomplexität können mehrere GP-Läufe nötig sein, um eine akzeptable Lösung zu finden – falls überhaupt eine gefunden werden kann. Idealerweise sollte GP mit wachsender Problemkomplexität „skalieren“. Gute Wege hierfür zu finden, ist ein aktives Forschungsfeld. Wie in der konventionellen Programmierung ist der Aufbau höherer Repräsentationen durch Subroutinen ein Ansatz. In Genetic Programming II diskutiert Koza Methoden zur Entdeckung wiederverwendbarer Subroutinen und präsentiert Ergebnisse, die die Fähigkeit hierarchischer, modulärer Programme zur Lösung komplexerer Probleme belegen.

Wie wir gesehen haben, koppelt GP die selbstorganisierenden Eigenschaften genetischer Algorithmen mit der Repräsentationskraft und Allgemeingültigkeit von S-Ausdrücken. Die Eleganz dieses Ansatzes vereinfacht die Problemspezifikation auf die Bereitstellung einer domänenspezifischen Fitness-Funktion und eines geeigneten Funktions- und Terminalsatzes. GP ist auf eine Vielzahl von Problemen anwendbar und bleibt ein fruchtbares Forschungsfeld.

Noch in den Kinderschuhen steckend, könnten zukünftige Durchbrüche uns einen Schritt näher an den „Heiligen Gral“ bringen: Systeme, die ihre eigenen Programme schreiben können.

Weiterführende Literatur

• Kinnear, Jr., K. E. (Hrsg.). Advances in Genetic Programming. Cambridge, Mass.: The MIT Press, 1994.
• Knuth, D. E. The Art of Computer Programming, Volume 3, Sorting and Searching. Reading, Mass.: Addison-Wesley, 1973.
• Koza, J. R. Genetic Programming. Cambridge, Mass.: The MIT Press, 1992.
• Koza, J. R. Genetic Programming II. Cambridge, Mass.: The MIT Press, 1994.
• Montana, D. J. „Strongly Typed Genetic Programming.“ BBN Technical Report #7866, Mai 1993.
• Mitchell, Melanie, An Introduction to Genetic Algorithms, The MIT Press, 1998.