Генетические алгоритмы

Элитизм

Группа исследований эволюционных алгоритмов (ТПУ)

Дискуссионная группа по эволюционным вычислениям

Написать письмо

В классическом описании генетического алгоритма подразумевается создание популяции потомков и замещение родительских особей их "детьми". Такой подход достаточно естественнен, но не особенно эффективен, т.к. потомки, полученные в результате генетических преобразований, могут быть хуже родительских особей. В результате появилось несколько подходов, "исправляющих" данное явление, которые можно объединить, используя понятие "элитизм" (elitism) (иногда "стратегия элитизма" (elitist strategy), я встречал также слово "элитаризм", которое, возможно, правильнее, с точки зрения орфографии, но, на мой взгляд, грубовато). В данной статье будет представленное краткое описание этих подходов. Отметим, что краткое описание элитизма уже было сделано гораздо раньше (см. Стратегии отбора и формирования нового поколения), однако я считаю необходимым уделить ему отдельное внимание. Выделим две причины: (1) есть необходимость в попытке обсуждения элитизма, для качественно лучшего понимания его роли; (2) повышение уровня терминологической культуры читателя и ознакомление с некоторыми существующими техниками.

Условно элитизм можно разделить на два класса-подхода, назовем их конкурентным и неконкурентным. Коротко их суть в следующем:

1. Конкурентный подход. Родительские особи "состязаются" с потомками и победители (или победитель) переходят в следующее поколение.
2. Неконкурентный подход. В этом случае часть родительской подпопуляции (случайная либо определенная по заданному правилу) переходит в новое поколение без каких-либо возражений со стороны электората.

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

Рассмотрим каждый класс более подробно. При этом будем по возможности принимать во внимание наработки в области эволюционных стратегий (evolutionary strategies), кстати, совершенно незаслуженно обделяемых вниманием в ряде российских статей по эволюционным алгоритмам. Свою историю эволюционные стратегии ведут с, как минимум, середины 60-х годов и принятые в них обозначения весьма удобны для указания различных подходов к элитизму.

1. Конкурентный подход

Выделим в классе конкурентных подходов 2 подкласса (в скобках приведены жаргонные названия, рекомендуемые для употребления в псевдо-, квази- и мета-научной литературе, такой, например, как настоящая статья):

• глобальное состязание (массовое побоище, жестокое и беспощадное)
• локальное состязание (бои удельных князьков на кулачках)

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

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

С точки зрения эволюционных стратегий конкурентный подход соответствует (mu + lambda) стратегии (которая называется "плюс-стратегия" (plus strategy)), где nu -- количество родительских особей, а lambda -- количество созданных потомков.

2. Неконкурентный подход

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

В эволюционных стратегиях неконкурентный подход соответствует (mu, lambda) стратегии (дословный перевод выглядит как "запятая-стратегия" (comma strategy)), смысл переменных mu и lambda остается прежним и олицетворяет один из немногих примеров стабильности в нашем непостоянном и динамичном мире.

3. Обсуждение

В данном разделе будет представлена попытка проанализировать последствия использования, либо не использования того или иного (а может быть и какого другого) подхода к элитизму. Прежде чем начать, заметим, что все изложенное ниже есть суть точка зрения автора, выработанная в результате весьма многочисленных и не менее весьма разнообразных экспериментов с генетическими алгоритмами, а также благодаря чтению всех попадавшихся под руку публикаций. Но, ближе к делу. Как говаривал Юрий Гагарин: "Поехали!".

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

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

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

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

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

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

Заключение

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

1. 1. Конкурентный подход с локальным состязанием.
2. 2. Конкурентный подход с глобальным состязанием.
3. 3. Неконкурентный подход.

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

Источники:

1. De Jong K. Generation Gaps Revisited. Foundations of Genetic Algotihms 2. -- 1993. -- P.19-28.
2. Beyer, Schwefel, Wegener. How to Analyse Evolutionary Algorithms, Technical Report No.CI-139/02. -- University of Dortmund, Germany, 2002.

[19 апреля 2005г.]