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

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

DJVU-файл Л.А. Растригин - Теория и применение случайного поиска, страница 27 Алгоритмы оптимизации основанные на методе проб и ошибок (2692): Книга - 5 семестрЛ.А. Растригин - Теория и применение случайного поиска: Алгоритмы оптимизации основанные на методе проб и ошибок - DJVU, страница 27 (2692) - СтудИзб2019-05-09СтудИзба

Описание файла

DJVU-файл из архива "Л.А. Растригин - Теория и применение случайного поиска", который расположен в категории "". Всё это находится в предмете "алгоритмы оптимизации основанные на методе проб и ошибок" из 5 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .

Просмотр DJVU-файла онлайн

Распознанный текст из DJVU-файла, 27 - страница

1. Поиск с возвратом: Р(1,0) =Р(0,!) =0,5; Т(з,0) =-Зз — 2; Т(з,!) =За; Т(з) =За — 1; з)1. 2. Поиск с пересчетом: Р(0, 3) =Р(0, 1) = '/сз, Р(0, 4) =Р(0, О) ='/зв' Р(2, 1) =Р(-2, 3) = с/сз' Р(1, 0) =Р(1, 1) =Р(1, 2) =Р( — 1, 4) =Р( — 1, 3) =Р( — 1, 2) =-'/сз, Р(з . 1 3) =Р(-з-1 1) =Р(э+3 1) =Р(-з — 3 3) =('/з)'"з/з' Р(э+2,2) =Р( — з — 2, 2) =ЗР(а+1,4) =- =ЗР( — з — 1, 0) = ('/з)'+з/с, з'= О; Т(з, 1) =За — 2; Т(з, 2) =Т(з, 3) =-- Т(гь 4) ==Зз; Т(з) =За-0,5, з~!. будем характеризовать величиной разности между математическим ожиданием выхода системы и экстремальным значением функции Я(х). Время поиска экстремума будем отождествлять со средним числом тактов, требуемых для того, чтобы из состояния с х=за система впервые попала в экстремальное состояние, т.

е. в состояние с х=О. Введем обозначения: Р(з, /) — вероятность того, что в стационарном режиме система поиска оказалась в состоянии (з, !); Т(з, !) — среднее число тактов, за которые система из состояния (з, !) попадает в состояние (О, /с). Тогда математическое ожнлассссе выхода системы 3. Поиск с линейным пересчетом: Р(1,0) =Р( — 1,4) =0,5; Т(з, 1) =1,5з — 2; Т(з,3) =Т(з,4) =1,5з; Т(з) =1,5з — (в/в), з~1. 4. Поиск «с наказанием случайностью»: Р(з, 1) =Р( — з, 0) = ('/ )»вв; Р(з, 0) =Р( — з,!) = ('/в)ы» з~1.

Р(0, 0) =Р(0, 1) = /в, Т(з, 1) =з; Т(з, 0) =э+2,25; Т(з) =а+1,!25, з)1. 5. Улучшенный поиск «с наказанием случайностью»: Р(1, 0) =Р( — 1,4) =Р(1, 1) =Р( — 1, 3) =в/вв, Р ( з + 1, 2) = Р ( — з — 1, 2) = 1 „5 ('/в) "+в' Р(з, 4) =Р( — з, О) = 1,5('/~) +в; Р(в+2,!) =Р( — а — 2,3) =075('/в)вь', Р(з 3) =Р(-з, 1) =45(~/4)8+в а~~О; Т(а+2 !) =з-! (в/з)," Т(а+1,2) =э+('/ ); Т(з,3) =Т(з,4) =з; Т(з) =а+05, з(1. 6. Поиск с запоминанием экстремума: Р(0, 0) =Р(1, 0) =Р(0, 1) =Р( — 1, 1) =0,25; Т(з) =з, з~~!. Схема 1 № а«орит«а ~ ! ! в ~ в ~ 4, в,' в ! Зв — ! ~ Зв — ОД 1,5« — ~ в+ (%) в+0,5 в -'(/! ~ Т(в! Как видно из приведенной схемы, наиболее эффективным способом поиска экстремума среди рассмотренных стохастических алгоритмов является улучшенный поиск «с наказанием случайностью» (№ 5); несколько хуже алгоритм № 4 (поиск «с пака.

заннем случайностью»). Алгоритмы № 1 и 2 отыскивают экстремум в три раза медленнее, а алгоритм № 3 — в полтора раза медленнее. Таким образом, при отсутстшщ помех алгоритмы поиска обладают следующей эффективностью. По времени поиска экстремума: № алгоритма ( ! ~ э ~ а ! а 1 а, а ! 0,5 ~ !О/9 ! 1,0 ! 1,5 ( 13,~12 0,5 ! Точность отслеживания при параболической характеристике: Схема 3 а а ! а ! а 1 ! а № алгОритма Т!ат 0,5 ! 79136 1,0 ! 4,5 47г'36 . 0,5 Среди стохастпческих алгоритмов наиболее высокой точностью отслеживания экстремума обладает поиск с возвратом.

$73. ВЛИЯНИЕ ПОМЕХ НА ЭФФЕКТИВНОСТЬ СТОХАСТИЧЕСКИХ АЛГОРИТМОВ ПОИСКА Как уже было выше сказано, общий анализ графа, представленного на рис. 7.1, проведен в (21 Поэтому влияние помех на работу алгоритмов поиска с возвратом, «с наказанием случайностью» и с запоминанием экстремума может быть оценено аналитически. На основании результатов 12] можно получить следующие формулы для вычисления величин Р(з, 1) и Т(з, !), введенных выше: Р(з, 1) =Р(з+1,0) =Р(1, 0) П вЂ” — ' — '-, зр:1; (73.1) р(х,О,О) т.~ р(а,!, 1) ' 181 Для оценки эффективности с точки зрения точности отслежчвания экстремума необходимо задаться видом экстремальной характеристики 1,1(х). В качестве примеров мы рассмотрим две характеристики: модульную (!г(х) = !х) ) и параболическу!о (Я(х) ха).

При этом получатотся следующие результаты. Точность отслеживания экстремума при модульной характеристике: Т(э, 1) =Т(з,1; з — 1, 1) + ~ - — ' -' — -+ +р(Й, 1,О) ,, р(й,1,!) ~'р(й,),О) ~ ' р(й+1+1,О,О) «-Р(» ),-а ~-ар( +'+» ) Здесь з)1; Т(з,о; з — 1,!) =1+2 Х П---- — ' — '- — -: р(з+1,0,0) а-е г-вр(з+ ' 1+р(з,1, О) Т(з,1; з-1, !) =-- --'— '- — + р(5, 1, 1) р(з,!,0) х Пр(э+1+1,0,0) Р(а 1 1)л-а г-вР(э+!+Г' (7.3.2) причем Т(1,1) = Т(1, 1; О, 1). Для четной функции Я(х) справедливы следующие формулы. Р(з, 1) =Р(з+1, 0) =Р( — з, 0) =Р( — з — 1, 1), з- 1; (7.3.3) Р(1, О) =Р(0, 1) =Р( — 1, — 1) =Р(0, 0) = <,,4(, ~ ~ри,о.о>) !аг В дальнейшем мы будем предполагать, что (7.3.3) всегда имеет место. Используя формулы (7.1.12), (7.1.!8), (7.1,22), (7.3.1) — (7.3.3), можно оценить эффективность алгоритмов поиска, характеризующихся величинами у и Т(з) (см.

формулы (7.2.1) н (7.2.2) ). Наиболее простые результаты при этом получаются для модульной экстремальной характеристики Я(х) = )х), поскольку в этом случае вероятности р(з, 1, й) для з~! не зависят от значения з, так как Я(за) — 9(зч 1)а) =.+а. Обозначим для этого случая р(з,!,1) =-г; р(з,о,о) =)г. Как следует нз (7.1.12), (7.1.!8) и (7.1.22), для любых а<+со О<!<!. При использовании формул (7.3.1) и (7.3.3) Р(э) =Р(з, 0) +Р(з, 1) =Р( — з, 1) +Р( — з, 0) = — Х,'-~„з~!, '~2 и точность отслеживания экстремума у (см. формулу (7.2.1) имеет простой вид 1+Л а У= 1 — Л 2 (7.3.4) 1 ~1+Л 2з-1/ 1+Л ! Т(э) = — ~ — --+: — ~1+ (! — г) — ~, э)1.

(7.3.5) 2 '11 — Л 1-Л~' В случае гауссовских помех и с дисперсией о' получаем еле. дувшие формулы для вычисления величии г и Л. Поиск с возвратом: г=0,25 1+Ф вЂ”; Лг=0,25 ! — (1)— Поиск «с наказанием случайностью» г=0,25 3+Ф вЂ”; Лг=0,25 3 — Ф— Поиск с запоминанием экстремума: г=0,5 1+Ф вЂ”; Лг=0,5 ! — Ф— Функция Ф(г) определена выше.

Эффективность работы стохастических алгоритмов поиска мы рассмотрим на примере двух случаев: модульной характеристики (Я(х) = !х)) и параболической характеристики Я(х) =- =к'). Алгоритмы № 1, 4, 6 исследовались аналитически с помощью формул (7.3.1) — (7.3.5), а алгоритмы № 2, 3, 5 были исследованы с помощью стохастпческого моделирования па ЭЦВМ. Результаты исследований представлены на рис.

7.11-- 7.14. На этих рисунках изображены кривые, характеризующие зависимость точности отслеживания экстремума у и времени поиска экстремума Т от величины стандартного отклонения помех о. Графики начерчены в логарпфмпческом масштабе Применение формул (7.2.2) и (7.3.2) позволяет вычислить время поиска экстремума: 1й У8' Щ' /Ф су ~. ~Р вг ~к о ~" ~.. к.а. - /У ~б -Р~ о ю гк .аг и ак и ~ '" ~ы. т.~~. У )" / и в относительных единицах. Прн исследовании времени поиска считалась, что система поиска начинает свое движение из состояния (5,1).

