Во-первых, допустимы схемы многоточечного
кроссовера. В большинстве литературных источников рассматриваются одноточечные, двухточечные и однородные ГА.
В одноточечном алгоритме при кроссовере каждая из родительских хромосом делится на две части, которые далее рекомбинируются. В двухочечном алгоритме используются две точки разрыва и, следовательно, хромосомы делятся на три части. В однородном кроссовере случайным образом генерируется строка B длиной D с двоичными значениями генов, где D -длина хромосомы. Если bi = 0 (bi

B, i

[1,D]), то i-е значение гена в первом потомке берется от первого родителя (во втором потомке — от второго родителя), если bi=1, то в первый потомок включается ген второго родителя (во второй потомок — от первого родителя).
Во-вторых, отметим ситуации, когда на состав
аллелей наложены некоторые дополнительные условия. Например, пусть в задаче разбиения графа число вершин в подграфах

и

должно быть

и

и пусть

-й аллель, равный 1, означает, что вершина

попадает в

, если же

-й аллель равен 0, то в

. Очевидно, что число единиц в
хромосоме должно равняться

, число нулей —

. Тогда при рекомбинации левый участок хромосомы берется от одного из родителей без изменений, а в правом участке (от другого родителя) нужно согласовать число единиц с

тем или иным способом.
Один из способов —
метод PMX (Partially Matched Crossover). Для иллюстрации PMX рассмотрим пример двухточечного кроссовера в задаче, когда в хромосоме должны присутствовать, причем только по одному разу, все значения
генов из заданного набора. Пусть в примере этот набор включает числа от 1 до 9.
В табл. 1 первые две строки представляют родительские хромосомы. Третья строка содержит хромосому одного из потомков, сгенерированного в результате применения двухточечного кроссовера (после второго и пятого
локусов). Полученная хромосома не относится к числу допустимых, так как в ней значения генов 1, 2 и 9 встречаются дважды, а значения 3, 4 и 5 отсутствуют. Четвертая строка показывает результат применения PMX. В этом методе выделяются сопряженные пары аллелей в одноименных локусах одной из рекомбинируемых частей. В нашем примере это пары (3 и 1), (4 и 9), (5 и 2). Хромосома потомка просматривается слева-направо; если повторно встречается некоторое значение, оно заменяется на сопряженное значение. Так, в примере в локусах 3, 5 и 9 повторно встречающиеся аллели 1, 2 и 9 последовательно заменяются на значения 3, 5 и 4.
Таблица 1
1 | 2 | . | 3 | 4 | 5 | . | 6 | 7 | 8 | 9 |
3 | 7 | . | 1 | 9 | 2 | . | 4 | 8 | 6 | 5 |
1 | 2 | . | 1 | 9 | 2 | . | 6 | 7 | 8 | 9 |
1 | 2 | . | 3 | 9 | 5 | . | 6 | 7 | 8 | 4 |