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

Рассмотрим аналитически процессы, происходящие во время альтернативной адаптации, с помощью автомата с переменной структурой. Для простоты будем изучать двуальтернативный процесс [86].

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

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

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

Использование классических процедур оценивания, требующих либо априорных сведений о характере изменения либо предположения о стационарности последовательности в настоящей постановке, отвечающей реальным условиям, невозможно. Это заставляет обращаться к адаптивной процедуре.

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

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

Определим индикаторную функцию результатов а эксперимента как вероятность, с которой на шаге следует выбирать альтернативу (при этом выбирается с вероятностью Подчиним такую индикаторную функцию естественному требованию: если в течение достаточно долгого времени выполняется при Кроме того, указанная тенденция в поведении в соответствии с постановкой должна достаточно быстро меняться на противоположную при переходе значений из интервала (1/2, 1] в [0, 1/2), что и обеспечивает адаптивность процедуры.

Индикаторную функцию удовлетворяющую сформулированным требованиям, будем искать в классе стохастических итеративных процедур вида

где — детерминированные параметры — последовательность независимых в совокупности случайных величин с распределениями Процесс (5.2.3) является марковским. Если , то если то Иначе говоря, точки 0 и 1 являются неподвижными для преобразования (5.2.3). Чтобы исключить эти и другие особые случаи, будем полагать При этих условиях, очевидно, почти наверное (п. н.) при

Теорема 1. Пусть при Тогда если и

то п. н. и в среднем при

Доказательство основано на стохастическом аналоге второго метода Ляпунова и проводится по той же схеме, что и доказательство теорем (2.5.2) и (2.7.1) в работе [138]. В качестве функции Ляпунова выбирается . При вводятся обозначения и процесс (5.2.3) можно записать в виде Аналогично для случая .

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

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

Оценим скорость сходимости процесса (5.2.3) к нулю. Пусть Из выражения (5.2.5) следует:

Поскольку функция выпукла, то, воспользовавшись не равенством Иенсена [231], получим оценку скорости сходимо в среднем:

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

Легко проверить, что правая часть выражения (5.2.7) минимальна при При этом

Из (5.2.3) можно непосредственно оценить снизу:

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

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

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

Рассмотрим ситуацию, когда последовательность существенно нестационарна, т. е. при различных вероятности могут быть как больше 1/2, так и меньше. Обозначим Не ограничивая общности, будем считать

Будем говорить, что являются промежутками отрицательной, а — положительной квазистационарности. В этих условиях процесс (5.2.3), вообще говоря, не будет сходиться к 0 или к 1 при Однако при последовательность будет иметь определенную тенденцию — монотонно приближаться в среднем к нулю или к единице в зависимости от четности

Далее ограничимся классом процедур вида (5.2.3), в которых (условие (5.2.4) всегда выполнено). Пусть произвольно, но фиксированно и Тогда по теореме 1, если то п. н. Если сходимость к нулю (единице) теоремой 1 не гарантируется, однако монотонно убывает (возрастает) при Параметр X тем самым определяет области чувствительности процедуры (5.2.3).

Назовем число порогом чувствительности процедуры (5.2.3), если оно удовлетворяет априорному требованию: по крайней мере при Эта цель будет достигнута при любом Однако, как следует из

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

Пусть промежуток имеет конечную длину. Тогда при помощи формул (5.2.6) — (5.2.9) можно оценить, как близко процесс

(5.2.3) успеет подойти к 0 или 1. Эти оценки существенно зависят от начального значения , в качестве которого здесь будет выступать реализация случайной величины Чем ближе реализация например, к 1, тем медленнее приближается к 0. Другими словами, чем лучше процесс (5.2.3) адаптировался к одному режиму, тем хуже он перестраивается при изменившихся условиях. Кроме того, поскольку все вычисления (и на ЭВМ) округляются, то при реализации достаточно близкой к единице (или к нулю), процесс (5.2.3) уже не выйдет из точки 1 (или 0) ни при каких последующих значениях

В реальных задачах всегда можно априори задать точность адаптации 8 таким образом, что приближение к 0 или 1 ближе, чем на не является практической необходимостью. Воспользовавшись такой ситуацией, можно избежать губительной «переадаптации» процедуры (5.2.3).

Пусть — те же, что и в процессе (5.2.3), и Определим новый процесс, который назовем — адаптивной процедурой выбора:

Организованная таким образом индикаторная функция удовлетворяет условию п. н. при Следовательно, процедура (5.2.11) приобретает способность к быстрой переадаптации.

Асимптотические свойства процессов (5.2.11) и (5.2.3) различны. Однако поскольку при п. н. они совпадают, то формулы (5.2.6) — (5.2.9) являются некоторыми характеристиками и процедуры (5.2.11). Пусть Не ограничивая общности, будем считать промежуток отрицательно квазистационарным. Тогда, как следует из выражения (5.2.6),

Эта оценка справедлива для процесса (5.2.11) до тех пор, пока п. н. Поскольку п. н., то, предполагая процесс адаптации на промежутке законченным, т. е. найдем время, в течение которого справедливо (5.2.12):

Процедура (5.2.11) по существу «отрезает» те траектории процесса (5.2.3), которые опускаются ниже уровня 8 (поднимаются выше 1—е). Поэтому может оказаться полезной оценка максимального времени достижения -уровня процессом (5.2.3) в среднем при условии, что он начинается из состояния п. н. Несложными преобразованиями из выражения (5.2.3) получим

Эта косвенная характеристика процесса (5.2.11), которую назовем временем -адаптации, однозначно определяется задаваемыми параметрами самого алгоритма и не зависит от поведения

Легко проверить, что время минимально при что соответствует найденной выше оптимальной скорости сходимости процесса (5.2.3). При этом

Чтобы практически использовать процедуру (5.2.11), необхо димо определить согласно смыслу задачи точность 8 и порог чувствительности у. Полагая затем в формуле получим оптимальный процесс со средним временем адаптации