|
2. Неконкурентный подход
В неконкурентном подходе все значительно проще. После оценки
текущей популяции выбираются несколько наилучших особей (т.е.
особей
имеющих
максимальную
приспособленность)
и
они
"автоматически" попадают в следующее поколение. При этом элитные
особи могут принимать участие в скрещивании наравне с остальными
особями. В силу того, что, таким образом, родительские особи не
соревнуются в той или иной форме со потомками, такой подход и
получил название неконкурентный.
В эволюционных стратегиях неконкурентный подход соответствует
(mu, lambda) стратегии (дословный перевод выглядит как "запятая-
стратегия" (comma strategy)), смысл переменных mu и lambda остается
А.Е. Кононюк Дискретно-непрерывная математика
80
прежним.
Здесь мы проанализируем последствия использования, либо не
использования того или иного подхода к элитизму. Что же влечет
использование элитизма? Очевидно, что при элитизме медленнее
обновляется генетическая информация в популяции, т.к. часть особей,
точнее их геномы, остаются неизменными при смене поколений. И хотя
такое возможно и без элитизма (например, скрещивание двух
"похожих" родительских особей может привести к созданию
идентичных с ними потомков) в случае с элитизмом вероятность этого
события существенно увеличивается, прежде всего, в силу специфики
самого подхода к элитизму. Хорошо это или плохо? Попытаемся
проанализировать.
Для этого необходимо понять, когда (не)выгодно интенсивное
обновление геномов популяции. Очевидно, что если популяция
"приближается" к глобальному оптимуму (т.е. находится на
сравнительно небольшом от него удалении), то резкие изменения
особей
(большинство
из
которых
обладают
высокой
приспособленностью)
нежелательны,
т.к.
могут
ухудшить
соответствующие этим особям решения. Поэтому, в данном случае,
элитизм, как способ сохранения "хороших" особей, необходим. Нужно
отметить, что описанная ситуация, как правило, не наблюдается в
начале эволюции, за исключением случая, когда решается очень
простая задача, но для них ГА, по большому счету, не нужны. Если же
эволюционный поиск находится в самом начале, то, очевидно,
необходимо активно исследовать пространство поиска, чтобы выделить
в нем потенциальные области, при попадании в которые, популяция
будет иметь высокую приспособленность. Однако, если в результате
генетических преобразований получается особь, которая находится в
одной из таких областей (и допустим обладает максимальной
приспособленностью по сравнению с остальными особями в
популяции) то необходимо, чтобы характерные для этой особи
генотипические (и, соответственно, фенотипические) признаки
закрепились в популяции, иначе данная область на неопределенное
время будет "потеряна".
Небольшое отступление. Генотип особи -- это, как правило, ее
генетическая информация, а фенотип особи -- соответствующее этой
А.Е. Кононюк Дискретно-непрерывная математика
81
особи решение поставленной задачи, т.е., в простейшем случае,
фенотип -- декодированный из генетического представления набор
оптимизируемых параметров. Другими словами, генотип -- это ДНК.
Изменение генотипа, получаемое в результате скрещивания и мутации,
влечет изменение соответствующего фенотипа и для случая прямого
кодирования здесь все очевидно, т.к. генотип однозначно
соответствует фенотипу (и обратно, для каждого фенотипа можно
найти единственный генотип). Для кодирования Грея отображение
генотип-фенотип также однозначно, хотя и не так наглядно. Однако
при неоднозначном соответствии генотипа и фенотипа могут
возникать проблемы в адекватной оценке особи.
Дело в том, что и приспособленная особь может исчезнуть, например,
потому что генератор случайных чисел выдал "неудачную" для этой
особи последовательность, в результате чего она либо вообще не
приняла участия в скрещивании (в частности, могут "задавить числом"
неприспособленные особи), либо ее потомки на нее не "похожи", либо
же они сильно мутировали. При использовании элитизма шансы, что
генетические
свойства
рассматриваемой
(потенциально
многострадальной) особи сохранятся и распространятся в популяции,
выглядят обнадеживающе. Получается, что и на начальных этапах
элитизм нужен.
Более сложная картина для неоднозначного отображения генотип-
фенотип. Например, когда в генотипе закодирована структура
искусственной нейронной сети (ИНС). Тогда одной и той же особи
(структуре ИНС) могут соответствовать различные по характеристикам
ИНС, в следствие различных значений весов связей. В этом случае,
даже если приспособленности некоторой особи высока, это не дает
достаточных
оснований
для
преимущества
перед
менее
приспособленными
объктами,
т.к.
все
рассуждения
о
приспособленности ведутся в условиях неполной информации. В
некоторой степени ситуацию можно выправить, если для каждой особи
исследовать несколько различных соответствующих ей фенотипов (в
данном примере ИНС с различными весами, но одинаковой
структурой). Тем не менее, неопределенность, хоть и меньшая,
остается. В силу этих рассуждений необходимость в элитизме в данном
случае остается под вопросом. Вполне возможно, что лучше вообще
запретить конкуренцию между особями, имеющими существенно
А.Е. Кононюк Дискретно-непрерывная математика
82
различные по составу генотипы (которым соответствуют сильно
отличающиеся структуры ИНС). Сделать это можно, например, с
помощью "нишинга (niching)".
В любом случае, не стоит забывать о "формуле успеха" в генетических
алгоритмах, которую можно сформулировать следующим образом:
"Необходимо соблюдать баланс между исследованием пространства
поиска (exploration) и использованием найденных хороших решений
(exploitation)". Т.е. если используется элитизм, другими словами, более
активно используются уже найденные хорошие особи, то необходимы
меры, которые будут компенсировать влияние элитизма, например,
увеличение вероятности мутации, либо увеличение размера популяции,
либо запрет на существование "особей-близнецов" в популяции. В
противном случае существенно увеличивается риск преждевременной
сходимости.
Использование элитизма, в целом, позволяет существенно улучшить
результаты работы ГА. Тем не менее, использовать элитизм необходимо
с определенной осторожностью, чтобы избежать преждевременной
сходимости. В результате классификации известных автору методов
элитизма предлагается выделять следующие подходы:
1. Конкурентный подход с локальным состязанием.
2. Конкурентный подход с глобальным состязанием.
3. Неконкурентный подход
.
Do'stlaringiz bilan baham: |
