Fluglern-Simulator

Was steckt dahinter?

Jede Schwanzmeise bekommt 60-mal pro Sekunde fünf Zahlen: wie hoch sie gerade ist, wie schnell sie steigt oder fällt, wie weit der nächste Stumpf noch weg ist und wo die nächsten beiden Lücken liegen. Daraus rechnet ihr Netz eine Zahl zwischen 0 und 1. Liegt sie über 0,5, schlägt die Schwanzmeise mit den Flügeln. Bei sechs Neuronen hat so ein Netz 43 Gewichte, und nur die ändern sich beim Lernen. Die Physik ist dieselbe wie im Spiel Meisenflug.

Normalerweise lernen neuronale Netze mit Backpropagation: Man rechnet aus, in welche Richtung jedes Gewicht den Fehler kleiner macht. Das geht hier nicht, weil es für einen einzelnen Flügelschlag keinen Fehler gibt. Ob ein Schlag gut war, zeigt sich oft erst einen Stumpf später, und ein Zusammenstoß passiert oder eben nicht. Die einzige Rückmeldung kommt ganz am Ende: Wie weit ist die Schwanzmeise gekommen? Deshalb lernen die Schwanzmeisen hier so, wie die Evolution funktioniert. Ausprobieren, bewerten, das Bessere behalten.

Der genetische Algorithmus nimmt das ziemlich wörtlich. Die zwei besten Schwanzmeisen kommen unverändert in die nächste Runde. Für alle anderen werden Eltern ausgelost, und von drei zufälligen Schwanzmeisen gewinnt immer die beste. Das Kind bekommt jedes Gewicht entweder von der Mutter oder vom Vater, und ein paar davon werden zufällig ein bisschen verändert. 2017 hat ein Team bei Uber gezeigt, dass dieses einfache Verfahren sogar Netze mit Millionen Gewichten trainieren kann, die Atari-Spiele spielen.

Evolution Strategies gehen anders vor. Es gibt nur ein Netz, sozusagen die Durchschnitts-Schwanzmeise (die gelbe). Alle anderen fliegen mit leicht verrauschten Kopien davon. Danach schaut man, welche Veränderungen gut waren, und schiebt das Durchschnittsnetz ein Stück in diese Richtung. Mathematisch ist das eine Schätzung des Gradienten, also genau das, was Backpropagation ausrechnen würde, nur durch Ausprobieren statt durch Ableiten. Ebenfalls 2017 hat OpenAI gezeigt, dass das mit Tausenden Rechnern parallel fast so gut klappt wie klassisches Reinforcement Learning.

Die Formeln, für alle, die es genau wissen wollen

Das Netz

$$\mathbf{h}=\tanh (W_1\mathbf{x}+{\mathbf{b}}_1),p=\frac{1}{1+e^{-({\mathbf{w}}_2^{\top }\mathbf{h}+b_2)}}$$

x sind die fünf Eingaben, jeweils ungefähr auf −1 bis 1 skaliert. Die Schwanzmeise flattert, wenn p > 0,5 ist. Alle Gewichte zusammen ergeben den Vektor θ, das „Genom“ der Schwanzmeise.

Fitness

$$F\left(\theta \right)=\frac{d}{360\text{px}}-\frac{1}{2}·\frac{|y_{\text{crash}}-y_{\text{gap}}|}{H}$$

d ist die geflogene Strecke, F zählt also ungefähr die geschafften Stümpfe. Der zweite Teil ist klein und entscheidet nur zwischen Schwanzmeisen, die an derselben Stelle abstürzen.

Genetischer Algorithmus: Mutation

$${\theta }_j^{\prime }={\theta }_j+\sigma {\epsilon }_j,{\epsilon }_j\sim \mathcal{N}(0,1)$$

Jedes Gewicht wird mit der Wahrscheinlichkeit p_m (Regler Mutationsrate) verändert, um einen zufälligen Betrag aus einer Normalverteilung mit Streuung σ.

Evolution Strategies: der Schritt

$${\nabla }_{\theta }\mathbb{E}\left[F\right(\theta +\sigma \epsilon \left)\right]=\frac{1}{\sigma }\mathbb{E}\left[F\right(\theta +\sigma \epsilon \left)\epsilon \right]\Rightarrow \theta \leftarrow \theta +\frac{\alpha }{n\sigma }\sum _{i=1}^n{u}_i{\epsilon }_i$$

ε ~ N(0, I) ist das Rauschen jeder Kopie, immer als Paar +ε und −ε. Statt der rohen Fitness nimmt u die Ränge, gleichmäßig verteilt zwischen −0,5 und 0,5, damit eine einzelne Schwanzmeise mit Glück nicht den ganzen Schritt bestimmt. α ist die Schrittweite.

Probier mal

• Zwei Neuronen statt sechs. Meistens klappt es trotzdem, weil die Aufgabe einfacher ist, als sie aussieht.
• Schalt die Windböen ein, wenn die Schwanzmeisen schon fliegen können. Die Kurve bricht ein und erholt sich dann langsam.
• Stell σ ganz klein. Der genetische Algorithmus kommt kaum noch vom Fleck, und Evolution Strategies verlieren die Richtung, weil alle Kopien gleich fliegen.

Gut zu wissen

• Beim genetischen Algorithmus springt der Median stark. In jeder Runde sind viele frisch veränderte Schwanzmeisen dabei, und die meisten Veränderungen machen es schlechter. Entscheidend ist die beste Schwanzmeise.
• Ohne den kleinen Abzug für einen Absturz weit weg von der Lücke wären am Anfang alle Schwanzmeisen gleich schlecht, und keins der beiden Verfahren wüsste, in welche Richtung es gehen soll.
• Jede Generation fliegt eine neue Strecke. Sonst würden die Netze eine Strecke auswendig lernen statt das Fliegen.
• Vereinfacht ist, dass die Schwanzmeisen ihre Umgebung als fünf saubere Zahlen bekommen. Echte Vögel, und Programme, die aus Bildern lernen, müssen das erst aus dem herauslesen, was sie sehen. Der Aufbau des Netzes bleibt hier immer gleich. Verfahren wie NEAT erfinden unterwegs auch neue Neuronen und Verbindungen dazu. Und nach 100 Stümpfen ist die Runde vorbei, sonst würde sie nie aufhören.

Quellen

• Such, F. P., Madhavan, V., Conti, E., Lehman, J., Stanley, K. O. & Clune, J. (2017). Deep Neuroevolution: Genetic algorithms are a competitive alternative for training deep neural networks for reinforcement learning. arXiv:1712.06567.
• Salimans, T., Ho, J., Chen, X., Sidor, S. & Sutskever, I. (2017). Evolution strategies as a scalable alternative to reinforcement learning. arXiv:1703.03864.
• Wierstra, D., Schaul, T., Glasmachers, T., Sun, Y., Peters, J. & Schmidhuber, J. (2014). Natural evolution strategies. Journal of Machine Learning Research, 15, 949–980.
• Stanley, K. O. & Miikkulainen, R. (2002). Evolving neural networks through augmenting topologies. Evolutionary Computation, 10(2), 99–127.