Genetische Programmierung erklärt: Wie Maschinen lernen, ihren eigenen Code zu schreiben

Vielleicht wird der „Heilige Gral“ der Informatik an dem Tag entdeckt, an dem unsere Maschinen ihre eigenen Programme schreiben können. Genetische Programmierung (GP) ist ein relativ neues Machine-Learning-Paradigma, das einen Schritt in diese Richtung darstellt.

GP hält großes Versprechen im Bereich der Regelungstechnik. In diesem Artikel besprechen wir, was genetische Programmierung ist, wie sie repräsentiert werden kann, und schauen uns ein Beispielprogramm an.

Dies ist der erste Artikel einer Serie. Um zu den nächsten Einträgen zu springen, wählen Sie unten:

• Genetische Operatoren in evolutionären Algorithmen
• Genetische Algorithmen-Beispiele: Evolution eines Sortierprogramms und symbolische Regression
• Anwendungen und Limitationen der genetischen Programmierung

Genetische Programmierung und genetische Algorithmen

GP ist im Wesentlichen eine Variation des genetischen Algorithmus (GA), ursprünglich von John Holland konzipiert. Wie ein GA ist GP ein evolutionärer Algorithmus, der auf genetischen Operatoren wie fitness-proportionaler Reproduktion, Crossover und Mutation basiert, um eine Population kodierter Programme – „Individuen“ – über successive Generationen hin zu einer Lösung zu treiben.

Im Gegensatz zu einem GA, der typischerweise eine festlange Bitstring-Kodierung nutzt, verwendet GP eine variabel große, baumbasierte Repräsentation eines tatsächlichen Programms. Daher produziert ein erfolgreicher GP-Lauf ein Computerprogramm, das bei gegebener Eingabe und Ausführung das gewünschte Ergebnis liefert.

Nichael Cramer und John Koza werden die Grundlagen der GP zugeschrieben. John Koza (der auch ein Patent auf GP hält) hat umfangreich zu GP geforscht; sein Standardwerk „Genetic Programming“ gilt als das grundlegende Werk zum Thema. Aktuelle Forschung zeigte ermutigende Erfolge von GP in vielfältigen Anwendungen: Roboter-Navigation, Erwerb von Spielstrategien, symbolische Regressionsanalyse und Regelsysteme.

Genetische Programmierung Repräsentation

Die oben erwähnte baumbasierte Repräsentation ist zentral für GP, da praktisch jedes Computerprogramm so dargestellt werden kann. In der Praxis eignet sich eine funktionale Sprache wie LISP gut dafür, und man sieht leicht, wie ein LISP S-Ausdruck als Baum diagrammiert werden kann (Abbildung 1).

Im Folgenden finden Sie drei separate Repräsentationen derselben Information:

Ein einfaches Programmfragment:
BEGIN
IF a < b THEN a := a + 1 ELSE b := b * b
c := a * b * 2;
END


LISP-Äquivalent:
(progn (if (a < b)
  (setq a (+ a 1))
  (setq b (* b b))
  )
  (setq c (* (* a b) 2))
)

Die inneren Knoten des Baums bestehen aus Funktionen, die Blattknoten aus Terminals. Funktionen müssen eine Argumentanzahl (Arity) von mindestens eins haben, wodurch sie mit anderen Funktionen oder Terminals verbunden werden können – sie bilden den „Kleber“ für Zweige im Baum.

Terminals umfassen typischerweise Konstanten und Variablen. Da Terminals die Blätter des Baums bilden, haben sie immer eine Arity von null. Sie müssen den Satz an Funktionen und Terminals für das zu lösende Problem wählen. Beispiel: Die logischen Funktionen AND, OR, NOT und die Terminals X1, X2 (zwei boolesche Eingabevariablen) sind geeignet, wenn Sie ein Programm entdecken wollen, das die XOR-Boolesche Funktion synthetisieren kann. Eine Fitness-Funktion ist ebenfalls erforderlich, da Sie die Mittel bereitstellen müssen, um ein Programm gegenüber einem anderen zu messen – im Sinne, dass eines besser ein gegebenes Problem löst.

Im XOR-Fall könnten wir die Fitness eines Programms testen, indem wir es einmal für jeden Fitness-Fall ausführen, der den vier möglichen booleschen Eingaben für X1 und X2 entspricht (0 0, 0 1, 1 0, 1 1), und die Anzahl korrekter Antworten (0, 1, 1, 0) für jeden Testfall aufsummieren.

Offensichtlich gilt ein Programm mit perfektem Score von vier als Lösung des XOR-Problems, wie in Listing 1 gezeigt.

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

Nächster Schritt: Genetische Operatoren

Im nächsten Artikel schauen wir uns die genetischen Operatoren an, die evolutionäre Algorithmen möglich machen. Wir werden sie auch in einem komplexeren Beispielalgorithmus einsetzen.

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.