ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 210
Скачиваний: 1
|
|
|
|
Замеченные ошибки |
|||
Стр [ |
Строка или № |
|
|
Напечатано |
|||
| |
|
формулы |
|
|
|
|
|
24 |
Форм. (0.3.29) |
Тх(Ух1х)В |
|
|
|
||
51 |
Форм. (0.3.11), |
|
|
|
|
|
|
63 |
4-я |
строка |
|
|
|
|
|
2-я |
строка |
= ( + 1,..., |
+ 1 , - 1 , - 1 ) ; |
||||
|
снизу |
|
|
|
|
|
|
71 |
Форм. (1.5.1), |
д у \ г ( 2 ) = _ а е 2 ; . . . |
|
||||
|
2-я |
строка |
.. . В3 |
Bt |
|
|
|
94 |
Матрица |
|
|
|
|||
|
(1.7.26) |
... 0 |
в3 |
|
|
|
|
|
|
|
|
|
|
||
111 |
Матрица |
.010...01. |
|
|
|||
|
(1.9.13) |
+ 2р<ф) |
|
||||
112 |
Форм. (1.9.14), |
тп+п |
|
|
|
||
|
2-я |
строка |
|
|
|
|
|
186 |
Табл. 2.2.2, |
1 |
|
|
|
|
|
|
2-я |
строка снизу |
— (1-/гб) |
|
|
||
|
|
|
4 |
|
|
|
|
191 |
Форм. (2.2.54), |
*°Р » |
= |
|
|
||
|
1-я |
строка |
2 - 1 |
|
|
|
|
294 |
1 -я строка снизу |
(0=1) |
|
|
|
||
334 |
2-я |
строка тек |
Тогда |
|
|
выражения |
|
340 |
ста |
снизу |
(3.5.11) |
и (3.5.12) |
|||
6-я и 7-я строки |
Случайный |
поиск в |
|||||
|
сверху |
многопараметриче- |
|||||
341 |
9-я |
и 10-я стро |
ских |
задачах. |
непре |
||
Сопоставление |
|||||||
|
ки |
снизу |
рывного и автоматного |
||||
|
|
|
случайного поиска. 118 |
||||
341 |
6—8-я строки |
Переходный процесс в |
|||||
снизу |
двумерной |
|
экстре |
||||
|
|
|
мальной |
системе при |
|||
|
|
|
наличии |
запрещенных |
|||
|
|
|
областей |
и случайном |
|||
|
|
|
методе поиска |
. 123 |
Должно быть
Т1(у/х)В
ДХ<т/2-Н)
= ( + 1,..., +1, - 1 , +1); дХ<"+2 >=-ое2 ; .. .
. . . ВгВ\
. . . 0 в2
. 000 .. . 01.
m + п
3 = m + 1
1
— (1 +Аб) 4
= Р2„ - 1 =
(6=1)
Тогда выражения (3.5.11) и (3.5.13) Проблемы случайного поиска, вып. 1.
Сопоставление непре рывного и автоматно го алгоритмов случай
ного поиска . . 113 Автоматная оптимиза
ция при наличии огра ничений . . . 123
Л. А. Растригин, К. К. Рапа. Автоматная теория случайного поиска.
ПОИСК С САМООБУЧЕНИЕМ
143
Здесь сумма
v
(2.1.27)
где Sj ( / = l , . . . , w ) определяется формулой (2.1.10), а qa — элементы матрицы (2.1.13), представляющие собой вероятность, с какой штрафуется автомат, если он на
ходится |
в состоянии W<*> (t = l , 2, . . . , m ) . Эта формула |
|||||||
аналогична формуле, рассмотренной в главе |
I I для |
слу |
||||||
чая, |
когда выход |
автомата совпадает |
с его |
состоянием. |
||||
2. |
Вероятностные |
автоматы со случайными |
выходами |
|||||
и детерминированными |
переходами. |
Функционирование |
||||||
этого |
автомата в случайной среде описывается частным |
|||||||
случаем |
цепи |
Маркова |
(2.1.25). Для |
этого |
случая |
мат |
||
рицы А0 |
и А\ |
являются |
стохастическими булевыми |
мат |
рицами, т. е. матрицами, у которых в каждой строке один элемент равен единице, а все другие равны нулю. Веро ятности штрафов для таких автоматов рассматриваются относительно его состояний и определяются формулой
(2.1.26). |
|
|
|
|
|
3. |
Вероятностные автоматы |
со |
случайными |
перехо |
|
дами |
и детерминированными |
выходами. |
Функциониро |
||
вание такого автомата в случайной |
среде |
(2.1.10) |
пред |
ставляет собой процесс оптимизации при помощи кол лектива независимых автоматов [12, 13]. Его полное функционирование описывается частным случаем цепи
Маркова |
(2.1.25). В этом случае матрицы А0 |
и Ах явля |
|||
ются |
стохастическими, а матрица Qij |
(формула |
|||
(2.1.13)) |
— булевой стохастической матрицей. Матрицы |
||||
Qi(i) |
(/= 1 , . . . , а) |
имеют вид |
|
||
|
|
0 • • 0 0 |
0 ••• 0 |
|
|
|
|
о •• 0 0 0 |
о |
(2.1.28) |
|
Qi(i) |
= |
о • • 0 1 0 |
о |
||
|
|
о •• 0 0 0 |
о |
|
m—ji
о •• о о о ••• о
ГЛАВА II
144
где номер /г- соответствует действию ДХ<->4>, которое про изводит автомат в состоянии W<'>. С учетом матрицы (2.1.28) и формулы (2.1.27) находим матрицу вероятнос тей штрафов
|
О |
|
О О |
о |
|
|
|
|
|
|
о |
о |
о |
|
|
S* = О |
0 |
0 |
••• s. |
о ••• о |
о |
(2.1.29) |
|
О |
0 |
0 |
••• 0 |
0 ••• 0 |
s |
|
где Sj( — ... ,v) — |
вероятность штрафа того дей |
ствия автомата ДХ( ^', |
которое соответствует состоя |
нию W<*>. |
|
Рассмотрим, как для автомата, заданного матрицами (2.1.11) и (2.1.12), определить выходную функцию
(2.1.2). Так как вектор ДХ принимает значение |
из конеч |
ного множества (2.1.6), то и координаты Axi |
(l—l,...,n) |
вектора ДХ принимают значения из конечных |
множеств |
Axle={lxlU),...,AxiW} |
(2.1.30) |
( / = 1 , 2 , . . . , / г ) , |
|
где vi — конечное число.
Выходную функцию автомата р^(ДХ), определенную формулой (2.1.2), задаем при помощи выходной функ
ции |
для |
каждой |
координаты |
Axt |
вектора ДХ, т. е. ис |
|||
пользуя п функций, не зависящих от номера |
шага N: |
|||||||
ptw |
(Axt) =*pi(AxiWrNN) |
|
|
|
(2.1.31) |
|||
|
|
|
|
( / = 1 , 2 , . . . |
n), |
|
|
|
где N — номер шага поиска. |
|
|
|
|
||||
Рассмотрим |
алгоритмы самообучения при поиске по |
|||||||
вершинам |
гиперкуба. Предположим, |
что |
координаты |
|||||
Axi |
(1 = 1,..., |
п) |
вектора ДХ |
могут |
принимать только |
|||
одно |
из |
двух |
значений: + 1 или |
— 1 . Тогда |
множество |
|||
действий |
автомата |
имеет |
|
|
|
|
||
v = 2n |
|
|
|
|
|
|
(2.1.32) |
ПОИСК С САМООБУЧЕНИЕМ
145
элементов, т. е. имеются 2п возможных смещений AX'J' в пространстве {X}. Предположим, что 1-я функция
(2.1.31) зависит только от 1-й координаты |
w\ вектора па |
|
мяти W. Тогда формулу (2.1.31) можно задать в виде |
||
следующих двух формул: |
|
|
Вер (Ax,m^i/WlW)=Fi(gi,Wi); |
|
(2.1.33) |
Вер (Дхг(*> = - 1 М < * > ) = l-Fi{qi,wi) |
(2.1.34) |
|
(/= 1, 2 , . . . , n; |
o; = const, 0<<7;< 1). |
|
Далее будем требовать, чтобы |
функции |
Fi(qi,wi) были |
монотонно возрастающими и чтобы они удовлетворяли условию
0^Fi(qi,Wi)^l |
|
|
(2.1.35) |
(1=1,... |
п). |
|
|
Функция Fi = Fi(qi,wi) |
может |
иметь следующий |
вид: |
1, |
если |
wi>q; |
|
Fi= • у ( 1 + - у ) , |
если |
\wt\^q; |
(2.1.36) |
. О, |
если |
wi<i — q. |
|
Вид этой функции показан на рис. 2.1.1. На изменение
10 — 2014
ГЛАВА II
146
координат Xi вектора W будем |
накладывать ограни |
|||
чение |
|
|
|
|
|
d, |
если |
Wi>d; |
,,Jv. |
wi= |
wi, |
если |
—d^.wi^.d\ |
(2.1.37) |
|
— d, если |
Wi<_ — d. |
|
Теперь рассмотрим, как, используя формулы (2.1.33) и (2.1.34), определить вероятность q^, т. е. вероятность по явления выхода АХ*-»' при условии, что автомат нахо дится в состоянии WW. По определению (2.1.9) поло жено
<7« = Вер (AX = AXU>/W=W<4'>).
Каждый выход AX(J> характеризуется набором своих ко ординат, т. е.
AX(J)=(Ax1 <i),...,Ax„<J)), |
|
|
(2.1.38) |
||||
где |
|
вероятностью Ft(qu |
|
||||
Дл:,0">= / |
+ 1 с |
шг<*>); |
|||||
\ |
—1 с вероятностью |
|
\~Fi(qi,Wi(i)). |
||||
Вероятности |
F^ |
= Fi(qt,Wi^) |
и |
1 — Fi(qt, w^) = 1 — F^ |
|||
зависят от состояния |
W ( |
i ) , в |
котором находится вектор |
||||
W, т. е. от координат |
Wi(i) |
вектора |
W^>. Эта зависимость |
||||
выражается |
формулами |
(2.1.33) |
и |
(2.1.34). Объединяя |
|||
формулы (2.1.33) и (2.1.34), имеем: |
|
||||||
Вер (Ax, = Ax,«>M = ^ ( i |
) ) = у [ 1 - 0 - |
||||||
~2F^)) |
signAx^J], |
|
|
(2.1.39) |
|||
где |
|
|
|
|
|
|
|
|
1, |
если |
г > 0 ; |
|
|
|
|
sign z = |
0, |
если |
г = 0; |
|
|
(2.1.40) |
— 1, если г-<0.
При Алтг<»> = 1 из этого соотношения получаем формулу (2.1.33), а при Ахг ('' = —1 — формулу (2.1.34). Следова тельно,
qij = Вер {Axi = Ax^i\ |
Ахп = Ax„(J)/W = W«>) = |
п
= ( Т У П П - |
sign Д*,и>], (2.1.41) |