Intelligenz vererben – Mit genetischen Algorithmen künstliche neuronale Netze trainieren

Künstliche neuronale Netze werden häufig zur Bild- oder Spracherkennung, für Vorhersagen oder auch zur Betrugserkennung eingesetzt. In einigen Bereichen sind die Ergebnisse sogar besser als eine menschliche Vorhersage. Um diese Trefferquoten zu erreichen, müssen die Netze jedoch zuvor aufwendig mit großen Mengen an Testdaten trainiert werden. Stehen keine ausreichenden Testdaten zur Verfügung oder können diese erst zur Laufzeit generiert werden, bieten genetische Algorithmen eine Alternative zum Training der Netze.

Künstliche Intelligenz (KI) und neuronale Netze sind in aller Munde. Die KI hat in den letzten Jahrzehnten Höhen und Tiefen erlebt und befindet sich derzeit in einer ihrer spannendsten Phasen. Mit Hardware wie Grafikkarten, die eigentlich für aufwändige 3D-Computerspiele genutzt werden, oder großen Cloud-Rechenzentren steht heute eine unglaubliche Rechenleistung zur Verfügung, um die komplexe Mathematik hinter den Algorithmen in überschaubarer Zeit zu berechnen.

Doch was steckt hinter all diesen Begriffen und wie sind sie einzuordnen? Was sind genetische Algorithmen und wie können sie neuronalen Netzen beim Lernen helfen?

Der folgende Blog-Beitrag beschreibt

• den Aufbau und die Anwendung künstlicher neuronaler Netze,
• die Grundlagen genetischer Algorithmen,
• wie diese das Training neuronaler Netze unterstützen können und
• anhand des übersichtlichen Beispiels GeneticSnake die Anwendung beider Themen.

Künstliche neuronale Netze

Unter Künstlicher Intelligenz (KI) versteht man ein Teilgebiet der Informatik, das sich mit der Übertragung menschlichen Lernens und Verhaltens auf Computer befasst. Ziel ist es, Computern die Fähigkeit zu eigenständigen Vorhersagen und Entscheidungen zu verleihen. Starke künstliche Intelligenz strebt das Ziel an, menschliche intellektuelle Fähigkeiten nachzuahmen oder sogar zu übertreffen. Derzeit sind wir noch weit davon entfernt. Schwache künstliche Intelligenz zielt darauf ab, sich auf konkrete Probleme zu fokussieren und durch maximale Rechenleistung bessere Ergebnisse zu erzielen als vergleichbare menschliche Leistung. Beispiele hierfür sind Bild- und Spracherkennung, Werbung und auch die Krebserkennung.

Ein weiterer Bestandteil von KI ist das maschinelle Lernen (Machine Learning), das versucht, Wissen aus Daten zu gewinnen. Dies können Informationen oder Muster sein. Dazu werden mathematische Modelle mit großen Datenmengen trainiert, um bestimmte Ergebnisse von geforderter Qualität vorherzusagen. Auf Basis der Trainingsdaten wird ein Modell entworfen, welches Beziehungen zwischen Eingabedaten und Ergebnissen generalisiert vorhersagen kann.

Eine wichtige Unterscheidung muss bei den Trainingsdaten gemacht werden:

• Einige Trainingsdaten beinhalten schon das korrekte Ergebnis, auch als Label (Klassen, Ziele) bezeichnet. Das können beispielsweise Datensätze von Millionen von Bildern sein, welche anzeigen, was auf den jeweiligen Bildern zu sehen ist (Lebewesen, Alltagsgegenstände, Zahlen, Buchstaben).
• Andere Trainingsdaten liefern keine Ergebnisse mit, wie beispielsweise bei Kreditkarten-Transaktionen, bei denen nicht bekannt ist, ob Betrugsfälle vorhanden sind. Andere Modelle müssen hier eingesetzt werden.

Es gibt drei Kategorien des maschinellen Lernens:

• Unüberwachtes Training – Hier können Modelle Daten gruppieren oder Ausnahmen erkennen, da keine Ergebnisse vorliegen.
• Überwachtes Training – Hier können Modelle aus unbekannten Eingaben Ergebnisse vorhersagen, da Ergebnisse vorliegen, anhand derer sie trainiert werden können.
• Beim Reinforcement Learning, auch scherzhaft als Training durch Schmerz bezeichnet, wird das Handeln eines Agenten auf Basis von Belohnungen bestimmt.

