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


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

5.2. Пассивные стратегии поиска. Оценка приближения к оптимуму

Переходя к рассмотрению различных методов поиска х*, z*, необходимо выяснить, каким образом могут быть найдены схемы, позволяющие получать LN в виде (5.2). Это удобно сделать прежде всего применительно к случаю N = 2.

Пусть х1 и х2 - значения х в двух экспериментах, причем 0≤х12≤1. Очевидно, длина l̄N = l̄2 представляет собой в данном случае наибольшее значение двух разностей х20 и x3-x1, где х0 и x3 равны соответственно нулю и единице.

Таким образом,


Исследовать l̄2 как функцию переменных х1, х2 удобнее всего путем построения линий l̄2 = const на плоскости x1, x2; эти линии показаны на рис. 5.5. По условиям выбора оптимальной стратегии нужно среди полученных l̄2 найти min l̄2 = L2.

Рис. 5.5
Рис. 5.5

Таковым является L2 = 0,5 (при x1 = x2 = 0,5). Принять эти x1 и х2 в качестве "рабочих" значений нельзя,поскольку оказалось нарушенным требование x12. Чтобы обойти это затруднение, введем величину ε-минимальное значение разности х2-x1, при котором еще различимы z2 и z1 (своего рода чувствительность метода). Тогда, положив x1 = 0,5-ε/2, x2 = 0,5+ε/2, можно обеспечить и различение z1, z2, х1, х2, и минимизацию l̄2. Следовательно, искомая стратегия и гарантированный результат определяются как

x1 = (1 - ε) /2, x2 = (1 + ε)/2, L2 = (l + ε)/2. (5.3)

Стратегию (5.3) обычно называют ε-минимаксной.

Перейдем теперь к случаю N = 3. Как я прежде, полагаем 0≤x1<x2<x3≤1, x0 = 0, x4 = 1; здесь уже три интервала [х0, х2], [х1, x3], и [х2, х4] подлежат сравнению с целью определения величины l̄3 = max{x2, x3-x1, 1-x2}, являющейся функцией трех переменных. Чтобы дать наглядную картину изменений l̄3, достаточно рассмотреть линии l̄3 = const на плоскости x1, х2 при фиксированных х3. Если x3 = 1, они полностью совпадают с линиями, построенными на рис. 5.5; если же х3<1 (например, х3 = 0,9; 0,7; 0,5), то картина меняется (рис. 5.6), однако ясно, что, во-первых, нельзя ожидать появления x3<0,5 (при x1<x2<x3) и, во-вторых, всегда нужно назначать x2 = 0,5 (это возможно, конечно, при ε<0,25).

Таким образом, для случая N = 3 существует множество минимаксных стратегий:

х2 = 0,5; х3-x1≤0,5; L3 = 0,5; ε<0,25. (5.4)
Рис.  5.6
Рис. 5.6

Сравнивая (5.4) и (5.3), можно видеть, что разность L2-L3 составляет всего 0,5ε, поэтому схема трех экспериментов при малых ε (понятие "малые" уточняется в каждом конкретном случае) не дает практически выигрыша в величине LN.

Естественно возникает вопрос: как построить минимаксную схему поиска х*, z* при произвольном, числе экспериментов N>3? Из предыдущих оценок следует, что, во-первых, N не может превысить величины [1 + 1/ε], если соблюдается ε-ограничение, и, во-вторых, с увеличением N варьирование значений х становится почти невозможным. Вместе с тем формирование ε-минимаксной стратегии облегчается хотя бы в том плане, что становится легче выбрать стратегию на основе "здравого смысла" и показать, что она является минимаксной, чем исследовать условия ее существования. В связи с этим рассмотрим стратегию поиска однородными парами (она применима в случаях, когда N четное).

Схема строится следующим образом (рис. 5.7): N значений х разбиваются на пары (х1, х2), (x3, x4), ... ..., (xN-1, xN) так, что величины разностей xq-xq-1 (q = 2, 3, ..., N) постоянны и равны ε; далее, интервал [0, 1] делится на N j 2+1 равные части (т. е. на отрезки длиной 2/(2+N)), и пары (xq-1, xq) размещаются с условием, чтобы точки деления попали между соответствующими xq-1, xq (при этом требуется сохранить расстояние между xq с четными индексами постоянным и равным 2(1+ε)/(N+2)). Такое размещение точек х1, х2, ...., xN всегда возможно, так как разность


не превышает ε при любых допустимых k (здесь k - номер очередной пары, 1≤k≤N/2).

Рис. 5.7
Рис. 5.7

Стратегия поиска однородными парами является ε- минимаксной, в чем можно убедиться, смещая любую из точек х1, х2,..., xN. Например, если x1 займет положение x̄1 (рис. 5.7), то интервал [х̄1, х3] будет больше, чем [х1, x3], и за счет этого увеличится l̄N, что недопустимо. Точно так же нельзя приблизить х2 к х3 из-за опасности расширения интервала [х0, х2] и т. д. Эффективность рассмотренной схемы оценивается величиной

LN = 2(1+ε)/(N+2). (5.5)

Теперь остается исследовать случай нечетного N. Поступим здесь так: точки с четными номерами расставим через равные промежутки длиной 2/(N+1), а точки с нечетными номерами - между четными точками так, чтобы расстояния x3-x1, x5-x3,....., xN-xN-2 находились в пределах от 2ε до 2/(N+1) (рис. 5.8). Последнее условие означает, во-первых, что LN зависит здесь только от положения точек с номерами 2, 4, ..., N-1 и, во-вторых, что существует множество оптимальных стратегий, отличающихся друг от друга значениями координат нечетных точек. Таким образом, LN = 2/(N +1). В том, что схема рис. 5.8 является ε-минимаксной, можно убедиться, изменив любое х с четным номером (l̄N возрастает).

Рис. 5.8
Рис. 5.8

В заключение заметим, что предложенные стратегии реализуются, если при данном ε число N выбрано должным образом.

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





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


Диски от INNOBI.RU




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