Часть 7. Эволюционные стратегии

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

Наиболее распространённая и часто применяемая – стратегия элитизма. Её суть сводится к сохранению на всех этапах эволюционного процесса постоянной по объёму прослойки лучших особей популяции. Считается, чем лучше особь, тем больше вероятность того, что она несёт в себе полезный генетический материал, который может быть использован для нахождения оптимума. Таким образом, использование стратегии элитизма позволяет исключить возможность удаления из популяции лучших особей при формировании нового поколения.

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

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

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

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

В этой связи большой эффект даёт применение стратегии «свежей крови».

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

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

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

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

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

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

Схема реализации стратегии миграции

Рис. 1. Схема реализации стратегии миграции

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

На рис. 2 изображён пример схемы реализации трёхэтапной турнирной эволюционной стратегии с размером популяции в 40 особей в каждой группе.

Схема реализации турнирной стратегии

Рис. 2. Схема реализации турнирной стратегии

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

По материалам учебного пособия: 
Дударов С. П. Математические основы генетических алгоритмов: учеб. пособие/ С. П. Дударов. – М.: РХТУ им. Д. И. Менделеева, 2012. – 56 с.


Если у вас есть статья, заметка или обзор, которыми вы хотите поделиться с аудиторией нашего сайта, присылайте информацию на: neuronus.com@yandex.ru.
Гость, оставишь комментарий?
Имя:*
E-Mail:


Свежее новое
  • На B-52 испытали новую гиперзвуковую ракету
  • Б-52 — знаменитый североамериканский бомбардировщик стратегического назначения. Минобороны США планирует оснастить этот самолет новейшим комплексом
  • Две погасшие звезды слились воедино и образовали одну, которая «ожила»
  • Можно ли из двух мертвых тел создать одно живое? Оказывается, это реально, если речь идет о звездах. Астрономы открыли такую редкую звезду, которая
  • Трансгенные грибы могут истреблять разносчиков малярии и других москитов
  • Ученые из США и Буркина-Фасо провели эксперименты, доказавшие эффективность нового средства от москитов. Это генномодифицированный гриб вида
  • Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
  • По сети гуляет видео, где несколько десятков летательных аппаратов ВМС Соединенных Штатов Америки демонстрируют слаженный взлет. Этот завораживающий
  • Ученые нашли окаменелость, которая сохранила целую стаю рыбок
  • В Америке нашли окаменелость, в которой «законсервирована» целая стайка рыбок. Они застыли в процессе движения, которое, как считают ученые, было
Последние комментарии
Ролик о массовом взлете конвертопланов Osprey и вертолетов CH-53E завораживает
Сколько раз я задавал вопрос про аварийную посадку конвертоплана,но так и не получил ответа. Если у него двигатели не повернутся вверх,то как он
5 необъяснимых для науки загадок
Ваша цитата: "Масса - это сконцентрированная Энергия. Энергия - это не сконцентрированная Масса".   Мой комментарий: Чтобы увеличить (в общем случае
Исследование показало: рождение ребенка старит женщину на 11 лет, а бездетные люди живут меньше
Корреляция в данном случае заключается в том что работает программа размножения. Программа размножения с точки зрения системы не дать умереть виду,
Сколько придется лететь со скоростью света до ближайшей звезды?
Ни какого замедления времени и ни какого сокращения расстояния не происходит при полёте в Космосе со скоростью близкой к скорости света, а тем более
Сколько придется лететь со скоростью света до ближайшей звезды?
Ближайшая звезда к нам, это Солнце. Расстояние порядка 150 млн. км. (Астрономическая единица). Несложные арифметические действия и "вуаля", получаем
Мы в социальных сетях
Статистика
3  
Всего статей 2003
1  
Всего комментариев 333
2  
Пользователей 118