In den letzten Jahren haben neuronale Netze verschiedener Architekturen dank der Rechenpower aktueller Computersysteme eine Renaissance im Bereich des überwachten Lernens erfahren. Sobald ein Netz eine komplexere Architektur aufweist, sprechen wir von tiefem Lernen (Deep Learning).

Neuronale Netze sind der Struktur des menschlichen Gehirns nachempfunden. Jedes neuronale Netz hat viele Neuronen, auch Perzeptron genannt, und wird in Schichten (Layern) organisiert. Jedes Neuron ist mit seinen Vorgängern und Nachfolgern in jeder Schicht verbunden. Dabei wird die Verbindung durch unterschiedlich starke Gewichte bestimmt. Jedes Neuron berechnet alle eintreffenden Signale mithilfe einer Aktivierungsfunktion und entscheidet anschließend, ob es das Ergebnis an seine Nachfolger weitergibt. Darüber hinaus gibt es einen Schwellenwert (Bias), der die Berechnung des Ergebnisses noch verfeinern kann. Neuronale Netze sind in verschiedenen Architekturen auf spezifische Anwendungen spezialisiert und definieren somit eine Beziehung zwischen Eingabedaten und dem passenden Ergebnis. Wenn ein unbekanntes Bild einer Katze an ein Bilderkennungsnetz übergeben wird, sollte es vorhersagen, dass es sich um eine Katze handelt. Neuronale Netze bestehen grundlegend aus einer Eingangsschicht, die die Daten annimmt, einer oder vielen versteckten Schichten, in denen die "Intelligenz" stattfindet, und einer Ausgangsschicht, die die Vorhersage liefert. Diese Vorhersage könnte zum Beispiel die Wahl zwischen "Hund oder Katze", die Frage nach einem Betrugsfall oder den Aktienkurs für morgen beinhalten.

Das Training eines neuronalen Netzes, auch als Backpropagation bezeichnet, beginnt mit der Definition eines passenden Architekturplans für das Netzwerk, gefolgt vom Anlegen und der Initialisierung mit zufälligen Gewichten in einem Computersystem. Anschließend wird das Netzwerk mit tausenden, wenn nicht Millionen von Daten gefüttert, und für jeden Datensatz wird die Abweichung zwischen der errechneten Vorhersage und dem Trainings-Ergebnis berechnet. Die genannten Schritte werden als Feed-Forward bezeichnet. Basierend auf komplexen mathematischen Verfahren wird versucht, Abweichungen zu minimieren. Hierfür werden die Gewichte jedes Neurons rückwärts durch das Netz minimal angepasst. Beim nächsten Durchlauf fallen die Abweichungen geringer aus. Dies wird wiederholt, bis die gewünschte Genauigkeit bzw. eine akzeptable Abweichung erreicht wird. Leider kann es bei diesem Verfahren vorkommen, dass nicht die beste, sondern nur eine lokale Genauigkeit (lokales Optimum) erreicht wird. Dadurch wird das neuronale Netz nicht weiter verbessert, obwohl bessere Ergebnisse erzielt werden könnten.

Das trainierte neuronale Netz wird am Ende der Trainingsphase als Modell bezeichnet und für spätere Nutzung gespeichert. Das Modell wird in einem Anwendungsfall in eine Produktionsumgebung eingebunden und für Vorhersagen unbekannter Eingabe-Daten genutzt.

Genetische Algorithmen

Genetische Algorithmen sind ein Teilbereich der Informatik, der der Natur nachempfunden wurde. Die Evolutionstheorie beschreibt die Entstehung und Anpassung von Lebewesen an ihre Umgebung. Sie versucht, die "besten" oder auch "stärksten" Gene der aktuellen Generation an ihre Nachfahren weiterzugeben, damit diese eine maximale Chance auf Überleben haben. Das stärkste Männchen versucht beispielsweise das attraktivste Weibchen zu finden, um seinen Fortbestand und den der Art zu sichern.

