В генетических алгоритмов и эволюционных вычислений , кроссовер , также называемой рекомбинации , является генетический оператор используется для объединения генетической информации двух родителей для создания нового потомства. Это один из способов стохастического генерирования новых решений из существующей популяции, аналогичный кроссоверу, который происходит во время полового размножения в биологии . Решения также могут быть созданы путем клонирования существующего решения, что аналогично бесполому воспроизведению.. Вновь созданные решения обычно мутируют перед добавлением в популяцию.
Различные алгоритмы эволюционных вычислений могут использовать разные структуры данных для хранения генетической информации, и каждое генетическое представление может быть рекомбинировано с разными операторами кроссовера. Типичными структурами данных, которые могут быть рекомбинированы с помощью кроссовера, являются битовые массивы , векторы действительных чисел или деревья .
Примеры [ править ]
Традиционные генетические алгоритмы хранят генетическую информацию в хромосоме, представленной битовым массивом . Методы кроссовера для битовых массивов популярны и являются наглядным примером генетической рекомбинации .
Одноточечный кроссовер [ править ]
Точка на хромосомах обоих родителей выбирается случайным образом и обозначается как «точка пересечения». Биты справа от этой точки меняются местами между двумя родительскими хромосомами. Это приводит к появлению двух потомков, каждое из которых несет некоторую генетическую информацию от обоих родителей.
Двухточечный и k-точечный кроссовер [ править ]
При двухточечном кроссовере две точки кроссовера выбираются случайным образом из родительских хромосом. Биты между двумя точками меняются местами между родительскими организмами.
Двухточечный кроссовер эквивалентен выполнению двух одноточечных кроссоверов с разными точками кроссовера. Эту стратегию можно обобщить на k-точечный кроссовер для любого положительного целого k, выбирая k точек кроссовера.
Однородный кроссовер [ править ]
В однородном кроссовере, как правило, каждый бит выбирается из любого родителя с равной вероятностью. Иногда используются другие соотношения смешивания, в результате чего потомство наследует больше генетической информации от одного родителя, чем от другого.
Кроссовер для упорядоченных списков [ править ]
В некоторых генетических алгоритмах не все возможные хромосомы представляют собой допустимые решения. В некоторых случаях можно использовать специализированные операторы кроссовера и мутации, которые разработаны, чтобы избежать нарушения ограничений задачи.
Например, генетический алгоритм, решающий задачу коммивояжера, может использовать упорядоченный список городов для представления пути решения. Такая хромосома представляет собой верное решение только в том случае, если список содержит все города, которые должен посетить продавец. Использование вышеуказанных кроссоверов часто приводит к хромосомам, которые нарушают это ограничение. Таким образом, генетические алгоритмы, оптимизирующие упорядочение данного списка, требуют различных операторов кроссовера, которые позволят избежать генерации неверных решений. Было опубликовано много таких кроссоверов: [1]
- частично отображенный кроссовер (PMX)
- велосипедный кроссовер (CX)
- оператор кроссовера заказов (OX1)
- оператор кроссовера на основе порядка (OX2)
- оператор кроссовера на основе позиции (POS)
- оператор рекомбинационного кроссовера с голосованием (VR)
- оператор кроссовера с переменным положением (AP)
- оператор последовательного конструктивного кроссовера (SCX) [ необходима ссылка ]
- симулированный бинарный оператор кроссовера (SBX)
Другие возможные методы включают оператор рекомбинации краев . В качестве альтернативы для решения упомянутой проблемы можно использовать двойные хромосомы. [2]
См. Также [ править ]
- Эволюционные вычисления
- Генетический алгоритм
- Хромосома (генетический алгоритм)
- Мутация (генетический алгоритм)
- Приближение фитнеса
- Функция фитнеса
- Отбор (генетический алгоритм)
Ссылки [ править ]
- Джон Холланд, Адаптация в естественных и искусственных системах , Издательство Мичиганского университета , Анн-Арбор, Мичиган. 1975. ISBN 0-262-58111-6 .
- Ларри Дж. Эшелман, Алгоритм адаптивного поиска CHC: как обеспечить безопасный поиск при участии в нетрадиционной генетической рекомбинации , в редакции Грегори Дж. Э. Роулинза, Труды первого семинара по основам генетических алгоритмов. страницы 265-283. Морган Кауфманн, 1991. ISBN 1-55860-170-8 .
- Томаш Д. Гвязда, Справочник по генетическим алгоритмам Том 1 Кроссовер для одноцелевых задач численной оптимизации , Томаш Гвязда, Ломянки, 2006. ISBN 83-923958-3-2 .
- ^ Педро Ларраньяга и др., "Изучение байесовских сетевых структур путем поиска наилучшего упорядочения с помощью генетических алгоритмов", IEEE Transactions on systems, man and cybernetics, Vol 26, No. 4, 1996
- ^ Riazi Амин (14 октября 2019). «Генетический алгоритм и реализация двойной хромосомы к проблеме коммивояжера» . С.Н. Прикладные науки . 1 (11). DOI : 10.1007 / s42452-019-1469-1 .
Внешние ссылки [ править ]
- Группа новостей: comp.ai.genetic FAQ - см. Раздел о кроссовере (также известном как рекомбинация).
