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

На правах рукописи

Метлицкая Дарья Вадимовна

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

Специальность 05.13.18 Математическое моделирование, численные методы и комплексы программ Специальность 05.13.01 Системный анализ, управление и обработка информации (авиационная и ракетно-космическая техника)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

1 2 ДЕК 2013

Москва - 2013

005543902

Работа выполнена на кафедре «Математическая кибернетика» в Московском авиационном институте (национальном исследовательском университете).

Научный руководитель: доктор физико-математических наук,

профессор Пантелеев Андрей Владимирович

Официальные оппоненты: доктор физико-математических наук,

профессор Лемак Степан Степанович

доктор технических наук. Сыпало Кирилл Иванович

Ведущая организация: ФГБУП «Институт проблем информатики

Российской академии наук»

Защита состоится « 27 » декабря 2013 г. в 10 ч. 00 мин. на заседании Диссертационного совета Д 212.125.04 Московского авиационного института (национального исследовательского университета) по адресу: 125993, Москва, А-80, ГСП-3, Волоколамское шоссе, 4, Ученый совет МАИ.

С диссертацией можно ознакомиться в библиотеке Московского авиационного института (национального исследовательского университета).

Автореферат разослан «1Ьг> и г> У^1/71 2013 г.

Ученый секретарь Диссертационного совета ДД^И25.04__^

кандидат физико-математических Н. С. Северина

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Актуальность работы. Задачи поиска оптимального управления нелинейными детерминированными динамическими системами широко используются во многих сферах науки. Например, для описания движения объектов в технике, физике, химии, экономике и др. Традиционно часто такие задачи возникают в области авиационной и ракетно-космической техники. Для нахождения их точного аналитического решения используются необходимые и достаточные условия оптимальности детерминированных динамических систем, однако с использованием данных условий решение можно получить лишь для узкого круга задач. В большинстве случаев для нахождения приближенного решения необходимо применять численные методы. На сегодняшний день известны численные методы, разработанные Евтушенко Ю.Г., Моисеевым H.H., Крыловым И.А., Черноусько Ф.Л., Тихоновым А.Н., Васильевым Ф.П., Колмановским В.Б., Кротовым В.Ф., Гурманом В.И., Хрусталевым М.М., Федоренко Р.П., Брайсоном, Хо Ю-ши, Пропоем А.И., Габасовым Р.Ф., Кирилловой Ф.М., Батуриным В.А., Срочко В.А., Дыхтой В.А., Васильевым С.Н. и многими другими авторами.

В последнее время большое внимание в научной литературе уделяется ме-таэвристическим методам глобальной оптимизации, которые позволяют найти решение «высокого качества» за приемлемое (с практической точки зрения) .время. Описание данных методов можно найти в работах Дж. Холланда, А. Райта, С. Дасгупта, Ф. Хереро, Н. Хансена, Л. де Кастро, А. Дуарта, Ф. Гловера, Д. Гольдберга, А. Париса, Р. Марти и др. Метаэвристические методы могут применяться в ситуациях, когда практически полностью отсутствует информация о характере и свойствах исследуемой функции. Применением генетических и других эволюционных алгоритмов к задачам оптимального управления занимались 3. Михайлевич, И. Л. Лопес Круз, Н. В. Дакев. Полученные в их работах результаты показывают хорошую применимость метаэвристических методов к задачам оптимального управления и актуальность исследований в данной области.

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

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

1) проведение сравнительного анализа стратегий и характерных свойств шести эволюционных методов условной глобальной оптимизации: генетических

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

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

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

4) разработка модификаций, повышающих точность работы рассматриваемых эволюционных методов;

5) применение разработанного программного обеспечения для решения* модельных примеров и прикладных задач управления химическими процессами и летательным аппаратом класса «воздух-воздух»;

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

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

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

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

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

Апробация работы. Результаты диссертационной работы докладывались на 14 конференциях, обсуждались на научных семинарах в Московском авиационном институте и Государственном научно-исследовательском институте авиационных систем (ГосНИИАС). Исследования были поддержаны РФФИ (грант № 12-08-00892-а), и Министерством образования и науки РФ: ФЦП «Научные и .научно-педагогические кадры инновационной России» на 2009-2013 гг. (гос. контракту 02.740.11.0471), НИР «Математическое моделирование и оптимизация в задачах создания авиационной и ракетно-космической техники» в рамках государственного задания на оказание услуг (per. номер: 7.623.2011). Была произведена государственная регистрация разработанных программ (свидетельства №2013617278, №2013617279, №2013617280). Результаты диссертационной работы внедрены в практику научно-исследовательской деятельности ФГУП «ГосНИИАС» (акт о внедрении от 20 ноября 2013 г.).

Публикации. Основные результаты диссертационной работы опубликованы в статьях [1-13] в журналах, входящих в Перечень ВАК, в других изданиях [14-17] и в трудах научных конференций [18-34]. Получены 3 свидетельства о государственной регистрации программ [35-37]. Всего по теме диссертации опубликовано 37 работ.

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

Исследуемые в диссертационной работе эволюционные методы традиционно применяются к решению задачи оптимизации целевой функции f(x)=f(xl,x2,...,x„), определенной на множестве допустимых решений

D = {x\xt е[а),6/],/ = 1,2,...,и}сЯ", и позволяют найти ее условный глобальный максимум (минимум) на заданном множестве, т.е. такую точку х* е D, что /(**) = max Ддг) (/(**) = min/(*)).

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

В первой задаче (нахождения оптимального программного управления дискретными динамическими системами) поведение нелинейной детерминированной дискретной модели объекта управления описывается разностным урав-" нением

*(< + !) =/(',*('),"(')), (1) где t - дискретное время, / е 7" = [0,1,..., vV — 1]; х - вектор состояния системы, xeR"; и - вектор управления, и eU(t) с Rq; U(t) - множество допустимых значений управления, для каждого значения t представляющее собой прямое произведение отрезков [а,(0>/ =1,2,...,q; число шагов дискретного времени N задано; f(t,x,u) = (fl(t,x,u),...,fn(t,x,u))T - непрерывная вектор-функция. Правый конец траектории x(N) свободен.

