Л.А. Растригин - Теория и применение случайного поиска (1121205), страница 26
Текст из файла (страница 26)
(7.1.12) Здесь р(А) — вероятность события А. Поведение системы описывается графом, представленным на рис, 7.1. В (2) приводится подробный анализ систем, описываемых графом такого типа. 2. Поиск с пересчетом. При поиске с пересчетом идея возврата несколько видоизменяется: после неудачного шага происходит не просто возврат в прежнее состояние, а в состояние, отличающееся от прежнего шагом в выбранном снова случай- ном направлении Щ Иначе говоря, после неудачного шага система повторяет этот же шаг, только в новом случайном направлении.
Алгоритм работы системы определяется следующей рекурреитной зависимостью: хь„=х;+$г ма-Оба з!дп(х~-х; 1)(1+эп(у; — р; ~)) = =х;+ аг. (7.1.13) Здесь 1, если г)0; э!ппг= О, если а=0; — 1, если х(0. В этом случае приращение управления ! может принимать уже не два значения, как в (?.1.1), а пять: 1=-2, — 1, О, 1, 2. Поэтому прн кодировании состояний парами чисел (з, !) удобно вместо !7.1.4) пользоваться соотношениями 1) х; = за; 2) х,— х; ~=2 — 1, (=0,1,2,3,4; 3) х1+~-х;=2 — Ь, Ь=О, 1,2,3,4, (7.1.14) В соответствии с этими соотношениями возможными в системе однотактовымн переходами являются переходы из состояния (з, !) в состояние (9+2 — Ь, Ь). Вероятности таких переходов р(з, 1, Ь) приводятся ниже в табл.
1. Поведение системы в этом случае описывается графом, представленным на рис. 7.3. Структура этого графа значительно более сложная по сравнению со структурой графа, изображенного на рис. 7,1. Оощнй анализ его провести трудно. При отсутствии помех проблема значительно упрощается. Граф, представленный на рис. 7.3, превращается в граф, изображенный на рис. 7.4. Вероятности переходов изменяются в соответствии с правилами предельного перехода при о-~.0. Прн этом оказывается, что если некоторый переход возможен, то ои происходит с вероятностью, равной 0,5. Кроме того, оказывается, что в состояния (0,2), (эР, 0), (-э*, 4), э~)2 система вообще не переходит, Для компактности представления вероятностей перехода из состояния в состояние введем следующие обозначения: а(з, !) =р(п Я(эа)-Я((з — 2+!)а)); р(э, !) =р(п(Я(эа) — Я((з — 2+!)а))=1-а(з, !), где р(Л) означает вероятность события А.
169 Таблица ! Вероятности переполов р(а, 1, Ь) при поиске с «пересчетом» 4 0,5!! О,ба 0,5Р 0,5 3 ! 0,50 ! 0,5а 0„5а 0,5Р 4 ! 0,5Р ! 0,5а ! 0,5)! ~ 0,5а В табл. ! приводятся значения вероятностей переходов 1т(з, 1, Л) системы поиска. В этой таблице для простоты аргументы у функций а(з, 1) и р(з, 1) опущены. В случае отсутствия помех (о=О) использование этих таблиц также возможно, ио прп этом надо иметь в виду следу!ощпе предельные соотношения: для всякого з*)0 )О, если 1«=.2; о ' !! если 1)2; ( 1, если 1~2; о ' !О, если 1=2; ( „1) 11, если 1(2; !пп р(з, 1) = ! — !пп а(з, 1) . о о В случае нормальных помех т) формулы для вычисления а и р имеют следующий вид (о>0): р (з, 1) = 0,5 ! + Ф~ Щ(за) — Я((з — 1+2) п) !'! !7! о 0 ( — ! 05а ! ! — ( 05а 2 1 3 0,5Р ! О,ба Таблнпе 2 Вероптностн перехоаов р(т, й ц прн понспе с лниеанмм «пересчетом» 0 ( ! ! з ) з 05а 1 — ~ 05а 0 05а ~ — ) 05а 0,5а 0,5а 0,5а з 4 0,5а 0,5а 0,5а Вероятности однотактовых переходов р(з, й й) для рассматриваемого случая приведены в табл.
2. В этой таблице применены обозначения предыдущего пункта. Граф поведения !72 где через Ф(г) обозначен интеграл вероятности, взятый в виде «н Ф(г) == ~ е -" сК Ип о 3. Поиск с линейным пересчетом. Отличительная особенность процесса поиска экстремума в этом случае заключается в том, что после неудачного шага система не возвращается в прежнее состояние, а делает удвоенный по величине шаг в прямо противоположном направлении [Ц. Алгоритм управления прн таком поиске имеет следующий вид: х;+1 — — х;+ Обогатил [1- зн(у, — ут 1))— -аз!дп(хт-х~,)[1+зн(у;-у; ~)[.
(?.!.15) Все обозначения в (7.1.15) были введены ранее. При поиске с линейным пересчетом также справедливы заключения, которые привели к формулам (7.1.14). Поэтому возможными переходами являются в этом случае однотактовые переходы из состояния (з„1) в состояние (з+2 — И, Ь), где 1 и 6 определяются формулами (7.1.14). Из (7.1.16) видно, что )хты — х;( =а, и поэтому для обозначения состояния системы мы возвращаемся к соотношениям (7.1.4).
Граф, описывающий поведение этой системы, совпадает с графом, представленным на рнс. 7.!. Вероятносттт переходов р(в, 1, й) могут быть вычислены в ссютветствии с формулой (7.1.16), которая, с учетом (7.1.4), приобретет следующий вид: х +, — — х, +0 5а (1 — 21Д„., — (1 — 21-$т ьт) зй(Я(ва)— — Я((в — ! +2!) а) — т1,], (7.1.17) и мы имеем р (в, О, ! ) = 0,5р (т1, Я (ва) — Я ((в — 1) а) ); р(в, О, О) =0 бр (т1~(~(ва) — Ю ((в — 1) а) )+ +р(ч ~Я(ва) — тт(( -1)а))' р(в, 1, 1) =05р(т1,"=Я(ва) — Я((в+1)а))+ 4-р (т!т "»Я(ва) — Я((в+1) а)); р(в, 1, 0) =О 5р(т1,«-.9(ва) — Я((в+1) а)). (7.1.18) !74 системы представлен на рис. 7.5. Характерной особенностью поиска с линейным пересчетом является то, что при его реализации переходы из состояний (д, !) с 1Ф2 в состояния (в, 2) не происходит (см.
табл. 2). Поэтому состояния (в, 2) являются практически нереализуемыми; онн вообще не изображены на рис. 75. Общий анализ графа, изображенного на рис. 7.5, является также трудным, и мы его не будем проводить аналитическим способом. При отсутствии помех этот граф значительно упрощается (си.
рис. 7.6). Практически нереализуемыми состояниями, кроме указанных выше, становятся еще и состояния (в*, О), ( — в*, 4), в«~2. На рис. 7.6 для обозначения дугграфа приняты такие же правила, что и на рнс, 7.2 (сплошиые дуги соответствуют переходам, совершаемым с вероятностью 1, штриховые — с вероятностью 0,5).
4. Поиск «с наказанием случайностью». Сущность этого метода состоит а том, что при удачном шаге следующий шаг делается в том же направлении; при неудаче следующий шаг делается в случайном направлении из нового состояния 11). Ллгоритм работы системы имеет следующий вид: хьы=х;+0,5(хт — х, ~+л$ы1+ + (-'; — — х +а«т+ ) вй(У вЂ” Ут — )1 (7.! .16) Как уже было сказано, общий анализ поведения систем, описываемых графом, изображенным на рис, 7.1, приводится в !2]. Прп отсутствии помех, в соответствии с формулами (?.1,2), (7.1.4) и (7.1.5), для положительной ветви (з>0) получаем х+, — — х~+05а (! — 2!+ $;+~ — (1 — 2! — $с ы) зд(! — 2!) ) = =х,+а)(1, $;ы). (7.1,19) Из (7.1.19) следует, что )(О, «ы+~) =$;+~ и 1(1, «сы) = — 1, поэтому р(з, О, О) =р(з, О, 1) =0,5; р(з, 1, О) =0; р(з, 1, 1) =1. Аналогичный анализ для отрицательной ветви (з<0) дает р(з, 1, 0) =р(з, 1,!) =05; р(з, О, О) =1; р(з,О, 1) =О, Для состояний (О, !) имеем хны =х„+а(! — 2!).
Таким образом, р(0,0, 1) =р(0, 1,0) =1; р(0, О,О) =р(О, 1,1) =О, В этом случае поведение системы описывается графом, представленным на рис. 7.7. 5, Улучшенный поиск «с наказанием случайностью». В этом случае производится небольшая модификация предыдущего способа: при неудачном шаге следующий шаг делается в случайном направлении не из нового состояния, а с пересчетом к прежнему состоянию [Ц. Алгоритм работы системы прп этом определяется соотношением хыи=х;+О бай+~+($+~ — 2э!дп(х; — х, ~))зп(у; — у;,Ц, (7.1 20) ю зв ! 1 1 ° « ° ! 4 -3/ ю .// Ф! 1г «Ф Рис, 7.7.
Здесь для обозначения состояний вновь приходится прибегать к соотношениям (7.1.14); возможными однотактовыми переходами являются переходы пз состояния (з, !) в состояние (з+2— — й, й). Таблнна 3 Вероптностн переводов р(с, 5 й) прн понсне «с иааааанием случайностьюа (улучшенный вариант) 0 1 ( ( 2 1 з 0 ! — ! «( 055 055 а ~ 0,5(3 0,56 0,5р ! а ) 0,55 2 05р ) а 3 ( 055 0,5Р ~ = ~ 0ДР ( В заключение приведем описание алгоритма неслучайного поиска, известного под названием алгоритма с запоминанием экстремума, подробное исследование которого было проведено в работе [4$.
Сравнительный анализ воздействия помех на работу алгоритмов случайного поиска и алгоритма с запоминанием экстремума дает возможность сделать полезные выводы о характере помехоустойчивости этих алгоритмов. 6. Поиск с запоминанием экстремума. При поиске с запоминанием экстремума после каждого меудачпого шага делается шаг в обратную сторону. При удачном шаге движение произ- м — ьт 177 Вероятности переходов р(з, (, й) из состояния в состояние приведены ъ таол.
3 (обозначения см. в пункте 2). Граф, описывающий поведение системы, приводится на рис. 7.8. Общий его анализ так же„как и графов, данных на рис. 7.3 и 7.6, провести трудно. Можно лишь указать, что этот анализ (по отношению ко всем трем типам) в численном виде может быть проведея методами, описанными в работах (2, 31. При отсутствии помех структура графа упрощается и он имеет вид, изображенный на рис. 7.9.
Как видно из этого рисунка, состояния (О, 2), (зе, 0), ( — 3*, 4), з«~2 являются практически нереализуемыми. Анализ графов, представленных на рисунках 7.2, 7.4, 7.6, 7.7, ?.9, мы проведем в следующем параграфе. водится в прежнем направлении. Алгоритм управления имеет вид х+,=х; — аз)ап(х; — х; 1)зд(у; — у; ~). (7.1.2!) Состояния системы при этом характеризуются парой чисел (з, 1), определяемых (7.!.4). Поведение системы описывается графом, представленным на рис. 7.1 и исследованным в г2, 4). Вероятности переходов системы р(з, )„а) определяются в соответствии с формулой хьы=х; — аз)ап(1-2!) здЯ(за) — Я((а — 1+2!) а) — 71,), нз которой следует, что р(з,О, 1) =р(П;<Я(за) — Я((з — !)а)); р(э, О, 0) =р(Ч,~Я(за) — Я((э — 1)а)); р(а, 1, 1) =-р(тм Я(эа) — Я((э+1)а)); р(з, 1, 0) =р(т1; -С7(за) — Я((э+1)а)).
При отсутствии помех для з>0 р(з,О,!) =р(з,!,1) =1; р(з, О,О) =р(з, 1,0) =О. Для отрицательной ветви (э<0) р(з, О,!) =р(а, 1,!) =0; р(з, О, О) =р(а, 1, 0) =1, причем р(0,0,0) =р(0,1,1) =1; р(0,0,1) =р(0,1,0) =О, Соответствующнй этому случаю граф представлен на рис. 7.!О. М -гр рр гд хр ла УТ И Л Риг.
7!О, $72. ЭФФЕКТИВНОСТЬ ПОИСКА ПРИ ОТСУТСТВИИ ПОМЕХ Эффективность работы системы мы будем рассматривать с двух точек зрения: !) точности нахождения экстремума; 2) времени поиска экстремума, Точность нахождения экстремума !?8 МЯ= 2, 2, Я(за) Р(з, /) и точность отслеживании экстремума у=МЯ вЂ” Я(О) = ~ (Я(за) — Я(О) ) ~ Р(э, !). (?.2.1) Бремя поиска экстремума Т(з) = 2„Т(з', !) /2„1. с (7.2.2) Анализ графов поведения систем, изображенных на рис. 7.2, 7.4, 7.6, 7,7, 7.9, легко провести методами, описанными в (2, 5). Этот анализ дает следующие результаты.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
