genetische-algorithmen

Genetische Algorithmen oder evolutionäre Algorithmen sind eine schon lange bekannte Klasse von Optimierungs-Algorithmen, die versuchen, mit den aus der Natur bekannten Strategien der Evolution Lösungen für bestimmte Probleme zu finden. Sie werden insbesondere dann eingesetzt, wenn Standard-Methoden die optimale Lösung gar nicht, oder nicht schnell und zuverlässig genug finden können.

Wo ist ganz oben? Lokale und globale Maxima

Ein Beispiel hierfür ist das Bestimmen des globalen Maximums einer Funktion, die viele weitere lokale (niedrigere) Maxima aufweist. Normale Optimierungen würden bei dieser Aufgabe entweder bei einem lokalen Maximum hängen bleiben, oder zwischen den Extremwerten endlos hin und her oszillieren.

genetic algorithm optimization

Beispiel für eine Funktion mit vielen lokalen Extremen

Genetische Algorithmen verwenden als Messung für die Zielerreichung immer eine sogenannte Fitness-Funktion. Mit Evolutions-Strategien wird dann versucht, das Ergebnis dieser Fitness-Funktion zu maximieren (z.B. den höchsten Wert einer Kurve mit vielen lokalen Maxima zu finden). Die Evolutions-Strategie besteht darin, alle zur Verfügung stehenden Parameter zufällig zu initialisieren – und zwar nicht nur einmal, sondern sehr oft und parallel.

Die Evolution von Parameter-Populationen

Es wird eine ganze Population von Funktionen mit jeweils unterschiedlichen Parametern gebildet, z.B. 100 verschiedene Funktions-„Individuen“. Von dieser Population werden dann z.B. die 10% ausgewählt, deren Fitness-Funktion den höchsten Wert aufweist, und alle anderen werden verworfen. Die verbleibenden Funktionen bzw. Individuen der Population werden durch Klonen, Re-Kombination und Mutation weiter „gezüchtet“, und dann wiederum anhand der Fitness-Funktion ausgesiebt.

Klonen bedeutet in diesem Zusammenhang kopieren, Re-Kombination bedeutet, dass ein zufälliger Teil der Parameter eines Individuums durch den entsprechenden Teil eines anderen Individuums der aktuellen Population ausgetauscht wird. Zusätzlich können sich einzelne Parameter eines Individuums durch zufällige Mutationen weiter entwickeln. Die Werte für die Re-Kombinations- und Mutationsraten, sowie die Größe der Population und der Prozentsatz, der jeweils überlebt sind entsprechend Hyperparameter, die vom Entwickler vorgegeben werden.

Die durch die Evolutions-Strategie erzielten Verbesserungen genetischer Algorithmen werden schließlich immer kleiner und ändern sich kaum noch, wenn das globale Maximum erreicht ist. Das Auffinden von globalen Maximum- oder Minimum-Werten in einer zerklüfteten Funktions-Landschaft ist also eine große Stärke der genetischen Algorithmen.

Kann man diese Optimierung auch für neuronale Netze einsetzen?

Genetische Algorithmen und Deep Learning

Künstliche neuronale Netze können selbständig lernen, Antworten auf bestimmte Arten von Fragen zu finden. Insbesondere im sich sehr rasant entwickelnden Bereich des Deep Learnings kann es dabei dazu kommen, dass die verwendeten Optimierungs-Algorithmen beim Versuch, die Fehlerfunktion zu minimieren, in einem lokalen Minimum „hängen“ bleiben und das „Lernen“ damit zum Erliegen kommt.

Zur Optimierung der einzelnen Neuronen-Gewichte in einem neuronalen Netz wird üblicherweise die sogenannte Backpropagation verwendet: Mit Hilfe verschiedener Techniken wird dabei für jedes einzelne Neuron der Anteil bestimmt, den dieses Neuron am gesamten Fehler hatte, und das Gewicht dieses Neurons für jeden seiner Input-Kanäle wird dann ein kleines Stück in die Richtung angepasst, die den Fehler minimieren soll.

Schon vor vielen Jahren gab es die Idee, alternativ genetische Algorithmen zur Optimierung von neuronalen Netzen einzusetzen. Damals war jedoch die zur Verfügung stehende Rechenleistung und dadurch auch die Erfahrung mit tiefen neuronalen Netzen nicht ausreichend vorhanden. Inzwischen gewinnt der Ansatz im Bereich des Deep Learnings jedoch zunehmend an Bedeutung.

Evolutions-Strategien zur Optimierung künstlicher neuronaler Netze

Die genetische Evolution von neuronalen Netzen funktioniert dann wie folgt: Es wird eine ganze Population von neuronalen Netzen mit zufällig initialisierten Neuronen-Gewichten gebildet. Diese Netze werden getestet, und diejenigen mit den besten Ergebnissen werden behalten und durch Klonen, Re-Kombination und Mutation weiter entwickelt, wie oben beschrieben.

Die Evolutions-Strategie bezieht sich hier also auf die Anpassung der Neuronen-Gewichte eines neuronalen Netzes. Dies hat den Vorteil, dass das Netz nicht oder nur sehr schwer in lokalen Minima hängen bleiben kann. Die Backpropagation wird durch die genetischen Algorithmen ersetzt, d.h. es wird nicht mehr bei einem einzelnen Netz jedes Neuron konsistent in eine Richtung angepasst und optimiert, sondern es werden parallel komplette neuronale Netze gezüchtet und weiter entwickelt.

Auf OpenAI wurde vor einigen Monaten eine Studie veröffentlicht, bei der versucht wurde, die Erfolge, die DeepMind beim Spielen von Atari-Games mit Deep Learning bzw. Reinforcement Learning erzielen konnte, mit durch genetische Algorithmen optimierten neuronalen Netze nachzustellen. Tatsächlich konnten die Forscher zeigen, dass die Ergebnisse der so „gezüchteten“ neuronalen Netze auf Augenhöhe mit denen von DeepMind waren.

atari evolution strategies

Ein weiterer sehr interessanter Aspekt von genetischen Optimierungs-Algorithmen für neuronale Netze ist die extrem einfache Parallelisierung der Optimierung – nämlich durch viele einzelne Instanzen, anstatt einer zentralen Trainings-Instanz.

Genetische Algorithmen und die Evolution von AI

Genetic Algorithms können im übrigen auch für das Hyperparameter Tuning von neuronalen Netzen eingesetzt werden. Um die optimale Konfiguration von Hyperparametern eines Deep Learning-Modells zu finden, sind oft viele und sehr zeitaufwendige Testreihen erforderlich. Durch den Einsatz von Evolutions-Strategien und genetischen Algorithmen konnten in einigen Fällen die Testaufwände um bis zum 80% reduziert werden.

Zusammenfassend lässt sich sagen, dass genetische Algorithmen zukünftig in vielen Bereichen eine stärkere Rolle spielen werden, und das durch das Übertragen von Evolutions-Strategien auf die Entwicklung von AI vielversprechende neue Arten von Training und „Zucht“ von künstlicher Intelligenz entstehen.


Grafik Beispiel für eine Funktion mit vielen lokalen Extremen: Public Domain

Grafik Atari: OpenAI