Эволюционные модели

Одним из примеров существенно машинных моделей являются эволюционные модели. Основная идея построения эволюционной модели была сформулирована Л. Фогелем1. Она заключается в том, чтобы модель сложного и трудно формализуемого объекта представить как результат эволюции некоторого простого объекта, т.е. «запустить» эволюционный процесс, подчиняющийся определенным правилам, и по окончании процесса зафиксировать характеристики получившегося объекта. Считается, что принятые в эволюционном моделировании правила описания эволюционного процесса согласуются с представлениями в биологии относительно того, как связаны высокоразвитые живые организмы и примитивные:

  • 1) предпосылка эволюции — наследственная изменчивость (мутирование);
  • 2) контролирующий и направляющий фактор — борьба за существование;
  • 3) преобразующий фактор — естественный отбор.

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

Таблица 13

Примеры соответствий социально-экономических и биологических параметров

Биологические параметры

Социально-экономические параметры

Сообщество

Корпорация, корпоративные объекты, субъекты, окружение

Видовое разнообразие и распределение в экологической нише

Типы распределения ресурсов, структура связей в корпорации

1 Фогель Л., Оуэнс А, Уолш М. Искусственный интеллект и эволюционное моделирование. М.: Мир, 1969.

Биологические параметры

Социально-экономические параметры

Экологическая ниша

Сфера влияния и функционирования, эволюции на рынке, в бизнесе

Рождаемость и смертность

Производство и разрушение

Изменчивость

Экономической обстановки, ресурсов

Конкурентные взаимоотношения

Рыночные отношения

Память

Способность к циклам воспроизводства

Естественный отбор

Штрафные и поощрительные меры

Наследственность

Производственные циклы и их предыстория

Регуляция

Инвестиции

Общую идею эволюционного моделирования наглядно иллюстрирует схема работы генетического алгоритма (рис. 1.2) — одного из наиболее популярных эволюционных алгоритмов. Генетические алгоритмы — вычислительные процедуры, базирующиеся на аналогии с природным процессом естественного отбора (селекции) и генетических преобразований, относящиеся к существенно машинным классам адаптивных алгоритмов. Примеры генетических алгоритмов — VEGA (Vector Evaluated Genetic Algorithm), FFGA (Fonseca and Fleming’s Multiobjective Genetic Algorithm), NPGA (Niched Pareto Genetic Algorithm) и SPEA (Strength Pareto Evolutionary Algorithm).

Упрощенная схема эволюционного моделирования

Рис. 1.2. Упрощенная схема эволюционного моделирования

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Достоинства:

  • • широкая область применения (возможность проблемно-ориентированного кодирования решений);
  • • возможность комбинирования с другими (неэволюционными) видами моделирования;
  • • отсутствие ограничений на вид целевой функции;
  • • пригодность для поиска в сложном пространстве решений большой размерности;
  • • ясность схемы и базовых принципов эволюционных вычислений.

Недостатки:

  • • отсутствие гарантии оптимальности полученного решения в силу эвристического характера эволюционных вычислений;
  • • вычислительная трудоемкость;
  • • относительно невысокая эффективность на заключительных фазах моделирования эволюции (операторы поиска в эволюционных алгоритмах не ориентированы на быстрое попадание в локальный оптимум).

  • [1] Дударов С. П. Математические основы генетических алгоритмов : учеб, пособие. М. :РХТУ им. Д. И. Менделеева, 2012.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >