Kapitel 2 : Genetische Programmierung

Genetische Programmierung, oft auch als GP bekannt, ist eine Methode, die in der künstlichen Intelligenz verwendet wird, um Programme zu entwickeln, um sie für eine bestimmte Aufgabe besser geeignet zu machen. Dies wird erreicht, indem Operationen, die natürlichen genetischen Prozessen ähneln, auf eine Population von Programmen angewendet werden.

Die Verfahren bestehen in der Auswahl der Programme, die für die Fortpflanzung (Crossover) und Mutation am besten geeignet sind, basierend auf einem vorgegebenen Fitnessmaß, das oft dem Kenntnisstand einer Person in der gewünschten Aktivität entspricht. Im Prozess der Erzeugung neuer und unterschiedlicher Kinder, die Teil der nächsten Generation von Programmen werden, umfasst der Crossover-Vorgang den Austausch zufälliger Teile ausgewählter Paarungen, die als Eltern bezeichnet werden. Der Prozess der Änderung eines Programms durch Mutation beinhaltet die zufällige Änderung eines Teils des Programms mit einer anderen Komponente des Programms nach dem Zufallsprinzip. Einige der Programme, die in Betracht gezogen wurden, aber letztendlich für die Replikation verworfen wurden, wurden von der vorherigen Generation auf die neue Generation übertragen. Danach wird die Auswahl zusammen mit den anderen Operationen rekursiv auf die nächste Generation von Programmen angewendet.

Die Mitglieder jeder neuen Generation sind im Durchschnitt oft gesünder als die Mitglieder der Generation, die vor ihnen kam, und das Best-of-Generation-Programm einer Generation ist in der Regel besser als die Best-of-Generation-Programme früherer Generationen. Die Evolution kommt oft zu einem Ende, nachdem eines der konstituierenden Programme ein zuvor festgelegtes Kompetenz- oder Fitnessniveau erreicht hat.

Es ist möglich, und es kommt tatsächlich ziemlich oft vor, dass eine bestimmte Ausführung des Algorithmus zu einer frühen Konvergenz zu einem lokalen Maximum führt, das weder ein globales Optimum noch eine vernünftige Lösung ist. Um ein wirklich hervorragendes Ergebnis zu erzielen, sind oft eine Reihe von Iterationen erforderlich, die von Dutzenden bis zu Hunderten reichen. Um Krankheiten vorzubeugen, ist es möglich, dass es wichtig ist, eine hohe Anfangspopulationsgröße sowie eine hohe Heterogenität zwischen den Individuen zu haben.

Es ist wahrscheinlich, dass Alan Turings Vorschlag, der 1950 gemacht wurde, die erste Aufzeichnung der Idee war, Programme zu entwickeln. zeigte 77 Ergebnisse, in denen die genetische Programmierung gut mit dem Menschen konkurrierte.

1996 etablierte Koza die Konferenz "Genetic Programming" als jährliche Veranstaltung.

Die frühen Arbeiten, die den Grundstein für zeitgenössische Forschungsgegenstände und Anwendungen in der genetischen Programmierung legten, sind ziemlich breit gefächert. Einige Beispiele für diese Arbeit sind Softwaresynthese und -reparatur, prädiktive Modellierung und Data Mining. Die Evolution von Computerprogrammen, die oft als Baumstrukturen im Speicher gespeichert sind, wird über GP durchgeführt. Das rekursive Auswerten von Daten ist mithilfe von Bäumen einfach zu bewerkstelligen. Da jeder Knoten in der Struktur eine Operatorfunktion ausführen kann und jeder Knoten, sogar Endknoten, als Operand fungieren kann, ist das Entwickeln und Auswerten mathematischer Ausdrücke ein einfacher Prozess. Daher bevorzugt GP in der Vergangenheit Programmiersprachen, die von Natur aus Baumstrukturen enthalten (z. B. Lisp; andere funktionale Programmiersprachen eignen sich auch).

Nicht-Baum-Repräsentationen wurden vorgeschlagen und erfolgreich umgesetzt, wie z.B. die lineare genetische Programmierung, die für die konventionelleren imperativen Sprachen geeignet ist [siehe z.B. Banzhaf et al. (1998)]. Eine andere Art der genetischen Programmierung, die als "GP" bekannt ist, wird als "kartesische genetische Programmierung" bezeichnet und verschlüsselt Computerprogramme mit einer Graphendarstellung anstelle der standardmäßigen baumbasierten Darstellung.

Die Mehrzahl der Darstellungen enthält Code, der strukturell nicht effektiv ist (Introns). Es könnte den Anschein haben, als ob solche nicht-kodierenden Gene sinnlos sind, da sie keinen Einfluss auf die Leistung einer einzelnen Person haben. Sie verändern jedoch die Wahrscheinlichkeit, unterschiedliche Nachkommen zu erzeugen, wenn sie den Variationsoperatoren unterworfen werden, was wiederum die Variationsmerkmale des Individuums verändert. Experimente scheinen eine schnellere Konvergenz zu zeigen, wenn Programmrepräsentationen verwendet werden, die solche nicht-kodierenden Gene ermöglichen, im Vergleich zu Programmrepräsentationen, die überhaupt keine nicht-kodierenden Gene enthalten.

