ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 164
Скачиваний: 0
ГЛАВА III
330
Как видим, это задача нелинейного программирования. Однако несложный анализ линий равного уровня сред него штрафа
с(РиР2) |
= |
const |
|
|
|
(3.4.44) |
||
показывает, |
что они |
являются |
прямыми. |
Это |
обстоя |
|||
тельство |
гарантирует |
решение |
задачи (3.4.43) |
на |
гра |
|||
нице области 0^.ри |
/ ? 2 ^ 1 - |
что |
делает |
оптимальную |
||||
стратегию |
чистой. |
|
|
|
|
|
|
|
Сказанное |
позволяет сделать |
вывод |
о том, |
что |
двойная рандомизация, рассмотренная в этом пара графе, по-видимому, не может повысить быстродействия поиска.
§ 3.5. В Ы Б О Р О П Т И М А Л Ь Н О Й
ПО С Л Е Д О В А Т Е Л Ь Н О С Т И
АЛ Г О Р И Т М О В П О И С К А
Вэтом параграфе, используя подход, изло
женный в работе [55], построим оптимальную последова тельность алгоритмов поиска. Пусть имеется набор т алгоритмов (стратегий), предназначенных для поиска экстремума функции Q(X). Пусть каждый алгоритм об ладает определенным набором операторов, которые при мем за состояния автомата. Пусть также заданы вероят
ности |
переходов рц^ |
из состояния i в состояние / (/ = |
|||||
= \,...,п) |
и соответствующие |
смещения в цели (доходы) |
|||||
сц{к) |
для каждого |
алгоритма |
(k=l,...,m), |
причем |
|||
строки |
(состояния) |
матрицы |
Pijlh) |
удовлетворяют усло- |
|||
|
|
|
|
п |
|
|
|
виям |
стохастичности |
^ P a w |
= 1 и 0^рц{к)^ |
1. Необхо- |
|||
|
|
|
|
3=1 |
|
шагов (переходов) N |
|
димо для всех состояний i и всех |
|||||||
(Л/ = 1, 2, 3,...) |
выбрать такую последовательность алго |
||||||
ритмов, |
которая |
бы максимизировала среднее |
смещение |
||||
к цели |
|
(доход). |
|
|
|
|
|
Для решения поставленной задачи оптимизации применим «принцип оптимальности» динамического про-
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
331
граммирования марковского типа, предложенный Р. Беллманом [56] и использованный Р. Ховардом [57] для ре шения определенных задач.
Приведем некоторые результаты работ [56—57], кото рые нам понадобятся в дальнейшем. Среднее смещение к цели (доход) для k-ro алгоритма на (УУ+1)-М переходе при условии, что система находится в £-м состоянии, равно
|
|
|
п |
|
|
|
|
|
|
|
stW(N+l) |
|
= ^jOij - w i d j - C J |
+ S j - w ^ ) ] . |
|
(3.5.1) |
|||||
Таким образом, средний доход в £-м состоянии |
получа |
|||||||||
ется |
путем |
осреднения |
|
случайной |
величины |
C j j ( f e ) + |
||||
+ Sjw(N) |
по всем состояниям /. Здесь |
C;;<ft> |
— доход при |
|||||||
переходе |
из |
состояния i в состояние / — в |
соответствии |
|||||||
с k-м алгоритмом; Sj(N) |
— |
средний |
доход, |
получаемый |
||||||
в состоянии / за оставшиеся N шагов. |
|
|
|
|||||||
Обозначим через di(N) |
номер |
алгоритма, |
выбираемый |
|||||||
в состоянии |
i на N-м шаге. Тогда |
оптимальной считается |
||||||||
такая |
последовательность |
di(N), |
которая |
максимизи |
||||||
рует средний доход для всех i и N: |
|
|
|
|||||||
|
|
|
|
|
|
п |
|
|
|
|
SiW(N+l)= |
max [g,№) + |
2 |
Pulh)Si(N)] |
, |
(3-5.2) |
где g^h) — непосредственно ожидаемый доход в момент выхода системы из состояния i по алгоритму k;
п |
|
g i W = 2J Pij{h)cii{h)- |
(3-5.3) |
j=i |
|
Решая рекуррентное выражение (3.5.2), находим опти мальную последовательность dt(N).
Для облегчения вычисления вектора s(N), а также для удобства теоретических выкладок и исследования поведения системы в переходный период применяется метод производящих функций (Z-преобразований) [57].
Так, например, после применения |
Z-преобразования |
|
вектор |
|
|
S(N+l)=g |
+ PS(N) |
(3.5.4) |
ГЛАВА III
332
запишется в виде |
|
|
|
W(Z) = -^-I(I-ZP)->g+ |
|
(/ - ZP) - 'S(O), |
(3.5.5) |
где |
|
|
|
W ( Z ) = ]?S(N)ZK |
. |
|
(3.5.6) |
лг =о |
|
|
|
Обратное преобразование вектора W(Z) дает искомый вектор S ( N ) . Для некоторых алгоритмов случайного по иска этот вектор вычислен в работе [58].
При больших N вместо (3.5.1) имеем следующую сис тему уравнений:
|
|
|
k |
|
|
|
|
|
|
|
t + V i = g i |
( k ) + |
J3=1£P i j m V j |
|
|
|
(3.5.7) |
||||
|
|
|
|
(i=l,...,N). |
|
|
|
|
|
|
Здесь |
Vi называется относительным |
весом |
[57], t |
— до |
||||||
ходом |
процесса. |
|
|
|
|
из п |
|
|||
Так |
как система |
уравнений |
(3.5.7) |
состоит |
урав |
|||||
нений |
с |
п+1 |
неизвестным |
(неизвестны |
t |
и |
\ч |
(i = |
||
= 1, ... ,я)) , то |
одно из V, полагают |
равным |
нулю, что, |
|||||||
как показано в работе [57], не влияет |
на определение оп |
|||||||||
тимальных di. Вся процедура определения |
оптимальных |
|||||||||
d{ при больших N сводится |
|
|
|
|
|
|
||||
а) к |
|
решению |
системы уравнений (3.5.7) |
относи |
тельно м;
б) к нахождению для каждого состояния i стратегии di, для которой имеет место
п п
g i ( d ' ) + ^ P i j ^ v j = |
max ( g i ( f |
t ) + £ |
Pij(k)v3) |
; |
|
|
3=1 |
h |
3=1 |
|
(3.5.8) |
|
|
|
|
|
|
в) |
к замене в формуле (3.5.8) |
g^h) |
на gi(di\ |
a Pij( f t ) на |
|
Pij ( d i' |
и к повторному |
решению |
системы (3.5.7). |
При этом от итерации к итерации доход t увеличива ется, т. е. получается улучшение решения. Остановка
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ
ззз
процесса производится при двухразовом совпадении век тора di, который в дальнейшем принимается за опти мальный. Причем оптимальному вектору di соответст
вует максимальный доход t. |
|
П р и м е р . Рассмотрим линейную |
модель |
Q(X)=ATX, |
(3.5.9) |
где Т — знак транспонирования. Пусть каждое измере ние функции Q(X) сопровождается нормально распреде ленной независимой помехой е(о) с нулевым математи ческим ожиданием и дисперсией а2 /2, т. е.
Q ' ( X ) = Q ( X ) + e ( a ) . |
(3.5.10) |
В качестве алгоритмов оптимизации рассмотрим сле дующие алгоритмы случайного поиска с «поощрением» случайностью:
а) алгоритм с возвратом при неудачном шаге, для ко торого матрица вероятностей переходов Р и матрица смещений С записываются в виде [58]
(3.5.11)
б) тот же самый алгоритм с применением процедуры накопления; тогда в каждой точке Xs имеем
|
г |
|
Q'(XS )=Q(X.S ) + y]£et |
(Г = 2 , 3 , . . . ) . |
(3.5.12) |
В этом случае матрицы Р и С принимают |
следующий |
|
вид: |
|
|
ГЛАВА III
334
W { T , r ) [ c - o ( ^ ) ]
с=
l + W(T
(3.5.13)
Здесь |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Ф(х) |
Лг |
[ |
e-t'dt; о*2 = |
— ; |
0 < \ Г ( Г , |
г ) < 1 ; |
|
|||||
|
|
1'я |
{ |
|
|
|
Т |
|
|
|
|
|
|
J V Q | |
— модуль градиента. |
|
|
|
|
|
|
|
|||||
|
Функция |
W(T,r) |
учитывает число |
наблюдений |
Т в |
||||||||
•(3.5.12) и стоимость г каждого наблюдения |
Q. |
|
|
||||||||||
|
Пусть № ( 7 » |
= (HT)W(r). |
Примем, что |
W{r) |
моно |
||||||||
тонно |
убывает |
с |
возрастанием |
г. |
Множитель |
(1 + |
|||||||
+ |
W(T,r))/2 |
появляется |
вследствие |
равенства |
количе |
||||||||
ства наблюдений над Q(X) при переходе |
рц и |
перехо |
|||||||||||
дах р]2 + Р2\- Количество |
наблюдений |
при |
переходах |
р\2 |
|||||||||
и |
рч\ |
также |
принято |
равным. |
Положим |
| V Q | = 1; |
|||||||
W(T, |
г) =2/3; а = 2; |
Т = 4. |
Тогда |
о.2 |
= о2/Т=1. |
Пусть |
|||||||
также |
Сц = 1. |
Тогда |
выражения |
(3.5.11) |
и |
(3.5.12) |
|||||||
можно будет переписать в виде |
|
|
|
|
|
|
|||||||
|
|
1 |
1 |
|
|
|
0,85 |
-1,15 |
: |
|
|
|
|
|
|
~2~ |
~2 |
|
|
|
|
(3.5.14) |
|||||
|
|
|
|
|
|
|
|
|
|
||||
|
|
1 |
о |
|
|
|
0,85 |
|
0 |
! |
|
|
|
|
|
|
1 |
|
|
2 |
•0,92 |
--•1,08 |
|
|
|||
|
-Р2 = |
~2~ |
с 2 = |
У |
|
|
6 |
|
|
(3.5.15) |
|||
|
|
1 |
о |
|
|
5 •0,92 |
|
0 |
|
|
|
|
|
335 |
ОПТИМАЛЬНЫЕ АЛГОРИТМЫ |
|
|||
|
|
|
|
|
||
|
|
|
|
Т а б л и ц а 3.5.1 |
||
Состояние |
i \ Стратегия k |
|
2 |
|
||
Критерий g { h +2PijhVj |
||||||
|
1 |
|
||||
|
|
|
/=1 |
|
||
|
|
1 |
-0,15+0,5-0,65 = 0,17 |
|||
' |
1 2 |
-0,12 + 0,5-0,65 = 0,2 |
||||
2 |
|
1 |
|
0,85 |
|
|
|
2 |
|
0,8 |
|
||
|
|
|
|
|||
Рассмотрим |
алгоритм |
с возвратом и матрицами (3.5.14) |
||||
и (3.5.15). Будем считать, что число переходов N велико. |
||||||
Чтобы |
начать процесс |
последовательных |
решений, по |
|||
ложим ^ = 0; |
vi = v2 = 0. |
Тогда из |
(3.5.7) |
g i ( 1 ) = — 0,15; |
||
g,<2> = -0,12; |
g2 <i)=o,85; |
g2 ( 2 ) =0,80. |
Отсюда maxgi<fc> = |
|||
|
max g 2 { h ) = 0,85. |
|
|
ft |
||
= —0,12; |
Следовательно,• в |
первом со- |
||||
|
h |
|
|
|
|
стоянии необходимо выбрать вторую стратегию, а во вто ром состоянии — первую. Новая матрица, соответствую щая этому решению, должна состоять из первой строки матрицы Р2 (3.5.15) и второй строки матрицы. Р[ (3.5.14). Так как матрицы Я, (3.5.14) и Р2 (3.5.15) оди наковы, то вновь получим матрицу Pi (3.5.14).
Теперь записываем систему уравнений (3.5.7), в кото рой использованы элементы матрицы Р\ (3.5.14) и ко-
II |
-0,12 |
|
ординаты вектора g= \ \ |
о 85 j | > т -е - |
|
/ + vi = -0,12 + 0,5vi + 0,5v2; |
(3 5 16) |
f + v2 = 0,85 + vi.
Например, при vi = 0 получим \'2 = 0,65 и доход |
/ = 0,2.. |
||||
Возвращаясь |
к процедуре (3.5.8) при vi = 0, v2 |
= 0,65,. |
|||
имеем таблицу |
3.5.1. Из данных таблицы |
можно |
заклю |
||
чить, |
что в первом состоянии |
необходимо |
выбрать вто |
||
рую |
стратегию, |
а во втором |
— первую. Эти стратегии |
совпадают со стратегиями, полученными на предыдущем шаге, значит, процесс сошелся и доход t достиг своего