Кроссовер

Возможны отклонения от представленной в простом генетическом алгоритме (ГА) схемы вычислений.

Во-первых, допустимы схемы многоточечного кроссовера. В большинстве литературных источников рассматриваются одноточечные, двухточечные и однородные ГА.

В одноточечном алгоритме при кроссовере каждая из родительских хромосом делится на две части, которые далее рекомбинируются. В двухочечном алгоритме используются две точки разрыва и, следовательно, хромосомы делятся на три части. В однородном кроссовере случайным образом генерируется строка 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