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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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


Последние комментарии
Дрон-камикадзе и ракеты с искусственным интеллектом: как в России создали умные боеприпасы и планируют применять в деле
Современная микроэлектроника, включая микроконтроллеры и процессоры для современных ПК, является продуктом высокотехнологического производства и
Как работает Любовь? Квантовая связь нейронной активности Людей
ребят,вот вам смешно,а квантовая связь влюбленных то существует.и я не шучу. мой парень видел глюки и в этих глюках присутствовала я.(если что,в
Почему космос не имеет начала и конца: комментарии учёных
Земля находится трёх слонах, которые стоят на черепахе
Судьба ледокола «Арктика» остается неопределенной после повреждения одного из двигателей
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Сообщение о покупке водородной яхты Билом Гейтсом оказалось ложным
Народ теперь что бы накачать мышцы и убрать лишний жир можно без спорта и диет, просто надел и забыл. Опробовал лично и результат удивил уже через
Мы в социальных сетях
Статистика
0  
Всего статей 2562
0  
Всего комментариев 1031
0  
Пользователей 264