Кроссовер (генетический алгоритм)

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

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

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

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

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

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

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

Двухточечное и k-точечное пересечение

При двухточечном кроссовере две точки кроссовера выбираются случайным образом из родительских хромосом. Биты между двумя точками меняются местами между родительскими организмами.

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

Равномерный кроссовер

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

действительных

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

Для операторов скрещивания, представленных выше, и для большинства других операторов скрещивания для битовых строк считается, что они также могут применяться соответственно к целочисленным или действительным геномам, каждый ген которых состоит из целого или действительного числа. Вместо отдельных битов в дочерний геном просто копируются целые или вещественные числа. Потомство лежит на оставшихся углах гипертела, охватываемого двумя родителями. $P_{1}=(1.5,6,8)$ и $P_{2}=(7,2,1)$, как показано на сопроводительном изображении для трехмерного случая.

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

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

Промежуточная рекомбинация

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

В этом операторе рекомбинации значения аллелей дочернего генома $a_{i}$ образуются путем смешивания аллелей двух родительских геномов. $a_{i,P_{1}}$ и $a_{i,P_{2}}$:

$\alpha _{i}=\alpha _{i,P_{1}}\cdot \beta _{i}+\alpha _{i,P_{2}}\cdot \left(1-\beta _{i}\right)\quad {\mathsf {with}}\quad \beta _{i}\in \left[-d,1+d\right]$ случайным образом равномерно распределены по генам $i$

Выбор интервала $[-d,1+d]$ Это приводит к тому, что помимо внутренней части гипертела, охватываемой значениями аллелей родительских генов, под вопросом также находится определенная среда для диапазона значений потомства. Значение $0.25$ рекомендуется для $d$ чтобы противодействовать тенденции к снижению значений аллелей, которая в противном случае существует при $d=0$.

На соседнем рисунке для двумерного случая показан диапазон возможных новых аллелей двух образцовых родителей. $P_{1}=(2,6)$ и $P_{2}=(9,2)$ в промежуточной рекомбинации. Результат дискретной рекомбинации $C_{1}$ и $C_{2}$ также нанесены на график. Промежуточная рекомбинация удовлетворяет арифметическому вычислению значений аллелей детского генома, требуемому теорией виртуального алфавита. Дискретная и промежуточная рекомбинация используются в качестве стандарта в стратегии эволюции .

Кроссовер для перестановок

Для задач комбинаторных обычно используются перестановки , специально разработанные для геномов, которые сами являются перестановками множества . Базовый набор обычно представляет собой подмножество $\mathbb {N}$ или $\mathbb {N} _{0}$. Если для таких геномов используется 1- или n-точечное или равномерное кроссовер для целочисленных геномов, дочерний геном может содержать некоторые значения дважды, а другие могут отсутствовать. Это можно исправить путем генетической репарации , например, путем замены избыточных генов с позиционной точностью на недостающие из генома другого ребенка.

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

Далее в качестве примеров представлены два оператора кроссовера: частично отображенный кроссовер (PMX), основанный на TSP, и кроссовер порядка (OX1), предназначенный для перестановок на основе порядка. Второе потомство может быть произведено в каждом случае путем обмена родительскими хромосомами.

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

Оператор PMX был разработан как оператор рекомбинации для TSP-подобных проблем. Объяснение процедуры иллюстрируется примером:

Процедура		Пример		Пример хромосомы
		Пусть даны две перестановки одного и того же множества.		$P_{0}=\left(A,B,C,D,E,F,G,H\right)$ и $P_{1}=\left(C,G,E,A,F,H,B,D\right)$
Случайным образом выберите две точки кроссовера, образующие сегмент гена в $P_{0}$.		Здесь с позиции гена с 4 по 6.		$P_{0}=\left(A,B,C,{\underline {D,E,F}},G,H\right)$
Выделенный участок копируется в дочернюю хромосому в том же положении.		Открытые позиции обозначены знаками вопроса.		$P_{C}=\left(?,?,?,{\underline {D,E,F}},?,?\right)$
Ищите гены, которые не были скопированы в соответствующем сегменте $P_{1}$ начиная с первой точки пересечения. Для каждого найденного гена (называемого $m$), посмотрите в потомке, какой элемент (называемый $n$) было скопировано на свое место из $P_{0}$. Копировать $m$ на должность, которую занимает $n$ в $P_{1}$ если он не занят. В противном случае перейдите к следующему шагу.		Ген $A$ является первым некопированным геном в соответствующем сегменте $P_{1}$: $\left(...,A,F,H,...\right)$. Ген $D$ было скопировано из $P_{0}$ на своем месте в $P_{C}$.		$P_{C}=\left(?,?,?,{\underline {{\mathbf {D}},E,F}},?,?\right)$
		Позиция $D$ в $P_{1}$ это самое дальнее правое положение и $A$ будет помещен туда в $P_{C}$.		$P_{C}=\left(?,?,?,{\underline {D,E,F}},?,A\right)$
