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

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

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

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

Добавлен: 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)