Der genetische Algorithmus - ein kurzer Überblick
Befor du genetische Algorithmen einsetzen kannst um mit ihnen Probleme zu lösen, muss ein Weg gefunden werden alle potentiell möglichen Lösungen zu codieren. Dies könnte in Form eines aus Gleitzahlwerten bestehender String sein, aber auch, der üblichere Weg, ein aus Binären Zahlen bestehender String. Ich werde diesen Binär-String von nun an Chromosom nennen. Ein typisches Chromosom könnte in etwas so aussehen:
10010101110101001010011101101110111111101
(Keine Angst, wenn nichts von alledem für dich im Moment Sinn ergibt, es wird dir bald alles etwas klarer werden. Solange entspann dich und lass dich berieseln.)
Am Anfang eines genetischen Algorithmus muss eine große Population von zufällig generierten Chromosomen erzeugt werden. Jedes einzelne stellt decodiert eine eigene Lösung zu unserem Problem dar. Sagen wir es gibt zu Anfang N Chromosome in unserer Population. Dann werden folgende Schritte solange wiederholt, bis eine Lösung für unser Problem gefunden wurde
Teste jedes Chromosom wie gut es darin ist, das gestellte Problem zu lösen und teile ihm eine entsprechende Fitness Punktzahl zu. Die Fitness Punktzahl ist ein Maß, das angibt wie gut das Chromosom darin ist, das gestellte Problem zu lösen.
Wähle zwei Chromosome der Population aus. Die warscheinlichkeit, dass ein Chromosom dabei gewählt wird ist proportinal zur Fitness des Chromosoms. Die Roulette Rad Selektion ist eine gern benutzte Methode.
Abhängig von der Rekombinationsrate (Anm.d.Ü.: Der Autor wählte hier Ursprünglich den Begirff der "Crossover"-Rate, da aber bereits früher von einer "Recombination" die Rede war, fand ich es sinnvoll den Begriff beizubehalten), rekombiniere die Bits von beiden Chromosomen an einer zufällig gewählten Stelle.
Gehe durch die Bits der gewählten Chromosome und negiere den Wert der Bits abhängig von der Mutationsrate.
Gehe alle Schritte erneut durch, bis eine neue Population mit N Mitgliedern entstanden ist.
Mit der Roulette Rad auswahl ist es möglich einzelne Chromosome in proportinaler Abhängigkeit ihrer Fitness aus der Population auszuwählen. Es wird nicht garantiert, dass der das Fitteste Chromosom in die nächste Generation weiter geht, aber es besteht eine sehr gute Chance, dass es das wird. Und so funktioniert's:
Stell dir vor, dass die Gesamt-Fitness der Population ein Kreisdiagramm oder ein Roukette Rad darstellt. Nun bekommt jedes Mitglied der Population ein Stückchen aus dem Rad zugewiesen. Die größe dieses Stückchen ist proportinal zur Fitness Punktzahl des Chromosoms. zB: je fitter ein Chromosom ist, desto größer ist das Stückchen, dass ihm zugewiesen ist. Nun musst du nurnoch das Rad "drehen", um das Chromosom auszuwählen an dessen Stückchen der Scheibe es anhält.
Die Rekombinationsrate ist einfach die Warscheinlichkeit, mit der zwei Chromosome ihre Bits austauschen. Ein guter Wert liegt bei etwa 7.0. Rekombination wird vollführt indem eine zufällige Stelle im Chromosom ausgewählt hinter welcher die Chromosome einfach alle Bits miteinander austauschen.
zB haben wir hier zwei Chromosome
10001001110010010
01010001001000011
Wir wählen einen zufälligen Wert innerhalb der Länge der Chromosome, sagen wir 9, und tauschen einfach alle Bits dahinter aus
aus dem von oben wird dann:
10001001101000011
01010001010010010
Dabei handelt es sich um die Warscheinlichkeit mit der ein Bit in einem Chromosom sich umkehrt (0 wird zu 1 und 1 zu 0). Normalerweise wird hier ein sehr geringer Wert gewählt, zB 0.001
Jedesmal wenn ein Chromosomenpaar aus der Population ausgewählt wird, wird erst geprüft ob eine Rekombination stattfinden soll und dann durchläuft der Algorithmus die gesamte Länge jedes Chromsomes und lässt die Bits mutieren, falls das erwünscht ist.