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

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

где υ

— нормирующий множитель:

(5.1.40)

Отсюда видно, что при штрафе i-я

альтернатива сохраняется с вероятностью, равной оценке вероятности,

что эта альтернатива оптимальна, и изменяется на j-ю вероятностью,

пропорциональной вероятности того, что j-я альтернатива лучше i-й.

Оценки вероятностей производятся подобно (5.1.30) с использованием

оценок, аналогичных (5.1.31) — (5.1.34).

Анализ показывает, что изложенный алгоритм адаптации

позволяет находить оптимальную альтернативу и перестраиваться на

другую, еще более эффективную, в случае изменения оптимальной

альтернативы.

§ 5.2. Исследование алгоритмов

альтернативной адаптации

Рассмотрим аналитически процессы, происходящие во время

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

структурой. Для простоты будем изучать двуальтернативный (q=2)

процесс [86].

Пусть имеются конкурирующие альтернативы U

и U

. Ве-

роятность предпочтительности одной альтернативы перед другой p =

Bep (U

) априори неизвестна и может изменяться во времени, т. е.

p = p

. Способ выбора одной из них, осуществляемый в каждый

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

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

альтернативной адаптации.

Решение подобной задачи заключается в реализации в каждый

момент времени простого правила:

(5.2.1)

и связано с оценкой величины р

Использование классических процедур

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

изменения p

, либо предположения о стационарности

последовательности {p

}, в настоящей постановке, отвечающей

реальным условиям, невозможно. Это заставляет обращаться к

адаптивной процедуре.

Представим результаты экспериментов с альтернативами U

и U

дискретные моменты времени t = 1, 2, ... в виде последовательности

{α

(5.2.2)

Для простоты предположим, что Bep (U

) = 0, где «~» — знак эквивалентности альтернатив по заданному

критерию. Однако при необходимости эквивалентность альтернатив

можно учесть с помощью α

= 0. Тогда, очевидно, Вер (α

= 1) = p

. В

каждый момент времени t процедура должна по результату at

«рекомендовать» выбор U

или U

Определим индикаторную функцию p'

результатов а эксперимента

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

(при этом U

выбирается с вероятностью 1 — p'

). Подчиним такую

индикаторную функцию естественному требованию: если в течение

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

>1/2 (<1/2), то p'→l (→0)

при t→∞. Кроме того, указанная тенденция в поведении p't в

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

противоположную при переходе значений p

из интервала (1/2, 1] в [0,

1/2), что и обеспечивает адаптивность процедуры.

Индикаторную функцию p'

, удовлетворяющую сформули-

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

итеративных процедур вида

t+1

= p'

+ λ

t+1

, (5.2.3)

где p'

и {λ

} — детерминированные параметры (0≤p'

≤l; 0≤ ≤λ

≤l); b

(1—p'

); {α

} — последовательность независимых в совокупности

случайных величин с распределениями Вер (α

= 1) = p

, Вер ( α

= —1)

= 1 — p

(0≤p

≤1). Процесс (5.2.3) является марковским. Если р'

= 0, то

= 0; если р'о= = 1, то p'

= 1. Иначе говоря, точки 0 и 1 являются

неподвижными для преобразования (5.2.3). Чтобы исключить эти и

другие особые случаи, будем полагать 0<р'

, λ

, p

<l. При этих

условиях, очевидно, 0<р'

<1 почти наверное (п. н.) при t = = 1, 2, ...

Теорема 1. Пусть p

≤p<1/2 (p

≥p>l/2) при t=l,2,... Тогда если

≤λ<1-2p (λ

≤λ<2p-1) и

(

5.2.4) то p'

→0 (p'

→l) п. н. и в среднем при t→∞.

Доказательство основано на стохастическом аналоге второго

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

теорем (2.5.2) и (2.7.1) в работе [138]. В качестве функции Ляпунова

выбирается V(x)=x/(1—х), х

[0; 1). При p

≥p>l/2 вводятся обозначения x

= 1—p'

, β

t+1

= = —α

t+1

и процесс (5.2.3) можно записать в виде x

t+1

= x

+ + λ

t+1

Аналогично для случая р

≤р<1/2.

Оценка среднего приращения V(x) по процессу (5.2.3) за один шаг

на t-м фиксированном шаге (при р

≤p<1/2)

M {V (p'

t+l

) - V(p'

) / p'

} ≤ λ

t+1

V (p'

)[λ-(l-2p)]. (5.2.5)

Следствие. Пусть процесс (5.2.3) стационарен, т. е. р

≡ ≡ р, λ

≡ λ.

Тогда если р<1/2 (р>1/2) и λ<1-2р (λ>2р-1), то p'

→0 (→1) при t→∞ п.

н. и в среднем.

Оценим скорость сходимости процесса (5.2.3) к нулю. Пусть

≥l>0. Из выражения (5.2.5) следует:

Поскольку функция V(x) выпукла, то, воспользовавшись не

равенством Йенсена [231], получим оценку скорости сходимо

сти в среднем:

(5.2.6)

Оценку (5.2.6) можно заменить на менее сложную (но и более

грубую):

(5.2.7)

Легко проверить, что правая часть

выражения (5.2.7) минимальна при l=λ=1/2—р. При этом

5.2.8) Из (5.2.3) можно

