Растригин Л.А. Адаптация сложных систем

Подождите немного. Документ загружается.

Puc. 5.5.2. Динамика работы алгоритма альтернативной адаптации процесса

сортировки:

a — при скачкообразном изменении коэффициента упорядоченности массивов, б

— при линейном изменении.

начинает устойчиво выбирать оптимальный в данной ситуации

алгоритм («min» при с = —0,8 и «пузырек» — при с = 0,8).

Динамика адаптации (рис. 5.5.2, б) при непрерывном измелении во

времени упорядоченности сортируемых массивов:

с (t) = 0,2 k. (5.5.6)

где k — номер очередного массива, показывает, что алгоритм

адаптации уверенно «включает» алгоритм, оптимальный в сло-

жившейся ситуации с.

Таким образом, предложенный алгоритм альтернативной

адаптации сортировки массивов позволяет надежно определять

наилучший в сложившейся ситуации алгоритм сортировки и пе-

реходить к другому, лучшему при изменении ситуации.

Описанные алгоритмы альтернативной адаптации применимы лишь

в том случае, когда число конкурирующих альтернатив крайне мало

(2—5). Если их число велико, то надо использовать алгоритмы

эволюционной адаптации, описанные в следующей главе.

Эволюционна

я адаптация

Ничто в мире не может вдруг объ-

явиться в конце после ряда соверша-

емых эволюцией переходов, если оно

незаметно не присутствовало в начале.

Пьер Тейяр де

Шарден

Идеи биологической эволюции, рассмотренные в § 3.7, дают богатую

пищу для структурной адаптации сложных систем. При этом

структуру объекта следует описать на языке графов, эволюция

которых реализуется прямым моделированием биологической

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

позволяющей отбирать на следующий этап эволюции лучшие

структуры. Реализация такой эволюции на графах получила название

эволюционного моделирования.

В этой главе рассмотрены основные алгоритмы эволюционной

адаптации и описано их применение для решения задач агрегации

графов, адаптации дисциплин обслуживания в вычислительных сетях,

адаптации структуры решающих правил и синтеза оптимальных

планов эксперимента для факторной модели объекта.

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

Эти алгоритмы являются квазибионическими алгоритмами

случайного поиска, параметрические аналоги которых рассмотрены в

§ 3.7. Рассмотрим теперь эволюцию структуры.

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

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

структурной адаптации.

Пусть структура W объекта может изменяться, причем эти

изменения, т. е. вариации (мутации) δW структуры W, принадлежат

заданному множеству Ξ возможных вариаций:

δW Ξ. (6.1.1)

Множество Ξ определяется ограничениями H и G (см. § 1.2) так, что

при соблюдении (6.1.1) выполняются условия

(6.1.2)

если H(W)≥Q и G(W)=0, где H и G — заданные функционалы

ограничений.

Таким образом, будем считать, что множество S вариаций δW

определено и задача состоит в оптимизации заданного функционала:

(6.1.3)

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

Процесс эволюции структуры W происходит поэтапно. На первом

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

= W

+ δW

(i = l, ..., k

), (6.1.4)

где δW

— i-я случайная вариация (мутация) структуры, ограниченная

(6.1.1), а число новых структур k

является параметром, который

назначается исходя из конкретных условий эволюции.

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

= Q (W

) (i = l, ..., k

), (6.1.5)

и происходит отбор, в процессе которого «вымирают» структуры с

большим значением минимизируемого функционала Q, в результате

чего на следующий этап эволюции остается q

лучших структур.

Можно воспользоваться алгоритмом вероятностного отбора, при

котором структура, имеющая большое значение минимизируемого

критерия, выбывает с большей вероятностью, чем структура с

меньшим критерием. Например, вероятность выбывания для Q>0

может быть определена так:

(6.1.6)

При этом процесс «разыгрывания» выбывающих структур за-

канчивается тогда, когда осталось q

структур. Так

моделируется естественный отбор, составляющий основу

биологической эволюции.

Заметим, что вполне может оказаться (особенно при малом k

), что

лучшая из новых структур хуже исходной W

В этом случае

естественно сохранить W

на следующий этап эволюции.

