В генетических алгоритмов и эволюционных вычислений , кроссовер , также называемой рекомбинации , является генетический оператор используется для объединения генетической информации двух родителей для создания нового потомства. Это один из способов стохастического генерирования новых решений из существующей популяции, аналогичный кроссоверу, который происходит во время полового размножения в биологии . Решения также могут быть получены путем клонирования существующего решения, что аналогично бесполому воспроизведению . Вновь созданные решения обычно мутируют перед добавлением в популяцию.
Различные алгоритмы эволюционных вычислений могут использовать разные структуры данных для хранения генетической информации, и каждое генетическое представление может быть рекомбинировано с разными операторами кроссовера. Типичными структурами данных, которые можно рекомбинировать с помощью кроссовера, являются битовые массивы , векторы действительных чисел или деревья .
СОДЕРЖАНИЕ
Примеры
Традиционные генетические алгоритмы хранят генетическую информацию в хромосоме, представленной битовым массивом . Методы кроссовера для битовых массивов популярны и являются наглядным примером генетической рекомбинации .
Одноточечный кроссовер
Точка на хромосомах обоих родителей выбирается случайным образом и обозначается как «точка пересечения». Биты справа от этой точки меняются местами между двумя родительскими хромосомами. Это приводит к появлению двух потомков, каждое из которых несет некоторую генетическую информацию от обоих родителей.
При двухточечном кроссовере две точки кроссовера выбираются случайным образом из родительских хромосом. Биты между двумя точками меняются местами между родительскими организмами.
Двухточечный кроссовер эквивалентен выполнению двух одноточечных кроссоверов с разными точками кроссовера. Эту стратегию можно обобщить на k-точечный кроссовер для любого положительного целого k, выбирая k точек кроссовера.
Единый кроссовер
В однородном кроссовере, как правило, каждый бит выбирается из любого родителя с равной вероятностью. Иногда используются другие соотношения смешивания, в результате чего потомство наследует больше генетической информации от одного родителя, чем от другого.
Кроссовер для упорядоченных списков
В некоторых генетических алгоритмах не все возможные хромосомы представляют собой допустимые решения. В некоторых случаях можно использовать специализированные операторы кроссовера и мутации, которые разработаны, чтобы избежать нарушения ограничений задачи.
Например, генетический алгоритм, решающий задачу коммивояжера, может использовать упорядоченный список городов для представления пути решения. Такая хромосома представляет собой верное решение только в том случае, если список содержит все города, которые должен посетить продавец. Использование вышеуказанных кроссоверов часто приводит к хромосомам, которые нарушают это ограничение. Таким образом, генетические алгоритмы, оптимизирующие упорядочение данного списка, требуют различных операторов кроссовера, которые позволят избежать генерации неверных решений. Издано много таких кроссоверов:
частично отображенный кроссовер (PMX)
велосипедный кроссовер (CX)
оператор кроссовера заказов (OX1)
оператор кроссовера на основе порядка (OX2)
оператор кроссовера на основе позиции (POS)
оператор рекомбинационного кроссовера с голосованием (VR)
Другие возможные методы включают оператор рекомбинации краев . В качестве альтернативы для решения упомянутой проблемы можно использовать двойные хромосомы.
Источник
Обзор методов отбора, скрещивания и мутации
На этом занятии мы с вами рассмотрим основные подходы к реализации операторов отбора, скрещивания и мутации, которые составляют основу любого ГА:
Методы отбора
Начнем с обзора методов отбора лучших хромосом в популяции. Напомню, что на этом этапе отбираются наиболее приспособленные особи, которые становятся «родителями» для формирования следующего поколения. Но, при этом, необходимо сохранить возможность и менее приспособленным особям давать незначительное количество своих потомков для сохранения разнообразия генофонда.
Правило рулетки
Метод отбора по правилу рулетки, или отбор пропорциональной приспособленности (fitness proportionate selection – FPS), заключается в случайном выборе индивидуума из популяции пропорционально его приспособленности. Предположим, у нас имеется несколько особей в популяции с разной степенью адаптации:
Индивидуум
Приспособленность
Тогда их можно условно представить на круговой диаграмме с секторами, размером соответствующих долей:
Затем, мы раскручиваем этот круг и тот сектор, на который будет указывать стрелка, будет выбран. Таким образом, отбирается особь в качестве родителя. Очевидно, что чаще (с наибольшей вероятностью) будут отбираться индивидуумы с большей приспособленностью, так как у них сектор занимает большую долю.
Стохастическая универсальная выборка
Стохастическая универсальная выборка (stochastic universal sampling – SUS) – модифицированный вариант рулетки, когда точки отбора (стрелки) располагаются равномерно вокруг диаграммы:
Вращение выполняется один раз и сразу производится отбор всех особей для дальнейшей операции скрещивания.
Преимущество этого подхода в том, что он гарантирует отбор не только индивида с большой долей сектора, но, скорее всего, будут отобраны и другие особи с меньшими секторами. То есть, выбор более равномерен и сохраняет, в некоторой степени, разнообразие популяции.
Ранжированный отбор
Следующий метод ранжированного отбора работает похожим образом на правило рулетки, но доли для индивидуумов вычисляются несколько иначе. Вначале все индивидуумы ранжируются (упорядочиваются) по возрастанию их приспособленности (см. столбец «Ранг»):
Индивидуум
Приспособленность
Доля ранга
Затем, вычисляются доли относительно ранга (а не приспособленности, как в правиле рулетки) и, тем самым, доли секторов становятся более равномерными, а значит, более равномерно будут отбираться родители из популяции:
Этот подход дает хорошие результаты когда в популяции имеются отдельные особи с высокой приспособленностью. Тогда, чтобы они не «захватили» всю популяцию, отбор лучше делать по рангу, а не по приспособленности. Также этот способ позволяет отбирать лучших претендентов, когда приспособленности особей в популяции примерно одинаковы. Тогда ранг позволит с заметно большей вероятностью отбирать самых лучших, сохраняя отбор менее приспособленных.
Масштабирование приспособленности
Развитие идеи ранжированного отбора привело к способу масштабированного отбора. Здесь вместо рангов исходные значения приспособленности масштабируются к заданному интервалу значений.
Например, у нас имеются особи с функцией принадлежности, равной:
Индивидуум
Приспособленность f
Новое значение f*
И мы все эти значения от 4 до 45 хотим перевести в новый диапазон [30; 80]. Это делается простой математической операцией:
,
где a, b – коэффициенты преобразования (линейной функции); f – значение приспособленности особи.
Найти коэффициенты a, b очень просто, зная величину нового диапазона [30; 80]. Мы можем сформировать два уравнения для граничных точек:
где — минимальное и максимальное значения приспособленности особей в популяции; — минимальное и максимальное значения диапазона.
Из этой системы линейных уравнений, находим коэффициенты a и b:
Для нашего конкретного случая эти коэффициенты, равны:
Отображение прежних значений f в новый диапазон f*, показано на рисунке ниже:
Что нам это в итоге дает? Смотрите, как меняется распределение долей секторов после операции масштабирования:
Благодаря этому, особи отбираются из популяции более равномерно, и у худших появляется реальный шанс оказаться в новой выборке и тем самым обеспечить разнообразие хромосом. С другой стороны, хорошо приспособленные особи не заменяют собой новую популяцию, а всего лишь с большей вероятностью отбираются наряду с остальными претендентами. Все это благотворно влияет на сходимость ГА к оптимальному или близкому к оптимальному решению.
Турнирный отбор
О турнирном отборе мы с вами уже говорили на одном из прошлых занятий. Идея очень проста, но вместе с тем, эффективна. Каждый раз из популяции случайным образом отбирается несколько претендентов (от двух и более). Затем, среди отобранных участников выбирается наиболее приспособленный (с наибольшим значением функции принадлежности). Он и переходит в новую выборку.
Процесс повторяется до тех пор, пока число «родителей» не станет равно размеру популяции.
Последнее время турнирному отбору отдается все больше предпочтений. Он решает проблему отбора наименее приспособленных особей, сохраняя разнообразие популяции, и позволяет вообще обходиться без функции принадлежности. Здесь достаточно уметь сравнивать приспособленность особей между собой. В некоторых трудноформализуемых задачах это особенно полезно.
Как же из всего этого разнообразия подходов выбрать наиболее эффективный для решения конкретной задачи с помощью ГА? К сожалению, ответа на этот вопрос нет. Это, как раз, пример трудноформализуемой задачи. Здесь на первый план выходит опыт разработчика таких алгоритмов и, конечно же, здравый смысл. Но, рекомендация очень простая: начинайте с турнирного отбора, а если результаты кажутся неудовлетворительными, то пробуйте другие способы.
Методы скрещивания
Скрещивание (также называется кроссинговер и кроссовер) следующая базовая операция в генетическом алгоритме. Здесь перебираются пары родителей (как правило, без повторения) из отобранной популяции и с некоторой высокой вероятностью выполняется обмен фрагментами генетической информации для формирования хромосом двух потомков. Если родители не участвовали в скрещивании, то они переносятся (копируются) в следующее поколение.
Одноточечное скрещивание
В самом простом варианте операция кроссинговера выполняет обмен между двумя половинками хромосом родителей для формирования хромосом потомков.
Вначале случайным образом определяется точка разреза хромосомы, а затем, соответствующие части меняются местами. Получаются две новые хромосомы для двух потомков.
Двухточечное и k-точечное скрещивание
Однако, как показывает практика, двухточечное скрещивание дает лучшие результаты, чем одноточечное. При двухточечном кроссинговере вместо одной точки разреза выбираются две случайным образом (разумеется, они не должны попадать на границы хромосом и совпадать между собой).
Принцип работы двухточечного скрещивания демонстрируется следующим рисунком:
А реализовать его можно с помощью двух одноточечных операторов скрещивания. Сначала делается обмен частями хромосом по первой точке разреза, а затем, — по второй.
Аналогично можно реализовать и k-точечное скрещивание.
Равномерное скрещивание
Следующая идея скрещивания заключается в формировании потомков из скрещивания отдельных пар ген родителей, которые отбираются из хромосом случайным образом. Здесь слово «равномерное» означает использование датчика равномерного распределения для определения случайной позиции генов в хромосоме.
В самом простом варианте можно проходит по генам обоих родителей и с некоторой заданной вероятностью менять их местами:
Но, в общем случае, произвольно выбирается ген у родителя 1, затем, у родителя 2 и производится их обмен.
Упорядоченное скрещивание
В предыдущем примере хромосомы родителей состояли из неповторяющихся чисел от 1 до 7, но после скрещивания мы получили потомков, у которых некоторые числа стали совпадать. В некоторых случаях такой результат является недопустимым. Например, если с помощью ГА решается задача поиска кратчайшего пути обхода всех городов, которые условно заданы числами от 1 до 7 и соединены магистралями в виде следующего графа:
У каждого участка маршрута между двумя соседними городами имеется определенная длина. И эту суммарную длину необходимо минимизировать. Так формулируется известная задача коммивояжера. В ней каждый потомок должен всегда содержать наборы чисел от 1 до 7 в своих хромосомах и потеря этой информации считается недопустимой.
Как раз для таких случаев был предложен способ упорядоченного скрещивания хромосом родителей. Идея его очень проста. Вначале делается уже известный вариант скрещивания, который не приводит к дублированию чисел, например, частый случай двухточечного скрещивания:
А оставшиеся значения генов у потомков заполняем следующим образом. Мы проходим все гены первого родителя, начиная от второй точки разреза, и добавляем значения, если они не еще не присутствуют в хромосоме первого потомка. Затем, ту же самую операцию выполняем со вторым родителем и вторым потомком. В результате, получим следующий набор генов у двух потомков:
Вообще, все эти алгоритмы перемешивания генов в потомках – творческий процесс и каждый из вас вполне может придумать свой собственный вариант и, кто знает, возможно, он окажется удачным для решения определенных задач.
Скрещивание смешением
В случаях, когда гены содержат вещественные значения можно воспользоваться способом под названием скрещивание смешением (blend crossover – BLX). Его идея достаточно проста. Вначале выбираются два родителя, условно обозначим их p1 и p2 с набором определенных генов:
Затем, последовательно перебираем соответствующие пары ген этих двух родителей и вычисляем интервал для последующей генерации случайных значений генов потомков. Интервал определяется формулой:
,
где — i-й ген первого и второго родителей соответственно; — некоторый коэффициент. На рисунке ниже показана зависимость интервала [d1; d2] от коэффициента α:
Здесь всюду полагалось, что p1 < p2. При имеем совпадение интервала со значениями в генах родителей. При интервал увеличивается в 2 раза, а при интервал становится больше в 4 раза. Обычно, на практике выбирают .
Далее, в интервале [d1; d2] случайным образом выбираются два числа: для первого и второго потомков. И так для всех генов. На выходе получаем двух потомков с новым набором ген.
Имитация двоичного скрещивания
Идея имитации двоичного скрещивания (simulated binary crossover – SBX) заключается в имитировании свойств одноточечного скрещивания, применяемое в двоичных хромосомах (состоящих из 0 и 1). Ключевой особенностью здесь является равенство среднего значения хромосом у родителей и у потомков.
Гены двух потомков вычисляются по следующим формулам:
где — коэффициент распределения; — хромосомы первого и второго родителей (представленные вектором из генов).
Смотрите, если , то потомки o1 и o2 будут идентичны родителям p1 и p2. При средние значения потомков становятся ближе друг другу, а при — дальше друг от друга. При этом, вне зависимости от выбора значения средние значения генов в хромосомах потомков и родителей оказываются равными. Это ключевое отличие данного метода скрещивания от предыдущего.
Величину в этом способе выбирают случайным образом при формировании каждой пары потомков. И, чтобы потомки были «схожи» с родителями, этот параметр вычисляют по формуле:
Значение u генерируется как равномерная случайная величина в диапазоне [0; 1], а параметр называется и отвечает за близость потомков к родителям. Обычно, его выбирают равным 10 или 20.
Методы мутации
Последний оператор, который применяется для формирования нового поколения популяции – это мутация. Обычно, она применяется с некоторой малой вероятностью к отдельным генам потомков, меняя их определенным образом. Мутация позволяет поддерживать генетическое разнообразие особей, чтобы популяция не выродилась и хромосомы не стали похожи друг на друга.
Инвертирование битов
Наверное, самый простой вариант мутации – это инвертирование битов, записанные в генах. Здесь может быть несколько вариантов реализации. Например, с некоторой (обычно низкой) вероятностью хромосома подвергается мутации и далее случайный бит (ген) переводится и инверсное состояние:
Либо, можно вначале также выбираем с некоторой вероятностью хромосому для операции мутации, а затем, проходим по всем генам и с некоторой другой (также низкой) вероятностью выполняем инверсию бит.
Мутация обменом
Для упорядоченных списков (когда в генах хромосомы хранятся индексы некоторого списка и они не должны повторяться, как в задаче коммивояжера) можно выполнять мутацию путем обмена случайно выбранных генов:
Этот же способ мутации можно использовать и в других типах задач, не обязательно только для списков.
Мутация обращением
Несколько видоизмененная идея мутации обменом является другой способ – мутация обращением. Здесь мы выбираем также случайным образом непрерывную последовательность генов, которые, затем, записываем в обратном порядке:
Этот метод также пригоден при кодировании списков в генах, так как данные не искажаются, а лишь меняются местами.
Мутация перетасовкой
Несколько более разнообразные результаты мутации можно получить, если в предыдущем алгоритме значения ген записывать не в обратном, а случайном порядке. Такой подход известен под названием мутация перетасовкой:
Мутация для вещественных чисел
Если в генах хранятся вещественные числа, то помимо рассмотренных подходов (кроме, может быть инвертирования битов), можно воспользоваться еще одним, связанным с генерированием случайных вещественных величин.
Например, можно вначале определить с некоторой небольшой вероятностью ген, который будет подвергаться мутации, а затем, в него записать новое случайное значение:
И здесь возникает один тонкий момент. Числа следует генерировать, во-первых, из области допустимых значений и, во-вторых, желательно близкими к исходному значению. Например, если мы знаем, что допустимый диапазон значений [-10; 10], то новое значение для прежнего гена с числом 1.2 можно смоделировать с помощью нормального закона распределения:
Здесь в качестве среднего значения (математического ожидания) берется, как раз величина 1,2 и ограничивается диапазоном [-10; 10].
На языке Python выполнить такое моделирование очень просто. Для этого можно воспользоваться функцией triangular(), которая ограничивает диапазон СВ [-off; off] и функцией gauss(), которая моделирует нормальные (гауссовские) случайные величины с заданным средним mu и стандартным отклонением sigma:
Элитизм
В заключение этого занятия отметим еще один механизм, применяемый совместно с оператором отбора в ГА – элитизм. Его смысл очень прост. В следующее поколение мы гарантированно отбираем небольшое число наиболее приспособленных (элитных) особей:
Причем, эти элитные индивидуумы также участвуют в скрещивании на правах родителей. Такой подход позволяет сохранять в популяции лучшие решения (не теряя их и не переоткрывая заново). В ряде задач это существенно увеличивает скорость сходимости ГА к некоторому приемлемому или оптимальному решению.
Вот так в целом можно выполнять операции отбора, скрещивания и мутации в генетических алгоритмах. Опять же, какой метод выбрать, зависит от типа решаемой задачи и от опыта разработчика ГА.
Поддержка методов отбора, скрещивания и мутации пакетом DEAP
В пакете DEAP уже реализованы многие из представленных методов отбора, скрещивания и мутации. Подробно о них можно посмотреть в официальной документации:
Ниже в таблицы перечислены все эти встроенные методы:
Кроме того, вы всегда самостоятельно можете реализовать свои собственные методы и встроить в ГА, реализуемый с помощью DEAP.
Видео по теме
Генетический алгоритм история и возможности
#1. Основные этапы работы генетического алгоритма
#2. Делаем генетический алгоритм для задачи OneMax
#3. DEAP — пакет для создания генетических алгоритмов
#4. Как генетический алгоритм находит решения. Преимущества и недостатки
#5. Обзор методов отбора, скрещивания и мутации
#6. Поиск минимальных маршрутов в графе
#7. Делаем элитизм. Жесткие и мягкие ограничения
#8. Расставляем корабли в игре Морской бой
#9. Пример поиска минимума функции
#10. Обучение с подкреплением или как загнать машину на гору
#11. Не дай шесту упасть или как нейросеть держит баланс
,
— минимальное и максимальное значения приспособленности особей в популяции; 
— минимальное и максимальное значения диапазона.
,
— i-й ген первого и второго родителей соответственно; 
— некоторый коэффициент. На рисунке ниже показана зависимость интервала [d1; d2] от коэффициента α:
имеем совпадение интервала со значениями в генах родителей. При 
интервал увеличивается в 2 раза, а при 
интервал становится больше в 4 раза. Обычно, на практике выбирают 
— коэффициент распределения; 
— хромосомы первого и второго родителей (представленные вектором из генов).
, то потомки o1 и o2 будут идентичны родителям p1 и p2. При 
средние значения потомков становятся ближе друг другу, а при 
— дальше друг от друга. При этом, вне зависимости от выбора значения 
называется и отвечает за близость потомков к родителям. Обычно, его выбирают равным 10 или 20.
