Neurotische Fahrräder: Genesis

Neulich dachte Youtube, ich würde es interessant finden, ein Video mit dem Titel "AI lernt Hill Climb Racing zu spielen" zu sehen. Es ist lustig, weil ich einige Minuten zuvor die nächsten Änderungen am Projekt vorgenommen hatte, bei denen meine Kollegen und ich zwischen Arbeit und Arbeit dieses Problem lösen. Es stimmt, es gab keine „KI“ in diesem Video - der Autor unterhielt das Publikum mit Box2D und beruhigte sich darauf. Trotzdem schlage ich vor, diese Tatsache als überzeugenden Beweis für die Relevanz des Themas zu betrachten und das Gerät unserer Rassel zu zerlegen.

Kurz zur Aufgabe: Das Fahrzeug - in unserem Fall entweder Alien oder die Singer-Nähmaschine auf Rädern, nennen wir es einfach „Agent“ - muss von Anfang bis Ende mit gleichnamigem Geräusch über die Dünen fahren. So sieht der Agent in seiner Sandbox aus:



Ein Agent, der die Rückseite der Strecke berührt oder nicht den richtigen Eifer zeigt, sich dem Ziel zu nähern, wird von der Strecke entfernt.

Wir werden das Problem mithilfe neuronaler Netze lösen, die jedoch durch den genetischen Algorithmus (GA) optimiert werden - ein solcher Prozess wird als Neuroevolution bezeichnet . Wir verwendeten die von Kenneth Stanley und Risto Miikkulainen zu Beginn des Jahrhunderts erfundene NEAT-Methode (NeuroEvolution of Augmenting Topologies) [1] : Erstens arbeitete er gut bei wichtigen Problemen für die Volkswirtschaft, und zweitens begannen wir mit der Arbeit an dem Projekt hatte bereits einen eigenen Rahmen für die Implementierung von NEAT. Ehrlich gesagt haben wir keine Lösungsmethode gewählt, sondern eine Aufgabe, bei der Sie das fahren können, was bereits fertig ist.

Die Abbildung zeigt ein ungefähres Schema genetischer Algorithmen:



Es ist ersichtlich, dass jede anständige GA von der ursprünglichen Bevölkerung ausgeht (die Bevölkerung ist eine Reihe möglicher Lösungen). Wir werden uns mit seiner Schaffung befassen und gleichzeitig das erste Prinzip von NEAT kennenlernen . Nach diesem Prinzip sollten alle Agenten in der Startpopulation die einfachste „minimale“ Topologie des neuronalen Netzwerks haben. Was hat die Topologie damit zu tun? Tatsache ist, dass sich in NEAT neben der Optimierung der Verbindungsgewichte auch die Netzwerkarchitektur weiterentwickelt. Dies macht es übrigens überflüssig, das Design für die Aufgabe zu erstellen. Der Übergang von einfachen zu komplexen Architekturen ist nicht nur logisch, sondern auch praktisch (es gibt weniger Suchraum). Sie müssen also mit einem Minimum an möglichen Topologien beginnen - so argumentierten die Autoren der Methode.

Für unsere und alle ähnlichen Fälle wird diese minimale Topologie aus den folgenden Überlegungen abgeleitet. Um etwas Sinnvolles zu tun, benötigt der Agent:

• Informationen über die Umwelt und ihren Zustand haben,
• Verarbeiten Sie diese Informationen
• interagiere mit deiner Welt.

Die erste Rolle spielen Sensoren - Neuronen der Eingangsschicht, denen wir nützliche Informationen für den Agenten liefern. Die Ausgangsschichtneuronen verarbeiten die Daten von den Sensoren. Akteure - Geräte, die mechanische Aktionen als Reaktion auf ein Signal von „ihrem“ Neuron der Ausgangsschicht ausführen - sind für die Interaktion mit der Umgebung verantwortlich. Das allgemeine Prinzip für die Konstruktion der Anfangskonfiguration lautet daher wie folgt: Wir bestimmen mit Sensoren und Aktoren, starten ein Neuron pro Aktuator, verbinden alle Sensoren und ein weiteres spezielles Neuron - ein Verschiebungsneuron ( Bias , siehe unten) mit zufälligen Gewichten für alle Neuronen Ausgabeschicht. Irgendwie so:



b - Bias, s - Sensoren, o - Neuronen der Ausgangsschicht, a - Aktoren, n - Anzahl der Sensoren, k - Anzahl der Aktuatoren