непосредственно оценить Mp'

и p'

снизу:

р'

> (1-λ)

п. н. (5.2.9)

Пусть теперь p

≥p>1/2 и

0<l≤λ

≤λ<2р-1. Проведя те же преобразования, что и при

доказательстве теоремы 1, получим оценки, аналогичные (5.2.6) —

(5.2.9), скорости сходимости

процесса (5.2.3) в среднем к единице. При этом в левых частях

неравенств окажется M(1 — p'

), а в правых вместо (1 — 2р) следует

записать (2р — 1).

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

} существенно

нестационарна, т. е. при различных t вероятности p

могут быть как

больше 1/2, так и меньше. Обозначим β

= = Mα

= 2p

— 1. Не

ограничивая общности, будем считать р < 1/2,

(5.2.10)

Будем говорить, что Т

, Т

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

a T

, T

, .... — положительной квазистационарности. В этих условиях

процесс (5.2.3), вообще говоря, не будет сходиться к 0 или к 1 при

t→∞. Однако при t T

последовательность {p'

} будет иметь

определенную тенденцию — монотонно приближаться в среднем к

нулю или к единице в зависимости от четности i.

Далее ограничимся классом процедур вида (5.2.3), в которых λ

≡ λ

(условие (5.2.4) всегда выполнено). Пусть p't

произвольно, но

фиксированно и T

= {t

+ l, ...}, т. е. t

i+1

=∞. Тогда

по теореме 1, если при , то р'

→0

(р'

→1) п. н. Если , то

сходимость к нулю (единице) теоремой 1 не гарантируется, однако

Mp'

монотонно убывает (возрастает) при t→∞. Параметр λ тем самым

определяет области чувствительности процедуры (5.2.3).

Назовем число порогом чувствительности про-

цедуры (5.2.3), если оно удовлетворяет априорному требованию: р'

→0

и р'

→1 по крайней мере при и . Эта

цель будет достигнута при любом λ<2γ. Однако, как следует из

формул (5.2.6) — (5.2.9), скорость сходимости различна при разных λ.

Легко проверить, что при заданном γ скорость сходимости в среднем

оптимальна, если λ=γ.

Пусть промежуток Т

имеет конечную длину. Тогда при помощи

формул (5.2.6) — (5.2.9) можно оценить, как близко про-

цесс (5.2.3) успеет подойти к 0 или 1. Эти оценки существенно зависят

от начального значения р'

, в качестве которого здесь будет выступать

реализация случайной величины p't

. Чем ближе реализация p't

например, к 1, тем медленнее p't приближается к 0. Другими словами,

чем лучше процесс (5.2.3) адаптировался к одному режиму, тем хуже

он перестраивается при изменившихся условиях. Кроме того,

поскольку все вычисления (и на ЭВМ) округляются, то при

реализации p't

, достаточно близкой к единице (или к нулю), процесс

(5.2.3) уже не выйдет из точки 1 (или 0) ни при каких последующих

значениях p

В реальных задачах всегда можно априори задать точность

адаптации ε таким образом, что приближение p't к 0 или 1 ближе, чем

на ε, не является практической необходимостью. Воспользовавшись

такой ситуацией, можно избежать губительной «переадаптации»

процедуры (5.2.3).

Пусть {α

}, λ, {b

} — те же, что и в процессе (5.2.3), и ε≤p'

≤l—ε.

Определим новый процесс, который назовем ε — адаптивной

процедурой выбора:

(5.2.11)

где x

t+1

= p'

+ λα

t+1

Организованная таким образом индикаторная функция удов-

летворяет условию ε≤p't≤l—ε п. н. при t = 1, 2, ... Следовательно,

процедура (5.2.11) приобретает способность к быстрой переадаптации.

Асимптотические свойства процессов (5.2.11) и (5.2.3) различны.

Однако поскольку при ε≤p't≤l—ε п. н. они совпадают, то формулы

(5.2.6) — (5.2.9) являются некоторыми характеристиками и процедуры

(5.2.11). Пусть . Не ограничивая общности, будем считать

промежуток Т

отрицательно квазистационарным. Тогда, как следует

из выражения (5.2.6),

(5.2.12)

Эта оценка справедлива для процесса (5.2.11) до тех пор, пока р't≥ε п.

н. Поскольку p't>p't

(1-λ)

t-t

п. н., то, предполагая процесс адаптации на

промежутке T

i-1

законченным, т. е. p't

= = 1—ε, найдем время, в

течение которого справедливо (5.2.12):

Процедура (5.2.11) по существу «отрезает» те траектории процесса

(5.2.3), которые опускаются ниже уровня ε (поднимаются выше 1—ε).

