Genetische Programmierung [geschlossen]

Ich habe kürzlich Reddit durchsucht und bin auf einen Beitrag gestoßen, der auf ein Beispiel für einen "genetischen JavaScript-Algorithmus" verweist. Ich war wirklich fasziniert von den Konzepten der genetischen Algorithmen und der Programmierung, aber selbst nach einigem Googeln bin ich immer noch etwas verwirrt. Wie funktioniert es?

Ich nehme an, die Vokabeln verwirren mich mehr als alles andere. Ich würde mich über kurze Beispiele und vielleicht Erklärungen freuen. Nur das Konzept der genetischen Programmierung und wie könnte ich es in meinen Projekten umsetzen und warum?

Klingt so, als würden Sie eher über genetische Algorithmen als über genetische Programmierung sprechen, aber hier ist mein Beitrag zu Ihrem Verständnis.

Es kann praktisch sein, sich GAs in Bezug auf die Teile vorzustellen, aus denen sie bestehen.

Angenommen, Sie haben ein Problem. Das erste, was Sie brauchen, ist eine Möglichkeit, um auszudrücken, wie eine Lösung aussehen wird. Wenn Sie einen hatte Handlungsreisende Problem mit den Städten A, B, C, D, E , dann wissen Sie bereits , was eine Lösung wie ein Array mit den Namen der Städte aussehen könnte , [B, C, A, D, E].

Dies ist das Gen .

Andernfalls als mögliche Lösung des Problems bekannt. Wie Steven A. Lowe erwähnt, sind Bit-Strings eine übliche Methode, um Gene zu kodieren, aber sie sind nicht erforderlich. es macht nur bestimmte Dinge einfacher. Der wichtige Teil ist, dass Sie eine Möglichkeit haben, eine Lösung in dieser Art von Array darzustellen.

Jetzt. Woher wissen Sie, ob die Lösung gut ist? Sie benötigen eine Funktion, die Ihnen Auskunft gibt und die die Lösung bewertet. Für TSP gibt es also möglicherweise eine Funktion, die die zurückgelegte Strecke über den Pfad [B, C, A, D, E] misst. Die "Note", die Sie zuweisen, kann einfach die zurückgelegte Strecke sein, aber bei komplizierteren Problemen können Sie Dinge wie die Reisekosten und andere Dinge einbeziehen.

Dies ist das Fitnessfunktion .

So können Sie jetzt eine mögliche Lösung finden und herausfinden, ob es etwas Gutes ist. Was kommt als nächstes?

Als nächstes müssen wir unsere erste Generation starten. Also generieren wir eine Menge zufälliger Lösungen. Es ist egal, ob sie gut sind oder nicht. Dies ist Ihre Ausgangs- oder Ausgangspopulation. Sie können dies Ihren Genpool nennen.

Sie nehmen also Ihren anfänglichen Genpool und wenden Ihre Fitnessfunktion auf alle an und geben ihnen alle eine Note. Jetzt müssen Sie zwei davon nehmen und daraus eine neue Population bilden - für die nächste Generation. Wen wählen Sie aus? Nun, Sie möchten nicht unbedingt nur die passendste auswählen, da dies zu Problemen führen kann. Stattdessen benötigen Sie eine Auswahlfunktion .

Eine Methode zur Auswahl, die sich leicht visualisieren lässt, ist die Verwendung einer Art Rad: Jedes Gen ist eine Scheibe auf einem Rad, und der Fitness-Score gibt an, wie groß die Scheibe ist (je besser die Fitness, desto größer die Scheibe). Setzen Sie eine Nadel auf das Rad und drehen Sie es (dh erzeugen Sie eine Zufallszahl). Die Stecknadel zeigt auf das erste übergeordnete Element. Wiederholen Sie dies für den zweiten Elternteil.

Jetzt müssen Sie neue Kinder erstellen. Sie möchten die Eltern zu einer neuen Population zusammenführen. Es gibt verschiedene Möglichkeiten, dies zu tun, aber sie werden alle als Crossover-Funktion bezeichnet . Sie können sie in zwei Hälften teilen und die Hälften zwischen den Eltern tauschen oder eine Art Interleaving durchführen. Dies ist sehr analog zu Säugetiereltern, die neue Kinder zur Welt bringen -> beide tragen ihre Gene zum neuen Kind bei.

