Принципы автоматизации Систем автоматического управления. Методы и алгоритмы

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Московский Государственный Горный Университет

РЕФЕРАТ

Принципы автоматизации Систем Автоматического Управления. Методы и Алгоритмы

Студент гр. САПР-1В-96

Царев Александр В.

Москва 1999 г.



Оглавление

Оглавление

Введение

1. Алгоритмы

1.1 Алгоритм локального параметрического поиска

1.1.1 Алгоритм случайного спуска

1.1.2 Случайный поиск с возвратом

1.1.3 Релаксационный алгоритм случайного спуска

Случайный поиск по наилучшей пробе

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

Адаптация величины рабочего шага

Адаптация распределения случайного шага

1.2 Учет ограничений в процессе случайного поиска

Ограничения типа неравенств

Ограничения типа равенств

Ограничения типа неравенств и равенств

Дискретные ограничения

Дискретные ограничения с неравенствами

1.3 Глобальный поиск

«Набросовые» алгоритмы

Случайный наброс с локальным поиском

Адаптивный набросовый алгоритм

Сглаживающие алгоритмы

Сглаживание функционала

Сглаживание траектории

Оптимизация в обстановке случайных помех

Метод стохастической аппроксимации

Сглаживание помех

Стохастическое накопление

Последовательное накопление

Симплексный алгоритм поиска

Структурная оптимизация

Дискретизация структуры

Эволюционная оптимизация структуры

2 Автоматизация проектирования систем автоматического управления

Принципы автоматизации проектирования систем автоматического 25управления

Этапы и стадии проектирования

Уровни автоматизации проектирования

Компоненты обеспечения САПР

Общие принципы построения САПР

Способы построения систем автоматизированного проектирования

Диалоговая система проектирования ДИСПАС

САПР адаптивных систем САПРАС

Система «Гамма-1М»

Введение

В этом реферате мной изложены широко распространенные алгоритмы и методы поиска, сортировки, сглаживания, накопления, оптимизации, а так же здесь рассматриваются наиболее общие вопросы автоматизированного проектирования Систем Автоматизированного Управления, основные этапы, уровни автоматизации процесса проектирования.

Весь материал мной подобран из справочника «Справочник по теории автоматического управления 1987г».

1. Алгоритмы

1.1 Алгоритм локального параметрического поиска

В случае параметрического синтез САУ, алгоритм решения задачи оптимизации имеет параметрический характер.

C[N+1] = C[N] + C[N+1] (13.3.1)

Где приращение C[N+1] вектора параметров C[N] определяется алгоритмом поиска, использующим приращение:

Q[N] = Q[N] - Q[N-1] (15.2.7)

в котором Q[N] = Q (C[N]).

1.1.1 Алгоритм случайного спуска

Этот алгоритм построен с помощь только двух операторов:

оператора случайного шага () и

оператора повторения предыдущего шага (+),

которые взаимодействуют как показано на рисунке 15.3.1 , где этот алгоритм изображен в виде графика с условными переходами (условия переходов рядом с соответствующими дугами переходов).

Рекуррентная форма записи этого алгоритма имеет вид:

(15.3.2)

где a - величина шага ()

- единичный случайный вектор распределенный по всем направлениям пространства оптимизированных параметров {C}

Q0 Q<0

+

Q0

Алгоритм имеет очень простую геометрическую интерпретацию. Это по сути дела, спуск шагами а в выбранном направлении . Как видно это стохастический аналог известного алгоритма наискорейшего спуска, в котором спуск производится в антиградиентом направлении.

Преимущество алгоритма случайного спуска заключается в том, что здесь нет затрат на определение градиентного направления.

Алгоритм случайного спуска опирается на следующие очевидное предположение относительно объекта оптимизации: вероятность удачи (Q < 0) в ранее удачном направлении больше, чем в случайном, т.е. целесообразно повторить удачные шаги, а при неудаче (Q 0) делать случайный шаг, т.е. обращаться к оператору .

Такая ситуация обычно имеет место вдали от экстремума Соп, что и определяет рекомендуемую область применения для алгоритма случайного спуска.

1.1.2 Случайный поиск с возвратом

Этот метод поиска моделирует метод проб и ошибок. Алгоритм этого метода построен из двух операторов: оператора случайного шага () и оператора возврата (-). Граф алгоритма с нелинейной тактикой показан на рисунке 15.3.2. Его работоспособность обеспечивается за счет того, что используется только удачные случайные шаги, а неудачные устраняются (точнее, исправляются) с помощью оператора возврата (-). Рекуррентная формула алгоритма имеет вид:

C[N+1]= (15.3.3)

Рассмотрим область целесообразного использования этого алгоритма.

Анализ показывает, что его следует применять в ситуациях со значительной нелинейностью функционала Q(C), когда целесообразно повторить удачные шаги, так как вероятность повторного успеха в этом случае мала. Такой бывают ситуация в районе экстремума Соп или

Q<0

Q<0 Q0 Q<0

- Q0

Q0

Рис. 15.3.2 Иллюстрация случайного Рис. 15.3.3 Иллюстрация поиска с возвратом.Релаксационного алгоритма случайного спуска.

на дне «оврага» минимизируемой функции. Именно в таких случаях целесообразно применение этого алгоритма.

1.1.3 Релаксационный алгоритм случайного спуска

Введение возврата в алгоритм случайного спуска (15.3.1) обеспечивает ему релаксационные свойства, т.е. не увеличивает минимизируемый функционал. Граф этого алгоритма изображен на рисунке 15.3.3. Его рекуррентная формула имеет вид:

= (15.3.4)

Здесь - знак конъюнкции, требующий одновременности выполнения событий, указанных в скобках.

1.1.4 Случайный поиск по наилучшей пробе

Алгоритм имеет вид:

(15.3.5)

где оп - случайный вектор, минимизирующий функционал в районе точки С[N]:

Q(C[N] + gоп) = min Q(C[N] + gj), (15.3.6)

i = 1,.,.,m

j - случайные независимые единичные векторы, с помощью которых обеспечивается режим случайных проб вокруг точки C[N].

Если величина g мала и функционал в районе С[N] достаточно гладкий, то можно повысить эффективность алгоритма следующим образом:

, (15.3.7)



где

(15.3.8)

и

(15.3.9)

В этом случае шаг делается по наилучшей пробе _, если модуль приращения функционала при этом больше модуля его приращения при наихудшей пробе +, и по наихудшей пробе + в обратном случае.

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

Многочисленные ситуации, складывающиеся в процессе решения задачи оптимизации типа «холм», «яма», «плоскогорье», «хребет», «овраг» и т. д. Заставляют искать средства такой перестройки алгоритма поиска, чтобы эти ситуации преодолевались бы с минимальными затратами. Такого рода перестройка алгоритма, реализуемая формально, является адаптацией этого алгоритма.

Таким образом, задача адаптации процесса поиска возникает всегда, когда алгоритм необходимо изменять в процессе поиска, чтобы поддержать его эффективность на необходимом уровне. Проблема адаптации возникает всегда при оптимизации сложных объектов, когда нельзя заранее указать на ситуацию, в которую попадает алгоритм поиска. Такого рода неопределенность типична для задач проектирования систем автоматического управления.

Параметрическая адаптация алгоритма случайного поиска опирается на то, что параметрами алгоритма случайного поиска являются величина рабочего шага a и параметра плотности распределения p() случайного шага . Заметим, что случайный поиск отличается от любого детерминированного именно наличием такого распределения, изменение которого позволяет адаптировать случайный поиск. Этой «рукоятки» управления процессом поиска не имеют регулярные алгоритмы, что выгодно отличает случайный поиск.

Рассмотрим адаптацию по каждому на указанных факторов отдельно.

1.1.5.1 Адаптация величины рабочего шага

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

(15.3.10)

где в соответствии с указанными соображениями 11; 2<1.

Значения параметров 1 и 2 алгоритма адаптации (15.3.10) зависят от вероятности того, что случайный шаг будет удачен, т. е. От вероятности события Q<0. В процессе адаптации следует стремиться к тому значению шага, при котором приближение к цели было бы наибольшим. Пусть вероятность удачного случайного шага при такой оптимальной величине шага равна P .Тогда оптимальные значения 1 и 2 связаны следующими соотношениями (15.2):

(15.3.11)

где величина P с ростом n стремится к 0,27. Используя это выражение, можно добиться оптимального режима адаптации алгоритма, что позволяет значительно убыстрить решение задачи оптимизации.

1.1.5.2 Адаптация распределения случайного шага

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

Пусть p() плотность распределения случайного шага . Основной характеристикой всякого распределения является его математическое ожидание E[]. Изменяя эту характеристику, можно эффективно воздействовать на процесс поиска. Практически это сведется к добавлению вектора V к 0 - случайному вектору с нулевым математическим ожиданием (E[0]=0)

=0+V, (15.3.12)

откуда следует, что E[]=V , т.е. имеет место «снос» процесса поиска в направлении V. Естественно, что этот снос должен быть направлен в сторону уменьшения функционала Q(C). Вектор V должен при этом отражать предысторию процесса поиска и таким образом выявлять перспективное направление движения при оптимизации.

Здесь помогает довольна очевидная эвристика: направление V следует формировать как взвешенную сумму случайных шагов, причем удачные шаги (Q<0) следует брать с положительными весами, а неудачные с отрицательными. При этом предпочтение должно отдаваться более свежей информации. Эта эвристика реализуется, например, такой простой рекуррентной формулой адаптации в процессе поиска:

V[N]=kV[N-1]- (15.3.13)

где 0 < k 1 - коэффициент забывания, а - коэффициент интенсивности учета новой информации.

Случайный поиск, снабженный такой адаптацией вероятностных свойств, обладает, как правило, повышенным быстродействием. Для этого ситуация, которая складывается в процессе оптимизации, не должна изменяться слишком быстро, иначе не к чему будет адаптироваться. Поэтому введение адаптации такого рода (ее часто называют самообучением) не всегда улучшает процесс поиска, но и не ухудшает его.

1.2 Учет ограничений в процессе случайного поиска

Проблема многопараметрической оптимизации в задачах оптимального проектирования всегда имеет условный характер, т. е. Связана с обязательным выполнением ограничений S(15.1.2). Случайный поиск как метод решения условных задач (15.1.1) отличается рядом преимуществ по сравнению с детерминированными методами. У случайного поиска имеются возможности, связанные со случайным характером поиска, которых в принципе не может иметь не один детерминированный метод решения задачи условной оптимизации.

Рассмотрим различные виды ограничений. Они могут иметь троякий характер. К ограничениям типа неравенств и равенств (15.1.2)

SH: hi(C)0, i=; SG: gj(C)=0, j=, (15.4.1)

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

SD:fz(C), z= (15.4.2)

где fz(.) - заданные функции, а - заданное значение, которое может принимать 2-я функция (r=). В частном случае при fz(C)=cz получаем

SD:Cz (15.4.3)

где - значение, которые может принимать z-я переменная (например, целочисленные значения).

Область поиска S, вообще говоря, может быть образована путем различных комбинаций пересечения областей SH, SG, SD. Разумными комбинациями в общем случае являются лишь две. Первая: S=SHSG как известно, связана с непрерывными задачами математического программирования, а вторая: S=SHSD - с задачами дискретного программирования.

Рассмотрим специфику процессов случайного поиска при учете ограничений различного рода.

1.2.1 Ограничения типа неравенств

Ограничения типа неравенств (S=SH) образует обычно область размерности n. Выход за границу этой области (CS) является сигналом о необходимости учета ограничений S. При случайном поиске это можно осуществить множеством способов. Рассмотрим наиболее эффективный из них.

Способ возврата заключается в том, что нарушение ограничений S отождествляется с неудачным шагом, т. е. c не убыванием показателя качества (), для чего вводится оператор возврата. Таким образом, в процессе поиска различаются лишь две ситуации удачного и неудачного шагов:

