Nachdem wir im letzten Artikel Individuen anhand eines Selektionsverfahren ausgewählt und in einen Marting Pool übertragen haben, wollen wir uns heute anschauen wie man mit Rekombinationsverfahren aus diesen Individuen Nachkommen für die neue Generation erzeugt.
Inhaltsverzeichnis
Rekombinationsverfahren im Allgemeinen
Bei dem Rekombinationsverfahren (Crossover) handelt es sich um das wahrscheinlich wichtigste Verfahren im Kontext der Genetischen Algorithmen. Bei der Rekombination werden aus zwei Individuen der Elterngeneration durch Kopieren von Genen die einzelnen Nachkommen für die nächste Generation erzeugt.
Wichtig hierbei ist, dass mit dem Rekombinationsverfahren nur ein Pool an Nachkommen generiert werden. Welche davon wirklich in die neue Generation übernommen werden, wird mit einem sogenannten Ersetzungsschema festgelegt.
Im Zuge meines Projektes habe ich mir die folgenden fünf Verfahren angeschaut. Die fett gedruckten sind die Verfahren, welche ich in C# implementiert habe.
- One-Point-Crossover
- N-Point-Crossover
- Template-Crossover
- Uniform-Crossover
- Shuffle-Crossover
Eine kurze Erklärung werde ich zu jedem Verfahren geben.
One-Point-Crossover
Beim One-Point-Crossover wird anhand einer Zufallszahl bestimmt, an welcher Stelle der Genpool der Elternteile getrennt wird. In dem folgenden Bild ist die Zufallszahl 5.
Der erste der beiden erzeugten Nachkommen erhält den ersten Teil der Chromosomen des ersten Elternteils und den Teil vom Schnittpunkt des zweiten Chromosoms. Der zweite Nachwuchs erhält die restlichen Gene, d.h. den ersten Teil des zweiten Elternteils und den zweiten Teil des ersten Elternteils.
Eine Implementierung in C# sieht wie folgt aus:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 | public void OnePointCrossover(GameObject P1 , GameObject P2, int brainsize){ int r1 = Random.Range (0, population.MartingPool.Length ); int r2 = Random.Range (0, population.MartingPool.Length ); int r3 = Random.Range (0, brainsize); for( int i = 0; i < brainsize; i++) { if (i < r3){ //Child 1 P1.GetComponent<Player>().brain[i][0] = population.MartingPool[r1].GetComponent<Player>().brain[i][0]; P1.GetComponent<Player>().brain[i][1] = population.MartingPool[r1].GetComponent<Player>().brain[i][1]; P1.GetComponent<Player>().brain[i][2] = population.MartingPool[r1].GetComponent<Player>().brain[i][2]; //Child 2 P2.GetComponent<Player>().brain[i][0] = population.MartingPool[r2].GetComponent<Player>().brain[i][0]; P2.GetComponent<Player>().brain[i][1] = population.MartingPool[r2].GetComponent<Player>().brain[i][1]; P2.GetComponent<Player>().brain[i][2] = population.MartingPool[r2].GetComponent<Player>().brain[i][2]; } if (i >= r3){ //Child 1 P1.GetComponent<Player>().brain[i][0] = population.MartingPool[r2].GetComponent<Player>().brain[i][0]; P1.GetComponent<Player>().brain[i][1] = population.MartingPool[r2].GetComponent<Player>().brain[i][1]; P1.GetComponent<Player>().brain[i][2] = population.MartingPool[r2].GetComponent<Player>().brain[i][2]; //Child 2 P2.GetComponent<Player>().brain[i][0] = population.MartingPool[r1].GetComponent<Player>().brain[i][0]; P2.GetComponent<Player>().brain[i][1] = population.MartingPool[r1].GetComponent<Player>().brain[i][1]; P2.GetComponent<Player>().brain[i][2] = population.MartingPool[r1].GetComponent<Player>().brain[i][2]; } } } |
N-Point-Crossover
Beim N-Point-Crossover gibt es im Gegensatz zur One-Point-Crossover mehrere Kreuzungspunkte. Das heißt, dass Eltern Individuum wird an mehreren stellen zerschnitten.
Das erste Kind erhält die Gene des ersten Elternteils bis zum ersten Kreuzungspunkt, dann die entsprechenden Gene des zweiten Elternteils bis zum nächsten Kreuzungspunkt. Nun werden die Chromosomen des ersten Elternteils wieder übernommen und so weiter. Das zweite Kind erhält die Chromosomen des anderen Elternteils auf die gleiche Weise.
Eine Implementierung in C# könnte dann so aussehen:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | public void TwoPointCrossover(GameObject P1 , GameObject P2, int brainsize){ int r1 = Random.Range (0, population.MartingPool.Length ); //MartingPool Gene 1 int r2 = Random.Range (0, population.MartingPool.Length ); //MartingPool Gene 2 int r3 = Random.Range (0, brainsize); //Split Point 1 int r4 = Random.Range (0, brainsize); //Split Point 2 if (r3 > r4){ int r = r3; r3 = r4; r4 = r; } for( int i = 0; i < brainsize; i++){ if (r3 < i && i < r4){ //Child 1 P1.GetComponent<Player>().brain[i][0] = population.MartingPool[r2].GetComponent<Player>().brain[i][0]; P1.GetComponent<Player>().brain[i][1] = population.MartingPool[r2].GetComponent<Player>().brain[i][1]; P1.GetComponent<Player>().brain[i][2] = population.MartingPool[r2].GetComponent<Player>().brain[i][2]; //Child 2 P2.GetComponent<Player>().brain[i][0] = population.MartingPool[r1].GetComponent<Player>().brain[i][0]; P2.GetComponent<Player>().brain[i][1] = population.MartingPool[r1].GetComponent<Player>().brain[i][1]; P2.GetComponent<Player>().brain[i][2] = population.MartingPool[r1].GetComponent<Player>().brain[i][2]; } else { P1.GetComponent<Player>().brain[i][0] = population.MartingPool[r1].GetComponent<Player>().brain[i][0]; P1.GetComponent<Player>().brain[i][1] = population.MartingPool[r1].GetComponent<Player>().brain[i][1]; P1.GetComponent<Player>().brain[i][2] = population.MartingPool[r1].GetComponent<Player>().brain[i][2]; //Child 2 P2.GetComponent<Player>().brain[i][0] = population.MartingPool[r2].GetComponent<Player>().brain[i][0]; P2.GetComponent<Player>().brain[i][1] = population.MartingPool[r2].GetComponent<Player>().brain[i][1]; P2.GetComponent<Player>().brain[i][2] = population.MartingPool[r2].GetComponent<Player>().brain[i][2]; } } } |
Template-Crossover
Bei diesem Verfahren wird zunächst ein Template zufällig über die Länge der Individuen erzeugt. Dieses Template wird mittels 0 und 1 dargestellt. Das erste Kind erhält für jedes 1 in der Vorlage das entsprechende Allel vom ersten Elternteil und für jedes 0 vom zweiten. Beim zweiten Kind wird das Verhalten bei 0 und 1 umgekehrt.
Uniform-Crossover
Beim Uniform Crossover wird für jede einzelne Stelle geprüft, ob es zwischen den beiden Elternteilen ausgetauscht wird oder nicht. Das ganze wird durch einen Wahrscheinlichkeitswert bestimmt.
Shuffle-Crossover
Bei diesem Kreuzungsverfahren werden die Gene der Eltern zunächst durchnummeriert und dann gemischt. Eine Einpunkt- oder N-Punkt-Weiche wird nun auf den gemischten Individuen durchgeführt. Schließlich werden die Gene entsprechend ihrer Nummerierung neu angeordnet.
Den gesamten Quellcode könnt ihr in meinem GitHub Projekt einsehen =)
Schreibe einen Kommentar