next up previous contents
Nächste Seite: Die Eimerkette für regelbasierte Aufwärts: Potentiell relevante nicht-neuronale Methoden Vorherige Seite: Dynamische Programmierung   Inhalt

Genetische Algorithmen

Eine sehr unterschiedliche Art gesteuerter Suche erfreut sich in den letzten Jahren wachsender Beliebtheit. Genetische Algorithmen durchforsten den Suchraum auf eine Weise, die von der biologischen Evolution inspiriert ist.

In der Hollandschen Version [16] repräsentiert eine Menge (genannt der `Pool') von Bitsequenzen fester Länge $n$ sogenannte Genotypen. Jeder Genotyp entspricht einem durch ihn definierten Phänotyp. Jeder Phänotyp wird an einer zu lösenden Aufgabe getestet, und sein Genotyp erhält abhängig von der Güte der Performanz eine reelle Zahl, die sogenannte Fitness, zugesprochen.

Je höher die Fitness eines Genotyps, desto höher ist die Wahrscheinlichkeit, daß er nun am `Fortpflanzungsprozeß' teilnehmen darf. Dieser läuft wie folgt ab: Zwei Genotypen (erfolgreiche werden wie gesagt bevorzugt) tauschen `genetisches Material' in Form von Bitsubsequenzen aus. Dabei werden einfach eine Anzahl aufeinanderfolgender Bits in der einen Sequenz ersetzt durch die entsprechenden Bits der anderen. Gelegentlich kommt auch eine `Mutation' vor, wobei zufällig ausgewählte Bits durch ihr Komplement ersetzt werden. Mit den Mutationen wird ein exploratives Element in den Suchprozeß eingeführt.

Die auf diese Weise neu konstruierten Genotypen werden auf dem Umweg über ihre zugehörigen Phänotypen getestet. Solche mit hoher Fitness verdrängen nun aus dem Pool solche mit niedriger Fitness. Verschiedenste Verdrängungsstrategien können dabei zur Anwendung kommen.

Das Verfahren wird iteriert, bis ein Genotyp entstanden ist, der genügend hohe Fitness aufweist, oder bis ein sonstiges Abbruchkriterium erfüllt ist.

Auf neuronale Netze mit binären Gewichten läßt sich das Verfahren ohne große Umschweife anwenden. Auch falls jedes Gewicht nur endlich viele verschiedene potentielle Werte annehmen kann, findet man schnell anwendbare Varianten genetischer Algorithmen. Ein entsprechendes Verfahren wird im folgenden als neurogenetischer Algorithmus bezeichnet.

Trotz der Allgemeinheit neurogenetischer Algorithmen (sie sind ja nicht abhängig von Netztopologie oder Gradienteninformation) hat man bisher merkwürdigerweise nur azyklische Netze damit trainiert, und das lediglich anhand von im Prinzip einfachen Problemen, die der allgemeinen Natur des genetischen Algorithmus nicht gerecht werden. Das liegt vor allem daran, daß sich viele Forscher über die fundamentalen Unterschiede der verschiedenen Arten des Lernens noch nicht im klaren sind, und somit auch die damit verbundenen Schwierigkeiten nicht zu würdigen wissen. Es ist bestimmt unklug, mit einem genetischen Algorithmus in direkte Konkurrenz zu den viel `informierteren' Gradientenabstiegsverfahren treten zu wollen (z.B. bei Klassifikationsaufgaben) [30]. Geschickter wäre es, sich mit neurogenetischen Algorithmen an Problemen zu versuchen, bei denen ein Verfahren wie Back-Propagation von vornherein keine Chance hat. Das sind zum Beispiel Probleme, bei denen nur uninformierte Reinforcementsignale zur Auswertung zur Verfügung stehen. Gegenwärtig wird in der Forschungsgruppe TIGKI der TUM im Rahmen eines Fortgeschrittenenpraktikums die Anwendbarkeit neurogenetischer Algorithmen auf vollständig rekurrente Netzwerke für die adaptive zeitabhängige Steuerung einfacher physikalischer Prozesse untersucht.

Etwas allgemeine Kritik neurogenetischer Algorithmen basierend auf dem Hollandschen Prinzip kann man allerdings jetzt schon formulieren:

Zum einen sprechen die experimentellen Befunde dafür, daß genetische Algorithmen nicht gut funktionieren, wenn sehr viele Parameter zu adjustieren sind. Die Konsequenz für die oben beschriebenen neurogenetischen Algorithmen wäre, daß sie nur für sehr kleine Netze brauchbar wären. Ein Weg, die Anzahl der Parameter zu reduzieren, ist, von einem gegebenen neuronalen Algorithmus auszugehen und nur noch einige wenige Netzeigenschaften wie z.B. die Netzwerktopologie der Auswahl durch einen genetischen Algorithmus zu überlassen. Damit schränkt man sich natürlich auf solche Aufgaben ein, die der vorgegebene neuronale Algorithmus im Prinzip zu lösen imstande ist.

Zum anderen sind neurogenetische Algorithmen nicht einmal eingeschränkt lokal in Raum und Zeit. Jeder Genotyp entspricht einem vollständigen Netzwerk. Steigt die Netzwerkgröße, braucht man auch mehr Genotypen, um den Gesamtraum aller Gewichtskombinationen hinreichend abdecken zu können.

Schließlich (und mit dem letzten Punkt zusammenhängend) betonen genetische Algorithmen den Wettbewerb und vernachlässigen die Kooperation. Zwar kooperieren Bitsequenzen während der Lernphase durch gegenseitigen Austausch von Information. Das Ziel jedoch ist das universelle Genie, nämlich diejenige einzelne Sequenz, die der Lösung der Aufgabe entspricht. Zumindest die Hollandschen genetischen Algorithmen zielen in keiner Weise auf irgendeine Form der Arbeitsteilung nach der Lernphase.

Es wird schon einen Grund für die biologischen genetischen Algorithmen gegeben haben, irgendwann einmal die neuronalen Lernalgorithmen zu erfinden ...


next up previous contents
Nächste Seite: Die Eimerkette für regelbasierte Aufwärts: Potentiell relevante nicht-neuronale Methoden Vorherige Seite: Dynamische Programmierung   Inhalt
Juergen Schmidhuber 2003-02-20


Related links in English: Recurrent neural networks - Subgoal learning - Reinforcement learning and POMDPs - Reinforcement learning economies - Selective attention
Deutsche Heimseite