Der Begriff "Auswahl" bezieht sich auf den Prozess der Auswahl einiger Mitglieder der aktuellen Generation, die die Eltern der nachfolgenden Generation werden. Die Auswahl der Personen erfolgt in einer probabilistischen Weise, so dass die Personen, die besser abgeschnitten haben, eine größere Wahrscheinlichkeit haben, ausgewählt zu werden. Mehrere andere Behandlungen haben sich bei einer Vielzahl von Problemen des Allgemeinmediziners als wirksamer erwiesen.

Elitismus, der beinhaltet, die nächste Generation mit der besten Person (oder den besten n Menschen) aus der gegenwärtigen Generation zu besetzen, ist eine Strategie, die oft eingesetzt wird, um Rückschritte zu verhindern. Elitismus bedeutet, die nächste Generation mit dem besten Individuum (oder den besten n Individuen) zu säen.

Im Prozess der genetischen Programmierung werden zwei gesunde Menschen aus der Population ausgewählt, um Eltern von einem oder zwei Nachkommen zu werden. Im Rahmen der genetischen Programmierung von Bäumen werden ihre Eltern als umgekehrte lispelartige Bäume dargestellt, wobei sich die Wurzelknoten ihrer Bäume ganz oben befinden. Bei einer Überquerung eines Teilbaums wird ein Teilbaum aus jedem übergeordneten Element nach dem Zufallsprinzip ausgewählt. (Dies wird gelb hervorgehoben, wenn Sie sich die Animation ansehen.) Um einen neuen untergeordneten Baum zu erstellen, wird der ausgewählte Teilbaum aus dem übergeordneten Baum entfernt, der seine Wurzel spendet (wie links in der Animation zu sehen), und dann durch eine Kopie des Teilbaums ersetzt, der zufällig aus dem anderen übergeordneten Baum ausgewählt wurde.

Es gibt Situationen, in denen ein Crossover für zwei untergeordnete Elemente verwendet wird. In diesem Szenario wird der entfernte Teilbaum (links in der Animation gezeigt) nicht einfach verworfen. Vielmehr wird sie in eine Kopie des zweiten Elternteils (rechts abgebildet) übertragen, wo sie den Platz des zufällig ausgewählten Teilbaums in der Kopie einnimmt.

Daher werden bei dieser Art von Teilbaum-Crossover zwei gesunde Bäume verwendet, um zwei Nachkommenbäume zu erzeugen.

In der genetischen Programmierung gibt es eine große Vielfalt an Mutagenese. Sie beginnen mit einem syntaktisch korrekten Elternteil, der fit ist, und versuchen dann, durch Randomisierung einen syntaktisch korrekten Nachkommen zu erzeugen. Während der Animation wird ein verzweigter Teilbaum zufällig ausgewählt (gelb hervorgehoben). Er wird eliminiert und an seiner Stelle wird ein zufällig erstellter Teilbaum eingefügt.

Andere Mutationsoperatoren wählen ein Blatt (einen externen Knoten) des Baums und ersetzen es durch ein zufällig ausgewähltes Blatt. Dies geschieht, wenn das Blatt ausgewählt ist. Eine andere Art von Mutation besteht darin, eine Funktion oder einen internen Knoten nach dem Zufallsprinzip auszuwählen und sie dann durch eine andere Funktion zu ersetzen, die die gleiche Arität (Anzahl der Eingaben) hat. Die Hoist-Mutation wählt zufällig einen Teilbaum aus und ersetzt ihn dann durch einen anderen Teilbaum, der sich in ihr befindet. Infolgedessen werden die Nachkommen einer Hoist-Mutation immer zierlicher sein. Der Austausch der Blatt- und Gleichgewichtsfunktionen garantiert, dass der Nachwuchs die gleichen Abmessungen wie sein Elternteil hat. Die Animation zeigt zwar, dass die Mutation des Teilbaums je nach Funktion und Terminalsätzen dazu führen kann, dass der Baum entweder vergrößert oder verkleinert wird. Die Größe des Ersatz-Teilbaums und damit die Größe des untergeordneten Baums ist ein Faktor, der sorgfältig durch andere Mutationen gesteuert wird, die auf dem Teilbaum basieren.

In ähnlicher Weise gibt es viele andere Arten von Mutationen, die während der linearen genetischen Programmierung auftreten können, und jede stellt sicher, dass das modifizierte Kind immer noch syntaktisch korrekt ist.

GP wurde gut als Werkzeug für die automatisierte Programmierung, als Werkzeug für maschinelles Lernen und als automatische Problemlösungsmaschine eingesetzt. All dies sind Beispiele für seine Vielseitigkeit. in der menschenwettbewerbsfähige Ergebnisse durch jede Art von genetischem und evolutionärem Rechnen geschaffen werden können und monetäre Anreize für ihre Leistungen erhalten werden. Im Laufe seiner Teilnahme an diesem Wettbewerb hat GP eine Reihe von Auszeichnungen erhalten.

Die Evolution eines genetischen Programmiersystems durch die Verwendung der genetischen Programmierung selbst ist das Ziel der vorgeschlagenen Meta-Lernmethode, die als metagenetische Programmierung bekannt ist.

Es scheint darauf hinzudeuten, dass Chromosomen, Crossover, sowohl Mutation als auch natürliche Selektion zur Evolution geführt haben. Daher sollte man sie, ähnlich wie ihre Gegenstücke im wirklichen Leben, sich selbst verändern lassen, anstatt diese Veränderungen von einem menschlichen Programmierer vorbestimmt zu haben.

Meta-GP wurde 1987 von Jürgen Schmidhuber offiziell vorgeschlagen.

Diejenigen, die mit diesem Konzept nicht...