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


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

5.3. Активные стратегии поиска. Эффективность устранения исходной неопределенности

Способы организации поиска х*, z*, рассмотренные в § 5.2, предполагали выбор сразу всех N значений х, что можно считать серьезным недостатком. С этой точки зрения всякая стратегия, предусматривающая последовательное (пошаговое) проведение опытов и оценку возникающих ситуаций, представляется более прогрессивной, так как позволяет экономить средства и время, с расходованием которых неизбежно связана постановка эксперимента. Именно это характерно для активных стратегий, изучаемых ниже. Полезно отметить, что они тоже являются ε-минимаксными.

Метод дихотомии

Метод дихотомии (половинного деления)-один из самых простых методов поиска. Его идея и содержание заключаются в следующем: из N экспериментов, находящихся в распоряжении исследователя, выбираются два (х1, х2) и размещаются на исходном единичном отрезке наилучшим (в смысле критерия L2) образом, т. е. симметрично относительно середины отрезка на расстояниях ε/2 от нее (рис. 5.9). В результате сравнения полученных величин z1 и z2 становится возможным указать гарантированный интервал неопределенности L2(1) = (1+ε)/2 (будем считать, что он смещен влево). Получив таким образом L2(1), можно повторить применительно к нему всю описанную процедуру, используя для этого вторую пару (x3, х4); это даст новый интервал неопределенности L2(2) = (L2(1)+ε)/2 = (1+3ε)/4, положение которого связывается с серединой отрезка L2(1). Затем наступает очередь следующей пары (x5, x6), размещаемой у середины L2(2) и позволяющей получить L2(3) = (L2(2) + ε)/2 = (1+7ε)/8. Процесс продолжается до тех пор, пока не будут проведены два последних эксперимента в xN-1 и xN; длина оставшегося интервала неопределенности, характеризующая эффективность метода, есть

(5.6)
Рис. 5.9
Рис. 5.9

Особенностью рассматриваемой схемы является то, что эффективность использования очередной пары экспериментов снижается по сравнению с эффективностью предыдущей пары. Действительно, если к некоторому моменту окажутся "израсходованными" η пар, η<N/2, то величина интервала неопределенности составит


Если мы попытаемся использовать еще одну пару, то получим


тем самым интервал L2(η) уменьшается на величину


Нетрудно видеть, что выигрыш Δ тем меньше, чем больше η (т. е. номер пары); в пределе (при η→∞) этот выигрыш стремится к нулю, хотя теоретически возможность размещения очередных пар сохраняется всегда (практически же не имеет смысла использовать более 7-8 пар).

Представляет интерес сравнительная оценка результатов (5.6) и (5.5). В качестве ее основы можно принять соотношение между числами экспериментов, необходимых для получения одинаковых LN в схемах поиска, изображенных на рис. 5.7, 5.9. Из равенства правых частей формул (5.6) и (5.5) следует


где N0 - новое обозначение числа экспериментов в формуле (5.5). Графики зависимости N0 от N, построенные для разных значений е, приведены на рис. 5.10. Они показывают, что затраты усилий (т. е. величина N0) при использовании пассивной стратегии тем больше, чем меньше ε и больше N; например, При N = 6 и ε = 0,05 величина N0 приблизительно в 2 раза превышает N, а при N = 10 и ε = 0,02 требуется провести порядка 40 "пассивных" экспериментов, что-бы получить тот же результат LN. Полезно заметить, что эффективность метода дихотомии снижается с увеличением ε.

Рис. 5.10
Рис. 5.10

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

Метод чисел Фибоначчи