Genetische Algorithmen orientieren sich an diesem Prinzip und dienen der Optimierung von mathematischen und statistischen Modellen. Durch die Auswahl der besten Ergebnisse und ihre zufällige Kombination und Mutation können im Laufe der Zeit sehr genaue Vorhersagen getroffen werden. Der Einsatz von Zufall löst das Problem der lokalen Optima im Backpropagation-Algorithmus von neuronalen Netzen.

Bestandteile Genetischer Algorithmen

Genetik

Der Begriff Genetik wird hier abstrakt verwendet. Gene sind Daten, die dazu dienen, die Generationen jeder Evolution zu verbessern. Dies kann durch die Optimierung von Größe und Gewicht oder durch Eigenschaften, die das Verhalten definieren, geschehen. Bei GeneticSnake werden die Gewichte des neuronalen Netzes als Gene verwendet.

Individuum

Jedes Individuum bei GeneticSnake stellt einen eigenständigen Teilnehmer dar, der durch seine Gene und Handlungen seine Fähigkeit unter Beweis stellen muss. Die Schlange wird durch ihre Position auf dem Spielfeld, Länge des Körpers und eigenem neuronalen Netz definiert. Komplexe Sätze und unnötiges Fachvokabular wurden vermieden, um Klarheit zu gewährleisten. Die Struktur des Textes sowie die Verwendung von korrekter Grammatik und Standardterminologie sorgen für Kohärenz und Präzision.

Population

Eine Population ist eine Ansammlung von Individuen. Jedes Individuum hat seine eigene genetische Ausprägung. Bei GeneticSnake besteht die Population aus mehreren hundert Schlangen, die jeweils auf einem eigenen Spielfeld aktiv sind.

Generation

Eine Generation stellt die Population zu einem bestimmten Zeitpunkt dar. In einer Generation werden solange Aktionen ausgeführt, bis ein bestimmter Schwellenwert erreicht wird oder die aktuelle Population “gestorben” ist. In GeneticSnake besteht eine Aktion aus dem jeweils nächsten Schritt im Spielfeld. Es gibt keinen Schwellenwert, die Generation läuft solange, bis die Population vollständig “gestorben” ist.

Evaluation

Bei der Bewertung wird festgestellt, wie gut sich das Individuum an seine Umwelt angepasst hat. In der Informatik wird eine Fitnessfunktion verwendet, um zu bestimmen, welches Individuum der aktuellen Generation das “beste” war, welches eine gute Leistung erbracht hat und welches versagt hat. Bei GeneticSnake ist die Fitnessfunktion eine kleine mathematische Formel, die sich aus der Gesamtzahl der Schritte, den Schritten seit dem letzten Apfel und der Entfernung zum Apfel errechnet.

Selektion

Bei der Auslese wird ein bestimmter Prozentsatz der aktuellen Generation bestimmt, der zu den Schlechtesten gehört und deshalb aussortiert wird. Dies kann ein fester Prozentsatz oder ein prozentualer Abstand zu den Besten der Generation sein. Dadurch wird Platz für neue Generationen geschaffen. Bei GeneticSnake wird derzeit in jedem Durchlauf die Hälfte der schlechtesten Schlangen aussortiert (50 Prozent Aussortierung).

Evolution

Evolution ist die Veränderung der Genetik einer Generation. Dabei gibt es verschiedene Vorgehensweisen.

• Das Beste der aktuellen Generation wird mit allen anderen gekreuzt. Was in der Natur gut funktioniert (der Stier mit seiner Herde), führt in der abstrakten Welt der Informatik allzu oft zu technischen Klonen, die die Fortpflanzung massiv negativ beeinflussen.
• Bei der Parthenogenese pflanzt sich das Individuum ohne Partner mit leicht veränderter Struktur fort. Auch dies führt häufig zu technischen Klonen.
• Die besten der aktuellen Generation kreuzen sich nach einem gewichteten Zufallsprinzip miteinander, bis die Population für die nächste Generation wieder vollständig ist, auch Kreuzung (Crossover) genannt. Bei der Kreuzung werden die Gene der beiden Elternpaare nach mathematischen Methoden vermischt, was zu einer veränderten Genetik des neuen Individuums führt. Bei jedem so entstandenen neuen Individuum besteht eine geringe Wahrscheinlichkeit einer Mutation. Dabei werden einzelne Gene minimal verändert. Dies kann bei einigen Mutanten zu einem besseren Ergebnis führen. führen.

