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

Часть серия на
Эволюционный алгоритм
Генетический алгоритм
Генетическое программирование

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

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

Примеры

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

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

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

OnePointCrossover.svg

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

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

TwoPointCrossover.svg

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

Единый кроссовер

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

Кроссовер для упорядоченных списков

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

Например, генетический алгоритм, решающий задача коммивояжера может использовать упорядоченный список городов для представления пути решения. Такая хромосома представляет собой верное решение только в том случае, если список содержит все города, которые должен посетить продавец. Использование вышеуказанных кроссоверов часто приводит к хромосомам, которые нарушают это ограничение. Таким образом, генетические алгоритмы, оптимизирующие упорядочение данного списка, требуют различных операторов кроссовера, которые позволят избежать создания неверных решений. Издано много таких кроссоверов:[1]

  1. частично отображенный кроссовер (PMX)
  2. велосипедный кроссовер (CX)
  3. оператор кроссовера заказов (OX1)
  4. оператор кроссовера на основе порядка (OX2)
  5. оператор кроссовера на основе позиции (POS)
  6. оператор рекомбинационного кроссовера голосования (VR)
  7. оператор кроссовера с переменным положением (AP)
  8. оператор последовательного конструктивного кроссовера (SCX)[нужна цитата ]

Другие возможные методы включают оператор реберной рекомбинации В качестве альтернативы для решения упомянутой проблемы можно использовать двойные хромосомы.[2]

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

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

  • Джон Холланд, Адаптация в естественных и искусственных системах, Пресса Мичиганского университета, Анн-Арбор, Мичиган. 1975 г. ISBN  0-262-58111-6.
  • Ларри Дж. Эшелман, Алгоритм адаптивного поиска CHC: как обеспечить безопасный поиск при использовании нетрадиционной генетической рекомбинации, в редакторе Грегори Дж. Э. Роулинза, Труды Первого семинара по основам генетических алгоритмов. страницы 265-283. Морган Кауфманн, 1991. ISBN  1-55860-170-8.
  • Томаш Д. Гвязда, Справочник по генетическим алгоритмам, том 1 Кроссовер для задач одноцелевой численной оптимизации, Томаш Гвязда, Ломянки, 2006. ISBN  83-923958-3-2.
  1. ^ Педро Ларраньяга и др., "Изучение байесовских сетевых структур путем поиска наилучшего упорядочивания с помощью генетических алгоритмов", IEEE Transactions on systems, man and cybernetics, Vol 26, No. 4, 1996
  2. ^ Риази, Амин (14 октября 2019 г.). «Генетический алгоритм и реализация двойной хромосомы для задачи коммивояжера». SN Прикладные науки. 1 (11). Дои:10.1007 / s42452-019-1469-1.

внешняя ссылка