Und hier ist die minimale NS für unsere Aufgabe:



Wir haben nur einen Aktuator - dies ist der Motor unserer Radkreation. Es weiß noch nicht, wie man schießt, springt und die Pfeife spielt. Der folgende Wert wird der Engine von einem einzelnen Neuron der Ausgabeschicht zugeführt (es ist eine Schande, ihn als Schicht zu bezeichnen):


Hier ist w _b der Wert des Gewichts der Verbindung, die von der Vorspannung zum Ausgangsneuron geht, multipliziert mit der Tatsache, dass jede Vorspannung "erzeugt", d.h. +1, s _i ist der auf den Bereich [0,1] des i-ten Sensors normierte Wert, w _i ist der Wert des Verbindungsgewichts vom i-ten Sensor zum Ausgangsneuron und f ist die Aktivierungsfunktion.

Als Aktivierungsfunktion verwenden wir diese Softsign-Fantasie:


- Sie zeigte die beste Leistung in Tests eines bekannten Neuroevolutionisten in engen Kreisen [2] . Und es macht keinen Sinn, die Weichheit der Biegungen und die Symmetrie des Graphen dieser Funktion mit der eckig gebogenen Leaky ReLU zu vergleichen:



Diese Figur zeigt die Reaktion des Mittels auf verschiedene Werte der Aktivierungsfunktion. Bei Werten nahe der Einheit dreht der Motor die Räder im Uhrzeigersinn, beschleunigt den Agenten vorwärts und kippt das Gehäuse stark nach hinten, so dass die schwachen, aber mutigen schnell auf den Rücken kippen und sterben. Bei Werten nahe 0 ist das Gegenteil der Fall, und bei einem Wert von 0,5 funktioniert der Agentenmotor nicht.

Die gleiche Abbildung zeigt die Rolle des Bias-Neurons - das Gewicht der Bindung, die von diesem zum Neuron der Ausgangsschicht geht, ist wie folgt aus (1) für die Größe und Richtung des Bias f (x) entlang der Abszisse verantwortlich. Die gepunktete Linie in der Figur zeigt eine graphische Darstellung der Aktivierungsfunktion bei w _b = -1. Es stellt sich heraus, dass ein Agent mit einer solchen Verbindung auch ohne Signal an den Sensoren ziemlich schnell zurückkehrt: f (x) = f (-1 + 0) ≈ 0,083 <0,5. Im Allgemeinen ermöglicht das horizontale Verschieben der Werte der Funktion, dass die Vorspannungsverbindung die Reaktion des Motors auf alle Sensorwerte und das Gewicht ihrer Verbindungen gleichzeitig subtil (gut oder dick, je nach Gewicht) anpasst. Es scheint, dass dem Suchraum eine neue Dimension hinzugefügt wurde (der „richtige“ Wert für w _b muss gesucht werden), aber die Vorteile in Form eines zusätzlichen Freiheitsgrades überwiegen die Möglichkeit solcher Verschiebungen.

Nun, wir haben die neuronalen Netze von Agenten der zukünftigen Anfangspopulation vorgestellt. NEAT ist jedoch ein genetischer Algorithmus und arbeitet mit Genotypen - den Strukturen, aus denen Netzwerke gebildet werden, oder allgemeiner mit Phänotypen im Dekodierungsprozess. Da wir mit dem Phänotyp begonnen haben, werden wir alles rückwärts machen: Versuchen Sie, das oben im Genotyp dargestellte Netzwerk zu codieren. Hier kann man nicht auf das zweite NEAT-Prinzip verzichten , dessen Hauptbestandteil wie folgt lautet: Im Genotyp werden neben der Struktur des neuronalen Netzwerks und den Gewichten seiner Verbindungen Informationen über die Entstehungsgeschichte aller seiner Elemente gespeichert. Mit Ausnahme dieses historischen Aspekts ist der Phänotyp im Genotyp fast „eins zu eins“ kodiert, daher werden wir das zweite Prinzip mit Fragmenten neuronaler Netze veranschaulichen.

Der Wert dieses Prinzips ist schwer zu überschätzen - es bietet Agenten die Möglichkeit der sexuellen Fortpflanzung. Das Thema ist ziemlich heikel, daher werden wir zunächst die asexuelle Fortpflanzung betrachten. Es passiert so: Es wird eine Kopie aller Gene des Agenten erstellt, eine von mehreren Arten von Änderungen wird an ihnen vorgenommen - Mutationen . In unserer Version von NEAT sind folgende Mutationen möglich:

