Войти
В генетических алгоритмах и эволюционных вычислений, кроссовер, также называемый рекомбинацией - это генетический оператор, используемый для объединения генетической информации двух родителей для создания нового потомства. Это один из способов стохастически генерировать новые решения из существующей популяции, аналогичный кроссоверу, который происходит во время полового размножения в биология. Решения также могут быть созданы путем клонирования существующего решения, что аналогично бесполому воспроизведению. Вновь созданные решения обычно мутируют перед добавлением в популяцию.
Различные алгоритмы в эволюционных вычислениях могут использовать разные структуры данных для хранения генетической информации, и каждое генетическое представление может быть рекомбинировано с разными операторами кроссовера. Типичными структурами данных, которые могут быть рекомбинированы с кроссовером, являются битовые массивы, векторы действительных чисел или деревья.
Традиционные генетические алгоритмы хранят генетическую информацию в хромосоме, представленной битовым массивом. Методы кроссовера для битовых массивов популярны и являются наглядным примером генетической рекомбинации.
Точка на хромосомах обоих родителей выбирается случайным образом и обозначается как «точка кроссовера». Биты справа от этой точки меняются местами между двумя родительскими хромосомами. В результате получается два потомка, каждое из которых несет некоторую генетическую информацию от обоих родителей.
При двухточечном кроссовере две точки кроссовера выбираются случайным образом из родительских хромосом. Биты между двумя точками меняются местами между родительскими организмами.
Двухточечный кроссовер эквивалентен выполнению двух одноточечных кроссоверов с разными точками кроссовера. Эту стратегию можно обобщить на k-точечный кроссовер для любого положительного целого k, выбирая k точек кроссовера.
В равномерном кроссовере, как правило, каждый бит выбирается из любого родителя с равной вероятностью. Иногда используются другие соотношения смешивания, в результате чего потомство наследует больше генетической информации от одного родителя, чем от другого.
В некоторых генетических алгоритмах не все возможные хромосомы представляют собой допустимые решения. В некоторых случаях можно использовать специализированные операторы кроссовера и мутации, которые разработаны, чтобы избежать нарушения ограничений задачи.
Например, генетический алгоритм, решающий задачу коммивояжера, может использовать упорядоченный список городов для представления пути решения. Такая хромосома представляет собой верное решение, только если список содержит все города, которые должен посетить продавец. Использование вышеуказанных кроссоверов часто приводит к хромосомам, которые нарушают это ограничение. Таким образом, генетические алгоритмы, оптимизирующие упорядочение данного списка, требуют различных операторов кроссовера, которые позволят избежать создания неверных решений. Было опубликовано много таких кроссоверов:
Другие возможные методы включают в себя оператор рекомбинации ребер. В качестве альтернативы, чтобы решить указанную проблему, можно использовать двойные хромосомы.