Sobald Sie diese neue Generation haben, geben Sie jedem Kind eine zufällige, aber seltene Mutation. Ich habe oft gesehen, dass Mutationsraten unter 1% liegen. Die Mutationsfunktion ändert zufällig etwas in Ihrem kodierten Gen. Wenn Ihr Gen ein Bitstring ist, kann es ein bisschen tauschen. Wenn es ein Array von Städten ist, können 2 Städte in der Liste getauscht werden. Der wichtige Teil ist, dass es ein relativ seltenes Ereignis ist und die Dinge durcheinander bringt.

Wiederholen Sie diesen Vorgang bis zu einer gewünschten Anzahl von Generationen oder bis Ihre Fitnessfunktion Eltern mit konstant hohen Fitnesswerten hervorbringt und Sie eine Lösung haben, die (hoffentlich, wenn Sie alles richtig gemacht haben) optimal ist.

Das war ein bisschen wortreich, also lassen Sie mich mit einer Metapher zusammenfassen:

1. Gene sind Menschen: Menschen lösen Probleme
2. Fitnessfunktionen sind Noten: Menschen erhalten eine Note basierend darauf, wie gut sie ein Problem lösen
3. Sie wählen 2 Menschen aus, um eine neue Population zu züchten: Sie geben Menschen mit besseren Noten bessere Zuchtchancen
4. Wenn die Eltern züchten, verbinden sie sich, um Kinder zu produzieren.
5. Sie mutieren selten und zufällig ihre Kinder
6. Sie bewerten die Kinder der neuen Bevölkerung
7. Spülen und wiederholen

Hoffe das hilft.

Codieren Sie eine Lösung für ein Problem als Bitfolge

Schreiben Sie eine Funktion (die als "Fitness" -Funktion bezeichnet wird), die auswertet, wie gut die codierte Lösung eine Bitfolge erhält. Das Ergebnis ist normalerweise eine Zahl zwischen 0 und 1

Generieren Sie zufällig eine Reihe dieser Bit-Strings und bewerten Sie ihre Fitness

wähle einige der Bündel - normalerweise die passenderen - und schneide sie in zwei Hälften und tausche die Hälften, um ein paar neue Bit-Strings zu machen (Crossover)

dann manchmal zufällig ein paar Bits in einigen der neuen Bit-Strings umdrehen (Mutation)

Wiederholen, bis eine gute Lösung entsteht

Warum tun Sie dies? Einige Probleme haben enorme mögliche Lösungsräume, die so groß sind, dass die Bewertung aller Möglichkeiten unpraktisch ist (siehe Problem des Handlungsreisenden).

Ich kann das Buch Genetische Algorithmen für Suche, Optimierung und maschinelles Lernen nur empfehlen

Durch genetische Programmierung kann der Computer Programme für Sie schreiben!

Denken Sie nicht an "Programme" wie MS Word, sondern an "Programme" wie folgt:

function(x){ return x*2; }

Diese Funktion (oder dieses Programm) selbst hat keinen Grund zu existieren. Wir suchen nach Lösungen für Probleme. Wenn Sie die Summe von zwei Zahlen finden müssen, öffnen Sie einfach den Taschenrechner und rechnen. Was ist, wenn Ihnen jemand die folgende Tabelle gegeben und Sie gebeten hat, die Beziehung zwischen resultund xund herauszufinden y:

x   y   result
99  1   (3.02)
79  88   2.01 
21  62   5.01 
84  52  (6.58)
12  70   5.54 
67  18   0.73 

Diese Daten sind Ihre "Trainings" -Daten. Ihr Computer verwendet diese Daten, um eine Hypothese zu erstellen, und testet sie dann anhand der tatsächlichen Daten.

Angenommen, Sie kennen keine Statistiken und sind der Meinung, dass dieses Problem zu schwierig ist, um es selbst herauszufinden, sodass der Computer es für Sie herausfinden kann.

Lassen Sie den Computer zufällig wilde Vermutungen anstellen

Sie lassen den Computer eine Million Antworten generieren und prüfen, ob eine von ihnen steckt (raten Sie ... eine Million Mal!). Das Folgende ist ein Beispiel für ein paar Vermutungen:

function(x,y){ return x+y; } // wrong
function(x,y){ return x/1*1*1*1*1*1+y; } //wrong, silly