: (CS)(Q<0), : (CS)(Q0) (15.4.4)

т.е. удачным шагом считается случай , когда ограничения не нарушены и одновременно уменьшился показатель качества. Неудачным шагом считается тот, при котором нарушены ограничения или увеличился показатель качества. Реакцией на является возврат в предыдущее состояние (C[N+1]=- C[N]) и случайный шаг. (C[N+2]=a). На удачу - можно реагировать по-разному. При случайном спуске (см. П. 15.3.2) - повторять удачный шаг (C[N+1]= C[N]). При алгоритме с возвратом (п. 15.3.1) - вводить случайный шаг (C[N+1]=a).

1.2.2 Ограничения типа равенств

Учет ограничений типа равенств (S=SG) в процессе случайного поиска связан с организацией движения вдоль этих ограничений. Это можно осуществить различными путями. Простейшим из них является введение «коридора», т.е. переход к ограничениям типа неравенств:

||gj(C)||<e, f= (15.4.5)

При этом величина - должна стремиться к нулю в процессе поиска.



1.2.3 Ограничения типа неравенств и равенств

Учет такого рода ограничений (SHSG) в процессах случайного поиска осуществляется путем прямого комбинирования методов, используемых в двух рассмотренных выше случаях.

1.2.4 Дискретные ограничения

Простейшая схема следующего поиска в случае ограничений SD опирается на случайный выбор новой точки в e - окрестности исходной точки. Пусть e - окрестность исходной точки С[N] имеет вид

||C-C[N]||e (15.4.6)

и пусть для простоты множество Sp образовано целочисленными векторами С. Это означает, что все координаты этих векторов имеют целочисленные значения (более общий случай легко сводится к этому). Пусть De[N] - множество целочисленных точек, попавших в --окрестность, т.е. удовлетворяющих условию (15.4.6). Так, например, при e=1 таких точек будет 2n.

Тогда процедура случайного поиска на (N+1)-м шаге будет связана со случайным выбором такой точки множества De[N], для которой выполняются очевидные условия

Q(C[N+1])<Q(C[N], C[N+1] De[N]. (15.4.7)

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

Критерием остановки процесса является отсутствие такой точки при достаточно большом e.

Очевидно, что этот процесс можно варьировать в широких пределах. Например, изменять характер меры в неравенстве (15.4.6) или адаптировать ее в процессе поиска. Большинство существующих эффективных методов решения дискретных задач оптимизации в той или иной степени используют изложенное (см. Например, (15.3)).

1.2.5 Дискретные ограничения с неравенствами

Учет ограничений типа неравенств в задаче дискретной оптимизации (SDSH) незначительно усложняет процедуру случайного поиска. В этом случае к условиям (15.4.7) добавляется еще одно условие C[N+1] SH , которое легко проверяется.

1.3 Глобальный поиск

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

Другой специфической чертой глобального поиска является отсутствие полной уверенности, что найденный за конечное время экстремум является глобальным. И лишь при неограниченном увеличении времени поиска вероятность утери глобального экстремуму может быть сколь угодно малой.

1.3.1 «Набросовые» алгоритмы

Так обычно называют алгоритмы глобального поиска, в которых используется процедура случайного наброса, т.е. случайного распределения пробных точек в области S.

1.3.1.1 Случайный наброс с локальным поиском

При этом на каждом i-м этапе из случайной начальной точки делается локальный спуск в ближайший минимум Cоп- любым локальным методом поиска (например, описанным в 15.3). За глобальным минимум принимается наименьший из полученных М локальных минимумов

(15.5.1)

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

Однако использование локального поиска совершенно необязательно при работе набросовых алгоритмов.

1.3.1.2 Адаптивный набросовый алгоритм

Он связан с адаптивным изменением плотности распределения наброса. Пусть p(C,V,) - плотность распределения, параметрами которого является вектор --, равный математическому ожиданию случайного вектора, а 2 - некоторая скалярная мера рассеивания этого распределения (типа обобщенной дисперсии), такая, что при =0 распределение вырождается в дельта-функцию п С=V, а с увеличением - область наброса расширяется пропорционально . Алгоритм поиска заключается в генерировании последовательности случайных точек C[1], ..., C[N] и выборе точки с наименьшим значением показателя качества аналогично (15.5.1):

(15.5.2)

Так будем условно обозначать решение задач . При этом параметры V и распределения адаптируются, например, следующим образом:

(15.5.3)

(15.5.4)

где 1<1, 2>1, т.е. зона поиска расширяется с каждой удачей и сужается при неудаче. Этот алгоритм стремится стянуть наброс вокруг лучшей точки. Темп такого стягивания, т.е. величина 1, определяет степень глобальности алгоритма. Если он велик (т.е. 1 мало), то, очевидно, будет найден ближайший локальный экстремум. Если мал, то шансы найти экстремум лучше ближайшего локального повышаются и при 1 1 вероятность отыскания глобального экстремума при N стремиться к единице (для этого необходимо, чтобы p(C,V,)0 для любой точки СS, т.е. чтобы плотность вероятности появления любой допускаемой точки не было равна нулю).

1.3.2 Сглаживающие алгоритмы

Идея сглаживания минимизируемого функционала или траектории поиска породила много эффективных алгоритмов глобального поиска. Рассмотрим некоторые из них.



1.3.2.1 Сглаживание функционала

Если минимизируемый функционал Q образован путем положения на «хорошую» унимодальную функцию мелких колебательных отклонений, то для отыскания глобального экстремума можно воспользоваться идеей сглаживания [15.6-15.8]. Делается это следующим образом.

В районе точки С осредним функцию Q(C) с некоторым неотрицательным весом q(Y):

(15.5.5)

Эта функция уже ближе к унимодальной, так как здесь несколько сглажена колебательная составляющая. Для вычисления значений этой сглаженной функции нужно воспользоваться методом Монте-Карло. Пусть в качестве весовой функции q(Y) выбрана плотность распределения p(Y), для которой выполняются условия

(15.5.6)

Тогда, генерируя в соответствии с этой плотностью случайные векторы Y1, ...., YN, можно оценить значение интервала (15.5.5) в любой точке С следующим образом:

(15.5.7)

Эта оценка при N совпадает с точным значением интеграла (15.5.5) и отличается от него при конечном N на случайную величину с нулевым средним и дисперсией порядка 1/N. Это дает возможность подбирать объем N случайной выборки таким образом, чтобы свойства оценки (15.5.7) были приемлемыми.

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

Если для этого воспользоваться градиентным методом, то для вычисления градиента можно воспользоваться аналитическим видом распределения p(.). Преобразуем интеграл (15.5.5) с помощью подстановки Z=C+Y к виду

(15.5.8)

Градиент можно определить путем прямого дифференцирования

(15.5.9)

где операция вычисления градиента осуществляется аналитически. Оценивать (15.5.9) можно также методом Монте-Карло

(15.5.10)

где Zi - случайные реализации вектора Z, распределенного в соответствии с заданной плотностью p(Z)0 для ZS. Процесс поисковой оптимизации при этом реализуется очевидной формулой .

Как легко заметить, такой поиск является случайным, так как здесь используются случайные точки Zi. Эффективная организация поиска требует изменения p(.) и N в процессе поиска, т.е. их адаптации таким образом, чтобы вдали от экстремума сглаживание было бы сильным и N мало, а по мере приближения к глобальному экстремуму N возрастало при уменьшении сглаживания.

1.3.2.2 Сглаживание траектории

Очень часто глобальный экстремум находится на «дне оврага» минимизируемого функционала Q(C). Под оврагом принято понимать ситуацию, характеризующейся следующей особенностью: почти вдоль всех направлений функционал сильно увеличивается (это «склоны» оврага) и только в сравнительно узком конусе направлений он слабо уменьшается (это и есть направление «дна» оврага). Локальный поиск в такой ситуации имеет рыскающий характер). Следует сгладить эту траекторию. Если глобальный экстремум лежит на дне оврага, то для такого сглаживания воспользоваться методом случайного поиска с направляющим конусом. Суть его состоит в следующем.

