Эволюционные стратегии

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Комментарии: