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

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

натива, которая минимизирует заданный

критерий качества Q объекта в

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

Решающее правило R (5.1.1) должно

решать задачу альтернативной адаптации

по локальным наблюдениям оценок

критерия

(5.1.3)

причем состояние

Y объекта, как обычно, зависит от

управления U неизвестным образом. Это обстоятельство позволяет

записать задачу (5.1.2) в форме

(5.1.4)

где зависимость Q(U) неизвестна.

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

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

выхода которых состоит из альтернативных управлений S. Здесь

эффективно могут быть использованы автоматы с целесообразным

поведением [134] и стохастические автоматы с переменной

структурой [46]. Рассмотрим их применение для альтернативной

адаптации.

5.1.2. Алгоритмы-автоматы

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

обучения автоматов. Будем считать, что входом автомата является

сигнал, характеризующий эффективность его функционирования в

данный момент времени. Этот сигнал имеет двоичный характер:

(5.1.5)

где c=0 соответствует позитивной реакции

среды (объекта), а с=1 — негативной.

ис. 5.1.1. Блок-схема альтер-

нативной а

апта

ии.

Естественно связать этот штраф с изменением минимизирумого

критерия Q функционирования объекта. Это можно сделать

следующим образом:

(5.1.6)

где

(5.1.7)

a U'

— управление, реализованное в

объекте на N-м шаге

Так как оценка приращения критерия (5.1.7) происходит в

обстановке значительной неопределенности о состоянии среды и

оператора объекта, влияющих на эту оценку, то удобно вос-

пользоваться рекуррентным сглаживанием:

(5.1.8),

где 0<k<1 — коэффициент сглаживания.

В этом случае оценка (5.1.7) принимает вид

(5.1.9)

Теперь рассмотрим автомат с целесообразным поведением. Будем

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

функционировании автомата меньше половины, т. е.

(5.1.10)

Иначе говоря, автомат за свои действия штрафуется (с=1)

реже, чем поощряется (с=0), что, очевидно, и характеризует

целесообразность его поведения. В терминах адаптации (5.1.10)

означает, что оценка приращения критерия качества чаще от-

рицательна, чем положительна.

Заметим, что это определение целесообразности не более чем

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

выполнении условия (5.1.10) поведение будет нецелесообразным —

например, когда положительные приращения критерия (5.1.7) по

модулю значительно больше отрицательных. Именно такая ситуация

имеет место в окрестности экстремума критерия, что обычно

затрудняет реализацию точной адаптации и требует введения

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

большинстве случаев эвристика (5.1.10) работает вполне эффективно,

чем мы и воспользуемся.

Рассмотрим алгоритм адаптации как автомат, т. е. пятерку вида

A = ‹ C, W, S, µ, υ ›. (5.1.11)

Здесь С — алфавит входов (это двоичный сигнал штрафа c (5.1.5)); S

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

альтернативами; W — множество состояний автомата:

W = {w

, ..., w

}; (5.1.12)

µ — функция переходов от одного состояния к другому:

w' = µ (w, с), (5.1.13)

где w' — новое состояние, в которое переходит автомат из состояния w

при входе с; υ - функция выходов, определяющая выход автомата по

его состоянию w и входу с:

(5.1.14)

Таким образом, для определения автоматного

алгоритма адаптации объекта необходимо знать:

1) множество состояний (5.1.12);

2) функцию переходов (5.1.13);

3) функцию выходов (5.1.14).

Разные способы задания этих факторов и отличают различные

автоматные алгоритмы адаптации. Рассмотрим два из них.

5.1.2.1. Автоматы с целесообразным поведением

Из всех многочисленных автоматов с целесообразным поведением

[46, 134] наибольший интерес для альтернативной адаптации

представляют, так называемые автоматы с линейной тактикой. Они

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

результату (нештрафу, с=0), закрепляется автоматом и повторяется, а

действие, приведшее к отрицательному результату (штрафу, с=1),

автомат «стремится» сменить на другое. Так обычно поступают живые

существа. В этом и состоит линейность тактики.

Введем l — параметр глубины памяти автомата. Каждое из q

действий автомата (альтернативных решений) имеет l состояний

памяти. Тогда число состояний автомата (5.1.12) m=ql.

Функцию переходов автомата с линейной тактикой удобно

представить в виде двух графов переходов (рис. 5.1.2) для двух

состояний входа автомата. Функция выхода этого автомата образуется

так, что на различных «усах» графа переходов (ем.

Рис. 5.1.2. Графы переходов состояний автомата с линейной тактикой:

а — при с=0, б — при с=1.

рис. 5.1.2) производятся различные действия, т. е. действие U

производится при w = w

Таким образом, w

является состоянием автомата, в koтором он

производит i-e действие U

Легко видеть, что при нештрафе (с=0) последнее действие

повторяется и закрепляется, а при штрафе (с=1) внутреннее состояние

автомата изменяется так, чтобы быстрее сменить это действие на

другое. Доказано [46, 134], что в стационарной среде, т. е. при

неизменных вероятностях штрафа за каждое действие, этот автомат

асимптотически оптимален:

(5.1.15

)

где М — знак математического ожидания; a

min

— минимальная

вероятность штрафа:

(5.1.16)

— вероятность штрафа за i-e действие автомата