Если место, занятое $n$ в $P_{1}$ уже занят элементом $k$ в потомке, $m$ ставится на место, занимаемое $k$ в $P_{1}$.		Следующий ген в $\left(...,A,F,H,...\right)$ является $F$ и это уже скопировано в дочернюю хромосому. Таким образом, следующий ген, который нужно обработать, — это $H$. Его положение в потомстве будет положением $F$ в $P_{1}$. Однако это место уже занято геном $E$. Так $H$ копируется в позицию $E$ в $P_{1}$.		$P_{C}=\left(?,?,H,{\underline {D,E,F}},?,A\right)$
После обработки генов из выбранного сегмента в $P_{1}$, остальные позиции в потомстве заполняются генами из $P_{1}$ которые еще не скопированы, в порядке их появления. В результате получается готовый дочерний геном.		Гены, скопированные с $P_{1}$ являются $C,G$ и $B$.		$P_{C}=\left(C,G,H,{\underline {D,E,F}},B,A\right)$

Заказать кроссовер (OX1)

Кроссовер заказов возвращается к Дэвису в исходном виде и представлена ​​здесь в несколько обобщенном варианте, имеющем более двух точек пересечения. Он передает информацию об относительном порядке от второго родителя потомку. Сначала число и положение точек пересечения определяются случайным образом. Полученные последовательности генов затем обрабатываются, как описано ниже:

Процедура		Пример		Пример хромосомы
		Пусть даны две перестановки одного и того же множества.		$P_{0}=\left(A,B,C,D,E,F,G,H,I,J\right)$ и $P_{1}=\left(B,D,A,H,J,C,E,G,F,I\right)$
Случайным образом выберите сегменты гена в $P_{0}$.		Здесь два сегмента от положения гена с 1 по 2 и с 6 по 8.		$P_{0}=\left({\underline {A,B}},C,D,E,{\underline {F,G,H}},I,J\right)$
В качестве дочерней перестановки генерируется перестановка, содержащая выбранные сегменты гена $P_{0}$ в том же положении.		Открытые позиции обозначены знаками вопроса.		$P_{C}=\left(A,B,?,?,?,F,G,H,?,?\right)$
Остальные недостающие гены теперь также переносятся, но в том порядке, в котором они появляются в $P_{1}$.		Недостающие гены $P_{0}$ в примере это:		$P_{\text{missing}}=\left\{C,D,E,I,J\right\}$ $P_{{\text{in order from }}P_{1}}=\left(D,J,C,E,I\right)$
В результате получается законченный геном ребенка.		Перенесенные гены подчеркнуты:		$P_{C}=\left(A,B,{\underline {D,J,C}},F,G,H,{\underline {E,I}}\right)$

Помимо прочего, пересечение заказов хорошо подходит для планирования нескольких рабочих процессов при использовании в сочетании с 1- и n-точечным пересечением.

Дополнительные операторы скрещивания для перестановок

Со временем было предложено большое количество операторов скрещивания для перестановок, поэтому следующий список — лишь малая часть. За дополнительной информацией читатель отсылается к литературе.

1. велокроссовер (CX)
2. кроссовер на основе порядка (OX2)
3. позиционно-ориентированный кроссовер (POS)
4. краевая рекомбинация
5. рекомбинация голосования (VR)
6. кроссовер с переменным положением (AP)
7. максимальный консервирующий кроссовер (MPX)
8. слияние кроссовера (MX)
9. оператор последовательного конструктивного скрещивания (SCX)

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

См. также

• Эволюционный алгоритм
• Генетическое представление
• Фитнес-функция
• Отбор (генетический алгоритм)

Библиография

• Джон Холланд (1975). Адаптация в природных и искусственных системах , докторская диссертация, издательство Мичиганского университета , Анн-Арбор, Мичиган. ISBN   0-262-58111-6 .
• Швефель, Ханс-Пауль (1995). Эволюция и поиск оптимума . Нью-Йорк: Джон Уайли и сыновья. ISBN  0-471-57148-2 .
• Дэвис, Лоуренс (1991). Справочник по генетическим алгоритмам . Нью-Йорк: Ван Ностранд Рейнхольд. ISBN  0-442-00173-8 . ОСЛК   23081440 .
• Эйбен, А.Е.; Смит, Дж. Э. (2015). Введение в эволюционные вычисления . Серия естественных вычислений. Берлин, Гейдельберг: Springer. дои : 10.1007/978-3-662-44874-8 . ISBN  978-3-662-44873-1 . S2CID   20912932 .
• Ю, Синьцзе; Ген, Мицуо (2010). Введение в эволюционные алгоритмы . Инженерия принятия решений. Лондон: Спрингер. дои : 10.1007/978-1-84996-129-5 . ISBN  978-1-84996-128-8 .
• Бек, Томас; Фогель, Дэвид Б.; Михалевич, Збигнев, ред. (1999). Эволюционные вычисления. Том. 1. Основные алгоритмы и операторы . Бристоль: Паб Института физики. ISBN  0-585-30560-9 . OCLC   45730387 .

Внешние ссылки

• Группа новостей: Часто задаваемые вопросы по comp.ai.genetic — см. раздел о скрещивании (также известном как рекомбинация).