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

Генетический алгоритм: боремся с преждевременной сходимостью

В предыдущем очерке (Выбор размера популяции для генетического алгоритма) был определен минимальный размер популяции необходимый для работоспособности генетического алгоритма:
N = 1 + LOG2(1/(1-P1^(1/L))), где
P1 — требуемая вероятность того, что случайный набор хромосом будет содержать все необходимые элементы для каждого локуса;
L — длина хромосомы.

В реальности данный размер популяции будет необходимым, но не достаточным для эффективной работы генетического алгоритма.
Происходит это из за преждевременной сходимости — остановки алгоритма до достижения глобального максимума (а зачастую и до достижения даже локальных максимумов).
Причина этого заложена в самой природе алгоритма: чем выше приспособленность хромосомы тем больше вероятность того, что она примет участие в скрещивании. Соответственно, тем большее количество раз она сможет принять участие в скрещивании.
Таким образом, генетический код хромосом, функция приспособленности которых существенно превышает среднее значение для популяции, получая преимущество, вытесняет из популяции другие наборы генетического кода.

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

Сам собой напрашивается экстенсивный путь борьбы с этим явлением — увеличение размера популяции, но найти интенсивный (не ресурсозатратный) путь гораздо интересней.

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

В качестве примера решается коммивояжер-подобная задача, длина хромосом L = 25
— по горизонтальной оси отложены все возможные значения хромосом, приведенные в десятичную систему координат (например хромосоме 1010010101111111110001010 соответствует x = 21692298);
— по вертикальной оси отложены значения функции приспособленности.
(как видно локальные максимумы достаточно сильно разделены друг от друга — в данной задаче наблюдаются все предпосылки для преждевременной сходимости).

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

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

Здесь будет очень полезен опыт природы.
Оператор скрещивания классического генетического алгоритма по сути своей соответствует мейозу — только в генетическом алгоритме число потомков равно числу предков.
Но в природе также существует и другой тип размножения — митоз и мы также можем приспособить его для использования в генетическом алгоритме.

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

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

Хромосомы с меньшей приспособленностью формируют пул для скрещивания между собой. Попарное скрещивание хромосом из пула проводится до тех пор пока не будет достигнута требуемая общая численность популяции (с учетом хромосом уже созданных с помощью оператора митоза). Выбор хромосом для скрещивания производится случайным образом методом рулетки (хромосомам с большей приспособленностью соответствует больший сектор на колесе рулетки). Численность популяции остается постоянной на протяжении всего времени работы генетического алгоритма.

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

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

Вот так выглядит распределение хромосом для стандартного генетического алгоритма (оттенки синего) и алгоритма с митозом (оттенки красно-коричневого). Размер популяции в обоих случаях: 2N.
Хромосомы разбиты по 5 квинтилям, в зависимости от поколения к которому они принадлежат.
Более ранние поколения показаны более светлыми оттенками.

— по горизонтальной оси отложены все возможные значения хромосом, приведенные в десятичную систему координат (например хромосоме 1010010101111111110001010 соответствует x = 21692298);
— по вертикальной оси отложены значения функции приспособленности.
Как видно из графика, для стандартного генетического алгоритма уже на ранних этапах характерна группировка вокруг областей локальных максимумов (в том числе и в области глобального максимума), затем случайным образом происходит концентрация хромосом вокруг одной из областей и вытеснение из популяции генетического материала, принадлежащего другим областям.
В тоже время, для алгоритма с митозом на ранних этапах характерна большая распределенность хромосом по всей области (при сопоставимых значениях приспособленности), на более поздних же этапах наблюдается планомерный дрейф в сторону области глобального максимума.

На этом графике можно сравнить эффективность работы генетического алгоритма с применением и мейоза и митоза (график красного цвета) по сравнению со стандартным генетическим алгоритмом (график синего цвета):

— по горизонтальной оси отложены значения размера популяции, где 1 — это размер популяции равный N (минимально необходимый размер популяции);
— по вертикальной оси отложены средние значения функции приспособленности хромосом, полученных в результате работы генетического алгоритма, где 1 — это значение функции приспособленности, равное глобальному максимуму.

Хорошо видно, что применение оператора митоза, позволяет существенно повысить результативность генетического алгоритма.
Так алгоритм с митозом для популяции размером в 2N (для рассчитываемого примера N=20) среднестатистически выдает результат в 0.9694 от максимально возможного. Для достижения таких же значений при применении стандартного генетического алгоритма потребуется популяция размером 7N.
Для достижения результата в 0.98 от максимального алгоритму с митозом потребуется популяция размером 3N, а стандартному алгоритму потребуется популяция размером 11N

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

Update: спасибо за вопросы и интересные комментарии — смогу ответить только вечером (к сожалению в течение дня не будет возможности); также сделаю вычитку, чтобы облегчить восприятие.

Источник

Обзор методов отбора, скрещивания и мутации

На этом занятии мы с вами рассмотрим основные подходы к реализации операторов отбора, скрещивания и мутации, которые составляют основу любого ГА:

Методы отбора

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

Правило рулетки

Метод отбора по правилу рулетки, или отбор пропорциональной приспособленности (fitness proportionate selection – FPS), заключается в случайном выборе индивидуума из популяции пропорционально его приспособленности. Предположим, у нас имеется несколько особей в популяции с разной степенью адаптации:

Тогда их можно условно представить на круговой диаграмме с секторами, размером соответствующих долей:

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

Стохастическая универсальная выборка

Стохастическая универсальная выборка (stochastic universal sampling – SUS) – модифицированный вариант рулетки, когда точки отбора (стрелки) располагаются равномерно вокруг диаграммы:

Вращение выполняется один раз и сразу производится отбор всех особей для дальнейшей операции скрещивания.

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

Ранжированный отбор

Следующий метод ранжированного отбора работает похожим образом на правило рулетки, но доли для индивидуумов вычисляются несколько иначе. Вначале все индивидуумы ранжируются (упорядочиваются) по возрастанию их приспособленности (см. столбец «Ранг»):

Затем, вычисляются доли относительно ранга (а не приспособленности, как в правиле рулетки) и, тем самым, доли секторов становятся более равномерными, а значит, более равномерно будут отбираться родители из популяции:

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

Масштабирование приспособленности

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

Например, у нас имеются особи с функцией принадлежности, равной:

Приспособленность 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

#4. Как генетический алгоритм находит решения. Преимущества и недостатки

#5. Обзор методов отбора, скрещивания и мутации

#6. Поиск минимальных маршрутов в графе

#7. Делаем элитизм. Жесткие и мягкие ограничения

#8. Расставляем корабли в игре Морской бой

#9. Пример поиска минимума функции

#10. Обучение с подкреплением или как загнать машину на гору

#11. Не дай шесту упасть или как нейросеть держит баланс

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

Источник

• ← что влияет на суставы человека
• что влияет на сюжет ведьмак 3 →