ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 216
Скачиваний: 1
ГЛАВА II
180
где ai и аг — направляющие косинусы градиентного век тора; ai 2 + a 2 2 = l - Видно, что при больших ./V MN[AQ] мало зависит от начальных вероятностей р^°К В пре дельном случае (Л7 -^оо) получаем
M[AQ] = hmMK{AQ]=~dai. |
(2.2.22) |
||
|
JV^OO |
Т'2 |
|
Отметим, |
что |
максимальное |
значение M[AQ] принимает |
в случае, |
если |
«i = l , т. е. когда направление градиента |
|
совпадает с координатной осью хх. Минимальное значе
ние M[AQ] принимает при a i - > - L , т. е. когда направлеУ2
ние градиента стремится к направлению АХ*1' или АХ( 2 ) . Тогда
M[AQ]= ~ d. |
|
(2.2.23) |
Следовательно, |
среднее приращение функции |
качества |
в зависимости от различного направления градиента из меняется в пределах
1 |
M[AQ] |
1 |
(2.2.24) |
|
2 |
d |
}'2 |
||
|
Рассмотрим частный случай, когда d=\. Тогда из мат рицы (2.2.14), подставляя d=l, получаем следующую матрицу переходных вероятностей за N шагов для век тора W:
|
|
|
1 0 |
0 0 |
|
|||
i4w (Wj/Wi) |
= |
0 |
1 0 |
0 |
(2.2.25) |
|||
0 |
1 0 |
0 |
||||||
|
|
|
|
|||||
|
|
|
1 0 |
0 0 |
|
|||
Как |
видно |
из матрицы, вероятности перехода вектора |
||||||
W из |
одного |
|
состояния |
|
в другое не зависят от номера |
|||
шага |
N. Состояния |
1 и 2 матрицы (2.2.25) являются по |
||||||
глощающими. |
|
Подставляя в (2.2.15) d=l, |
получаем: |
Н |
(2.2.26) |
р 2 ( Л ' ) = р 2 ( 0 ) + р <0). |
' |
ПОИСК С САМООБУЧЕНИЕМ
181
В этом случае распределение вектора W по сущест венным состояниям 1 и 2 не зависит от номера шага по иска N. Оно зависит лишь от начальных вероятностей Рг( 0 ) . В пределе при JV-voo получаем:
рх |
= |
lim р 1 ( л - ) = р 1 ( 0 ) + р 4 ( 0 ) . |
|
|
|||
|
|
iV-*-oo |
|
|
(2.2.27) |
||
р2 |
= |
Н т р 2 ( л ' > = |
/72 <°>+/7 3 ( 0 ) . |
|
|
||
|
|
JV-*oo |
цепь Маркова является |
неэргодической. |
|||
В этом |
случае |
||||||
Если |
d=l, |
то в соответствии с формулой (2.2.21) |
сред |
||||
нее |
приращение |
функции качества на N-u шаге |
поиска |
||||
не зависит от N и равно |
|
|
|||||
M [ A Q ] = ^ - a 1 + ( p 1 ( ° ) + p 4 ( 0 ) - P 2 ( 0 , - P 3 < 0 ) ) ~ а 2 . |
|
||||||
|
|
|
|
|
|
(2.2.28) |
|
Дальше |
рассмотрим особый случай, когда направление |
||||||
градиента |
оптимизируемой системы совпадает с |
одной |
|||||
из биссектрис, например с биссектрисой |
АХ*1*, т. е. когда |
||||||
ai = a 2 =l/y2 . Тогда по формуле (2.2.9) получаем: |
|
||||||
AQO>=|gradQ|; AQ<2>: = AQ(3) = 0; |
(2.2.29) |
||||||
AQ(4) = |
- | g r a d Q | . |
||||||
|
|
||||||
Используя эти неравенства и формулу самообучения (2.2.4), запишем матрицу переходных вероятностей для вектора памяти W в следующем виде:
|
|
1 |
о |
О |
о |
|
4 ( W / W ; ) |
= |
<7n + <7i4 |
О |
о |
||
<7l2 + </l3 |
О |
?11+<?14 |
о |
|||
|
|
|||||
|
|
|
О |
О |
<?12 + <?13 |
|
|
|
|
|
|
(2.2.30) |
|
Переходы |
из |
одного состояния |
в другое |
показаны на |
||
рис. 2.2.3 в виде |
графа. |
|
|
|
||
Из матрицы (2.2.30), используя формулу |
Перрона, по |
|||||
лучаем матрицу |
переходных |
вероятностей |
за yV шагов |
|||
для вектора |
памяти W: |
|
|
|
||
ГЛАВА II
182
A (W/W*) = |
|
|
|
|
|
|
|
|
||||
|
|
|
|
1 |
|
|
О |
О |
|
О |
|
|
|
l - ( 9 l l + V l 4 ) j V |
(qn + qn)N |
|
О |
|
О |
|
|||||
|
l-(<7n + <7i4)* |
|
О |
(<7п + <714)я |
|
О |
||||||
|
|
О |
|
0 |
|
|
|
|||||
|
1 - ( < 7 I 2 + |
7 1 3 ) W |
|
|
(?12 |
+ |
<71зГ |
|||||
|
|
|
|
|
|
|
|
|
|
|
|
(2.2.31) |
|
|
|
|
|
|
По этой матрице находим распреде |
||||||
|
|
|
|
|
|
ление вектора |
W на JV-M шаге по |
|||||
|
|
|
|
|
|
иска: |
|
|
|
|
|
|
|
|
|
|
|
|
|
Р 1 № = 1 - ( 9 1 1 + 4 1 4 № ° ) - ( < ? П + |
|||||
|
|
|
|
|
|
|
+ < 7 1 4 ) № Р З ( 0 ) - ( < ? . 2 + 9 . З ) Л Г Р 4 ( 0 ) ; |
|||||
Рис. |
2.2.3. Граф |
веро |
|
p 2 { N ) = |
(<7п + < 7 и № 0 ) ; |
|
||||||
ятностей перехода для |
|
|
||||||||||
вектора |
памяти |
(на |
|
Pz{N)-(qn |
+ |
qu)NPsw; |
|
|
||||
правление |
градиента |
|
|
|
||||||||
совпадает |
с |
биссек |
|
|
|
|
|
|
|
|||
трисой |
первого |
квад |
|
Р 4 < * > = ( < 7 . 2 + |
< 7 1 3 Г Р 4 < 0 ) , |
|
|
|||||
ранта) . |
|
|
|
|
|
|
|
|
|
|
(2.2.32) |
|
где |
|
|
|
|
|
|
|
|
|
|
|
|
<7n + |
<7i4= |
Y |
( L + D 2 ) ' |
<7i2 + <7i3= у |
( l - ^ 2 ) - |
|
|
|||||
Рассмотрим |
случай, |
когда |
выполняется |
условие 0 < |
||||||||
<d<l. |
|
Тогда |
при предельном |
переходе N-^oo |
получаем |
|||||||
|
|
JV^OO |
|
0 |
при |
t = 2, |
|
|
|
|
(2.2.33) |
|
|
|
|
|
|
|
|
= 2,3, 4. |
|
|
|
|
|
В этом случае цепь Маркова |
является |
эргодической и в |
||||||||||
пределе |
вектор W с вероятностью 1 принимает |
значение |
||||||||||
W b |
т. е. система обучается идеально. Среднее |
прираще |
||||||||||
ние |
функции |
качества |
на N-м шаге |
поиска |
равно |
|||||||
(2.2.34)
ПОИСК С САМООБУЧЕНИЕМ
183 |
|
|
В пределе при N-^oo |
получим |
|
M[AQ] = lim МK[AQ] |
= d. |
(2.2.35) |
Из формулы (2.2.35) |
видно, что в случае, когда |
oci = l/"|/2,. |
результат почти вдвое превышает приращение функции качества. Отметим, что такой случай маловероятен и поэтому результат (2.2.35) имеет узко локальный ха рактер.
Дальше рассмотрим |
частный случай, когда |
|
d = L |
||||
Тогда из матрицы (2.2.31) получаем следующую |
мат |
||||||
рицу переходных вероятностей за N шагов: |
|
|
|||||
|
1 0 |
0 |
0 |
|
|
||
^ ( W / W i ) = |
0 |
1 0 |
0 |
(2.2.36) |
|||
0 |
0 |
1 0 |
|||||
|
|
|
|||||
|
1 0 |
0 |
0 |
|
|
||
Из этой матрицы видно, что состояния 1, 2, 3 являются поглощающими, а состояние 4 — несущественным. В пре деле при Л/->-оо получаем:
p1 = limpi(J V )=p1 <°)+p4 (0).
JV->oo
p2 = Hm Р2т = Рг{0)\
(2.2.37>
p3 = lim ръ ( J V ) = p 3 ( 0 )
N-*oc
j04 = Hm p 4 ( ] V ) =0.
JV->oo
Таким образом, установлено, что для d=\ цепь Мар кова также является неэргодической.
2. Случай я = 2; 6 = 4 - . Выше рассмотрен простейший
К
случай покоординатного обучения в процессе случайного поиска, когда имеется всего два уровня памяти для каж дой координаты. Обычно количество уровней памяти больше двух. В этом случае вектор может находиться в одном из (2&+1)2 состояний, где k — целое число. Эти состояния пронумерованы и показаны на рис. 2.2.4.