На сферическом (радиусом a) дне конуса с вершиной в С[N] и осью V[N] делаются m случайных проб C1[N], ...,Cn[N]. Следующее (N+1)-e состояние определяется по наилучшей пробе

(15.5.11)

а ось следующего конуса выбирается в соответствии с

V[N+1]=(1/a)(C[N+1]-C[N]), (15.5.12)

т.е. вдоль сделанного рабочего шага. Легко видеть, что траектория такого поиска полога и позволяет отслеживать направление оврага независимо от того, вверх или вниз идет этот овраг. Угол между следующими друг за другом шагами здесь не превышает половины угла раскрытия направляющего конуса. Изменяя этот угол, можно воздействовать на гладкость траектории поиска, т.е. адаптировать его (15.9). Когда конус раскрывается в сферу, получаем поиск по наилучшей пробе, рассмотренный выше (см.п.15.3.4)

1.4 Оптимизация в обстановке случайных помех

В задачах проектирования систем автоматического управления «зашумление» функционала появляется в результате применения методов статистического моделирования для оценки значения функционала Q(C). При этом точное значение функционала неизвестно. Доступны лишь его наблюдения, которые удобно описывать соотношением

Q`(C)=Q(C)+e, (15.6.1)

где e - независимые случайные помехи с нулевым математическим ожиданием и дисперсией 2.

Рассмотрим наиболее распространенные методы поиска, решающие задачу оптимизации исходного функционала Q(C) по его «зашумленным» наблюдениям(см.п.15.6.1).

1.4.1 Метод стохастической аппроксимации

Этот метод является, по сути дела, градиентным методом с программно изменяемыми пробными и рабочими шагами

(15.6.2)

где компоненты оценки градиента имеют вид



(15.6.3)

а ei - i-й орт (i=). Для сходимости этой процедуры при достаточно широком классе функционалов Q(C) необходимо, чтобы коэффициенты рабочего (a[N]) и пробного (g[N]) шагов удовлетворяли следующим соотношениям [15.10, 15.11]:

(15.6.4)

Предпоследнее из этих соотношений требует, чтобы величина a[i] уменьшалась не слишком быстро, а последнее чтобы коэффициент пробного шага g[i] уменьшался значительно медленнее рабочего a[i]. Условиям (15.6.4) удовлетворяют, например, следующие соотношения:

(15.6.5)

где 0<1; >0; 2(-)>1 .

Хотя сходимость этого метода показана строго математически, его практическое применение обычно не удовлетворяет решению прикладных задач. Дело здесь в том, что указанная сходимость метода проявляется при N. В практических расчетах всегда существенно иное - необходимо в процессе поиска быстро попасть в некоторую малую окрестность экстремума. С другой стороны, программный характер изменения параметров (15.6.5) не учитывает ситуации, сложившейся в процессе поиска, что не может не повлиять на эффективность процесса оптимизации.

Все эти обстоятельства и объясняют то, что стохастическая аппроксимация обычно не используется для решения практических задач синтеза систем автоматического управления, хотя и хорошо исследована математически. Потребности практики заставляют искать иные, более эффективные пути решения задачи параметрической адаптации. Рассмотрим некоторые из них.

1.4.2 Сглаживание помех

Идея сглаживания, примененная в п. 15.5.2.1. для решения многоэкстремальных задач, может быть использована и для сглаживания случайных помех. Действительно, сглаженный функционал

(15.6.6)

отличается от исходного Q(C), не возмущенного помехами, за счет двух обстоятельств - процедуры сглаживания и наличия помех. Его монтекарловская оценка имеет вид

(15.6.7)

где Yi - случайные реализации вектора Y в соответствии с его заданной плотностью распределения p(Y) (15.5.6).

Легко видеть, что случайная составляющая сглаженной функции имеет [15.12] пониженную дисперсию, равную 2/N , где 2 - дисперсия случайной помехи в (15.6.1).

Аналитическая форма задания плотности распределения дает возможность (16.13) оценить градиент сглаженной «зашумленной» функции (15.6.6). Для этого достаточно аналогично изложенному в п. 15.5.2.1 продифференцировать (16.6.6) по С. Получаем формулу для численной оценки градиента зашумленного функционала по его наблюдениям в виде (15.5.10), где вместо Q(.) надо подставить Q`(.). Однако оценку градиента зашумленного минимизируемого функционала можно получить и иным образом.

1.4.3 Стохастическое накопление

Воспользуемся для вычисления градиента его стохастической оценкой (15.2.6), где вместо Q(C) следует поставить Q`(C). Проекция этой оценки на градиентное направление имеет определенные статистические характеристики (15.12). Ее среднее значение равно модулю градиента, а дисперсия определяется выражением

(15.6.8)

где k - модуль градиента функционала. Дискретный вариант такой адаптации, когда каждый параметр варьируется на двух уровнях, рассмотрен в работе (15.2).

1.4.4 Последовательное накопление

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

(15.6.9)

заданного порога

||R[N*]||A (15.6.10)

Полученные значения N* определяют оценку вектора градиента

(15.6.11)

Эта оценка будет тем точнее, чем больше порог А.

Порог A иногда удобно определять не для модуля R[N], а для всех его компонент ri[N], i=:

R[N]=[r1[N] ... rn[N]]T. (15.6.12)

При

||rj[N]||A (15.6.13)

принимается решение о рабочем шаге вдоль j-й координаты, которая изменяется следующим образом:

система автоматизированный управление проектирование

xj[N+1]=xj[N]-a sgn rj[N], (15.6.14)

а по остальным продолжается накопление информации. При этом начальное значение суммы для i-й координаты может отличаться от нуля, чем вводится адаптация к направлению наиболее интенсивного уменьшения минимизируемого функционала.

1.4.5 Симплексный алгоритм поиска

Этот алгоритм отличается тем, что на каждом N-M шаге хранится не одна, а n+1 точек вершин симплекса (n+1)-гранной пирамиды в n-мерном пространстве параметров {C}:

S[N]=<C0[N], C1[N], ..., Cn[N]>, N=0,1, ... (15.6.15)



Эта пирамида может быть «равносторонней» (см. Рис. 15.6.1.а) или «прямоугольной» (см. Рис. 15.6.1.б). Алгоритм симплексного поиска состоит в том, что на каждом (N+1)-м шаге новый симплекс S[N+1]

C2 C2

C1[N] C3[N ] C2[N]

S[N+1 ]

S[N] S[N] S[N+1]

C2[N] C0[N] C1[N] C0[N] C4[N]

a C1 b C1

Рис. 15.6.1. Иллюстрация симплексного метода поиска

образуется из «старого» S[N] путем добавления одной точки Cn+1[N] и исключением Cj[N]S[N]. Исключается точка с максимальным значением показателя качества ( в случае его минимизации, а при максимизации надо исключать точку с минимальным значением критерия), т.е.

(15.6.16)

а новая Cn+1[N] образуется симметрично основанию симплекса S[N]\Cj[N]. На рис. 15.6.1 показаны примеры образования нового симплекса S[N+1] из S[N] ( на рис. a i=2, a на рис. б i=1). В (15.15) приведены формулы для вычисления координат новой точки Cn+1[N] равностороннего симплекса. Приведем формулы для прямоугольного симплекса.

Пусть точка C0[N] соответствует вершине прямого угла симплекса (см. 15.6.1,б), а bi(i=) - величина i- ребра симплекса, направленного вдоль i-й координаты Сi. Тогда положение прямоугольного симплекса однозначно определится вершиной С0[N] и вектором A[N]=[a1[N], ...,an[N]]т , координаты которого определяют направление ребер симплекса:

ai[N] {-1, +1}, i= (15.6.17)

(так, например, для симплекса на рис. 15.6.1, б имеем a1[N]=1, a2[N]=-1. Вершина симплекса S[N],таким образом, имеют вид:

Ci[N]=C0[N]+ai[N]biei, i=, (15.6.18)

где ei - i-й орт.

В соответствии с алгоритмом симплексного метода поиска получаем

(15.6.19)

Напомним, что j - номер точки симплекса S с максимальным значением показателя качества.

Однако при использовании этих формул ввиду сложности минимизируемого функционала и наличия случайных помех возможно образование тупиковых ситуаций

Может оказаться, что точка Cn+1 имеет минимальное значение критерия, т.е. Cj[N+1]=Cn+1[N], и тогда в соответствии с алгоритмом перехода к S[N+1] мы вернемся к исходному симплексу S[N], т.е. S[N+2]=S[N]. Выход из этой ловушки осуществляется исключением точки Cj[N+2] из множества точек, среди которых ищется по (15.6.16) точка с максимальным значением показателя качества.

Может оказаться, что одна из точек сохраняется в симплексе более чем n+1 шагов, за которые при нормальной работе метода все точки должны обновиться. В результате происходит так называемое «вращение» симплекса относительно этой точки. Следует повторить определение критерия в это точке. Если значение критерия при этом изменится существенно ( и вращение должно продолжаться), то это означает, что точка вращения расположена вблизи экстремума и следует уменьшить симплекс

(15.6.20)

подтянув его к этой точке. Так происходит адаптация размеров симплекса.

1.5 Структурная оптимизация

Задача автоматического проектирования САУ включает в себя и определение структурных факторов. Они могут быть определены в процессе решения оптимизационной задачи (15.1.5) Для этого необходимо построить процесс поиска оптимальной структуры W. Такого рода процесс поиска можно осуществить двояким образом - дискретизацией структуры и путем ее эволюционной оптимизации.

1.5.1 Дискретизация структуры

Если структура образуется набором структурных элементов, то ее удобно кодировать двоичным вектором

W=(1, ..., n), (15.7.1)

где i характеризует наличие (i=1) или отсутствие (i=0) i-го структурного элемента в проектируемой САУ. На вектор W могут быть наложены ограничения типа равенств и неравенств, характеризующие зависимость между структурными элементами. Тогда задача проектирования САУ сводится к решению следующей оптимизационной задачи:

(15.7.2)

где ограничения S имеют вид

(15.7.3)

Здесь функционалы Q, gj и hi определяются характером задачи проектирования конкретной САУ.

Как видно, задача проектирования сведена к задаче бинарного программирования, решение которой при малых n возможно полным перебором, а при больших - путем сведения дискретной задачи к непрерывной и дальнейшим решениям ее методами параметрического поиска, рассмотренными выше. Сделать это можно, например, введением штрафной функции вида :

(15.7.4)

где v>0 - коэффициент штрафа, а область S` определена условиями

