Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 25
Текст из файла (страница 25)
Граница, разделяющая область параметров на зоны предпочтения (уФ1), вычислена, как упоминалось выше, для 1=1. Совершенно очевидно, что ее можно использовать и при АФ!. 0 Рг5 05 ! 2 ~0 у Рис бЗ. Полученные результаты, по-видимому, можно оообщить, чтобы обосновать эффективность метода случайного баланса в прболеме отсеивания экспериментов [Ц.
С другой стороны, как было замечено выше, эти результаты позволяют критически отнестись к теореме Брукса (см. [Ц) о наименьшем числе откликов. Дело в том, что число и+! являлось оптимальным как храйнее наименее возможное значение числа откликов. Теперь же следует принять, что оптимальное число откликов по заданному критерию должно быть 2(т -и+1. Попок такого числа откликов начат Е.
Г. Николаевым [1Ц. Прплох1ение 1 1. Оценка метода крутого восхождения (6.3.3) М(а!) =а,; )!(а,) =пай(до=пи'. уквг а!к! н умаМ Рос 6'.4. На рпс. 6.4 представлена геометрическая интерпретация результата 1-й серии экспериментов по определению дга11 Я(Х). Здесь Н = (й„ ..., П„) — вектор помехи, распределенной нор- А мально: Л7(0, ои); Ь1= — Х еол Лгй Р! Из рис. 6.5 видно„что й+й соз <р соз 01= — — .=..=. Уйк+)77+ 2й 0 соз гу й= ) акад д(Х) ); и= ) го). (6.3.4) Отсюда соз О=,гк ~соз 0,р()7) р(ч!) 7(117(ко„ (6.3.5) о о где 2йо-1 ехР(-пог2ои') р(й) = 2 — ", Г~ — ') (6.3.6) есть т-распределение, а 161 Используя ортогональное планирование, легко получить пол кс компонентные оценки вектора градиента: ага!) Я(Х) =- (а„..., аА). А а!=а!+ — ~ ен, 1=1... и; 17'=и+1; й!д,, " Таблица 1 1 0,5 ( 0,25 0,936 ! 0.985 0,419 ( 0,459 1,17, 1,070 х ! 10 соз 6 ! О,!47 со.
Е ( 0,036 т , '2Я5 0,496 а,!57 1,58 ! 0,757 0,284 1,33 2 1 0,482 0,739 0,102 0,180 !,18 1,02 0,25 0,978 0.283 0,865 0.5 0,916 0,258 О,89 х ! 1О соз й ' 0,110 соз $ 0,021 т ! 1,32 и =!! 2 1 0,464 0,73 0,081 0,142 0,96 0,87 О,б 0,202 0,75 0,25 0,975 0,222 0,730 !О О. 103 0,017 !Я1 х соз О соз зз т 0,26 0,973 0,189, 0 645 0,5 0,904 0,172 0,66 1 0,723 О,! 21 0,75 2 0,455 0,069 0,825 10 0,102 0,015 0,85 х соз 41 соз 9 т л= 19 2 1 0,453 0,715 0,061 0,107 0,74 0,67 0,25 0,973 0,169 0,580 0,5 О,ООЗ 0,152 0.60 1О 0,101 0,013 0,78 х соз О соз 59 т г( — ") 2 р(~р) = 1 3!и"-за — плотность распределения телесул!'( - -) ного угла в и-мерном пространстве [!О).
Определение интеграла (6.3.5) связано с серьезными трудностями. Выражение его в виде бесконечного ряда получено Бруксом и Микки (см., напр., [Ц). Однако эти формулы не дают удобного аппарата для анализа, Поэтому интеграл (6,3,5) был вычислен методом Монте— Карло на базе днух тысяч экспериментов; соответствующие результаты представлены в табл. 1. 1 ! = —.="-.;=-. (соз 0~ --- -=:- — — — . и+!' (6,3.7) 2.
Оценка случайного поиска Как указано выше, при случайном поиске на 1-м этапе измерений значения функции отклика замеряются в двух точ- ках: в центре эксперимента — ~в точке Хьь и в одной равно- вероятно выбранной Й-й вершине симплекса ортогонального планирования — в точке (Х;э+ дВе) . Фиксируем выбор вершины Вю т. е. фиксируем угол ~ре межу векторами дгаг) Я(Х) и Ва.
Найдем соз ~ре=М(соз ~рм), Следуя (!2), вычисляем ~'-е приращение функции отклика ЛЯ'ы =- яй~п соз гее+ е'; = ЛЯа+ е',; (6.3.8) е,=Л'(О, ) 2, о), Следующий центр эксперимента определяем по формуле Хеььц — — Х;ц+ 1и,а Вм (6.3.9) где 1,а=з! Вп(ЛЯ'сч) Обозначим проекцию продвижения в пространстве параметров в направлении пгаб Я(Х) как Ьхм = ! сча)'и соз гре При отсутствии помехи!м=з!ип (ЛЩ и Ьхм =а(/а( соз фа ), (6.3.10) т.
е. продвижение в направлении пгад Я(Х) происходит все время со скоростью, пропорциональной ~соз чх). При помехе же это продвижение произойдет лишь с вероятностью р[1м= =з(Вп(ЬЩ1 Так как при фиксированном ме случайная вели- Здесь х= — — отношение помехи к сигналу. дй Аппроксимируя результаты этой таблицы, можно получить оценку чина ЛЯ'гя распределена нормально, то из (6.3.8) можно вычис- лить р((м=в)дп(ЛЯх)]=Ф.' — — — — -- - =Ф]а сов грг], (63.11) ~ д)г'~п сов егй 2а где Следовательно, Аха= а)гп] сов гРг]Ф ) а сов сРг ! =.ауп сов гРа. Отсгода совгр=М(совгрг)= / ]совяг]Ф]асовя]р(~р)гйр, где р(гр) определяется, как и в (6,3.6). В силу периодичности и четности подынтегральной функции па 1О, и] сов ф не зависит от ~рх и справедливо соотношение сов ф=2 ~ сов ~рФ(асов ~р) р(гр) йр, о Интегрируя, имеем 1 Г 1 аг 1 3 а4 х)'ггп ! 1! (и+2) 21(а+2) (и+4) Результаты, вычисленные по этой формуле для различных и и х, даны в табл.
1. ГЛАВА Ъп АНАЛИЗ ШАГОВЫХ АЛГОРИТМОВ СЛУЧАЙНОГО ПОИСКА ЭКСТРЕМУМА ПРИ НАЛИЧИИ ПОМЕХ (одномерный случай) В настоящей главе проведено исследование шаговых алгоритмов случайного поиска в присутствии случайных помех на. блюдения (нзмерения, вычисления) функций Я(х).
Исследова. ние проводится для простого случая одномерных функций Я(х). Изложение ведется в терминах автоматических систем поиска. Нетрудяо видеть при этом, что поведение такой системы можно интерпретировать как реализацию вычислительного процесса поиска экстремума. При анализе системы поиска будем предполагать, что искомым экстремумом функции 1,1(х) является ее минимум, В данной главе основное внимание уделяется следующим вопросам: 1) каким образом эффективность работы системы случайного поиска зависит от интенси|вности помех и 2) не являются ли алгоритмы случайного поиска более помехоустойчивыми, чем детермированные алгоритмы Следует особо отметить, что исследования проводятся для случая одномерной системы, когда эффективность случайного поиска заведомо хуже детерминированного 111.
й 7.1. АЛГОРИТМЫ УПРАВЛЕНИЯ И ВЕРОЯТНОСТЬ ОДНОТАХТОВЫХ ПЕРЕХОДОВ 1. Поиск с возвратом. Идея алгоритма состоит в том, что система, продвигаясь за один такт на фиксированный шаг а (в пространстве управлений) в случайно выбранном направлении, возвращается в прежнее состояние, если этот шаг был неудачным (функция Я(х) увеличилась), либо вновь продвига- 165 ется на шаг а в случайном направлении, если предыдущий шаг был удачным (значенне функции Я(х) уменьшилось) [1). Обозначим через у; значения функции Я(х) а люмент, когда управление (значение аргумента функции) равно х;: у,=Я(х;) +еь где е; — случайная помеха.
Относительно е, будем считать, что она имеет нулевое математическое ожидание, дисперсию 0,5о' и симметричное распределение; кроме того, последовательность е, (1= 1, 2, 3,...) будем считать совокупностью независимых случайных величин. Алгоритм управления, таким образом, будет иметь вид х;+~=х;+0,5(у;+~а — х;+х; ~) — 0,5(х; — х; ~+ +з -ыо)зй'(р — й' — ). (71 !) Здесь 1, если грв0; зя х= — 1, если г~0; $; — - случайная величина, принимающая значения +1 и — 1 с вероятностью 0,5 независимо от ! и от того, какие значения принимали величины ~~; з (Й=-1, 2, 3,...). Обозначим $„-~ — в;= =ць Случайная величина Ч, имеет нулевое математнческоеожиданне и дисперсию о'. При отсутствии помех (о=0) алгоритм (7.1.!) можно переписать в следующем виде: хгы=х;+0,5фыа — х;+х; ~) — 0,5(х;-х; ~+ + $ьыа) зй Я(хг) — Я (х;,) ); (7.1.2) при наличии помех при анализе (7.1.!) надо иметь ввиду. что х;+,=х;+0,5(~~+~а — х;+х; ~) — 0,5(х;-х; ~+ +$оча)зй(О(х,) — Я(х;,) -и;).
(7.!.3) Применяя систему обозначения состояний, принятую в [2), можно поведение системы поиска. работающей в соответствии с алгоритмом (7.1.1), описать стохастическим графом, изображенным на рис. 7.1. Напомним, что в [2) под состоянием (з, !) понимается такая ситуация, при которой (7.1.4) 1) х;=за; 2) х; — х; ~=(1- 2!)а, 1=0,1. Переходы нз состояния (з, !) в состояние (д, й) осуществляются с вероятностями р(з, 1, й) «2], причем д — з= 1 — 26, 5=0,1.
166 Таким образом, й=О соответствует переходам из состояния (з, 1) в состояние (э+1, О), а Ь=1 соответствует переходам в состояние (з-!, 1). д/ Р l -11 Дl /1 Я1 Рис, ?л. Найдем вероятности р(з, 1, й) для алгоритма (?.1.1). Заметим, что р(э, 1, 1) =! — р(з, 1, 0). Будем считать, что функция Я(х) имеет единственный экстремум, который достигается в точке х;=О, т, е. э=0.
В этом случае для всех з>0 ад(Я(х;) — Я(х; ~)) =зй(х; — х~ ~), (7.1.5) а для всех э<0 зд(Я(х;) — Я(х; !)) =зд(х; ~ — х;), Из соотношений (7.1.2), (7.1.4) и (7.1.5) следует, что для з>О хг ы =х, +О 5а ($ьы — 1+21 — ($;~~+1 — 21) зй(1 — 21)) = =1(1, $г ы) а. (7.!.6) Из (7.!.4) и (7.!.6) следует, что 1(0, $гы) = — 1, а )(1, йьы) =$;еь Поэтому для а>0 р (з, О, 1) = 1; р (з, О, 0) =О; р(з, 1, 1) =0,5; р (з, 1, О) = 0,5, Аналогичный анализ отрицательной ветви (э<0) дает р(а,0,0) =0,5; р(э,0,1) =0,5; р(э,!,0) =1; р (з„1, ! ) = О. (7.! .8) Нетрудно также показать, что для состояний (0,1) и (0,0) р(0, 1, 0) =р(0, 1, 1) =р(0, О, 0) =р(0, О, 1) =05.
(719) Поэтому поведение системы поиска при отсутствии помех описывается графом, представленным на рис. 7.2. На этом рисунке переходы„изображенные сплошной линией, совершаются с веРис 72, р оятностью 1, а переходы, изображенные штриховымн линиями, — с вероятностью 0,5. В присутствии помех прн измерении функции Я(х) вместо (7.1.6) имеем х;+~ — х;=О 5а (~и ~ — 1+21 — (~т ы+1 — 2!) з|(Я(за)— -9((з — 1+21)а) — т! )1 (7.1.10) Из (7.1.10) следует, что С;э|а, если (т1т)Я(за) — Я((з — 1+21)а)); тты ' (21 — 1)и,если (т1т -(Г(за) — Я((з — 1+21)а)), Поэтому переходные вероятности в этом случае имеют следующий вид: р(з, О, 1) =0,5р (т1т) Я(за) — Я((з — 1) а))+ +р (т1,~Я(за) — Я((з — 1) а)); р(з, О, 0) =О 5р (т1т) Я(за) — Я((з-1)а)); р(а, 1,!) =Обр(т!т)Я(эа) -Я((э+1)а)); р(з, 1, 0) =05р(т1т)Я(за) -Я((э+1)а))+ +р(пт~Я( ) — Я(( +1)а)).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
