Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 22
Текст из файла (страница 22)
» Теорема 1 доказана. Теорема 2. При выполнении условий теоремы 1 утверждение последней остается справедливым для алгоритма (5.3.2). Доказательство. Теорему 2 можно доказать аналогично теореме 1, заметив (рис. 5.1), что выход функции Я(Х) за пределы кусочно-линейной аппроксимации может иметь место, когда должна быть заменена функцией распределения от двух независимых случайных величин Х; и соз ~;.
Величина Х; имеет плотность, соответствуюшую н-распределению (5.4.28) р(Х) = — ;---;------- 2« оГ— а угол ~р имеет равномерное распределение ]9] в и-мерном про- странстве В выражении (5.4.28) учтено, что дисперсия случанных величин апь — еаь равна 2о'. Применяя и — 2 раза операцию интегрирования по частям к функции распределения г(х) =/ р(Х)НХ, получим а » « Р(х) = х с„аХ"-ье-*'~ +с„/ е-х'0Х, » з о о где с„ь — - константы. Так как е' *" при Х- «убывает быстрее, чем возрастает любая степень Х, то прп Х со аналогично (5.4.25) получим ««3 А~ — / у р(Х)р(~р) аХа~р — — е 2 оо Дальнейшее доказательство теоремы 2 сводится к повторению доказательства теоремы !.
Замечание. Если помехи е; распределены по закону, отличному от нормального, то в теоремах ! и 2 утверждение «с вероятностью !» следует заменить на р(]х — Мх) !»]: ! — Б(р), (5,4.29) где Ь(р)-+О при й. со. 1ы Применим неравенство Чебышева о2 (! ! (И)) (5.4.30) к центрпрованиой случайной величине а . х — Мх= — гл"теь 2а Из (5.4.12) и (5.4.21) следует, что 11 А,=р а 1 — —,1=. ю' ! )~аг (5.4.31) Таким образом, Р(!х — Мх! ~И])Р!! — 1 '+те: > 2й~ )а1 — —. = )1 — 1 )' га 2де(Н2а ~ — 2и ' 1 где а= — — у>0 2 па~ 2д'Р(2'* 1 — —.~ 11 При конечном о можно выбрать настолько большим ~', что т †.„, <5(р), где б(р) — сколь угодно малое число. Из теорем 1 и 2 можно вывести следствие, Следствие.
При выполнении условий следствия к лемме 1 утверждения с вероятностью 1 в теоремах 1 и 2 можно заменить неравенством (5.4.29). 4 В.В, НАДЕЖНОСТЬ СЛУЧАЙНОГО ПОИСКА В ОБСТАНОВКЕ ПОМЕХ и — и ыз Одной нз важнейших характеристик процесса поиска является его надежность, Под надежностью поиска [11! будем подразумевать вероятность решения задачи оптимизации поисковым методом с точностью, не менее заданной. В качестве поисковых методов, предназначенных для отыскания единственного экстремума (минимума) функции Я(Х), рассмотрим алгоритмы (5.3.2) и (5.3.8).
Вудем рассматривать надежность обоих методов с точки зрения вероятности настройки системы за определенное время (число измерений функции 9(Х)). Из работы (15] следует, что анализ надежности алгоритмов (5.3.2) и (5.3.8) на произвольных объектах затруднителен, поэтому рассмотрим линейное поле, в котором критерий надежности можно значительно упростить, В линейном поле удобно воспользоваться понятием смещения к цели У; «11) за одну итерацию (2п определений Ю).
Из рис. 5.1 следует, что для алгоритма (5.3.2) смещение к цели 04=а4А+а;(Х;(сов срь (5,5.1) а для алгоритма (5.3.8) смещение к цели У;" за 2а определений Я: У";= ~ '1а; "й(тпл)э+а,вааелсоз~р,"), (552) ь ! где 1в — ' в — ° .— 'а — 'в-М„° ' и соз 4р= — -" - — — -; А= ) йга4! Я(Х) ). (Е„афтаб Я(Х)) ! Кгаб Я(Х)! О выборе а - см. з 5.3. Введем коэффициент а„равныи отношению математических ожиданий, взятых из выражений (5.5.2) и (5.5.1). Из $5.3 следует, что а; больше 1, начиная с п)2, и возрастает с увеличением и. Он характеризует среднюю эффективность алгоритма случайного поиска.
Дисперсии выражений (5.5.1) и (5.5.2) — Р(0';) н Р(У";). Р(Г;) =а;~)Х;)соз~рь (5.5.3) 2) У,;("-'е и и 2 — оолГ (5.5.4) 146 Величина !Х;! имеет плотность р(Х;), соответствующую и-распределению: где ос=)'2о, а угол ~р; имеет равномерную плотность распределения в и-мерном пространстве; з!пе-а~р, р(чч) =-,„— — — — — ' — — 1!1) (555) / з!и"-'р;йр; Ъ Учитывая, что М(соыр~) =О, В(сойерс) = —, а также, что ве! и* личины )Х;) и соыр; независимы, получим 0(0';) =пай!!Х;!з0(соз<Р;) =аРоаз, (5.5.6) где СО М) Е;)з= / )2;)зр!Х;)г()Хс) =лиаз — второй центральный момент о величины )Е;). 0(0";) =па;-зйз0(г!Р)+а; аз', (5,5.7) где 3 1 0 ( ~! Р) = Мпи ((4гп ) " =," " 2п(и+2) 4п' ' 3 1 2а(п+2) ' !' 2п Пусть обоими методами совершено по 1-й итерации, т.
е, по 2п!' раз определялась функция Я. Обозначая дисперсии смещения к цели для алгоритмов (1) и (2), через 0'; и 0"; получим: 0з=.~ Х.Л ! 0 . (и г4 ~йз0(,!з)) '~ .г (5.5 8) (5.5,9) м. Учитывая (5.3.3) н а;>1, нетрудно заметить, что ряд ОЭ А «„(па;а М(т!') — а;), составленный из разностей матенатиче. 1 ских ожиданий (5.5.2) и (5.5.!), расходится. Учитывая также, что ряды (5.5.8) и (5.5.9) прп 1 =ао сходятся, найдем такой номер 7, при котором для 1~7 имеет место правило 3-х сигм, т. е, с вероятностью, превышающей '/и случайный поиск окажется эффективней стохастнчсской аппроксимации.
Номер 1 можно найти пз следующего неравенства: „! г А ~„'[лагвМ(т)') -а4)З ~/ ~ [оо'-Ап)) (г)')] ~; а; а'. 1 ! Если допустить, что о(е,) =О, то получим случай, рассмотренный в [!Ц. Рассуждая аналогично [1Ц, получим, что при п~2 вероятность того, что случайный поиск окажется эффективней стохастической аппроксимации по смещению к цели и стремится к 1 по мере возрастания числа итерации и сложности оптимизируемой системы. Некоторые дополнительные результаты содер.
жатся в [1й). ГЛАВА Ю ПРИМЕНЕНИЕ МЕТОДОВ СЛУЧАЙНОГО ПОИСКА В ЗАДАЧАХ ПЛАНИРОВАНИЯ ЭКСПЕРИМЕНТОВ 5 а.1. ОБъект и цели теОРии плАИНРОВАния ЭКСПЕРИМЕНТОВ Формирование теории планирования эксперимента как научной дисциплины стало возможным благодаря взаимосвязанному развитию двух отраслей науки: математической статистики и кибернетики.
Методы факторного анализа,развитыевматематической статистике Р. Фишером, обогащенные положением кибернетики о возможности управления объектом,при неполной информации о его структуре, явились краеугольным камнем теории планирования экспериментов, основы которой изложены в монографии Щ. Ввиду возможности неполной информации о структуре обьекта удобно рассматривать в общем случае объект при помощи модели «черного ящика». изображенной на рис.
6.). Здесь приняты следующие обозначения: Х вЂ” вектор входа объекта; Š— вектор помехи, действующей на объект; Я(Х, Е) — максимпзируемая функция качества объекта, называемая его откликом (в соответствии с терминологией, принятой в теории планирования экстремальных экспери- Е ментов). Важно отметить то обстоятельство, что отклик объекта (в общем случае) неизвестен исследователю; оп может быть только измерен в некоторые моменты времени, 119 Относительно вектора помехи Е предполагается, что исследователь может сформулировать те плн иные гипотезы о параметрах ее распределения и проверить адекватность этих гипотез на опыте. Единственное, что должен знать исследователь до решения задачи, это пространство векторов возможных входных воздействий Х', содержащих подпространство векторов входных воздействий Х, существенно влияющих на отклик объекта. Одной из целей теории планирования экспериментов является решение задачи о выделении подпространства векторов входных воздействий Х, которые существенным образом влииют на отклик объекта.
Это так называемая задача об отсеивания несущественных факторов. В «1) рассмотрены трн метода планирования отсеивающих экспериментов: 1) насыщенные планы; 2) сверхнасыщенные планы (метод случайного баланса); 3) последовательное отсеивание (в частности, метод «латинского квадрата»). Выбор того или иного метода зависит от того объема априорной информации об объекте, который имеет исследователь.
К недостаткам разработки проблемы отсеивающих экспериментов в монографии [1] следует отнести то, что ясно не оговорено, что результаты отсеивающих экспериментов зависят от той области пространства векторов входных воздействий, где проводилось отсеиванне факторов. Дело в том, что при решении задач планирования экспериментов исследователь зачастую уходит достаточно далеко за пределы пространства векторов входных воздействий, где проводится отсеивание несущественных факторов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