(15.7.5)

где wh - непрерывный параметр. Задача (15.7.4) имеет многоэкстремальный характер и решается глобальными методами.

Другим способом сведения дискретной задачи (15.7.2) и непрерывной является рандомизация, в соответствии с которой вводится непрерывный вектор вероятностей

P=P1, ..., Pn), (15.7.6)

в котором

Pk=P{wk=1} (15.7.7)

-вероятность события wk=1. С помощью этого вектора функционал Q(W) сглаживается:

(15.7.8)

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

(15.7.9)

Сглаженный (или рандомизированный) функционал Q(W) зависит лишь от непрерывного вектора вероятностей Р. Легко видеть, что минимум этого функционала лежит в одной из вершин гиперкуба {P}, т.е. решение Pоп является двоичным вектором, который совпадает с решение исходной задачи. Для приближенной оценки значения сглаженного функционала при заданном Р можно воспользоваться методом Монте-Карло:



где N база оценки, а Wi случайный двоичный вектор распределения Р. С ростом N точности оценки естественно возрастает.

1.5.2 Эволюционная оптимизация структуры

Если структура W проектируемой системы может изменяться так, что будут соблюдаться ограничения S, накладываемые на структуру, то синтез такой структуры может быть реализован так называемым эволюционным методом. При этом вариации структуры не выводят за пределы заданных S, т.е.

W+S (15.7.10)

Задача структурной оптимизации записывается в виде

(15.7.11)

Процесс эволюции структуры W происходит поэтапно. На первом этапе порождаются измененные структуры:

W0.i=W0+i, i=1, k0, (15.7.12)

где i i-я случайная вариация структуры, ограниченная (15.7.10). Число новых структур k0- является параметром, который назначается из конкретных условий эволюции данной структуры.

Новые структуры (15.7.12) оцениваются по критерию эффективности



Q0.i=Q(W0.i), i=1, k0 (15.7.13)

и далее происходит отбор, в процессе которого отсеиваются структуры с большим значением минимизируемого функционала Q, в результате чего на следующий этап эволюции остаются q0<k0 структур. Можно применять алгоритм вероятностного отбора, при котором структура, имеющая большее значение минимизируемого критерия, выбывает с большей вероятностью, чем структура с меньшим значением критерия. Вероятность такого выбора для Q>0 может быть определена соотношением

(15.7.14)

При этом процесс «разыгрывания» выбывающих структур заканчивается тогда, когда остается q0 структур.

Заметим, что вполне может оказаться (особенно при малом k0), что лучшая из новых структур хуже исходной W0. В этом случае естественно W0 сохранить на следующий этап эволюции.

На втором этапе эволюции каждая из остающихся структур изменяется аналогично (15.7.12) и дает столько новых структур, чтобы их общее число вместе с исходными было равно k0. Последующий отбор составляет q1 структур на следующий этап эволюции, и т.д.

Легко видеть, что такого рода эволюция структуры будет стремиться отбирать структуры с малым значением критерия качества, среди которых находится и оптимальная структура. Случайность вариаций и отбор обеспечивают целенаправленность процесса эволюции к оптимальному решению Wоп.

Рассмотрим влияние параметров ki и qi (i=0,1, ...). Эти параметры позволяют изменять число структур на каждом этапе и уровень отбора. При qi=1 на следующий этап эволюции оставляется лишь одна структура. Такая структура эффективна при унимодальности задачи(15.7.11). Ее многоэкстремальность требует qi>1 и значение qi тем больше, чем сложнее поиск глобального экстремума. Число ki также влияет на эффективность процесса эволюции. При большем ki эволюция имеет глобальную тенденцию, но идет медленней, т.е. требует значительных затрат времени и памяти ЭВМ.

Здесь изложены примеры структурной оптимизации без параметрической подстройки параметров С объекта. Параметрическая оптимизация, если она необходима для повышения эффективности структур, легко вводится перед стадией отбора и осуществляется параметрическими методами, рассмотренными выше.

Рассмотрим в качестве примера структуры, описываемые графом. В этом случае в процессе оптимизации оптимизирует граф.

Пусть структура W объекта описывается графом

Г=<А,В>, (15.7.15)

где А - множество из n его вершин, а В - множество ребер с их параметрами:

В=[bij]nXn, (15.7.16)

где bij - параметры дуги, соединяющей i-ю и j-ю вершины. На графе Г задан функционал качества, который следует минимизировать:

(15.7.17)

где S - ограничения, которым должен удовлетворять оптимизируемый граф Г.

Опишем множество вариаций графа . Например, оно может состоять из следующих изменений:

объединение двух случайно выбранных вершин графа в одну;

введение новой (n+1)-й вершины со случайными связями bn+1, i(i=) и bj,n+1 (j=);

устранение случайно выбранной вершины вместе с ее связями;

введение новой связи двух случайно выбранных вершин;

устранение случайно выбранного ребра;

случайное «переключение» случайно выбранного ребра и т.д.

Как видно, спектр возможных случайных вариаций графа может быть достаточно велик, что обеспечивает эволюции большое разнообразие, необходимое для отыскания оптимального графа. Значения параметров дуг графа (15.7.16) могут подстраиваться специально на стадии параметрической оптимизации, предшествующей отбору лучших структур.

Это направление эволюционной оптимизации графа интенсивно развивается в настоящее время и получило название эволюционного моделирования, что связано с оценкой функционала Q(Г) путем моделирования поведения системы, работа которой описывается этим графом (15.14).