Представленные данные позволяют сделать следующие выводы, которые имеют место для одномерного случайного поиска: 1. Алгоритмы случайного поиска, наиболее точно отслеживающие экстремум, оказываются наименее эффективными в смысле времени поиска экстремума, н наоборот. Как правило, это характерно и для детерминированных алгоритмов (2]. 2. Наиболее эффективным алгоритмом случайного поиска в смысле точности отслеживания экстремума является поиск с возвратом, затем идут поиск с линейным пересчетом, улучшенный поиск «с наказанием случайностью», поиск с пересчетом и, наконец, поиск «с наказанием случайностью».

3. Наиболее быстродействующим алгоритмом случайногопоиска является поиск «с наказанием случайностью» (кстати, улучшение алгоритма здесь практически не увеличивает эффективность; это имеет место лишь для очень слабых помех), далее идут поиск с линейным пересчетом, поиск с пересчетом и, наконец, поиск с возвратом. 4. Все рассмотренные алгоритмы обладают практически одинаковой помехоустойчивостью (т. е. понижение эффективности алгоритма с увеличением дисперсии помех происходит примерно с одинаковой скоростью) за исключением алгоритма поиска с линейным пересчетом. Помехоустойчивость алгоритма поиска с линейным пересчетом выше, чем у остальных алгорит. мов.

