Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

7.4. Стохастическая аппроксимация при оптимальных параметрах процесса. Роль гипотез

Определение оптимальных последовательностей корректирующих коэффициентов ставит самостоятельные задачи перед исследователем, поскольку соответствующие результаты во многом зависят от предполагаемых свойств функции zи = f(х) и особенностей применяемой схемы поиска х*.

Процедура Роббинса - Монро

Пусть известно, что zи принадлежит классу линейных функций, т. е. zи=Ax+B. Следовательно, истинное значение корня есть х* = -В/А. Поскольку Yi = xi-aizиi и σ2[Ri] = a2σ2z], выражение критерия принимает вид Ki = (ai-1/A)2(Axi+B)2+a2iσ[δz]*. Стремясь достичь min Ki, будем выбирать аi из условия dKi/dai = 2(ai-1/А) (Axi + B)2+2aiσ2z] = 0, что дает

(7.3)

Анализ формул (7.3) позволяет сделать следующие выводы:

- каким бы ни был уровень помех при данном i, знание класса функций, к которому принадлежит zи = f(x), оказывается недостаточным; нужно по крайней мере знать А и быть уверенным в том, что отношение σ2z]/(Axi + B)2 меняется с изменениями i должным (в смысле требований сходимости) образом;

- наилучший результат поиска (точное решение задачи) достигается при σ[δz] = 0 и aiopt = 1/A = const; здесь K imin = 0;

- наихудший результат поиска получается при σ[zz]→∞; здесь первое же значение aiopt обращается в нуль, и поиска как такового не будет, причем Kimin есть квадрат расстояния между х* и исходной точкой x1;

- при любой конечной дисперсии 0<σ2<∞ ответ на вопрос о величинах aiopt и Kimin может быть дан лишь на основе каких-то дополнительных сведений о В.

* (Индекс "i" в обозначении δz здесь опущен, чтобы не загромождать последующие формулы.)

Чтобы конкретизировать последнее замечание, обратимся к иллюстративному примеру. Ясно, что точное знание В сняло бы в целом задачу поиска, так как при известном А легко вычислить х* = -В/А, поэтому будем считать Bmin≤B≤Bmax (величины Bmin и Вmax заданы), значение А известно и находится в пределах 0<A<∞, σ2z] = 1; требуется найти корректирующий коэффициент для точки xi = - (Вmax + Bmin)/2A, полученной на предыдущем шаге (рис. 7.3). Без потери общности можно положить 1 = 1 и рассматривать xi = x1 как исходную точку поиска. В этих условиях Axi + B = B-В̄, где


На рис. 7.4 представлен качественный график зависимости a1opt от В. Вследствие неоднозначности В величина a1opt определяется с точностью до 0≤a1opt≤A-1 × [ 1 + +4/(Вmax-Bmin)2]-1, поэтому рис. 7.4 играет лишь вспомогательную роль (его роль возрастает с уменьшением неопределенности в оценке возможных В).

Рис. 7.3
Рис. 7.3

Рис. 7.4
Рис. 7.4

Обратимся к выражению Ki, которое имеет здесь вид K1 = (ai-1/A)2(В-В̄)221. Нетрудно заметить, при любом постоянном ai значение Ki. растет с увеличением модуля разности В-В̄ тем быстрее, чем больше коэффициент (a1-1/A)2. Это нежелательно из-за опасности получить большие в случае, если величина В окажется близкой к Bmax или Bmin. Наоборот, слабая зависимость Ki от В-В̄ при a1≈1/A является в этом смысле более предпочтительной. Таким образом, в качестве "рабочего" значения a1 выбираем a1 = A-1[1 + 4/(Bmах-Bmin)2]-1, что позволяет совершить переход в точку х2. После того как координата х2 будет вычислена, рассмотренная ситуация повторится снова с той лишь разницей, что при оценке а2 придется учитывать требование сходимости процесса (это находит выражение в неравенстве a2<a1).

Предложенная схема решения не является универсальной; она возникает из конкретных условий задачи и может измениться с получением новой информации.

Процедура Кифера - Вольфовица

Пусть известен класс функций, к которому принадлежит zи = f(х), причем f(x) дифференцируема по крайней мере дважды. Из уравнения df/dx=0 следует х* = ξ(Р), где Р - совокупность параметров, определяющих конкретное значение f(x) при том или ином х (в схеме Роббинса - Монро в роли Р выступали А, В и ξ(Р) = -В/А).

Обозначим через ω разность zи(xi + ci)-zи(xi-ci), входящую в выражение Yi так что х*-Yi = ξ(P)-xi-aiωi/ci. Критерий эффективности остается прежним:


Чтобы найти оптимальные в смысле min Ki последовательности {аi} и {сi}, рассмотрим систему уравнений dKi/ai = 0, dKi/dci = 0, которая в данном случае имеет вид

(7.4)

Складывая строки (7.4), получаем aiωω'/ci-ω'ci(ξ-xi) = 0, откуда следует либо аiω/ci - (ξ-xi) = 0, либо ω'ci = 0. Первое условие не может быть выполнено по

следующей причине: его подстановка в верхнее уравнение (7.4) приводит либо к ξ-хi = 0, либо к σ2 = 0, что противоречит смыслу задачи. Остается исследовать равенство ω'ci = 0. Здесь возникают два предположения: существует единственное значение ci = ciopt, удовлетворяющее рассматриваемому равенству; свойства f(x) таковы, что не позволяют осуществить выбор ciopt с использованием условия ω'ci = 0. В первом случае нетрудно получить решение (7.4), дающее (после проверки достаточных условий существования Ki) искомый результат- ciopt и


