Глава 6. Эволюционная адаптация

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

Пьер Тейяр де Шарден

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

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

§ 6.1. Алгоритмы эволюционной адаптации

Эти алгоритмы являются квазибионическими алгоритмами случайного поиска, параметрические аналоги которых рассмотрены в § 3.7. Рассмотрим теперь эволюцию структуры.

6.1.1. Общая модель эволюции структуры

Начнем с модели структурной эволюции, которая лежит в основе структурной адаптации.

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

Множество определяется ограничениями Н и (см. § 1.2) так, что при соблюдении (6.1.1) выполняются условия

если где Н и — заданные функционалы ограничений.

Таким образом, будем считать, что множество вариаций определено и задача состоит в оптимизации заданного функционала:

определенного на структуре

Процесс эволюции структуры происходит поэтапно. На первом этапе порождаются возмущенные (мутированные) структуры:

где случайная вариация (мутация) структуры, ограниченная (6.1.1), а число новых структур ко является параметром, который назначается исходя из конкретных условий эволюции.

Новые структуры (6.1.4) оцениваются по критерию эффективности

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

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

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

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

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

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

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

Заметим, что немаловажную роль играет эффективность оценки структуры. Эта оценка, как правило, бывает очень трудоемкой и сводится или к вычислению многомерных интегралов, или к оценке функционирования имитационной модели с назначенной структурой. В обоих случаях удобно воспользоваться методом Монте-Карло (см. § 3.2).

Здесь описывается адаптация без параметрической подстройки (см. § 1.5). Параметрическая адаптация, если она необходима для повышения эффективности структур, легко вводится перед стадией отбора и осуществляется стандартными параметрическими методами (см., например, § 3.5).

Рассмотрим в качестве примера и наиболее распространенного случая объекты, структура которых описывается графом.