ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 188
Скачиваний: 1
ВВЕДЕНИЕ
14
В настоящей книге везде будут рассмотрены алго-^
ритмы дискретно |
распределенного |
поиска |
{10]. Исследо |
|||||
вание таких алгоритмов поиска |
обосновано хотя бы тем, |
|||||||
что |
они широко |
применяются |
в технических |
устройст |
||||
вах |
— автоматических оптимизаторах |
[11], работающих |
||||||
по алгоритмам случайного |
поиска. |
|
|
|
||||
Дискретно |
распределенный |
поиск |
характеризуется |
|||||
тем, что множество реализаций |
случайного |
вектора АХ^, |
||||||
определяемое |
формулой |
(0.1.13), содержит |
конечное |
|||||
число векторов. |
|
|
|
|
|
|
||
Дискретно распределенный поиск будет определяться при помощи задания конечного множества из m элемен тов, которые могут быть значениями вектора ДХ<*>:
ДХ«>=(Д*,<1 >,...,Дхп( *) ) |
(0.2.11) |
||
|
( i = l , 2 |
m). |
|
Поиск по вершинам |
гиперкуба. Пусть, например, коор |
||
динаты вектора ДХ^ равны одному из двух |
чисел: + 1 |
||
или |
— 1, т. е. |
|
|
X i W e { + l , - 1 } . |
|
(0.2.12) |
|
При |
таком поиске векторы смещения AXN |
направлены |
|
к вершинам л-мерного гиперкуба. Число возможных
реализаций |
вектора |
смещения |
АХ для такого |
поиска |
равно числу вершин |
n-мерного гиперкуба, т. е. |
|
||
т = 2«. |
|
|
(0.2.13) |
|
Векторы |
возможных смещений |
АХ занумеруем |
в сле |
|
дующем порядке: |
|
|
|
|
АХН+™/2) = _ ДХМ |
|
(0.2.14) |
||
(« = 1 , 2 , . . . . т ) .
Запись алгоритмов (0.2.2) и (0.2.4) для дискретно рас пределенного поиска остается такой, как для непре рывно распределяемого поиска, только S здесь пред ставляет собой случайный вектор, образующийся путем равновероятного выбора одного вектора смещения АХ из 2" возможных.
К дискретно распределенному поиску применима идея самообучения [1, 3, 5, 6, 9]. При алгоритме покоординат-
ВВЕДЕНИЕ
15
ного самообучения для каждой координаты на М-и шаге задаются вероятности положительного и отрицательного смещения:
+ 1 С В Е Р ° Я Т Н 0 С Т Ь Ю |
(0.2.15) |
—1 с вероятностью |
1 — p i ( J V ) |
|
( i = I , n ) . |
Вероятности Pi( J V ) зависят
памяти Wjv= ( Ш 1 ( Л Г ) , . . . , гап(Ю) Эта зависимость, например,
от J-Й координаты вектора на iV-м шаге, т. е. от w^NK может иметь следующий
В И Д |
: |
0 |
при а><<*><-1; |
|
|
||
pi(N)= |
\j |
(l+WiiN)) |
при |
| ш ^ | < 1 ; |
(0.2.16) |
||
|
|
1 |
при |
Wi<-N\ |
|
|
|
где |
Wiw |
— |
t-я |
координата |
вектора памяти |
Wjv на N-m |
|
шаге поиска. Следовательно, решающую функцию по иска задают формулы (0.2.15) и (0.2.16). Алгоритм са
мообучения |
задается |
для |
|
каждой |
координаты |
в |
виде |
||||||||||
WilN+» |
|
= |
WiW-b |
sign |
( A Q J V A ^ W ) |
|
|
|
(0.2.17) |
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
(i=l,...,n). |
|
|
|
|
|
На изменение w^N) |
накладывается |
ограничение |
|
|
|||||||||||||
| ш ^ > | г ^ |
|
|
|
|
|
|
|
|
|
|
|
|
(0.2.18) |
||||
|
(0<dt). |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
Другой |
алгоритм |
самообучения |
образует |
систему |
по |
||||||||||||
иска |
с |
|
применением |
|
оптимизирующих |
|
автоматов |
||||||||||
[2, 12—16]. Здесь параметр памяти Wi(N) |
соответствует |
||||||||||||||||
состоянию i-ro автомата |
на |
N-u |
шаге. |
Оно |
|
принимает |
|||||||||||
одно |
из |
дискретных |
значений, число |
которых |
равно |
||||||||||||
числу состояний автомата. Вероятность Pi(N) |
может |
при |
|||||||||||||||
нимать значения |
1 или 0 в зависимости |
от значения |
па |
||||||||||||||
раметра |
Wi^K |
Переход |
вектора памяти КУ{<№> |
ИЗ |
одного |
||||||||||||
состояния |
в |
другое |
|
от |
iV-ro шага поиска к |
{N+\)-uy |
|||||||||||
шагу |
является |
случайным. |
Следовательно, |
|
решающая |
||||||||||||
функция |
поиска |
задается |
формулой (0.2.15) |
|
и выраже |
||||||||||||
нием |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
„.(*> = |
{ s J g n ^ W > |
|
|
е |
с л |
и |
т™>0; |
|
|
|
|
|
|||||
Н г |
|
I |
l + signte;^), |
|
если |
w^<0. |
|
|
к |
|
' ' |
||||||
ВВЕДЕНИЕ
16
Алгоритм самообучения можно также задать, например, при помощи рекуррентной формулы
t0i( J V ) — б sign (AQjvAxj( J V ) ) |
с вероятностью qf, |
Wiw + 6 sign ( A Q W A X J ( J V ) ) |
с вероятностью l — c/i |
|
(0.2.20) |
Если решающую функцию поиска задать формулами (0.2.15) и (0.2.16), а алгоритм самообучения — форму лой (0.2.20), то получаем более общий алгоритм, обоб щающий как алгоритм покоординатного самообучения,
так и систему автоматного |
поиска. |
|
Покоординатный |
поиск |
[17—19] также является дис |
кретно распределенным поиском. При этом поиске одна
из координат |
вектора AXJV принимает значение |
+ 1 или |
||||||
— 1, а все другие координаты этого вектора |
|
равны нулю, |
||||||
т. е. |
|
|
|
|
|
|
|
|
A * i W e = { l , 0 , - 1 } |
|
|
|
|
|
(0.2.21) |
||
( i = |
1,2 |
л) |
|
|
|
|
|
|
при выполнении условия |
|
|
|
|
|
|
||
п |
|
|
|
|
|
|
|
|
2|Дх4 (*п| = 1. |
|
|
|
|
|
(0.2.22) |
||
i=i |
|
|
|
|
|
А Х для поко |
||
Число возможных |
направлений смещения |
|||||||
ординатного поиска в этом случае |
равно |
|
|
|
|
|||
т = 2п. |
|
|
|
|
|
|
(0.2.23) |
|
Троичный |
поиск |
[20] |
характеризуется |
тем, |
что все |
|||
координаты вектора AXN |
принимают одно |
из |
значений |
|||||
+ 1, 0 или — 1 , т. е. имеет |
место (0.2.21) |
без |
ограничения |
|||||
(0.2.22). Число возможных направлений |
смещения А Х в |
|||||||
пространстве X для троичного поиска равно |
|
|
|
|||||
т = Зп. |
|
|
|
|
|
|
(0.2.24) |
|
|
§ 0.3. Н Е К О Т О Р Ы Е С В О Й С Т В А |
|
||||||
|
В Е Р О Я Т Н О С Т Н Ы Х А В Т О М А Т О В |
|
||||||
|
Под |
вероятностным |
автоматом |
понима |
||||
ется объект [21—24] |
|
|
|
|
|
|
||
A = <X,Y,U; |
р(и',у/и,х)>, |
|
|
|
|
(0.3.1) |
||
ВВЕДЕНИЕ
|
17 |
|
|
|
|
|
|
где X, У, U — |
конечные или счетные множества соот |
||||||
ветственно |
входных символов, выходных символов (букв) |
||||||
и состояний |
автомата; |
|
|
|
|
||
р{и', у/и, х) |
|
|
|
|
(0.3.2) |
||
—• условная |
вероятность того, что автомат, будучи в со |
||||||
стоянии |
u(u^U), |
при подаче на вход буквы |
х(х^Х) |
||||
выдает |
на выход |
букву у(у^У), |
переходя |
одновременно |
|||
в состояние u'(u'^U). |
При этом функция |
(0.3.2) |
должна |
||||
удовлетворять очевидным условиям |
|
|
|||||
р(и',у/и,х)^0 |
|
при |
всех и ' е ( / |
и (/еУ; |
|
(0.3.3) |
|
|
|
|
|
|
|
|
(0.3.4) |
Начальные условия вероятностного автомата определя
ются |
распределением вероятностей |
начального состоя |
||
ния |
рт(и) |
на множестве состояний |
u^U, |
причем оче |
видно, что |
|
|
|
|
|
|
|
|
(0.3.5) |
Содержательное функционирование |
вероятностного |
|||
автомата состоит в следующем. В начальный момент вре
мени |
^ = 0 известно |
распределение вероятностей началь |
|
ных состояний автомата |
рт(и). |
||
На |
вход вероятностного автомата в дискретные |
||
моменты времени |
|
|
|
/ = 1 , 2 , 3 , . . . , Л Г , |
|
(0.3.6) |
|
подается некоторая |
последовательность |
||
X1X2X3 ... Xjv • • • |
|
(0.3.7) |
|
из множества входных символов X. Автомат работает потактно, т. е. в каждый дискретный момент времени выдает на выход некоторый символ у из множества выходных символов У и переходит одновременно в новое состояние u'^U в соответствии с функцией условной ве роятности (0.3.2). Таким образом, после прохождения N тактов на выходе автомата получается последователь ность
У\УгУз . • • Уп |
|
(0.3.8) |
и автомат находится в состоянии Un- |
|
|
2 — 2014 |
Г О С . П У Б Л И Ч Н А Я |
|
НАУЧ; |
••• иЧЕСКАЯ |
|
Б И Б Л И О Т Е К А С С С Р
ВВЕДЕНИЕ
18-
Вдальнейшем алгоритмы поиска будут рассмотрены как вероятностные автоматы. При этом будет показано, что различные классы поисковых алгоритмов представ ляются как различные вероятностные автоматы.
НЕКОТОРЫЕ ТИПЫ ВЕРОЯТНОСТНЫХ АВТОМАТОВ
Вероятностный автомат типа Мили [21, 22, 24]. Вероятностный автомат является вероятностным ав томатом типа Мили, если для условной плотности веро
ятности (0.3.2) |
выполнено |
условие |
|
р {и', у/и, x)=pi |
(и'/и, х) р2 |
(у/и, х), |
(0.3.9) |
т. е. последующее состояние, в которое переходит ав томат u'^U, не зависит от выхода автомата y^Y, а вы ход у не зависит от состояния, в которое переходит авто мат для любого значения входа х е Х автомата и для любого состояния автомата u^U. Это означает, что вы ход автомата и его состояние не зависят друг от друга. Они определяются лишь значениями входа и предыду щего состояния.
Вероятностный автомат типа Мура [21,22,24]. Вероят ностный автомат является автоматом типа Мура, если всюду, где
р(и'/и,х)ф0, |
(0.3.10) |
выполнено соотношение |
|
p(ylu,x,u')=p(y/u'), |
(0.3.11) |
следовательно, если выход автомата зависит только от его состояния и не зависит от входа. Таким образом, для вероятностного автомата типа Мура имеем
р {и', у/и, |
х)=р |
(и'/и, х) р (у/и'), |
(0.3.12) |
|
т. е. такой автомат является частным |
случаем автомата |
|||
Мили. |
|
|
|
|
Автомат |
со |
случайными |
реакциями |
[21, 25]. Вероят |
ностный автомат называется автоматом со случайными реакциями (с детерминированной функцией переходов), если он является автоматом типа Мили и условная веро ятность р{и'/и, х) принимает только два значения: 0 и 1.