Genetische Programmierung [geschlossen]

13

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?

Tom
quelle
1
Es gibt ein gutes Buch von Mat Buckland mit dem Titel "AI Techniques for Game Programming" ( amazon.com/Techniques-Programming-Premier-Press-Development/dp/… ), in dem die Hälfte des Buches genetische Algorithmen behandelt. Der Titel des Buches ist ein bisschen falsch, es ist ein Buch über GAs und neuronale Netze. Es ist eine großartige Einführung in das Thema.
Steven Evers

Antworten:

19

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.

Steven Evers
quelle
Dies ist eine großartige Erklärung. Ich habe immer gedacht, dass genetische Algorithmen besser als darwinistische Algorithmen oder evolutionäre Algorithmen beschrieben werden, aber "genetisch" beschreibt die Mechanik sicherlich besser (wenn nicht die Gesamtidee davon). Ich werde sie darwinistische genetische Algorithmen nennen.
Steven Lu
Ist Conways Lebensspiel ein genetischer Algorithmus?
Florian Margaine
@Florian Margaine: Das Spiel des Lebens ist ein zellularer Automat, ein nicht verwandtes Konzept (ausgehend von der Tatsache, dass das Spiel des Lebens vollständig deterministisch ist, während GA stochastisch ist).
Scrwtp
1
Dies ist zweifellos die beste Erklärung für GA, die ich je gehört habe. Ich habe genetische Algorithmen, die in der Vergangenheit erwähnt wurden, mehrmals gesehen, normalerweise mit beiläufigen Erklärungen, aber ich habe nie wirklich verstanden, was sie bis jetzt waren. Vielen Dank!
Locke
Ich wünschte, ich hätte diese Erklärung gesehen, als ich anfing, GAs zu lernen!
Avrohom Yisroel
7

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

Steven A. Lowe
quelle
Eine Amazon-Suche nach "Genetic Algorithms" brachte mir vier Seiten Zeug. Ich habe nur die erste Seite angeschaut, aber keines der Bücher dort trug den Titel "Genetic Algorithms". Können Sie mehr Details zum Buch wie den vollständigen Titel und den Autor angeben?
David Thornley
Herausforderung: Wiederholen Sie die Antwort als genetischen Algorithmus. [-:
dumm
@ David Link hinzugefügt; veröffentlicht im Jahr 1989, daher gibt es jetzt vielleicht bessere, aber dieser hat die Dinge gut erklärt
Steven A. Lowe
1
@veryfoolish: Zuerst die Frage als begrenzte diskrete Raumlösung wiederholen
Steven A. Lowe
@ David Genetische Algorithmen sind wahrscheinlich auch ein oder zwei Kapitel in einem größeren Buch über künstliche Intelligenz.
Barry Brown
6

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.)

Shahbaz
quelle
1

Ü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.

scrwtp
quelle
-1

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.

Fred Foo
quelle