ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 198
Скачиваний: 1
ПОИСК БЕЗ САМООБУЧЕНИЯ
|
|
71 |
|
|
|
|
оценка |
алгоритмов |
вычисляется по |
формуле, получен |
|||
ной из выражений |
|
(1.3.50) и (1.4.41), |
|
|||
т]*= |
7(pi<0> + 3p |
8 |
( 0 ) ) |
. |
(1.4.44) |
|
КИ |
Z. |
|
|
|||
|
|
О |
|
|
|
|
При Pi( 0 ) ->0 и р3 ( 0 ) ->-1 отношение (1.4.44) стремится к максимальному значению (г]*-»-7), а при /?i( 0 ) ->0 и р3(°'-»-0 — к минимальному (г)*-Я)).
§ 1.5. А Л Г О Р И Т М Г А У С С А — З Е Й Д Е Л Я И Е Г О С Т О Х А С Т И Ч Е С К И Й В А Р И А Н Т
Сущность алгоритма Гаусса—Зейделя со стоит в следующем [3]. Процесс оптимизации происхо дит последовательно по каждой переменной, т. е. со стоит из последовательных спусков в направлении ко ординатных осей.
В этом параграфе для простоты |
исследуем одну м о- |
|
д и ф и к а ц и ю |
а л г о р и т м а |
Г а у с с а — З е й д е л я . |
Сначала для спуска выбираются подряд все положи тельные направления координатных осей, а потом — все отрицательные. Если по выбранному направлению спуска приращение функции качества отрицательно
(AQ'<0), ТО производится спуск по этому |
направлению |
||
до тех пор, |
пока |
функция качества |
уменьшается |
(AQ'<0) . Если |
A Q ' ^ 0 , то происходит переход к следу |
||
ющему направлению |
спуска. |
|
|
Из сказанного следует, что автомат этого алгоритма поиска имеет 2п состояний, которые пронумеруем в сле дующем порядке:
АХ(» = ае,; ДХ<2) = ае2 ; |
АХ<»> = ае„; |
AX<n +1 ) = - aei ; АХ<2> = - а е 2 ; . .. ; АХ<2"> = - а е „ ,
где а — величина шага; е ь . . . , е „ — координатные орты.
ГЛАВА I
72
Далее будем предполагать, что а=\. Матрицы пере ходных вероятностей автомата в соответствии с алго ритмом поиска равны
при нештрафе (AQ'<0)
|
100 . . . О |
||
А0 = |
010 . . . 0 |
(1.5.2) |
|
|
|
||
|
ООО . . . 1 |
|
|
при штрафе |
( A Q ' ^ 0 ) |
||
|
0100 . |
. |
0 |
|
0010 . |
. |
0 |
А,= |
|
|
(1.5.3) |
|
0000 . |
. |
1 |
|
1000 . |
. |
0 |
Предполагается, что оптимизация идет при наличии помехи, определяемой формулой (0.1.22), и что функция качества Q(X) линейная. Тогда ее приращение kQ'i оп ределяется формулой (1.2.15), а вероятности штрафов (AQ'i^O) — формулой (1.2.17). Следовательно, вероят ности штрафов действий автомата-поиска определяются выражением
y [ l - 0 > ( 2 - ^ - ) ] при |
i = n + l , n |
+ 2, ... ,2n , |
||
|
|
|
|
(1.5.4) |
где Ф(г) |
— функция Лапласа; |
|
|
|
а; |
— направляющие |
косинусы |
вектора |
гради- |
|
|
|
п |
|
|
ента функции качества Q(X); ^ |
ai2= I . |
||
|
|
|
г=1 |
|
ПОИСК БЕЗ САМООБУЧЕНИЯ
73
Функционирование автомата в среде (1.5.4) описывается цепью Маркова со следующей матрицей переходных ве роятностей:
|
l - s i |
si |
0 0 - 0 |
0 |
о |
|
|||
^(S ) |
= |
0 |
l - s 2 |
s2 |
0 ••• 0 |
0 |
о |
(1.5.5) |
|
0 |
0 |
0 |
0 - - 0 |
l - s m _ , |
Sm—1 |
||||
|
|
|
|||||||
|
|
sm |
0 |
0 |
0 ••• 0 |
О |
1 Sm |
|
|
где m=2n. |
|
|
|
|
|
|
|
||
Поскольку |
функция |
качества |
Q(X) линейна, то, при |
||||||
нимая |
офО, |
получаем |
однородную эргодическую цепь |
||||||
Маркова. Следовательно, вектор предельных вероят
ностей |
Р = ( р и . . . , рт) |
пребывания автомата |
в состоя |
ниях i |
(t'= 1,2,..., т) |
находится как решение |
системы |
линейных уравнений |
|
|
|
P=4'(S)P, |
|
.(1.5.6) |
|
гд е Л ' ( 5 ) —транспонированная матрица (1.5.5). Решая эту систему, находим
Р г = |
{— |
( / = 1 , 2 , . . . , т ) . |
(1.5.7) |
Si ZJ —
Средний штраф автомата равен
т
(1.5.8)
а среднее смещение в пространстве параметров {X}
М[АХ]= |
(pi-pn+u |
р2-Рп+2, |
Рп-р2п) |
= |
ГЛАВА I
74
|
Pep |
Pep |
1 |
(1.5.9) |
|
|
* S\ — Sn—i |
Sn — S2n ' tTl |
|||
|
|
||||
Среднее приращение |
функции |
качества |
на одном шаге |
||
|
|
п |
|
|
|
M[AQ]-- |
1 |
V |
/ 1 |
1 |
(1.5.10) |
23=1 |
Г |
|
CCi. |
||
|
|
|
|
||
Подставляя выражения (1.5.4) в формулы (1.5.8) и
(1.5.9), в окончательном виде имеем |
|
|
|
||
Рср = |
2п |
|
|
|
(1.5.11) |
|
•» 1 |
|
|
|
|
|
it |
П |
Ф |
V 2а |
/ |
M[AQ]=- |
2- |
|
|
||
г=1 |
|
7 |
\ ~ a i - |
||
|
i - i 1 |
\ 2а ' |
|
|
|
|
|
|
|
|
(1.5.12) |
Для двумерного случая при большой помехе из фор
мул (1.5.11) |
и (1.5.12) находим |
|
|
|
(1.5.13) |
M[AQ]= |
2Ула |
(1.5.14) |
|
|
|
С л у ч а й |
б е з в о з д е й с т в и я |
п о м е х ( а = 0 ) не |
обходимо рассмотреть особо. В этом случае при выпол нении условия (1.3.14) из формулы (1.5.4) следует:
Si = |
'•Sn—1; |
s n+l— ••" —52n = 0, |
ПОИСК БЕЗ САМООБУЧЕНИЯ
75
и поэтому матрица (1.5.5) принимает вид
|
0100 • • 0000 • • 0 |
|
0010 • • 0000 • • 0 |
|
0000 • • 1000 • • 0 |
|
0000 • • 0100 • • 0 |
A(S) = |
(1.5.15) |
|
0000 • • 0100 • • 0 |
|
0000 • • 0010 • • 0 |
|
0000 • • 0000 • • 1 |
Из этой матрицы видно, что цепь Маркова является неэргодической. Ее состояния от 1 до л являются переход ными, а состояния от п+1 до 2п — поглощающими. Как нетрудно показать, Л^-я степень матрицы (1.5.15) имеет вид
N+1
|
0 |
• |
• 100 • • |
0000 ••• 0 |
|
||
|
0 |
• • 010 |
• • |
0000 ••• 0 |
|
||
|
0 • • 000 • • 1000 ••• 0 |
|
|||||
|
0 • • 000 |
• • 0100 ••• 0 |
|
||||
|
|
|
|
|
|
|
N |
AN(S) = |
0 • • 000 ••• 0100 |
•• • 0 |
(1.5.16) |
||||
|
0 |
• • 000 |
• • |
0100 |
••• 0 |
|
|
|
0 |
• • 000 |
• • 0010 |
••• 0 |
|
||
0 ••• 000 ••• 0000 •• . 1
пп