2. Автоматизация проектирования систем автоматического управления

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

В процессе этого развития пока не созданы унифицированные установившиеся структуры систем автоматизированного проектирования (САПР) САУ, и поэтому здесь излагаются основные принципы и некоторые способы построения САПР САУ, пригодные для проектирования как непрерывных, так и цифровых систем ограниченного уровня сложности.

2.1 Принципы автоматизации проектирования систем автоматического управления

Здесь рассматриваются наиболее общие вопросы автоматизированного проектирования САУ, основные этапы, уровни автоматизации процесса проектирования.

2.1.1 Этапы и стадии проектирования

Процесс проектирования систем автоматического управления, как и любой технической системы, можно разделить 916.1, 16.2) НА СЛЕДУЮЩИЕ ЭТАПЫ.

1 ЭТАП- разработка и обоснование технического задания(ТЗ) на систему, в процессе которой определяется цель и назначение системы управления, задаются характеристики и модель объекта управления, формулируются технические требования к системе и ее технико-экономические показатели.

2 ЭТАП - разработка технического предложения, на этом этапе выбирается один или несколько вариантов построения систем управления и дается оценка выполнимости требований ТЗ.

3 ЭТАП - разработка эскизного проекта, когда осуществляется синтез устройства управления и анализ выполнения требований ТЗ.

4 ЭТАП - техническое проектирование. На этом этапе, используя выбранные структурные схемы и определенные на третьем этапе параметры, разрабатываются принципиальные электрические (электромеханические, кинематические) схемы отдельных блоков системы и осуществляется анализ уточненной системы с учетом математических моделей готовых и разрабатываемых блоков (под блоками системы понимаются измерительные и исполнительные устройства, средства реализации алгоритма управления, аналого-цифровые и цифро-аналоговые преобразователи и т.п.). Если результаты такого анализа показывают, что система не удовлетворяет требования ТЗ, то осуществляется уточнение параметров устройства и управления (параметрический синтез).

5 ЭТАП - конструкторское проектирование (разработка рабочих чертежей). Здесь на основе принципиальных схем разрабатываются чертежи для изготовления опытного образца создаваемой системы.

6 ЭТАП - технологическое проектирование и изготовление опытного образца.

7 ЭТАП - экспериментальное исследование опытного образца, в результате которого в конструкторскую и технологическую документацию, разработанную на предыдущих этапах, вносятся изменения.

Отметим, что процесс проектирования САУ, как и любого технического устройства, носит характер последовательных приближений к требованиям, сформулированным в ТЗ. Это означает, что каждый этап проектирования может заканчиваться не переходом к следующему, а возвратом к любому из предыдущих этапов, и, таким образом, спроектированная система является результатом целого рядя итераций.

Cодержание 5-го и 6-го этапов проектирования слабо связано со спецификой задач автоматического управления, и поэтому проблемы проектирования на этих этапах решаются в рамках задач проектирования технических устройств (электрических, механических, гидравлических и т.п.), на базе которых строится устройство управления.

Центральным и специфически характерным для САУ является 3-й этап проектирования, который будет называться этапом анализа и синтеза системы управления.

Этот этап можно разбить на несколько стадий (16.3):

Преобразование, анализ и упрощение математической модели объекта (ММО). Вначале осуществляется преобразование МО, заданной в произвольной форме, к форме удобной для последующего анализа объекта и синтеза устройства управления. К числу таких преобразований относятся: приведение уравнений к форме Коши, к форме «вход-выход», построение передаточной матрицы, построение дискретной модели непрерывного объекта и т.д. Затем осуществляется анализ управляемости, устойчивости, минимально-фазовости и других свойств объекта. Упрощение ММО включает в себя понижение порядка (или числа) уравнений объекта, линеаризацию части или всех нелинейных его элементов, пренебрежение малыми изменениями параметров и т.п.

Классификация и формализация задачи управления. На этой стадии принимается решение о методе синтеза алгоритма управления (алгоритма работы управляющего устройства) и осуществляется формализация задачи в соответствии с принятым методом синтеза.

Синтез алгоритма управления. Он осуществляется в соответствии с принятым выше методом синтеза. В качестве таких методов часто выступают изложенные в предыдущих главах методы современной теории управления.

Анализ синтезированной САУ. Вначале осуществляется анализ САУ в условиях, при которых она была синтезирована, а затем с учетом факторов, опущенных при упрощении ММО (анализ в «реальных условиях»).

Как процесс проектирования в целом, так и выполнение каждого этапа и, в частности, этапов анализа и синтеза носят итерационный характер (результат выполнения определенной стадии может привести как к выполнению последующей, так и к возврату к предыдущей стадии) до тех пор, пока не будут выполнены требования ТЗ.

2.1.2 Уровни автоматизации проектирования

Для автоматизации процесса проектирования на 2-7 этапах широко используются ЭВМ. Последующее изложение будет посвящено в основном вопросам использования ЭВМ для автоматизации третьего этапа проектирования, поскольку автоматизация проектирования последующих этапов незначительно зависит от особенностей задач автоматизированного управления. Кроме того, широкое применение цифровых управляющих машин для реализации алгоритмов управления приводит к тому, что процесс проектирования САУ часто заканчивается четвертым этапом, в течении которого выбирается тип управляющей машины и устройства связи с объектом и осуществляется программирование синтезированного алгоритма управления.

Можно выделить следующие уровни автоматизации:

уровень (уровень отдельных прикладных программ) характеризуется автоматизацией отдельных операций стадий анализа и синтеза. Эти операции далее называются элементарными проектными операциями (ЭПО). Каждый программный модуль ЭПО позволяет решить с помощью ЭВМ содержательную в терминах ТАУ задачу. К числу таких задач относятся, например, приведение уравнений объекта к форме Коши, аналитическое конструирование оптимальных регуляторов, анализ устойчивости системы и т.п.;

