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

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

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

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

Список операторов, представленный ниже, ни в коем случае не является полным и служит в основном в качестве примерной иллюстрации этого типа диадического генетического оператора . Больше операторов и больше подробностей можно найти в литературе. ^{[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}=(3,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. кроссовер с чередующимися позициями (AP) ^[12]
7. максимальный консервантный кроссовер (MPX) ^{[5] [19]}
8. кроссовер слияния (MX) ^{[5] [20]}
9. последовательный конструктивный оператор кроссинговера (SCX) ^[21]

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

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

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

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

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

Ссылки

1. Дэвис, Лоуренс (1991). Справочник по генетическим алгоритмам . Нью-Йорк: Van Nostrand Reinhold. ISBN 0-442-00173-8. OCLC  23081440.
2. Эйбен, AE; Смит, JE (2015). «Представление, мутация и рекомбинация». Введение в эволюционные вычисления. Серия «Естественные вычисления» (2-е изд.). Берлин, Гейдельберг: Springer. стр. 49–78. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
3. Ю, Синьцзе; Ген, Мицуо (2010). «Кодирование и операторы». Введение в эволюционные алгоритмы. Принятие решений. Лондон: Springer. С. 40–63. doi :10.1007/978-1-84996-129-5. ISBN 978-1-84996-129-5. OCLC  654380156.
4. Ю, Синьцзе; Ген, Мицуо (2010). «Операторы вариации для кода перестановки». Введение в эволюционные алгоритмы. Инженерия принятия решений. Лондон: Springer. С. 285–299. doi :10.1007/978-1-84996-129-5. ISBN 978-1-84996-128-8.
5. Букер, Лэшон Б.; Фогель, Дэвид Б.; Уитли, Даррелл; Анджелина, Питер Дж.; Эйбен, AE (2000). «Рекомбинация». В Бэк, Томас; Фогель, Дэвид Б.; Михалевич, Збигнев (ред.). Эволюционные вычисления. Том 1, Основные алгоритмы и операторы. Бристоль: Издательство Института физики. С. 256–307. ISBN 0-585-30560-9. OCLC  45730387.
6. Syswerda, Gilbert (1989), Schaffer, JD (ред.), «Равномерный кроссовер в генетических алгоритмах», Труды 3-й Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско: Morgan Kaufmann, стр. 2–9, ISBN 1558600663
7. Eiben, AE; Smith, JE (2015). «Операторы рекомбинации для представления вещественных чисел». Введение в эволюционные вычисления. Серия «Естественные вычисления» (2-е изд.). Берлин, Гейдельберг: Springer. стр. 65–67. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
8. Мюленбейн, Хайнц; Шлиеркамп-Фузен, Дирк (1993). «Прогностические модели для генетического алгоритма селекционера I. Непрерывная оптимизация параметров». Эволюционные вычисления . 1 (1): 25–49. doi :10.1162/evco.1993.1.1.25. ISSN  1063-6560. S2CID  16085506.
9. Голдберг, Дэвид Э. (1991). «Реально-кодированные генетические алгоритмы, виртуальные алфавиты и блокировка». Complex Syst . 5 (2): 139–167.
10. Стендер, Дж.; Хиллебранд, Э.; Кингдон, Дж. (1994). Генетические алгоритмы в оптимизации, моделировании и имитации . Амстердам: IOS Press. ISBN 90-5199-180-0. OCLC  47216370.
11. Швефель, Ганс-Пауль (1995). Эволюция и поиск оптимума. Нью-Йорк: Wiley. ISBN 0-471-57148-2. OCLC  30701094.
12. Larrañaga, P.; Kuijpers, CMH; Murga, RH; Inza, I.; Dizdarevic, S. (1999). «Генетические алгоритмы для задачи коммивояжера: обзор представлений и операторов». Artificial Intelligence Review . 13 (2): 129–170. doi :10.1023/A:1006529012972. S2CID  10284682.
13. Голдберг, Дэвид Э.; Лингл, Р. (1985), Грефенстет, Джон Дж. (ред.), «Аллели, локусы и задача коммивояжера», Труды Первой международной конференции по генетическим алгоритмам и их приложениям (ICGA) , Хиллсдейл, Нью-Джерси: Lawrence Erlbaum Associates, стр. 154–159, ISBN 0-8058-0426-9, OCLC  19702892
14. Eiben, AE; Smith, JE (2015). «Рекомбинация для представления перестановок». Введение в эволюционные вычисления. Серия Natural Computing (2-е изд.). Берлин, Гейдельберг: Springer. стр. 70–74. doi :10.1007/978-3-662-44874-8. ISBN 978-3-662-44873-1. S2CID  20912932.
15. Якоб, Вильфрид; Квинте, Александр; Стаки, Карл-Уве; Зюсс, Вольфганг (2008), Рудольф, Гюнтер; Янсен, Томас; Бёме, Никола; Лукас, Саймон (ред.), «Быстрое многоцелевое планирование заданий для ограниченных ресурсов с использованием гибридного эволюционного алгоритма», Параллельное решение задач из природы – PPSN X , т. LNCS 5199, Берлин, Гейдельберг: Springer, стр. 1031–1040, doi :10.1007/978-3-540-87700-4_102, ISBN 978-3-540-87699-1, получено 2023-01-14
16. Оливер, IM; Смит, DJ; Холланд, J. (1987), Грефенстет, Джон Дж. (ред.), «Исследование операторов перестановочного кроссовера в задаче коммивояжера», Труды Второй международной конференции по генетическим алгоритмам и их приложениям (ICGA) , Хиллсдейл, Нью-Джерси: Lawrence Erlbaum Associates, стр. 224–230, ISBN 978-0-8058-0158-3
17. Syswerda, Gilbert (1991). «Оптимизация расписания с использованием генетических алгоритмов». В Davis, Lawrence (ред.). Справочник по генетическим алгоритмам . Нью-Йорк: Van Nostrand Reinhold. стр. 332–349. ISBN 0-442-00173-8. OCLC  23081440.
18. Уитли, Даррелл; Старквезер, Тимоти; Фукуэй, Д'Энн (1989), Шаффер, Дж. Д. (ред.), «Проблемы планирования и коммивояжеры: оператор рекомбинации генетических ребер», Труды 3-й Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско: Morgan Kaufmann, стр. 133–140, ISBN 1558600663
19. Dzubera, John; Whitley, Darrell (1994), Davidor, Yuval; Schwefel, Hans-Paul; Männer, Reinhard (ред.), «Расширенный корреляционный анализ операторов для задачи коммивояжера», Parallel Problem Solving from Nature — PPSN III , т. 866, Berlin, Heidelberg: Springer, стр. 68–77, doi :10.1007/3-540-58484-6_251, ISBN 978-3-540-58484-1, получено 2023-01-15
20. Блэнтон, Джо Л.; Уэйнрайт, Роджер Л. (1993), Форрест, Стефани (ред.), «Маршрутизация нескольких транспортных средств с ограничениями по времени и пропускной способности с использованием генетических алгоритмов», Труды 5-й Международной конференции по генетическим алгоритмам (ICGA) , Сан-Франциско: Morgan Kaufmann, стр. 452–459, ISBN 978-1-55860-299-1
21. Ахмед, Закир Хуссейн (2000). Последовательная конструктивная выборка и связанные с ней подходы к комбинаторной оптимизации (PhD). Университет Тезпур, Индия.
22. Риази, Амин (14 октября 2019 г.). «Генетический алгоритм и реализация задачи коммивояжера на основе двух хромосом». SN Applied Sciences . 1 (11). doi : 10.1007/s42452-019-1469-1 .

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

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