Задача оптимального управления и ее решение эволюционным алгоритмом «серого волка»

Полный текст

Основной подход к численному решению задачи оптимального управления заключается в ее преобразовании в задачу нелинейного программирования, которое состоит в дискретизации компонент вектора управления по времени [1]. При таком подходе точность численного решения задачи оптимального управления пропорциональна числу точек дискретизации, но одновременно с точностью растет и размерность пространства искомых параметров. В полученной после преобразования задаче вычисление целевой функции требует интегрирования системы дифференциальных уравнений. Для задач с высокой степенью пространства требуемых параметров, вычисление целевой функции будет занимать б льшую часть от всего времени вычислений. Из этого следует, что сложность алгоритмов в задачах оптимального управления более правильно оценивать по числу вычислений целевой функции, а не по числу поисковых итераций. Еще одна важная особенность задачи оптимального управления состоит в отсутствии сведений о топологических свойствах целевой функции в пространстве искомых параметров. Для случаев, когда целевая функция содержит большое количество локальных экстремумов, велика вероятность, что методы нелинейного программирования будут находить локальные экстремумы, значение которых не дает информации о месте расположения глобального оптимума в пространстве искомых параметров. Таким образом, градиентные методы, т.е. методы, требующие вычисления первой производной, которые наиболее часто применялись на практике для решения задач оптимального управления, могут застревать в локальных экстремумах и тем самым работать неэффективно. Первые эволюционные алгоритмы появились в конце XX века [2]. Их также называют популяционными, роевыми или алгоритмами, вдохновленными природой. В настоящее время класс эволюционных алгоритмов насчитывает более 150 методов. Новые уникальные методы, а также множество гибридных методов пополняют данный класс до сих пор. Многие методы из класса эволюционных алгоритмов имеют экзотические имена, которые удобны для использования, но лишь косвенно могут показать используемые в методе математические подходы. Авторы используют термин «эволюционные алгоритмы» для тех методов, которые имеют следующие две общие черты: а) для вычислений используется начальное множество возможных решений, которое генерируется случайным образом; б) на последующих вычислительных этапах модификация или «эволюция» этого множества выполняется в соответствии с информацией о ранее вычисленных значениях целевой функции для элементов множества возможных решений. Современные методы, относящиеся к классу эволюционных алгоритмов, могут применяться с любыми типами функций, в том числе и с функциями с множеством локальных экстремумов. В работах [3; 4] показана эффективность эволюционных алгоритмов для решения задач оптимального управления и их преимущество над классическими градиентными методами. Однако присутствие стохастической составляющей в модификации множества возможных решений все еще вызывает недоверие у некоторых ученых. Целью данной работы является изучение эффективности применения современного алгоритма «серого волка» для решения задач оптимального управления на примере задачи оптимального управления самолетом при совершении боевого разворота. Задача оптимального управления Задача оптимального управления в наиболее часто используемой для численных решений постановке: ẋ = f(x, u), где x Î ℝn, x = [x1, …, xn]T - вектор состояния; u Î ℝm, u = [u1, …, um]T - вектор управления, f(x, u) = [f1(x, u), …, fn(x, u)]T. Ограничения на управление u- £ u £ u+, - - T где u-, u+ - заданные постоянные векторы ограничений; u- = [u1 , …, um ] , + + T u+ = [u1 , …, um ] . Начальные условия x(0) = x0, 0 0 T где x0 - заданный вектор начальных значений, x0 = [x1 , …, xn] . Терминальные условия x(tf) = xf, f f T где xf - заданный вектор терминального состояния, xf = [x1, …, xn] ; tf - ограниченное время процесса управления ⎧⎪t, если t < t + t = ⎨ и || x(t) - x f || £ e, f ⎪⎩t + - иначе где t+, ε - заданные положительные величины, норма разности векторов может выбираться из особенностей задачи, для модели объекта с соизмеримыми компонентами вектора состояния целесообразно выбрать Евклидову норму || x(t) - x f ||= n å i =1 i i (x (t) - x f )2 . Функционал качества t f J = || x(t f ) - x f || + ò f0 (x, u)dt ® min. 0 Результатом решения задачи оптимального управления является вектор управления с компонентами в форме функций времени ũ(·) = [ũ1(·), …, ũm(·)]T, поэтому данная задача относится к классу задач бесконечномерной оптимизации. Для применения к решению задачи оптимального управления методов нелинейного программирования необходимо аппроксимировать искомые функции ũi(·), i = 1, …, m функциональными зависимостями от конечного числа параметров. Для этой цели часто используют полиномы, ортогональные ряды или кусочнофункциональную аппроксимацию. Приведем редукцию задачи оптимального управления к задаче нелинейного программирования с помощью кусочно-линейной аппроксимации. Зададим малый интервал Δt > 0, и определим количество интервалов ⎢ t + ⎥ M = ⎢ ⎥. ⎣Ät ⎦ Значение управления ũ(t) = [ũ1(t), …, ũm(t)]T в момент времени t определяем из соотношения j j ⎧u-, если q(t, j, i, Ät ) < u- ⎪ + + u j (t) = ⎨uj , если q(t, j, i, Ät ) > u j , ⎩ ⎪⎪q(t, j, i, Ät) - иначе где iΔt £ t < (i + 1)Δt; q(t, j, i, Δt) = q(j-1)M+i + (q(j-1)M+i+1 - q(j-1)M+i) i = 1, …, M, j = 1, …, m. (t -(i -1)Ät); Ät В результате поиск управления в задаче оптимального управления заменяем поиском вектора постоянных параметров q = [q1, …, qp]T, где p = m(M + 1). При поиске значения параметров ограничиваем q i i - £ qi £ q+, i = 1, …, p, - + - - где qi , qi u+ - заданные значения ограничений на параметры; qi +, i = 1, …, p, ⎣A⎦ - целая часть числа A. £ u ⎣i/(M+1)⎦+1, ⎣i/(M+1)⎦+1 £ qi Алгоритм «серого волка» Алгоритм «серого волка» был предложен в 2013 году [5]. По словам авторов, их алгоритм имитирует иерархию лидерства и механизмы охоты серого волка в дикой природе. Для моделирования иерархии лидерства используются четыре типа серых волков: альфа, бета, гамма и омега. Математическое моделирование иерархии лидерства серых волков предполагает, что альфа - это лучшее известное на текущий момент решение целевой функции. Бета и гамма - соответственно второе и третье по качеству решения целевой функции. Остальные решения из множества возможных решений, называемые омега, эволюционируют по определенным правилам на основе своего текущего значения и текущих значений альфа, бета и гамма. Сравнительный анализ алгоритма, проведенный авторами метода, показал, что алгоритм «серого волка» может составить конкуренцию многим хорошо известным и зарекомендовавшим себя эволюционным алгоритмам. Отличительная особенность алгоритма «серого волка» среди множества других методов из класса эволюционных алгоритмов заключается в отсутствии свободных параметров, требующих настройки под определенную задачу. Для вычислений по этому методу требуется указать только размер множества возможных решений и максимальное число вычислительных итераций. При рассмотрении алгоритма «серого волка» генерируем множество начальных возможных решений: где qi = [qi , …, qi Q = (q1, …, qH), ]T, i = 1, …, H, H - размер множества возможных решений; 0 2M-1 i + - - qj = ξ(qj - qj ) + qj , j = 0, …, p - 1, ξ - случайное число, ξ Î [0; 1]. Вычисляем значение целевой функции для каждого возможного решения F = (f1 = J(qi), …, fH = J(qH)). Задаем текущее значение счетчика итераций w = 0, максимальное число итераций W и начинаем вычислительные итерации. В текущем множестве возможных решений Q выбираем три наилучших решения qα, qβ, qδ: J (qa ) = min{J (qi ) : i = 1, ¼, H }, i (1) J (qb ) = min{J (qi ) : "i Î{1, ¼, H } \ a}, i (2) J (qd ) = min{J (qi ) : "i Î{1, ¼, H } \ {a, b}}. i Вычисляем значение параметра линеаризации a = 2 - 2w , W (3) (4) где w = 0, …, W - 1. Для каждого возможного решения qi, i = 1, …, H в текущем множестве Q производим вычисления альфа, бета и гамма составляющих, а затем производим модификацию возможного решения qi. Вычисляем значение составляющей альфа α α α α i αj = qj - dj |gj qj - qj |, j = 0, …, p - 1, (5) j где gα j = 2aξ - a, dα = 2ξ, ξ - случайное число, ξ Î [0; 1]. Вычисляем значение составляющей бета β β β β i βj = qj - dj |gj qj - qj |, j = 0, …, p - 1, (6) j где gβ j = 2aξ - a, dβ = 2ξ, ξ - случайное число, ξ Î [0; 1]. Вычисляем значение составляющей гамма γ γ γ γ i γj = qj - dj |gj qj - qj |, j = 0, …, p - 1, (7) γ γ где gj = 2aξ - a, dj = 2ξ, ξ - случайное число, ξ Î [0; 1]. Вычисляем новое значение возможного решения qi j j j j j ⎧q -, если (a + b + g ) / 3 < q - ⎪ qi = ⎨q + , если (a + b + g ) / 3 > q + , (8) j j j j j j ⎪ ⎪⎩(a j + b j + g j ) / 3 - иначе i = 1, …, H, j = 0, …, p - 1. Увеличиваем значение счетчика итераций и повторяем вычисления (1-8) до достижения максимального числа итераций. Задача оптимального управления самолетом при выполнении боевого разворота Боевой разворот - авиационный термин, которым принято обозначать вид маневрирования самолета, при котором он совершает быстрый разворот на 180° с одновременным набором высоты. При рассмотрении задачи оптимального управления самолетом в режиме боевого разворота критерием оптимальности служит выход самолета на заданную высоту и траекторию за минимальное время. Приведем описание математической модели, описывающей движение самолета [6]: ẋ = Vcos θcos ψ; ẏ = Vsin θ; ż = -Vcos θsin ψ; V· = g (u P cos a - C qS - G sin q); G 1 x Ġ = -CS; · θ = g(u2Ncos u4 - cos θ)/V; y· = - gu2 N sin u4 . V cos q Параметры имеют следующие значения: g = 9,81; S = 55; q = ρ(y)V2/2; ρ(y) = 3,3 · 10-10y2 - 1,155 · 10-5y + 0,125; P = (10 + V2/a2(y))(25 000 - y)/12,5; a(y) = 340,3 - 4,08 · 10-3y; a(u1, u2 ) = u2 NG ; u1P + 4,6qS CS = (0,7 + 2(u1 - 0,3)2)u1P/3600; N = min ⎧ qS , 150 000 , 8⎫; ⎨ G g ⎬ ⎩ ⎭ Cx = 0,02 + 3,174α2 + 0,03u3. Начальные значения фазовых координат и управлений: x = 0, y = 5000, z = 0, V = 300, ψ = 0, θ = 0, G = 20 000, u1 = 0, u2 = 1/N, u3 = 0, u4 = 0. f f Целевые значения фазовых координат: yf = 7000, ψf = -π, θf = 0, u2 = 1/N, u4 = 0. На управления наложены следующие ограничения: 0,05 £ u1 £ 1, 0,01 £ u2 £ 1, 0 £ u3 £ 1, |u· | £ 0,2, |u· | £ 0,25, |u· | £ 1, |u· | £ 1,57. 1 2 3 4 Необходимо найти управления u1(t), u2(t), u3(t), u4(t) обеспечивающие перемещение самолета из начальной точки в целевую точку, заданную условиями, за кратчайшее время. Вычислительный эксперимент Для проведения вычислительного эксперимента по поиску оптимального управления самолетом при совершении боевого разворота использовались следующие данные: Значение целевой функции вычислялось по формуле ⎧t, если P(t) £e J = tf + P(tf) → min, где t f = ⎨ . ⎩t + - иначе Значение штрафа P(t) вычислялось по формуле P(t) = {[0,001(y(t) - y f)]2 + (ψ(t) - ψ f)2 + (θ(t) - θ f)2 + 2 + (u2(t) - uf)2 4 + (u4(t) - uf)2}1/2. Параметры модели имели следующие значения: t+ = 17,5, ε = 0,01, Δt = 0,25, M = ⎣17,5/0,25⎦ = 70, p = 4(M + 1) = 284, q- = [-0,5 -0,5 -0,5 -π]T, q+ = [2 2 2 π]T. Требовалось найти управление в виде: u- q + q - q t - i + < u- ⎟ ⎠ ⎧ ⎛ ⎞ ⎪ k , если ⎪ i + Mk ( i + M (k -1)+1 i + M (k -1) )⎜⎝ Ät 1 k ⎪ ⎛ ⎞ u t = ⎨u+ если q + q - q t - i +1 > u+ , k ( ) k , ⎪ i + M (k -1) ( i + M (k -1)+1 i + M (k -1) )⎜⎝ Ät ⎠⎟ k ⎪ ⎪qi + M (k -1) · (q i + M (k -1)+1 ⎛ - qi + M (k -1) )⎜⎝ 1⎟ t - i + ⎞ t - иначе ⎩ Ä ⎠ где iΔt £ t < (i + 1)Δt, i = 1, …, M, k = 1, 2, 3, 4. Решением задачи оптимального управления будет вектор параметров q = [q1, …, qp]T. Поиск вектора оптимальных параметров осуществлялся с помощью алгоритма «серого волка». Размер множества возможных решений в алгоритме «серого волка» составлял H = 32, максимальное число итераций W = 4096. В результате вычислений было получено значение целевой функции J = 0,0434. Результаты моделирования с полученными в ходе вычислений результатами проиллюстрированы (на рис. 1 показана траектория движения самолета, рис. 2 - изменение высоты полета во времени, рис. 3 - изменение угла наклона самолета во времени, рис. 4 - изменение направления движения самолета, рис. 5 - изображены графики изменения управлений во времени). y 7000 6800 6600 6400 6200 6000 5800 5600 5400 5200 5000 0 200 400 600 800 1000 1200 1400 1600 x Рис. 1. Оптимальная траектория движения самолета [Fig. 1. Optimal trajectory of the aircraft] y 7000 6800 6600 6400 6200 6000 5800 5600 5400 5200 5000 0 1 2 3 4 5 6 7 8 9 10 1112 13 141516 17 t q 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 0 1 2 3 4 5 6 7 8 9 10 1112 13 141516 17 t 75 Рис. 2. Изменение высоты полета во времени [Fig. 2. Aircraft altitude change] Рис. 3. Изменение угла наклона самолета во времени [Fig. 3. The angle of inclination of the aircraft] y 0 -0,2 -0,4 -0,6 -0,8 -1 -1,2 -1,4 -1,6 -1,8 -2 -2,2 -2,4 -2,6 -2,8 -3 0 1 2 3 4 5 6 7 8 9 10 1112 13 141516 17 t Рис. 4. Изменение направления движения самолета [Fig. 4. Aircraft direction] u1 u2 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 t 1 0,95 0,9 0,85 0,8 0,75 0,7 0,65 0,6 0,55 0,5 0,45 0,4 0,35 0,3 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 t u3 1 0,9 0,8 0,7 0,6 0,5 0,4 0,3 0,2 0,1 0 а б u4 1 2,8 2,6 2,4 2,2 2 1,8 1,6 1,4 1,2 1 0,8 0,6 0,4 0,2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 t 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 t в г Рис. 5. Графики оптимального управления: a - управление u1; б - управление u2; в - управление u3; г - управление u4 [Fig. 5. Graphs of optimal control: a - optimal control u1; b - optimal control u2; c - optimal control u3; d - optimal control u4] Выводы Основными сложностями при численном решении задач оптимального управления, редуцированных в задачу нелинейного программирования, являются неопределенность топологических свойств целевой функции в пространстве искомых параметров и большая размерность пространства поиска. Полученные в вычислительном эксперименте решение задачи оптимального управления боевым разворотом самолета результаты показали, что современный эволюционный алгоритм «серого волка» эффективно использовать для решения сложных задач оптимального управления.

Список литературы