Курсовая работа по курсу "Структурный анализ и синтез" на тему "Параметрическая идентификация" (стр. 2 )

значение х2 неизменно. Затем определяется полученное при этом приращение б/7! величины F, которое можно считать пропорцио­нальным значению величины частной производной

Рис IV-5. Поиск миниму­ма функции методом гра­диента.

(если величина dxi всегда одна и та же). Далее производится при­ращение 6х2 величины х2. В это время х\ = const. Получаемое при этом приращение 6F2 величины F является мерой другой частной производной

l£-Ef-coi»l«''» <IV"69>

Определение частных производных (IV, 68) и (IV, 69) означает, что найден'вектор с координатами dF/dxi и дР/дх2, который назы­вается градиентом величины F и обозначается как

Известно, что направление этого вектора совпадает с направле­нием наиболее крутого возрастания величины F. Противоположное ему направление — это направление «наискорейшего спуска», или другими словами, наиболее крутого убывания величины F.

После нахождения составляющих градиента пробные движения прекращаются и начинаются рабочие шаги по направлению, про­тивоположному направлению градиента, причем величина шага тем больше, чем больше абсолютная величина вектора grad F. Эти условия осуществляются, если величины рабочих шагов да;* и Д#2 пропорциональны полученным ранее значениям частных производных:

где а — положительная константа.

После каждого рабочего шага оценивается приращение А/7 ве­личины F. Если оно оказывается отрицательным, это означает, что движение происходит в правильном направлении и нужно двигать­ся в том же направлении МоМ\ дальше. Если же в точке mi ре­зультат измерения показывает, что Д/7 > 0, то рабочие движения прекращаются и начинается новая серия пробных движений. При этом определяется градиент gradF в новой точке М\, затем рабо­чее движение продолжается по новому найденному направлению - наискорейшего спуска, т. е. по линии М\М2, и т. д. Этот метод на­зывается методом наискорейшего спуска или методом крутого вос­хождения.

-Когда система находится вблизи минимума, показателем чего является малое значение величины

происходит переключение на более «осторожный» метод поиска, так называемый метод градиента. Последний отличается от ме­тода-наискорейшего спуска тем, что после определения градиента grad F делается лишь один рабочий шаг, а затем в новой точке опять начинается серия пробных движений. Такой метод поиска обеспечивает более точное установление минимума, чем метод наи­скорейшего спуска, между тем как последний позволяет быстрее приблизиться к минимуму. Если в процессе поиска точка М дохо­дит до границы допустимой области и хотя бы одна из величин mi, М2 меняет знак, метод меняется и точка М начинает двигаться вдоль границы области.

Эффективность метода крутого восхождения зависит от выбора масштаба переменных и вида поверхности отклика. Поверхность со сферическими контурами дает быстрое стягивание к оптимуму.

Недостатки метода крутого восхождения:

1. Ограниченность экстраполяции. Двигаясь вдоль градиента, мы основываемся на экстраполяции частных производ­ных целевой функции по соответствующим переменным. Однако форма поверхности отклика может изменяться и необходимо из­менять направление поиска. Другими словами, движение на пло­скости не может быть продолжительным (см. пример IV-6).

2. Трудность поиска глобального оптимума. Ме­тод применим для отыскания только локальных оптимумов. ,

Метод крутого восхождения при наличии

ограничений

При наличии ограничений на изменение параметров целевой функции базисная точка выбирается так, чтобы она лежала в пре­делах ограничений, и поиск начинают по методу крутого восхож­дения. После расчета следующей точки оценивается: не произошло ли нарушения ограничений; если нарушения нет, поиск продол*

222

Дается. Когда какое-либо ограничение нарушено, производят ра­счет градиента в соответствии с учетом ограничений (см. ниже).

Может быть использован также метод, согласно которому при одном нарушении ограничений точка возвращается на линию огра­ничений. Когда существует более чем одно ограничение, и в каж* дый момент времени новое ограничение нарушается, метод тре* Сует, чтобы точки были перенесены к новому ограничению. В этом; методе принимается, что оптимум лежит на ограничении. 1

