ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 193
Скачиваний: 1
6
Ро
р.
Р2
Yo
Yi
Y 2
M[\Q]
ГЛАВА III
290
j 1
1
1
0
Произволь
ное
Произволь
ное
-1
-1
MB[AQ] -0,33
0,9 |
0,8 |
0,7 |
0,6 |
1 |
1 |
1 |
0,87 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0,13 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
-0,82 |
-0,67 |
-0,54 |
-0,44 |
-0,67 |
-0,43 |
-0,25 |
0,11 |
-0,33 |
-0,33 |
-0,33 |
-0,33 |
П р и м е ч а н и я : 1. sL = 1; s2 =0.
2. Прочерк в графе означает, что при соответст
Д ля случая, когда есть помеха, по формулам |
(3.2.29) и |
|||
(3.2.28) |
находим: |
|
|
|
A M A Q b - |
. j * - " ' ' 1 |
" ? . , , : |
(3.2.76) |
|
|
|
(2 — S i S 2 ) ( 1 - 6 ) + 1 |
|
|
MB[AQ] |
= - |
, f , |
• |
(3.2.77) |
|
|
3[1 — S i s 2 ( l |
—6)] |
|
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
|
291 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Т а б л и ц а 3.2.1 |
||
0,5 |
0,4 |
|
0,3 |
|
0,2 |
0,1 |
0 |
|
|
1 |
|
|
|
|
|
|
|
0,75 |
0,67 |
|
0 |
|
0 |
0 |
0 |
|
0 |
|
|
|
j |
|
|
1 |
|
0 |
| |
0,43 |
0,41 |
0,38 |
0,38 |
|||
|
||||||||
0,25 |
0,33 |
|
0,14 |
|
0,18 |
0,22 |
0,25 |
|
0 |
0 |
|
0 |
|
0 |
0 |
1 или 0 |
|
0 |
0 |
|
0 |
|
0 |
0 |
0 |
|
1 |
I |
|
1 |
|
1 |
1 |
1 или 0 |
|
-0,39 |
-0,36 |
|
-0,37 |
|
-0,41 |
-0,46 |
-0,52 |
|
— |
— |
|
— |
|
|
— |
— |
|
|
|
|
|
|
|
i |
|
|
-0,33 |
-0,33 |
|
-0,33 |
|
-0,33 |
-0,33 |
-0,33 |
|
вующих значениях параметра б алгоритм не работает.
Из формул (3.2.74) и (3.2.75) видно, что алгоритм слу чайного спуска производит оптимизацию только тех объ ектов, для которых 0 , 5 < б ^ 1 , а объекты, которые ха рактеризуются большей величиной случайности, этот алгоритм не оптимизирует.
На рис. 3.2.2 представлено изменение M[AQ] в зави симости от параметра объекта б для построенных опти мальных алгоритмов: график 1 — для алгоритма
19*
|
|
ГЛАВА III |
|
|
292 |
6 |
1 |
|
|
||
|
Ро |
1 |
|
p. |
0 |
|
р2 |
0 |
|
Yo |
\o¥=i |
|
Vi |
Произволь |
|
ное |
|
|
|
Произволь |
|
Y 2 |
ное |
|
MS[AQ] |
-0,20 |
1 |
|
|
1 |
M[AQ] |
-0,6 |
1 |
Mc n [AQ] |
-0,6 |
0,9 |
0,8 |
0,7 |
0,6 |
1 |
1 |
1 |
0,98 |
0 |
0 |
0 |
0 |
о |
0 |
о |
0,02 |
0 |
0 |
о |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
-0,20 |
-0,19 |
-0,19 |
-0,19 |
-0,50 |
-0,450 |
-0,38 |
-0,31 |
-0,41 |
-0,26 |
-0,15 |
-0,07 |
1
TT D и м e ч а н и я: 1. Si=0,8; $2=0,2.
F 2. Прочерк в графе означает, что при соответст
(3.2.65), |
график 2 — для алгоритма (3.2.68), график 3 — |
||
для алгоритма |
(3.2.71), |
график 4 — для алгоритма слу |
|
чайного |
спуска, |
график |
5 — для алгоритма случайного |
поиска с возвратом. Жирной линией показано M[AQ] для интегрального оптимального алгоритма. По этим графи кам видно значительное преимущество оптимального ал горитма перед известными алгоритмами случайного спуска и случайного поиска с возвратом. В таблице 3.2.1
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
|
293- |
|
|
|
|
|
|
|
|
|
Т а б л и ц а 3.2.2 |
||
0,5 |
0,4 |
0,3 |
0,2 |
0,1 |
| |
о |
0,83 |
0,74 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0,47 |
0,45 |
0,43 |
|
0,42 |
0,17 |
0,26 |
0,06 |
0,10 |
0,14 |
|
0,16 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
1 |
1 |
i 1 |
1 |
1 |
|
1 |
|
|
|
||||
-0,18 |
-0,18 |
-0,18 |
-0,17 |
j -0,17 |
|
-0,17 |
-0,27 |
-0,25 |
-0,24 |
-0,25 |
-0,26 |
|
-0,27 |
0 |
|
— |
— |
— |
|
— |
вующи.х значениях параметра б алгоритм |
не работает. |
|
|
|||
приведены |
аналитически подсчитанные значения |
Ро, Рь |
Р2, уо> Yi> |
Y2 Д л я оптимального алгоритма, а |
также |
Mc n {AQ] и |
MB [AQ] для алгоритмов случайного спуска и |
|
случайного |
поиска с возвратом. |
|
Построить оптимальный алгоритм поиска при нали чии помех аналитическим путем, используя выражения
(3.2.29) и (3.2.28), |
весьма затруднительно, поэтому он |
был определен из |
этих выражений на ЭЦВМ методом |
ГЛАВА III
|
294 |
|
|
|
|
|
б |
1 |
| 0,9 |
0,8 |
|
0,7 |
0,6 |
|
|
I |
|
|
|
|
|
1 |
1 |
|
i |
|
1 |
Ро |
1 |
\ 1 |
|
|||
|
|
|
|
1 |
|
|
р. |
0 |
0 |
|
j |
|
0 |
|
|
|
0 |
0 |
0 |
|
Р2 |
0 |
0 |
0 |
0 |
||
|
|
|
|
1 |
|
|
|
|
0 |
|
1 |
|
0 |
Yo |
Yo=l |
0 |
0 |
|
||
|
|
|
|
1 |
|
|
Yi |
Произволь |
0 |
0 |
|
0 |
0 |
ное |
|
|||||
|
|
|
|
|
||
Y 2 |
Произволь |
0 |
1 |
|
1 |
1 |
ное |
|
|||||
|
|
|
|
|
|
|
M[AQ] |
-0,20 |
-0,18 |
-0,16 |
-0,14 |
-0,12 |
|
Mcu[AQ] |
-0,20 |
-0,14 |
-0,09 |
-0,05 |
-0,02 |
|
MB[AQ] |
-0,07 |
-0,07 |
-0,06 |
-0,06 |
-0,06 |
|
Пр и м е ч а н и я : 1. Si=0,6; s2 = 0,4.
2.Прочерк в графе означает, что при соответст
случайного поиска. Результаты расчетов оптимального алгоритма для значений s b равных 0,8; 0,6, и значений б, равных 0,9; 0,8; 0,7; 0,6; 0,5; 0,4; 0,3; 0,2; 0,1; 0, приве дены в таблицах 3.2.2 и 3.2.3. Там же приведены значе ния Af[AQ] для построенного оптимального алгоритма и для сравнения значения /МСЯ[Д(2] и MB [AQ] для алгорит мов случайного спуска и случайного поиска с возвратом. Значения первого столбца (а=1 ) таблиц найдены ана-
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
|
295 |
|
|
|
|
|
|
|
|
Т а б л и ц а 3.2.3 |
|
0,5 |
0,4 |
0,3 |
0,2 |
0,1 |
0 |
0,89 |
0,78 |
0,71 |
0 |
0 |
0 |
|
|
|
|
|
|
0 |
0 |
0 |
0,48 |
0,46 |
0,45 |
0,11 |
0,21 |
0,29 |
0,04 |
0,08 |
0,10 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
-0,10 |
-0,09 |
-0,09 |
-0,09 |
-0,09 |
-0,10 |
0 |
— |
— |
— |
— |
— |
-0,06 |
-0,06 |
-0,06 |
-0,05 |
-0,05 |
-0,05 |
вующих |
значениях параметра б алгоритм не работает. |
|
|||
литическим путем по формулам (3.2.29) и (3.2.28). Из таблиц видно, что при увеличении помех, т. е. при Si-v0,5; s2-M3,5 ( G - V O O ) , уменьшается быстродействие оптималь ного алгоритма. Это свойство также следует из формул (3.2.29) и (3.2.28), из которых получаем
l i m G = l ; |
limM[AQ] = 0. |
(3.2.78) |
< J - > 00 |
0 - > О О |
|
ГЛАВА III
296
А Н А Л И З ПРОЦЕССА О П Т И М И З А Ц И И СТОХАСТИЧЕСКОЙ МОДЕЛИ, НЕ СВЯЗАННОЙ С П О И С К О М
В этом случае матрица переходных вероят ностей объекта (3.2.6) не зависит от действия объекта. Предположим, что оба состояния объекта Q( 1 >(X) и Q ( 2 ) (X) равноценны. Тогда матрицы (3.2.6) равны
Д 0 ) = Д<2) |
= |
|
б |
1-6 |
|
|
|
(3.2.79) |
|
1-6 |
6 |
|
|
|
|||||
|
|
|
|
|
|
||||
Подставляя |
в |
формулы |
(3.2.26) значения |
611 = 622 = 6 и |
|||||
выражения |
(3.2.25), имеем: |
|
|
|
|||||
Pi 0 ) = p 4 ( D = p 2 |
( 2 ) |
--Ръ(2) |
= |
1 |
6 + ( l - 2 6 ) ( B s i + Y s2 ) |
||||
|
|
|
|
|
|
4 ' 2 6 + ( 1 - 2 6 ) (P + Y) |
' |
||
|
|
|
|
|
|
|
|
|
(3.2.80) |
(1)= Р з(1 ) |
= 0 Рг,(2 ) |
= --Pi (2): |
j |
_ |
6 + (1-26) |
(ps2 + ysi) |
|||
|
4 " |
26+(1 - 26 ) ( P + Y ) |
' |
||||||
|
|
|
|
|
|
||||
где р = Ро+Рь Y = Yo + Yi-По формулам (3.2.28) и (3.2.27) с учетом (3.2.79), (3.2.25) и (3.2.80) находим:
M[AQ] = |
(1-26) ( P - Y ) |
(SI-S2) |
|
|
(3.2.81) |
|
26+(1 - 26 ) (p+y) |
|
|
|
|
Pcp = |
6+(l-26)[p(s1 2 +s2 2)+2YSiS2 |
J |
(3.2.82) |
||
26+(1 - 26 ) (p + y) |
|
|
|||
|
|
|
|
||
Из формулы (3.2.81) следует, что |
если 0 , 5 < 6 ^ 1 , то |
||||
M[AQ] достигает минимума |
при у = 0 |
|
и р = 1. Это озна |
||
чает, что оптимальным является алгоритм, значения па
раметров которого равны: |
Yo = Y i = 0 ; Уг—i', |
Po+Pi = l ; |
||
Рг = 0. |
Учитывая |
условие |
Po + 2pi + P 2 = l , имеем ро=1; |
|
р 1 = 0. |
Получаем |
алгоритм, в соответствии с |
которым |
|
при неудачном шаге следует делать возврат, .а при удач ном шаге — продолжать движение по тому же направ лению. Среднее приращение функции качества на одном
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
297
шаге для такого алгоритма имеет максимальное из воз
можных |
значений: |
|
|
M[AQ]= |
(1—26) |
—s2 ), |
(3.2.83) |
а средний штраф |
равен |
|
|
Pcp = 6 + ( l - 2 6 ) ( s 1 2 + s2 2 ). |
(3.2.84) |
||
Для алгоритма |
случайного спуска |
имеем: |
|
^ „ _ ч Ш 1 ^ 1 ! г £ ! з и 1 |
( 3 2 8 6 ) |
а для алгоритма случайного поиска |
с возвратом полу |
чаем: |
|
»wta- " " ^ м " - ' |
( 3 2 8 7 > |
» . < - M + d - W + t f ) |
( 3 2 8 8 ) |
Из формул (3.2.83), (3.2.85) и (3.2.87) следует, что среднее приращение функции качества при исполь
зовании |
|
оптимального алгоритма в |
(3 — 26) раз |
больше, |
||||
чем |
при |
использовании |
алгоритма |
случайного |
спуска, |
|||
и в |
( i + 2 |
6 ) раз |
больше, |
чем |
при алгоритме случайного |
|||
поиска с возвратом. |
|
|
|
|
||||
При |
0 |
^ б < 1 / 2 |
алгоритмы |
случайного спуска |
и слу |
|||
чайного поиска с возвратом не работают, что аналогично результатам, описанным в работе [28]. В этом случае, в
соответствии с |
формулой (3.2.81), отслеживать |
направле |
||||
ние градиента |
будет алгоритм, для которого |
у > Р , |
т. е. |
|||
алгоритм |
с |
неразумным поведением. |
Оптимальным |
|||
является |
алгоритм, для которого |
р = 0, |
у = 1 , |
т. е. |
р0 = |
|
= Pi = 0, |
р 2 = 1 |
и уо=1, у\=У2 = 0- |
Это означает, что |
при |
||
нештрафе следует сделать обратный шаг с вероятностью,
равной |
единице, а при штрафе — продолжать движе |
ние по |
тому же направлению. Среднее приращение |