Sie können dies wissen oder nicht, aber Funktionen oder Programme können auch als Bäume dargestellt werden. Die zweite Funktion wäre beispielsweise:

(+ (/ x (* 1 (* 1 (* 1 (* 1 (* 1 1)))) y)

Sie können es eher wie einen Baum aussehen lassen, indem Sie es wie folgt einrücken (übrigens, schauen Sie sich die Umkehrnotation und die Lisp-Syntax an ... aber Sie werden verstehen, warum wir in Kürze Programme wie dieses darstellen):

(+ 
    (/ x 
        (* 1 
            (* 1 
                (* 1 
                    (* 1 
                        (* 1 1)))) 
    y)

( +Ist an der Spitze mit zwei „Blättern“ von /und y. /Selbst mehrere Kinder hat, etc.)

Deshalb lesen Sie so viel über "Bäume" in der genetischen Programmierung. In jedem Fall stecken wir die Werte von xund yin diese Funktion und sie gibt uns die FALSCHE Antwort. Kein Wunder, da wir das zufällig generiert haben.

Sie beschließen nun, eine Million solcher Lösungen zu generieren. Alle von ihnen sind falsch. Sie stellen jedoch fest, dass einige Antworten näher an der richtigen Antwort liegen als andere. Mit anderen Worten, einige Lösungen passen besser als andere. Beachten Sie, dass der Computer nicht weiß, was "richtig" und "falsch" ist, sodass Sie Ihre eigene "Fitnessfunktion" bereitstellen müssen. Diese Funktion erhält eine mögliche Lösung, die Trainingsdaten, und ist dafür verantwortlich, dem GP-System mitzuteilen, wie "fit" diese Lösung ist. Wie Sie sich vorstellen können, wird diese Funktion millionenfach ausgeführt.

Was macht GP anders?

Das unterscheidet die genetische Programmierung von wilden Vermutungen. Sie beschließen, eine weitere Runde von Millionen Vermutungen anzustellen. Sie tun es jedoch etwas intelligenter. Sie nehmen die besten 10% der Vermutungen (diejenigen, die sich den tatsächlichen Werten näherten) und machen sie zu einem Teil der zweiten Generation. Sie nehmen auch viele dieser Lösungen (vielleicht die gleichen 10% ... ich erinnere mich nicht) und beschließen, "sie zu mischen".

Sie wählen nach dem Zufallsprinzip zwei Lösungen aus, wählen nach dem Zufallsprinzip Teilbäume aus und tauschen sie aus. Ein Teil von Lösung A endet also unter Lösung B und umgekehrt - Sie haben sie nur "gekreuzt". Sie nehmen auch einige Lösungen und "mutieren" sie einfach ... nehmen Sie einen Teilbaum und "vermasseln Sie es" ein wenig (hey, wenn die Lösung schrecklich ist, könnte das "Vermasseln ohne Grund" sie tatsächlich verbessern).

Eine gute Art, darüber nachzudenken, ist folgende: Ihre Eltern haben bestimmte Eigenschaften - Haarfarbe, Körpergröße, Krankheitswahrscheinlichkeit usw. Sie als Kind erben verschiedene Eigenschaften von beiden Elternteilen. Wenn beide Eltern olympische Sportler wären, wären Sie auch ein Supersportler, oder? Nun, Biologen, Soziologen und sogar Historiker mögen sich mit dieser Idee auseinandersetzen, aber Informatiker befassen sich hier nicht mit der Moral der Eugenik. Sie sahen nur, dass ein "System" ziemlich gute Lösungen lieferte, und beschlossen, es in Software zu modellieren.

Wenn es nicht mit der Biologie übereinstimmt, aber dennoch gute Antworten liefert ... sagen viele Informatiker gemeinsam: "Was auch immer, und danke für die Terminologie." Beachten Sie auch, dass alle Ihre Brüder und Schwestern und nicht genau das gleiche ... auch wenn sie die gleichen Eltern haben. Jede Person hat Gene, die aus irgendeinem Grund mutieren (bitte zeigen Sie dies keinem Biologen, es geht darum, die Motivation hinter einem Großteil der Terminologie zu verstehen).

Jetzt veranlassen wir den Computer, Millionen von Programmen zu generieren und deren Fitness zu messen. Die besten Lösungen überleben die nächste Generation. Wir "mutieren" auch und gehen auf die "Population" über (beachten Sie, wie die Sprache der Genetik und Biologie verwendet wird). Sobald die zweite Generation erstellt ist, wird die Fitness erneut gemessen. Da diese Generation die besten Lösungen aus der Vorgängergeneration hat UND wir die besten Lösungen (zusammen mit der mittelmäßigen Bevölkerung - um die Vielfalt aufrechtzuerhalten) gekreuzt und mutiert haben, sollte diese Generation mindestens ein wenig besser sein als die Vorgängergeneration.

Wir setzen dies für eine sehr große Anzahl von Generationen fort. Jede Generation bietet (hoffentlich) immer bessere Lösungen, bis wir die richtige Antwort erhalten. Beispielsweise:

(+ (- 2.2 (/ x 11) (* 7 (cos y))))

Na sieh dir das an, das ist richtig!
(Ich habe dies von http://en.wikipedia.org/wiki/Genetic_programming kopiert , das auch eine grafische Darstellung dieses Baums hat.)

Krimskrams

Es gibt einige wichtige Fragen, wie Sie entscheiden, welche "Terminals" ( +, -, *, /, cos, sin, tan) für Ihr GP-System verfügbar sind, wie Sie die Fitnessfunktion schreiben und wie das System mit unsinnigen Programmen wie (1 + cos)oder (2 / "hello")(unter vielen anderen) umgeht .

Es ist ziemlich langweilig, Gleichungen zu entwickeln. Interessanter wird es, wenn Ihr Terminal-Set wie folgt aussieht: (Feuer, Feind spüren, bewegen, ...) und Ihre Fitness-Funktion Ihre Gesundheit und die Anzahl der Leichen von Kampfmonstern misst.

Das meiste habe ich aus dem Gedächtnis geschrieben, aber das ist die Grundidee. Ich habe in meinen Collegejahren einen GP gemacht. Sie sollten auf jeden Fall damit herumspielen. Machen Sie sich keine Gedanken über das Verständnis der Terminologie, laden Sie einfach einige kostenlose GP-Systeme herunter, durchlaufen Sie einige Beispiele, um ein Gefühl dafür zu bekommen, und stellen Sie sich Ihre eigenen interessanten Beispiele zusammen (finden Sie Beziehungen zwischen verschiedenen Datensätzen, versuchen Sie, sie mit dem Spiel zu verknüpfen APIs usw.)

Überleben der Stärksten: Natürliche Selektion mit Windows Forms war der Einstieg in die genetische Programmierung. Es ist einfach zu lesen und der Code kann heruntergeladen werden. Der Nachteil ist, dass GP ein Mittel benötigt, um zur Laufzeit erstellten Code auszuführen, und zum Zeitpunkt, als der Artikel geschrieben wurde, war C # für diese Aufgabe nicht gut geeignet. Aus diesem Grund verwendet das Beispiel CodeDOM, um Code zur Laufzeit zu generieren, zu kompilieren und auszuführen, wodurch die Komplexität noch erhöht wird.

Seitdem hat sich etwas geändert, da .NET nun eine eigene ExpressionTree-API hat, die wahrscheinlich eine elegantere GP-Implementierung in C # als die im Artikel beschriebene ermöglichen würde. Aber es ist gut genug, um zu verstehen, wie GP funktioniert.

Hier können Sie ein kostenloses eBook über GP herunterladen, das auch ein sehr kurzes Java-Codebeispiel enthält, das Sie vielleicht auch interessant finden.

Genetische Algorithmen und genetische Programmierung sind verwandt, aber unterschiedliche Konzepte.

Genetische Algorithmen (GAs) sind Suchalgorithmen für komplexe Optimierungsprobleme. In einer GA codieren Sie die Parameter einer Lösung für ein Problem in einer "DNA" -Bitfolge und "züchten" diese Bitfolgen dann nach dem Zufallsprinzip: Lassen Sie sie reproduzieren, indem Sie Teile davon kombinieren und "Überleben der Stärksten" anwenden, indem Sie alle Bitfolgen löschen Sie haben außer denen, die Ihr Problem am besten lösen können.

Die genetische Programmierung (GP) ist noch komplizierter: Hier repräsentieren Sie Programme nicht anhand ihrer DNA (Bitstrings), sondern anhand von Analysebäumen, die Sie züchten und auswählen.