Rekombination von A,B

1. Adjazenzinformationen vereinigen und für jeden Knoten aufschreiben:

Adj(1)={2,5} {3,5}={2,3,5}

Adj(2)={1,3} {4,5}={1,3,4,5}

Adj(3)={2,4} {1,4}={1,2,4}

Adj(4)={3,5} {2,3}={2,3,5}

Adj(5)={1,4} {1,2}={1,2,4}

2. Einen Startknoten aus denen der "Eltern" wählen.

Hier wird S = 2 gewählt.

3. Den gerade verwendeten Knoten aus den Adjazenzmengen entfernen.

Neue Adjazenzmengen:

Adj(1)={3,5}

Adj(2)={1,3,4,5}

Adj(3)={1,4}

Adj(4)={3,5}

Adj(2)={1,4}

4. Aus der Menge an möglichen Nachfolgeknoten den bzw einen mit der niedrigsten Anzahl Nachfolgemöglichkeiten auswählen:

Alle kommen mit nun noch 2 möglichen Folgeknoten infrage. Hier wird Knoten 1 gewählt.

(Sollte kein Folgeknoten mehr zur Auswahl stehen, so muss ein zufälliger noch nicht verwendeter Knoten ausgewählt werden.)

5. Schritte 3 und 4 wiederholen, bis alle Knoten verwendet sind.

Endergebnis (Vorschlag): E=(2, 3, 1, 5, 4)

Mit der Rekombination von C,D kann analog verfahren werden. Ein mögliches Ergebnis lautet F=(3, 4, 5, 2, 1)

Mutation findet durch zufällige Auswahl von Start- und Endknoten eines Teilstückes und Inversion der Elementreihenfolge in diesem Teilstück statt.

z.B. für A mit Startknoten 1 und Endknoten 5 (Das Teilstück ist hier also gleich des gesamten Kandidaten): A'=(5, 4, 3, 2, 1)

oder für E mit Startknoten 3 und Endknoten 4: E'=(2, 4, 5, 1, 3)

Zur Bewertung einfach die Längen aus der Entfernungsmatrix addieren.

Länge(A)= 5 + 6 + 1 + 7 + 4 = 23

Aus den insgesamt 8 Lösungskandidaten die 4 optimalsten (geringster Weg) wählen.

Diese ausgewählten Kandidaten würden in einem Algorithmus erneut durch den Zylkus geschickt, sodass an die Optimallösung angenähert wird.