Zurück zur Evolution

Bei all der Aufregung um neuronale Netze und Deep-Learning könnte man leicht auf die Idee kommen, in der Welt der Informatik gehe es um nichts anderes mehr. Schließlich sind neuronale Netze bei Aufgaben wie Objekt- und Gesichtserkennung sowie bei Schach, Go und vielen Videospielen inzwischen besser als Menschen.

Diese Netze sind an die Funktionsweise des menschlichen Gehirns angelehnt. Nichts könnte mehr Potenzial haben, oder?

Nicht ganz. Eine vollkommen andere Methode hat das Potenzial, deutlich leistungsfähiger zu werden als neuronale Netze und Deep-Learning. Die Technik basiert auf dem Prozess, durch den das menschliche Gehirn entstanden ist – Evolution. Dabei handelt es sich um eine Abfolge von iterativen Veränderungen und Auswahl, deren Ergebnis die komplexesten und leistungsfähigsten Maschinen überhaupt sind – Augen, Flügel, Gehirn und so weiter. Man kann die Kraft der Evolution nur bewundern.

Genau das ist der Grund dafür, dass Informatiker seit langem versuchen, von ihr Gebrauch zu machen. Das so genannte evolutionäre Computing hat in den 30 Jahren, seitdem es erstmal für die Optimierung einer Produktionslinie für Traktoren eingesetzt wurde, bemerkenswerte Fortschritte gemacht. In den letzten Jahren aber spielte es wegen der riesigen Erfolge bei Deep-Learning nur noch eine Nebenrolle.

Das könnte sich jetzt wieder ändern – dank der Arbeit von Dennis Wilson und Kollegen an der Universität Toulouse in Frankreich. Die Forscher haben gezeigt, dass evolutionäres Computing bei einer symbolträchtigen Aufgabe dieselbe Performance erreichen kann wie Maschinen für Deep-Learning: bei Video-Spielen wie Pong, Breakout oder Space Invaders, mit denen Deep-Learning im Jahr 2013 erstmals von sich reden machte.

Evolutionäres Computing funktioniert vollkommen anders als neuronale Netze. Das Ziel dabei ist, mit einem etwas kontraintuitiven Ansatz Computer-Code zu generieren, der ein konkretes Problem löst.

Konventionell werden Programme geschrieben, indem man von Grundprinzipien ausgeht und ein konkretes Ziel im Sinn hat. Evolutionäres Computing dagegen beginnt mit vollkommen willkürlich generiertem Code – und zwar nicht nur einer Version davon, sondern vielen, manchmal mehreren hunderttausend.

Jedes dieser Programme wird dann daraufhin getestet, ob es das gesetzte Ziel erreicht. Und natürlich sieht der Code darin schrecklich aus, weil er zufällig generiert wurde. Ebenfalls rein zufällig aber sind manche Stücke Code besser als andere. Diese werden dann in eine neue Generation übernommen, in der schon mehr Beispiele für gute Programmierung zu finden sind.

Allerdings darf die folgende Generation keine exakte Kopie der vorigen sein. Stattdessen werden bestimmte Veränderungen daran vorgenommen. Zum Beispiel werden manchmal zwei Ausdrücke getauscht, was mit einer Punktmutation zu vergleichen ist. Oder es werden zwei Programme genommen, in der Mitte geteilt und neu zusammengesetzt – wie bei sexueller Rekombination.

Jede der neuen Generationen wird dann wieder auf ihre Leistung getestet. Die besten Code-Stücke werden in der nächsten Generation bevorzugt reproduziert, und so geht es weiter. Auf diese Weise entwickelt sich der Code weiter. Nach vielen Generationen kann er auf diese Weise besser sein, als es einem menschlichen Programmierer möglich gewesen wäre.

Informatiker haben solche evolutionären Ansätze mit Erfolg für Probleme von der Konstruktion von Robotern bis zum Bau von Flugzeug-Teilen angewendet. Wegen des enormen Interesses an Deep-Learning sind sie später jedoch aus der Mode geraten. Also lautet eine wichtige Frage, ob evolutionäres Computing die Leistung von Deep-Learning-Maschinen erreichen kann. Um das zu überprüfen, haben Wilson und Kollegen den Ansatz genutzt, um Code zu entwickeln, der Spielhallen-Spiele aus den 1980er und 1900er Jahren steuert.

