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

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

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

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

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

Добавлен: 19.06.2024

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

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

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

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

49

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

|

ЛХ<_Ь

если

A Q V i ^ O ;

1

I 3,

если

A Q V i > 0 ,

где S — случайный вектор из множества (1.2.1).

В случае штрафа (AQ'>0, т. е. с—\) матрица А{ сов­ падает с (1.2.5) и соответствует случайному шагу, т. е. равновероятному выбору одного из m возможных на­ правлений. При «нештрафе» (AQ'^O, т. е. с = 0) мат­ рица А0 — единичная, что соответствует повторению предыдущего шага. Таким образом, матрица переход­ ных вероятностей алгоритма случайного спуска в про­ цессе оптимизации имеет вид (1.2.18), где

1 — SiН

,

если

t = ;;

 

агр =

 

m

 

(1.2.25)

 

 

 

 

 

St

 

 

 

. . .

 

m

,

если

1ф].

 

 

§ 1.3. Л И Н Е Й Н Ы Й А Л Г О Р И Т М

 

 

С Л У Ч А Й Н О Г О П О И С К А

 

 

Линейные

алгоритмы случайного

поиска

характеризуются тем, что после удачного шага

(AQ'^O)

последующий шаг делается в том же направлении, а после неудачного шага (AQ'>0) выбирается новое слу­ чайное направление. В данном параграфе исследуем ли­ нейный алгоритм случайного поиска, определенный фор­ мулами (1.2.24). Для этого алгоритма матрица переход­ ных вероятностей при нештрафе ( A Q ' ^ 0 ) имеет вид [42]

1 0 0 . . 0 0 0

0 1 0 . . 0 0 0

0 0 0 . . 0 1 0

0 0 0 . . 0 0 1

4 — 2014

ГЛАВА I

50

апри штрафе (Д<2'>0)

тт

(1.3.2)

_1_

тт

где m = 2 n .

Далее предположим, что в процессе поиска вероят­ ности штрафов Si ( t = l , . . . , m ) постоянные. Это имеет место, например, для линейной функции Q(X) . Тогда функционирование автомата описывается простой одно­ родной цепью Маркова со следующей матрицей переход­ ных вероятностей (см. формулу (1.2.25)):

 

bi

ai

ах

а2

 

а2

 

а2

 

а2

«2

Л(Б) =

 

 

 

 

 

(1.3.3)

 

От—1

й т - 1

&гп-\

й т - 1

Ьт-\

С1т-\

 

О-т

&т

&т

dm

dm

Ьт

где

 

 

 

 

 

 

di=- т

bi=\

— Si

+ т

 

 

(1.3.4)

По этой матрице с учетом (1.3.4) и (1.2.17) видно, что для афО цепь Маркова является эргодической. Поэтому вектор предельных вероятностей Р—(ри...,рт) явля­ ется решением системы уравнений

P=4'(S)P ,

(1.3.5)

где A'(S) — транспонированная матрица (1.3.3). Ре­ шая эту систему, находим

b\ — a\—l

S\

b2 — a 2 - l

s2

(1.3.6)

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

51

Ъ\ — ах

— 1

S i

 

 

P m = T

 

 

ГР1=—ри

 

ит

dm

I

Sm

 

 

После нормировки pi ( i = l

m)

имеем

Pi^~S*

 

 

 

 

(1.3.7)

Si

 

 

 

 

 

( i = l , . . . , m ) ,

 

 

 

где

m

 

 

 

 

 

 

 

 

 

s * - ( 2 t ) ~ 1 -

 

 

( L 3 - 8 )

 

3=1

'

 

 

 

Предельный средний штраф

равен

P c p = mS*.

 

 

 

(1.3.9)

Можно

показать, что имеет место

неравенство

0<Pcv<~

.

 

 

 

(1-3.10)

причем при сг->-оо рС р->-^- и при а->0 рС р->0. Следова­ тельно, рассмотренный автомат, соответствующий ли­ нейному алгоритму случайного поиска, обладает целе­ сообразным поведением в процессе оптимизации при на­ личии помехи с ограниченной дисперсией.

Пронумеруем направления смещения ДХ( г ) в прост­ ранстве X следующим образом:

ДХ<1>=( + 1, ... ,+1) ;

Д Х ( 2 ) = ( + 1 , . . . ,

+ 1

, - 1 ) ; ДХ<з> =

= ( + 1 , . . , , + 1 , - 1 , + 1 ) ;

ДХ<«>=(+1, ... , + 1 ,

- 1 , - 1 ) ; . . . ;

ДХ<™/2-» =

( + 1,

- 1 ,

. . . , - 1 , +1) ;

\ дх<"^)= ( + 1 , - 1 , . . . , - 1 ) ;

ДХ<™/2+» = -ДХ(*>

 

 

 

 

(1.3.11)

 

( '

• '

т )

-

Тогда средний вектор смещения в пространстве X будет равен

4*

ГЛАВА I

52

Л * [ Д Х ] = [(

Sm — Sm/2 ^

SmSjn'2 '

Sm/4+2 Sm/4

Srn/4s m/4+m/2

S m — S m / 2 \ С И

^

S i + m / 2 — S i

X

S i S i 4 - m / 2

S m /4+n - m / 2 Sm/4+1 S T O , 4 + i S m / 4 + i - ) - m / 2

!/ S i + m / 2 — S i

 

Sm.Sw.r2

'

N

SiSi+m/2

 

S2 +m/2 — S 2

 

S 3 + m / 2 — S3

 

 

S2S2 +m/2

 

s 3 S 3 + m / 2

 

 

S4+m/2 S4

 

S m

S m / 2

) S*] ,

(1.3.12)

S4S4+TO/2

 

 

Smr&m

 

 

 

 

где 5* определяется

формулой (1.3.8). Среднее измене­

ние показателя

качества

 

 

 

M[AQ] = S*\ S

l + w / 2 ~ 5

'

( a i + a 2 + - + a n ) +

 

LSiSi+ T O /2

,S 2 + T O /2 — S 2

 

 

 

S2S2+m/2 - ( « 1 +

+ a n - i — a n ) +

 

 

 

 

S3+m/2~S3

••• +an-2 — C t n - l + a n )

+

 

 

 

S3S3+m /2 ( « 1 +

 

 

S4+m/4 — S 4

( a H

han-2 — a n - i — ctn) 4 Ь

 

 

 

S4S4+m/2

 

 

 

 

 

 

 

 

,

Sm—1

STO/2—1 ,

 

.

 

 

H

 

 

 

(ai— ••• - a n - i + a n ) +

 

 

 

 

Sm—lSm/2—1

 

 

 

 

.

S m Sm/2

(a,

a„)] ,

 

(1.3.13)

 

 

 

SjnfeSn

 

 

 

 

где

a i 2

= l

(напомним, что ai

— направляющие

i=l

 

 

 

 

 

 

 

косинусы

градиента).

 

 

 

С л у ч а й

б е з

в о з д е й с т в и я

п о м е х и

необхо­

димо

рассмотреть

отдельно. Предположим, что направ­

ление

градиента

функции

Q(X) удовлетворяет

условиям

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