книги / Системы экстремального управления
..pdfВычислим градиент функции качества в точке а:*:
grad Q = |
kq (хг — x*)q~l. |
(5.1.8) |
Тогда |
akq (л;г — х*)9-1 |
(5.1.9) |
Аж{+1 = |
||
и |
= xt + <*kq (xt — х*)^1. |
(5.1.10) |
*i+i = яг + Да;{+1 |
||
Запишем это выражение в виде |
|
|
xi+1 — х* = (xi — х*) — akq (xi — х*)<~1 |
|
|
и, разделив обе части на xt — х*, получим |
|
|
* |
|
|
——— ;—= 1 — akq fa — л;*)4"2. |
(5.1.11) |
|
X. —X |
|
|
г |
|
|
Обозначим расстояние до экстремума в точке а:,- через у с.
Vi = xi — х*. |
(5.1.12) |
Здесь y t 0 ввиду принятого предположения |
Xi^> х*. |
Тогда (5.1.11) запишется в ^более компактном виде: |
|
-& !-= 1 - |
(5.1.13) |
Очевидно, что для сходимости необходимо, чтобы (?д+1 | ■< < у и откуда получаем следующее условие:
!2щ ! = ц - < Л и И < 1 ,
которое легко приводится к виду
0< адй:уГ2 < 2 . |
(5.1.14) |
Как видно, чем меньше по модулю правая часть (5.1.13), тем быстрее сходится процесс поиска. Поэтому, чем ближе
величина aqkyt* к единице, тем интенсивнее сходимость процесса.
При q = 2, т. е. в случае, когда характеристика объ екта представляет собой квадратичную параболу, полу чаем условие сходимости в виде
При а = |
1 |
имеем |
yi+1 — О, т. е. экстремум дости |
2к |
гается за один шаг поиска. Это — самые выгодные усло вия для применения градиентного метода.
При g > 2 сходимость процесса зависит от близости
к экстремуму. Действительно, процесс |
сходится при |
2 |
(5.1.15) |
\У Г 2< aqk |
и расходится в противном случае. Как видно, для расши рения зоны устойчивости достаточно уменьшить параметр шага а.
При выполнении условия сходимости (5.1.15) процесс поиска будет идти по-разному. В случае, когда
aqk1 <|»Г1< a2qlc ?
получаем из (5.1.13)
УиVi1 < 0 ,
что означает изменение знака ?д+1 п о сравнению со зна ком yi. Здесь поиск происходит как бы с «перескоком» через экстремум.
Бели же
1
i » n < aqk 1
то система в процессе поиска приближается к экстремуму с одной стороны.
На рис. 5.1.3 для иллюстрации показаны примеры про цессов поиска при различных начальных условиях уй (показаны только рабочие шаги). Первый и второй про цессы неустойчивые, а третий, четвертый и пятый — ус тойчивые. Разница между процессами в) и г) заключается в том, что в процессе г) во время поиска был достигнут
уровень | у |ч-а = jjp, обозначенный пунктиром на рис. 5.1.3,
после чего на следующем шаге система в соответствии с (5.1.13) сразу попала в экстремум у* = 0.
При 9 = 1 объект имеет кусочно-линейную характерис тику. В этом случае длина рабочего шага постоянна и равна
независимо от расстояние до цели, т. е. рреимущества градиентного метода не используются. Градиентный ме тод работает как поиск с парными пробами (см. § 4.1).
Любопытно поведение градиентного поиска на клювообразном объекте, т. е. при 0 < ^ < 1 . В этом случае на рушается основная предпосылка, положенная в основу
Рис. 5.1.3. Примеры процессов градиентного поиска |
при g > |
2: |
|||||
2 |
|
2 |
1 |
2 |
|
|
1 |
а) I У0 1 ^ а к д * |
I Уо I |
п * 8’ 8^ |
адк |
I Уо I |
a a k > |
I У° I |
• |
|
|
адк |
|
• адк ' |
|
адк ' |
градиентного метода,— наклон характеристики не опре деляет расстояния до цели. Поэтому при работе этим ме тодом на объекте с клювообразной характеристикой вда ли от цели рабочие шаги будут малыми. G приближением к цели величина рабочего шага будет увеличиваться и при у ж 0 шаг будет настолько большим, что выбросит систему из района экстремума, т. е. расстроит объект. Это, естественно, ограничивает применение градиентного метода и позволяет его использовать при оптимизации объектов, для которых q 1.
Рассмотрим динамику движения системы к экстрему му. Для этого обратимся к выражению (5.1.13), из кото рого легко получить
J ^ L . = - akgyt 1. |
(5.1.17) |
Как видно, левую часть этого выражения можно прибли-
женно представить в виде производной, т. е. (5.1.17) можно написать в непрерывном виде, считая i — непрерыв ным временем
dy
d i
akqyq 1. |
(5.1.18) |
'(Заметим, что переход от (5.1.17) к (5.1.18) возможен при гмалом изменении у, т. е. при малом а.) Решение этого
.дифференциального уравнения ие представляет труда. Действительно, запишем его в виде
ж — акд di
У
л, интегрируя правую и левую части, получим |
|
П |
|
§ -ирг ~ — àkqi. |
(5.1.19) |
Vo У
Для простоты будем рассматривать процесс поиска при одностороннем приближении к экстремуму (для этого до статочно выбрать коэффициент а достаточно малым). В этом случае получаем для g = 2
— 2aki, |
|
откуда окончательно следует |
|
у{ж Уов-^кК |
(5.1.20) |
При д^> 2 получаем из (5.1.19)
—akqi
ч- '1 ( l / р
ипосле очевидных преобразований имеем
Уг = |
________ уо________ |
(5.1.21) |
[1 + ((7 — 2) a q k i y f ' 2 ] 1^ ' 2 |
Как видно из этих выражений, с ростом i расстояние до цели yi стремится к нулю, т. е.
1 т щ = 0, |
(5.1.22) |
что доказывает сходимость процесса поиска при доста точно малом ак.
С точки зрения скорости сходимости процесса выгоднее выбирать величину а как можно больше. Однако
слишком большое значепие а может нарушить условие устойчивости процесса поиска (5.1.14). Это обстоя тельство заставляет выбирать величину а оптимально: не малой, но и не слишком большой.
Выбор оптимальной величины параметра а можно производить адаптивно. Для^этого достаточно увеличи вать’а при совпадении знаков "двух последовательных ра бочих шагов поиска и уменьшать в противном случае:
a,N+i = aw (1 -\-v sign AX N - AXN -I ). |
(5.1.23) |
Любопытно, что такого рода адаптация, кроме всего, дает возможность расширить зону устойчивой работы ал горитма. Действительно, в процессе неустойчивой рабо ты AXJV*Ажлг-1 <С 0 и величина a будет уменьшаться до тех пор, пока не войдет в устойчивую зону.
В заключение этого параграфа отметим, что градиент ный метод хорош лишь при наличии необходимой инфор мации об экстремальной характеристике объекта, а точ нее о показателе q параболы. При этом метод дает наиболь ший эффект при q = 2. Если же такой информации нет, то применение градиентного метода, как показано выше, может привести даже к неустойчивости процесса поиска. При отсутствии указанной информации следует приме нять более «осторожные» алгоритмы поиска, рассмотрен ные в предыдущей главе.
§ 5.2. Поиск с линейной экстраполяцией
Если известно, что функция качества объекта Q =
— Q (х) достаточно хорошо может быть представлена в виде кусочно-линейной функции и при этом заранее из вестно наименьшее значение показателя качества Q*, то для оптимизации можно эффективно воспользовать ся методом линейной экстраполяции.
* Смысл этого метода заключается в следующем. По двум значениям функции качества Q (х0‘ + g) и [(? (х0 — g) определяется поведение функции качества в районе х0 в предположении, что эта функция линейна:
<?, (») = Q(*° ~ 8) — (*. + g).
Здесь Qd ( х ) — экстраполированная по двум значениям функция качества (см. рис. 5.2.1, где эта функция пред ставлена в виде прямой, проходящей через две замерен ные точки).
Теперь, зная минимальное значение функции качест ва, нетрудно получить предполагаемую оценку положе ния экстремума хх. Для этого нужно решить ли нейное уравнение
& fa ) = <?*, (5.2.2)
которое дает
#1 = #о + ё "Ь
I 2g [Q* — Q (*о + g)]
' Q(xo +g) —Q (xo — g)
(5.2.3)
Полученное положение эк стремума нужно прове рить. Если
Q fa ) = Q*,
Рис. 5.2.1. Линейная экстраполя ция по двум замерам функции качества.
ТО найдено действительное положение |
экстремума |
|
И Хх = |
X * Если же |
|
|
Q (ь) + Q* |
(5.2.4) |
(как |
это имеет место для случая, показанного на рис. |
|
5.2.1), то это означает, что функцию Q (х) нельзя считать |
в точности кусочно-линейной и следует перейти к следую щему этапу, т. е. сделать эксперименты в точках хх + g, линейно экстраполировать функцию качества и, прирав нивая ее минимальному значению Q*, определить х2 и т. д.
Таким образом на i-м шаге такого экстраполяционного поиска получаем следующую оценку положения цели:
где |
Xi = |
—|—Дх(, |
(5.2.5) |
|
|
|
|
|
2Q* — Q |
+ g) — Q (*{_! - |
g) |
* ~ ё |
Q (**_! + g) - Q K_i - g) |
(5.2.6) |
|
|
Процесс поиска заканчивается тогда, когда
|А<?1 = К? (яг-i + g) — Q (яг-i — g) I ^ 0,
T. e. приращение близко к нулю и, следовательно, объект находится в районе экстремума. Другим критерием оста нова является то, что полу ченное значение экстремума Q (х^ совпадает с заданным Q* или отличается от него на
заданную величину е. Блок-схема этого алгорит
ма поиска показана на рис. 5.2.2. Здесь к известным опе
|
раторам |
добавлен |
оператор |
|||||
|
«Аж», обозначающий опреде |
|||||||
|
ление рабочего шага по фор |
|||||||
|
муле (5.2.6). |
|
|
|
||||
|
го |
Блок-схема экстремально |
||||||
|
регулятора, работающего |
|||||||
|
в |
соответствии с указанным |
||||||
|
алгоритмом, |
показана |
на |
|||||
|
рис. 5.2.3. Здесь блок управ |
|||||||
|
ления БУ управляет работой |
|||||||
|
всех |
блоков |
экстремального |
|||||
|
регулятора. Сначала сраба |
|||||||
|
тывает |
|
генератор |
пробных |
||||
|
шагов |
ГПШ, реализующий |
||||||
|
операторы «ж + |
показан |
||||||
|
ные на |
рис. 5.2.2. |
Получен |
|||||
|
ные |
в |
результате |
действия |
||||
|
этих |
операторов |
значения |
|||||
|
функции |
качества Q (ж+ # ) |
||||||
|
обрабатываются |
вычисли |
||||||
Рис. 5.2.2. Блок-схема алго |
тельным |
устройством |
ВУ, |
|||||
которое |
|
на |
схеме |
очерчено |
||||
ритма поиска с линейной эк |
пунктиром. |
ВУ определяет |
||||||
страполяцией. |
рабочий шагАж по формуле (5.2.6) и сообщает его исполнительному механизму ИМ, который по соответствующей команде Б У изменяет управ ляемый параметр требуемым образом ж —»- ж + Аж.
Рассмотрим теперь сходимость процесса поиска с ли нейной экстраполяцией для различных моделей функций
качества. Пусть |
(5.2.7) |
Q (х) = к (х — x*)q -\-Q*, |
|
где показатель q 0. |
|
Рис. 5.2.3. Блок-схема экстремального регулятора с линейной экс траполяцией.
Для простоты рассмотрим случай очень малых значе ний g, когда имеет место следующее очевидное выражение:
AQ (*$_х) |
dQ(*i_i) |
(5.2.8) |
|
2g |
dx |
||
|
|||
Тогда, переходя к новой переменной |
|
||
у = х |
—х *, |
(5.2.9) |
|
получаем на i-м шаге поиска |
|
Vi = У i-г + |
&Уг, |
|
где для параболы q-й степени имеем |
||
АУ* = - |
ktf-i |
Уи1 |
dQ(*j_i) |
|
|
|
|
dx
Подставляя (5.2.11) в (5.2.10), получим
(5.2.10)
(5.2.11)
Уг = U i-l |
^ i - l |
Я — 1 |
(5.2.12) |
-------- — |
= У-1-Х-^—^— |
Очевидно, что процесс поиска сходится, если
Уил я
т. е. расстояние до цели, которая расположена в точке у* = 0, с каждым шагом должно уменьшаться. Это требо вание сразу определяет значения показателя объекта у, для которых процесс поиска с линейной экстраполяцией сходится. Разрешая неравенство (5.2.13), получаем условие
« > 4 - - |
(5-2-14) |
Из (5.2.12) получаем |
|
Vi = Уо |
(5.2.15) |
откуда видно, что при q' = 1 экстремум у* = 0 дости гается за один этап поиска = 0. Этого следовало ожи дать, так как случай q = 1 полностью соответствует ис ходным предпосылкам метода линейной экстраполяции.
Определим число шагов поиска, необходимое для опре деления положения экстремума с точностью е. Для этого следует решить относительно N уравнение
Логарифмируя правую и левую части, получаем
1п-^-
Л Г * — I—Уол ~. (5.2.16) ,n ± ï = n
я
Из этого выражения хорошо видно, что с возрастанием q число шагов поиска, необходимых для отыскания экстре мума с заданной точностью е, увеличивается, т. е. сходи мость процесса ухудшается. При больших q получаем
и, подставляя это значение в (5.2.16), имеем для больших q
N æ - q i n - i - , |
(5.2.17) |
Уо
т. е. в этом случае число необходимых шагов поиска при мерно пропорционально величине q.
Рис. 5.2.4. Примеры процессов поиска с лилейной экстраполяцией при различных значениях параметра q.