Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 27
Текст из файла (страница 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
