Сравнительный анализ численных алгоритмов решения задач оптимального управления

УДК 519.62

Г. Р. Шангареева, И. В. Григорьев, С. А. Мустафина

СРАВНИТЕЛЬНЫЙ АНАЛИЗ ЧИСЛЕННЫХ АЛГОРИТМОВ РЕШЕНИЯ ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ

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

численный алгоритм.

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

Key words: method of successive approximations, the method of variations, optimal control, phase constraints, numerical algorithm.

In this article step by step algorithms were developed for solving optimal control problems based on the method of successive approximations and the method of variations in the space of controls. The algorithm of the method of successive approximations requires details of the problem to the boundary problem of the maximum principle. In turn, the algorithm of the variations is more versatile because it is based on iterating state variables and control in the phase space. A numerical study and comparative analysis of the developed algorithms performed at different values of accuracy.

Введение

Методы теории оптимального управления интенсивно используются в различных прикладных областях [1]-[6]: в механике полета (решение различных задач оптимизации полета самолетов и космических кораблей), в технике (оптимизация работы технических систем, робототехника), в физике и энергетике (оптимизация режимов работы ядерных реакторов, оптимизация режимов передачи электрической энергии), в экономике (нахождение оптимальных режимов функционирования в различных микро - и макромоделях экономики), а также во многих других отраслях человеческой деятельности. На данный момент не разработано единого универсального метода решения этой задачи, что в основном объясняется трудностью решения задач оптимального управления.

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

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

Постановка задачи

Пусть состояние физического процесса или объекта характеризуется переменными состояния (фазовыми координатами) х1 (:)х2 ()...хп ((). Физический процесс или динамика объекта описывается системой дифференциальных уравнений (уравнениями состояния):

dXi- = f,ft,x1,x2,...xn,u), i = 1,...,n, dt iV 1 2 n '

