Grundlagen
Genetic Programming
Norbert Bartos
bartos@email.tgm.ac.at
Genetic Programming
Norbert Bartos
Seit kurzer Zeit sind auf Tagungen des Fachbereiches der „Artificial Intelligence“ vermehrt Beiträge aus dem Gebiet des „Genetic Programmings“ zu finden. Dabei geht es um das automatische, evolutionäre Erstellen von Programmen durch Computer. Es ist dies eine Teildisziplin des „Machine Learning“ und reicht in seinen Wurzeln bis 1958 zurück. Damals hat R.Friedberg einige Assemblerprogramme einer 1-Bit-Maschine erfolgreich evolutionär durch einen Computer entwickeln lassen. Die Ideen sind aber dann wieder fallengelassen worden, da für wirklich sinnvolle und damit aber komplexe Problemstellungen, die damaligen Computer viel zu langsam waren. Erst Mitte der 80er-Jahre, bedingt durch das vermehrte Aufkommen von (massiv) parallelen Supercomputern, begannen wieder ernstzunehmende Publikationen in wissenschaftlichen Zeitschriften, bis schließlich 1992 durch das Buch von J.R.Koza ein starker Interessensanstieg hervorgerufen wurde. Er zeigte nämlich, dass man auf diese Weise Programme generieren kann, die in manchen Fällen sogar besser, als die durch den Menschen erstellten Programme sind.
“Genetic Programming“ basiert auf genetischen Algorithmen. Die dazu notwendigen Basiselemente sind
l Functions ( + | - | * | ...) und Terminals (Inputs, Outputs, Konstante),
l ein Programmstrukturraum variabler Länge (Codiervorschrift),
l genetische Operatoren (Mutation, Crossover),
l Fitness Function und Selection Function.
Programme können hierbei repräsentiert werden in
l linearer (textueller) Form: ältestes und heute kaum mehr verwendetes Prinzip;
l Baumform bzw. intern durch Listen: heute meist verwendet;
l Graphenform: allgemeinste Struktur; erlaubt Schleifen, Rekursionen, Speicher; komplex, daher selten verwendet und derzeit noch kaum erforscht.
Die folgenden einfachen Beispiele mögen das Evolutionsprinzip für LISP-Programme erläutern:
a) Crossover:
Gegeben seien folgende Eltern:
Elter 1: ( * ( + a b ) c )
Elter 2: ( * ( - d e ) ( + f g ) )
Durch Crossover der kompatiblen Teillisten ( + a b ) und ( - d e ) in den Eltern entstehen dann die folgenden Kinder:
Kind 1: ( * ( - d e ) c )
Kind 2: ( * ( + a b ) ( + f g ) )
b) Mutation:
Gegeben sei der Elter ( * ( + a b ) c ). Durch Mutation beispielsweise eines Operators entsteht dann das Kind ( * ( - a b ) c ).
Das Verhältnis von Crossover zu Mutation beträgt in der Praxis meist 9:1.
Probleme für die praktische Anwendung:
l Es entstehen hohe Rechenzeiten, da mit großen Populationen (typisch 500 bis 5000 und mehr Programmexemplare) gearbeitet wird, welche über viele Generationen (typisch 100 bis 1000) verändert werden.
l Es ist ein hoher Speicherbedarf vorhanden, da alle Exemplare der aktuellen Population (Eltern und Kinder) gespeichert werden müssen.
l Die Evaluation der Fitness-Funktion gestaltet sich ebenfalls recht aufwendig und daher langwierig.
Es sind daher Parallelrechner zwingend erforderlich.
Die Anwendungen heute basieren meist auf der Sprache LISP, seltener auf anderen High-Level-Languages. Maschinencode-Evolution ist bei den modernen komplexen Prozessoren zu aufwendig. Die wichtigsten Anwendungsgebiete sind
l Autonome Roboter,
l Pattern Recognition,
l Image Processing.
Für interessierte Leserinnen und Leser ist das folgende Buch empfehlenswert:
Es ist dies ein umfassendes und sehr übersichtliches Werk, welches kein wesentliches Vorwissen im Bereich der evolutionären Techniken voraussetzt. Es ist auch für Anfänger in diesem Bereich leicht verständlich und zum Selbststudium geeignet.