Kinder erzeugen

In diesem Abschnitt beschäftigen wir uns schließlich mit dem offenen Punkt des Verfahrens, nämlich wie aus einem Elternpaar zwei Kinder erzeugt werden.

Auch dazu orientieren wir uns an Vorgängen in der Natur, genauer an der Genetik: Die Permutationen (bzw. Rundtouren) der Eltern werden als Chromosomen angesehen und die beiden Kinder berechnen sich aus den Chromosomen (Permutationen) ihrer Eltern.

Das genaue Vorgehen beschreiben wir nun anhand eines Beispiels zum folgenden Elternpaar:

Segmente tauschen

Zunächst wird bei beiden Eltern jeweils ein Segment gleicher Länge zufällig ausgewählt:

Der erste Schritt zur Erzeugung der Kinder ist es nun, genau diese Segmente zu tauschen:

Dabei wird rein zufällig entschieden, wie lang die zu tauschenden Segmente sind, im Beispiel wurden Segmente der Länge fünf gewählt. Es wird auch rein zufällig entschieden, an welcher Stelle die Segmente bei den Eltern beginnen. Dabei können die Segmente auch über die Ränder hinweg gewählt werden.

Positionen übertragen

Im nächsten Schritt werden alle Positionen der Eltern übertragen. Dabei werden jedoch diejenigen Zahlen (bzw. Orte) ausgelassen, die bereits im (getauschten) Segment vorhanden sind:

Beispiel: Bei der ersten Position des ersten Kindes kann die 4 nicht vom Elternteil übertragen werden, da dies zum Konflikt mit dem getauschten Segment führen würde (die 4 ist hier bereits vorhanden).

Das Weglassen bereits vorhandener Zahlen ist wichtig, da jeder Ort genau einmal besucht werden soll. Anderenfalls würde es zu einer nicht zulässigen Lösung bzw. Rundtour führen.

Positionen auffüllen

Schließlich sind die offenen Positionen aufzufüllen. Dabei werden jeweils die Zahlen verwendet, die bei den Eltern an der Stelle stehen, die zum Konflikt führen:

Beispiel: Da die 4 nicht an der ersten Position des ersten Kindes übertragen werden könnte, schauen wir, welche Zahl an der Position des Elternteils steht, bei der das Kind nun die 4 hat. Dies ist eine 7 und damit gibt es keinen Konflikt, daher wird entsprechend die erste Position des Kindes mit der 7 aufgefüllt.

Quiz

Erzeuge zwei Kinder gemäß der Vorgehensweise zuvor bezogen auf folgendes Elternpaar mit bereits zum Tausch ausgewählten Segmenten:

Welche Zahl gehört an die Position A?
1
2
3
4
5
6
7
8
Welche Zahl gehört an die Position B?
1
2
3
4
5
6
7
8
Welche Zahl gehört an die Position C?
1
2
3
4
5
6
7
8
Welche Zahl gehört an die Position D?
1
2
3
4
5
6
7
8
Ausblick