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

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

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

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

Представленный ниже список операторов ни в коем случае не является полным и служит, главным образом, примерной иллюстрацией этого типа диадических генетических операторов . Больше операторов и более подробную информацию можно найти в литературе. ^{[1] [2] [3] [4] [5]}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle \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]}$случайным образом равномерно распределены по генам ${\displaystyle i}$

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

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

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

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

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

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

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

Оператор PMX был разработан как оператор рекомбинации для TSP, подобных проблемам. ^{[13] [14]} Объяснение процедуры иллюстрируется примером:

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

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

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

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

Со временем было предложено большое количество операторов скрещивания для перестановок, поэтому следующий список — лишь малая часть. За дополнительной информацией читатель отсылается к литературе. ^{[1] [5] [14] [12]}

1. велокроссовер (CX) ^{[16] [14]}
2. кроссовер на основе порядка (OX2) ^{[5] [17]}
3. позиционный кроссовер (POS) ^{[5] [17]}
4. краевая рекомбинация ^{[18] [14]}
5. голосующая рекомбинация (VR) ^[12]
6. кроссовер с переменным положением (АП) ^[12]
7. максимальный консервирующий кроссовер (MPX) ^{[5] [19]}
8. слияние кроссовера (MX) ^{[5] [20]}
9. последовательный конструктивный оператор кроссовера (SCX) ^[21]

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

Смотрите также

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

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

