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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


 
Свежее новое
  • Искусственный интеллект смог визуализировать 2D изображения.
  • Ученые из Вашингтона разработали модель, которая способна воссоздавать движения человека на фотографиях и картинах. Она создает для него 3D модель и
  • Искусственный интеллект, робот Вера, получил 226 млн рублей
  • ФРИИ и Кировский завод вкладывают 226 миллионов рублей в представителя «Сколкова» — компанию «Стафори», создавшую робота-рекрутера. Искусственный
  • В Москве состоялся финал PicsArt AI Hackathon, с самым крупным призовым фондом в истории
  • 30 ноября-2 декабря, в Москве прошел крупнейший хакатон в сфере искусственного интеллекта и компьютерного зрения - PicsArt AI Days. На хакатон было
  • В следующем году в Москве, заработает видеоконтроль, способный обнаружить преступников
  • Как рассказал в своем сообщении Сергей Собянин, новая система будет способна анализировать записи с видеокамер. Быстрая обработка данных позволит
  • В Москве пройдет один из крупнейших хакатонов в мире в сфере искусственного интеллекта
  • PicsArt, ведущая творческая платформа для создания контента и визуализации историй в социальных сетях с более чем 100 миллионами активных
Последние комментарии
Как работает Любовь? Квантовая связь нейронной активности Людей
Как вы считаете, возможно ли образование квантовых взаимодействий между человеком и ИИ? 
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
А почему бы сразу СИИ не запустить в другую галактику, может там нет коррупции, воровства, плебейства и прочей муры, которая не только мешает
Искусственный Интеллект. Концепция развития и внедрения Искусственного Интеллекта (Искусственной Аналитики)
Согласен. проблема ИИ не в наборе задач. Главная проблема - познание процесса мышления как феномена физиологии головного мозга человека.
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Господа - непубликация моего вполне невинного предложения о пересборке Win-10  в удобопользуемый вид, со 146% вероятностью характеризует "ценность"
Сильный Искусственный Интеллект «Smart-MES» как основа Технологической Сингулярности России
Если Ваш SM столь замечателен-могуч-адаптивен, что вот-вот пристроит нам сингулярность, то нельзя-ли ему решить ничтожную, но практическую задачу -
Мы в социальных сетях
Статистика
1  
Всего статей 1538
3  
Всего комментариев 72
0  
Пользователей 63