Начальное условие: х(0)=хо. Применяется программное управление. Множество допустимых процессов D(0,x0) - это множество пар d = (х(-),и(-)), включающих траекторию *(-) = {хо,;с(1),...,д:(Л0} и допустимое управление и(-)={и(0).«(1)>—,u(N~l)}, где u(t)eU(t), удовлетворяющих уравнению состояния (1) и начальному условию.

На множестве D(0,х0) определен функционал качества управления

т = (/,Х(0М0) + F{x(N)) , (2)

1=0

где f°(t,x,u), F(x) - заданные непрерывные функции.

Требуется найти taKjro пару d* = (х * (■), и * (•)) е D(0, х0), что

I(d*) = шах 1(d). (3)

dtD{0,xtl)

Во второй задаче (нахождения оптимального программного управления непрерывными системами) поведение нелинейной детерминированной непре-. рывной модели объекта управления описывается дифференциальным уравнением

* = /(г,*(0,и(0), (4)

где х - вектор состояния системы, xsR"; и - вектор управления, и =(их,...,ич)Т <=U(t)<zfcq\ U(t) - множество допустимых значений управления, для каждого значения t представляющее собой прямое произведение отрезков [а,(ОАО)], (=l,2,...,g; t - непрерывное время, t^T = [t0,tN], начальный t0 и

конечный tN моменты времени заданы; f(t,x,u) = {fx{t,x,u),...,fn(t,x,u)f -

непрерывно-дифференцируемая вектор-функция. Правый конец траектории x{tN) свободен.

Начальное условие: x(t0)=x0. Предполагается, что система управления является разомкнутой по состоянию и применяется программное управление. Множество допустимых процессов D(t0,x0) - это множество пар d = (x(t),u(t)), включающих траекторию х(/) и кусочно-непрерывное допустимое управление "('). удовлетворяющих дифференциальному уравнению системы и начальному условию. На множестве допустимых процессов D(t0,x0) определен функционал качества управления

W = ]f\ux{t),u(t))dt +F{x{tN)), (5)

'о

где f°it,x,ú) и F(x) - заданные непрерывные функции.

Требуется найти такую пару d*=(x*(t),u*(/)) еD(t0,x0), что

I(d*) = шах 1(d). (6)

</£D(/0, Л0)

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

x = f(t,x(t),x(t-x),u(t)), (7)

где все обозначения аналогичны второй задаче, т£0 - величина запаздывания. Правый конец траектории x(tN) свободен. Начальное условие:

*(') = g(t). V/ е [-т, /0); x(t0 ) = х0. (8)

где g(t) - заданная кусочно-непрерывная вектор-функция. Предполагается, что система управления является разомкнутой по состоянию и применяется программное управление. На множестве допустимых процессов D{t0,x0) определен функционал качества управления вида (5). Требуется найти такую пару d* = (x* (t),u * (/)) е D(t0,x0), которая удовлетворяет (6).

В первой главе рассматриваются генетические алгоритмы (ГА) условной оптимизации с бинарным и вещественным кодированием. ГА имитируют в своей работе природные способы оптимизации: генетическое наследование и естественный отбор. При решении задачи в ГА используются конечные наборы возможных решений, называемые популяциями и состоящие из особей. Оптимизируемая целевая функция /(х) эквивалентна природному понятию приспособленности особи. В ГА с бинарным кодированием каждая особь представляет собой бинарную строку, полученную из вектора параметров x = (x¡,x2,...,xn)r eD при помощи операции кодирования. В ГА с вещественным кодированием каждая особь представляется набором вещественных чисел, т.е. самим вектором x = (xl,x2,...,xnf eD.

Применение ГА сводится к исследованию множества допустимых решений при помощи перехода от одной популяции к другой. При этом ГА имити-

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

Рис. 1. Общая схема работы генетического алгоритма

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

Во второй главе рассматриваются методы, имитирующие иммунные системы живых организмов: метод искусственных иммунных систем (ИИС) и расширенный метод искусственных иммунных систем.

Метод ИИС в своей работе использует идеи, заимствованные из иммунологии, имитируя работу иммунной системы живого организма. Рассматриваемая целевая функция /(х) эквивалентна природному понятию приспособленности иммунной клетки к борьбе с чужеродными телами и называется функцией приспособленности. Вектор параметров целевой функции х ~{хх,х2,...,х„)Т называется иммунной клеткой.

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

ляции применяются биологические операторы: клонирование, мутация и селекция. Во время операции клонирования часть клеток с лучшей приспособленностью клонируется. Получившиеся клоны подвергаются мутации. Если лучший из клонов-мутантов при этом оказывается лучше родительской клетки, то во время операции селекции он заменяет ее в популяции. Во время обновления популяции происходит замена клеток с худшим значением целевой функции на новые, сгенерированные случайным образом. Таким образом, формируется новая популяция. Метод заканчивает работу после того, как сформируется заданное количество популяций. Схема работы метода ИИС представлена на рис. 2.

Рис. 2. Общая схема работы метода ИИС

Проведенные в диссертационной работе исследования метода ИИС показали, что при решении задач поиска оптимального управления детерминированными системами, которые относятся к задачам высокой размерности, точность работы метода ИИС снижается. Для решения этой проблемы разработана модификация метод ИИС. Предлагается изменить оператор мутации. В отличие от классического оператора мутации, где изменению подвергались все координаты клетки, в предложенном операторе количество изменяющихся координат зависит от номера итерации метода. Каждая координата подвергается мутации с вероятностью %, определяемой формулой: Г 1, если к <в-К;

~ [1 + е-а/а: , если к>в-К.

Если номер текущей итерации к не превысил 9-100% (0 е [0,1] - параметр метода), от максимального числа итераций К, то вероятность мутации равна 1, иначе вероятность мутации линейно уменьшается таким образом, что на последней итерации она составляет 0. Также изменяется выражение, согласно которому происходит мутация. В новом операторе подвергшаяся мутации координата может принимать граничные значения из множества допустимых.

Еще одно изменение вносится на шаге обновления популяции. Для ускорения сходимости метода ИИС при добавлении новых клеток в популяцию используется оператор скрещивания, применяемый в ГА с вещественным кодированием. Каждая координата новой клетки х"е"' генерируется согласно выражению:

где х], х/ - I -е координаты первой и у -й клеток в упорядоченной популяции, и> - случайное число, описываемое равномерным законом распределения на отрезке [0;1]. Однако во избежание сходимости к локальным экстремумам половина

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

Особенностью расширенного метода ИИС является сочетание локального и глобального поиска решения. На каждой итерации глобального поиска осуществляется локальный поиск, после которого происходит сокращение популяции и добавление в популяцию новых клеток. Локальный поиск представляет собой итерационный процесс, во время которого к популяции применяются биологические операторы: клонирование, мутаг/ия и селекция, - и происходит смена популяции на новую. Расширенный метод ИИС заканчивает работу после генерации заданного числа популяций или если после завершения очередной итерации глобального поиска число оставшихся после сокращения клеток не изменилось. Общая схема работы метода представлена на рис. 3.

Рис. 3. Общая схема работы расширенного метода ИИС

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

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

Г0.25, если к<0ЯК; [0.1, если к>0.ЪК.

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

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

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

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

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

Стадия расширения состоит из нескольких этапов: локальное расширение, глобальное расширение и дополнительное расширение. На этапе локального расширения производится генерация новых узлов в направлении наилучшего из соседних. На этапе глобального расширения для каждого из узлов сетки генерируется новый узел в направлении наилучшего узла сетки. На этапе дополнительного расширения сетки производится исследование новых участков множества допустимых решений. На стадии сокращения в МДС происходит удаление слишком близких друг к другу решений. Общая схема работы МДС представлена на рис. 4.

Для решения задач поиска оптимального управления детерминированными системами, которые относятся к задачам большой размерности, разработана модификация МДС, повышающая точность его работы. В модифицированном МДС смягчаются условия удаления узлов на шаге сокращения сетки: худший из двух узлов удаляется, если они имеют более чем / близких координат, где / -параметр метода. В МДС без модификаций один из узлов удаляется, если они имеют хотя бы одну близкую координату. Внесенное изменение позволяет

Рис. 4. Общая схема работы метода динамических сеток

избежать слишком большого сокращения сетки и добиться сохранения информации об уже найденных «хороших» решениях.

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

Сравнение работы МДС и разработанной модификации на модельных и прикладных задачах показало, что модифицированный МДС работает лучше, чем метод без модификаций.

В первой, второй и третьей главах диссертации разработаны пошаговые методики применения эволюционных методов условной оптимизации к решению задач поиска оптимального программного управления нелинейными дискретными и непрерывными детерминированными динамическими системами. При использовании исследуемых в работе эволюционных методов для решения задач оптимального управления дискретными системами оптимизируется управление «(•). Целевой функцией является функционал 1{с1) = /(*(■),«(•))• Особь (клетка, узел) с номером к в популяции (сетке) представляет собой вектор и =(ик(0),ик(\),...,икЩ—\))Т, который соответствует дискретному управлению «*(■) = {г/(0),г/(1),...,г/(уУ-1)}. Для того чтобы найти значение функционала !Ык), соответствующее паре с!к = (хк(-), «*(•))> необходимо найти траекторию дискретной системы хк(-) ={.х(0),.х4(1),...,х*(Л0}, соответствующую управлению и (■), из разностного уравнения (1) с учетом начального условия.

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

В диссертационной работе приведены примеры работы эволюционных методов. Решены три модельные задачи поиска оптимального управления дискретными системами, три прикладные задачи поиска оптимального управления химическими процессами, модели которых представляют собой непрерывные, нелинейные системы, и две задачи поиска оптимального управления непрерывными системами с запаздыванием по выходным переменным. Число оптимизируемых переменных при этом изменялось от 10 до 160, а при исследовании зависимости точности решения от размерности задачи - до 800. Ниже приведены некоторые из решенных задач.

Пример 1. Поведение модели объекта управления описывается системой разностных уравнений:

х (,+!) =__• х- | n- x2{t)+u,(t)Xl(t + \).

' 1 + 0.01 •и,(0-(3 + м2(/))' 2 l+«,(0-(l + «2(0)'

х (, + 1) =_£ЕзСО_

1+0.01-м2(/)-(1+и3(О)' где t =0,1,-..,N—1; Л' - параметр задачи. Задано начальное состояние системы х(0)=[2, 5,7]7 и ограничения на управление 0<«1(/)<4, 0<u2(t)<4, 0 < u3(t) <0.5. На множестве допустимых процессов определен функционал качества

N-1

I=x?(N) + xl(N) + xl(N) +([2>i20 -1) +x|(i-l) + 2u^(t -1)] •

(=i

[f>320 -1) + 2",2(/ -1) + 2uj(t -l)])1'2. (=i

Требуется найти минимальное значение функционала и оптимальный процесс, на котором это значение достигается. Задача решалась для различного числа шагов системы N. Минимальное значение функционала, найденное эволюционными методами, представлено в табл. 1. Полученное решение сравнивалось с известным решением, найденным итерационным методом динамического программирования (ИДП).

Таблица 1. Результаты работы в примере 1

Метод N=20 N = 50 JV = 100

ГА бинарным кодированием 209.27381 241.01111 260.83801

ГА с вещественным кодированием 209.26937 240.91706 258.33987

Метод ИИС 211.74483 262.01719 326.71907

Модифицированный метод ИИС 209.27319 240.91904 258.34077

Расширенный метод ИИС 209.30731 241.37386 261.13136

Модифицир. расширенный метод ИИС 209.26945 240.93244 258.40943

мдс 216.73137 276.23071 353.11170

Модифицированный МДС 209.27319 240.92003 258.97413

Метод ИДП 209.26937 240.91700 258.33922

По полученным данным можно заметить, что большинству методов удалось найти решение, близкое друг к другу и к решению методом ИДП, а разработанные модификации значительно повышают точность работы эволюционных методов. Оптимальное управление, полученное ГА с вещественным кодированием для N = 20, представлено на рис. 5.

Ї Q-V-- V-...... V • • • Ul(t) v v u2(t) А » U3(t) .

• •

• • • ' ' , . :

.... ...

t

Рис. 5. Оптимальное управление в примере 1

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

- с/х, -17.6х,х2 - 23х,х6и3;

( = -дх6 +Ю2.6Х4Х5 - 23х]х6щ; , = -дх7 + 46х,х6и3;

4. \и2 - Ьи\ +

х8 = 5.8((7Х] -М4)-3.7Ы, +<] (23х4 +1 \х5 + 28х6 + 3 5х7 ) - 0.099

х2 = щ -цх2 ~\1 Ьххх2 -146X2X3;

= ^ срс^ 13х2х2 | х4 = -<?х4 + 35.2х,х2 — 51 .Зх4х5; х5 = -дх5 +21 9х2х3 — 51 .Зх4х5; где <у = щ +и2 + и4, 0 <1 =0.2. Начальное условие:

х(0) = [0.1883; 0.2507; 0.0467; 0.0899; 0.1804; 0.1394; 0.1046; 0]Т. Ограничения на управление: 0 < и, (<) < 20,0 < и2 (/) < 6,0 < щ (/) < 4,0 < м4 (/) < 20. Критерий качества управления: 1 = х8(7Л,). Необходимо максимизировать критерий при помощи выбора кусочно-постоянного управления, удовлетворяющего заданным ограничениям. Задача решалась для различного числа N точек разбиения при переходе к дискретной системе. Максимальное значение функционала, найденное эволюционными методами, представлено в табл. 2. Полученное решение сравнивалось с известным решением, найденным итерационным методом динамического программирования (ИДП).

Метод N=11 N = 20 ТУ =40

ГА бинарным кодированием 21.7660 21.7938 21.7745

ГА с вещественным кодированием 21.7660 21.7973 21.8178

Метод ИИС 21.1552 20.9672 20.6444

Модифицированный метод ИИС 21.7483 21.7970 21.8007

Расширенный метод ИИС 21.5073 21.0973 20.8627

Модифицир. расширенный метод ИИС 21.7482 21.7935 21.6588

МДС 20.4297 20.2702 21.7950

Модифицированный МДС 21 7483 19.7823 21.8118

Метод ИДП 21.7572 — —

По полученным данным можно сделать вывод, что ГА удалось улучшить решение, найденное методом ИДП, а большинству остальных методов удалось найти близкое друг к другу решение. При увеличении размерности задачи получено более высокое значение функционала. Разработанные модификации методов повышают точность их работы. Оптимальное управление, полученное модифицированным методом ИИС для А^ = 11, представлено на рис. 6.

— и1(0 -- и2<0 ■•■ 113(0 ..........44(0

аоо 0.05 0.10 0.15 0.20

[

Рис. 6. Оптимальное управление в примере 2

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

х, = х2(/);

х2 = -1 Ох, (/) - 5 х2 (0 - 2х, (г - т) - х2 (г - т) + х3 = 0.5(1 Ох,2 (0 + х2 (0 + г/2 (/)), где 0</ </дг =5, х- время запаздывания, параметр задачи. Начальное условие: х,(/) =х2(0 = 1, -т</<0, х3(0) = 0. Ограничения на управление: -1<м<1. Критерий качества управления: / =х3(?д,). Необходимо минимизировать критерий при помощи выбора кусочно-линейного управления, удовлетворяющего заданным ограничениям.

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

Таблица 3. Результаты работы в примере 3

Метод N=10 N = 20

т = 0.5 т = 1 т = 0.5 т = 1

ГА бинарным кодированием 2.6080 2.9307 2.6066 2.9295

ГА с вещественным кодированием 2.6079 2.9307 2.6067 2.9295

Метод ИИС 2.6077 2.9304 2,6067 2.9296

Модифицированный метод ИИС 2.6077 2.9304 2.6066 2.9295

Расширенный метод ИИС 2.6077 2.9305 2.6067 2.9295

Модифицир. расширенный метод ИИС 2.6077 2.9304 2.6066 2.9295

МДС 2.6121 2.9399 2.6217 2.9402

Модифицированный МДС 2.6077 2.9304 2.6066 2.9295

Метод ИДП 2.6076 2.9302 2.6064 2.9292

По полученным результатам видно, что эволюционным методам удалось найти решение, близкое к решению, найденному методом ИДП. Разработанные модификации методов позволяют улучшить найденное методами без модификаций решение. Оптимальное управление, полученное модифицированным МДС для N = 20, т = 0.5 и т = 1, представлено на рис. 7.

Рис. 7. Оптимальное управление в примере 3

В диссертационной работе рассмотрена прикладная задача управления ракетой класса «воздух-воздух» средней дальности AIM-120. Требуется перевести ракету из начального положения с заданными начальными условиями в точку, характеризуемую заданной высотой, при фиксированном времени полета ракеты, обеспечивая: а) максимальную дальность полета; б) максимальную среднюю скорость полета.

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

б = £ (и - cos(9 + -i-)); V = g(R-cosa-F*o6 _sin(0 + -2L-));

V h + R3 mg h + R3

jc = Kcos9; y=V • sin 0, где x,y - горизонтальная и вертикальная координаты ракеты, V - модуль скорости ракеты, 0 - угол наклона траектории; и sU(t) с R - управляемая величина; U(t) - заданное множество допустимых значений управления: U(t) —\a(t),b(t)]\ а - угол атаки; g - ускорение свободного падения; R, - радиус Земли; h - высота над поверхностью Земли; т - масса ракеты; R - тяга двигателя ракеты; Fno- -сила лобового сопротивления; t е.Т = \tQ,tN\, начальный и конечный моменты времени заданы.

Начальное состояние системы задано: x(l0)= xQ, y(t0) = у0, 0(/о) = 90, V(t0) = V0 . Запуск ракеты считается успешным, если конечная высота ракеты отличается от заданной высоты не более чем на 200 метров, т.е. на правом конце траектории должно выполняться условие: |>'(/Л,)->'Л,|<200, где yN - заданное значение. На множестве допустимых процессов D определен функционал качества управления 1(d). В случае, когда требуется максимизировать дальность полета ракеты, функционал качества имеет вид:

m=C,(y-yN)2+%, (9)

xN

где С\ и С2 — весовые коэффициенты, которые выбираются таким образом, чтобы оба слагаемых имели одинаковый порядок. В случае, когда требуется максимизировать среднюю скорость, функционал качества имеет вид:

m=c,(y-yN)2+^, (Ю)

— — S1 1 <N

где V - средняя скорость ракеты, V = — = — j" F(t)dx, S - путь, пройденный ра-

lN lN о

кетой за время tN., V(x) - скорость ракеты в момент времени т, С: и С2 - весовые коэффициенты, выбираемые аналогично предыдущему случаю.

Требуется найти такую пару d* =(х* (t),u*(f)) eD, которая обеспечивает минимум функционала на множестве допустимых процессов.

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

Рис. 8. Оптимальное управление и траектория, полученные для задачи поиска оптимального управления ракетой класса «воздух-воздух»

В четвертой главе приведена структура и примеры работы комплекса программ «Эволюционные методы глобальной условной оптимизации в задачах поиска оптимального управления детерминированными системами». Комплекс был разработан в среде Microsoft Visual Studio 2010, на языке С#. Он содержит пять модулей, реализующих алгоритмы эволюционных методов, в каждом из которых имеется несколько подмодулей для решения трех задач поиска: глобального условного экстремума функций многих переменных, оптимального программного управления дискретными детерминированными системами и оптимального программного управления непрерывными детерминированными системами. Для генетических алгоритмов и методов, имитирующих иммунные системы организмов, в комплекс программ включен специализированный модуль решения прикладной задачи нахождения оптимального управления летательным аппаратом.

Кроме рассматриваемых в первых трех главах эволюционных методов, в комплекс включены: метод рассеивания с модификациями и две эволюционные

стратегии преобразования ковариационной матрицы. Общая схема комплекса представлена на рис. 9.

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

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

Рис. 9. Общая структура комплекса программ

Рис. 10. Задача поиска условного глобального экстремума функций

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

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

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

В приложении 1 приведены характеристики и техническая постановка задач управления ракетой типа «воздух-воздух», решаемых в первой и второй главах.

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

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

ОСНОВНЫЕ НАУЧНЫЕ РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

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

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

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

Публикации в журналах перечня ВАК

1. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с бинарным и вещественным кодированием для приближенного синтеза субоптимального управления детерминированными системами // Автоматика и телемеханика. 2011,№ 11.-С. 117-129.

2. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с вещественным кодированием к задаче оптимального управления дискретными системами // Вестник компьютерных и информационных технологий. №9, 2011. — С. 17-23.

3. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с бинарным кодированием к задаче поиска оптимального управления непрерывными детерминированными системами// Авиакосмическое приборостроение. №2, 2011.-С. 23-30.

4. Пантелеев A.B., Метлицкая Д.В. Формирование генетических алгоритмов с вещественным кодированием в задаче синтеза оптимального управления дискретными системами //Авиакосмическое приборостроение. №3,2011,- С.26-31.

5. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с бинарным кодированием к задаче оптимального управления дискретными системами // Научный вестник МГТУ ГА. 2010, № 157,- С. 34-41.

6. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов к задаче оптимального управления дальностью полета летательного аппарата типа

воздух-воздух // Вестник Московского авиационного института. 2011, №4, т. 18. -С. 102-113.

7. Пантелеев А. В., Метлицкая Д. В. Применение метода искусственных иммунных систем в задачах поиска условного экстремума функций // Научный вестник МГТУ ГА. 2012, № 184. - С. 54-61.

8. Пантелеев А. В., Метлицкая Д. В. Формирование генетических алгоритмов поиска оптимального управления средней скоростью полета летательного аппарата типа воздух-воздух // Вестник Московского авиационного института. 2012, №3, т. 19.-С. 149-159.

9. Пантелеев A.B., Метлицкая Д. В. Приближенный синтез оптимального управления дискретными системами с помощью генетических алгоритмов с вещественным кодированием// Научный вестник МГТУ ГА. 2011, № 169. -С. 13-19.

10. Пантелеев А.В, Метлицкая Д.В. Модифицированный метод искусственных иммунных систем в задачах поиска оптимального управления дискретными системами // Информационные и телекоммуникационные технологии. 2012, № 14. -С. 43-51.

11. Пантелеев A.B., Метлицкая Д.В. Комплекс программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // Электронный журнал «Труды МАИ», №37, 2010, http://www.mai.ru/science/trudy/published.php?ID=13421.

12. Метлицкая Д.В. Генетические алгоритмы поиска оптимального управления непрерывными детерминированными системами // Электронный журнал «Труды МАИ», №45,2011, http://www.mai.ru/science/trudy/published. php?ID=25544.

13. Пантелеев А. В., Метлицкая Д. В. Применение метода динамических сеток в задачах поиска оптимального управления дискретными детерминированными системами // Научный вестник МГТУ ГА. 2013, №195. С. 21-28.

Публикации в других изданиях

14. Пантелеев A.B., Метлицкая Д.В. Применение генетических алгоритмов с бинарным и вещественным кодированием к задаче поиска условного экстремума функций // Теор. вопр. выч. техн. и прогр. обеспеч. Межвуз. сб. научн. тр., МИРЭА, 2010.-С. 156-165.

15. Метлицкая Д.В. Алгоритмическое обеспечение модифицированного метода искусственных иммунных систем // Теор. вопр. выч. техн. и прогр. обеспеч. Межвуз. сб. научн. тр., МИРЭА, 2011. - С. 81-86.

16. Пантелеев А.В, Метлицкая Д.В. Комплекс программных средств «Генетические алгоритмы с бинарным и вещественным кодированием в задачах синтеза оптимального управления дискретными и непрерывными динамическими системами» // Проблемы авиастр., косм, и ракетостр.: Сб. науч. тр. - М.: Изд-во Ваш полиграфический партнер, 2012. - С. 296-302.

17. Метлицкая Д.В. Применение метода искусственных иммунных систем для оптимизации стоимостных показателей предприятия // Научный альманах. Вып. 16: Материалы VIII научно-практической конференци молодых ученых и студентов «Инновационный менеджмент в аэрокосмической промышленности». — М.: Изд-во «Доброе слово», 2012. - С. 174-182.

Доклады на научных конференциях

18. Метлицкая Д.В. Разработка комплекса программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // XLVIII Межд. научная студ. конф. «Студент и научно-технический прогресс», Новосибирск, 2010: Тез. докл. - Новосибирск: Новосиб. гос. ун-т, 2010. - С. 168-169.

19. Метлицкая Д.В. Лабораторный практикум «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // VII Всеросс. конф. студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования», Москва, 2010: Тез. докл. - М.: Вузовская книга, 2010. -С. 129-130.

20. Метлицкая Д.В. Разработка комплекса программных средств «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // XLVI Всеросс. конф. по проблемам математики, информатики, физики и химии, Москва, 2010: Тез.'докл. Секции математики и информатики. - М.: РУДН, 2010.-С. 26-28.

21. Метлицкая Д.В. Разработка лабораторного практикума «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // Научно-практическая конф. студентов и молодых ученых МАИ «Инновации в авиации и космонавтике — 2010», Москва, 2010: Тез. докл. - СПб.: Мастерская печати, 2010.-С. 288-289.

22. Метлицкая Д.В. Разработка лабораторного практикума «Генетические алгоритмы условной оптимизации с бинарным и вещественным кодированием» // II Межд. научно-практической конф. "Научно-техническое творчество молодежи -путь к обществу, основанному на знаниях", Москва, 2010: Сборн. научн. докл. -М: МГСУ, 2010. - С. 433-435.

23. Метлицкая Д.В. Генетические алгоритмы с бинарным и вещественным кодированием в задачах синтеза оптимального управления непрерывными динамическими системами // 9-я Межд. конф. «Авиация и космонавтика - 2010», Москва, 2010: Тез. докл. - СПб.: Мастерская печати, 2010. - С. 388.

24. Метлицкая Д.В. Применение генетических алгоритмов с бинарным и вещественным кодированием к задаче поиска оптимального управления непрерывными детерминированными системами // Конкурс научно-технических работ и проектов «Молодежь и будущее авиации и космонавтики - 2010», Москва, Аннотация работ. -СПб: Мастерская печати, 2010. - С. 128-129.

25. Метлицкая Д.В. Генетические алгоритмы с бинарным и вещественным кодированием в задачах поиска оптимального управления динамическими системами // Материалы XLIX Межд. научной студ. конф. «Студент и научно-технический прогресс»: Математика / Новосиб. гос. ун-т., 2011. - С. 173.

26. Метлицкая Д.В. Применение генетических алгоритмов с бинарным и вещественным кодированием к задаче поиска оптимального управления летательным аппаратом» // Научно-практическая конф. студентов и молодых учёных МАИ «Инновации в авиации и космонавтике - 2011», 2011, Москва. Сборник тезисов докладов. - М.: МЭЙЛЕР, 2011. - С. 107-108.

27. Метлицкая Д.В. Комплекс программных средств «Генетические алгоритмы с бинарным и вещественным кодированием в задачах поиска оптимального управления динамическими системами» // Материалы XVII Межд. конф. по вычис-

лительной механике и современным прикладным программным системам (ВМСППС'2011), 2011. Алушта. - М.: Изд-во МАИ-ПРИНТ, 2011. - С. 711-713.

28. Метлицкая Д.В. Применение модифицированного метода искусственных иммунных систем к задачам поиска оптимального управления дискретными динамическими системами // 10-я Межд. конф. «Авиация и космонавтика - 2011», Москва, 2011: Тез. докл. - СПб.: Мастерская печати, 2011. - С. 238.

29. Метлицкая Д.В. Методы, основанные на искусственных иммунных системах, в задачах поиска глобального условного экстремума функций многих переменных // L Межд. научная студ. конф. «Студент и научно-технический прогресс», Новосиб., 2012: Тез. докл. - Новосиб.: Новосиб. гос. ун-т., 2012.-С. 178.

30. Метлицкая Д.В. Генетические алгоритмы в задаче поиска оптимального управления средней скоростью полета летательного аппарата // Инновации в авиации и космонавтике - 2012. Московская научно-практическая конф. молодых ученых, Москва, 2012: Тез. докл. -М.: ООО «Принт-салон», 2012. - С. 247-248.

31. Метлицкая Д.В. Поиск оптимального управления дискретными системами с помощью модифицированного метода искусственных иммунных систем // Межд. научно-методич. конф. "Информатизация инженерного образования (Инфорино-2012)", Москва, 2012: Тез. докл.-М.: Издательский дом МЭИ, 2012. - С. 214-215.

32. Метлицкая Д.В. Применение метода искусственных иммунных систем в задаче поиска оптимального управления детерминированными системами // 11-я Межд. конф. «Авиация и космонавтика — 2012», Москва, 2012: Тез. докл. — СПб.: Мастерская печати, 2012. — С. 388.

33. Метлицкая Д.В. Применение метода рассеивания в задачах поиска оптимального программного управления детерминированными системами // Московская молодежная научно-практич. конф. «Инновации в авиации и космонавтике -2013», Москва, 2013: Тез. докл.-М.: ООО «Принт-салон», 2013.-С. 288-289.

34. Метлицкая Д.В. Применение метода динамических сеток в задачах поиска оптимального программного управления детерминированными системами // Материалы XVIII Межд. конф. по вычислительной механике и современным прикладным программным системам (ВМСППС'2013), 2013, Алушта. - М.: Изд-во МАИ-ПРИНТ, 2013. - С. 777.

Свидетельства о государственной регистрации программ

35. Метлицкая Д.В. Применение генетических алгоритмов глобальной оптимизации с бинарным и вещественным кодированием в задаче оптимального управления дальностью полета летательного аппарата типа «воздух-воздух» / Метлицкая Д.В. // Св-во о гос. регистрации программы для ЭВМ № 2013617278. Федеральная служба по интеллект. собствеиности.-07.08.2013.

36. Метлицкая Д.В. Применение генетических алгоритмов глобальной оптимизации с бинарным и вещественным кодированием в задаче оптимального управления средней скоростью полета летательного аппарата типа «воздух-воздух» / Метлицкая Д.В. // Св-во о гос. регистрации программы для ЭВМ № 2013617279. Федеральная служба по интеллект. собственности.-07.08.2013.

37. Метлицкая Д.В. Применение методов глобальной оптимизации, имитирующих иммунные системы живых организмов, в задаче оптимального управления дальностью полета летательного аппарата типа «воздух-воздух» / Метлицкая Д.В. // Св-во о гос. регистрации программы для ЭВМ № 2013617280. Федеральная служба по интеллект. собственности.-07.08.2013.

Подписано в печать; 22 11.13 Тираж: 100 экз. Заказ № 1067 Отпечатано в типографии «Реглет» Москва, Ленинградский проспект д.74 (495)790-47-77 www reglet.ru

МОСКОВСКИЙ АВИАЦИОННЫЙ ИНСТИТУТ (национальный исследовательский университет)

На правах рукописи

04201451809

Метлицкая Дарья Вадимовна

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

05.13.18 - Математическое моделирование, численные методы

и комплексы программ 05.13.01 - Системный анализ, управление и обработка информации

(авиационная и ракетно-космическая техника)

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель

доктор физико-математических наук,

профессор А. В. Пантелеев

Москва 2013

ОГЛАВЛЕНИЕ

Введение.............................................................................................................................................5

Глава 1. Применение генетических алгоритмов......................................................................18

1.1. Генетический алгоритм с бинарным кодированием.........................................................18

111 ПпТ1Г»ОШ1А ОТПОТПГ1Ш ГТГЧТТГ»Т/-а ГПЛ^ОТТТЛГЛГЛ 1 Q

1 J. *

1.1.2. Применение генетического алгоритма с бинарным кодированием в задаче нахождения оптимального программного управления дискретными системами.........25

1.1.3. Применение генетического алгоритма с бинарным кодированием в задаче нахождения оптимального программного управления непрерывными системами......28

1.2. Генетический алгоритм с вещественным кодированием.................................................32

1.2.1. Описание стратегии поиска глобального экстремума...........................................32

1.2.2. Применение генетического алгоритма с вещественным кодированием в задаче нахождения оптимального программного управления дискретными системами.........33

1.2.3. Применение генетического алгоритма с вещественным кодированием в задаче нахождения оптимального программного управления непрерывными системами......36

1.3. Примеры применения генетических алгоритмов............................................................39

1.3.1. Задачи оптимального управления дискретными системами.................................39

1.3.2. Задачи оптимального управления непрерывными системами..............................45

1.3.3. Задачи оптимального управления летательным аппаратом..................................53

1.3.4. Рекомендации по выбору параметров алгоритмов.................................................60

1.4. Выводы................................................................................................................................62

Глава 2. Применение методов, имитирующих иммунные системы организмов...............63

2.1. Метод искусственных иммунных систем..........................................................................63

2.1.1. Описание стратегии поиска глобального экстремума...........................................63

2.1.2. Применение метода искусственных иммунных систем в задаче нахождения оптимального программного управления дискретными системами..............................65

2.1.3. Применение метода искусственных иммунных систем в задаче нахождения оптимального программного управления непрерывными системами...........................70

2.2. Расширенный метод искусственных иммунных систем..................................................72

2.2.1. Описание стратегии поиска глобального экстремума...........................................72

2.2.2. Применение расширенного метода искусственных иммунных систем в задаче нахождения оптимального программного управления дискретными системами.........74

2.2.3. Применение расширенного метода искусственных иммунных систем в задаче

нахождения оптимального программного управления непрерывными системами......80

2.3. Примеры применения методов, имитирующих иммунные системы организмов........83

2.3.1. Задачи оптимального управления дискретными системами.................................83

2.3.2. Задачи оптимального управления непрерывными системами..............................85

2.3.3. Задачи оптимального управления летательным аппаратом..................................98

2.4. Выводы..............................................................................................................................102

Глава 3. Применение метода динамических сеток................................................................103

5.1. Метод динамических сеток...............................................................................................103

5.1.1. Описание стратегии поиска глобального экстремума.........................................103

5.1.2. Применение метода динамических сеток в задаче нахождения оптимального программного управления дискретными системами.....................................................105

5.1.3. Применение метода динамических сеток в задаче нахождения оптимального программного управления непрерывными системами..................................................111

5.2. Примеры применения метода динамических сеток........................................................114

5.2.1. Задачи оптимального управления дискретными системами...............................114

5.2.2. Задачи оптимального управления непрерывными системами............................116

5.2.3. Рекомендации по выбору параметров метода.......................................................123

5.3. Выводы................................................................................................................................124

Глава 4. Комплекс программ.....................................................................................................125

4.1. Структура комплекса.........................................................................................................125

4.2. Возможности комплекса....................................................................................................127

4.3. Примеры работы комплекса..............................................................................................128

4.3.1. Задача поиска глобального экстремума функций многих переменных.............128

4.3.2. Задача поиска оптимального программного управления дискретными системами...........................................................................................................................132

4.3.3. Задача поиска оптимального программного управления непрерывными системами...........................................................................................................................133

4.4. Выводы...............................................................................................................................135

Заключение....................................................................................................................................136

Библиографический список.......................................................................................................137

Приложение 1. Характеристики и техническая постановка задачи поиска

оптимального управления ракетой..........................................................................................147

3

Приложение 2. Набор тестовых функций................................................................................151

Приложение 3. Метод рассеивания...........................................................................................156

П3.1. Описание стратегии поиска глобального экстремума.................................................156

П3.2. Применение метода рассеивания в задаче нахождения оптимального

программного управления дискретными системами.....................................................159

программного управления непрерывными системами..................................................166

П3.4. Рекомендации по выбору параметров метода..............................................................168

П3.5. Примеры применение метода рассеивания...................................................................170

Приложение 4. Эволюционные стратегии преобразования ковариационной

матрицы..........................................................................................................................................173

П4.1. Эволюционная стратегия преобразования ковариационной матрицы.......................173

П4.1.1. Описание стратегии поиска глобального экстремума......................................173

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

дискретными системами...................................................................................................174

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

непрерывными системами................................................................................................177

П4.2. Модифицированная эволюционная стратегия преобразования ковариационной

матрицы...............................................................................................................................179

П4.2.1. Описание стратегии поиска глобального экстремума......................................179

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

управления дискретными системами...............................................................................180

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

управления непрерывными системами............................................................................183

П4.3. Примеры применения эволюционных стратегий преобразования ковариационной матрицы..............................................................................................................................185

ВВЕДЕНИЕ

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

Основополагающими результатами, полученными в теории оптимального управления, являются принцип максимума JI.C. Понтрягина [87], метод динамического программирования Р. Беллмана [5], достаточные условия оптимальности В. Ф. Кротова [24]. На их основе созданы различные методы решения задач оптимального управления.

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

Для решения задач оптимального управления динамическими детерминированными системами к настоящему времени получены необходимые и достаточные условия оптимальности. Однако при этом возникают трудности, связанные с необходимостью решать краевую задачу, с большой размерностью систем и их нелинейностью, с многоэкстремалыюстыо задачи, а также с наличием ограничений на управление и вектор состояния. Поэтому точное аналитическое решение задач оптимального управления возможно получить лишь для узкого круга задач. В связи с перечисленными трудностями построения аналитического решения большое значение получили приближенные и численные методы решения задач оптимального управления, которым посвящены работы Ю.Г. Евтушенко, H.H. Моисеева, А.Б. Куржан-ского, Р.П. Федоренко, И.А. Крылова, Ф.Л. Черноусько, А.Н. Тихонова, Ф.П. Васильева, В.Б. Колмановского, II. Н. Красовского, А. М. Летова, С.Н. Васильева, В.Ф. Кротова, В.И. Гурмана, М.М.Хрусталева и многих других.

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

К первому подходу относятся итерационные процедуры на основе принципа максимума Понтрягина (ПМ) и классического вариационного исчисления, которые основываются на сведении задачи оптимального упоавления к коаевой задаче с использованием необходимых условий оптимальности. Подобные методы разрабатывались и широко применялись для численного решения задач оптимального управления в работах В.К. Исаева, В.В. Сонина, В.Н. Лебедева [26], Г.Л. Гродзовского [13], H.H. Моисеева [54], Брайсона и Хо Ю-ши [6] и многих других. Итерационные процедуры ПМ также связаны с локальными и нелокальными аппроксимациями функционалов, вспомогательными задачами на максимум функции Понтрягина, разнообразными схемами игольчатого варьирования управлений, процедурами нелокального улучшения. Для дискретных систем аналогичные подходы развивались в работах А. И. Пропоя, Р. Габасова и Ф. М. Кирилловой [88, 9].

Вторую группу образуют методы, в основе которых лежат итерационные процессы в пространстве управляющих функций с использованием формул для приращения функционала качества. Для этого используются либо формулы классического вариационного исчисления (такие методы называют градиентными методами оптимального управления), либо соотношения, связанные с ПМ Понтрягина (методы последовательных приближений). Градиентные методы в пространстве управляющих функций, использующие формулы для первой вариации функционала качества, и методы штрафных функций, были предложены в работах Л. И. Шатровского [97], Т. М. Энеева [98], Брайсона, Денхэма [108], Хо Ю-ши [124] и др. Метод последовательных приближений, основанный на принципе максимума Понтрягина, был предложен в работах: Келли, Коппа, Мойера [128], И. А. Крылова, Ф. Л. Черноусь-ко [25]. Дальнейшей разработке метода и улучшению скорости сходимости посвящены работы И. А. Крылова, Ф. Л. Черноусько, Н. В. Баничука. Градиентные методы используют классические и неклассические вариации функционалов, вспомогательные задачи на минимум вариаций, квазиградиентные процедуры.

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

работы Н. Н. Моисеева [53], В. И. Коробова [23], JI. Д. Подвального [85], Р. П. Федоренко [95], Р. Jlyyca [131].

Еще одну группу методов образуют методы улучшения на основе условий оптимальности Кротова. К ним относятся приближенные и численные методы оптимального управления непрерывными и дискретными системами: итерационные методы первого и второго порядков поиска с использованием достаточных условий локальной оптимизации Гурмана В. И., а также методы на основе полиномиальной аппроксимации решения уравнения Беллмана и траекторного восстановления функции цены. Данному направлению посвящены работы Гурмана В. И., Хрусталева М.М., Батурина В.А., Срочко В.А., Дыхта В.А., Аручинцева A.B.

Методы пятой группы характеризуются общим подходом, связанным с применением алгоритмов нелинейного программирования. Он заключается в дискретной аппроксимации задачи оптимального управления и адаптации конечномерных методов оптимизации к получающимся дискретным задачам управления. Это направление развивалось в работах Н. Н. Моисеева, Ю. Г. Евтушенко, 10. М. Ермольева, Ф. П. Васильева и др.

Кроме вышеописанных групп методов существуют методы, основанные на анализе множеств достижимости [15], нелокальные методы улучшения [7], методы, основанные на многомерных аппроксимациях и параллельных вычислениях [17] и многие другие. Кроме того, существуют перспективные направления развития новых методов, связанные с комбинированием различных методов в процессе решения задач [94] и использованием растущих возможностей современной вычислительной техники.

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

В диссертационной работе для решения задач оптимального управления нелинейными дискретными и непрерывными детерминированными динамическими системами применяются эволюционные методы глобальной оптимизации. Данные методы относятся к ме-таэвристическим методам глобальной оптимизации, которые позволяют найти решение «высокого качества» за приемлемое (с практической точки зрения) время. Описание данных методов можно найти в работах Дж. Холланда, А. Райта, С. Дасгупта, Ф. Хереро, Н. Хансена, Л. де Кастро, А. Дуарта, Ф. Гловера, Д. Гольдберга, А. Париса, Р. Марти и многих других.

В своей классической постановке эволюционные методы применимы к решению задачи оптимизации многопараметрической целевой функции

f(x) = f{xx,x2,...,xn), (В.1)

определенной на множестве допустимых решений D = {x\xj е [а,,£,], / = 1,2,...,«}с: R", и позволяют найти ее условный глобальный максимум (минимум) на заданном множестве, т.е. такую точку х* е D, что

/(**) = шах f(x) ( f(x*) = min f(x) ). (B.2)

*e£> xsD

Задача поиска минимума функции /(х) сводится к задаче поиска максимума путем замены знака перед функцией на противоположный: /(**) = min f(x) = -max[-/(jc)].

xeD xeD

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