N-Point

Der N-Point Crossover-Operator ist der Standardoperator in den Genetischen Algorithmen. Das bedeutet jedoch nicht, dass er in seiner Grundform auch der effizienteste ist.

Dieser Operator arbeitet mit einer einstellbaren Anzahl $n$ von Bruchstellen zwischen 1 und (maximal) der Länge $l$ des Kindgenoms $G_K$. Es werden dann per Zufall $n$ voneinander verschiedene Sollbruchstellen innerhalb der Länge des Genoms ermittelt. An jeder Bruchstelle wird auf das Genom des jeweils nächsten Elternteils übergesprungen, um dessen Gene an das Kindgenom weiterzugeben.

Abbildung 5.10: N-Point Crossover bei 3 Eltern und 2 Bruchstellen

Als einfachste Form dieses Operators ist der 1-Point Crossover in der Literatur schon eingehend untersucht worden. Ein Ergebnis dieser Untersuchungen ist die Bestätigung der von Holland und Goldberg aufgestellten Theorie, dass der 1-Point Crossover Problemstellungen mit eng gekoppelten Building-Blocks bevorzugt. In solchen Fällen wurde durch Goldberg et al. 1991 empirisch nachgewiesen, dass Genetische Algorithmen Testprobleme mit diesem Kreuzungsoperator in einer Zeit proportional zu $l\cdot\log(N)$ gelöst haben, mit $l$ der Länge des Genoms [24]^5.2.