По методу Розенброка функция цели видоизменяетея введе­нием множителей. Всякий раз, как одно из переменных нарушает ограничения, множитель равен нулю, т. е. функция цели умно­жается на нуль и поэтому. равна нулю. Если значения переменной находятся в пределах допустимого режима, множитель равен 1 и целевая функция принимает ее полное значение. Однако, когда значения переменной снижаются до пределов, предписываемых «пограничной зоной», множительный фактор изменяется парабо­лически от 0 до 1 в пределах пограничной зоны и целевая функция изменяется от 0 до ее полного значения.

для удобства на примере однопараметрического объекта, в котором организация движения сводится к выбору соотношения между ско­ростью изменения входа системы и сигналом, полученным с устрой­ства, определяющего положение экстремума. Как и в обычных си­стемах регулирования, в экстремальных системах возможно пост­роение релейных и линейных систем. В релейных экстремальных системах для управления движением используется лишь знак пока­зателя экстремума; величина сигнала, поступающего на исполни­тельный механизм, не зависит от расстояния до экстремума. Такие системы называются экстремальными системами с независимым поиском. Если же для управления движением используется и ве­личина показателя экстремума, т. е. скорость движения зависит от расстояния до экстремума, то системы называются системами с за­висимым поиском или пропорциональными.

При поиске по чувствительности и при шаговом поиске по при­ращениям возможно использование как систем с независимым поис­ком, так и пропорциональных систем. Системы с запоминанием экст­ремума не могут изменять скорость пропорционально расстоянию до экстремума, так как при движении к экстремуму показатель экстремума е= 0 и только после экстремума s^fc 0. Поэтому системы с запоминанием экстремума обязательно релейные.

Иначе обстоит дело в многомерных системах. Как известно, функция нескольких переменных у = f (х±, х2, . . . , хп) имеет при системе значений (х1э, х2э, ..., хпэ) в точке Рэ экстремум, если можно указать такое число е, что область х19 — е < х1э < д:1э + + е, Х2э — е < Х2э < Х2э + е, .. ., х„э — е < хпэ < хпэ + е входит

в область задания функции и для каждой системы значений в этой области, кроме самой системы (х19, х2э,..., хпэ), удовлет­воряются условия

/ (xv xz,..., xn) < / (х1э, х2э,..., хпэ) — для случая максимума и / (*!, *2,..., хп)> f (х19, х2э,..., хпэ) — для случая минимума.

Из определения видно, что для нахождения положения экстре­мума необходимо проводить исследование поведения объекта при изменении всех параметров. Способ перехода от одного управ­ляющего параметра к другому и алгоритм движения поэкстремаль­ней поверхности определяет организация движения к экстре­муму.

Все существующие методы поиска многомерного экстремума мож­но разделить на две основные группы: регулярный поиск и случай­ный. К основным методам регулярного поиска относятся.

Метод сканирования. Этот метод заключается в последовательном переборе всех возможных состояний системы. Oflf позволяет опреде­лить экстремум за один цикл поиска, однако для^ поиска экстремума многомерных систем применяется в очень редких случаях — в экст­ремальных дискретных системах с небольшим числом возможных со­стояний. В основном метод сканирования применяется при настрой-

ке одномерных многоэкстремальных систем на глобальный экстре­мум.

Сканирующий трехканальный оптимизатор установлен в ана­логовой моделирующей машине МН-11.

Метод Гаусса—Зайделя. Суть метода сводится к поиску экстре­мума последовательно по всем координатам так, что на каждом эта­пе экстремум отыскивается только по одной координате, т. е.

—L-= 0. Этим методом за один цикл поиска не удается найти xi искомое состояние.

На рис. 1.8, а показана экстремальная поверхность. Допустим, что в начальный момент объект находится в точке А, которой соот­ветствует координата уа и воздействия xla и *2а. Через точку Л проведем плоскость Slt параллельную плоскости хгу. Пересекаясь

т

с экстремальной поверхностью, она дает экстремальную линию /. Оставляя х2 постоянным, ищем этот частный экстремум (т. е. ус­ловие ~- — 0) путем изменения хг от xla до хи. Получаем точку

В. Проведем плоскость S2 через точку В частного экстремума, па­раллельную плоскости х$. Пересечение ее с экстремальной по­верхностью даст экстремальную линию 2. Оставляя х± постоянным,

