Файл: Растригин Л.А. Автоматная теория случайного поиска.pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.06.2024

Просмотров: 177

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

ПОИСК БЕЗ САМООБУЧЕНИЯ

43

 

 

 

 

Т а б л и ц а 1.2.1

Теория

поисковой

оптимизации

Теория вероятностных автоматов

Объект

 

 

Среда

 

Оптимизатор, работающий по ме­ Вероятностный автомат

тоду случайного

поиска

 

 

Реакция объекта

 

Входной алфавит автомата

 

 

 

С = ( 0 , 1 )

(с=0)

AQ'scO

 

 

нештраф

AQ'>0

 

 

штраф (с=1)

ДХ Ь ДХ2 , ь

. . , Д Х т

 

Выходной

алфавит автомата

Состояние

объекта

?)

Состояние

среды

r-ero-(f-

S = ( s i , . . . , sm)

 

 

 

 

\ oxi

дх„!

 

 

Будем рассматривать сначала покоординатный поиск, когда вдоль координатных осей равновероятно делаются единичные шаги в обоих направлениях

А Х = ( ± 1 , ± 1 , . . . , ± 1 ) .

(1.2.1)

Очевидно, что в этом случае т четно. Определим индексы следующим образом:

AXH)=-kX(i+ml2)

( 1 - 2 . 2)

( ) •

„ т

т. е. шаги с индексами, различающимися величиной-^- ,

равны по модулю и противоположно направлены. Покажем теперь, как некоторые описанные ранее ал­

горитмы покоординатного поиска записываются в тер­ минах теории автоматов.

ГЛАВА Г

44

Нелинейный алгоритм случайного поиска:

f

Н, если

A Q V i ^ O ;

* 1

R, если

A Q V J X ) ,

где

A Q V ^ Q ^ X i - O - Q ^ X ^ )

(1.2.3)

и Х*_, = Х М + ДХ1_,.

(1.2.4)

Здесь

S

— оператор

случайного

шага, который

пред­

 

 

ставляет

собой

равновероятный

выбор из

 

R

т — 2п возможностей

(1.2.1);

 

 

 

— оператор

реакции на AQ'> 0 (напомним,

 

 

что рассматривается случай минимизации).

 

 

Пусть для конкретности R выражает

опера­

 

 

цию возврата в

исходную точку,

т. е. Ri =

 

 

= - Д Х ( _ , .

 

 

 

пока­

Блок-схема оптимизации по этому алгоритму

зана

на

рис. 1.2.1, а. Здесь П

—

блок памяти

предыду­

щего значения показателя качества; ИМ —• исполнитель­ ный механизм, выполняющий операцию (1.2.4); бук­ вой S обозначен генератор случайных шагов.

Заметим, что данный алгоритм не тождествен опи­ санному в работе [1]: в последнем после возврата необхо­ димо следует случайный шаг, в алгоритме же (1.2.3) реакция R может повторяться, если повторяется нера­ венство AQ'>6 .

Теперь сформулируем этот алгоритм в терминах функ­ ционирования вероятностных автоматов [39].

Вероятностный автомат, описывающий указанный ал­ горитм случайного поиска, оперирует двумя стохасти­ ческими матрицами, соответствующими двум реакциям

среды

(штраф и нештраф). Нештрафу

(с = 0) соответст­

вует

стохастическая матрица

выбора

случайного

шага

АХ:

 

 

 

(1.2.5)

А0=\\рц\\

 

 

 

( г , / = 1 , . . . , т ) ,

 

 

 

где

1

 

 

 

 

 

 

(1.2.6)

 

 

 

 

Штрафу ( с = 1 ) соответствует

нестохастическая

мат­

рица

реакции

 

 

 

ПОИСК БЕЗ САМООБУЧЕНИЯ

 

 

45

 

 

 

 

 

^ i = llfl«ll

 

 

 

 

(1.2.7)

( t ' , / = l , . . . , m ) ,

 

 

 

 

 

где

 

 

 

 

 

1 при

2

 

 

 

 

т

( .

т .

\

(1-2.8)

 

 

~2

( i = — +

1 , . . . , т ] ;

 

 

\ '

2

 

 

О при остальных значениях i,

/.

 

Иначе говоря, матрица реакции состоит из четырех бло­ ков — двух единичных и двух нулевых:

Л , =

О

(1.2.9)

 

О

Нетрудно заметить, что эта матрица обеспечивает воз­ врат системы в исходное состояние при AQ'>0 .

Таким образом, вероятностный автомат, эквивалент­ ный алгоритму случайного поиска с возвратом, пред­ ставляется в виде следующей комбинации матриц:

А=(\-с)А0+сАь

(1.2.10)

Блок-схема оптимизации с применением этого вероят­ ностного автомата показана на рис. 1.2.1,6. Здесь блоке выполняет естественную операцию:

f 1, если AQ'>0;

(1.2.11)

\ 0, если AQ' 0.

Блок А\ представляет собой автомат, срабатывающий при с = 1 в соответствии с матрицей А\, т. е. реализую­ щий поведение при штрафе. Блок А0 реализует вероят­ ностный автомат Ло, т. е. образует случайный шаг S.

Заметим, что обе матрицы Ло и А\ можно

объединить

в одну следующего вида:

 

А{с) = \\сц?\

(1.2.12)

ГЛАВА I

46-

где

 

 

I . '

т\

1 + с ( / и - 1 ) I . . т

 

• / = H - T

( i = l , . . . , T ) ;

 

при

 

 

 

1 - е

1 = 1 -

 

 

 

при остальных значениях i, у.

 

l m

 

 

 

 

(1.2.13)

 

 

 

 

а) г '

 

 

 

1

 

Объект

 

 

 

 

О,-

 

 

 

 

 

да

 

 

 

АХ;

 

 

 

 

Случайный

нет

 

 

 

шаг

 

 

 

б)

им

к-

4-1

 

05ъе>'кт

Рис. 1.2.1. Блок-схема оптимизации:

а — с алгоритмом случайного поиска; б — с применением вероят­

ностного автомата.

ПОИСК БЕЗ САМООБУЧЕНИЯ

47

Обе схемы на рис. 1.2.1, а и б работают строго иден­ тично. Поэтому дальнейшее изучение поведения системы оптимизации, работающей по алгоритму случайного поиска (1.2.3), можно производить с привлечением аппарата теорий вероятностных автоматов.

Среда в этой теории описывается

вектором

S = ( s b s 2 , , , . , s m ) ,

(1.2.14)

где Si — вероятность штрафа (с=1) при ДХ = ДХ<*>.

При отсутствии помех в определении приращения показателя качества получаем

AQi=(AXugradQ(X)),

(1.2.15)

и вероятность штрафа ( A Q ^ > 0 )

равна

S i = sgnAQ(*>

 

(1.2.16)

где

 

 

sgn z = { 1 -

если z>0;

 

О, если 2=^0.

 

При наличии нормальных некоррелированных помех, накладывающихся на показатель качества, получаем более общую формулу:

где Ф(г) — интеграл вероятности; а2 — дисперсия нормальной помехи;

Ф ( * ) = - / e-*ldt.

Очевидно, что с изменением градиента показателя качества вектор S будет также изменяться.

Далее, для полного описания функционирования сис­ темы случайного поиска как вероятностного автомата необходимо установить связь между поведением внеш­ ней среды и действиями автомата, т. е. замкнуть цепь обратной связи. Для этого в формулу (1.2.13) вместо коэффициента с подставим вероятность штрафа при £-м действии автомата, т. е.

ГЛАВА I

48-

 

 

 

l+Si(m-l)

I . . m

I . л

m\

при

( t ' = f - + 1 - . . . , m ) ;

m

при остальных значениях г, j .

(1.2.18)

 

Тогда процесс оптимизации случайным поиском описы­ вается простой цепью Маркова со следующей матрицей переходных вероятностей (см. § 0,4):

A(S)

= (I-S)A0+SAu

 

(1.2.19)

здесь

Л о и А г — матрицы

(1.2.5) и (1.2.7) соответст­

 

 

I

венно;

 

 

 

 

— единичная

матрица;

 

 

5

— диагональная матрица

 

5i

0

0 . . .

0

0

 

0

s2

0 . . .

0

0

5 =

 

 

 

 

(1.2.20)

 

О О О

Sm-l

О

 

О О О

0

sm

где Si — вероятность штрафа при i-м действии автомата. Располагая этими данными и пользуясь аппаратом теории вероятностных автоматов, можно определить ста­

тистические свойства поиска. Пусть

P=(Pl,p2,...,Pm)

(1.2.21)

— вектор

предельных вероятностей

шагов AX<! >,...

. . . , А Х ( т ) .

Тогда осредненный шаг, определяющий эф­

фективность поиска, равен

 

М[АХ] - 2 PiАХ»),

(1.2.22)

а средняя вероятность штрафа

т

Рср= 2

P%Si.

(1.2.23)

Смотрите также файлы