• Änderung des Verbindungsgewichts
• Verknüpfung aufheben
• Link hinzufügen
• Einfügung von Neuronen.

Die ersten drei Arten von Mutationen sind ohne weitere Erklärung einfach und verständlich. Das Einfügen eines Neurons ist in der folgenden Abbildung dargestellt. Es erfolgt immer anstelle der vorhandenen Verbindung, die Verbindung wird entfernt und an ihrer Stelle erscheinen zwei neue:



Hier ist h ein verstecktes Neuron.

Zwei Agenten sind an der sexuellen Fortpflanzung oder Kreuzung beteiligt - Eltern, und als Ergebnis erscheint ein dritter - ein Kind. Bei der Bildung des Genotyps des Kindes findet beispielsweise ein Austausch von Genen oder Gruppen von Genen von Eltern statt, deren Bedeutung identisch ist. Das zweite Prinzip ist genau das, was Sie brauchen, um nach Genen mit derselben Bedeutung zu suchen.

Stellen Sie sich vor, wir möchten Agenten mit Genotypen kreuzen, die verschiedene Mutationsreihen aus der obigen Liste durchlaufen haben:



Es erscheint logisch, nach einigen Fragmenten zu suchen, die in Bezug auf die Topologie bei beiden Elternteilen gemeinsam sind, und ein Stück dieser Fragmente für den Genotyp des ungeborenen Kindes zu nehmen. Es wird schwierig sein, dies zu tun, sogar NP ist im allgemeinen Fall schwierig, aber nehmen wir an, wir haben es geschafft. In diesem Fall stellen wir fest, dass im rechten übergeordneten Element zwei Teilgraphen vorhanden sind, die isomorph zum Diagramm des linken übergeordneten Elements sind. In der folgenden Abbildung sind die Bögen dieser Untergraphen in verschiedenen Farben hervorgehoben:



Welches für die Rekombination mit Genen der linken Eltern wählen?

Wenden wir uns der Entstehungsgeschichte dieser Genotypen zu:



Beide Vorfahren der Elternagenten begannen erwartungsgemäß mit minimalem NS (T ₀ ). Ihre Genome mutierten dort irgendwie, und zum Zeitpunkt T ₁ wurde das verborgene Neuron in die Verbindung s ₁ -> o des Vorfahren des linken Elternteils eingefügt. In diesem dramatischen Moment finden die Gene, die die Bindungen s ₁ -> h und h -> o codieren, ihre Bedeutung im Vorfahren des linken Elternteils: Substitution des Links s ₁ -> o .
Die Gene s ₁ -> h ₁ und h ₁ -> o im Genotyp des rechten Elternteils zum Zeitpunkt T ₂ haben genau die gleiche Bedeutung. Das weitere Schicksal unserer Vorfahren ist für uns nicht von besonderem Interesse - wir wissen bereits, womit wir uns vermischen müssen:



Wie man die genetische Vorgeschichte richtig schreibt, kann man beim nächsten Mal erkennen, zumal wir in diesem Bereich einige kleine Funde haben, die mit der Anpassung der ursprünglichen Technik an ein stabiles Reproduktionsschema verbunden sind.

Es ist Zeit abzurunden. Der Artikel begann mit Youtube - und wir werden ihn vervollständigen. In einer früheren Version des Simulators beendete ein Kollege, der den Code zum Generieren des Tracks geschrieben hatte, ihn mit nichts, einem Abgrund ohne Boden. Die Reaktion eines neuronalen Netzwerks, das sich lange Zeit in Gegenwart eines Erdfirmaments unter Rädern entwickelt hat, auf ein solches Design seines kleinen Universums kann vielleicht als „Template Break“ bezeichnet werden:


Eine umfangreiche Sammlung anderer anekdotischer Geschichten aus dem Leben der Cybernaturalisten findet sich in [3] .

Quellen

[1] KO Stanley und R .. Miikkulainen, Evolving Neural Networks durch Augmenting Topologies Evolutionary Computation, vol. 10, nein. 2, pp. 99-127, 2002.
[2] C. Green, „Eine Überprüfung der Aktivierungsfunktionen in SharpNEAT“, 19. Juni 2017.
[3] J. Lehman et al., „Die überraschende Kreativität der digitalen Evolution: Eine Sammlung von Anekdoten aus den Forschungsgemeinschaften für evolutionäre Berechnungen und künstliches Leben“, arXiv: Neural and Evolutionary Computing, 2018.