соответствующим условию -^— — 0, ищем второй частный экстре­мум (т. е. условие -^—= 0) путем изменения х2 от х2а до х2с. Получаем точку С.

Повторяем эту операцию до тех пор, пока ~- и -~- не станут

ох1_ oxz

равными нулю. Практически вектор состояния у будет совершать колебания около экстремальной точки, при попеременном измене­нии хг и х2. Указанный метод нетрудно распространить на любое число переменных, от которых зависит экстремум.

Возьмем теперь линии равных значений у, которые обозначим бис. Проекции этих линий на плоскость х^х2 обозначим Ъ' и с'. Из чертежа видно, что переключать хг и х2 нужно тогда, когда траектории х± и х2 станут касательными к проекциям линий рав­ных значений у, т. е. к кривым Ь' и с'.

Основным недостатком метода является медленная сходимость поиска и невозможность настройки в некоторых случаях. Достоин­ство метода заключается в простоте алгоритма и его схемной реали­зации, что в ряде случаев оказывается решающим при выборе мето­да поиска.

Метод градиента. Сущность метода состоит в том, что система движется в направлении, обратном мгновенному направлению век­тора градиента функции. При этом движение может быть непре­рывным или шаговым.

Градиентом, grad у называется вектор, направленный по нор­мали к поверхности уровня в сторону возрастания (убывания) функ­ции у и численно равный скорости изменения функции по направле­нию нормали

|grady| = ^. (1-18)

Рассмотрим экстремальную поверхность (рис. 1.8, б). Спроекти­руем на плоскость хгх2 линии равного значения у. Получим кон­центрические эллипсы, если экстремальная поверхность аппрокси­мирована эллиптическим параболоидом. Допустим, что объект находится в точке А, которой соответствует координата уа и воздейст­вия xla и х2а. Возьмем градиент в точке А

grad,a = ^.

Геометрически градиент будет являться перпендикуляром к ка­сательной в точке А' на линии равного значения. Проекции гради­ента на оси Xi и х2 соответственно будут:

л ду

grad,,«/ = —;

л ду

grad,,,,^.

Начнем изменять воздействия хг и х2 со скоростью, пропорцио­нальной градиентам:

/ х - а ^Lf Xi - а, ^ г,

ду,

x2 = az—^-t. дх2

Непрерывно измеряя градиент и меняя пропорционально ему скорости воздействия хг и х2 , будем перемещаться от одной линии

„ du равных уровней к другой, пока не достигнем точки, где •—• =

-р - = 0. Полученная траектория АО на экстремальной поверх­ности является траекторией шарика, свободно скатывающегося под действием силы тяжести из экстремальной точки. В этой точке изменение х± и х2 нужно прекратить. Практически вектор у будет совершать колебания около точки экстремума при небольших из­менениях *! и xz.

Можно пойти по другому пути, который проще осуществим. Измерять градиент не непрерывно, а дискретно с некоторым шагом h. Воздействия х. г и х2 меняются скачками, величины которых про­порциональны составляющим градиента:

л l ду

Д*1 = bi -=г;

дхг

. 1 ду

Д*2 — Ь2 -^- •

0*2

При таком методе поиска экстремум достигается достаточно быстро.

Очевидно, что при шаговом движении сходимость поиска зави­сит от правильности выбора рабочего шага (коэффициента Ь^. При значительных bl и ярко выраженной нелинейности оптими­зируемой функции в окрестности yl поиск может расходиться. При малых bt и функции, близкой к линейной, возрастает время движения к экстремуму за счет увеличения времени анализа состав­ляющих градиента и рабочего времени.

Непрерывное движение возможно при непрерывном измерении всех составляющих градиента, а это осуществимо лишь при поиске с разнесением частот поискового сигнала (о>П(. =f= o>n;.; t =£='/)•

215

При шаговом поиске методом градиента значительным недостат­ком является необходимость сложного анализа (п пробных шагов перед рабочим шагом.) Наиболее ценным свойством, способствую­щим использованию метода градиента, является его точность. Оп­ределение градиента производится одним из способов, изложенных в §1.3.

Метод наискорейшего спуска. Этот метод является развитием шагового поиска методом градиента. Сущность его заключается в следующем (рис. 1.8, в). Начальное положение характеризуется точкой А, в которой градиент

i*rad^ -(-?-).•

Запишем проекции градиента на оси хг и xz gra<U »=•!*-;

OXi

gwO = -^ •

dxz

Пропорционально градиентам будем изменять х± и х2 до тех пор, пока не получим -^— = 0. Это произойдет тогда, когда вектор

градиента коснется какой-либо проекции линии равных значений у (точка В). В этой точке снова замеряем градиент

1^> = (ж1

Опять изменяем хг и х2, скорости которых пропорциональны составляющим градиента до тех пор, пока —rf-=fc= 0. Повторяя ука-

fl/2

занные операции несколько раз, попадем в точку экстремума по траектории АВО. Во время поиска х± и х% можно мен ять шагами или непрерывно.

Метод наискорейшего спуска несколько проще метода градиен­та и дает достаточно малое время выхода в экстремальную точку.

Методы наискорейшего спуска и градиента можно распростра­нить на п независимых переменных.

При непрерывном движении новое измерение градиента произ­водится при -jjj-= 0, ибо при неподвижной экстремальной поверх­ности значение -^-= 0 означает, что —Цг - = 0. При шаговом дви­жении такой алгоритм позволяет выбирать коэффициент bt при меньшем объеме априорной информации о характере оптимизируе­мой функции, ибо уменьшение скорости рабочего шага не приводит к увеличению времени анализа. Нетрудно заметить, что чем более полога линия градиента оптимизируемой функции, тем выгоднее

216

использование метода наискорейшего спуска по сравнению с мето­дом градиента. Большая скорость сходимости является основным преимуществом этого метода и делает его основным при настройке многомерных систем.

Очевидно, что в случае объекта с существенно нелинейными градиентными направлениями метод наискорейшего спуска вы­рождается в метод градиента.

Кроме регулярного поиска, существует множество алгоритмов случайного поиска, в основе которых лежит случайный перебор со­стояний системы из множества возможных состояний {X}, обеспечи­вающих множество значений {Y}, на выходе системы. Перебор состоя­ний прекращается, если система попадает в подмножество {X*}, обес­печивающее выполнение заданного требования, т. е. при у £{Y*}. Методы случайного поиска не получили пока широкого распростра­нения. Преимущества и отличия методов случайного поиска от ре­гулярного аналогичны преимуществам и отличиям случайной выбор­ки по сравнению с регулярной. Случайный поиск именно в силу случайности выбора очередного состояния систем не может попасть в ловушку типа «седла» для метода градиента или «хребта» для ме­тода Гаусса — Зайделя.

Рассмотрим некоторые алгоритмы случайного поиска и прежде всего — алгоритм чисто случайного поиска, впервые примененный в гомеостате Эшби. Поиск основан на определении знака прираще­ния функции качества при случайном направлении пробного шага. Если направление пробного шага оказалось результативным (знак приращения соответствует цели поиска: плюс при поиске максиму­ма или минус при поиске минимума), то в этом же направлении делается рабочий шаг, а из нового положения — пробный шаг в случайном направлении. Если в результате пробного шага прира­щение показателя качества не соответствует поставленной задаче, то рабочий шаг не производится, а система либо возвращается в исходное положение и делает пробный шаг в другом направлении, либо осуществляет пробный шаг в новом направлении из той точки, куда ее привел предыдущий (неверный) пробный шаг. Эти варианты чисто случайного поиска называются соответственно случайным по­иском с возвратом и случайным поиском с пересчетом. На рис. 1.9 показано движение системы при обоих вариантах поиска.

Алгоритм случайного поиска с возвратом может быть записан в виде

*i4l ~ Xi ~Ь_Д*/+1°> _

I а С при y(xi) ^ y(xi+ l);

АлГ _ ) ^

/+1l -A^. при у (*/>#(*!-И).

где х — вектор состояния входа объекта; С —случайный единичный вектор; а — величина рабочего шага.

Знаки неравенств определяются целью поиска (максимум или минимум).

Алгоритм случайного поиска с пересчетом можно записать в следующем виде:

Рис. 1.9. Организация движения к экстремуму при случайном поиске

В [39] приведены исследования количества проб, обеспечиваю­щих заданную вероятность успеха поиска, и показано, что число проб не зависит от количества регулирующих воздействий. Необхо­димое число проб п может быть определено из соотношения