Anwendungen und Einschränkungen des genetischen Algorithmus

An dieser Stelle in der Serie zur genetischen Programmierung (GP) haben wir erfahren, was genetische Programmierung ist und wie sie Informationen darstellt, wie genetische Operatoren in evolutionären Algorithmen funktionieren und ein Sortierprogramm durch symbolische Regression entwickelt haben.

Hier sehen wir uns auf hoher Ebene an, was diese Technologie während ihrer Entwicklung leisten kann.

Praktische Überlegungen zur genetischen Programmierung

Um dieses letzte Kapitel unserer Serie zu verstehen, erinnern wir uns an ein XOR-Beispiel, das wir im ersten Teil dieser Serie besprochen haben:

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.

Schauen wir uns auch das symbolische Regressionsbeispiel aus dem vorherigen Artikel an:

Eine polynomielle Annäherung an sin(x) im Intervall (0 <=x <=pi/2) (Definiertes Programm () (+ (* (* (* X X) X) (* 0,2283 -0,6535)) X) ) Die Vereinfachung des obigen Programms ergibt die folgende äquivalente Gleichung:polysin(x) =-.1492 x
3
 + x Ergebnisse:

x	sin(x)	polysin(x)
0.000	0.000	0.000
0.078	0.077	0.077
0,156	0,155	0,155
0,234	0,231	0,232
0.312	0.306	0.307
0.390	0.380	0.381
0.468	0.451	0.452
0.546	0.519	0.521
0.624	0.584	0.587
0.702	0.645	0,650
0.780	0.703	0.709
0.858	0.756	0.763
0.936	0.805	0.813
1.014	0.848	0.858
1.092	0.887	0.897
1.170	0.920	0.931
1.248	0.948	0.957
1.326	0.970	0.978
1.404	0.986	0.991
1.482	0.996	0.996
1.560	0.999	0.993

Auflistung 4. Symbolische Regression.

Beachten Sie, dass sowohl die XOR- als auch die hier vorgestellten Beispiele für die symbolische Regression bei der Auswertung einen einzelnen Wert zurückgeben.

Diese Eigenschaft muss keine Einschränkung darstellen, da es durchaus möglich ist, dass eine Funktion oder ein Terminal bei der Ausführung einen Nebeneffekt hat. Dies ist häufig bei Sortierprogrammen der Fall, die eine Funktion mit dem möglichen Nebeneffekt enthalten, ein Paar von Elementen in einem Vektor auszutauschen. In der Praxis kommt es häufig zu Nebenwirkungen. Einige zusätzliche Beispiele für nützliche Nebeneffekte sind das Zuweisen einer Variablen zu einer anderen oder das Ändern der Richtung, in die ein Roboter schaut.

Unser Funktionssatz kann bedingte Funktionen enthalten, die den entwickelten Programmen die Fähigkeit verleihen, Entscheidungen zu treffen. Bedingte Funktionen werten ihre Argumente selektiv aus. Betrachten Sie als Beispiel eine Funktion mit einer Stelligkeit von drei, wie (if arg1 arg2 arg3). Die Funktion wird ausgewertet, indem das erste Argument ausgewertet wird, und wenn das Ergebnis wahr ist, wird das zweite Argument ausgewertet; andernfalls wird das dritte Argument ausgewertet. Auch iterative Konstrukte sind möglich, da eine Funktion eines ihrer Argumente mehrmals auswerten kann. Zusätzliche Komplexität entsteht jedoch durch die Notwendigkeit, die Anzahl der Iterationen und die Verschachtelungsebene zu begrenzen, um eine Situation zu vermeiden, in der die Bewertung einer Person übermäßig lange dauern kann. Es wurde einige Arbeit geleistet, um rekursive Formulierungen zu ermöglichen, obwohl der Erfolg in diesem Bereich etwas begrenzt war.

Obwohl die Ergebnisse von GP-Systemen dazu neigen, LISP-ähnliche Programme zu sein, muss ein GP-System nicht in LISP implementiert werden. Viele Systeme sind in C oder C++ implementiert. Eine linearisierte Darstellung des Programmbaums kann verwendet werden und der Overhead von dynamischem Speicher zusammen mit einer teuren Garbage Collection kann vermieden werden. Die Effizienz der Fitnessfunktion verdient besondere Aufmerksamkeit, da sie aufgrund der vielen Aufrufe pro Generation oft ein Flaschenhals ist. Ein ausgezeichnetes Papier, in dem verschiedene Implementierungstechniken diskutiert werden, finden Sie in Advances in Genetic Programming (zitiert im Abschnitt Empfohlene Lektüre unten).

