Оптимального управления 1 страница

Вычислительные методы решения задач

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

Впервые математически сформулированные эти вопросы яв­лялись задачами вариационного исчисления, которое и обязано им своим возникновением [12]. В классическом вариационном исчислении нет, однако, решения целого ряда вариационных задач, важных для современной техники. Поэтому стали появ­ляться другие методы, например, объединенные одним общим математическим приемом, который называется принципом мак­симума [13]. В настоящее время, в связи с бурным развитием средств вычислительной техники, наиболее популярны различные вы­числительные методы оптимизации, например, методы динами­ческого программирования [14], математического программиро­вания [8, 15] или так называемые генетические алгоритмы [16].

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

dxi/dt = fi(x₁ х₂ ,..х_n, i = 1, 2, … n, (1.33)

где x₁ х₂ ,..х_n — величины, характеризующие процесс, т.е. фазовые координаты объекта управления, определяющие его состояние в каждый момент времени t, а, — пара­метры управления (в том числе и настраиваемые параметры ре­гуляторов), определяющие ход процесса.

Для того чтобы ход управляемого процесса был определен на некотором отрезке времени достаточно, чтобы на этом отрезке времени были заданы как функции времени пара­метры управления:

(1.34)

Тогда при заданных начальных условиях

(1.35)

решение системы (1.33) определяется однозначно. Подлежащая решению вариационная задача, связанная с управляемым про­цессом (1.33), заключается в следующем.

Рассматривается интегральный функционал:

где — заданная функция.

Для каждого управления (1.34), заданного на некотором от­резке времени t₀ < t < t_t однозначно определяется ход управляе­мого процесса, и интеграл (1.36) принимает определенное зна­чение.

Допустим, что существует управление (1.34), переводящее объект управления из заданного начального фазового состояния (1.35) в предписанное конечное фазовое состояние:

x_i(t₁)= х_i1, i = 1, 2,..., п. (1.37)

Требуется отыскать управление

u_j(t), j = 1, 2,..., т, (1.38)

которое осуществит перевод объекта управления из состояния (1.35) в состояние (1.37) таким образом, чтобы функционал (1.36) имел минимальное значение. При этом моменты времени t₀, t₁ не фиксируются, а требуется только, чтобы в начальный момент времени объект находился в состоянии (1.35), а в конечный — в состоянии (1.37) и чтобы функционал (1.36) достигал мини­мума (возможен случай, когда t₀, не фиксированы).

В технических задачах параметры управления не могут при­нимать любые произвольные значения. Поэтому для любой точ­ки, характеризующей текущее значение управления, должно вы­полняться условие (u₁..., u_m) U. Причем выбор множества U должен отражать специфику объекта управления. Во многих тех­нических задачах это множество замкнуто. Введение подобных ог­раничений приводит к неклассическим задачам вариационного исчисления, которые лучше решать вычислительными методами.

Часто встречаются задачи об оптимальном переходе объекта управления из некоторого начального многообразия М_а точек фазового пространства на некоторое конечное многообразие M_v причем размерности этих многообразий могут быть произволь­ными. В частности, когда оба многообразия равны нулю, то мы приходим к исходной задаче.

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

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

Допустим, что в фазовом пространстве имеется движущая точка

(1.39)

Тогда возникает задача об оптимальном приведении объекта (1.33) в совпадение с движущейся точкой (1.39). Эта задача легко сводится к первой, если ввести новые переменные, положив:

i= 1, 2... п. (1.40)

В результате этого преобразования система (1.33) превра­щается в новую, правда уже не автономную, а целью управле­ния становится приведение объекта у_{ у₂,..., у_п в неподвижную точку (0, 0,..., 0) фазового пространства.

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

Весьма важным представляется случай, когда преследуемый объект является управляемым и его движение описывается сис­темой дифференциальных уравнений:

d /dt = (z₁, z₂,.., z_n,u₁ и₂,..., u_m ) (1.41)

Задача управления заключается в том, чтобы, зная техни­ческие возможности преследуемого объекта, т. е. систему урав­нения (1.41) и его положение в каждый данный момент време­ни, определить управление преследующего объекта в тот же момент времени так, чтобы преследование осуществлялось оп­тимальным образом. В такой постановке задача рассматривается в теории дифференциальных игр [17, 18]. При этом предпола­гается, что в начальный момент времени положение преследу­емого объекта известно, а дальнейшее его поведение описыва­ется вероятностным образом и процесс его движения считается марковским. В этих предположениях ищется такое управление пре­следующим объектом (1.33), при котором встреча некоторой ма­лой окрестности объекта (1.33) с преследуемым объектом (1.41) или его малой окрестностью являлась наиболее вероятной.

Указанная задача может быть обратной, т. е. ищется управ­ление для преследуемого объекта (1.41), такое, чтобы встреча некоторой малой окрестности объекта (1.41) с преследующим объектом (1.33) или его малой окрестностью являлась наименее вероятной. Более того, может быть задача, когда преследующих объектов несколько. Все эти задачи относятся к теории диффе­ренциальных игр, а оптимальное решение ищется в условиях неполной определенности.

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

Таким образом, при синтезе сложных систем управления обычно необходимо решать задачи принятия решения (ЗПР) об оптимальности системы. Для случаев, когда удается указать шка­лу — целевую функцию, значение которой определяет решение, известны и хорошо развиты теория и методы математического программирования [19], позволяющие проводить качественный и численный анализ возникающих при этом четких задач опти­мизации решения. Учет неопределенностей, которые могут воз­никать при решении задач принятия решения при управлении сложными объектами, функционирующими в плохо формали­зуемой среде, позволяет применять указанные методы матема­тического программирования с большим или меньшим успехом и в этих случаях.

Рассмотрим наиболее популярные вычислительные методы принятия решений.

• Математическое программирование (МП).

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

В задаче МП требуется вычислить n-мерный вектор X, оп­тимизирующий (обращающий в максимум или минимум в зависимости от содержательной постановки задачи) критерий качества решения (x) при соблюдении ограничений (x) где f— известные скалярные функциона­лы, и — заданные числа, G — заранее заданное множество п- мерного пространства.

Таким образом, задача МП имеет вид:

(1.42)

В зависимости от свойств функции f = < /₀, /,, •••, /„ > и множества G будет тот или иной класс задач оптимизации. Если все функции f— линейные, a G- многогранное множе­ство, то это задачи линейного программирования (ЛМП). Если среди функций f встречаются нелинейные, то это задачи нели­нейного программирования (НМГ1). Среди нелинейных экстре­мальных задач выделяют выпуклые задачи (ВЗНМП), в которых максимизации подлежат вогнутые функции f_n(x) при вогнутых функционалах ограничений f(x) и выпуклой области G. Задачи, в которых G имеет конечное или счетное число точек, выделе­ны в специальный раздел математического программирования — целочисленное или дискретное программирование (ДМП). Если функционал f₀ квадратичный, а все остальные функции f ли­нейные и G многогранное множество, то это задачи квадратич­ного программирования (КМП), которые можно привести к задачам (ЛМП) при использовании теоремы Куна-Таккера [8].

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

• Математическое программирование в порядковых шкалах (МППШ).

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

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

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

Пусть G — некоторое фиксированное компактное множество в — рефлексивные, транзитивные и пол­ные бинарные отношения в шаре, содержащем G предпочтения, g₀— предпочтение лица, принимающего решение. При этом —могут интерпретироваться как предпочтения лиц, ограничивающих, каждый по-своему, множество допус­тимых планов. Некоторые из отношений g_j могут определяться обычными функциональными неравенствами, ограничивающими диапазоны изменения различных компонент решения.

Обозначим через и_i, j = 1, 2,..., r — заданные априори точки G и будем считать, что план х G допустим по j-му ограничению, если xg_j и_j. т. е. если пара (х, u_j) g_jСоответствен­но назовем точку х G допустимым решением, если х g_j и_j, j = 1, 2,..., r.

Задача МППШ представляет собой задачу выбора "наилуч­шего" (в смысле бинарного отношения g_Q) среди допустимых ре­шений. В ней требуется найти одно из решений х* — такое, что:

методы МП. Однако точное вычисление P(C_QQ) даже при неболь­шом числе логических переменных q_j представляет собой весьма трудоемкого задачи, которую целесообразно решать приближен­но [1]. Кроме того, иногда вместо вероятностных оценок реше­ний уравнений типа: C₀Q = 0 используют минимаксные оценки достоверности V(С₀ Q), которые вычисляют, используя правила:

V() = max{V(), V()} и = min{V(), V()}.

Большинство нелинейных задач МППШ не имеет процеду­ры решения приемлемой трудоемкости. Однако для задач вы­пуклого МППШ, т. е. для задач, в которых множество G выпук­ло, а предпочтения g, j = 0, 1, 2,..., r — вогнуты, разработан диалоговый метод решения. Такая процедура позволяет по пос­ледовательно предъявляемым альтернативам и получаемой ло­кальной информации о предпочтениях g на соответствующих парах вариантов получить е приближенное решение задачи. При расширении понятия "оптимизация по бинарному отношению" и расширении понятия " оптимальное по g₀ решение", удается обобщить метод решения выпуклой задачи МППШ на случай произвольных (нерефлексивных, неполных и нетранзитивных) бинарных отношений [19]. Ожидается, что значительного про­гресса в решении задач МППШ удастся достичь за счет приме­нения нейронных сетей.

* Обобщенное математическое программирование (ОМП).

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

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

Формально запись модели ОМП имеет вид:

где f(x), j = 0, 1, 2,..., r— вектор-функции в R^m_j, и, — фиксиро­ванный вектор в R^m, g.,j =0, 1,2,..., r— бинарные отношения на G с R".

Модель ОМП соответствует выбору объектов, основанному на сравнении его характеристик, тогда как МППШ соответствует выбору объектов, производимому при непосредственном срав­нении пар объектов. Поэтому структура модели ОМП значительно сложнее.

К модели ОМП можно прийти в задачах оптимального уп­равления системами логико-лингвистического типа, если при выборе оптимального решения системы логических уравнений требуется анализировать сложные лингвистические выражения, являющиеся атрибутами (w*, w) или формируемые из атрибу­тов (w*, w) логических переменных q и q*, характеризующих ре­шения (х*, х). При этом, если указанные лингвистические выра­жения могут быть сведены к логическим выражениям вида f. = C.Y, где С — идентификационная строка из 0 и 1, Y— век­тор, компонентами которого являются конъюнкции логических переменных, характеризующих решения (х*, х), то решение мо­жет быть автоматизировано программными средствами искусст­венного интеллекта [20]. Кроме того, к модели ОМП можно прийти и в процессе решения задач оптимизации управления эволюционно-генетического типа, если в процессе эволюции сохранять неизменными предпочтения ЛПР.

Однако для получения приемлемой трудоемкости решения задач ОМП необходимо, чтобы характеристики вектор-функ­ции , области определения решения G и используемые би­нарные отношения удовлетворяли некоторым специальным требованиям. Так, конструктивные методы анализа задач ОМП построены для случаев, когда составляющие вектор-функции f(x) — линейные или вогнутые функции, G— выпуклое множе­ство, а бинарные отношения g — непрерывные, вогнутые, мо­нотонные и регулярные предпочтения. Такие модели ОМП на­зывают моделями обобщенного выпуклого программирования (ОВП). Решение задач ОМ П в настоящее время связывают с использованием нейронных сетей и сред типа A- life.

• Многошаговые задачи обобщенного математического про­граммирования (МнОМП).

В предыдущем случае функция выбора (ФВ), определяемая предпочтениями ЛПР, была постоянна. Многошаговая схема обоб­щенного математического программирования может реализовывать произвольную ФВ на конечном множестве вариантов. Схема МнОМП предполагает некоторое расширение понятия "задача ОМП". Это расширение сводится к тому, что допустимое мно­жество решений разрешается получать из множеств решений, выделяемых отдельными ограничениями задачи (xgu_j), не толь­ко их пересечением (уничтожение плохих особей в системе A-life), но и их объединением (скрещивание особей в системе A-life). К МнОМП можно прийти в задаче оптимизации управ­ления эволюционно-генетического типа при изменяющихся предпочтениях ЛПР.

Схема МнОМП представляет собой множество задач ОМП, каждая из которых отвечает фиксированному предъявлению X. При этом решение исходной задачи ОМП может быть принято в каче­стве входа (предъявления) для другой задачи ОМГ1 и т. д. Таким образом, приходим к последовательной многошаговой схеме ОМП. Однако последовательная схема не реализует все ФВ. В частности, в рамках последовательной схемы не могут быть сформированы некоторые экстремальные задачи, например задача о минимаксе. Недостаток последовательной схемы можно устранить, если раз­решить использование на шаге t результатов предыдущих шагов.

Для построения схемы МнОМП с большим числом шагов изменения ФВ с заданной точностью требуется чрезмерно мно­го наблюдений за реализациями ФВ. Кроме того, вычислитель­ная сложность решения задач МнОМП быстро растет с увеличе­нием числа шагов. Поэтому возникает проблема аппроксимации ФВ функциями, реализуемыми более простыми механизмами, такими, например, как схема безусловной оптимизации по би- нарному отношению (уничтожение худшей из двух особей пос­ле скрещивания), одно-, двух- и т. д. шаговые схемы ОМГ1 (унич­тожение худших после первого, второго и т. д. шагов эволюции). Однако использование современных систем типа A-life позволя­ет достичь определенного прогресса в решении задач МнОМП.

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

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

Рассмотренные вычислительные методы не исчерпывают все возможные методы решения задач оптимизации управления. Однако они являются наиболее продвинутыми в теоретическом плане и в части реализации с помощью интеллектуальных про­граммных систем [1, 20]. Поэтому изложенные методы могут рассматриваться как конструктивная основа рационального вы­бора решений подобных задач. Кроме того, в зависимости от решаемого типа задачи можно с большим или меньшим успе­хом использовать готовые вычислительные алгоритмы и соответ­ствующие инструментальные программные средства, среди ко­торых в настоящее время широко применяются нейронные сети и программные системы A-life с генетическими алгоритмами.

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

УПРАВЛЯЮЩИЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ

2.1 Обобщенное описание

Структура ЭВМ, получившая имя Дж. фон Неймана, была описана им в "Первом наброске отчета по ЭДВАКу" (First Draft jf a Report on the ED VAC, 1945 г.). В нем приводится, ставшее впоследствии классическим, деление компьютера на арифметическо-логическое устройство, устройство управле­ния и память. Здесь же высказана идея программы, хранимой в памяти.

Существенным недостатком машин фон Неймана является принципиально низкая производительность, обусловленная пос­ледовательным характером организации вычислительного про­цесса. Наличие одного процессора обусловливает и другой недо­статок этих машин — низкую эффективность использования памяти. В самом деле, память однопроцессорных ЭВМ можно представить как длинную последовательность ячеек. Централь­ный процессор выбирает содержимое одной из них, дешифри­рует, исполняет команду и, при необходимости, возвращает ре­зультат памяти в заранее обусловленную ячейку. Затем обращается к очередной ячейке для считывания следующей команды, и про­цесс повторяется до тех пор, пока не будет выбрана последняя команда исполняемой программы. Нетрудно заметить, что по­давляющее большинство ячеек памяти бездействуют. Если ввес­ти понятие коэффициента использования аппаратуры как отно­шение числа одновременно работающих элементов ЭВМ к общему числу этих элементов, то для машин фон Неймана этот коэффициент будет очень низким.

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

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

По мере преодоления технических проблем построения ком­пьютеров накапливались проблемы, связанные с их использо­ванием. Трудности сместились из области выполнения программ компьютера в область создания программ для компьютера. На­чались поиски языков программирования, пригодных для чело­века. Начиная с языка, воспринимаемого компьютером (машин­ного языка), стали появляться более удобные формализмы и системы обозначений. И хотя степень абстракции языков воз­растала, начиная с языка ассемблера и далее к Фортрану, Алго­лу, Паскалю, Аде и т.д., все они несут печать машины с архи­тектурой фон Неймана. Например, в однопроцессорной машине имеются процес­сор, оперативная память, внутренние часы (таймер), внешние часы, внешние устройства и шины: адресная, данных и управ­ления. Таймер вырабатывает сигналы одинаковой временной протяженности, которые используются при управлении внут­ренним потоком информации. Внешние часы используются для измерения работы пользователя и измерения времени, которое занимает выполнение тех или иных операций. Через определен­ные промежутки времени таймер генерирует прерывание и про­цессор опрашивает все активные устройства, вырабатывающие запросы на обслуживание процессором (прерывания). Устрой­ства обслуживаются в соответствии с установленными приори­тетами прерываний, и после обслуживания процессор удаляет выставленное устройством прерывание. Приоритеты могут из­меняться программно, и тогда изменяется порядок обслужива­ния. Таймер используется процессором и для разделения време­ни между программами (задачами). Дисциплина обслуживания может учитывать структуру оперативной памяти, количество поступивших на обслуживание программ и назначенные им при­оритеты. Дисциплина разделения времени может изменяться, если при выполнении программ определяются характеристики, которые учитываются при их дальнейшем выполнении. В тех слу­чаях, когда память организована постранично и программы, поступившие на обслуживание, могут быть все загружены в опе­ративную память, программам могут отводиться разные стра­ницы, и прерывание выполнения текущей программы и пере­ход к выполнению следующей программы происходят без выгрузки программы из оперативной памяти, иначе текущая программа выгружается из оперативной памяти и загружается следующая. Порядок выполнения программ определяется вы­бранным алгоритмом в соответствии с приоритетами и време­нем, уже затраченным на ее выполнение. Рассматривая сложные многопроцессорные машины для высокоскоростных вычислений, можно увидеть, что, несмотря на различную архитектуру, все управляющие вычислительные машины (УВМ) описываются с помощью обобщенной маши­ны фон Неймана, в основе которой лежат различные автомати­ческие системы дискретного действия для переработки инфор­мации и которые в кибернетике обычно называют "автоматами" или "конечными автоматами". Поэтому анализ и синтез указан­ных устройств основывается на теории систем дискретного дей­ствия, которая охватывает широкий круг вопросов, связанных с исследованием возможности автоматизации тех или иных процессов переработки информации, повышением производительности и надежности обработки информации и созданием эф­фективных методов их анализа и синтеза новой элементной базы.

Дата добавления: 2015-04-29