Это объясняется тем, что при поиске этим алгоритмом позволяется делать удвоенные по величине шаги в направлении экстремума. Этой особенности лишены все остальные алгоритмы. В заключение следует заметить, что сделанные выводы надо считать предварительными, так как они характеризуют только одномерный случай. СЛУЧАЙНЫЙ ПОИСК КАК МЕТОД СИНТЕЗА ДИНАМИЧЕСКОГО ОБЪЕКТА 5 вл. метОды ОНРеделения динАмических хАРАктеРистик ОБЪЕКТОВ ~а И()=Х а ((-ВМ о (8.1.1) 18т Важной проблемой, которую необходимо решить на первом этапе автоматизации управления объектом, является определение динамических характеристик (ДХ) объекта.

Эта проблема становится центральной при управлении с приспосабливанием, поскольку оио,предполагает автоматическое быстрое и периодическое изучение динамических свойств управляемого объекта. Методам решения этой проблемы по результатам активных пли пассивных экспериментов на объекте посвящена многочисленная литература, из которой можно отметить, например,[1--8), Определение ДХ объекта с помощью активных экспериментов, предполагающих подачу на вход объекта специального тестового сигнала„часто недопустимо из соображений нормальной эксплуатации объекта.

Поэтому основное внимание в указанных выше источниках уделяется методам постановки и обработки результатов пассивного эксперимента. Наиболее распространен аналитический подход к определению ДХ объекта, основанный на численном решении интегрального уравнения идентификации (уравнение Винера-Хопфа),Для одномерного стационарного линейного динамического объекта это уравнение записывается в виде илп (8.!.2) К,,(т) =3' ($)К.,(т-ИЙ, о где ыД) — искомая импульсная переходная характеристика исследуемого объекта; у(1) — . выходной сигнал объекта; х(1) -- сигнал на входе объекта; К„,,(т) — взаимная корреляционная функция выходного и,входиого сигналов объекта; К,,(т) -" автокорреляционнаи функция входного сигнала объекта. Читателю, желающему ознакомиться с различными методамн решения этих уравнений, можно порекомендовать книгу (8), содержащую исключительно полный библиографический список. Недостаток аналитического подхода к определению ДХ заключается в исключительной трудоемкости решения уравнения Винера-Хопфа с допустимой для практики погрешностью.

Из приведенных в литературе оценок (например, в (6)) следует, что длины реализаций сигналов х(1) и у((), по которым определяется импульсная переходная функция, должны в десятки раз превышать время практического затухания взаимной корреляппонной функции объекта. Это требование часто вступает в противоречие с тем, что многие объекты в течение длительного периода записи сигналов уже не могут рассматриваться как стационарные. Наконец, следует особо отметить, что определение функции ы($) при конечных длинах реализаций х(() н рН) или по выборочным функциям К„„(т) и К, (т) является математически некорректной задачей.

Как показано в работе А. Н. Тихонова 19), небольшое изменение этих исходных данных может вызвать существенное различие получаемых функций ы(К). Уверенность в правильности полученного результата может быть достигнута только с применением предложенного в работе [9) метода регуляризации, как это сделано, например, в работе 110).

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