ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 192
Скачиваний: 1
ГЛАВА 1П
298
•функции качества на одном шаге для такого алгоритма имеет максимальное из возможных значений:
M[bQ]- |
(1-26) (s, - s 2 ) . |
|
|
(3.2.89) |
|
При 6=1/2 по |
формулам |
(3.2.81) |
и (3.2.82) |
имеем |
|
M[AQ] = 0 |
И /7Ср =1/2. Это означает, что в классе |
рассмат |
|||
риваемых |
алгоритмов нет |
алгоритма, |
отслеживающего |
||
поведение такого |
объекта. |
|
|
|
|
Рассмотрим случай, когда матрица объекта (3.2.79) имеет вид
6 1-6
(3.2.90)
6 1-6
т. е. когда объект принимает следующее состояние вполне независимо от предыдущего. В этом случае мат рицы (3.2.20) имеют вид
Т20+Т21 |
|
g21 |
g22 |
|
|
|
/г2 1 |
h22 |
(3.2.91) |
|
: |
gll |
gl2 |
|
|
! |
h n |
h\2 |
|||
|
|
|
|
|
|
|||||
С учетом матриц (3.2.19) и |
(3.2.91) из |
системы |
(3.2.18) |
|||||||
следует: |
|
|
|
|
|
|
|
|
|
|
P i (2) |
= |
1-6 |
• P i ( I ) - Р2(2) = 1-6 |
Р2( |
|
|
(3.2.92) |
|||
Для |
получения |
предельных |
вероятностей |
р ^ 1 ' |
и р 2 ( 1 ) |
|||||
имеем систему уравнений |
|
|
|
|
|
|||||
P l U ) |
= ( g l l + g 2 2 ) P l ( 1 ) + ( U 2 1 + M P 2 ( I ) ; |
|
|
(3.2.93) |
||||||
|
|
|
5_ |
|
|
|
|
|
|
|
PlW+p2 |
(1): |
|
|
|
|
|
|
|
||
2 ' |
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
||
.'Из этой системы |
находим: |
|
|
|
|
|
||||
P i ( i ) = |
_ . . |
|
h2i + |
hl2 |
|
|
|
|
|
|
l~gn-g22 |
+ h2l + |
hl2' |
|
|
|
|
||||
|
|
2 |
|
|
|
(3.2.94) |
||||
Рго)=А. |
|
|
|
|
|
|
|
|||
|
I ~ g l l - g 2 2 |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
||
|
|
2 l-gu-g22 |
+ h2i + hl2 |
|
|
|
|
|||
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
|
299 |
|
|
|
|
где |
|
|
|
|
|
gn=(a10 |
+ an)&; |
g2 2 = (a20 |
+ a2l) |
( 1 - 6 ) ; |
|
hi2={an |
+ al2)d; |
h2X = (a2l |
+ a22) |
(3 2 |
95) |
( 1 - 6 ) ; |
|
||||
aih определяются |
формулами |
(3.2.25). |
|
||
Подставляя выражения (3.2.94) |
в формулы (3.2.21) и |
||||
(3.2.22), находим средний штраф и среднее смещение на
одном |
шаге: |
|
|
|
|
|
|
|
|
|
|
|
|
|
= |
( l - g u - g 2 2 ) s i + (h2X |
+ h22)s2 |
|
|
|
|
||||||
P |
c i > ~ |
l-gn-g22 |
+ h2l + |
hi2 |
|
|
|
|
|
||||
|
|
+ 6 ( g l l + g 2 2 + |
ft21 |
+ |
frl2-l) |
(Sl-S2) |
. |
2 |
g 6 |
||||
|
|
|
l - g l l - g 2 2 + /l2 l+fcl2 |
|
|
|
|
||||||
M[AQ)= (26-1) g " + ^ |
+ |
^ |
i |
+ |
^ 2 |
- |
l |
( 3 |
2 9 7 ) |
||||
|
|
|
1 ~ gl 1 — g22 |
+ |
«21 + |
"12 |
|
|
|||||
Подставляя в эти выражения равенства (3.2.95) и |
учи |
||||||||||||
тывая формулы (3.2.25), имеем: |
|
|
|
|
|
|
|||||||
|
|
P + Y |
|
|
|
|
|
|
|
|
|
|
|
M [ A Q ] = ( 2 6 - l ) 2 ( s , - s 2 ) , |
|
|
|
(3.2.99) |
|||||||||
|
|
|
|
|
P + Y |
|
|
|
|
|
|
||
где |
|
|
|
|
|
|
|
|
|
|
|
|
|
P = Pi + p2; |
Y=Yi + Y2- |
|
|
|
|
|
|
|
|
|
|||
Из |
последней |
формулы |
следует, |
что |
M[AQ] |
принимает |
|||||||
минимальное |
значение, |
равное |
|
— |
(26— 1)2 (sL — s2), |
при |
|||||||
|3 = 0, |
т. е. при |
Ро=1," |
Pi = (32 |
= 0 и уфО |
(у0ф1). |
Следова |
|||||||
тельно, для вполне стохастической модели объекта опти мальным является алгоритм, в соответствии с которым при удачном шаге поиска следует продолжать шаги в том же направлении, а при неудачном — с произвольной вероятностью, отличной от единицы, можно выбрать лю бой шаг.
ГЛАВА III
300
АН А Л И З ПРОЦЕССА О П Т И М И З А Ц И И
ЛИ Н Е Й Н О Й М О Д Е Л И ОБЪЕКТА
Линейную модель объекта можно задать
при помощи следующей матрицы: |
|
||
Д(1) = Д(2) = Д = j |
1 |
0 |
(3.2.100) |
|
1 |
0 |
|
в которой |
|
|
|
6п<-> = 621<-> = 1; |
6 i 2 ^ = 6 2 2 ( i , = 0 |
(3.2.101) |
|
( £ =1,2) .
В этом случае матрица (3.2.10) записывается как
a,ft<» 0
T i h ' ' |
N f l / i |
0 |
а матрица (3.2.9) имеет вид
|
а1 0 <» |
0 |
« „ ( ' ) |
|
|
аюм |
0 |
fl„<2) |
|
|
о2 >( 1 ) |
0 |
Й20 ( 1 ) |
|
А = |
а21<2> 0 |
« 2 0 ( 2 ) |
||
а и ( 1 ) |
0 |
a 2 i ( 1 ) |
||
|
||||
|
а г 2 ( 2 ) |
0 |
а2 1 (2) |
|
0 |
а,2о> |
0 |
GI 2 (2) |
0 |
а2 1 о> |
0 |
a 2 i ( 2 ) |
0 |
« 2 0 ( , ) |
0 |
а 2 о ( 2 ) |
с„(') |
0 |
|
0 |
« 1 1 ( 1 ) |
«i><2> |
0 |
й1 2 (2) |
0 |
а „(2) |
(3.2.102)
0 |
а м (') |
0 |
|
|
0 |
а, ,(2) |
0 |
|
|
0 |
a22<') |
0 |
|
|
0 |
а22<2> 0 |
(3.2.103) |
||
0 |
a 2 i ( 1 ) |
0 |
||
|
||||
0 |
а2 1 (2) 0 |
|
||
0 |
Й10( 1 > |
0 |
|
|
0 |
Ою ( 2 ) |
0 |
|
|
Из матрицы видно, что состояния цепи Маркова, со ответствующие второму состоянию объекта Q ( 2 ) ( X ) , не существенны, а предельные вероятности этих состояний равны нулю:
/>!<2) =р2 <2> = р3<2> = р4 (2)= 0 . |
(3.2.104) |
Следовательно, процесс оптимизации линейной модели описывается цепью Маркова со следующей матрицей пе реходных вероятностей:
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
301-
|
|
Й10 |
a l l |
а12 а11 |
|
|
|
|
||
|
|
а21 |
#20 #21 а22 |
|
|
|
(3.2.105) |
|||
|
|
0.22 #21 а20 #21 |
|
|
|
|
||||
|
|
а\\ |
|
а п |
#и a w |
|
|
|
|
|
Учитывая |
равенства |
(3.2.17), |
имеем Р\ = Р\, |
р 2 = Ръ, где |
||||||
введено |
обозначение |
Рг = Р г ( 1 ) |
(i = 1, - -., 4). Из системы |
|||||||
(3.2.18) |
получаем уравнения |
|
|
|
||||||
Р\= |
(#io + #n)Pi + (а21 + |
а22)р2; |
|
(3.2.106) |
||||||
Рг= (#ii + ai2 )Pi + (#20 + |
|
|
|
|||||||
#2i)/?2, |
|
|
|
|||||||
решая |
|
которые с учетом |
условия |
pi+p2= |
находим: |
|||||
|
_L |
|
|
# 2 1 + #22 |
|
|
|
|
|
|
Pi1 |
У a 2 l |
+ a 2 2 + a l 2 + a n |
|
|
(3.2.107) |
|||||
|
|
|
|
|
|
|
|
|
|
|
Р2-- |
J_ |
|
#i2 + # n |
|
|
|
|
|
||
|
|
2 |
# 2 1 + # 2 2 + # 1 2 + #11 |
|
|
|
||||
Подставляя |
в формулы (3.1.21) |
и (3.1.22) |
найденные |
|||||||
предельные |
вероятности |
р { и р 2 и учитывая |
равенства |
|||||||
(3.2.104) и выражения |
(3.2.25), получаем: |
|
||||||||
Р с р = |
|
P (Sl 2 |
+ S 2 2 ) + 2 y S l S 2 |
, |
|
|
. (3.2.108) |
|||
|
|
|
|
P + Y |
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
M[AQ)= |
- |
(Y-P) ( S |
l - S |
2 ) |
|
|
(3.2.109) |
|||
|
|
|
|
|
P + Y |
|
|
|
|
|
где |
|
|
|
|
|
|
|
|
|
|
P = Pi + P2i |
Y = Yi +Y2- |
|
|
|
(3.2.110) |
|||||
Из формулы (3.2.109) видно, что минимальное значение, равное s2 — su M[AQ] принимает при (3 = 0; Y ^ 0 , Т. е. при
Ро=1; Pi = p2 = 0; уоФ1; Y I + Y 2 = T ^ 0 . Следовательно, при
оптимизации линейной модели объекта оптимальным яв ляется алгоритм модифицированного случайного спуска с произвольными вероятностями выбора направлений по иска при неудачном шаге и с исключением продолжения