Genetisches Training der Neuronalen Netze

Was versteht man unter genetischem Training neuronaler Netze? Die Gewichte eines neuronalen Netzes werden als Gene bezeichnet. Die einzelnen Gewichte eines Neurons in jeder Schicht werden wie eine lange DNA-Kette aneinandergereiht. Jedes Individuum hat sein eigenes neuronales Netz mit seiner eigenen DNA-Kette. Bei einer Population von 500 Individuen sind dies 500 neuronale Netze. Diese DNA-Kette wird als Erbgut bezeichnet und mit dem oben beschriebenen Verfahren verbessert. Gibt es weitere wichtige Eigenschaften, die in der Evolution genutzt werden sollen, werden diese ebenfalls an die Genetik angehängt. Das bedeutet, dass nach jeder Generation die DNA-Kette zweier Eltern aus den neuronalen Netzen ausgelesen, zu einer neuen DNA-Kette für den Nachfolger gekreuzt und dieser dann wieder in das neuronale Netz geladen wird. All dies geschieht eher zufällig. Dem System werden keine konkreten Hinweise oder Spielzüge vorgegeben. Es gibt auch keine vorher festgelegten Regeln. Nur die ständige Veränderung der Gene führt im Laufe der Zeit zu einem neuronalen Netz, das sich besser zurechtfindet als seine Vorgänger.

GeneticSnake

GenetikSnake ist ein guter Anwendungsfall, der als Beispiel für unsere beschriebenen Ansätze dienen kann. Anstatt tausende von Spielen im Voraus aufzuzeichnen und damit ein klassisches neuronales Netz zu trainieren, wird das Netz während des Spielens kontinuierlich mit Daten gefüttert und kann sich durch Genetik langsam verbessern.

GenetikSnake basiert auf dem einfachen Spiel Snake. Die Welt besteht aus einem Gitter aus Quadraten. In diesem Gitter lebt eine Schlange, die sich ständig bewegt. Dabei kann sie sich nur in die vier Himmelsrichtungen bewegen. Nach und nach erscheinen Äpfel in der Welt. Frisst die Schlange einen dieser Äpfel, erhält sie einen Punkt und neue Lebensenergie. Gleichzeitig wächst ihr Körper um eine Einheit, sie wird länger. Wenn die Schlange den Rand berührt, stirbt sie. Frisst sie sich selbst, stirbt sie.

Ziel ist es nun, die Schlange so lange wie möglich zu bewegen, ohne dass sie stirbt. Das Spiel ist theoretisch gewonnen, wenn die Schlange so groß geworden ist, dass sie das gesamte Spielfeld einnimmt.

Ein Gamer kann nun die Schlange beispielsweise mit der Tastatur steuern, die Richtung bestimmen und Punkte sammeln.

Das Ziel unserer Anwendung ist es, eine KI zu schaffen, die das Spiel selbstständig und ohne menschlichen Einfluss spielt. Dazu wird ein neuronales Netz modelliert, das als Input die sichtbare Umgebung der Schlange, den Rand, den Apfel und den eigenen Körper erhält. Als Ergebnis sagt uns das Netz, in welche Richtung sich die Schlange bewegen soll.

Der aktuelle Stand

Mittlerweile gibt es zahlreiche Frameworks und Bibliotheken auf dem Markt, die jahrelange Praxiserfahrung sammeln konnten und extrem laufzeitoptimiert sind. Gerade für die Programmiersprache Python gibt es mit Keras/Tensorflow (Google) und PyTorch (Facebook) zwei Systeme, mit denen der Anwender schnell Erfolge erzielen kann. Für ein grundlegendes Verständnis der verwendeten Algorithmen wurde bei GeneticSnake jedoch auf diese Hilfe verzichtet. Für die Anwendung wurde ein eigenes neuronales Netz entwickelt, das den FeedForward-Teil für die Vorhersage bereitstellt. Die genetischen Algorithmen sind ebenfalls handgeschrieben, so dass jede Änderung des Codes getestet werden kann.

• Der Code für das neuronale Netz ist auf GitHub verfügbar.