На втором этапе эволюции каждая из оставшихся структур

мутирует аналогично (6.1.4) и дает столько «потомков», что их общее

число вместе с «родителями» равно k

. Последующий отбор оставляет

на следующий этап эволюции q

структур. Далее процесс повторяется.

Легко видеть, что такого рода эволюция структуры будет

«стремиться» отбирать структуры с малым значением критерия

качества, среди которых находится и оптимальная структура.

Случайность вариации δW обеспечивает сходимость процесса

эволюции к оптимальному решению W

Рассмотрим влияние параметров k

и q

(i = 0, 1, ... ). Эти параметры

позволяют изменять численность «популяции» структур и уровень

отбора. При q=1 на следующий этап эволюции оставляется одна

лучшая структура. Такая стратегия эффективна при «унимодальности»

задачи (6.1.3). Многоэкстремальность требует q

>1 и тем больше, чем

сложнее поиск глобального экстремума. Численность популяции k

также влияет на . эффективность процесса эволюции. При большем k

эволюция имеет глобальную тенденцию, но идет медленнее, так как

требует значительных затрат времени и памяти ЭВМ.

Значение этих параметров следует адаптировать в процессе

эволюции, учитывая ее специфику, цели и результаты. Алгоритмы

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

Заметим, что немаловажную роль играет эффективность оценки

структуры. Эта оценка, как правило, бывает очень трудоемкой и

сводится или к вычислению многомерных интегралов, или к оценке

функционирования имитационной модели с назначенной структурой.

В обоих случаях удобно воспользоваться методом Монте-Карло (см. §

3.2).

Здесь описывается адаптация без параметрической подстройки

(см. § 1.5). Параметрическая адаптация, если она необходима для

повышения эффективности структур, легко вводится перед стадией

отбора и осуществляется стандартными параметрическими методами

(см., например, § 3.5).

Рассмотрим в качестве примера и наиболее распространенного

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

6.1.2. Эволюционная адаптация графа

Пусть структура W описывается графом

Г = ‹A, B›. (6.1.7)

Здесь А — множество из п вершин, а В — множество ребер с их

параметрами:

B = || b

n×n

. (6.1.8)

где b

— параметры дуги, соединяющей i-ю вершину с j-й.

На графе Г задан функционал качества, который следует

минимизировать:

(6.1.9)

где S — ограничения, которым должен удовлетворять адаптируемый

граф Г в соответствии с условиями (6.1.2).

Опишем множество Ξ возможных вариаций графа δГ (6.1.1). Оно

может состоять, например, из следующих изменений:

Ξ = (ξ

, ..., ξ

), (6.1.10)

где ξ

— объединение двух случайно выбранных вершин графа в

одну; ξ

— введение новой (n+1)-й вершины со случайными

связями b

n+1,i

(i = i

, ..., i

) и b

n+1

(j = j

, ..., j

); ξ

— устра-

нение случайно выбранной вершины вместе с ее связями; ξ

—

введение новой связи двух случайно выбранных вершин; ξ

—

устранение случайно выбранного ребра; ξ

— случайное «пере-

ключение» случайно выбранной дуги, и т. д.

Как видно, спектр возможных случайных мутаций графа может

быть достаточно велик, что обеспечивает эволюции большое

разнообразие, необходимое для отыскания оптимального графа.

Значения параметров дуг графа (6.1.8) могут подстраиваться

специально на стадии параметрической адаптации, предшествующей

отбору лучших структур.

6.1.3. Эволюционная адаптация автомата

Другим важным примером является адаптация автомата. Пусть

детерминированный конечный автомат, описывающий поведение

адаптируемого объекта, имеет вид шестерки:

‹ X, Z, Y, µ(x, z), υ(x, z), z

›, (6.1.11)

где X = {x

, ..., х

} — алфавит входов и Y = {у

, ..., у

}. — алфавит

выходов, заданные связями автомата со средой; Z = = {z

, ..., z

} —

алфавит внутренних состояний автомата; z' = = µ(x, z) — функция

переходов, определяющая состояние, в которое переходит автомат из

состояния а при входе х; υ(х, z) =

= y — функция выхода, определяющая выход автомата при состоянии

