Eine Einführung in die genetische Programmierung:Ein System, das sich selbst programmiert?

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 Paradigma des maschinellen Lernens, das einen Schritt in diese Richtung darstellt.

GP verspricht viel im Bereich der Regelungstechnik. In diesem Artikel besprechen wir, was genetische Programmierung ist, wie sie dargestellt werden kann, und werfen einen Blick auf ein Beispielprogramm.

Dieser Artikel ist der erste einer Reihe. Um zu den nächsten Einträgen zu springen, wählen Sie unten einen aus:

• Genetische Operatoren in evolutionären Algorithmen
• Beispiele für genetische Algorithmen:Entwicklung eines Sortierprogramms und symbolische Regression
• Anwendungen und Grenzen der genetischen Programmierung

Genetische Programmierung und genetische Algorithmen

GP ist im Wesentlichen eine Variation des genetischen Algorithmus (GA), der ursprünglich von John Holland entwickelt wurde. Wie ein GA ist GP ein evolutionärer Algorithmus, der sich auf genetische Operatoren wie fitnessproportionale Reproduktion, Crossover und Mutation stützt, um eine Population codierter Programme oder "Individuen" durch aufeinanderfolgende Generationen zu einer Lösung zu führen.

Im Gegensatz zu einem GA, der typischerweise eine Bitkettencodierung mit fester Länge verwendet, verwendet GP jedoch eine baumbasierte Darstellung eines tatsächlichen Programms mit variabler Größe. Daher erzeugt das Ergebnis eines erfolgreichen GP-Laufs ein Computerprogramm, das bei entsprechender Eingabe und Ausführung das gewünschte Ergebnis liefert.

Nichael Cramer und John Koza wird zugeschrieben, den Grundstein für GP gelegt zu haben. John Koza (der auch ein Patent auf GP hält) hat eine beträchtliche Menge an Forschungen über GP betrieben und sein wegweisendes Buch "Genetic Programming" gilt als das wegweisende Werk zu diesem Thema. Aktuelle Forschungen haben einige ermutigende Erfolge der GP in einer Vielzahl von Anwendungen gezeigt, darunter Roboternavigation, Erlangung von Spielstrategien, symbolische Regressionsanalyse und Kontrollsysteme.

Darstellung der genetischen Programmierung

Die zuvor erwähnte baumbasierte Darstellung ist für das GP-Thema von zentraler Bedeutung, da praktisch jedes Computerprogramm auf diese Weise dargestellt werden kann. In der Praxis ist eine funktionale Sprache wie LISP für diese Form gut geeignet, und es ist leicht zu erkennen, wie ein LISP-S-Ausdruck als Baum dargestellt werden kann (Abbildung 1).

Unten finden Sie drei separate Darstellungen derselben Informationen:

Ein einfaches Programmfragment: START WENN a LISP-Äquivalent: (progn (wenn (a  

 
 

 
 
Abbildung 1. Baumdarstellung eines Programms. Beachten Sie, dass (progn arg1 arg2 arg3 ... argn) jedes Argument sequentiell auswertet.  
 

 
 

 Die inneren Knoten des Baums bestehen aus Funktionen, während die Blattknoten aus Terminals bestehen. Funktionen müssen eine Argumentanzahl (allgemein als arity bezeichnet) von mindestens 1 haben, damit sie mit anderen Funktionen oder Terminals verbunden werden können und so den "Klebstoff" für Zweige innerhalb des Baums bereitstellen.
 

 Terminals enthalten normalerweise solche Dinge wie Konstanten und Variablen. Da Terminals die Blätter des Baumes bilden, haben sie immer eine Stelligkeit von Null. Sie müssen den Satz von Funktionen und Terminals für das Problem auswählen, das Sie lösen möchten. Beispielsweise sind die logischen Funktionen AND, OR und NOT sowie die Klemmen X1 und X2, die zwei boolesche Eingangsvariablen darstellen, geeignet, wenn Sie versuchen, ein Programm zu finden, das die boolesche Funktion XOR synthetisieren kann. Eine Fitnessfunktion ist auch erforderlich, da Sie die Mittel bereitstellen müssen, damit ein Programm mit einem anderen in dem Sinne gemessen werden kann, dass eines ein bestimmtes Problem besser löst.
 

 Im XOR-Fall können wir beispielsweise die Fitness eines Programms testen, indem wir das Programm einmal für jeden Fitnessfall ausführen, der den vier möglichen booleschen Eingaben für X1 und X2 (0 0, 0 1, 1 0, 1 1) und entspricht Addieren der Anzahl der richtigen Antworten (0, 1, 1, 0) für jeden Testfall. 
 

 Offensichtlich gilt ein Programm, das eine perfekte Punktzahl von vier liefert, als Lösung des XOR-Problems, wie in Listing 1 gezeigt.
 

 
 
Eine perfekte Lösung für das von GP entdeckte XOR-Problem: (Definiertes Programm () (UND (ODER X1 X2) (NICHT (UND X1 X2) ) ) ) 
 
Auflistung 1.  XOR-Ergebnis 
 

 
 
Weiter:Genetische Operatoren
 

 Im nächsten Artikel werfen wir einen Blick auf die genetischen Operatoren, die evolutionäre Algorithmen ermöglichen. Wir werden sie auch in einem komplexeren Beispielalgorithmus verwenden.
 

 
 
Empfohlene Lektüre
 
 
Kinnear, Jr., K. E. (Hrsg.). Fortschritte in der genetischen Programmierung . Cambridge, Massachusetts:The MIT Press, 1994.
 
Knuth, D. E. Die Kunst der Computerprogrammierung, Band 3, Sortieren und Suchen . Reading, Massachusetts:Addison-Wesley, 1973
 
Koza, J. R. Genetische Programmierung . Cambridge, Massachusetts:The MIT Press, 1992.
 
Koza, J. R. Genetische Programmierung II . Cambridge, Massachusetts:The MIT Press, 1994.
 
Montana, D. J. „Stark typisierte genetische Programmierung“. BBN Technischer Bericht #7866, Mai 1993.
 
Mitchell, Melanie, Eine Einführung in genetische Algorithmen , The MIT Press, 1998.
 
 

            


            

               Beurteilung von Buzzwords:Digitale Transformation        
                So entwerfen Sie einen Fuzzy-Logic-Controller