ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 233
Скачиваний: 1
ПОИСК С САМООБУЧЕНИЕМ
261 |
|
§ |
2.9. Т Р О И Ч Н Ы Й А Л Г О Р И Т М П О И С К А |
В |
предыдущих параграфах были рассмот |
рены алгоритмы двоичного поиска, при которых по каж
дой координате |
Хг |
приращение Ах; |
(г = |
1,...,п) может |
принимать одно |
из |
двух значений: |
—1 |
или -4-1. Здесь |
рассмотрим алгоритм троичного поиска, при котором
приращение Ах; принимает одно |
из трех значений: |
— 1, |
О или + 1 . Рассмотрим троичный |
поиск в процессе |
опти |
мизации коллективом независимых вероятностных авто
матов |
[20]. Пусть в |
дискретные |
моменты |
времени |
ty |
|||||
( / V = l , |
2, ... ) |
каждый |
автомат |
коллектива |
|
Aj с |
вероят |
|||
ностью |
}.j ( O ^ ^ j ^ l ) |
участвует в |
процессе |
поиска, |
т. е. |
|||||
совершает смену |
состояний |
под |
воздействием |
входа |
||||||
AQ{tN) |
и выдает |
на выход сигнал Axj(t^), |
или с вероят |
|||||||
ностью |
\—Xj = Kj |
не участвует в процессе поиска. В мо |
||||||||
мент времени |
tN |
состояния автоматов w(ty) |
и значения |
|||||||
переменной |
Xj(tN) |
|
определяются по |
следующим фор |
|||||
мулам: |
|
|
|
|
|
|
|
|
|
|
Wj(tN) |
/ |
W(w}(tN^), |
AQ(tN)); |
|
|
|
||
|
I |
Wj(tN-i), |
|
ес:ли автомат Aj не работает; |
|||||
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
(2.9.1) |
|
XJVN) =xi(ty-l) |
+AXj(tN), |
|
|
|
(2.9.2) |
|||
где Axj(tN) |
|
— выходное действие автомата Aj |
в |
момент |
|||||
tN, |
которое |
определяется однозначно |
состоянием |
памяти |
|||||
riDj и участием Aj |
в процессе поиска; |
|
|
|
|||||
|
|
|
— 1 |
при |
l^Wj^m; |
|
|
||
|
AXj(tN) |
= |
+ |
1 |
при |
т+ lsCayj==52m; |
|
(2.9.3) |
|
|
|
|
|
0, если автомат Л; не работает. |
|
|
|||
|
Далее для простоты изложения рассмотрим одномер |
||||||||
ный случай |
( / i = l ) . Пусть автомат имеет 2т |
состояний |
|||||||
и |
переходы |
автомата из одного состояния в другое, |
|||||||
когда он работает, задаются стохастическими |
матри |
||||||||
цами |
|
|
|
|
|
|
|
|
|
ГЛАВА II
|
262 |
|
|
|
|
|
|
||
f>0(P)=XQ = |
|
|
|
|
|
|
|
||
Г\ г2 |
0 |
0 |
0 . . 0 0 0 0 0 . .. 0 0 0 0 |
||||||
ri 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 |
0 |
0 |
. • ri 0 г2 |
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 г2 |
0 Г\ |
||
0 |
0 |
|
0 |
0 |
0 |
. . 0 0 0 0 0 |
. .. 0 0 Г2 Г\ |
||
|
|
|
|
|
ш |
|
|
m |
(2.9.4) |
=/?,= |
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|||
г2 |
г{ |
|
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 Г\ 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 г2 |
||
0 |
0 |
|
0 |
0 |
0 |
. . 0 0 0 0 0 |
. .. 0 0 |
г2 |
|
т |
т |
Когда автомат |
не работает, т. е. не участвует в про |
цессе поиска, его состояние не изменяется и его переход ные матрицы равны единичной матрице
|
1 |
о |
о . . . |
О |
|
R0w = Rlm = |
О |
1 |
о . . . |
о |
(2.9.5) |
|
|
|
|
||
|
О |
0 |
0 . . . |
1 |
|
ПОИСК С САМООБУЧЕНИЕМ
263
Введем новый автомат с количеством состояний, рав ным 4т. Пусть первую группу состояний нового авто мата образуют состояния исходного автомата совместно с событием «Автомат работает», а вторую группу — со стояния автомата совместно с событием «Автомат не ра ботает». Нумерация состояний и переходы из одного со
стояния |
в |
другое |
для |
нового |
автомата |
показаны |
на |
||||
рис. 2.9.1. |
|
|
|
|
|
|
|
|
|
|
|
По этому рисунку получаем следующие переходные |
|||||||||||
матрицы |
автомата: |
|
|
|
|
|
|
|
|
||
А0- |
RoX |
RQX |
|
|
|
RiX |
RXX |
(2.9.6) |
|||
|
|
|
|
|
|
|
|
|
|||
|
IX |
|
IX |
|
|
|
IK |
|
IX |
|
|
где Ro и Ri |
— |
матрицы |
(2.9.4); |
|
|
|
|
|
|||
|
/ |
— |
единичная матрица |
(2.9.5); |
|
|
|||||
|
X — |
вероятность |
того, |
что |
автомат работает; |
||||||
Я = 1 — л — вероятность того, что автомат не работает. |
|||||||||||
Объединяя |
матрицы |
А0 |
и АХ |
с |
учетом |
вероятностей |
|||||
штрафов |
действий |
A X ( i ) |
автомата, |
получаем матрицу |
А, |
||||||
| h,
л |
* ' |
Д |
imtl / |
£i 3 m |
i |
-Г |
Рис. 2.9.1. Графы переходов автомата, описывающего алгоритм троичного поиска:
а — при нештрафе; б — при штрафе.
ГЛАВА II
264-
которая описывает функционирование автомата в слу чайной среде:
А: |
RX |
RX |
|
(2.9.7) |
|
|
|
||
|
IX |
IX |
|
|
Здесь |
матрица R имеет |
вид (2.9.8). Ее элементы имеют |
||
вид |
|
|
|
|
Vi = rlsi + r2(l-Si) |
=r2+ |
(r1-r2)si; |
||
\-Vi |
= rx-{rx-r2)Si |
; |
|
|
здесь Si — вероятность |
штрафа действия ДХ(*> автомата |
|||
в t-м состоянии; |
|
|
||
|
|
|
|
(2.9.9) |
Далее предполагается, что функция качества Q(X) линейна. Тогда AQ ( i ) = a (i = l , . . . , m ) и AQ(») = — a (t = = m + 1 , . . . , 2m). Следовательно,
S — S, — . . . —Sm — 1 S m + i — • = 1 — S2n
- И ' Ч £ ) ] . |
(2.9.10) |
|
где a = ] grad Q(X) |. С учетом формул (2.9.9) и (2.9.10) матрица R принимает вид
R = |
|
|
|
|
|
|
|
|
»i |
|
о |
о |
о . . . О О |
О |
о |
||
vi |
0 |
1 - и, |
о |
о . . . о |
о |
|
о |
о |
0 |
с/! |
0 |
1 - ^ |
о . . . о |
о |
|
о |
о |
|
|
|
|
|
|
|
|
2т |
0 |
О |
О |
О 0 . . . У, |
0 |
1 - 0 ! |
о |
||
0 |
0 |
О |
О |
0 . . . 0 |
V[ |
|
0 |
1 - у, |
О 0 |
0 |
0 |
0 . . . 0 |
0 |
|
i»! |
1 - р , |
|
|
|
|
|
2т |
|
|
|
|
(2.9.11)