Es werden zufällig je zwei Individuen ausgewählt und mit ihnen ein Kreuzen der "Gene" durchgeführt. Beim tsp wählt man z.B. zwei Positionen in den Touren aus und tauscht deren Verlauf zwischen den beiden Touren aus.
Gerade die mögliche ungezielte Veränderung von Individuen durch die beiden Schritte Mutation und Kreuzen ist wichtig für die Lösung von Suchproblemen mit Genetischen Algorithmen, da sie uns die Möglichkeit gibt, das Problem des Hängenbleibens in lokalen Maxima zu vermeiden.
Beim crossing over werden zwischen zwei verschiedenen Individuen Gene ausgetauscht! Daher erfolgt in diesem Fall an zwei Stellen eine zufällige Auswahl:
Der Vorgang des crossing over ist im Programm für die Lösung des tsp sehr viel schwieriger zu realisieren als der vorige Schritt. Das Problem ist, dass eine Tour beim tsp nur zulässig ist, wenn sie jede Stadt genau einmal enthält. Die Gen - Information steckt also nicht darin, welche Städte in der Tour enthalten sind, sondern in welcher Reihenfolge.
Wenn nun also aus der einen Tour ein Tourenabschnitt in die andere übernommen wird, dann muss man davon ausgehen, dass in diesem Abschnitt sowohl Städte enthalten sind, die in dem ersetzten Abschnitt liegen, als auch Städte, die in dem nicht zu ersetzenden liegen. Und für die gilt nun, dass man sie daraus entfernen muss.
Will man das verständlich machen, muss man sich genauer mit der verwendeten Datenstruktur beschäftigen. Dafür gibt es zwar verschiedene Möglichkeiten, unter Scheme ist aber eine Liste naheliegend. Es bleibt noch eine Frage zu klären: Wie gewährleistet man die Rundtour ? Eigentlich stellt unsere Datenstruktur eine Ringliste dar. (siehe das Bild auf der vorigen Seite)
Das läßt sich in Scheme zwar auch als Datenstruktur realisieren, Ringlisten sind aber nicht einfach zu handhaben, sodass man eher bei einer einfachen Liste bleiben wird. Die Ankopplung kann man nun entweder dadurch realisieren, dass man das erste Element der Liste (die Startstadt) zwangsweise an das Ende noch einmal setzt, oder dass man die einfache Liste so behandelt, als wäre es so. In jedem Fall sind Tauschvorgänge für die Startstadt entweder unzulässig oder sinnlos und sollten im Programm unterbunden werden.
Erläuterung des crossing over am Beispiel:
(A B C D E F G H I J K L) wird gekreuzt mit (A K B D L C E F I J H G) zwischen den Positionen 3 und 6:
A | B | C | D | E | F | G | H | I | J | K | L |
A | K | B | D | L | C | E | F | I | J | H | G |
würde zunächst einmal bei der ersten Tour ergeben:
A | B | B | D | L | C | G | H | I | J | K | L |
Das ist aber wegen der grün markierten Städte nicht zulässig. Die Lösung ist aber relativ einfach zu finden: Diese Städte müssen durch die (rot markierten) , die nun nicht mehr auftauchen ersetzt werden. Dafür gibt es verschiedene Varianten, eine wäre:
A | E | B | D | L | C | G | H | I | J | K | F |
und nach dem selben Verfahren entsprechend die andere Tour:
A | K | C | D | E | F | B | L | I | J | H | G |
spielt noch an einer weiteren Stelle eine wichtige Rolle: Für die beiden Prozesse Mutation und crossing over werden Wahrscheinlichkeiten festgelegt, mit deren Veränderung wesentlicher Einfluß auf die Entwicklung der Generationenfolge genommen werden kann. Mit ihnen wird festgelegt, welcher Anteil der Individuen mutiert wird oder welcher Anteil an einem crossing over teilnimmt.