Поэтому может оказаться полезной оценка максимального времени

достижения ε-уровня процессом (5.2.3) в среднем при условии, что он

начинается из состояния ε≤ ≤p't

≤1—ε п. н. Несложными

преобразованиями из выражения (5.2.3) получим

Эта косвенная характеристика процесса (5.2.11), которую назовем

временем ε-адаптации, однозначно определяется задаваемыми

параметрами самого алгоритма и не зависит от поведения {α

Легко проверить, что время T(ε,γ,λ) минимально при λ=γ, что

соответствует найденной выше оптимальной скорости сходимости

процесса (5.2.3). При этом Т(ε,γ,λ)

опт

= Т(ε,γ) =

Чтобы практически использовать процедуру (5.2.11), необхо

димо определить согласно смыслу задачи точность ε и порог

чувствительности γ. Полагая затем в формуле (5.2.11) λ=γ,

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

Т(ε,γ).

§ 5.3.

Альтернативная адаптация

в процессах поисковой оптимизации

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

оптимизации [168].

Проблема поисковой оптимизации возникла в связи с необ-

ходимостью решения сложных задач типа математического

программирования:

(5.3.1)

возникающих при алгоритмизации процессов

управления, принятии оптимальных решений и т. д. Здесь Q(X) —

скалярная функция качества векторного аргумента Х=(x

,...,x

), опре-

деленного в области Ω. Эта область может быть или континуальной и,

задаваться системой равенств и неравенств:

(5.3.2)

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

аргумента:

Ω : {X

} (i = l, ...), (5.3.3)

или сочетанием этих ограничений. Возможны и другие формы

задания области Ω.

Сложность решения (5.3.1) для мало-мальски реальных задач

заключается прежде всего в том, что функция Q(X) и область Ω заданы

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

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

неформальный (экспертный) характер. Это обстоятельство

практически исключает применение стандартных методов

математического программирования, опирающихся на известную

структуру и вид функции Q(X) и области Ω.

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

решения X

, удовлетворяющего очевидному условию

(5.3.4)

Суть поискового метода отыскания X

сводится к построению

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

, X

, ..., X

, ..., (5.3.5)

которая должна сходиться к достаточно малой окрестности решения

. Алгоритм поиска F связывает следующие друг за другом

состояния:

N+1

= F (X

, W

), (5.3.6)

где W

— фактор предыстории, например W

= {X

N-1

, ..., X

N-l

}; l —

глубина предыстории. Однако удобнее алгоритм F определять для

смещения

∆X

N+1

= F (X

, W

), (5:3.7)

связывающего два соседних состояния X

N+1

= X

+ ∆X

N+1

в про-

странстве оптимизируемых параметров {X}.

Очевидно, что алгоритм F должен удовлетворять определенным

требованиям, предъявляемым к процессу поиска решения задачи. Эти

требования можно представить в виде набора критериев,

характеризующих эффективность процесса поиска:

K = (k

, ..., k

). (5.3.8)

Каждый из критериев зависит от алгоритма F и ситуации L, сло-

жившейся в процессе оптимизации:

L = ‹ Q (X), L ›. (5.3.9)

Таким образом, каждый критерий в (5.3.8) имеет вид

= k

(F, L) (i = 1, ..., m). (5.3.10)

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

задаче оптимизации:

(5.3.11)

где — оптимизируемый критерий

эффективности алгоритма F, выбранный из множества (5.3.10); Е —

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

критериям из (5.3.10). Решением задачи (5.3.11) является оптимальный

алгоритм F

, зависящий, естественно, от ситуации L.

Введя понятие класса ситуаций

{L} = {Q (X), L} (5.3.12)

и правило оценки критерия на этом классе (например, как

максимума или среднего на классе), получаем оптимальные

алгоритмы поиска. Примерами таких оптимальных алгоритмов

являются известные алгоритмы Кифера и Ньютона: первый —

для класса одномерных унимодальных функций без случай

ных помех, заданных на ограниченном интервале, при мини

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

определенности в оценке положения экстремума; второй — для

класса положительно-определенных квадратичных форм при

Ω=R

и отсутствии случайных помех.

Однако число подобных оптимальных алгоритмов весьма мало, да

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

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

конкретного объекта к тому или иному классу, для которого построен

оптимальный алгоритм. Именно это обстоятельство заставляет

обращаться к адаптации алгоритмов поиска, т. е. приспосабливать

алгоритм на каждом шаге к сложившейся ситуации L (здесь под

ситуацией понимается уже не вся задача оптимизации (5.3.9), а лишь

ее локальный фрагмент в окрестности точки X

Представим алгоритм F поиска в виде двойки

F = ‹S, C›, (5.3.13)

где S — его структура, а С = (с

, ..., c

) — параметры. Такое разделение

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

структуры алгоритма. Однако интуитивно структурные категории

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

специалистами по поиску.

Адаптация алгоритма F может производиться по двум на-

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