ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 205
Скачиваний: 1
ГЛАВА I
110
|
\ |
S |
~7~) |
(ai + |
aa) |
+ |
\ ~ Г |
~ |
|
( « 1 - 0 2 ) |
|
M[AQ] = 1 |
S ! |
S 3 ' |
|
|
4 |
S 2 |
|
S 4 ' |
|
|
|
|
|
|
|
|
2£« |
|
|
(1.9.10) |
|||
|
|
|
|
|
|
|
|
|
|
|
|
Далее |
рассмотрим |
случай, |
когда |
отсутствует |
помеха |
||||||
( а = 0 ) . |
Тогда имеют место |
формулы |
(1.8.18) |
и |
(1.8.19). |
||||||
Следовательно, матрица переходных вероятностей цепи Маркова (1.9.5) приобретает вид
0 • • 0 0 • • 0 1 0 0 0 • • 0
|
|
0 • • 0 0 • • 0 1 0 0 0 • • 0 |
|
|
|
|
0 • • 1 0 • • 0 0 0 0 0 • • 0 |
|
|
A(S) |
= |
0 • • 0 0 • • 1 0 0 0 0 • • 0 |
|
(1.9.11) |
|
|
|||
|
|
0 • • 0 0 ••• 0 0 1 0 0 • • 0 |
|
|
|
|
0 • • 0 0 • • 0 0 0 1 0 • • 0 |
|
|
|
|
0 • • 0 0 • • 0 0 0 0 0 • • 1 |
|
|
|
|
0 ••• 1 0 • • 0 0 0 0 0 • • 0 |
|
|
|
|
т |
|
|
|
|
2 |
|
|
Из этой матрицы видно, что у цепи |
Маркова |
состояния |
||
от 1 до т / 2 и от т + 1 до т + п — |
невозвратные, а от |
|||
m/2 + l |
до |
m — поглощающие. Поэтому она |
является |
|
неэргодической и ее предельные вероятности зависят от ее начальных вероятностей Pi ( 0 ) , 1 = I,... ,т + п. Вероят ности перехода за ./V шагов и предельные вероятности оп ределяются при помощи УУ-й степени матрицы (1.9.11). Можно показать, что эта степень равна следующим матрицам:
ПОИСК БЕЗ САМООБУЧЕНИЯ
111
1) |
для |
Nsz:n |
|
|
|
|
|
|
0 ••• 0 |
• 00 • • 00 |
• 0 • • 01 |
00 • • 00 |
|
|
|
0 • • 0 * 00 • • 00 ] 0 ' • 01 ' 00 • • 00 |
||||
|
|
0 • • 0 . 10 • • 00 . о • • 00 00 • • 00 |
||||
|
|
|
|
|
|
т |
|
|
|
|
|
|
2 |
|
|
0 • • 0 |
• 00 ••• 01 |
• 0 • • 00 |
00 • • 00 |
|
|
|
0 • • 0 . 00 • • 00 . 0 • • 00 . 10 • • 00 |
||||
|
|
0 • • 0 • 00 • • 00 • 0 • • 00 • 00 • • 01 |
||||
|
|
0 • • 0 |
10 • • 00 0 • • 00 00 • • 00 |
|||
|
|
|
|
|
|
N |
|
|
0 • • 0 |
10 • • 00 0 • • 00 00 • • 00 |
|||
|
|
т |
т |
|
|
n-N |
|
|
Т |
i |
|
|
|
2) |
для |
N>n |
|
|
|
(1.9.12) |
|
|
|
|
|||
|
|
• 100 •••оо |
• |
т |
|
|
|
|
|
|
|
|
|
|
|
|
100 • •00 |
|
Т |
|
|
|
|
]. |
|
||
|
|
0 ' |
100 • •00 |
' |
0 |
|
|
|
|
|
|
m |
|
|
|
• 010 • •01 |
|
2 |
|
|
|
|
•. |
|
|||
|
|
• 100 • •00 |
• |
|
(1.9.13) |
|
|
|
|
|
|||
|
|
0 |
|
|
0 |
|
|
|
' |
100 • •00 |
|
|
|
ГЛАВА I
112-
где нулями обозначены блоки, элементы которых равны нулю.
Предельные вероятности цепи Маркова равны ее пол ным вероятностям на JV-M шаге при N>n:
|
О |
при |
t'= 1, . . . |
т |
|
|
|
|
2 ' |
|
m/2+l |
т+п |
ри |
i= у + 1; |
Pi=PiN(N>n) |
= |
|
||
|
|
|
||
|
j = l |
j=m+l |
т |
|
|
pi (0) |
при |
|
|
|
i = — +2, |
|||
|
о |
при |
t = m + 1, . . . , т + п. |
|
|
|
|
|
(1.9.14) |
Средний штраф рабочих шагов равен
|
III |
(1.9.15) |
Рср. р |
0. |
2=1
Среднее смещение в направлении градиента определя ется по формуле (1.9.9) с использованием вероятностей (1.9.14):
|
|
m/2+l |
т+п |
|
|
|
|
M[AQ]=- |
[( |
£р}М+ |
^ Р ^ ) ( а 1 |
+ |
а2+- |
||
|
|
j = |
l |
j = m+l |
|
|
|
— + ап) |
+p2+mhm(ai |
+ a2+--- |
|
|
|||
••• + an-i-an) |
+рг+т/2{0) |
(ai + a2 H |
\-an-z~ |
||||
— a„ - i + a„) + p4 +m/2( 0 > (oci + a2 H |
|
H an-2 — «n-i — |
|||||
— ccn) 4 |
|
r p m - i ( 0 ) |
( a i - a 2 |
a n - i + a n ) + |
|||
+ |
Pm{0)(ai-a2- |
~an-\ |
— an) |
|
(1.9.16) |
||
Для двумерного случая (л = 2) по формулам (1.9.14) и (1.9.16) получаем:
ПОИСК БЕЗ САМООБУЧЕНИЯ
113 — —
Pi = Р2 = 0; рг=pi<°> +р2<°> + р 3 ( 0 )
р 4 = р 4 ( 0 ) ; Р5 = Ре = 0;
Af[AQ]= - [ W 0 ' + р2<°> + Р з ( 0 ) + р 5 + p 4 ( 0 ) ( a i - a 2 ) ] .
+ р 5 ( 0 ) + Рб( 0 ) ;
(1.9.17)
( 0 ) + р 6 ( 0 > ) (а, + а 2 ) + (1.9.18)
§ 1.10. С О П О С Т А В Л Е Н И Е Н Е П Р Е Р Ы В Н О Г О И А В Т О М А Т Н О Г О
А Л Г О Р И Т М О В С Л У Ч А Й Н О Г О П О И С К А
Непрерывный вариант случайного поиска характеризуется тем, что шаг в n-мерном пространстве параметров определяется как радиус-вектор, конец кото рого равномерно распределен по поверхности «-мерной гиперсферы, а начало лежит в ее центре.
В многоканальных оптимизаторах [11, 43] использу ется дискретный, т. е. автоматный, вариант случайного поиска, при котором конец радиуса-вектора распределя ется равномерно только по вершинам n-мерного гипер
куба, а |
начало вектора по-прежнему лежит в центре |
«-мерной |
гиперсферы, описывающей гиперкуб. |
Рассмотрим, как введение дискретности повлияет на эффективность и статистические свойства поиска [44].
Под эффективностью поиска будем понимать его быстродействие [3], измеряемое средней величиной бла гоприятного приращения функции качества объекта, приходящейся на один шаг поиска. Быстродействие по иска характеризует скорость смещения к экстремуму функции в направлении ее градиента. Быстродействие поиска будем исследовать, используя линейную модель функции качества
Q ( X ) = Q ( 0 ) + [ g r a d Q ( X ) , X ] , |
(1.10.1) |
где X — n-мерный вектор параметров; [gradQ(X),X] —скалярное произведение вектора гра
диента на вектор X.
8 — 2014
ГЛАВА I
114
Интересующее нас приращение функции качества за один шаг легко вычисляется на основании (1.10.1):
AQf = Q(X1 + AXi ) - Q(X<) = [grad Q(X),||ДХ4 1cos
|
|
|
|
|
(1.10.2) |
Здесь |gradQ(X) | и |
|АХ| |
— модули |
gradQ(X) = |
||
= (аи...,ап) |
и вектора |
шага |
A X J ; ф* |
— |
угол между |
направлением градиента и направлением |
шага. |
||||
Из формулы (1.10.2) следует, что эффективность слу чайного поиска определяется «удачностью» выбора на правления случайного шага (при фиксированных |gradQ(X)| и | Д Х , | ) .
Так, при поиске maxQ(X) шаги будут удачными, если coscpi>0. При неудачном шаге происходит автоматичес кий возврат в предыдущую удачную точку и снова опре деляется случайное направление шага. При удачном шаге также делается случайный шаг, что отличает про цедуру нелинейного алгоритма. В линейном алгоритме за неудачным шагом следует повторение шага в том же направлении.
Таким образом, |
эффективность алгоритмов |
обоего |
||||
вида |
существенно |
зависит от |
результативности |
одного |
||
случайного |
шага. Поэтому изучим свойства |
автоматного |
||||
случайного |
поиска на одном случайном шаге. |
|
||||
При |
расчете эффективности |
случайного |
шага, для |
|||
того чтобы получить оценку в сопоставимых единицах, необходимо, как принято выше, полагать, что
| g r a d Q ( X ) | = l ; |
[АХ[ = |
1. |
(1.10.3) |
|
Тогда координаты вектора шага |
A X j = (Ахц,..., Ax,„) |
|||
имеют вид |
|
|
|
|
Ах< t — + |
—=• |
|
|
|
|
( / - I . * |
») . |
|
( u a 4 ) |
Другими |
словами, |
вектор |
АХг- есть |
вершина п-мерного |
гиперкуба и случайный механизм выбора шага заклю чается в выборе любой вершины этого гиперкуба равно вероятно, т. е. с вероятностью 1/2".
Так же без ограничения общности можно положить, что производится поиск maxQ(X) и задача заключается