Реализация этого метода связана с использованием последовательности целых чисел, открытой итальянским математиком Леонардом Пизанским (Фибоначчи) в начале XIII века. Чтобы проследить за ходом развития схемы поиска х*, z*, предположим, что в нашем распоряжении имеется, как обычно, N экспериментов. Оценим ситуацию, которая возникает после того, как в соответствии с некоторой ε-минимаксной стратегией проведен N-1 эксперимент и остается выбрать последнее значение x = xN. К этому моменту гарантированная длина интервала неопределенности становится равной LN-1 а сам интервал содержит точку XN-1 (рис. 5.11), причем среди всех величин zq(q = 1,..., N-1), полученных в предшествующих экспериментах, наибольшей является именно zN-1. Положение xN-1 на отрезке LN-1 зависит от того, какая стратегия была реализована на предыдущих шагах.

Длина конечного интервала неопределенности будет определяться не только выбираемым xN, но и уже имеющимся xN-1. Очевидно, результат поиска окажется наилучшим в смысле (5.2) только тогда, когда xN-1 расположится на расстоянии ε/2 от середины LN-1 (рис. 5.11) (в этом случае достаточно разместить точку xN симметрично xN-1 и найти LN = (LN-1 + ε)/2 независимо от того, в каком отношении находятся zN и zN-1). Таким образом, первым требованием к исследуемой схеме является следующее: после проведения N-1 экспериментов точка xN-1 должна занять на LN-1 положение, указанное на рис. 5.11 (естественно, в ходе экспериментов допускается перенумерация точек).

Рис. 5.11
Рис. 5.11

Рис. 5.12
Рис. 5.12

Рис. 5.13
Рис. 5.13

Пусть теперь стоит задача выбора двух последних значений х (xN-1 и xN) в условиях, когда N-2 эксперимента проведены и найден интервал LN-2, содержащий точку xN-2, в которой получено значение z = zN-2, наилучшее (по смыслу задачи) в рассматриваемой серии опытов (рис. 5.12). Начнем выбирать xN-1 (внутри LN-2); как только xN-1 и соответствующее zN-1 станут известны, можно будет указать новый интервал неопределенности, меньший LN-2. Поскольку заранее нельзя предсказать, будет ли zN-1>zN-2. лучше всего расположить точку xN-1 симметрично xN-2 несмотря на то, что расстояние между xN-1 и xN-2 окажется наверняка больше ε. Предложенный выбор хN-1 дает гарантию того, что длина нового интервала неопределенности не превысит величины LN-1, отмеченной на рис. 5.12, причем LN-1 не может быть уменьшена, если задана точка xN-2 (т. е. LN-1 является минимаксом). Зная теперь xN-1 и помня о требовании, отраженном в рис. 5.11, приходим к выводу: чтобы получить результат LN, необходимо два последних эксперимента провести так, как показано на рис. 5.13, выполнив тем самым условие LN-2 = LN-1 + LN.

Рис. 5.14
Рис. 5.14

Таблица 5.1
Таблица 5.1

Если сделать очередной шаг и поставить задачу: найти xN-2, xN-1, xN при известных LN-3, xN-3, zN-3, то окажется, что рассуждения, приведенные выше, могут быть целиком перенесены и на этот случай. Таким образом, приходим к равенству LN-3 = LN-2 + LN-1 далее схема строится так, как показано на рис. 5.14.

Теперь ясно, что основное соотношение, характеризующее изучаемый метод, имеет вид

(5.7)

Его анализ удобно начать с конкретизации выражений Lq(q = N, N-1, ...), сведя их в табл. 5.1.

Нетрудно заметить, что коэффициенты при LN и ε в формулах таблицы составляют последовательность чисел Фибоначчи, задаваемую равенствами F0 = F1 = 1, Fk = Fk+1+Fk-2, где k - номер числа, принимающий значения 2, 3, ... Используя это обстоятельство, можно дать общую запись выражения Lq приведенную в нижней строке табл. 5.1, откуда следует L1 = FNLN-εFN-2. Но L1 есть исходный единичный интервал неопределенности (L1 = 1), поэтому

LN = (1 + εFN-2)/FN, (5.8)

Соотношение (5.8) позволяет оценить эффективность метода чисел Фибоначчи (прежде всего в сравнении с методом дихотомии). Приравнивая правые части формул (5.8), (5.6) и обозначая N в (5.6) как Nд, получаем

