Эффективность кроссовера в генетических алгоритмах

Я реализовал ряд генетических алгоритмов для решения целого ряда проблем. Однако я все еще скептически отношусь к полезности кроссовера/рекомбинации.

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

Конечно, это может быть связано с плохими выборами функции кроссовера и/или вероятностей, но я хотел бы получить некоторые конкретные объяснения/доказательства того, почему/кроссовер улучшает GA. Были ли какие-либо исследования в отношении этого?

Я понимаю причины этого: кроссовер позволяет объединить два человека в один индивидуум. Но мне кажется, что мы можем поговорить с ученым и ягуаром, чтобы получить умный и быстрый гибрид.

РЕДАКТИРОВАТЬ: В ответе mcdowella он упомянул, что найти случай, когда пересечение может улучшиться при поднятии холма из нескольких точек старта, нетривиально. Может ли кто-нибудь уточнить этот момент?

Ответ 1

Вы правы в том, что скептически относитесь к кросс-операции. Существует бумага, называемая "Об эффективности кроссовера в моделируемой эволюционной оптимизации" (Fogel and Stayton, Biosystems, 1994). Он доступен бесплатно на 1 (хороший источник многих других замечательных пабов также Фогеля).

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

Ответ 2

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

Менее экстремальный случай, поэтому мы часто целые числа серого кода в GA.

Вам необходимо адаптировать функции кроссирования и мутации к кодировке. GA распадаются довольно легко, если вы бросаете на них несимпатичные вычисления. Если кроссовер A и B не дает что-то вроде A-like и B-like, то это бесполезно.

Пример:

Геном имеет длину 3 бита, бит 0 определяет, является ли оно землей или морским жильем. Биты 1-2 описывают пищеварительные функции для наземных существ и визуальные возможности для морских обитателей.

Рассмотрим двух существ, живущих на земле.

    | bit 0 | bit 1 | bit 2
----+-------+-------+-------
Mum | 0     | 0     | 1
Dad | 0     | 1     | 0

Они могут перекрещиваться между битами 1 и 2, давая ребенку, чья пищеварительная функция является компромиссом между мамой и папой. Отлично.

Этот кроссовер кажется разумным при условии, что бит 0 не изменился. Если это так, ваша функция кроссовера превратила какие-то кишки в какие-то глаза. Er... Wut? Возможно, это были случайные мутации.

Возникает вопрос, как ДНК обходит эту проблему. Ну, это и модальное, и иерархическое. Есть большие секции, которые могут сильно меняться без особого эффекта, в других одна мутация может иметь резкие эффекты (например, бит 0 выше). Иногда значение X влияет на поведение, затушеванное Y, и все значения X являются законными и могут быть исследованы, тогда как модификация Y делает segfault животных.

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

Ответ 3

У меня сложилось впечатление, что скалолазание с нескольких случайных запусков очень эффективно, но попытка найти случай, когда перекрестное улучшение может улучшиться, является нетривиальным. Одна из ссылок - "Кроссовер: Божественный Afflatus in Search" Дэвида Икланцана, в котором говорится

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

Связанная с этим статья - "Преодоление иерархической сложности Хилла - Восхождение на Building Block Structure "Дэвида Икланцана и Дэна Думитреску, в котором говорится

Гипотеза Building Block предполагает, что генетические алгоритмы (GA) хорошо подходят для иерархических проблем, где эффективное решение требует правильной декомпозиции задачи и сборки решения из суб-решение с сильными нелинейными взаимозависимостями. Бумага предлагает горный альпинист, работающий над пространством строительного блока (ВВ) которые могут эффективно решать иерархические проблемы.

Ответ 4

Джон Холланд два семенных произведения "Адаптация в естественных и искусственных системах" и "Скрытый порядок" (менее формальный) обсуждают теорию кроссовера по глубине. ИМО, Голдберг "Генетические алгоритмы поиска, оптимизации и машинного обучения" имеет очень доступную главу о математических основах, которая включает такие выводы, как:

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

Другой хорошей ссылкой может быть Анкенбрандт "Расширение теории сходимости и доказательство временной сложности генетических алгоритмов" (в "Основах генетических алгоритмов" Роулинса).

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

Ответ 5

Кроссовер и мутация!! На самом деле они оба необходимы. Кроссовер - это исследовательский оператор, но мутация является эксплуататорской. Учитывая структуру решений, проблему и вероятность скорости оптимизации, очень важно выбрать правильное значение для Pc и Pm (вероятность кроссовера и мутации).

Проверьте GA-TSP-Solver, он использует множество методов кроссовера и мутаций. Вы можете протестировать любой кроссовер вместе с мутациями с заданными вероятностями.

Ответ 6

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

Одних только генетических операторов недостаточно для решения больших/сложных задач. Когда ваши операторы не улучшают ваше решение (поэтому, когда они не повышают ценность фитнеса), вы должны приступить к рассмотрению других решений, таких как инкрементная эволюция и т.д.