Wie in anderen Paradigmen des maschinellen Lernens, wie z. B. neuronalen Netzen, besteht die Möglichkeit, die Trainingsdaten (GP-Testfälle) zu überfitten. Eine Überanpassung kann auftreten, wenn die Lösung die Daten effektiv "merkt", wodurch kaum mehr als eine ausgeklügelte Nachschlagetabelle bereitgestellt wird. Eine einfache Möglichkeit, diesen Effekt einzudämmen, besteht darin, einen Sparfaktor zu verwenden. Ein Sparsamkeitsfaktor ist typischerweise ein kleiner Bruchteil multipliziert mit der Anzahl der Knoten innerhalb des Programmbaums, dessen Ergebnis in die Fitnessfunktion aufgenommen wird. Die Idee ist, kleinere, vermutlich allgemeinere Lösungen zu belohnen. Darüber hinaus werden Sie ermutigt, geeignete experimentelle Designtechniken zu verwenden. Wenn Sie beispielsweise versuchen, ein Modell für die Vorhersage zu entwickeln, empfiehlt es sich, die Fitnessbewertung auf eine Teilmenge der verfügbaren Daten zu beschränken. Auf diese Weise können die verbleibenden Daten die Vorhersageleistung des resultierenden Modells messen.

Wie bei evolutionären Algorithmen gibt GP keine Garantie dafür, eine exakte Lösung oder gar eine akzeptable Lösung zu finden. Die Ergebnisse können von Lauf zu Lauf stark variieren. Häufig konvergiert der Prozess vorzeitig auf ein lokales Minima. Die Leistung hängt stark von der Problemkomplexität, ihrer Darstellung durch die Wahl der Funktionen und Terminals und den Eigenschaften der Fitnessfunktion ab.

Anwendungen für die genetische Programmierung

Genetische Programmierung wurde erfolgreich auf Probleme angewendet, die in folgenden Bereichen auftreten:

• Schaltungsdesign
• Kombinatorische Optimierung
• Kontrollsysteme
• Kurvenanpassung/Regressionsanalyse
• Datenkomprimierung
• Wirtschaftliche Prognosen/Finanzmodellierung
• Erwerb der Spielstrategie
• Mathematische Sequenzinduktion
• Neurales Netzwerkdesign
• Mustererkennung und -klassifizierung
• Zufallszahlengenerierung
• Roboternavigation
• Symbolische Integration und Differenzierung
• Dreidimensionales Design

Zukünftige Richtungen für die genetische Programmierung

Je nach Komplexität des Problems können mehrere GP-Läufe erforderlich sein, um eine akzeptable Lösung zu finden, falls überhaupt eine gefunden werden kann. Idealerweise möchten wir, dass GP mit zunehmender Komplexität des Problems "skaliert". Gute Wege zu finden, um dieses Ziel zu erreichen, ist ein aktives Forschungsgebiet. Wie in der konventionellen Programmierung ist die Vorstellung, Darstellungen auf höherer Ebene durch Unterroutinen zu erstellen, eine Möglichkeit, dieses Problem anzugehen. In Genetische Programmierung II diskutiert Koza Methoden, die wiederverwendbare Subroutinen entdecken können, und präsentiert Ergebnisse, die die Fähigkeit von hierarchischen, modularen Programmen unterstützen, komplexere Probleme zu lösen.

Wie wir gesehen haben, koppelt GP die selbstorganisierenden Eigenschaften des genetischen Algorithmus mit der Darstellungskraft und Allgemeingültigkeit von S-Ausdrücken. Die Eleganz dieses Ansatzes vereinfacht die Problemspezifikation dahingehend, eine domänenspezifische Fitnessfunktion und einen geeigneten Funktions- und Endgerätesatz bereitzustellen. Anwendbar auf eine Vielzahl von Problemen, ist die Allgemeinmedizin nach wie vor ein fruchtbarer Boden für die Forschung.

Noch in den Kinderschuhen stecken könnten uns zukünftige Durchbrüche einen Schritt weiter zum Heiligen Gral von Systemen führen, die in der Lage sind, ihre eigenen Programme zu schreiben.

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.