ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 200
Скачиваний: 1
|
|
|
ГЛАВА I |
|
|
|
|
|
|
Рассмотрим с л у ч а й б е з |
в о з д е й с т в и я п о м е х и , |
||||||||
т. е. когда |
а = 0 . Тогда |
по формулам |
(1.5.4) имеем: |
||||||
|
Г |
1 при |
i— 1 , . . . , п; |
|
(1.6.30) |
||||
' |
I |
0 |
при |
i = n+1,..., |
|
2п. |
|||
|
|
||||||||
По формулам (1.6.4) |
находим: |
|
|||||||
_ |
Г |
1 |
при |
i = l |
, |
. . . . я; |
|
||
г _ |
I |
0 |
при |
г' = п + 1 , . . . , |
2п; |
(1.6.31) |
|||
|
|
|
|
|
|
|
|
|
|
|
Г 0 |
при |
i = 1 , . . . , /г; |
|
|
||||
й ' ~ |
I |
1 при |
t' = n + |
1 , . . . , |
2п. |
|
|||
Матрица |
(1.6.6) при условии |
(1.3.14) |
имеет вид |
||||||
|
|
|
00 |
1000 |
|
00 |
|
|
|
|
|
|
00 |
0100 |
|
00 |
|
|
|
A(S) |
= |
|
00 |
• 0000 - |
10 |
|
(1.6.32) |
||
|
00 |
• 0010 - |
00 |
|
|||||
|
|
|
|
|
|||||
00 • 0000 ••• 01
10 • 0000 ••• 00
Из |
матрицы |
видно, что состояния от |
2 |
до я этой |
цепи |
Маркова |
являются невозвратными, |
а |
состояние 1 |
исостояния от п+1 до 2п — циклическими с пе
риодом п + 1. |
Следовательно, |
предельные вероятности |
|||
равны |
|
|
|
|
|
Pl~Pn+l= |
••• |
|
1 |
|
|
=Р2п: |
' |
|
|||
|
|
|
П + 1 |
(1.6.33) |
|
Р2 = РЗ= |
••• =Рп = 0. |
|
|||
|
|
||||
Среднее приращение функции |
качества |
||||
M[AQ]=- |
|
1 |
V «г |
|
(1.6.34) |
|
п+ 1 |
г=2 |
|
|
|
ПОИСК БЕЗ САМООБУЧЕНИЯ |
|
|
87 |
|
• |
Д ля двумерного |
случая (п = 2) по |
формулам (1.6.33) |
и (1.6.34) имеем |
|
|
Pi=P3 = P 4 = - j ; |
р2 = 0\ |
(1.6.35) |
M [ A Q ] = - 4 - « 2 . |
|
(1.6.36) |
О |
|
|
§ 1.7. А Л Г О Р И Т М П О С Л Е Д О В А Т Е Л Ь Н О Г О Г Р А Д И Е Н Т А
В данном параграфе рассмотрим одну моди фикацию метода градиента. Эта модификация характе ризуется тем, что после пробного шага gi>0 рабочий шаг, имеющий величину
AXi = — at sign AQig |
(1-7.1) |
(гд-е AQig — приращение функции качества в результате пробного шага gi), делается в t'-м направлении. Такая процедура производится по всем координатам. Строгоговоря, этот метод нельзя назвать градиентным. Это,, скорее, полярный метод. Представим алгоритм как веро ятностный автомат.
1. Одномерный случай |
( п = 1 ) . Состояния |
автомата |
пронумеруем в следующем |
порядке: |
|
AXW = g ; Д Х < 2 ) = - а ; АХ& = + а. |
(1.7.2) |
|
Здесь g — пробный шаг, а ±а — рабочие шаги поиска. Пусть вход автомата, как обычно, определяется величи ной штрафа
f 1, если |
A Q ' ^ O ; |
ч ч |
c = s g n A Q ' = 1 |
л л / ^ - п |
(1-7-3) |
10, если |
AQ < 0 . |
|
Выход автомата совпадает с его состоянием и образует трехбуквенный алфавит (1.7.2).
Далее предположим, что a=g=\. Графы переходов автомата показаны на рис. 1.7.1, а его матрицы перехо дов имеют вид
ГЛАВА I
88
|
|
AG<0 |
Рис. 1.7.1. Графы переходов автомата для |
||
случая |
« = 1. |
|
при нештрафе |
(AQ'<0) |
|
00 1 |
|
|
100 |
(1.7.4) |
|
100 |
|
|
лри штрафе ( A Q ' ^ 0 ) |
||
0 |
1 0 |
|
1 |
0 О |
(1.7.5) |
1 О О |
|
|
Случайная среда задается через вероятности штрафов действия автомата, которые в предположении о линей ности функции качества (grad Q(X) = const) и нормиро
ванное™ его градиента |
= 1 I равны |
|
89 ПОИСК БЕЗ САМООБУЧЕНИЯ
(1.7.6)
Функционирование автомата поиска в случайной среде (1.7.6) описывается цепью Маркова с циклической мат рицей переходных вероятностей
|
! 0 |
Si |
1 — S i |
|
|
|
|
|
|
||
A(S) |
= I |
1 |
О |
О |
|
|
|
|
|
(1.7.7> |
|
|
|
1 0 |
о |
|
|
|
|
|
|
||
Предельные |
вероятности |
для |
этой |
цепи Маркова |
равны |
||||||
|
1 |
|
|
1 |
|
1 |
п |
^ |
|
(1.7.8Х |
|
Pi=~2' |
Pa=YSl> |
Р з = у |
О - |
^ |
- |
||||||
|
|||||||||||
Средний штраф рабочих |
шагов |
|
|
|
|||||||
Pcv.v=slS2=±[l-<&(-±)], |
|
|
|
|
(1.7.9), |
||||||
а среднее смещение по направлению градиента |
|
||||||||||
M [ A Q ] = p 3 - p 2 = - j С1 ~ 2 s i ) = - 4 Ф |
( 27 ) * |
( 1 - 7 Л 0 ) ' |
|||||||||
При а->-0 имеем |
|
|
|
|
|
|
|
||||
Рср.р-^О; |
|
M[AQ]-» |
|
2 ' |
|
|
|
(1J.11)> |
|||
|
|
|
|
|
|
|
|
|
|
||
а при |
а->-оо |
|
|
|
|
|
|
|
|
|
|
Р с р . р ^ - ^ ; |
M[AQ]->0. |
(1.7.12)., |
|
|
|||
2. Двумерный |
случай |
(п = 2). Состояния автомата про |
|
нумеруем в следующем |
порядке: |
|
|
ГЛАВА I
99
AQzO
UQ'<0
Рис. 1.7.2. Графы переходов автомата для случая п=2.
AXW=gei; |
ДХ<2 > = |
- а е , ; |
Д Х ( 3 ) = с е , ; |
|
|
|
(1.7.13) |
Д Х < 4 > = £ е 2 ; |
ДХ<5 > = |
- а е 2 ; |
Д Х ( 6 > = а е 2 . |
Графы переходов автомата показаны на рис. 1.7.2. Имеем следующие матрицы переходов автомата:
при нештрафе (AQ'<0)
0 0 1 О О О
ОО О 1 О о
ОО О 1 О о
А0 = |
|
(1.7.14) |
|
О О О О 0 1 |
|||
|
|||
1 |
О ОО О О |
|
|
1 |
О ОО О О |
|
|
ПОИСК БЕЗ САМООБУЧЕНИЯ
|
91 |
|
|
|
|
при штрафе |
|
(AQ'^O) |
|||
0 |
1 |
0 |
'0 |
0 |
0 |
0 |
0 |
0 |
'1 |
0 |
0 |
0 |
0 |
0 |
' 1 |
0 |
0 |
|
|
|
|
|
(1.7.15> |
0 |
0 |
0 |
'о |
1 0 |
|
1 0 |
0 |
^0 |
0 |
0 |
|
1 |
0 |
0 |
.0 |
0 |
0 |
Функционирование автомата описывается цепью Мар кова
> Si |
1 - 5 ! •о 0 |
0 |
|||
) |
0 |
0 |
• 1 0 |
0 |
|
) |
0 |
0 |
• 1 0 |
0 |
|
|
|
|
|
|
(1.7.16); |
) 0 |
0 |
'0 |
5 4 |
1 — Si |
|
|
0 |
0 |
'о |
0 |
0 |
|
0 |
0 |
^0 |
0 |
0 |
где
s, - s, = y [ l + ® ( - g - ) ] ; |
(1.7.17) |
- • H ' - t e ) ] .
а; — направляющие косинусы вектора-градиента функ ции
Q(X) = a i * i + a2X2; a i 2 + a 2 2 = l . |
(1.7.18) |