Растригин Л.А. Адаптация сложных систем
Подождите немного. Документ загружается.
Таким образом, задача сводится к определению оценки (4.7.42).
Именно для нее и предлагается воспользоваться методом Монте-
Карло. Сделать это можно следующим образом.
Пусть надо оценить частную производную по параметру c
i
.
(4.7.43)
Как известно,
(4.7.44)
где
(4.7.45)
Т — объем «разыгрываний» случайной величины х; t = t (δ, C) —
число попаданий х в промежуток [x
(N)
— δ, x
(N)
+ δ] при параметрах С.
Ограничиваясь конечным значением Т, можно для (4.7.44) получить
следующую приближенную оценку:
(4.7.46)
Выбор величины промежутка δ должен быть
оптимальным. Действительно, δ не должна быть слишком малой, так
как тогда t будет мало, оценка (4.7.46) будет слишком грубой и
понадобится значительно увеличить объем Т, чтобы уточнить оценку.
С другой стороны, величина δ не должна быть слишком большой,
иначе оценка будет носить не локальный характер.
Теперь частные производные (4.7.46) можно представить в виде
приближенных выражений:
(4.7.47)
где e
i
(i = 1, ..., k) —
орт i-й координаты пространства искомых параметров {С}. Здесь t (δ,
С ± ∆
i
e
i
) обозначает число попаданий случайной величины х в зону
x
(N)
— δ < x < x
(N)
+ δ при параметрах С, варьированных на величину
±∆
i
по параметру c
i
, т. е. c
i
→ c
i
± ∆
i
.
Выбор величины ∆
i
, как и δ, должен быть оптимальным — как при
всяком численном дифференцировании.
Любопытно, что оценка (4.7.47) не зависит явно от объема
испытаний Т. Однако этот объем должен быть одинаков для оценки t
при обеих вариациях параметров ±∆
i
.
Предложенный метод может примениться для идентификации
параметров оптимизируемого объекта и как средство для организации
оптимального поиска. Такими параметрами o6ъекта, необходимыми
для построения оптимальных алгоритмов поиска экстремума,
являются модуль градиента показателя качества, дисперсия помехи,
кривизна гиперповерхностей равного уровня показателя качества и др.
§ 4.8. Адаптивный синтез
датчика случайных чисел
с заданной автокорреляционной функцией
Задача синтеза датчика случайных процессов с заданными
корреляционными свойствами представляет собой сложную вы-
числительную проблему [207]. Применение адаптивного подхода
позволяет построить довольно простой алгоритм синтеза такого
датчика, который легко реализуется на ЦВМ [162].
Рассмотрим центрированные случайные процессы в дискретном
времени, получаемые при помощи следующего линейного
рекуррентного выражения:
(4.8.1)
Здесь x
t
— значение случайной функции
х в момент t; ε
t
— независимые случайные числа с нулевым
математическим ожиданием и единичной дисперсией. Простейший
частный случай выражения. (4.8.1) при п = т = 1 рассмотрен и
подробно проанализирован в работе [160]. Автокорреляционная
функция процесса (4.8.1)
K (q) = M
t
(x
t
x
t-q
), (4.8.2)
где M
t
— знак математического ожидания, очевидно, зависит от
параметров р
1
, ..., p
n
, a
1
, ..., а
т
датчика. Задача синтеза случайного
процесса с заданными корреляционными свойствами заключается в
определении указанных параметров так, чтобы полученная
автокорреляционная функция K(q) наименьшим образом уклонялась
от заданной K
0
(q).
В качестве меры этого уклонения (невязки) могут быть
предложены различные функции, например
(4.8.3)
где F — четная положительная функция, или
(4.8.4)
Очевидно, что эта функция зависит от параметров датчика, которые
следует подобрать так, чтобы минимизировать невязку Q, т. е. решить
задачу
4.8.5) где
P = (p
1
, ..., p
n
); (4.8.6)
A = (a
1
, ..., a
m
).
Заметим, что каждое определение минимизируемой функции Q (P, A)
по формуле (4.8.3) или (4.8.4) всегда связано с вычислением
корреляционной функции (4.8.2), что крайне трудоемко. Так, в работе
[243] эта задача решалась аппаратурно с применением
автоматического оптимизатора, причем основные потери были
связаны с оценкой автокорреляционной функции при заданных
параметрах Р и А.
Однако в случае линейной зависимости (4.8.1) удается получить
явные выражения для корреляционной функции K(q) (4.8.2) в
зависимости от параметров Р и А. Для этого достаточно решить
некоторую систему линейных алгебраических уравнений, вывод
которой приведен ниже.
Используя выражение (4.8.2) и предполагая, что K(0) = = D(x) = 1;
D(ε) = 0; M(ε
i
ε
j
)=0 (i≠j), получаем после подстановки (4.8.1) в (4.8.2) и
ряда преобразований следующее рекуррентное выражение для
автокорреляционной функции процесса (4.8.1):
(4.8.7)
где l(t) определяется
также рекуррентно:
для t < 0;
для t ≥ 0, (4.8.8)
причем a
m+t
= 0 для t>0. Как видно, эти формулы для заданных Р и А
дают возможность довольно просто вычислить все необходимые
значения автокорреляционной функции K(q) и
далее определить степень ее невязки Q с заданной функцией К
0
(q) по
формуле (4.8.3) или (4.8.4).
Чтобы начать этот рекуррентный процесс определения К(q),
необходимо знать п начальных значений автокорреляционной
функции, из которых известно только одно К(0) = 1. Для этого
достаточно решить линейную систему уравнений (n-1)-го порядка
относительно K(1), ..., К(п—1), которая получается из (4.8.7) при q = 1,
2, ..., n-1. Автокорреляционную функцию естественно считать четной,
т. е. K(q) = K(—q).
На выбор параметров Р и А накладывается ряд ограничений. Одно
из них связано с единичной дисперсией генерируемого процесса и
выражается равенством
(4.8.9)
Другие ограничения
накладываются на выбор параметров и выражаются в виде очевидных
неравенств:
| K(q) | ≤ 1 (q = 1, 2, ...), (4.8.10)
которые обеспечивают устойчивость генерируемого случайного
процесса (4.8.1). Это условие эквивалентно выполнению критерия
Гурвица для разностных уравнений [235]. В процессе поиска значения
искомых параметров, которые приводят к нарушению указанных
ограничений, следует отбрасывать.
Как легко видеть, определение корреляционной функции K(q) при
любом q представляет собой следующую процедуру.
1. Для заданных значений Р и А решается линейная система
уравнений (4.8.7) при q = l, ..., n-1, из которой определяются
K (1), ..., K (n-1).
2. Последующие значения K(q) при q≥n определяются рекуррентно
из системы (4.8.7).
Решение задачи (4.8.5) определения параметров Р и А теперь
представляется в виде
(4.8.11).
где ограничения S образуются равенством
(4.8.9) и неравенствами (4.8.10). Решение задачи (4.8.11) и дает
искомые значения параметров
P
*
= (p
*
1
, ..., p
*
n
); (4.8.12)
A
*
= (a
*
1
, ..., a
*
m
)
датчика (4.8.1), автокорреляционная функция которого K(q)
наименьшим образом отличается от заданной К
0
(q).
Задача (4.8.11) имеет п+т переменных, что при больших п
затрудняет процесс поиска оптимума. Число неизвестных переменных
можно сократить до m в случае, когда автокорреляционная функция
К
0
(q) задана точно (а не получена в результате наблюдений). Делается
это следующим образом.
Формула (4.8.7), как можно заметить, при q≥т принимает
простой вид:
(4.8.1З)
Очевидно, что для определения Р достаточно
положить K(q) = = К
0
(q) и взять п реализаций этой формулы при q =
m, ..., m — — n—1. Получаем систему уравнений, линейных
относительно неизвестных р
1
, ..., р
п
:
(4.8.14)
Здесь предполагается, что
К
0
(-q) = К
0
(q).
Разрешая эту систему,
получим Р. Этим число
неизвестных параметров сократится до т: а
1
, ..., а
т
. Однако
если исходная функция К
0
(q) получена приближенно — например, в
результате соответствующей обработки конечной реализации случай-
ного процесса, то этим приемом воспользоваться нельзя и поиск
следует производить по всем переменным.
Рассмотрим теперь несколько наиболее распространенных
случаев.
Случай п = 1, т = 2. Формула (4.8.1) принимает вид
x
t
= px
t-1
+ a
1
ε
t
+ a
2
ε
t-1
.
Корреляционная функция (4.8.7):
Условие устойчивости: |р|<1. Параметры р, а
1
, а
2
связаны следующим
очевидным соотношением:
p
2
+ a
1
2
+ a
2
2
+ pa
1
a
2
= 1.
На рис. 4.8.1 показан характер поведения полученной корреляционной
функции при различных значениях параметра а
2
. Из
этих графиков хорошо видно, что, варьируя значения а
2
, можно
достаточно произвольно изменять значение К(1). Последующее
поведение корреляционной функции при q>0 имеет экспонен-
циальный характер.
С л у ч а й n=1, m>1. Нетрудно убедиться, что в этом случае
экспоненциальный характер функции автокорреляции проявляется
лишь при q≥m. Ее значения при 0<q<m могут быть, вообще говоря,
достаточно произвольными, но в естественных пределах,
обеспечивающих | K(q) | ≤ 1. Это обстоятельство позволяет
синтезировать широкий класс функций с экспоненциальным
«хвостом».
Случай n=2, m=l приводит к следующей рекуррентной формуле
для корреляционной функции (q>0):
K (q) = p
1
K(q-1) + p
2
K (q-2)
с начальными значениями
Из естественных условий | K(1) | ≤ 1 и | К(2) | ≤ 1 получаем уравнения
для допустимой области параметров, обеспечивающих устойчивость
генерируемого случайного процесса:
p
1
+ p
2
≤ 1;
p
1
- p
2
≥ 1;
p
2
≥ -1.
На плоскости параметров (рис. 4.8.2) эта область имеет форму
равнобедренного треугольника, каждая точка которого опреде-
Рис. 4.8.1. Поведение корреляционной Рис. 4.8.2. Область допустимых пара-
Функции для случая n=l, m=2. метров (n=2, m=l). Наборы точек
«а» и «б» соответствуют кривым на
рис. 4.8.3.
Рис. 4.8.3. Характер поведения корреляционных функций
при значениях параметров, отмеченных точками на рис.
4.8.2: а — р
1
=1, б — p
2
= —0,7.
ляет корреляционную функцию. Характер поведения этих функций
показан на рис. 4.8.3 для значений параметров, отмеченных на рис.
4.8.2 точками. Из рисунков хорошо видно, что рассматриваемый
случай весьма богат разнообразием корреляционных функций.
Случай п=т=2. Рекуррентная формула при q≥0 имеет тот же вид,
что и для предыдущего случая. Однако
Следовательно, не изменяя характера поведения корреляционной
функции при q≥2, можно, варьируя произведение а
1
а
2
, несколько ее
деформировать.
Проиллюстрируем это на следующем простом примере. Для
реализации случайного процесса с корреляционной функцией вида
K
0
(q) = e
-αq
cos ωq
следует воспользоваться рассмотренным случаем (п=т=2). Так как
затухание α и частота ω корреляционной функции не зависят от
начальных значений функции, то эти параметры могут быть
определены при а
2
= 0, т. е. так же, как и в предыдущем случае (n=2,
m=l).
На рис. 4.8.4 показаны корреляционные функции с неизменными
полученными значениями параметров p
1
= l,5; p
2
= —0,7 и
различными а
2
. Хорошо видно, что затухание и частота при этом не
изменяются.
Выбор оптимального значения а
2
производится путем мини-
мизации функции невязки
которая зависит лишь от одного параметра К(1).
На рис. 4.8.5 показан характер поведения этой функции для
значений α=0,184 и ω = 0,482, которые обеспечиваются р
1
= = 1,5 и р
2
= —0,7 при N=20. Хорошо виден экстремальный характер этой
зависимости. Следует отметить ненулевое значение невязки в
экстремальной точке K(1) =0,747, хотя в принципе, как показано в
работе [207], экстремум равен нулю. Это объясняется ограниченной
точностью расчетов (не превышавшей третьего знака после запятой),
что и дало в сумме минимальное значение невязки Q
min
= 0,091.
Рuc. 4.8.4. Поведение
корреляционных функций
(n=m=2) при изменении
а
1
a
2
(значения указаны на
рисунке).
Рис. 4.8.5. Экстремальная зависимость
функции невязки от К(1).
В заключение отметим, что предлагаемый способ синтеза
рекуррентной зависимости (4.8.1) может быть использован как метод
кодирования встречающихся корреляционных функций.
Действительно, в пространстве {Р, А} каждая точка определяет
некоторую корреляционную функцию K(q). При заданной невязке
Q(P,А) для любой корреляционной функции K
0
(q) можно найти вектор
(Р
*
, А
*
), минимизирующий эту невязку. Параметры этого вектора и
определяют код функции K(q).
Другой особенностью предлагаемого метода является простота его
программирования на ЦВМ. Действительно, по сути дела,
определение необходимых параметров сводится к многократному
решению системы линейных алгебраических уравнений и к процессу
многопараметрической оптимизации, что очень просто реализуется
путем применения соответствующих стандартных программ.
Параметрическая адаптация является наиболее разработанным
инструментом адаптация — как в алгоритмическом, так и в
прикладном плане. Однако ее ограниченность, связанная с тем, что
далеко не все объекты удается «разъять» до параметров, заставляет
искать новые типы адаптации, которым посвящены две последующие
главы.
Альтернативн
ая адаптация
Быть иль не быть, вот в чем вопрос...
Шекспир. «Гамлет»
Когда число варьируемых состояний объекта невелико, следует
обращаться к альтернативной адаптации, которая позволяет
поддерживать в объекте оптимальное состояние. При этом ес
тественно воспользоваться автоматными моделями адаптации.
В данной главе рассматриваются два алгоритма альтернатив
ной адаптации — детерминированные автоматы с целесообраз
ным поведением и стохастические автоматы с переменной струк
турой. Эти автоматы применяются для переключения алгорит
мов при решении задач адаптивной поисковой оптимизации,
адаптивной сортировки массивов, адаптивного выбора способа
кодирования при передаче данных по каналу связи и адаптив
ного определения длины информационной части пакета в ка
нале связи двух ЭВМ.
§ 5.1. Алгоритмы альтернативной адаптации
5.1.1. Постановка задачи
Пусть 5 — множество возможных альтернатив, допустимых в
процессе адаптации
S = {U
1
, ..., U
q
},
где q — число таких альтернатив. Задача адаптации (1.2.9) (см.
первую главу) в данном случае заключается в указании, какую
альтернативу следует реализовать в сложившейся ситуации в среде X
и объекте Y. Эта задача решается правилом (алгоритмом) R:
U
j
=R (X, Y, U
i
), (5.1.1)
где U
i
, U
j
S. Проще говоря, алгоритм адаптации является, по сути
дела, управляемым переключателем (рис. 5.1.1), с помощью которого
в объекте адаптации поддерживается та альтер-