[Diskussion] Genetische Programmierung
Ich hab gestern mal ein bisschen in den WikiBooks gestöbert und bin auf einen interessanten Artikel über die Genetische Programmierung am Beispiel der Turingmaschine" gestoßen. Darin werden in zwei Beispielen genetische Algorithmen erklärt. Das erste Beispiel ist ein OpenOffice.org-Makro, mit dem Das sogenannte Rucksackproblem gelöst werden soll. Heißt so viel wie dass man eine bestimmte Anzahl Gegenstände vorhanden sind, die alle ein Gewicht und einen (Nützlichkeits-)Wert haben. Ziel ist es, Gegenstände mit einem maximalen Gesamtgewicht (Im Beispiel 20 kg) und gleichzeitig einem möglichst hohen Wert zusammenzustellen. Theoretisch könnte man jede mögliche Kombination ausprobieren, was aber je nach Anzahl der Gegenstände Tage dauern würde. Stattdessen wird der von Darwin beschriebene Ablauf der Evolution nachgebildet, um eine optimale Lösung zu "züchten". Dazu wird jede Kombination als Bitkette dargestellt und diese Ketten dann miteinander gekreuzt, wobei immer nur die "bessere" Hälfte der Kombinationen gekreuzt wird. Die "schlechtere" Hälfte wird aussortiert.
Am Anfang wird eine beliebige Zahl von Ketten (am besten ein Vielfaches von 4) aus zufälligen Bits erzeugt.
Beispiel:
Code:
Jedes Bit steht für einen Gegenstand.
0 = nicht mitnehmen
1 = mitnehmen
Ketten vor der Kreuzung:
Bits Wert (von mir willkürlich bestimmt)
1: 0010001101 0,95
2: 1110111011 0,64
3: 1001101110 0,61
4: 1101011010 0,58
5: 1101101110 0,45
6: 1001101101 0,33
7: 1011111001 0,29
8: 1010110100 0,01
Zur Kreuzung werden die Elternketten zertrennt (z.B. in der Mitte, aber es sind auch mehrere Schnitte möglich) und eine Hälfte ausgetauscht.
Code:
Kreuzung von 1 und 2:
1: 00100 01101
2: 11101 11011
> 00100 11011
> 11101 01101
3 und 4 werden auch gekreuzt und 5 bis 8 gelöscht, so dass nach der Kreuzung wieder 8 Ketten vorhanden sind.
Um zu verhindern, dass nach wenigen Kreuzungen immer wieder die gleichen Ketten entstehen, kann einerseits die Stelle, an der die Ketten geschnitten werden verschoben werden. Oder aber man mutiert die Ketten. Nach einer zufälligen Zeitspanne wird ein Bitflip (aus 0 wird 1 und umgekehrt) an einer zufälligen Stelle durchgeführt.
Das ganze wird bis zu einer bestimmten Abbruchbedingung wiederholt. Diese Abbruchbedingung kann in diesem Fall etwa eine festgelegte Anzahl an Durchläufen, das erreichen eines bestimmten Werts oder ein Einbruch der Entwicklungsgeschwindigkeit sein. Den letzten Fall kann man allerdings auch ausgleichen, indem man Mutationen wahrscheinlicher macht.
Das zweite, in Java geschriebene Beispiel soll einem Computer beibringen, selbst simple Programme als "Turningmaschine" (ähnlich wie Brainfuck, aber simpler aufgebaut) zu schreiben. Dazu wird der Code als Bitkette dargestellt und mutiert. Um die Qualität des Codes zu messen, wird das Ergebnis mit einem Satz an erwarteten Ein- und Ausgaben verglichen. Wie das genau funktioniert, könnt ihr ja selber nachlesen.
In diesem Beispiel werden noch ein paar zusätzliche Funktionen zur Evolution eingebaut, die sich größtenteils an der Natur orientieren. So werden neue Ketten eine Zeit lang getrennt abgelegt, wo sie sich nicht kreuzen, aber dafür schneller mutieren. Auch die Mutation beschränkt sich nicht mehr auf einen Bitflip, sondern wird deutlich komplexer.
So, genug Theorie. Den Rest könnt ihr ja selber in der PDF-Datei oder im beigelegten Sourcecode nachlesen. Die Frage ist nur: Wofür ist das gut? Die beiden Beispiele sind wohl nicht gerade praxisnah. Das Rucksackproblem ist unter Rollenspielern zwar wohlbekannt, lässt sich in diesem Fall aber meistens von Hand besser lösen :D Auch das eigenständige Schreiben von Programmen als Turingmaschine nach Trial-And-Error-Verfahren macht nur bei simplen Sachen wie dem im Beispiel vorkommenden Unärrechner Sinn.
Der einzige Verwendungszweck, den ich mir vorstellen kann wäre die lernende KI, wo sich einzelne Taktikbruchstücke weiterentwickeln.