Асимптотическая оптимальность означает, что в стационарной

среде при увеличении объема памяти l автомат всегда будет совершать

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

Очевидно, что в нестационарной среде нельзя объем памяти

l делать слишком большим, так как при этом затрудняется

перестройка с одного действия автомата на другое. Чем более

нестационарна среда, тем меньше должен быть параметр па

мяти l.

Таким образом, при использовании автомата с линейной тактикой

для целей альтернативной адаптации эффективность

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

которого обычно представляет некоторую трудность.

Рассмотренный автомат является детерминированным. Далее

перейдем к стохастическим автоматам.

5.1.2.2. Стохастические автоматы с переменной структурой

Простейшим стохастическим автоматом с переменной структурой

является «автомат-строка», реализующий независимый выбор

альтернатив с вероятностями

= (p

, ..., p

), (5.1.17)

где

Процесс изменения структуры (обучения) такого автомата

заключается в изменении вероятностей Р на каждом шаге таким

образом, чтобы вероятность альтернативы при нештрафе

увеличивалась, а при штрафе — уменьшалась с учетом нормирования

вероятностей:

= p

N-1

+ ∆p

(i = l, ..., q), (5.1.18)

где

при U'

= U

;

при U'

= U

, (j≠i), (5.1.19)

причем

f(•)>0; φ(•,•)<0 при с = 0;

f(•)<0; φ(•,•)>0 при с = 1. (5.1.20)

На функции f и φ накладываются очевидные ограничения:

0 ≤ z + f(z) ≤ 1;

0 ≤ z + φ(z, w) ≤ 1; (5.1.21)

для любого 0 ≤ z ≤ 1 и при 0 ≤ z

≤ 1. Этим условиям

удовлетворяют, например, такие функции:

(5.1.22)

(5.1.23)

(5.1.24)

5.1.2.3. Алгоритм «многорукого

бандита»

Известная задача о «двуруком бандите» [256, 263]* может быть

интерпретирована как задача о двуальтернативной адаптации. Для

простоты рассмотрим сначала этот случай (q = 2).

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

с = 0 сохраним удачную альтернативу, т. е. будем действовать в

соответствии с линейной тактикой (рис. 5.1.3, а), а при с = 1 сохраним

первую альтернативу с вероятностью р, а вторую — с вероятностью

1—р и перейдем к другой альтернативе с дополняющими

вероятностями (рис. 5.1.3, б).

Рис. 5.1.3. Граф алгоритма двуальтернативного выбора: а — при с=0, б

— при с=1.

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

водимый в действие одной рукояткой («рукой»). Задача о «двуруком бандите»

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

при запуске автомата какой-то одной «рукой» больше, чем другой. Задача состоит

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

наибольший выигрыш, и при этом свести к минимуму про-

при с=0;

при c=l,

где всего имеется три параметра:

0<α<1; β,γ>0.

В простейшем случае β = γ = 1.

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

процессе адаптации. Очевидно, что при U

вероятность р должна

возрастать, а при U

— уменьшаться.

Для оценки р введем функцию риска [250—253]. В общем случае

ее логично записать в виде

(5.1.25)

Здесь p*

— вероятность того, что i-я

альтернатива является наилучшей, т. е.

= Вер [U

= U*] (i = l, ..., q) (5.1.26)

где U* — оптимальная альтернатива; р

— вероятность использования

i-й альтернативы алгоритмом адаптации, а υ

— ущерб, испытываемый

при использовании; i-й альтернативы, если она неоптимальна.

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

решению задачи минимизации

(5.1.27)

где S: Отсюда вытекает, что при υ

≠0 оптимальная

стратегия имеет вид (5.1.26), т. е.

P* = (p*

, ..., p*

). (5.1.28)

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

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

(5.1.26). Проведем оценивание для q = 2.

Естественно предположить, что

(5.1.29)

где Q

и Q

— средние значения показателя

качества для каждой альтернативы соответственно, а ε(σ) —

реализация независимых случайных величин с нулевым

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

Будем считать, что распределение этих случайных величин

нормальное. Тогда вероятность того, что альтернатива U

лучше U

(5.1.30)

где Φ — функция Лапласа, а «крышечкой» обозначены оценки,

которые определяются рекуррентно на каждом шаге адаптации:

(5.1.31)

Оценки

дисперсий:

(5.1.32)

(5.1.33)

при U'

N+1

= U

;

(5.1.34) если U'

N+1

= U

Здесь параметр

сглаживания µ

выбирается исходя из сведений об уровне нестационарности объекта

адаптации. Если объект стационарен, то оптимальное значение

параметра µ

= = (N — 1) / N, В нестационарном случае µ

= const и

значение его тем больше, чем больше нестационарность.

Легко видеть, что в стационарном случае

(5.1.35)

При этом р→1 при Q

и р→0 при Q

, т. е. в пределе

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

В многоальтернативном случае при c = 0 реализуется линейная

тактика, т. е. матрица переходов единичная:

(5.1.36)

При штрафе с = 1 стохастическая матрица

переходов

= || р

q×q

, (5.1,37)

имеет элементы диагональные:

= p

(5.1.38)

из (4.1.26) и недиагональные:

= υ

Bep ( U

) (i ≠ j = 1, ..., q), (5.1.39)