уровень (уровень пакетов прикладных программ), когда объединение программных модулей ЭПО в пакет прикладных программ позволяет автоматизировать отдельную стадию или весь этап проектирования;

уровень - САПР САУ.

Выделим некоторые признаки, отличающие САПР от предыдущих двух уровней автоматизации.

Комплексность (или системность). Этот признак заключается (16.4) в том, что автоматизация проектирования должна пронизывать весь процесс проектирования от «завязки» проекта САУ (разработки технического предложения) до выпуска рабочих чертежей деталей системы, обеспечивающих ее изготовление, либо программ для управляющей ЭВМ, если процесс проектирования не содержит пятого этапа. Этот признак подразумевает возможность включения САПР САУ в САПР объекта управления.

Простота общения с ЭВМ. Это означает наличие : а) технических средств (например, дисплея), б) входного языка, близкому к естественному профессиональному языку пользователя, в) средств вывода информации на ЭВМ в форме, близкой к принятой документальной, г) возможности диалога с ЭВМ, в процессе которого пользователь может получать промежуточные результаты, изменять ход дальнейших вычислений, а также исходные промежуточные данные, не повторяя без необходимости проделанных вычислений заново.

Быстродействие, под которым подразумевается достаточно малое время (3-5 мин) выполнения ЭВМ каждого этапа проектирования. Это время необходимо для осуществления диалога пользователя (специалиста в области ТАУ - на третьем этапе, инженера-электрика или инженера-механика - на четвертом этапе, конструктора - на пятом этапе и технолога - на шестом этапе) с ЭВМ в естественном для человека ритме.

2.1.3 Компоненты обеспечения САПР

Комплекс средств обеспечения САПР содержит (16.5,16.6) компоненты: математического (методологического), лингвистического, программного, технического, информационного обеспечения.

Остановимся подробнее на некоторых компонентах.

Компонентами методологического обеспечения САПР САУ являются документы, в которых изложены способы и методы ТАУ, позволяющие построить программные модули элементарных проектных операций (ПМ ЭПО) и указать способ объединения ПМ ЭПО в некоторый программный модуль процедуры (ПМП), разрешающий определенный класс задач ТАУ.

ЭПО - это неделимый (минимальный) содержательный фрагмент ТАУ: Как правило, ЭПО представляет собой операционное определение понятия ТАУ. Такое операционное определение может быть не единственным. Например, устойчивость линейной стационарной системы может определяться как с помощью построения функции Ляпунова, так и непосредственно вычислением собственных чисел матрицы, входящей в модель системы, записанной в форме Коши, и поэтому ЭПО «Анализ устойчивости» имеет два варианта реализации.

Опишем теперь понятие класса задач ТАУ (16.7). Класс задач ТАУ характеризуется тремя видами математических моделей : модель целей управления (критерии точности, качества и т.п.). модель объекта управления и управляющего устройства (регулятор), модель среды (внешние возмущения и помехи). Каждая из этих моделей характеризуется атрибутами 1-го, 2-го и т.д. рангов. Так, атрибутом 1-го ранга модели объекта управления является тип оператора модели (линейный или нелинейный оператор), атрибутом 2-го ранга - вид уравнений модели объекта управления (алгебраические, обыкновенные дифференциальные, дифференциально-разностные, интегральные, в частных производных), атрибутами 3-го ранга являются начальные отклонения, параметрические и структурные возмущения модели.

Указанные три модели с их атрибутами образуют класс задач ТАУ. Совокупность классов задач, решаемых конкретной САПР САУ, определяет ее функциональные возможности.

Компонентами лингвистического обеспечения являются документы, содержащие словарь входного языка, синтаксический и семантический процессор (16.8). Словарь входного языка содержит термины ТАУ, математические символы, используемые при описании моделей системы управления, возмущений и цели управления и их атрибутов, а также отдельные слова естественного языка, необходимые для описания требований к системе управления. Входной язык разделяется (16.2) на язык описания системы управления (язык описаний объекта (ЯОО) и язык описания заданий (ЯОЗ).

Компонентами программного обеспечения САПР САУ являются документы с текстами программных модулей процедур, разрешающих отдельные классы задач ТАУ. Программный модуль процедуры, решающий некоторый класс задач ТАУ, состоит из ПМ ЭПО, выполняемых в последовательности, образующей план решения класса задач ТАУ. План решения часто зависит от конкретных параметров моделей.

2.1.4 Общие принципы построения САПР

Процесс создания САПР САУ базируется на следующих общих принципах (16.5): включения, системного единства, комплексности, развития, информационного единства, совместимости, инвариантности.

Смысл первых трех принципов во многом исчерпывается описанием приведенного выше 1-го признака САПР. Принцип развития требует, чтобы САПР САУ разрабатывалась и функционировала как развивающаяся система. Это, в частности, означает, что расширение функциональных возможностей САПР САУ (т.е. увеличение числа классов решаемых задач ТАУ) не должно приводить к переработке программных модулей действующих (до расширения) процедур.

Принципы информационного единства, совместимости и инвариантности состоит в том, что различные САПР САУ (САПР САУ различных классов задач ТАУ) должны использовать единую терминологию, символы, условные обозначения, способы представления информации, а программное обеспечение третьего и четвертого этапов проектирования не должно зависеть от физической природы системы управления. Построение САПР САУ с использованием этих принципов позволяет создать интегрированную САПР САУ, охватывающую в пределе всю совокупность задач ТАУ.

2.2 Способы построения систем автоматизированного проектирования

В 60-х и 70-х годах было разработано большое количество программ, обеспечивающих первый (16.9-16.11) и второй (16.12-16.16) уровни автоматизации проектирования САУ. В последние годы ведутся интенсивные работы по созданию различных САПР САУ. Из этих систем выделим наиболее характерные, отражающие распространенные способы построения САПР САУ: диалоговую систему проектирования автоматических систем (ДИСПАС) (16.17); САПР адаптивных систем (16.18); диалоговый пакет прикладных программ «Гамма-1М» для синтеза и анализа линейных многомерных систем управления по заданной точности и качеству (16.19).