• Джон Холланд (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. ОСЛК  45730387.

Рекомендации

1. Дэвис, Лоуренс (1991). Справочник по генетическим алгоритмам . Нью-Йорк: Ван Ностранд Рейнхольд. ISBN 0-442-00173-8. ОСЛК  23081440.
2. Эйбен, А.Э.; Смит, Дж. Э. (2015). «Представление, мутация и рекомбинация». Введение в эволюционные вычисления. Серия Natural Computing (2-е изд.). Берлин, Гейдельберг: Springer. стр. 49–78. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
3. Ю, Синьцзе; Ген, Мицуо (2010). «Кодирование и операторы». Введение в эволюционные алгоритмы. Инженерия принятия решений. Лондон: Спрингер. стр. 40–63. дои : 10.1007/978-1-84996-129-5. ISBN 978-1-84996-129-5. ОСЛК  654380156.
4. Ю, Синьцзе; Ген, Мицуо (2010). «Операторы вариации кода перестановки». Введение в эволюционные алгоритмы. Инженерия принятия решений. Лондон: Спрингер. стр. 285–299. дои : 10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.
5. Букер, Лашон Б.; Фогель, Дэвид Б.; Уитли, Даррелл; Анджелина, Питер Дж.; Эйбен, А.Е. (2000). «Рекомбинация». Ин Бек, Томас; Фогель, Дэвид Б.; Михалевич, Збигнев (ред.). Эволюционные вычисления. Том. 1. Основные алгоритмы и операторы. Бристоль: Паб Института физики. стр. 256–307. ISBN 0-585-30560-9. ОСЛК  45730387.
6. Сисверда, Гилберт (1989), Шаффер, JD (редактор), «Равномерное кроссовер в генетических алгоритмах», Труды 3-й Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско: Морган Кауфманн, стр. 2–9, ISBN 1558600663
7. Эйбен, AE; Смит, Дж. Э. (2015). «Операторы рекомбинации для действительного представления». Введение в эволюционные вычисления. Серия Natural Computing (2-е изд.). Берлин, Гейдельберг: Springer. стр. 65–67. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
8. Мюленбайн, Хайнц; Шлиркэмп-Воозен, Дирк (1993). «Прогнозирующие модели для генетического алгоритма селекционера I. Непрерывная оптимизация параметров». Эволюционные вычисления . 1 (1): 25–49. дои : 10.1162/evco.1993.1.1.25. ISSN  1063-6560. S2CID  16085506.
9. Голдберг, Дэвид Э. (1991). «Генетические алгоритмы с реальным кодом, виртуальные алфавиты и блокировка». Комплексная система . 5 (2): 139–167.
10. Стендер, Дж.; Хиллебранд, Э.; Кингдон, Дж. (1994). Генетические алгоритмы в оптимизации, симуляции и моделировании . Амстердам: IOS Press. ISBN 90-5199-180-0. ОСЛК  47216370.
11. Швефель, Ханс-Пол (1995). Эволюция и поиск оптимума. Нью-Йорк: Уайли. ISBN 0-471-57148-2. ОСЛК  30701094.
12. Ларраньяга, П.; Куиджперс, CMH; Мурга, Р.Х.; Инза, И.; Диздаревич, С. (1999). «Генетические алгоритмы решения задачи коммивояжера: обзор представлений и операторов». Обзор искусственного интеллекта . 13 (2): 129–170. дои : 10.1023/А: 1006529012972. S2CID  10284682.
13. Голдберг, Дэвид Э.; Лингл, Р. (1985), Грефенстетт, Джон Дж. (редактор), «Аллели, локусы и проблема коммивояжера», Труды Первой международной конференции по генетическим алгоритмам и их приложениям (ICGA) , Хиллсдейл, Нью-Джерси: Lawrence Erlbaum Associates, стр. 154–159, ISBN 0-8058-0426-9, OCLC  19702892
14. Эйбен, AE; Смит, Дж. Э. (2015). «Рекомбинация для представления перестановок». Введение в эволюционные вычисления. Серия Natural Computing (2-е изд.). Берлин, Гейдельберг: Springer. стр. 70–74. дои : 10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
15. Якоб, Уилфрид; Квинт, Александр; Стаки, Карл-Уве; Зюсс, Вольфганг (2008), Рудольф, Гюнтер; Янсен, Томас; Бёме, Никола; Лукас, Саймон (ред.), «Быстрое многоцелевое планирование заданий с ограниченными ресурсами с использованием гибридного эволюционного алгоритма», Параллельное решение проблем из природы – PPSN X , Берлин, Гейдельберг: Springer, vol. LNCS 5199, стр. 1031–1040, номер документа : 10.1007/978-3-540-87700-4_102, ISBN. 978-3-540-87699-1, получено 14 января 2023 г.
16. Оливер, IM; Смит, диджей; Холланд, Дж. (1987), Грефенстетт, Джон Дж. (редактор), «Исследование операторов скрещивания перестановок в задаче коммивояжера», Труды Второй международной конференции по генетическим алгоритмам и их приложениям (ICGA) , Хиллсдейл, Нью-Джерси: Lawrence Erlbaum Associates, стр. 224–230, ISBN. 978-0-8058-0158-3
17. Сисверда, Гилберт (1991). «Оптимизация расписания с использованием генетических алгоритмов». В Дэвисе, Лоуренс (ред.). Справочник по генетическим алгоритмам . Нью-Йорк: Ван Ностранд Рейнхольд. стр. 332–349. ISBN 0-442-00173-8. ОСЛК  23081440.
18. Уитли, Даррелл; Старквезер, Тимоти; Фукуэй, Д'Анн (1989), Шаффер, JD (редактор), «Проблемы планирования и путешествующие продавцы: оператор рекомбинации генетических краев», Труды 3-й Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско: Морган Кауфманн, стр. 133–140, ISBN. 1558600663
19. Джубера, Джон; Уитли, Даррелл (1994), Давидор, Юваль; Швефель, Ханс-Пауль; Мэннер, Рейнхард (ред.), «Расширенный корреляционный анализ операторов для задачи коммивояжера», Параллельное решение проблем из природы - PPSN III , Берлин, Гейдельберг: Springer, vol. 866, стр. 68–77, номер документа : 10.1007/3-540-58484-6_251, ISBN. 978-3-540-58484-1, получено 15 января 2023 г.
20. Блэнтон, Джо Л.; Уэйнрайт, Роджер Л. (1993), Форрест, Стефани (редактор), «Маршрутизация нескольких транспортных средств с ограничениями по времени и мощности с использованием генетических алгоритмов», Труды 5-й Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско: Морган Кауфманн, стр. 452–459, ISBN. 978-1-55860-299-1
21. Ахмед, Закир Хусейн (2000). Последовательная конструктивная выборка и связанные с ней подходы к комбинаторной оптимизации (доктор философии). Университет Тезпур, Индия.
22. Риази, Амин (14 октября 2019 г.). «Генетический алгоритм и двуххромосомная реализация задачи коммивояжера». С.Н. Прикладные науки . 1 (11). дои : 10.1007/s42452-019-1469-1 .

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

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