ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 19.06.2024
Просмотров: 173
Скачиваний: 0
ГЛАВА I
38 |
; |
• |
функционирование этого автомата в случайной среде, имеет вид
|
1-р |
р |
(1.1.5) |
|
R+ |
О |
1 |
||
|
где р — вероятность отыскания решения, удовлетворяю щего поставленным целям управления ( Q ^ q ) . Эффек тивность функционирования гомеостата существенно зависит от величины р . Чем больше р , тем быстрее нахо дится решение и, следовательно, тем эффективнее работа гомеостата.
Стохастический характер данного автомата определя ется двумя факторами — оператором случайного шага Е и неопределенностью среды (стохастичность среды за висит от неизвестного вектора ситуации Е ) .
Применение описанной схемы слепого поиска к опти мизации многопараметрических систем не приводит к успеху. Это связано с тем, что для более или менее сложных объектов управления вероятность р отыскания цели «сразу» очень мала, и процесс слепого поиска не обходимого управления связан, как правило, с огром ными затратами времени.
Рассмотренный алгоритм случайного поиска (1.1.3) пригоден для отыскания решения в принципе, т. е. гаран тирует конечность времени отыскания условий, удовлет воряющих целям управления. Однако вопросы быстро действия не решаются этим алгоритмом, поскольку он предназначен для управления объектами самого широ кого класса с единственным ограничением, связанным с конечностью вероятности отыскания решения.
В задачах экстремального управления часто содер жатся дополнительные сведения об объекте, например о характере поведения показателя качества объекта при различных управлениях. Эта информация дает возмож ность применить новые алгоритмы управления, которые построены на базе случайного гомеостатического поиска, но решают вопросы быстродействия уже с учетом имею щихся дополнительных сведений об объекте.
Дополнительные сведения об объекте оптимизации не сет функция качества Q(X), которую нужно минимизи ровать. Значение Q(X) очень часто может служить ме рой близости к цели, т. е. мерой успеха поиска.
ПОИСК БЕЗ САМООБУЧЕНИЯ
39 |
|
|
|
|
|
|
Сформулируем |
один |
из а л г о р и т м о в |
|
с л у ч а й |
||
н о г о п о и с к а , |
который |
основывается на |
высказанных |
|||
соображениях: |
|
|
|
|
|
|
|
при |
Ri~, т.е. если |
A Q i ^ O ; |
(1.1.6) |
||
|
при |
Ri+, |
т. е. если |
A Q t < 0 , |
||
|
|
|||||
где ДХг — рабочее смещение на £-м шаге, а случайные пробы 3 предполагаются достаточно малыми по мо дулю, чтобы обеспечить достаточно большую вероят ность достижения подцели. Нетрудно заметить, что этот алгоритм является дифференциальным аналогом гомеостатического алгоритма и обычно называется алгорит мом случайного спуска или случайным поиском с линей ной тактикой. Смысл его прост и естествен. Система де лает случайные шаги в пространстве управляемых пара метров, пока не будет найден такой шаг, который при ведет к уменьшению функции качества. Положительная реакция алгоритма заключается в движении по выбран ному направлению, т. е. в повторении этого шага до тех пор, пока показатель качества не начнет увеличи ваться, что вызовет отрицательную реакцию — случай ные пробы новых направлений и т. д.
Эффективность такого алгоритма поиска гарантиру ется условием небыстрого изменения функции Q(X), со гласно которому успех в X] может повториться в Х2 , если расстояние между Х[ и Х2 не очень велико. На этом ос новании в алгоритме (1.1.6) предусмотрены повторные шаги в выбранном направлении.
Рассмотрим работу этого алгоритма как стохастиче ского автомата в случайной среде, которая в данном слу чае представлена объектом оптимизации. Направленный
граф работы такого автомата показан |
на рис. 1.1.2, где |
S — оператор случайного смещения, |
a R+ — оператор |
положительной реакции. Стрелками на рисунке пред-
А0>0 ( |
(^Х^^^^ГоЛ |
\ A O i 0 |
|
fa) \ |
\tJL^ja±^XzJ |
J & |
|
|
1 |
(t-p2) |
2 ^ |
Рис. 1.1.2. Граф гомеостатического алгоритма оптимизации (линейная тактика).
ГЛАВА I
40
ставлены переходы от одного оператора к другому, при чем рядом указаны события, вызывающие эти переходы, а в скобках — вероятности этих событий. Автомат мо жет пребывать в двух состояниях и задается матрицей переходов
|
P i |
l ~ P l |
" |
|
(1.1.7) |
|
1-р2 |
Р2 |
|
|
|
где |
вероятности р{ |
и р2 зависят |
от свойств среды, т. е. |
||
от |
оптимизируемого |
объекта, |
и изменяются вместе |
||
с этим объектом. |
|
|
|
||
Нетрудно |
заметить, |
что эффективность рассматривае |
|||
мого алгоритма зависит от того, |
как часто применяется |
||||
оператор R+. |
|
|
|
||
Именно в этом цикле показатель качества уменьша ется и происходит настройка системы. Поэтому значе ние вероятности р2 в значительной мере определяет эффективность применения данного алгоритма. Алгоритм эффективен, если объект таков, что значение р2 доста точно близко к единице.
Однако эффективность алгоритма зависит и от вероят ности выхода автомата на указанный цикл, т. е. от ве личины 1— ри которая соответствует вероятности слу чайного определения удачного направления (AQ<0) . Достаточно большое значение этой величины обеспечи вает работоспособность алгоритма.
Таким образом, для эффективной работы алгоритма
случайного |
поиска (1.1.6) |
необходимо, |
чтобы объект оп |
||||
тимизации |
удовлетворял |
следующим |
требованиям: |
||||
1) значение рх не должно быть очень малым, 2) |
значе |
||||||
ние р2 должно быть велико. |
с л у ч а й н о г о |
по |
|||||
Рассмотренный |
а л г о р и т м |
||||||
и с к а построен |
н а п р и н ц и п е |
« н а к а з а н и я » |
с л у |
||||
ч а й н о с т ь ю , в |
соответствии с которым оператор слу |
||||||
чайного шага S вводится как отрицательная реакция на |
|||||||
неудачу при отыскании подцели. В случае удачи |
поиск |
||||||
осуществляется |
тем же |
способом, |
который |
привел |
|||
к удаче. Такая форма поведения, безусловно, разумна и целесообразна для линейных и близких к ним объектов, свойства которых с переходом из одного состояния в дру гое изменяются незначительно.
.Именно поэтому автомат, реализующий подобный ал-
ПОИСК БЕЗ САМООБУЧЕНИЯ
41
горитм, называется автоматом с линейной тактикой [39]. Если же условие линейности объекта не выполняется и
вероятность р2 мала, то рассмотренный линейный |
алго |
||
ритм поиска имеет ограниченное применение. |
|
||
Объекты, для которых вероятность |
р% мала, |
часто |
|
бывает |
целесообразно оптимизировать, |
применяя |
а л г о |
р и т м |
с н е л и н е й н о й т а к т и к о й . В этом алгоритме |
||
отрицательная реакция R~ заключается в регулярном |
|||
«исправлении» ошибок, т. е. каждый |
раз принимаются |
||
меры для того, чтобы устранить последствия неудачи. Этот алгоритм можно записать в следующем виде:
(1.1.8)
Оператор случайного шага S здесь вводится как поло жительная реакция R+ на удачный шаг, который привел к уменьшению функции качества AQ<0 . Отрицательная реакция R~ вызывает действие, направленное на прео доление полученного отрицательного эффекта (AQ>0), после чего снова следует случайный шаг Н. Таким обра зом, работоспособность этого алгоритма поиска дости гается исправлением ошибок, допущенных в процессе случайных проб.
Граф алгоритма показан на рис. 1.1.3. Матрица пере ходов графа имеет вид
где р — вероятность случайного удачного шага (р = р\). Очевидно, что для эффективной работы этого алгоритма объект вовсе не обязан обладать свойствами «гладкости». Единственное условие, предъявляемое алгоритмом к объ екту, заключается в том, чтобы вероятность р была не очень мала.
AQ>0
AQ<0
(Р)
Рис. 1.1.3. Граф алгоритма случайного поиска с нелинейной тактикой.
42 ГЛАВА I
Рассмотренные выше алгоритмы случайного поиска являются стохастическими автоматами, переходные мат рицы которых определяют "статистические свойства опе ратора случайного шага, которые в процессе поиска оста ются неизменными. Естественно использовать возмож ность изменения вероятностных свойств оператора Н для целенаправленного воздействия на переходные вероят ности, чтобы повысить эффективность указанных алгорит мов. Данную задачу решают а л г о р и т м ы с а м о о б у ч е н и я, т. е. способы перестройки статистических свойств оператора Е, основанные на предыстории поиска. Такое самообучение вносит в поиск дополнительную обратную связь и является реакцией более высокого порядка на по ведение объекта в процессе поиска, чем R+ или R~.
Таким образом, можно утверждать, что алгоритмы случайного поиска являются вероятностными автоматами, адаптация которых производится путем введения само обучения в процессе их функционирования.
§1.2. П Р Е Д С Т А В Л Е Н И Е
С Л У Ч А Й Н О Г О П О И С К А В В И Д Е В Е Р О Я Т Н О С Т Н О Г О А В Т О М А Т А
В предыдущем параграфе показано, что ал горитмы случайного поиска могут рассматриваться как простейшие вероятностные автоматы, имеющие два со стояния — случайный шаг S и реакцию R на результат этого случайного шага. В данном параграфе эта точка зрения расширяется и обобщается, что позволяет не только привлечь теорию вероятностных автоматов к ис следованию работы алгоритмов случайного поиска, но и построить новые алгоритмы.
Начнем с определения исходных понятий, точнее, с установления связи между понятиями теорий поисковой оптимизации и вероятностных автоматов. Эта связь отражена в таблице 1.2.1.
Рассмотрим алгоритм случайного поиска с ограничен ным, т. е. конечным, числом т возможных направлений движения в пространстве оптимизируемых параметров.
