ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 203
Скачиваний: 1
ПОИСК БЕЗ САМООБУЧЕНИЯ
103
M[AQ]=- — [(si+sa-l) |
( « i + a 2 ) + (s!-s2 ) ( a i - a 2 ) ] , |
|
(1.8.16) |
где |
|
T>+«(^)] =
s'2
S 3
S 4 |
= |
|
|
|
|
|
|
|
|
|
|
|
(1.8.17) |
S i , s 2 |
определяются формулой |
(1.8.8). |
|
|
|||||||||
Далее |
рассмотрим |
случай, |
когда |
отсутствует |
помеха |
||||||||
(о = 0). |
Предположим, |
что направление вектора |
гради |
||||||||||
ента функции Q(X) удовлетворяет условию |
|
||||||||||||
o c i > a 2 > - - - > a n > 0 ; |
|
|
|
|
|
|
(1.8.18) |
||||||
a i > a 2 H |
|
han. |
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
||||
Тогда из формул (1.8.17) |
и (1.8.8) следует: |
|
|||||||||||
s'i = s'2 |
= |
• • • = s'm/2 |
= |
1; |
|
s'm /2+i = |
• • • = |
s ' m = 0 ; |
(1.8.19) |
||||
Si = S 2 = - - |
- = Sn=l: |
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
||||||
Поэтому по формуле |
(1.8.7) получаем: |
|
|||||||||||
qi = q2=--- |
= qm/2=0; |
|
<7m/2 +i=l; |
|
|
(1.8.20) |
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ятп/2+2 |
|
= От = |
0, |
|
|
|
|
|
|
|
|
||
а по формулам |
(1.8.11) |
имеем: |
|
|
|
|
|||||||
|
|
|
1 |
при |
|
т |
|
|
т+1, |
m + n; |
|
||
|
|
— — |
|
i = |
2 |
— + 1 , |
|
||||||
|
|
1 + п |
|
|
|
|
|
|
|
|
(1.8.21) |
||
|
|
|
|
|
|
. „ |
т |
т |
|
||||
|
|
|
О |
при |
|
п |
|
||||||
|
|
|
1=1,2, ... , — , — + 2 , . . . , т . |
|
|||||||||
ГЛАВА I
104
Средний штраф рабочих шагов и среднее изменение функции качества равны
|
|
п |
|
|
P c p . p = 0; |
M[AQ]=-~|— |
У |
a i . |
(1.8.22) |
Сравнение |
формул (1.8.22) |
и |
(1.7.38) |
показывает, что |
при отсутствии помехи алгоритм параллельного гради ента по быстродействию в 2/(1/я+1) раза превосходит алгоритм последовательного градиента.
Таким образом, в пределе при n-voo это отношение стремится к 2.
§1.9. А Л Г О Р И Т М Н А И С К О Р Е Й Ш Е Г О
СП У С К А
Этот алгоритм, так же как и алгоритм па раллельного градиента, представляет собой поиск по вершинам гиперкуба. Метод наискорейшего спуска от личается от метода параллельного градиента тем, что после удачного рабочего шага не происходит перехода к пробным шагам, а продолжается спуск по направле
нию |
удачного |
рабочего |
шага |
до первого неудачного |
|
шага, |
после чего снова |
совершаются пробные шаги [3]. |
|||
Схема метода |
наискорейшего |
спуска |
показана на |
||
рис. |
1.9.1. Аналогично |
методу градиента |
метод наиско |
||
рейшего спуска может быть представлен в виде двух ав
томатов: |
а в т о м |
а т а п р о б н ы х ш а г о в |
Л<П> и |
а в т о |
м а т а р а б о ч и х |
ш а г о в Л( Р>. Автомат |
пробных |
шагов |
|
имеет п+1 |
состояний: п состояний — рабочие шаги, одно |
|||
фиктивное состояние — автомат пробных |
шагов. |
|
||
Пусть входами автомата пробных шагов Л<П ) и авто
мата рабочих |
шагов |
Л<Р> ЯВЛЯЮТСЯ числа с = 0 или с = 1 |
|||
и векторы C j = (с{^\ |
..., |
cn{i)), |
определяемые |
формулами |
|
(1.8.2). Тогда автомат, соответствующий |
алгоритму |
||||
наискорейшего |
спуска, |
представляет собой |
а в т о м а т |
||
с о г р а н и ч е н и я м и |
н а |
в х о д е . Переходы |
из одного |
||
состояния в другое для автомата пробных шагов Л<П ) и автомата рабочих шагов Л ( Р ) показаны на рис. 1.9.2. По этому рисунку получаем следующие переходные мат рицы:
UQ'<0 (c*0)
ГЛАВА I
106
8 |
9 ... Я |
9 9 - |
1 2 |
J |
m m * ] |
Рис. 1.9.2. Графы переходов автомата пробных шагов
(а)и автомата рабочих шагов (б).
1)для автомата пробных шагов
J0 |
1 |
0 |
0 |
• |
• |
0 |
ho |
0 |
1 |
0 |
• |
• |
0 |
i • |
|
|
0 |
• |
• 1 |
|
0 |
0 |
0 |
||||
1 1 |
0 |
0 |
0 |
• |
• |
0 |
111 |
|
|
|
|
|
|
|
|
n + 1 |
|
|
|
|
2) для автомата рабочих шагов
юг |
т+1 |
т+ I — }
ПОИСК БЕЗ САМООБУЧЕНИЯ
107
о•• о о
о•• о о
> m+l
о •• |
0 |
о |
1 |
|
|
о •• |
1 |
о |
01 |
|
|
j |
|
m+l-j |
( / = 1 , 2 , . . . ,2"), |
(1.9.2) |
|
|
|
|
|||
Объединяя матрицы при AQ'<0 автомата пробных шагов А( П > и автомата рабочих шагов А<Р>, имеем пере ходную матрицу
1 |
о о ••• о о - о о |
о о о ••• о |
||||
0 |
1 о ••• о о ••• о о |
о о о ••• о |
||||
0 |
0 |
0 - 0 0 - 1 0 0 0 0 - 0 |
|
|||
0 |
0 |
|
0 - 0 0 - 0 0 1 0 0 - 0 |
(1.9.3) |
||
0 0 |
|
0 - 0 0 - 0 0 0 1 0 - 0 |
|
|||
О О О |
0 о |
0 0 0 0 0 |
1 |
|||
О О О |
1 о 0 0 0 0 0 |
о |
||||
Объединяя |
|
матрицы |
А Г П и |
АЦР, получаем переходную |
||
матрицу автомата при штрафе |
|
|||
0 • • 0 0 • • 1 0 |
0 |
0 • • 0 |
|
|
0 • • 0 0 • • 1 0 0 |
0 • • 0 |
|
||
0 ••• 0 0 ••• 0 1 0 0 ••• 0 |
(1.9.4) |
|||
0 • • 0 0 • • 0 0 |
1 0 • • 0 |
|||
|
||||
|
|
|
! » |
|
0 • • 0 0 • • 0 0 |
0 |
0 • • 1 |
|
|
0 • • 1 0 - 0 0 |
0 |
0 • • 0 |
|
|
ГЛАВА I
108
Функционирование автомата в случайной среде опи сывается цепью Маркова с матрицей переходных вероят ностей
|
|
|
|
|
0 |
|
0 • • |
0 |
S'l |
0 0 • • 0 |
|
|
|
|
0 |
1 - s ' 2 |
o - • |
0 |
S'2 |
0 0 • • 0 |
|
|
|
|
|
0 |
0 |
|
0 ••• 1 s m |
S m 0 0 • • 0 |
||
|
|
|
|
0 |
0 |
|
0 ••• |
0 |
0 |
1 0- •• 0 |
|
|
|
|
0 |
0 |
|
0 ••• |
0 |
0 |
0 0 ••• 1 |
|
|
|
|
<?i |
|
Яг • • |
qm |
0 |
0 0 • • 0 |
|
|
|
|
|
|
|
m |
|
|
n |
|
|
|
|
|
|
|
|
|
|
|
(1.9.5) |
где |
s' j ( / = 1,..., m) — вероятность штрафа /-го рабо |
|||||||||
чего |
шага; |
qj определяется |
формулой |
(1.8.8). Предель |
||||||
ные |
вероятности |
этой |
цепи |
находятся |
как решение сис |
|||||
темы алгебраических |
уравнений |
|
|
|||||||
Pi = (l-s'i)Pi |
|
+ |
qiPm+n |
|
|
|
|
|||
|
|
|
|
|
( t ' = l , .. . , т); |
|
|
|||
|
|
то |
|
|
|
|
|
|
||
P m + 1 = |
^ |
|
S'iPf, |
|
|
|
|
|
(1.9.6) |
|
|
|
i = |
l |
|
|
|
|
|
|
|
Рт+2 — Рт+\! • • • i |
Рт+п = |
Ргп+п— и |
|
|
||||||
Решением этой системы |
является |
|
|
|||||||
|
|
7j{2-V-.+n) |
' п р и / = 1 , . . . , т ; |
|||||||
|
I |
|
|
5=1 |
J |
|
|
|
|
|
|
т |
|
|
|
|
|
|
|
|
|
|
1 ( |
|
|
+п ) |
|
при i=m+ |
1 , . . . , т + п. |
|||
|
|
3=1 |
3 |
|
|
|
|
|
|
|
(1.9.7)
ПОИСК БЕЗ САМООБУЧЕНИЯ
109
Средний штраф рабочих шагов равен
Р с р . р = ^ < ? г (2jh+nYi • |
(1.9.8) |
|
т |
т |
|
2 = 1 |
j=l i |
|
Среднее смещение по направлению градиента опреде ляем по формуле (1.8.11), заменяя в этой формуле qi
т
(i= 1 , . . . , т + п) |
на |
qi/s'iH |
(1+« ) на |
^ |
qi/s'i |
+ |
n: |
||||
|
|
|
|
|
|
|
|
г=1 |
|
|
|
|
х |
Si |
' |
|
|
S i+m/2 |
s |
1 ' |
|
|
|
X ( a 1 + a 2 + - + a n ) + ( - ^ L - - ^ - ) ( a 1 |
+ |
||||||||||
|
|
|
|
|
4 |
S 2+m/2 |
S 2 ' |
|
|
||
. . . |
|
|
ч , / |
|
q3+m/2 |
|
q% \ |
|
|
||
+ a 2 H |
h a n - i - a n ) + \ — |
|
— ) X |
|
|
||||||
|
|
|
|
|
|
x S 3+m/2 |
S 3 |
|
|
||
X ( a i a 2 H |
Ь a n - 2 — a n - i + a „ ) + |
|
|
|
|||||||
. |
/ qt+m/2 |
<74 \ |
, |
. |
, |
, |
|
|
|
|
|
+ |
I — |
|
— I (ai + a2 H |
ha n -2 —an-i — |
|||||||
|
X S 4 + m / 2 |
S 4 ' |
|
|
|
|
|
|
|
|
|
-a„)+- |
+ \—, |
|
- 7 - — |
|
l ( a |
i - a 2 |
- - |
||||
|
|
|
/ |
q-m |
|
qrn/2 |
|
\ |
|
|
|
|
« „ _ , + « „ ) +1 — |
|
— — I X |
|
|
|
|||||
|
|
|
x |
о m |
|
J mi 2 |
|
|
|
|
|
X ( a i — |
a 2 — ••• — ctn-i — a « ) ] |
• |
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
(1.9.9) |
Для двумерного |
случая |
|
(n = 2) |
|
по |
этой |
формуле |
||||
имеем |
|
|
|
|
|
|
|
|
|
|
|