Содержание к диссертации
Введение
1. Постановка задачи 10
1.1. Формализация задачи 10
1.2. Обзор методов решения 13
1.3. Метод генетического программирования 15
1.4. Выводы к разделу 1 30
2. Метод сетевого оператора 31
2.1. Программная запись формулы 31
2.2. Графическая запись формулы 34
2.3. Сетевой оператор 37
2.4. Матрица сетевого оператора 48
2.5. Выводы к разделу 2 58
3. Алгоритм синтеза 59
3.1 Принцип базисного решения 64
3.2 Генетический алгоритм 70
3.2.1. Выбор конструктивных множеств 70
3.2.2. Выбор размерности сетевого оператора 74
3.2.3. Выбор базисного решения 76
3.2.4. Представление решения в виде хромосомы 79
3.2.5. Функция приспособленности 83
3.2.6. Отбор и репродукция новых хромосом 84
3.2.7. Завершение алгоритма 87
3.3. Пример синтеза системы управления 87
3.4. Выводы к разделу 3 102
4. Синтез системы стабилизации космического аппарата 104
4.1. Постановка задачи 104
4.2. Результаты вычислительного эксперимента 105
4.3. Выводы к разделу 4 132
Заключение 133
Список литературы 134
- Метод генетического программирования
- Графическая запись формулы
- Представление решения в виде хромосомы
- Результаты вычислительного эксперимента
Введение к работе
Работа посвящена решению задачи синтеза системы автоматического управления. Данная задача на протяжении многих лет является одной из ключевых проблем теории управления. Задача заключается в следующем. Задан объект управления, математическая модель которого описывается системой обыкновенных дифференциальных уравнений. Заданы критерии качества, представленные в виде интегральных функционалов и терминальных условий. Необходимо найти управление в виде функции координат пространства состояний, обеспечивающее оптимальное с точки зрения критериев качества функционирование объектов управления с учетом ограничений на управление и начального состояния объекта.
При синтезе систем управления чаще всего используют формальную постановку задачи оптимального управления Л.С. Понтрягина [1]. Отличие рассматриваемой) в работе задачи синтеза от задачи оптимального управления заключается в том, что вместо искомого управления в виде функции от независимой переменной, чаще всего этой переменной является время, ищется управление в виде функции от координат пространства состояний: Данная постановка задачи синтеза с одним функционалом рассматривается- в задаче динамического программирования Р. Беллманом [2].
Задача синтеза систем управления, т.е. задача получения управления в виде функциональной зависимости от координат пространства, состояний объекта, является главной задачей теории» автоматического управления. В общем случае для нелинейного объекта1 управления и произвольных критериев качества задача синтеза в настоящий момент не решена. Основной причиной отсутствия решения данной важнейшей задачи управления является сложность, а точнее практически невозможность получения аналитического решения задачи оптимального управления в общей постановке. В тех случаях, когда аналитическое решение задачи оптимального управления получено, синтез управления может быть построен на основе анализа найденного аналитического решения краевой задачи для системы дифференциальных
уравнений. Например, известно решение задачи синтеза управления для линейных систем невысокого порядка по критерию быстродействия [1,3].
Метод динамического программирования [2] позволяет решить задачу синтеза, если будет найдено аналитическое решение уравнения Беллмана в частных производных. Наиболее известным является решение, полученное для линейного объекта, квадратичного функционала и отсутствия ограничений на управление. Функциональная зависимость управления от координат пространства состояний объекта выражается линейным матричным преобразованием, полученным в результате решения уравнения Риккатти [4, 5].
Как правило, задача синтеза управления решается в два этапа. На первом этапе с помощью численных методов находится оптимальное управление как функция от времени. Для данного оптимального» управления находятся оптимальные траектории движения системы. На втором этапе строится система стабилизации, которая обеспечивает нахождение объекта в окрестности оптимальных траекторий. При этом система линеаризуется в окрестности оптимальных траекторий и этап синтеза системы стабилизации осуществляется в кассе линейных систем [6]. Данный подход не обеспечивает решение задачи синтеза оптимального управления, т.к. стабилизируемая во времени траектория в окрестности оптимальной траектории не обязательно будет оптимальной. Также ограниченный класс линейных систем стабилизации не приводит к оптимальной зависимости управления от пространства состояний.
В последнее время разработаны методы синтеза управления на основе синергетического подхода [7, 8, 9]. Данный подход позволяет на основе неформализованных процедур анализа системы построить притягивающее многообразие в пространстве состояний. Оптимальные траектории системы должны находиться в окрестности притягивающего многообразия. Синергетический подход ограничен классом задач и не позволяет построить формальный метод синтеза.
В настоящий момент наблюдается бурное развитие вычислительной техники и информационных технологий. Скорость вычислений на широко
используемых персональных компьютерах за последние десять лет увеличилась с 300 МГц до 5 ГГц. Это позволило применять вычислительную технику для решения новых сложных задач в различных областях. Существенные успехи получены в области использования компьютеров для символьных вычислений. На основании формальных преобразований компьютер позволяет строить аналитические решения различных математических задач.
Современные математические пакеты Mathematica, Maple, MathCad, Matlab и др. позволяют с помощью символьных преобразований получать решения в аналитическом виде. Данные решения могут быть точно получены только для тех задач, для которых они существуют. В случаях отсутствия решений пакеты позволяют построить аппроксимацию решений с высокой степенью точности в виде разложения в ряды. Аппроксимация решения задачи оптимального управления в виде разложения во временные ряды не позволяет построить зависимость управления от координат пространства состояний, т.к. ряды не учитывают аналитическую зависимость решения от начальных условий. В некоторых случаях символьную обработку можно использовать для решения задачи синтеза управления, если аппроксимировать решения многомерными рядами, аргументами которых являются координаты пространства состояний. Это возможно только для систем небольшой размерности.
В 1992 г. профессор Стэндфордекого университета Дж. Коза и его ученики разработали метод генетического- программирования [10]. Метод позволяет использовать генетический алгоритм, [11] для построения алгоритма программы. Сегодня метод генетического программирования бурно развивается и применяется для решения сложных задач.
В' работе синтез системы управления основывается на методе
генетического программирования. С помощью генетического
программирования осуществляется поиск функциональной зависимости управления от координат пространства состояний. В отличие от классического генетического программирования разработана новая структура данных для
представления аналитических зависимостей в ЭВМ. Данная структура названа сетевым оператором [12]. Сетевой оператор обеспечивает более эффективное вычисление формул.
Актуальность темы диссертационной работы заключается в том, что задача синтеза систем управления в общем случае в настоящий момент не решена. Предпосылкой для создания эффективного метода решения являются последние достижения, полученные в области алгоритмизации, и эффективные современные средства вычислительной техники.
Предметом диссертационного исследования является задача синтеза системы оптимального управления. Задача заключается в том, чтобы найти управление в виде функции координат пространства состояний, обеспечивающее оптимальное с точки зрения критериев качества функционирование объектов управления с учетом ограничений на управление и начального состояния объекта.
Целью диссертационной работы является разработка метода синтеза системы автоматического управления, т.е. получение оптимального управления в виде функциональной зависимости от координат пространства состояний. Для достижения поставленной цели необходимо решить следующие задачи:
- разработать и исследовать эффективный метод представления
функциональных зависимостей в ЭВМ;
разработать и исследовать эффективный генетический алгоритм для поиска функциональных зависимостей при решении задачи1 синтеза оптимального управления;
разработать и исследовать метод сетевого оператора для прикладной задачи синтеза системы управления стабилизацией спутника.
Методы исследования, используемые в диссертации, основываются на результатах, получены в областях теории управления, системного анализа, методах оптимального управления, теории графов, теории алгоритмов.
Новизна научных результатов, полученных в диссертации, заключается в том, что разработан новый метод многокритериального структурно-
параметрического синтеза системы управления. Разработанный метод использует новую структуру данных, сетевой оператор. Структура позволяет описывать произвольные математические выражения и представлять их в ЭВМ с помощью целочисленной матрицы, что позволяет увеличить эффективность алгоритма синтеза.
Практическая значимость результатов работы заключается в том, что разработанный метод синтеза предназначен для построения систем управления реальными динамическими объектами. В диссертации приведен пример синтеза системы стабилизации углового движения космического аппарата. На основании разработанных алгоритмов создан программный комплекс для синтеза систем управления.
Использование результатов работы осуществляется в учебном процессе на кафедре Кибернетики и мехатроники Российского университета дружбы народов. Издано учебно-методическое пособие. Работа выполнялась по теме гранта РФФИ №06-08-01485-а «Исследование методов синтеза систем автоматического управления».
Апробация результатов, полеченных в диссертации, подтверждается докладами на следующих научных конференциях и международных симпозиумах: «Интеллектуальные системы» (INTELS'2006) (г. Краснодар), III международной конференции по проблемам управления (г. Москва, 2006), «Надежность и качество 2007» (г. Пенза), «Космонавтика. Радиоэлектроника. Геоинформатика 2007» (г. Рязань), XV Международной конференции по механике и современным программным системам (ВМСППС'2007) (г. Алушта).
Основные положения, выносимые на защиту:
1. Метод многокритериального структурно-параметрического синтеза
системы управления на основе принципа базисного решения и генетического
алгоритма. Алгоритм позволяет одновременно искать решения для
структурного и параметрического синтеза.
2. Новая структура данных, сетевой оператор, которая предназначена для
представления формулы в ЭВМ. Метод преобразования формулы в сетевой
оператор. Представление сетевого оператора в виде целочисленной верхней треугольной матрицы. Алгоритм вычисления формулы по матрице сетевого оператора.
3. Решение задачи многокритериального структурно-параметрического синтеза системы стабилизации углового движения космического аппарата на основе разработанного метода.
Результаты диссертации опубликованы в 11 научных трудах, в том числе в двух изданиях из списка ВАК.
Диссертация состоит из введения, четырех разделов, заключения; списка литературы и приложений. Объем работы - 145 страниц, включая 78 рисунков и 4 таблицы, список литературы содержит 51 наименование.
В первом разделе дана. формальная постановка задачи. Рассматривается задача структурно-параметрического синтеза системы автоматического управления: Метод синтеза должен обеспечить построение структуры системы управления и подобрать оптимальные значения параметров выданной: системе. В главе приведен обзор работ, посвященных решению проблемысинтеза системы автоматического управления.7 Утверждается, что не? существует эффективных автоматизированных методов синтеза систем автоматического управления для нелинейных объектов управления и произвольных функционалов. Для построения алгоритма решения задачи синтеза в работе предложено использовать метод, генетического программирования, который; может обеспечить; получение решения; задачи синтеза^ близкого к оптимальному решению;
Во втором разделе разработан метод сетевого оператора для синтеза оптимальной системы управления. Представлены исследования свойств сетевого оператора, изучены, и формализованы способы построения аналитических выражений в форме сетевого оператора. Сетевой оператор описывается с помощью целочисленной верхней треугольной матрицы, которая является эффективной структурой данных для вычисления формулы.
В третьем разделе приведена разработка генетического алгоритма для решения задачи синтеза на основе метода сетевого оператора. При построении алгоритма используется метод базисной структуры, который обеспечивает сохранение свойств сетевого оператора при генетических операциях. Рассмотрен методический пример синтеза оптимального управления на основе разработанного метода.
В четвертом разделе рассмотрена задача синтеза управления для стабилизации углового движения космического аппарата. Рассмотрены задачи синтеза с различными ограничениям на управление и с двумя критериями качества. Полученная в результате синтеза система управления исследована на влияние вариаций начальных условий на значения функционалов. Показано, что синтезированная система управления обеспечивает значения функционалов близкие к оптимальным значениям, полученным при решении задачи оптимального управления методом принципа максимума Понтрягина.
В заключении представлены основные научные результаты, полученные в работе.
Работа выполнена в Российском университете дружбы народов на кафедре Кибернетики и мехатроники.
Метод генетического программирования
Генетическое программирование является развитием метода генетического алгоритма [35-40]. Оно появилось при использовании генетического алгоритма для автоматического написания программ [10]. Автоматическое написание программ подразумевает создание такой программы, которая могла бы создавать другие программы без детального описания алгоритма, используя только набор требований и условий.
Препятствием на пути решения задачи автоматического написания программ является то, что существующие методы обучения машин, искусственного интеллекта, нейронных сетей не ищут решения в виде компьютерных программ. Решения представлены в виде специальных структур, например, весовых векторов в нейронных сетях, деревьев решений, коэффициентов полиномов, строк хромосом в обычном генетическом алгоритме. Очевидно, что компьютерные программы не создаются при помощи весовых векторов, деревьев решений и т.д. Программистам тяжело работать с такими специальными структурами, так как эти структуры не обладают достаточной гибкостью. Поэтому если необходимо чтобы компьютер решал поставленную задачу без детального программирования, структурами должны быть компьютерные программы.
Компьютерные программы обладают гибкостью [10] при:
- иерархическом выполнении операций;
- выполнении альтернативных вычислений по выходу промежуточных расчетов;
- выполнении итераций и рекурсий;
- выполнении вычислений с переменными разных типов;
- выделении промежуточных значений и подпрограмм для их последующего использования.
Преимуществом автоматического написания программ является то, что не надо заранее указывать размер, форму и сложность структуры решения:
Для реализации поставленной цели необходимо решить задачу выбора необходимой программы из множества возможных программ. Очевидно, что такая задача слишком сложна для обычного случайного поиска. Генетическое программирование является попыткой найти необходимую программу адаптивным или интеллектуальным способом. Интеллектуальный поиск на любом множестве начинаем с выбора одной или более структур из данного множества и оценки ее пригодности при решении задачи. Затем эту информацию используем для изменения, в лучшем случае для улучшения, направления поиска и видов выбора структур из множества. Примером такого поиска являются итерационные алгоритмы нахождения экстремума. В алгоритмах выбираем точку, ее пригодность сравниваем с пригодностью близлежащих точек, а затем осуществляем движение точки в направлении точки с наилучшей пригодностью. Таким образом, траектория движения точки зависит от информации, полученной на предыдущих итерациях.
В генетическом программировании возможным решением является код программы, которая удовлетворяет заданным требованиям или решает поставленную задачу. Для универсального описания программы и ее кодировки используется польская запись программного кода.
Польская запись [41] представляет собой строку символов, описывающих операторы и операнды, и является промежуточным кодом, к которому преобразуют трансляторы исходные тексты программ при их переводе в машинные команды. Польская запись является удобным и универсальным видом записи программы.
Рассмотрим пример польской записи для арифметического выражения С учетом скобок получаем следующую запись:
[(A + B)-[(C?/(D-E)l Скобки определяют порядок выполнения вычислений. В обычной польской записи скобки не используются. Вычисления выполняются слева направо. Первоначально определяется тип операции, например, унарная, бинарная и т.п. В приведенном примере четыре бинарные операции сложения, вычитания, умножения и деления и одна унарная - возведение в квадрат. Затем из записи берется необходимое число операндов для вычисления. Для получения польской записи сначала рассматриваем самые внутренние скобки, имеющие наивысший приоритет порядка вычислений. В нашем случае это выражения [А + В\ [D-E) и унарная операция возведения в 9 квадрат С . Обозначим операцию возведения в квадрат значком «Л». Тогда в польской записи они имеют вид, соответственно + АВ , DE и Л С . В результате получаем промежуточную запись (+ АВ - (Л С / DE)).
Графическая запись формулы
Графическая запись формулы предназначена для представления формулы в виде графа. При такой записи бинарные операпии, входящие в программную запись формулы, должны обладать следующими свойствами:
- коммутативность Х/М=Х/М ХІ є02 ы\у (25) ассоциативность
В графической записи формулы бинарные операции будут соответствовать вершинам графа, а унарные операции - ребрам. Поэтому в графической записи при описании формулы необходимо установить чередующийся порядок между бинарными и унарными операциями.
Графическая запись формулы — это запись бинарной операции, которая отвечает следующим требованиям:
а) аргументами бинарной операции являются унарные операции или единица, соответствующая данной бинарной операции;
б) аргументом унарной операции является либо бинарная операция, либо элемент из множества переменных или параметров;
в) аргументами бинарной операции не могут быть унарные операции, аргументами которых является один и тот же параметр или переменная. Рассмотрим в качестве примера выражение у = l-b + Jb -4ас\/2а.
Графическая запись формулы для рассматриваемого математического выражения будет иметь следующий вид:
У = Х2 (pi (Хі (РЗ Ф0 Р4 Осі (Р2 (4РЗ (Х2 (pi W,Pl \ 2 (pi (а) р5(Х2 (2),Pl (а), (С)))))ІР5(Х2 (2),Р, Ml.
Графическая запись формулы в отличие от программной записи содержит чередующиеся бинарные и унарные операции. Согласно определению графической записи формулы непосредственными аргументами бинарной операции не могут быть переменные и параметры, поэтому используется тождественная унарная операция.
Бинарные операции сложения и умножения, используемые в графической записи, являются коммутативными, ассоциативными и имеют единичные элементы. Для операции сложения единичным элементом является ноль, а для операции умножения - единица. Для их реализации некоммутативных операций, например вычитания z\ - Z2 или возведения в степень z 2 и др. необходимо модифицировать выражение или использовать дополнительные операции. Например, рассмотрим выражения z\-z2=zx +(-z2)=3Cl(pi(zi),P3fe)) 2= ln( )=p6(X2(pi(z2),p7(zi) где pi(z) = z, P3(z)=-z, p(,(z)=ez, py(z) = ln(z) - унарные операции. Любую программную запись формулы можно перевести в графическую запись. Действительно, согласно определению графическая запись формулы также является программной. Если программная запись формулы не является графической, то это может быть вызвано следующими причинами: а) аргументом унарной операции является унарная операция; б) аргументом бинарной операции является бинарная операция, переменная или параметр; в) аргументом унарных операций, которые являются аргументами бинарной операции, является один и тот же параметр или переменная. Рассмотрим все возможные отличия между программной и графической записями отдельно. Пусть в программной записи аргументом унарной операции является унарная операция р?- 1р (а)). Для перевода в графическую запись вводим дополнительную бинарную операцию суммирования. При суммировании используем единичный элемент, ноль. Получаем следующее уравнение рДру(а)]=Х1(о,рД%1(о,ру-(а)), где xl(z ,z")=z + z" - бинарная операция суммирования. Пусть в программной записи аргументом бинарной операции являются бинарная операция и параметр или переменная, например, X/ІР; (a X7wr Pyt(c))j- Для пеРевДа в графическую запись используем тождественную унарную операцию. Получаем следующее уравнение X/ (р/ ( lXm[b 9k(c)jj=Xi (Р/ (4Pi (xm(pi (b) Pk(c)))l r e Pi 00 = z тождественная операция. Пусть бинарная операция имеет в качестве аргументов унарные операции, аргументом которых является один и тот же параметр или переменная, например, Х/\Р/(a)»Pt-(a)j- Для перевода записи в графическую введем дополнительные унарную и бинарную операции X/(p/W P W)=X/(p/W Pi( ol0 PifcW)))» где Pl(z)=z - тождественная операция, %Q{Z JZ") = Z + z" - операция суммирования. Заметим, что согласно определению графической записью формулы может быть только бинарная операция. Это вызвано тем, что бинарные операции в графическом представлении соответствуют вершинам графа, а граф без вершин невозможен. Программной записью может быть, как бинарная, так и унарная операции. Для перехода к графической записи используем внешнюю бинарную операцию, например, суммирование с нулевым элементом. Пусть О задано выражение у-ЛІех . Представим выражение в виде программной записи, получим у = р4 (р6 (р2 (x)jj. Для перевода программной записи в графический вид используем бинарную операцию сложения с нулем. В результате получаем следующую графическую запись формулы у = %{ (oj,p4(x1 (? P6(xi (O,P2(A:)JJJ)J. Для графической записи формулы первоначально записываем формулу с помощью унарных и бинарных операций, получаем программную запись формулы. Затем приводим программную запись формулы к графической. Если в формуле необходимо использовать больше двух аргументов для бинарной операции, то для графической записи формулы используем тождественную унарную операцию.
Представление решения в виде хромосомы
1. На основе принципа базисного решения определено множество малых вариаций сетевого оператора. Разработана структура данных для поиска функциональной зависимости решения задачи (1.1)-(1.4) в виде сетевого оператора. Структура данных представляет собой упорядоченное множество векторов вариаций, которые изменяют базисное решение.
2. Разработаны предложения по выбору:
- конструктивных множеств: переменных, параметров, унарных и бинарных операций;
- размерности сетевого оператора;
- базисного решения.
Составлены таблицы бинарных и унарных операций, которые рекомендуется использовать при решении задачи синтеза систем управления.
3; Введено понятие условного множества Парето оптимальных решений. Условное множество Парето является подмножеством хромосом в популяции. Для оценки приспособленности хромосомы определен параметр, расстояние до. условного множества Парето. Данный параметр используется в генетическом алгоритме для расчета вероятности скрещивания хромосом.
4. Разработан генетический алгоритм для решения задачи (1.1)-(1.4). Алгоритм позволяет одновременно искать решения для структурного и параметрического: синтеза. Хромосома, используемая- в алгоритме, состоит из двух частей: структурной части; представляющей? собойі. упорядоченное множество векторов вариаций, и параметрической части в виде битовой строки. При скрещивании двух хромосом получаем четыре потомка, два из. которых имеют только новые параметрические части; а два других - новые параметрические и структурные части. В алгоритм введен новый параметр -эпоха, который определяет количество поколений между сменой базисного решения.
5. На основе разработанного алгоритма многокритериального структурно-параметрического синтеза системы управления решена задача синтеза управления для двух независимых системы второго порядка. Показано, что полученное управление близко к оптимальному. Это подтверждает корректность использования предложенного алгоритма для решения данной задачи.
Результаты вычислительного эксперимента
Из результатов проведенного эксперимента можно сделать вывод, что полученная в результате синтеза нелинейная система управления является робастной по отношению к изменениям начальных условий. В работе [50] оптимальное значение функционала составило J\ = 2,5075.
Как видно из результатов моделирования синтезированные нелинейные системы управления обеспечивают стабилизацию спутника за заданное время и значение функционала по управлению, отличающегося от оптимального не более чем на 25%. В отличие от результатов полученных Р.П. Федоренко синтезированные системы управления представляют собой нелинейные обратные связи по координатам пространства состояний. Такой вид управления сохраняет качество управления при вариации начальных условий (см. рис. 4.27-4.32). Расчеты проводились на персональном компьютере с процессором AMD Athlon 64, с тактовой частотой 1ГГц. Время расчета составило не более 10 минут.
1. На основе разработанного алгоритма многокритериального структурно-параметрического синтеза системы управления решена задача стабилизации углового движения космического аппарата с разными ограничениями на управление. Полученные системы управления, выбранные из множества Парето, являются нелинейными и обеспечивают стабилизацию космического аппарата относительно начала координат и значение критерия качества управления, близкого к оптимальному. Результаты вычислительного эксперимента подтверждают эффективность работы алгоритма.
2. На основе проведенного моделирования показано, что синтезированные системы управления в виде нелинейных обратных связей по координатам пространства состояний являются робастными по отношению к изменению начальных условий.
В результате проведенного научного исследования были получены следующие результаты:
1. Разработан сетевой оператор, который является графическим представлением формулы, определены его свойства, обоснован метод преобразования формулы в сетевой оператор. На основе матрицы смежности сетевого оператора и его свойств разработан метод пстроения матрицы сетевого оператора. Матрица является целочисленной верхней треугольной, и она является эффективной структурой данных, для вычисления формулы. Разработан алгоритм вычисления формулы по матрице сетевого оператора.
2. На основе принципа базисного решения определено множество малых вариаций сетевого оператора и разработан генетический алгоритм для решения задачи многокритериального структурно-параметрического синтеза системы управления. Алгоритм позволяет одновременно искать решения для структурного и параметрического синтеза.
3. На основе разработанного алгоритма решена задача синтеза системы стабилизации углового движения космического аппарата. Система управления из полученного условного множества Парето, обеспечивает стабилизацию космического аппарата относительно начала координат и значение критерия качества управления, близкого к оптимальному. На основе проведенного моделирования показано, что синтезированные системы управления в виде нелинейных обратных связей по координатам пространства состояний являются робастными по отношению к изменению начальных условий.