Um die Anwendung dennoch übersichtlich und verständlich zu halten, wurde die Anwendung als native Java-Anwendung mit einer einfachen Swing-Oberfläche (Fat-Client) entwickelt. Aus Performancegründen werden nur die ersten 20 Spielfelder angezeigt, während der Rest im Hintergrund berechnet wird.

• Der Code von GeneticSnake ist auf GitHub verfügbar.

Sobald die Anwendung erstellt und die Algorithmen definiert sind, lehnen wir uns zurück und sehen dem Treiben entspannt zu? So einfach ist es leider nicht. Wenn man nicht genau definiert, was eine gute Generation ausmacht, wird man kaum eine Verbesserung sehen. Wenn zum Beispiel nur die Schritte gezählt werden, sind Schlangen, die endlos im Kreis laufen, die besten. Die Schlangen bekommen als Input nur das, was sie sehen und wissen. Das sind die Abstände zum Rand, zum Apfel und zum eigenen Körper, die Richtung aus der sie kommen und ihre Lebensenergie. Sie bekommen keine Spielregeln und keine Hinweise, was eine sinnvolle Aktion wäre. Das muss alles selbst gelernt werden, bis das neuronale Netz sinnvoll entscheiden kann, wohin es gehen soll. Im Laufe der Evolutionen und Generationen passen sich die Netze immer besser an das Spiel an und verallgemeinern ihre Aktionen. Das bedeutet, dass ein gut trainiertes Netz auch in einer anderen Umgebung funktionieren kann. Beispielsweise kann die beste Schlange auch in einem Raster von 50x500 Feldern überleben, obwohl sie nur auf 10x10 trainiert wurde.

In vielen KI-Projekten ist die Post-Model-Phase eine der längsten Phasen. Hier werden Hyperparameter angepasst und immer wieder Details verbessert. Anschließend wird die Simulation wieder und wieder getestet. Nach vielen Versuchen und Rückschlägen wurde für GeneticSnake eine Netzwerkarchitektur mit passenden genetischen Algorithmen gefunden, so dass Verbesserungen sichtbar wurden. Nach einigen Minuten und ca. 3000 Generationen mit je 100 Schlangen wurden bereits 60 und mehr Äpfel in einem Durchgang gefressen!

Fazit

Das Beispiel GeneticSnake zeigt, dass durch geschickte Auswahl von Umgebungsdaten als Eingabewerte für das neuronale Netz und von Genen, die als Gewichte für das neuronale Netz dienen, in kürzester Zeit beachtliche Ergebnisse erzielt werden können. Während beim “klassischen” Training von neuronalen Netzen ganze Bildschirmszenen als lange Eingangsvektoren in komplexe Netze verwendet werden, die dann stundenlang gerechnet und trainiert werden, reichen hier 30 Eingangswerte aus. Andererseits muss aber im Vorfeld und bei der Entwicklung der Algorithmen und des Modells genau überlegt werden, welche Informationen zur Verfügung gestellt werden müssen, damit sich die Gene und damit das neuronale Netz verbessern. Dazu gehört auch die Fitnessfunktion, die angibt, welche Schlange die “beste” der aktuellen Generation ist. Diese Experimentierphase dauerte einige Zeit, bis erste Erfolge sichtbar wurden.

Ausblick

GeneticSnake befindet sich derzeit in der Post-Model-Phase. Das bedeutet, dass der grundlegende Algorithmus und das gewählte Modell erfolgreich sind, aber durch Optimierung des Quellcodes die Geschwindigkeit der Anwendung erhöht und durch sogenanntes Hyperparameter-Tuning die Lernerfolge des Modells verbessert werden können. Von einem neuronalen Netz, das das Spiel komplett durchspielt, ist GeneticSnake noch weit entfernt. Ein solches Training kann noch viele Stunden in Anspruch nehmen.

Bei adesso wird seit 2020 das Studentenprojekt “KI-Plattform” realisiert. Die KI-Plattform stellt Usern verschiedene Anwendungsfälle von KI in einer benutzerfreundlichen, nicht-technischen Webanwendung vor. Neben der Bilderkennung, der Betrugsanalyse und der Auswertung von Satellitenbildern wird derzeit das Thema Genetik mit einem recht komplexen Anwendungsfall umgesetzt. Eine moderne Webdarstellung von GeneticSnake wird sicherlich noch Platz im Projekt finden.