ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 227
Скачиваний: 1
t\r2 |
ГI2 |
0 |
0 |
0 . . |
0 |
0 |
0 |
0 |
0 . . . |
0 |
0 |
0 |
0 |
Г\Г2 |
0 |
|
0 |
0 . |
0 |
0 |
0 |
0 |
0 . . . |
0 |
0 |
0 |
0 |
0 |
Г\Г2 |
0 |
гГ- |
0 . . |
0 |
0 |
0 |
0 |
0 . . . |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 . • |
гхг2 |
0 |
|
0 |
0 . . . |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 . . |
0 |
г;1 |
0 |
Г\Г2 |
0 . . . |
0 |
0 |
0 |
0 |
О |
О |
О О О . . . |
О |
0 0 |
О 0 . . . |
/-[2 0 гхг2 |
о |
||||||
О |
О |
0 |
0 0 . . . |
О |
0 0 |
О 0 . . . |
О /-,2 |
0 |
гхг2 |
||||
О |
О |
О О О . . . |
О |
0 0 |
О |
0 . . . |
О |
0 |
rt 2 |
r , r 2 ! |
|||
|
|
|
т |
|
|
|
|
|
|
пг |
|
|
|
(2.6.27)
ПОИСК С САМООБУЧЕНИЕМ
|
233 |
|
|
|
|
|
|
Т](г2) |
можно |
получить |
из 7"i(гi) и Т2(г2) — из |
Т2(г{), |
|||
если в этих матрицах поменять местами гх и г2. |
Мар |
||||||
Предельное |
распределение |
вероятностей цепи |
|||||
кова |
следующее: |
|
|
|
|
|
|
|
|
1 |
(а-Ь)ат~'Ь>- |
|
|||
|
~-P2m+\-i— -Г" f 1 |
ат — Ьт |
|
|
|||
|
|
2 |
(2.6.28) |
||||
|
|
|
|
|
|
||
|
|
1 |
|
(a-b)am~ibi~1 |
|
||
P2m+i — Pim+l—i — "7Г r2 |
a |
m |
— b |
m |
|
||
|
|
2 |
|
( i = l , 2 , . . . , m ) , |
|
||
|
|
|
|
|
|
|
|
где |
|
|
|
|
|
|
|
a = /-!2 + r2 2 ; b = 2r1r2. |
|
|
|
|
|
||
Среднее приращение |
функции |
|
|
||||
M [ A Q ] = - ^ |
( п - ^ о , . |
|
|
(2.6.29) |
|||
|
У2 |
|
|
|
|
|
|
Полученная формула совпадает с формулой (2.6.17). Следовательно, увеличение памяти автомата Л 2 в рас смотренном случае не влияет на среднее приращение функции Q(xi,x2) при ее оптимизации.
Из изложенного в этом параграфе видно, что относи тельно среднего приращения функции Q(X) на одном шаге поиска оба алгоритма эквивалентны, т. е. для обоих можно указать такие значения их параметров, при которых средние приращения функции Q(X) совпадают.
§ 2.7. СТАТИСТИЧЕСКИЕ СВОЙСТВА КОЛЛЕКТИВА ВЕРОЯТНОСТНЫХ АВТОМАТОВ ПРИ ОПТИМИЗАЦИИ ФУНКЦИИ л ПЕРЕМЕННЫХ
В предыдущем параграфе были получены формулы для определения предельных вероятностей цепи Маркова и среднего приращения функции Q(X), если эта функция зависит от одного или двух перемен ных. В этом параграфе получим общие формулы для случая функции Q(X) п переменных при условии, что
ГЛАВА II
234 |
|
каждый автомат коллектива |
имеет два состояния [16], |
т. е. память автоматов т\—\ |
(/= 1,...,п). |
За состояние системы, как и раньше, примем элемент
множества возможных значений вектора |
W = (wi, w 2 , . . . |
|
..., wn), |
которое обозначим через {W}. Общее число воз |
|
можных |
значений вектора W конечно и |
равно |
п
|
|
|
|
(2.7.1) |
Пусть |
pij |
(i, |
/ e [ W } ) означает вероятность |
перехода |
вектора |
W |
из |
состояния W ( i ) в состояние WW |
за один |
шаг. Переход вектора W из одного состояния в другое описывается цепью Маркова с матрицей переходных ве
роятностей (2.1.25), матрицы |
Л 0 |
и А\ |
которой определя |
ются формулами (2.1.107) и (2.1.108). |
|
||
Предельные вероятности р |
и ..., |
р 2 п |
этой цепи Маркова |
в общем случае находятся как решение системы алгеб раических уравнений (2.1.20). В этом параграфе [16] по кажем другой, более простой прием нахождения пре дельных вероятностей
Разобьем множество состояний системы {W} на два
непересекающихся |
подмножества |
{W}+ |
и |
{ W } - , при |
|||||
чем W e { W } + , |
если AQ>0 |
при смещении АХ; в про |
|||||||
тивном случае, т. е. когда |
AQ<0, |
W e { W } - . |
Случай, |
||||||
когда AQ = 0, |
который возможен |
при совпадении |
линии |
||||||
уровня функции Q(xu...,xn) |
с одним из поисковых дви |
||||||||
жений AXW (/ = 1 , . . . , 2"), не будем |
рассматривать. |
||||||||
Пусть |
глубина |
памяти |
всех |
автоматов |
коллектива |
||||
равна единице |
( т г |
= 1 ; 1=1,... ,п). |
В этом |
случае |
вектор |
||||
состояний |
системы |
W = ( ш ь |
. . . , да„) |
имеет |
2™ различных |
||||
значений. Перенумеруем эти значения следующим обра зом: номера от 1 до 2"-1 присваиваются состояниям сис темы, входящим в { W } - . Остальным состояниям, вхо дящим в (W}+, номера присваиваются по следующему
правилу: |
если |
состояние |
W = (wu |
..., |
wn) имеет номер |
г = 1 , 2,...,2п~х |
(т. е. A Q ( i ) < 0 ) , то номер i + 2n~x присваи |
||||
вается такому |
состоянию |
из { W } + , |
для |
которого |
|
A Q ( l + 2 |
> = - A Q W |
|
|
|
|
ПОИСК С САМООБУЧЕНИЕМ
|
235 |
|
|
|
|
В случае вероятностных |
автоматов |
коллектива |
(0 < |
||
< / А < 1 ; |
1=1,... , п ) |
множество состояний вектора |
W об |
||
разует |
эргодический |
класс, |
состоящий |
из одного |
под |
класса. |
|
|
|
|
|
Отсюда следует, что существуют предельные вероят ности pi того, что система будет находиться в состояниях
W«> |
( i = l , . . . , 2 " ) . |
|
|
|
вероятности pi и |
pi+s |
|
||||
Согласно |
[16] предельные |
со |
|||||||||
стояний |
W<*> вектора |
W |
( f = l , . . . , s ) , |
где s = 2™_ 1 , опре |
|||||||
деляются следующими |
формулами: |
|
|
|
|
||||||
|
|
|
s |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.7.2) |
|
где |
вероятность |
перехода |
рц для |
вероятностных |
ав |
||||||
томатов, |
глубина |
памяти |
которых |
равна |
единице, |
||||||
имеет вид |
|
|
|
|
|
|
|
|
|
||
|
|
П |
|
|
П |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(2.7.3) |
|
причем xi = ri |
(1=1,...,п), |
если 1-я |
координата |
вектора |
|||||||
W<i'= (wu |
..., |
wn), |
имеющего |
номер |
/ |
(/= 1, ... ,2"), сов |
|||||
падает с 1-й координатой вектора состояний W ( i ) , имею
щего номер |
i (i= 1 , . . . , 2п). |
В противном |
случае Xi = |
||
= 1—^. Для |
состояний W = (w\,..., |
wn), принадлежа |
|||
щих {W}+, т. е. имеющих |
номер j = s+ 1 , . . . , 2s, |
наобо |
|||
рот, в случае совпадения указанных |
координат |
Xi=\—ri, |
|||
в случае несовпадения Xi = rt |
(1=1,... |
, п ) . |
|
|
|
Вероятности перехода рц удовлетворяют следующим
свойствам. |
|
|
С в о й с т в о |
1: |
|
Pii — Pi+s,i |
|
(2.7.4) |
( / = 1 , |
, s; i=l, . . . , 2s). |
|
С в о й с т в о |
2: |
|
PiA+s — Pii |
|
(2.7.5) |
( / = 1 , |
,2s; 1=1,..., |
s). |