ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 179
Скачиваний: 0
ГЛАВА I
58
Решая эту систему уравнений, находим:
|
1 |
l — b2 — a2 |
|
Р1=Р4 |
= — |
\-Ь2~а2 |
+ 2аГ |
|
2 |
||
|
1 |
|
2а: |
Р 2 Р г |
2 ' \-b2-a2 |
+ 2al ' |
|
Подставляя формулы (1.3.24) в выражение учитывая равенства (1.3.33), имеем:
(L3-36>
(1.3.6) и
P l = p 4 = ± S 2 = ± [ l - o ( - L ) ] ;
(1.3.37)
p 2 = P 3 = l S l = l [ l + o ( l b ) ] .
По формуле (1.2.23)
p c p = 2 S l s 2 = - i - y02(^ - ) . |
(1.3.38) |
Из формулы (1.3.38) следует, что автомат, соответствую щий этому алгоритму, обладает целесообразным поведе нием. Среднее приращение показателя качества за один шаг поиска равно
M[AQ] = s 2 - S l = - o ( ^ - ) . |
(1.3.39) |
В пределе при о->0 (а=^=0) получаем:
P l =Pi-^0; |
р 2 = р 3 - ^ - 1 ; р с р - > 0 ; |
M [ A Q ] - ^ - l . |
|
|
(1.3.40) |
При а-^-оо имеем:
(1.3.41)
В случае, когда о = 0, цепь Маркова, описывающая ли нейный алгоритм случайного поиска, является неэргодической, в силу чего этот случай требует отдельного ана лиза.
ПОИСК БЕЗ САМООБУЧЕНИЯ
|
59 |
|
|
|
|
|
|
|
|
Из формул (1.3.25) |
при а = 0 получаем: s i = l; s 2 |
= s 3 = |
|||||||
= 0; s4 = 1. |
|
|
|
|
|
|
|
|
|
Матрица (1.2.23) для д в у м е р н о г о |
с л у ч а я |
б е з |
|||||||
в о з д е й с т в и я |
п о м е х и |
при условии (1.3.14) имеет вид |
|||||||
|
4 |
4 |
4 |
Т |
|
|
|
|
|
A(S) = |
0 |
1 |
0 |
о |
|
|
|
(1.3.42> |
|
0 |
0 |
1 |
о |
|
|
|
|||
|
|
|
|
|
|
||||
|
_1_ _1_ |
|
|
|
|
|
|
||
|
т |
т |
Т |
Т |
|
|
|
|
|
Л^-я степень этой |
матрицы |
|
|
|
|
|
|||
|
|
1 |
2 j Y - l 2 N - l |
1 |
|
|
|||
|
2iv+i |
2n+i |
2N~*1 |
2N+\ |
|
|
|||
|
|
О |
|
1 |
|
О |
О |
(1.3.43), |
|
|
|
О |
|
О |
|
1 |
О |
||
|
|
|
|
|
|
||||
|
|
1 |
2 * - 1 |
2 W - 1 |
1 |
|
|
||
|
2iv+i |
2 l V + 1 |
2 J V + 1 |
2^+' |
|
|
|||
По этой матрице получаем вектор вероятностей на N-щ |
|||||||||
шаге |
|
|
|
|
|
|
|
|
|
|
1 |
|
( P l ( 0 |
) + P 4 ( 0 > ) |
|
при |
i = 1, 4; |
|
|
|
2Л-+1 |
|
|
||||||
|
2 N - l |
|
|
|
|
|
(1.3.44). |
||
|
( P l ( 0 |
) + P 4 ( 0 ) ) |
+ Р г ( 0 ) |
При 1 = 2, 3. |
|
||||
|
2N+l |
|
|
||||||
|
|
|
|
|
|
|
|
|
|
Вектор предельных вероятностей равен |
|
|
|||||||
О |
|
|
|
|
при i= 1, 4; |
(1.3.45) |
|||
|
|
|
|
|
|
|
|
||
р.(о>+ i_ (р 1 (0)+ р4 ( о )) |
П р И |
i = 2,3. |
|
||||||
Средний вектор смещения в пространстве X |
|
||||||||
М [ Д Х ] = ( - 1 , |
- ( Р з ( |
0 ) - р 2 |
( 0 ) ) ) . |
|
(1.3.46) |
||||
ГЛАВА I
60
Д л я среднего приращения функции качества имеем
М[А Q] = - |
а, - |
(р3 |
(0) - р 2 |
(О) y i - а , 2 . |
(1.3.47) |
|
Особо следует рассмотреть случай а\ = а2 |
= ^2\2. Тогда |
|||||
в соответствии |
с определением алгоритма |
(1.2.24) |
||||
|
1 |
1 |
1 |
1 |
|
|
|
4 |
4 |
Т Т |
|
|
|
A(S) = |
0 |
1 |
0 |
0 |
|
(1.3.48) |
|
0 |
0 |
1 |
0 |
|
|
|
0 |
0 |
0 |
1 |
|
|
Вектор предельных вероятностей равен |
|
|||||
0, |
|
|
|
если |
/ = 1 ; |
(1.3.49) |
Рг-- |
|
|
|
|
|
|
+ |
~ P i { 0 |
\ если |
/ = 2,3,4. |
|
||
Р г т |
|
|||||
Дл я среднего приращения показателя качества в этом случае имеем
M [ A Q ] = - (4/>1( 0 ) + Р з ( 0 ) ) у 2 . |
(1.3.50) |
§ 1.4. Н Е Л И Н Е Й Н Ы Й А Л Г О Р И Т М С Л У Ч А Й Н О Г О П О И С К А
Для нелинейного алгоритма характерно то, что после удачного шага (AQ'^O) выбирается новое случайное направление шага, а после неудачного шага (AQ'>0) делается возврат в предыдущее состояние. В этом па раграфе исследуем нелинейный алгоритм случайного поиска, определенный формулой (1.2.3) в § 1.1.
Для этого алгоритма матрицы переходных вероятнос тей имеют вид [43]:
61 |
ПОИСК БЕЗ САМООБУЧЕНИЯ |
|
|
при нештрафе (AQ'^.0) |
|
1 |
1 |
т |
т |
|
(1.4.1) |
1 |
1 |
т |
т |
где т=2п; |
|
при штрафе |
(AQ'>0) |
О
(1.4.2)
о
где нулями обозначены блоки, элементы которых равны нулю, а I — единичная матрица.
Далее будем предполагать, что в процессе поиска ве личины Si (i=l,...,m), определенные по формуле (1.2.17), постоянны (например, функция Q(X) является линейной). Тогда функционирование автомата описыва ется простой однородной цепью Маркова со следующей матрицей переходных вероятностей (см. формулы (1.2.8)):
A(S) = |
|
|
|
|
|
|
|
|
ax |
ax |
|
bi |
ax |
ai |
• Ol |
|
|
a2 |
a2 |
•• a2 |
|
b2 |
a2 |
•• a2 |
m |
|
|
|
|
|
|
|
|
|
~2~ |
dm/2 |
CLml2 |
•• am/2 |
|
flm/2 |
|
•• |
b m l 2 |
|
bmh+\ |
&т/2+1 |
* " Om/2+l |
flm/2+I |
O m /2+l |
flm/2+1 |
••• |
Omh+i |
|
|
|
|
|
am |
CLm |
" |
й щ |
|
m |
m |
(1 |
T |
|
|
где |
|
|
a » = — ( 1 - s O ; |
bt= — (1 — S f ) +su |
(1.4.4) |
m |
m |
|
