ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 234
Скачиваний: 1
|
|
|
|
|
|
|
|
|
|
|
|
К5 |
*>1 |
|
0 |
0 |
0 .. . |
0 |
0 |
0 |
0 |
0 .. |
0 |
0 |
0 |
v2 |
0 |
1 — v2 |
0 0 . . . |
0 |
0 |
0 |
0 |
0 . . |
0 |
0 |
0 |
|
0 |
|
0 |
1 — V'c 0 .. |
0 |
0 |
0 |
0 0 . . |
0 |
0 |
0 |
||
0 |
0 |
0 |
0 |
0 . |
|
0 |
|
0 |
0 . . |
|
|
s |
|
l-Vrn |
0 |
0 |
0 |
||||||||
0 |
0 |
0 |
0 0 . . . |
0 |
1 |
0 |
Vm |
0 . . |
0 |
0 |
о |
|
0 |
0 |
0 |
0 |
0 . . |
0 |
0 |
0 |
0 |
0 .. |
1 — V2m-\ |
0 |
V2m—\ |
0 |
0 |
0 |
0 0 . . |
0 |
0 |
0 |
0 0 . |
0 |
1 - v2m |
|||
|
|
|
|
|
|
|
|
|
|
|
|
(2.9.8) |
ГЛАВА II
266
Из матрицы (2.9.7) получаем систему векторных уравне ний для нахождения предельных вероятностей состоя ний автомата:
Pl = |
PlRl+P2Ik; |
(2.9.12)
P 2 = P , f l M - P i A ,
где
P i = ( p i , р 2 т ) ;
(2.9.13)
Р2= (Р2т+Ь • • • , Рш) •
Из системы векторных уравнений (2.9.12) находим
P 2 = 4 1 P i - |
(2-9.14) |
к
Подставляя это выражение в первое уравнение системы (2.9.12), получаем
Pl = Pl(XR |
|
+ U), |
|
|
|
(2.9.15) |
||||
где матрица |
KR + XI имеет вид (2.9.16). |
|
||||||||
Решая |
систему |
уравнений |
(2.9.15) и используя |
фор |
||||||
мулу |
(2.9.14), находим |
|
|
|
|
|||||
|
|
/ |
1-и, |
V - 1 |
|
|
i = 2,. . ., 2т; |
|
||
|
|
I |
|
|
I |
рх |
|
при |
|
|
|
|
|
|
|
|
|
|
|
(2.9.17) |
|
4 |
1 |
я |
/ |
i - |
^ у |
- |
рх |
при |
t = 2m + 1 , . . . , Am. |
|
|
|
|
|
|
|
|
|
|||
После |
нормировки |
вероятностей pi (t = l, ... ,4m ) |
полу |
|||||||
чаем |
|
|
|
|
|
|
|
|
|
|
Xvx + X X ( l - o i ) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Xv i |
X |
X(\-vx) |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Xvx |
X |
A,(l-i>i)0 |
0 |
0 |
0 |
0 |
|
XR + XI = |
|
|
|
|
|
|
|
|
0 |
0 |
0 |
о |
о |
Xvx |
X |
X(l-Vi) |
0 |
о |
0 |
0 |
о |
0 |
0 |
Xvx |
I |
X(\- |
о |
0 |
0 |
о |
0 |
0 |
0 |
Xvx |
1 + л ( 1 |
(2.9.16)
ГЛАВА II
268 |
|
|
|
|
|
|
х (l-Vi |
V - 1 |
1 |
|
• , |
о |
|
' / 1 - 0 ! У" 1 |
1 |
|
. п |
|
||
( |
j |
_ _ |
— |
при t |
= 2m + |
|
' |
|
£ ( ' . - |
) |
|
|
|
|
|
|
|
+ |
1, . .. , 4/и. |
|
|
|
|
|
|
|
(2.9.18) |
Поскольку гх>г2, |
имеем |
|
|
|
|
|
0 < ^ ^ - < 1 . |
|
|
|
|
|
(2.9.19) |
По формуле суммы геометрической прогрессии находим
2 т |
|
|
|
|
>, |
- ) = — |
к - |
^ — . |
(2.9.20) |
В окончательном виде формулу предельных вероятнос тей pi можем записать так:
|
4 |
71 |
~ П Р И » = 1 , . . . , 2 ш ; |
|
j |
vx2m— (1 |
-vx)2m |
|
|
Pi= ' |
~ |
|
(l-vl)i-lvl2m-i(2vl-l) |
|
Иг |
Х-——- |
|
-— |
- при t = 2m + |
I |
|
|
|
+ 1 , . . . , 4/л. |
(2.9.21)
Среднее приращение функции качества на одном шаге вычисляется по формуле
m |
2m |
(2-9'22) |
M[AQ]= £ |
Pi- 2 Pi- |
|
i = l |
i—m+\ |
|
Подставляя в |
эту формулу выражения |
(2.9.21), на |
ходим: |
|
|
ПОИСК С САМООБУЧЕНИЕМ
269
lit
|
V l 2 m _ { l _ V l - ) |
|
|
|
|
|
||
|
2т |
|
|
|
|
|
|
|
- |
J % i 2 m - i ( l - - t ' i ) , ' - - |
1 l = л — |
2 U l _ 1 |
|
•X |
|||
|
|
|
|
|
2 m _ / 1 _ 7 | Л 2 т |
|
||
|
|
|
|
|
2m |
|
|
|
* - £ r [ ^ ( ^ ) - < ? ( - ^ ) ' ] - |
||||||||
|
|
1 |
i=l |
1 |
i=m+l |
1 |
|
|
|
[0,2m _ |
( l _ t |
, 1 ) 2 m ] ( 1 |
_ U l ) L |
\ |
/ J X |
||
|
, = 1 |
|
|
/ |
^ " ^ ( l - ^ ) ' |
|
|
|
|
1- |
|
|
|
|
|
|
|
|
|
T - T ^ - T ^ r . |
|
|
(2-9.23) |
|||
|
• |
+ |
T |
W ' |
|
|
|
|
где |
|
|
|
|
|
|
|
|
|
ri-(rl~r2)sl |
|
|
|
|
(2.9.24) |
||
vi |
|
r2+(ry-r2)sl |
|
|
||||
|
|
|
|
|
||||
Для случая, |
когда о т с у т с т в у е т |
п о м е х а , |
si = l и |
|||||
1 — vx |
r2 |
|
|
|
|
|
|
|
L = |
— , |
|
|
|
|
(2.9.25) |
||
из формулы (2.9.23) при учете соотношения (2.9.25) имеем
|
1 |
|
|
M[AQ] = l |
) Г ' ' . |
_ |
(2.9.26) |
ГЛАВА II
270
Полученная формула отличается от выражения (2.6.11) только множителем X.
Следовательно, поскольку 0 < Я < 1 , то для случая ли нейной функции качества и при размерности л = 1 про странства {X} алгоритм троичного поиска по сравнению с алгоритмом двоичного поиска имеет, как и ожидалось, более медленную сходимость.
Г Л А В А I I I
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
§ 3 . 1 . П О С Т А Н О В К А З А Д А Ч И С И Н Т Е З А О П Т И М А Л Ь Н О Г О А Л Г О Р И Т М А
ВК Л А С С Е А Л Г О Р И Т М О В
ДИ С К Р Е Т Н О Р А С П Р Е Д Е Л Е Н Н О Г О
С Л У Ч А Й Н О Г О П О И С К А |
|
|||
В главах I |
и |
I I было |
показано, что |
алго |
ритм случайного поиска |
в |
процессе |
оптимизации |
можно |
интерпретировать как вероятностный автомат в случай ной среде. Там же приведены конструкции автоматов,
описывающих известные алгоритмы |
детерминирован |
||
ного |
и случайного поиска. В настоящем |
параграфе на |
|
базе |
представления алгоритмов поиска |
в |
виде вероят |
ностных автоматов будем отыскивать оптимальные алго ритмы для оптимизации широкого класса объектов.
Рассмотрим класс алгоритмов дискретно распределен ного поиска. Эти алгоритмы характеризуются тем, что
смещения ДХ в пространстве параметров Х = ( х ь |
. . . , хп) |
оптимизируемого объекта Q(X) разрешаются по |
направ |
лениям, число которых т конечно. Пусть дозволенные смещения ДХ в пространстве {X} определяются условием,
что приращение |
координат |
ДХг ( t = l , . . . , n ) |
может |
при |
||
нимать |
только |
два значения: + 1 или |
— 1 . Тогда |
число |
||
возможных направлений |
смещения |
т = 2п. |
Индексы |
|||
этих направлений строим следующим образом: |
|
|||||
ДХ |
т = - Д Х г - |
|
|
|
(3.1.1) |
|
•л— |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
Алгоритмы поиска задаем в классе автоматов со сле дующими стохастическими матрицами перекода [53]: