Главная » Просмотр файлов » Л.А. Растригин - Теория и применение случайного поиска

Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 18

Файл №1121205 Л.А. Растригин - Теория и применение случайного поиска (Л.А. Растригин - Теория и применение случайного поиска) 18 страницаЛ.А. Растригин - Теория и применение случайного поиска (1121205) страница 182019-05-09СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 18)

На основе получаемых в процессе поиска оценок параметров можно управлять длиной рабочего шага поиска с целью более точного нахождения экстремума функции качества и сокращения среднего времени поиска экстремума. Если имеется априорная информация о неизвестном параметре Х, то его оценку целесообразно находить по максимуму апостериорной вероятности, которая определяется в каждом рм состоянии объекта по статистике, собираемой в результате измерений прп т случайных пробах. Прн этом в качестве апрнор- 1!О Результаты эксперимента с учетом поправки на смещение дают более приемлемые оценки искомых параметров.

Для сопоставления оценки (4.6.33) с оценкой в линейном поле найден значение соотношения (4.5.33) в случае, если выборка будет использована для линейного поля. Определив математическое ожидание М[г), получим, что ной информации для !'-го состояния объекта можно использовать оценку Хн. „полученную в предыдущем ! — 1-м состоянии. Такой подход к оценке параметров экстремального объекта целесообразен в случае существенной корреляции между соседними состояниями. В [214) показано, что в среднем оценка параметра А по формуле Бейеса сходится к действительному значению оцениваемого параметра. $4.7. стАтистический пОиск с АдлптлциеЙ При экстремальном управлении многомернымп зашумленными объектами и отыскании экстремума функций и-переменных с,наложенными на них случайными возмущениями скорость оптимизации существенно снижается нз-за ошибок в определении вектора градиента н его модуля.

Одним из методов повышения скорости сходимости детерминированных и стохастических методов поиска в задачах с шумами является локальное накопление [2!5 †2], на основе которого удается оценить полезный сигнал -- приращение функции качества — или определить усредненное направление вектора градиента. 11иже предлагается метод оптимизации, в котором используется оценка как направления градиента [МО), так и его модуля, получаемая путем обработки локальной статистики на каждом шаге поиска (4.6.5). Такой алгоритм назовем статистическим поиском с адаптацией.

Рассмотрим подробнее данный алгоритм. Пусть объект описывается одноэкстремальной функцией качества (4.7.1) Я =О(Х,А), где Х= (хь хь...,х„) — и-мерный вектор состояния объекта; Х вЂ” вектор неизвестных параметров объекта, которые должны определятьсн во время поиска. В канале связи на функцию качества накладывается помеха, и в экстремальный регулятор поступает значение функции качества Я'=Я(Х, 1.) +е. (4.7.2) Помеха является стационарным пекоррелированпым случайным процессом с нормальным законом распределения и известными параметрами (О,оз!2).

Рассматриваемый алгоритм поиска состоит в следующем. Из текущего состояния Х! делается щ случайных проб + яЕ! и вычисляются соответствующие приращения функции качества [210! Лд !!!!= д" (Х, +дВл Л) — д*(Х! — дВн л), ! = 1, 2,..., и, (4.7.3) х!„—. х!+лхг+,, д ЛХ, =- — — -' ).„и!, РЧ (4.7.4) (4.7.5) Ъ'! — т-ыер- градиентного где а — масштабный коэффициент рабочего шага; ный вектор, являющийся статистической оценкой направления и, согласно [2!О), у;= Х е!Ла~!(!!.

/-! (4,7.6) Как видно из (4.7.5), длина рабочего шага определяетсялокальиой оценкой модуля градиента функции качества. В данном алгоритме используется оценка, полученная для линейного поля. По своей структуре она проще соответствующей оценки для центрального поля. Выбирая пробный шаг достаточно малым, можно приближенно считать центральное поле линейным в окрестности исследуемой точки и применять алгоритм с линейной оценкой модуля градиента для оптимизации нелинейных функций качества. Данный алгоритм применяется в предположении, что помеха относится к классу нормально распределенных случайных процессов (величин! с нулевым средним значением и известной !!з где л — величина пробного шага в пространстве оптимизируемых параметров; Е;= (с!!!!, с;о!,..., с„!л) — единичный случайный вектор, равномерно распределенный в пространстве оптимизируемых параметров.

При этом Х в (4.7.1) является скаляром. На основе последовательности ЛЯ,"(!), ЛЯ!"!э!,..., ЛЯ,~ыи определяется оценка модуля градиента (4.6.10), являющаяся функцией локальной статистики н числа оптимизируемых параметров. Тогда алгоритм можно представить в виде следующих рекуррептиых выражеш!й: дисперсией. Если дисперсия помехи неизвестна, ее легко оценить на основе многократного замера функции качества в ~'-м и 1+1-м состояниях: л и'=- — ~, (ЛЯ"'Р> — Р4ч )' э=1,2,..., й, (4.7.7) Й-1,=, где й — число замеров функции качества в каждом состоянии; Ло',и1=0 ел(Хгзы) — 1~ в~(Х,); По формуле (4.7.7) оценивается требуемое удвоенное значение дисперсии.

Такую оценку необходимо сделать один раз, при этом й следует выбрать достаточно большим с тем, чтобы получить оценку высокой точности. Рассмотрим два вида статистического поиска. Ранее отмел чалось, что,некоторые оценки Х„<'~ вследствие конечности объема выборки могут оказаться мнимыми. Выборки, приводящие к мнимым оценкам, назовем неудачными.

В алгоритме первого вида неудачная выборка отбрасывается и из того же состояния системы проводится повторная выборка до получения действительной оценки модуля градиента. Алгоритм второго вида характеризуется тем, что при неудачной выборке повторное накопление в данном 1-м состоянии не проводится, а делается рабочий шаг '~/. л ЛХ;+~ — — — а — ' Х„п " Ж! с использованием оценки модуля градиента в предыдущем! — 1-и состоянии.

Данный алгоритм исследован экспериментально путем моделирования поиска на ЭЦВМ БЭСМ-ЗМ. Модель объекта описывается функцией качества 4 Я(х) = ~, аххх'. (4.7.8) Крнгерием останова поиска является первое попадание 8 — м системы в е-окрестность экстремума, равнукз О,!. Исходные данные таковы: а,=аз=аз —— 1; а4 — — О,5; х,0==хза=хзч=х4Р 25; а2=4. База каждого просчета равнялась 500 вариантам. Масштабный коэффициент пробного шага а=1. Будем характеризовать качество метода поиска средним числом экспериментов Л'. Мгу =пи~, (4.7.9) хв ! Ю зо 40 га !!4 где пг — - выбранное число проб (иакоплений) в каждом состоянии системы; и -- среднее число выборок на один цикл поиска, включа~ощее в себя как среднее число удачных,таки среднее количество неудачных выборок.

Ясно, что математическое ожидание числа экспериментов пропорционально времени поиска экстремума. При моделировании рассмотрен вопрос о влиянии масштабного коэффипиента рабочего шага на затрачиваемое число экспернментов )у. Результаты моделнрованин отражены на рнс. 4.9, из которого видно, что существует оптимальное значение а, „ при котором МЛ' минимально. Однако величина а,ч, зависит от положения исходной точки в пространстве параметров. Кривая ! соответствует указанным выше исходным координатам, а кривая 2попэ ! лучена при поиске из начальной точки, расположенной в два раза ближе, чем в случае кривой Таким образом, при настройке экстремальной системы управления с использованием данного алгоритма поиска необходим подбор оптимального масштаба раРас.

4.4 бочего шага. Увеличивая число накоплений т, можно точнее оценить вектор и модуль градиента. Однако прн этом будет возрастать число экспериментов йГ. С другой стороны, при малом числе накоплений и оценки параметра Х будут производиться с боль- ма юа яю яэ~ юла юа а г с а а ююиюютэюммммт шими ошибками, вследствие чего число экспериментов может увеличиться. Поэтому возникает вопрос о выборе оптимального числа накоплений. На рнс. 4.10 представлены в виде кривых результаты моделирования — зависимость среднего числа экспериментов при поиске от числа накоплений. Кривая 1 относится к алгоритму первого вида, а кривая 2 — ко второму. Эксперимент показал, что при обоих видах поиска существует опти- мальное значение числа накоплений, при котором среднее число экспериментов минимально, что подтверждает ранее сделанньш вывод о малости оптимального объема выборки. На этом же рисунке для сравнения приводится кривая д, характеризующая скорость оптимизации методом случайного поиска с пакопле- Н О/ дзд405 ОбдглЗ ЗЭ Щ В Ф 6 К М 6 Рис, 4.1/.

нием, для которого также определен оптимальный масштабный коэффициент рабочего шага (рис. 4.11). Длина пробного шага в сравниваемых алгоритмах выбиралась единичной. Найдено путем моделирования оптимальное число накоплений для случайного поиска. Из кривой 3 (см. рис. 4.!0) видно, что объем экспериментов минимален при числе накоплений т= 1. Сравнивая оптимальное число экспериментов для рассматриваемых алгоритмов, можно отметить, что статистический поиск с адаптацией в среднем имеет большую скорость сходимости.

Известно, что чем меньше отношение «сигнал)помеха», тем медленнее сходится процесс поиска. Зависимость среднего числа экспериментов при поиске от величины дисперсии помехи, полученная для алгоритма первого вида, показана на рис. 4.12. Как следует из графика, при малых помехах средние затраты экспериментов мало отличаются от затрат на незашумленном объекте (ов= 0). Прп дальнейшем увеличении интенсивности помех среднее число экспериментов резко возрастает. Исследуемый алгоритм опробован на функции с оврагом. Анализ проведенного моделирования показал, что система быстро выходит в район оврага и затем начинает длительное время блуждать по оврагу, пока благодаря воздействию помехи не попадает в требуемую окрестность.

Таким образом, ыб данный алгоритм кв овражной ситуации» пракгическп нс работоспособен, как впрочем и другие градиентные методы. На основе проведенного экспериментального изучения свойств статистического поиска с управляемой длиной рабочего шага можно сделать следующие выводы; 1) СущаетауЕт ОнтнМаЛЬНЫй ОбЪЕМ НаКОПЛЕНнй Лцн„, При КО- тором алгоритм имеет в среднем максимальное быстродействие; 2) алгоритм отличается повышенной скоростью сходимостп по сравнению со случайным поиском с накоплением; 3) в данном виде алгоритм практически не работоспособен чв овражной ситуации»; 4) рассмотренный алгоритм целесообразно применять для оптимизации многомерных зашумленных объектов, имеющих унимодальную функцию качества.

ГЛАВА т СОПОСТАВЛЕНИЕ СЛУЧАЙНОГО ПОИСКА И СТОХАСТИЧЕСКОИ АППРОКСИМАЦИИ $ вл. ИОстАНОвкА 3АдАчи В последнее время большой интерес проявляется к методам стохастической аппроксимации, впервые предложенным Г. !роббинсом и С. Монро [1], Д.

Характеристики

Список файлов книги

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6508
Авторов
на СтудИзбе
302
Средний доход
с одного платного файла
Обучение Подробнее