где и = и({) - функция, характеризующая управляющее воздействие, : - время.

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

Задача оптимального управления заключается в определении функции управления и = и() в интервале :о < : < Т, которая обеспечивает экстремум (максимум и минимум) критерия качества, заданного в виде функционала: Т

:о

и удовлетворяет ограничению:

<р

где f 0(х:,и), Я(Т, х) - заданные непрерывно дифференцируемые функции. В качестве критериев качества могут приниматься энергетические затраты, время достижения цели, ошибка управления, стоимость, минимальный расход продукта и т. п.

Решение задачи оптимального управления требует задания начальных х, ((о) и конечных состояний хI (т), / = 1,., п.

Оптимальное управление и = и() определяет оптимальную траекторию х, = х, (:) в п -мерном фазовом пространстве, движение по которой из начального состояния обеспечивает достижение оптимального значения функционала (критерия качества) [8].

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

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

Задача оптимального управления (1) - (3) с помощью принципа максимума [9] может быть сведена к решению краевой задачи системы дифференциальных уравнений 2п-го порядка.

Введем п - мерный вектор ц = (,..., цп) сопряженных переменных (импульсов) и функцию Гамильтона Н :

Н

Запишем сопряженную систему: = " ^

dt j=i

dxi

Vj, i = 1.....n

v(t ) = -'

с граничными условиями: dx '

Согласно принципу максимума искомое оптимальное управление доставляет функции H (t, x,y,u) максимум по u е U при любом t е [[, T], если x(t) и y/(t) удовлетворяют системе (1) и граничным условиям (6).

Одним из наиболее распространенных методов решения указанной краевой задачи является метод последовательных приближений в пространстве управлений [10]-[13].

Задаем в качестве первого приближения некоторое допустимое управление u 0 (t), (t0 < t < T) (выбор его может быть основан на каких-либо физических соображениях) и полагаем счётчик числа итераций равным 0.

Метод итерационный и k итерация заключается в следующем:

1. Интегрируем управляемую систему с управлением u _ uk (t) до момента t _ T . При этом определяется траектория xk (t) и граничные условия

для сопряженной системы.

2. Интегрируем сопряженную систему от момента

t _ T до t _ t0 при u _ uk (t), x _ xk (t) - определяем сопряженные переменные ц/к (t) на интервале [0, T ].

3. Определяем новое приближение uk+1 (t) на интервале [¿0, T ] из максимума функции H (t, x,y,u):

4. H

ueU

5. Если условие (7) определяет uk+1(t) неединственным образом, то выбираем любое из возможных значений. После этого переходим к следующей итерации и т. д.

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

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

Описанный метод очень прост с вычислительной стороны, так как на каждом шаге требует лишь решения двух задач Коши: «слева направо» для системы (1) и «справа налево» для системы (5).

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

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

Алгоритм метода вариаций

Метод вариаций по своей сути является методом перебора вариантов в фазовом пространстве, каждый раз определяем минимум функционала качества.

Метод вариаций в пространстве управлений состоит в следующем. Производится вариация траектории в дискретных точках, отстоящих на время dt , по каждой из компонент вектора x , причем при варьировании k - ой точки все остальные считаются фиксированными. Если значение критерия качества уменьшилось, то движение продолжается в этом направлении. Метод вариаций в пространстве управлений представляет сочетание дискретизации задачи с методом покоординатного спуска.

Положим, что известно некоторое управление u(t) е U, которое будем называть невозмущенным

управлением.

В методе вариаций на каждой итерации вариация Su управления u(t) определяется путем минимизации линейной части приращения функционала I(u),

вызванного этой вариацией:

T

min SI(du) = min Г WT (t)Su(t).

SueSU SueSU J

0

Здесь SU - некоторая малая окрестность невозмущенного управления u(t).

Общая схема метода вариаций в пространстве управлений:

1. Полагаем счётчик числа итераций k равным нулю и задаем начальное приближение к оптимальному управлению uk (t) е U.

2. Решаем задачу Коши для системы дифференциальных уравнений (1) с управлением, полученным на предыдущем шаге - получаем фазовую траекторию xk (t).

3. Вычисляем 1к (и) - значение функционала качества (3) на невозмущенной траектории ик (:). Запоминаем значение критерия и управление в достаточном числе точек.

4. В окрестности невозмущенной траектории ик (:) выполняем линеаризацию задачи - вычисляем функциональную производную

ууО (:) = д1 (и) и определяем окрестность бЦк ди

невозмущенной траектории.

5. Из условия

Т

......,1к (

ЗиеЗи"

min SIk (du) = min ¡Wo (t))Su(t)dt,

ueSUk SueSUkJ V '

находим приращение Suk управления uk

6. Полагаем uk+1 (t) = uk (t) + Suk .

7. Повторяем цикл с п.2 до тех пор, пока не выпол-

k

нится условие ou <s .

Вычислительный эксперимент

На основе созданных алгоритмов реализован программный комплекс на языке Object Pascal в среде Delphi, который включает возможности остановки процесса [15]-[16]. При этом погрешности будут рассчитываться по евклидовой норме:

exi (ii " x1 (ti))2; ^ = ^ (x2i - x2 (ti))2;

IZW -u*(ti))2.

Тестовый пример. Пусть управляемый процесс описывается системой дифференциальных уравнений:

М' )= х 2

X2

с начальными условиями:

х1

и следующими ограничениями на переменную времени:

0 < t < 2л

и на управление:

Н < 1.

Критерий оптимизации имеет вид

I = x2

Требуется найти оптимальное программное управление и *(() и соответствующую ему траекторию x *((), которые удовлетворяют уравнениям (8)-(9), ограничениям (10)-(11) и условию (12).

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

Результат аналитического решения задачи представлен в работе [17]. Оптимальное управление и (t) на отрезке [0,2 л ] имеет две точки переклю-

чения и, следовательно, три промежутка знакопо-стоянства:

7 * *

при 0 < t < —: u (t) = -1, x1 (t) = cos t -1,

x2 (t) = - sin t;

7 3—

при — < t < —: u* (t) = 1, x/(t) = cos t - 2 sin t +1.

x2 (t) = - sin t - 2cos t;

3л . _ «... .

при — < t < 2л: u (t) = -1,

x1 (t) = cost - 4sint -1, x2 (t) = -sint - 4cost.

Минимальное значение функционала равно x2*(2л) = -4.

В таблице 1 и таблице 2 представлен сравнительный анализ результатов численного решения задачи (8)-(12) методом вариации и методом последовательных приближений при различных значениях начального приближения, точности вычислений.

Таблица 1 - Сравнительный анализ результатов решения задачи при точности вычислений 10-3

Параметры Метод вариаций Метод последовательных приближений

Начальное приближение ио 0,9 0,9

Скорость вычислений, с 3,84 0,54

Погрешность еи 2,962 0,998

Погрешность ех, 0,016 1,419

Погрешность ех^ 0,017 1,479

Значение функционала -3,996 -3,783

Таблица 2 - Сравнительный анализ результатов решения задачи при точности вычислений 10-5

Параметры Метод вариаций Метод последовательных приближений

Начальное приближение ио 0,1 0,1

Скорость вычислений, с 5,35 1,32

Погрешность еи 2,002 0,009980

Погрешность ех, 0,1093 0,24285

Погрешность ех^ 0,1088 0,20681

Значение функционала !т|П -3,9999 -3,98396

Полученные результаты показывают удовлетворительное согласование с аналитическим решением.

Заключение

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

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

Литература

1. Байтимерова А.И., Мустафина С.А., Спивак С.И. Поиск оптимального управления в каскаде реакторов для процессов с переменным реакционным объемом // Системы управления и информационные технологии. 2008. Т. 32. № 2. С. 38-42.

2. Григорьев И.В., Михайлова Т.А., Мустафина С.А. О численном алгоритме метода вариаций в пространстве управлений // Фундаментальные исследования. 2015. № 5-2. С. 279-283.

3. Иремадзе Э.О., Мустафина С.А., Спивак С.И. Неопределенность в кинетических константах и расчет оптимальной температуры // Математическое моделирование. 2000. Т. 12. № 3. С. 21-22.

4. Григорьев И.В., Мифтахов Э.Н., Мустафина С.А. Математическое моделирование процесса полимеризации стирола с малеиновым ангидридом // Вестник технологического университета. 2015. Т. 18. № 15. С. 211-216.

5. Григорьев И.В., Мустафина С.А. Реализация численного алгоритма метода вариаций в пространстве управлений // Молодой ученый. 2015. № 9 (89). С. 110-115.

6. Степашина Е.В., Мустафина С.А. Численный алгоритм уточнения механизма химической реакции (^ер-методом // Журнал Средневолжского математического общества. 2011. Т. 13. № 3. С. 118-121.

7. Григорьев И.В., Мустафина С.А. Нахождение оптимального программного управления методом итераций // Путь науки. 2015. № 5 (15). С. 10-13.

8. Михайлова Т.А., Григорьев И.В., Мустафина С.А. Исследование синтеза бутадиен-стирольного сополимера на основе метода монте-карло с учетом распределения по времени пребывания // Фундаментальные исследования. 2015. № 5-3. С. 517-520.

9. Шангареева Г.Р., Григорьев И.В., Мустафина С.А. Программное средство «SAOptimal» для решения задач оптимального управления // Хроники объединенного фонда электронных ресурсов Наука и образование. 2015. № 8-9 (75-76). С. 52.

10. Вайтиев В.А., Степашина Е.В., Мустафина С.А. Идентификация математических моделей редуцированных схем реакций // Известия Томского политехнического университета. 2013. Т. 323. № 3. С. 10-14.

11. Ikramov R.D., Mustafina S.A. Numerical study of the Belousov-Jabotinsky's reaction models on the basis of the two-phase Rozenbrock's method with complex coefficients // International Journal of Applied Engineering Research.

2014. Т. 9. № 22. С. 12797-12802.

12. Григорьев И.В., Мустафина С.А. Реализация численного алгоритма решения задач оптимального управления с фазовыми ограничениями //Аспирант. 2015. № 5-1 (10). С. 49-51.

13. Степашина Е.В., Мустафина С.А. Формирование математической модели каталитических процессов с переменным реакционным объемом на основе теоретико-графового подхода // Известия Томского политехнического университета. 2012. Т. 320. № 3. С. 31-36.

14. Крылов И.А., Черноусько Ф.Л. О методе последовательных приближений для решения задач оптимального управления. - Ж. вычислит. матем. И матем. физ., 1962, т. 2, №6.

15. Григорьев И. В., Шангареева Г. Р., Мустафина С. А. Программный продукт «VarOptimalControl» решения задач оптимального управления // Хроники объединенного фонда электронных ресурсов Наука и образование.

2015. № 8-9 (75-76). С. 46.

16. Шангареева Г.Р., Мустафина С.А. Метод последовательных приближений для решений задач оптимального управления // Проблемы теории и практики современной науки. Материалы Международной (заочной) научно-практической конференции. РИО ООО «Наука и образование». Нефтекамск, 2015. С. 138-140.

17. Понтрягин Л. С. Математическая теория оптимальных процессов. - М.: Наука. 1976. 392 с.

© Г. Р. Шангареева - асп. каф. математического моделирования Стерлитамакского филиала «Башкирский государственный университет», shangareeva.gulnaz@gmail.com; И. В. Григорьев - асп. той же кафедры, grigoryevigor@mail.ru; С. А. Мустафина - д.ф.-м.н., проф., зав. каф. математического моделирования Стерлитамакского филиала «Башкирский государственный университет», mustafina_sa@mail.ru.

© G. R. Shangareeva - postgraduate student of the department of mathematical modeling, Sterlitamak Branch of Bashkir State University, shangareeva.gulnaz@gmail.com; 1 V. Grigoryev - postgraduate student of the same Department, grigoryevigor@mail.ru; S. A. Mustafina - doctor of Science, Professor, head of chair of mathematical modeling, Sterlitamak Branch of Bashkir State University, mustafina_sa@mail.ru.