z и входе х; z

— начальное состояние автомата.

В автомате можно изменять алфавит состояний Z, начальное

состояние z

и функции перехода µ(٠,٠) и выхода υ(٠,٠). Задача

оптимизации заключается в том, чтобы, варьируя эти факторы,

построить автомат, минимизирующий функционал, заданный на

изменяющихся состояниях автомата, т. е. решить задачу

(6.1.12)

Для вычисления этого функционала

необходимо иметь последовательность состояний среды х

, ..., x

, ...,

которая образует вход автомата.

Случайный поиск оптимального автомата, минимизирующего

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

преобразования графа автомата, в котором вершинами являются

внутренние состояния z

, ..., z

, а направленными дугами — условные

переходы, определяемые функцией перехода µ(х, z). Очевидно, что

операции преобразования этого графа обеспечивают соответствующее

изменение автомата.

При оптимизации структуры автомата случайные вариации его

структуры образуются, например, следующими операциями над

графом, аналогичными перечисленным в п. 6.1.2:

: введение новой вершины z

l+1

со случайными дугами, свя-

зывающими ее с другими вершинами, т. е. случайное задание функции

µ(x, z

l+1

);

: устранение случайно выбранной вершины z

(i = 1, ..., l) вместе

с ее дугами;

: введение новой дуги, связывающей две случайно выбранные

вершины z

и z

, т. е. задание функций z

= µ(х, z

) и z

= = µ(х, z

);

: устранение случайно выбранной дуги;

: случайное «переключение» случайно выбранной дуги, т. е.

переход от z

= µ(х, z

) к z

= µ(х, z

), где z

, z

и z

— случайные

вершины.

Как видно, реализация одного из указанных операторов-мутаций

несколько изменяет автомат и тем самым — значение

минимизируемого функционала. Естественно те мутации, которые

уменьшают значение функционала, считать благоприятными, а

мутации, увеличивающие его, — неблагоприятными, что и использует

процесс отбора.

Параметрическая адаптация, предшествующая этому отбору,

состоит в определении начального состояния z

и функции выхода,

задаваемой значением выхода автомата у, соответствующего паре ‹х,

z›, что эквивалентно заданию функции выхода υ(٠,٠). Это означает,

что алфавит У автомата и его начальное

Состояние z

определяются на стадии параметрического синтеза, т. е.

методами параметрической адаптации (непрерывной и дискретной),

рассмотренной в главе 4.

Направление эволюционной адаптации интенсивно развивается в

настоящее время и получило наименование эволюционного

моделирования [36, 126, 127], что связано с оценкой функционала

(6.1.12) путем моделирования поведения автомата в заданной среде.

§ 6.2. Адаптивная агрегация графов [291] 6.2.1.

Постановка задачи

Пусть имеется ориентированный граф, определяемый парой

Г = ‹ A, В ›. (6.2.1)

Здесь А — конечное множество вершин графа, каждая из которых

имеет вес

A = {a

, ..., a

}; (6.2.2)

>0 — вес i-й вершины; В — множество ребер, каждое из которых

определяется своим весом. Эти веса образуют матрицу

B = || b

n×n

, (6.2.3)

где b

≥Q — вес ребра, связывающего i-ю вершину с j-й. Нулевой вес

= 0) соответствует отсутствию ребра.

В общем случае предполагаем, что веса вершин и ребер зависят от

состояния X среды, в которую погружен объект, описываемый графом,

т. е.

= a

(X) (6.2.4)

= b

(Х).

Это состояние изменяется во времени непредсказуемым об

разом, т. е.

X = X (t). (6.2.5)

Введем агрегированный граф

Г' = ‹ A', В' ›, (6.2.6)

который получается из Г (6.2.1) путем объединения его вершин:

A' = (a'

, ..., a'

), (6.2.7)

где т<п;

/г — множество номеров вершин графа Г, объединенных (агре-

гированных) в одну вершину a'

графа Г' ( , I

∩ ∩ I

= 0

при l≠k). B' = || b'

m×m

(6.2.8)

— матрица графа Г', где

(6.2.9)

Как видно, агрегация определяется однозначно:

U = (I

, .., I

). (6.2.10)

Задача оптимальной агрегации заключается в минимизации суммы

весов ребер агрегированного графа

( 6.2.11)

при соблюдении ограничений на веса его

вершин:

(U, X) ≤ c

(l = 1, ..., k), (6.2.12)

где

C = (c

, ..., c

) (6.2.13)

— заданные верхние границы весов агрегированного графа Г',

которые определяются выделенными ресурсами.

Таким образом, для поиска оптимальной агрегации необходимо

решить следующую задачу минимизации:

(6.2,14)

где ограничения S имеют вид

S : A' (U, X) ≤ C. (6.2.15)

Решение этой задачи U

естественно назвать оптимальной агрегацией.

Она должна изменяться во времени ввиду изменения свойств среды X,

влияющей на веса вершин и ребер (6.2.4) ис-ходногр графа.

Задача адаптации заключается в поддержании агрегации в

оптимальном состоянии, зависящем от изменяющихся свойств среды

X, т. е.

= U

(X). (6.2.16)

Если свойства среды неизменны, т. е. Х=const, то задача адаптации

сводится к оптимизационной задаче (6.2.14), которую обычно

называют задачей о разрезании графа.

При медленном изменении среды адаптивная агрегация может

быть сведена к последовательному повторению решения задачи о

разрезании графа. Именно поэтому задаче адаптивной агрегации

графа предшествует задача о его разрезании. Рассмотрим ее

специфику.

Прежде всего следует отметить неоднозначность решения U

данной задачи. Действительно, решением является любая

перестановка полученной оптимальной агрегации (6.2.10), так как

оптимальность не зависит от нумерации вершин агрегированного

графа. Это сразу значительно увеличивает число оптимальных

вариантов агрегации, что очень важно при использовании алгоритмов

случайного поиска.

Далее, рассматриваемая задача является типичной задачей

структурной адаптации, поскольку полностью отсутствуют не-

прерывные составляющие в решении U

И наконец, это типичная задача эволюционной адаптации (см. §

1.5), так как при незначительном изменении агрегации (например, при

«перебросе» одной вершины) минимизируемая функция изменится

также незначительно, что позволяет воспользоваться поисковым

методом при отыскании оптимальной агрегации.

Рассмотренная постановка задачи имеет детерминированный

характер, так как изменение состояния среды X однозначно

определяет параметры (6.2.4) задачи.

Однако часто имеет место стохастическая среда, состояние

которой изменяется определенным, но известным стохастическим

образом р(Х), где р(٠) — плотность распределения измеряемых

состояний среды. При этом естественно осреднить критерий (6.2.11) и

ограничения (6.2.12) по X:

(6.2.17)

Теперь задача синтеза оптимальной

агрегации U

принимает вид

(6.2.18)

где ограничение S может иметь различный вид. Например: ог-

раничение путем осреднения

(6.2.19)

где

(6.2.20)

(6.2.21)

ограничение по максимуму

(6.2.22)

где

(6.2.23)

(6.2.24)

и т. д. — в зависимости от

содержательной постановки решаемой задачи.

Задачу (6.2.18) называют задачей стохастического програм-

мирования: ее минимизируемый критерий и ограничения яв-

ляются стохастическими характеристиками, зависящими от свойств

среды, т. е. от р(Х). Неопределенность свойств среды исключает

использование методов математического программирования и

заставляет искать другие пути решения задачи (6.2.18). Адаптация

является, пожалуй, единственным надежным способом решения этой

сложной задачи.

6.2.2. Примеры практических задач

агрегации графа

6.2.2.1. Компоновка электронной аппаратуры

Эта техническая задача элементарно сводится к задаче о

разрезании неориентированного графа в детерминированной по-

становке. Вершинами графа здесь являются элементы схемы (емкости,

резисторы, большие интегральные схемы и т. д.), а ребрами —

провода, соединяющие эти элементы. Весами вершин (6.2.2) являются

площади или объемы элементов схемы (в зависимости от целей

агрегации), а веса (6.2.3) ребер агрегируемого графа обычно равны

единице, если связь имеется, и нулю — при отсутствии электрической