Nд = 2 log2 [(1-e)FN/(1-ε(FN-3-FN-2))]
Рис. 5.15
Рис. 5.15

Кривые Nд = Nд(N), построенные для разных значений ε, показаны на рис. 5.15; легко видеть, что разница в числах N здесь не такая большая, как на рис. 5.10. Например, при N = 5 и ε = 0,05 Nд = 7 (в схеме дихотомии требуется затратить всего на два эксперимента больше, чтобы получить тот же результат поиска). Приблизительно те же соотношения сохраняются и для других значений ε. Это объясняется существованием при каждом ε = const предельного числа N, которое может быть найдено из условия: длина конечного интервала не определенности Ln не должна быть меньше 2ε, следовательно, FN+1≤1/ε (например, для ε = 0,02 F8<1/ε, по F9>1/ε, т. е. искомое Nиред = 7). Таким образом, в диапазоне реальных значений N (от 4-5 до 25-30) отношение (N-Nд)/Nд колеблется в пределах 0,2-0,3. Большая эффективность метода чисел Фибоначчи связана с тем, что сокращение длины очередного интервала Lq требует проведения одного нового эксперимента, тогда как в схеме дихотомии их требовалось два.

В заключение рассмотрим вопрос о выборе точки x1 и связанной с этим возможностью реализации метода. Из предыдущего анализа следует х1 = 1-L2; но L2 = FN-1LN-εFN-3 (см. табл. 5.1) или с учетом (5.8) L2 = FN[FN-1+ε(FN-1FN-2-FNFN-3)]. Отсюда следует, что сделать первый шаг здесь можно лишь тогда, когда назначено число N, т. е. x1 = x1 (N). Это является недостатком, затрудняющим в ряде случаев решение задачи из-за невозможности изменить N после начала экспериментов. Всегда желательно располагать стратегией, не требующей предварительного задания N, но приближающейся по своей эффективности к исследованному методу чисел Фибоначчи.

Метод золотого сечения

Выше было показано, что использование рекуррентного соотношения (5.7) в качестве основы для построения схемы поиска х*, z* оказывается весьма эффективным. Можно ожидать, что ориентация на разные начальные условия позволит найти в рамках этого соотношения разные схемы поиска, каждой из которых присущи свои особенности, но всем им - достаточно высокая эффективность.

Рассмотрим величину τ = Lq-1/Lq и потребуем ее постоянства при разных q одновременно с выполнением условия (5.7). Разделим обе части (5.7) на Lq+1>0, указав тем самым уравнение τ2 = τ+1, которому должно удовлетворять τ (здесь τ2 = Lq-1/Lq+1). Положительный корень этого уравнения есть τ = (1+√5)/2≈1,618; зная его, можно построить последовательность экспериментов, начиная с x1 = 1 - 1/τ = 0,382 (рис. 5.16), и прийти в конце концов к интервалу неопределенности

LN = 1/τN-1. (5.9)
Рис. 5.16
Рис. 5.16

Проводить эксперименты здесь можно до тех пор, пока выполняются совместно условия (5.9), LN-1 = τLN, LN≥0,5 (LN-1 + ε), откуда следует N≤1 + [lg(2-τ) - lgε](lgτ)-1. Например, для ε = 0,02 получаем Nпред = 6.

Сравнение результатов (5.9) и (5.8) можно провести, приняв за основу отношение соответствующих величин LN при одинаковых N (обозначим его как L). Разделив, почленно (5.9) на (5.8), получим L = FN/((1 + εFN-2N-1). Очевидно, наибольшие значения L принимает при ε = 0, причем, начиная с N = 4, оно стабилизируется около 1,17. Таким образом, с точки зрения эффективности метод золотого сечения занимает промежуточное положение между методами дихотомии и чисел Фибоначчи.

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





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


Диски от INNOBI.RU




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