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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Гость, оставишь комментарий?
Имя:*
E-Mail:


 
Свежее новое
  • Подопытные животные могут вздохнуть с облегчением? Вскоре их заменит искусственный интеллект
  • Исследователи разработали систему искусственного интеллекта, которая может быть использована для тестирования побочных эффектов применения различных
  • Робот поможет в ремонте вашего автомобиля
  • Когда Джейми Людольф столкнулся с непростым автомобильным ремонтом, он обратился к сервисный центр, но сегодня в автосалоне в Атланте, он может
  • Компания HUAWEI стремится захватить трон компаний из Силиконовой долины в сфере производства чипов для нужд AI
  • Китайский технологический гигант Huawei успешно реализует свою стратегию по захвату рынка производства чипов, который принадлежит представителям
  • Ежегодный форум по системам искусственного интеллекта RAIF 2018 состоится 23 октября 2018 в конгресс-парке «Рэдиссон Ройал Москва»
  • 23 октября в конгресс-парке «Рэдиссон Ройал Москва» состоится второй ежегодный форум по системам искусственного интеллекта — RAIF 2018 (The Russian
  • Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
  • Технологическая Сингулярность (ТС), т.е. взрывное развитие технического прогресса, а значит и взрывное развитие экономики России, предполагает в
Последние комментарии
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
У нас очень странный народ, если что не понимает, то обязательно надо сунуть в морду. Зачем? А не лучше ли поинтересоваться, почему именно так? У
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Господин Чернов. Поясню. Любой инструмент, даже прозаическая кофемолка, проходят процедуру стендовых испытаний. Сертификат соответствия
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
     " И странная картина получается в коридорах власти ". Странная картина  получается, если полагать, что власть эта поставлена для решения задач
Как работает Любовь? Квантовая связь нейронной активности Людей
Спасибо за статью, но удивило, что ни в статье, ни в перечне литературы не упоминаются исследования и четкие выводы о структуре воды как
Искусственный интеллект против команды профессиональных геймеров в DOTA 2. Кто победит?
Офигенно, крутая инаф.
Мы в социальных сетях
Статистика
1  
Всего статей 1526
0  
Всего комментариев 62
0  
Пользователей 51