Diese Spiele stehen in einer Datenbank namens Arcade Learning Environment zur Verfügung, die zunehmend genutzt wird, um das Lernverhalten unterschiedlicher Algorithmen zu untersuchen. In der Datenbank finden sich 61 Atari-Spiele wie Pong, Space Invaders, Breakout und Kung Fu Master.

Die Aufgabe besteht darin, einen Algorithmus zu entwickeln, der Spiele wie Pong erlernt, indem er nichts weiter tut, als den Bildschirm beobachten, so wie es auch Menschen machen. Er muss also jede Spielsituation analysieren und dann herausfinden, wie er seine Punktzahl maximiert.

Die Steuerungsmöglichkeiten sind bei allen Spielen gleich. Der Controller lässt sich in acht Richtungen bewegen (rauf, runter, links, rechts und viermal diagonal), außerdem gibt es einen Knopf, und der Controller kann gleichzeitig mit einem Knopfdruck bewegt werden; die letzte Option ist, nichts zu tun. Nicht in allen Spielen werden alle 18 möglichen Kombinationen verwendet, manche kommen mit 4 aus.

Erst einmal muss der Code entstehen. Für evolutionäre Algorithmen benötigt man ein Vokabular von Ausdrücken, die aneinandergereiht Computer-Code ergeben. Die Ausdrücke reichen von einfachen Konstrukten wie ADD (x+y)/2 bis zu komplexeren mathematischen Operationen mit Bedingungen.

Wichtig dabei ist die Auswahl der Ausdrücke für das Vokabular. Wilson und Kollegen nutzten einen Satz, der für kartesische genetische Programmierung, wie ihr Verfahren bezeichnet wird, bereits vorliegt.

Der Prozess beginnt durch die zufällige Generierung von Code mit 40 Ausdrücken. Das ist das „Genom“ des Programms, das dann getestet wird, um zu prüfen, wie gut es das Spiel gemessen an der erreichten Punktzahl schon beherrscht. Abhängig von der Leistung wird das Genom dann mit Mutationen reproduziert, erneut getestet und so weiter. Insgesamt testete das Team auf diese Weise 10.000 unterschiedliche Genome.

Die Ergebnisse sind bemerkenswert. Zuerst spielen die Genome schrecklich schlecht, mit der Zeit aber wurden sie besser. Und nach vielen Generationen wurden sie gut, zum Teil besser als Menschen.

Bei Kung Fu Master zum Beispiel fand der evolutionäre Algorithmus heraus, dass der beste Angriff ein Schlag aus der Hocke ist. In der Hocke ist ein Spieler sicherer, weil er dadurch der Hälfte der auf ihn abgeschossenen Kugeln entgeht und trotzdem angreifen kann. Die Strategie des Algorithmus bestand darin, dieses Manöver wiederholt einzusetzen und ansonsten nichts zu tun. Wie sich zeigte, ist das sehr effektiv.

Für die an der Studie beteiligten menschlichen Spieler war das überraschend. „Diese Strategie manuell nachzuspielen, brachte mehr Punkte als eine normale Spielweise. Der Autor benutzt jetzt ausschließlich Schläge aus der Hocke, wenn er in diesem Spiel angreift“, schreibt Wilson.

Insgesamt war der Evolutionsalgorithmus bei vielen Spielen gut und zum Beispiel bei Kung Fu Master sogar besser als Menschen. Ebenso wichtig: Er funktionierte nicht weniger gut als viele Ansätze mit Deep-Learning und übertraf sie bei Asteroids, Defender und Kung Fu Master.

Zudem erreichte er diese Ergebnisse schneller und hat noch einen weiteren Vorteil. Weil der Algorithmus nur wenige Zeilen umfasst, ist er leicht zu verstehen. Bei Deep-Learning dagegen gibt es das gut bekannte Problem, dass man manchmal unmöglich herausfinden kann, warum Programme bestimmte Entscheidungen treffen, was praktische und rechtliche Probleme bereiten kann.

Insgesamt spricht die Arbeit dafür, dass Informatiker, die sich nur auf Deep-Learning konzentrieren, ein wichtiges Werkzeug übersehen. Der evolutionäre Ansatz ist eine leistungsfähige Alternative, die sich in vielen Situationen einsetzen lässt. Tatsächlich haben einige Forscher bereits begonnen, mit Hilfe von Evolution zu besseren Maschinen für Deep-Learning zu kommen.

()