Эффективность кроссовера в генетических алгоритмах
Я реализовал ряд генетических алгоритмов, чтобы решить множество проблем. Однако я все еще скептически отношусь к полезности кроссовера / рекомбинации.
Я обычно сначала внедряю мутацию, прежде чем внедрить кроссовер. И после того, как я внедряю кроссовер, я обычно не вижу значительного ускорения, с которым генерируется хорошее решение-кандидат, по сравнению с простым использованием мутации и введением нескольких случайных особей в каждом поколении для обеспечения генетики.
Конечно, это может быть связано с плохим выбором функции кроссовера и / или вероятностями, но я хотел бы получить некоторые конкретные объяснения / доказательства того, почему / не улучшает ли кроссовер GA. Были ли какие-либо исследования по этому поводу?
Я понимаю причину этого: кроссовер позволяет объединить сильные стороны двух людей в одного человека. Но для меня это все равно, что сказать, что мы можем спариться с ученым и ягуаром, чтобы получить умный и быстрый гибрид.
РЕДАКТИРОВАТЬ: В ответе McDowella, он упомянул, как найти случай, когда переход может улучшить при восхождении на холм из нескольких начальных точек, нетривиально. Может ли кто-нибудь уточнить этот момент?
6 ответов
Вы правы, скептически относясь к операции кроссовера. Существует статья под названием "Об эффективности кроссовера в моделируемой эволюционной оптимизации" (Fogel and Stayton, Biosystems 1994). Это доступно бесплатно в 1.
Кстати, если вы еще этого не сделали, я рекомендую изучить технику под названием "Дифференциальная эволюция". Это может быть очень хорошо при решении многих задач оптимизации.
Это сильно зависит от гладкости вашего пространства поиска. Извращенный пример, если каждый "геном" хэшируется перед использованием для генерации "феномов", тогда вы просто будете выполнять случайный поиск.
Менее экстремальный случай, поэтому мы часто используем целые числа серого кода в GA.
Вы должны адаптировать функции кроссовера и мутации к кодировке. ГА распадаются довольно легко, если вы бросаете в них несимпатичные вычисления. Если пересечение A и B не приводит к чему-то похожему на A и B, то это бесполезно.
Пример:
Геном имеет длину 3 бита, бит 0 определяет, обитает ли он на суше или на море. Биты 1-2 описывают функции пищеварения для обитающих на суше существ и визуальные возможности для обитающих на море существ.
Рассмотрим два обитающих на земле существа.
| bit 0 | bit 1 | bit 2
----+-------+-------+-------
Mum | 0 | 0 | 1
Dad | 0 | 1 | 0
Они могут пересекаться между битами 1 и 2, давая ребенку, чья пищеварительная функция является неким компромиссом между мамой и папой. Отлично.
Этот кроссовер кажется разумным при условии, что бит 0 не изменился. Если есть, то ваша функция кроссовера превратила какие-то кишки в какие-то глаза. Э-э... Что? С таким же успехом это могли быть случайные мутации.
Напрашивается вопрос, как ДНК обходит эту проблему. Ну, это и модально, и иерархически. Существуют большие разделы, которые могут сильно измениться без особого эффекта, в других же отдельные мутации могут иметь радикальные эффекты (как бит 0 выше). Иногда значение X влияет на поведение, вызванное Y, и все значения X являются законными и могут быть изучены, тогда как модификация Y делает ошибку в животном.
Теоретический анализ ГА часто использует чрезвычайно грубые кодировки, и они больше страдают от числовых вопросов, чем семантических.
У меня сложилось впечатление, что восхождение на холм с нескольких случайных стартов очень эффективно, но попытка найти случай, когда кроссинговер может улучшить это, нетривиальна. Одна ссылка - "Кроссовер: Божественное Аффлатус в Поисках" Дэвида Икланзана, в котором говорится
Традиционная теория GA опирается на гипотезу Building Block (BBH), которая утверждает, что генетические алгоритмы (GA) работают, обнаруживая, подчеркивая и объединяя схемы низкого порядка в высококачественных строках, строго параллельным образом. Исторически попытки запечатлеть топологические особенности фитнес-ландшафта, которые иллюстрируют этот интуитивно простой процесс, были в основном безуспешными. Популяционные рекомбинационные методы неоднократно выигрывали у специально разработанных абстрактных наборов тестов с помощью различных вариантов алгоритмов, основанных на мутациях.
Похожий документ - "Преодоление иерархической сложности путем восхождения на гору строительных блоков" Дэвида Илканзана и Дэна Думитреску, в котором говорится, что
Гипотеза Building Block предполагает, что генетические алгоритмы (GA) хорошо подходят для иерархических задач, где эффективное решение требует правильной декомпозиции проблемы и сборки решения из подрешения с сильными нелинейными взаимозависимостями. В статье предлагается альпинист, работающий над пространством стандартных блоков (BB), который может эффективно решать иерархические проблемы.
Две основополагающие работы Джона Холланда "Адаптация в естественных и искусственных системах" и "Скрытый порядок" (менее формальные) подробно обсуждают теорию кроссовера. ИМО, Гольдберг "Генетические алгоритмы в поиске, оптимизации и машинном обучении" имеет очень доступную главу о математических основах, которая включает в себя такие выводы, как:
Как с кроссовером, так и с воспроизведением.... те схемы с показателями выше среднего и короткими определяющими длинами будут дискретизироваться с экспоненциально увеличивающейся скоростью.
Другим хорошим примером может служить "Расширение теории сходимости и доказательство сложности времени генетических алгоритмов" Анкенбрандта (в "Основах генетических алгоритмов" Роулинса).
Я удивлен, что сила кроссовера не была очевидна для вас в вашей работе; Когда я начал использовать генетические алгоритмы и увидел, насколько мощным кажется "направленный" кроссовер, я почувствовал, что получил представление об эволюции, которая перевернула то, чему меня учили в школе. Все вопросы о том, "как мутация может привести к тому и другому?" и "Ну, в течение стольких поколений..." стало казаться в корне ошибочным.
Кроссовер и мутация!! На самом деле они оба необходимы. Кроссовер - исследовательский оператор, но мутация - эксплуатационный. Учитывая структуру решений, проблемы и вероятность скорости оптимизации, очень важно выбрать правильное значение для Pc и Pm (вероятность кроссовера и мутации).
Проверьте этот GA-TSP-Solver, он использует много методов кроссовера и мутации. Вы можете проверить любой кроссовер наряду с мутациями с заданными вероятностями.
Это в основном зависит от пространства поиска и типа кроссовера, который вы используете. Для некоторых проблем я обнаружил, что использование кроссовера в начале и затем мутации ускорит процесс поиска решения, однако это не очень хороший подход, так как я в конечном итоге найду похожие решения. Если мы используем как кроссовер, так и мутацию, я обычно получаю более оптимизированные решения. Однако для некоторых проблем кроссовер может быть очень разрушительным.
Также одних генетических операторов недостаточно для решения больших / сложных проблем. Когда ваши операторы не улучшают ваше решение (то есть, когда они не увеличивают ценность пригодности), вы должны начать рассматривать другие решения, такие как постепенное развитие и т. Д.