Во втором случае приходится выбирать ciopt из каких- то дополнительных соображений, а для оценки aiopt использовать только верхнюю строку (7.4), что, однако, не меняет результата. Таким образом,

(7.5)

Выводы, которые можно здесь сделать, не отличаются в принципе от тех, которые дал анализ формул (7.3):

- знание лишь класса функций zи = f(x) оказывается недостаточным для определения оптимальной последовательности {аi/ci};

- точность получаемых решений тем выше, чем меньше σ2z], и наоборот; в предельных случаях (σ=0 и (σ=∞) соответственно Ki = 0, aiopt=(ξ-xi)cioptω-1 и Ki=(ξ-xi)2,aiopt=0;

- при любой конечной дисперсии 0<σ2z]<∞ ответ на вопрос o величинах (ai/ci)opt, Kmin можно получить лишь на основе дополнительных исследований свойств функции zи = f(x).

Все рассмотренные соотношения, относящиеся к процедурам стохастической аппроксимации, были даны в предположении М [Ri] = 0. Имеет смысл оценить, к чему приведет отказ от этого предположения. Требование сходимости процесса поиска в среднеквадратическом может быть представлено теперь как

(7.6)

Под знаком предела здесь стоит сумма двух существенно положительных величин, что равносильно замене (7.6) условиями


Ясно, что анализ сходимости, проведенный в 7.2, применим и к (7.6) (с заменой Yi-x̂ на Yi-x̂+М), хотя присутствие М[Ri] должно привести к появлению систематической ошибки в оценке х*. Этот нежелательный эффект можно компенсировать внесением соответствующих поправок в гипотезы, касающиеся реальных характеристик zи = f(x).

Методы стохастической аппроксимации, изученные в этой главе, допускают обобщение на задачи со многими переменными, где схемы переходов остаются теми же:


Ниже дан иллюстративный пример.

Пример: найти точку экстремума функции zи = *f(x), если известно, что результаты экспериментов содержат случайные погрешности с характеристиками M[δz] = 0, σ2z] = 0,5 и f(x) = ax2+bx+c, а = 3/4, -10≤b≤5.

Рис. 7.5
Рис. 7.5

Решение: поскольку на х не накладывается ограничений, можно использовать условие df/dx = 2ax+b = 0 для определения х*, z*; это приводит к задаче об отыскании корня функции zи=Ax+B, причем А=1,5 и В∈[-10, 5]. Здесь целесообразно применить процедуру Роббинса - Монро с оценкой точности решений по критерию Ki (см. п. 7.4) .

а) Пусть в качестве исходной взята точка x0 = 0 и z0 = -4 (случайная величина); чтобы найти x1 = x0-a0z0, нужно определить


График зависимости а0 opt от В приведен на рис. 7.5 (вследствие неоднозначности В он играет вспомогательную роль). Обращаясь к выражению K0 = (а0-1/А)2(Ах0+В)220σ2 = (а0-2/3)2В220/4, замечаем, что наименьшее влияние величины В на K0 достигается при а0≈1/А приняв а0 = 0,65, получаем x1 = 2,6.

б) Пусть эксперимент, проведенный в точке x1 = 2,6, дал z1 = 1; следовательно,



ситуаций повторяется: нужно выбирать ах близким к 1/A, сводя к минимуму зависимость K1 от неопределенной величины В, поэтому полагаем a1 = 0,6 (здесь учитывается требование ai+1<ai, см. п. 7.2) и x2 = x1-a1z1 = 2.

в) Пусть эксперимент в х2 для z2 = -0,5, т. е.

a2opt = 2/3[1+1/4(3+B)2],
K2 min = (a2-2/3)2(3+B)2+a22/4,

и a2 принимается равным 0,55; отсюда х3 = х2-a2z2 = 2,28 и т. д.

Продолжение поиска по рассмотренной схеме (zi выбирались с соблюдением условия σ2z] = 0,5) позволяет прийти к выводу, что истинное значение В вряд ли близко к -10 или 5; скорее всего оно находится в пределах -5, -1 (на это указывают выражения ai opt, i = 0, 1, 2), и имеет смысл перейти к новой гипотезе: -5≤B≤3.

г) Пусть в качестве очередного xi оставлено х3 = 2,28 и z3 = - 0,55; следовательно,


(принимается равным 0,5, см, рис. 7.6) и x4 = = 2,55; очевидно, стандартные переходы с уменьшающимися ai opt (i = 4, 5,...) можно продолжать до тех пор, пока не будут проведены все N экспериментов; последнее из имеющихся значений Ki определит конечную ошибку решения (в данном примере после 10 шагов получаем х* = -2,4, Kmin = 0,06).

Рис. 7.6
Рис. 7.6

В заключение заметим, что выбранная последовательность корректирующих коэффициентов ai не является строго оптимальной; величина, на которую уменьшается ai+1 по сравнению с а*, сохранялась постоянной, равной примерно a0/N≡1/(AN). Это правило удобно использовать тогда, когда исходная гипотеза о возможных В остается неизменной; в противном случае более перспективной оказывается "ступенчатая" последовательность {аi}, в которой ai сохраняются постоянными до очередной переоценки гипотезы, после чего назначается новое (уменьшенное) аi и т. д.

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

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"