Введение

Оператор, используемый для изменения генетической информации хромосом из поколения в поколение.

В генетических алгоритмах и эволюционных вычислениях кроссовер, также называемый рекомбинацией, – это генетический оператор, используемый для объединения генетической информации двух родительских особей с целью создания новых потомков. Это один из способов стохастического (вероятностного) получения новых решений из существующей популяции, аналогичный кроссоверу, происходящему при половом размножении в биологии. Решения также могут быть получены путем клонирования существующего решения, что аналогично бесполому размножению. Новые решения могут подвергаться мутациям перед добавлением в популяцию. Различные алгоритмы эволюционных вычислений могут использовать различные структуры данных для хранения генетической информации, и каждое генетическое представление может быть рекомбинировано с использованием различных операторов кроссовера. Типичными структурами данных, которые могут быть рекомбинированы с помощью кроссовера, являются битовые массивы, векторы вещественных чисел или деревья. Перечень операторов, представленный ниже, не является исчерпывающим и служит лишь иллюстративным примером данного типа бинарного генетического оператора. Более подробную информацию и другие операторы можно найти в специализированной литературе.

Пересечение для бинарных массивов

Традиционные генетические алгоритмы хранят генетическую информацию в хромосоме, представленной битовым массивом. Методы кроссовера для битовых массивов широко распространены и служат наглядным примером генетической рекомбинации.

Одноточечный кроссовер

Точка на хромосомах обоих родителей выбирается случайным образом и обозначается как "точка кроссинговера". Участки хромосом справа от этой точки обмениваются между двумя родительскими хромосомами. В результате получаются два потомка, каждый из которых несет в себе часть генетической информации от каждого из родителей.

Двухточечный и к-точечный кроссовер

В двухточечном кроссовере две точки кроссовера выбираются случайным образом из родительских хромосом. Участки между этими двумя точками меняются местами между родительскими организмами. Двухточечный кроссовер эквивалентен выполнению двух одноточечных кроссоверов с различными точками кроссовера. Эта стратегия может быть обобщена до k-точечного кроссовера для любого положительного целого числа k, выбирая k точек кроссовера.

Однородный кроссовер

В однородном кроссовере, как правило, каждый бит выбирается от одного из родителей с равной вероятностью. Иногда используются и другие коэффициенты смешивания, в результате чего потомство может наследовать больше генетической информации от одного родителя, чем от другого. В однородном кроссовере хромосома не делится на сегменты, а каждый ген рассматривается отдельно. По сути, для каждого гена определяется случайным образом, от какого родителя он будет унаследован.

Кроссовер для целых или реальных геномов

Для операторов кроссовера, представленных выше, и для большинства других операторов кроссовера для битовых строк, справедливо, что их также можно применить аналогичным образом к геномам, состоящим из целых или вещественных чисел, где каждый ген представляет собой целое или вещественное число. Вместо отдельных битов, целые или вещественные числа просто копируются в геном потомка. Потомки располагаются на оставшихся вершинах гипертела, образованного двумя родителями , как показано на сопроводительном изображении для трехмерного случая.

Дискретная рекомбинация

Если правила однородного кроссовера для битовых строк применяются при генерации потомков, это также называется дискретной рекомбинацией.

Пересечение для пермутаций

Для комбинаторных задач обычно используются пермутации, специально разработанные для геномов, которые сами являются пермутациями множества. Базовое множество обычно является подмножеством целых чисел или множества {1, …, n}. Если для таких геномов используется кроссовер в одной или n точках или однородный кроссовер для целочисленных геномов, то дочерний геном может содержать некоторые значения дважды, а другие могут отсутствовать. Это можно исправить с помощью генетического ремонта, например, заменой повторяющихся генов на отсутствующие из другого дочернего генома, сохраняя их позицию. Чтобы избежать генерации недопустимого потомства, были разработаны специальные операторы кроссовера для пермутаций, которые удовлетворяют основным требованиям к таким операторам, а именно, что все элементы исходной пермутации также присутствуют в новой, и изменяется только порядок. Можно различать комбинаторные задачи, где допустимы все последовательности, и задачи, где существуют ограничения в виде недопустимых частичных последовательностей. Хорошо известным представителем первого типа задач является задача коммивояжера (TSP), где цель состоит в том, чтобы посетить заданный набор городов ровно один раз по кратчайшему маршруту. Примером задачи с ограничениями является планирование нескольких рабочих процессов. Рабочие процессы включают ограничения на последовательность выполнения некоторых отдельных операций. Например, нельзя разрезать нить, пока в заготовке не будет просверлено соответствующее отверстие. Такие задачи также называют пермутациями, основанными на порядке. Далее в качестве примеров представлены два оператора кроссовера: частично отображаемый кроссовер (PMX), вдохновленный задачей коммивояжера, и кроссовер порядка (OX1), разработанный для пермутаций, основанных на порядке. Во втором случае потомка можно получить, поменяв местами родительские хромосомы.

Частично отображенный кроссовер (PMX)

Оператор PMX был разработан как оператор рекомбинации для задач, подобных TSP. Объяснение процедуры иллюстрируется примером: Процедура Пример Пример хромосомы Пусть даны две перестановки одного и того же набора, а и . Случайным образом выбираются две точки кроссовера, формирующие генный сегмент в . Здесь – от позиции гена 4 до 6. Выбранный участок копируется в дочернюю хромосому в том же положении. Свободные позиции обозначаются вопросительными знаками. Ищем гены, которые не были скопированы в соответствующем сегменте , начиная с первой точки кроссовера. Для каждого найденного гена (обозначим его ) ищем в потомке, какой элемент (обозначим его ) был скопирован на его место из , в позицию, занимаемую , если она свободна. В противном случае переходим к следующему шагу. Ген является первым нескопированным геном в соответствующем сегменте : Ген был скопирован из на его место в . Если место, занимаемое в , уже занято элементом в потомке, помещаем в место, занимаемое в . Следующий ген в – , и он уже был скопирован в дочернюю хромосому. Таким образом, следующим геном для обработки является . Его позиция в потомке будет позицией в . Однако это место уже занято геном , поэтому копируем в позицию в . После обработки генов из выбранного сегмента , оставшиеся позиции в потомке заполняются генами из , которые еще не были скопированы, в порядке их появления. В результате получается завершенный геном потомка. Гены , скопированные из и .