На правах рукописи
Маджара Тарас Игоревич
ИНТЕЛЛЕКТУАЛЬНАЯ СИСТЕМА ДЛЯ РЕШЕНИЯ
ЗАДАЧ ОПТИМАЛЬНОГО УПРАВЛЕНИЯ С
ВЫЧИСЛИТЕЛЬНЫМИ ОСОБЕННОСТЯМИ
05.13.01 – Системный анализ, управление
и обработка информации
АВТОРЕФЕРАТ
диссертации на соискание ученой степени кандидата технических наук
Владивосток 2011
Работа выполнена в лаборатории оптимального управления Института динамики систем и теории управления Сибирского отделения РАН (ИДСТУ СО РАН).
Научный руководитель: доктор технических наук Горнов Александр Юрьевич
Официальные оппоненты: чл.-корр. РАН, доктор физико-математических наук, профессор Федотов Анатолий Михайлович доктор технических наук, профессор Жирабок Алексей Нилович
Ведущая организация: Институт программных систем им. А.К. Айламазяна РАН (г. Переславль-Залесский)
Защита состоится « 05 » декабря 2011 г. в 14 часов на заседании диссертационного совета Д 005.007.01 в Институте автоматики и процессов управления ДВО РАН по адресу: 690041, г. Владивосток, ул. Радио, 5.. Иркутск, ул. Лермонтова,
С диссертацией можно ознакомиться в библиотеке Института автоматики и процессов управления ДВО РАН.
Автореферат разослан « 03 » ноября 2011 г.
Ученый секретарь диссертационного совета Д 005.007.01, к.т.н. А.В. Лебедев
ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ
Актуальность работы. В настоящее время при решении сложных практических задач, направленных на создание или изучение объектов и процессов в самых разных областях человеческой деятельности, все чаще используются методы системного анализа. Одним из наиболее востребованных средств исследования закономерностей функционирования и развития таких объектов и процессов стали задачи оптимального управления (ЗОУ), охватывающие широкий спектр проблем, таких как динамика полета вертолетов [В.И. Гурман, В.А. Батурин], самолетов и других летательных аппаратов на различных этапах полета [А.И. Тятюшкин, R. Pytlak, R.B. Viner], управление космическими [Р.П. Федоренко] и подводными [M. Chyba, T.
Haberkorn, S.B. Singh, R.N. Smith, S.K. Choi] аппаратами, ядерными [Л.Т.
Ащепков] и биохимическими [S. Park, W.F. Ramirez] реакторами и многих других. Естественным продолжением теоретических разработок в области численных методов решения ЗОУ стала их реализация на ЭВМ в виде многочисленных комплексов программ. Однако было отмечено, что подавляющее большинство успешно решенных практических задач потребовало привлечения авторов этих программных комплексов, одновременно выступающих в роли экспертов по оптимизации. Решение каждой конкретной практической задачи нуждалось в ручном поиске оригинального вычислительного сценария, предусматривающего многократный запуск комплекса с уточнением алгоритмических параметров и анализом промежуточных результатов, осуществляемых самим разработчиком.
Необходимость его привлечения объяснялась многими факторами, в числе которых объективная трудность решения задач оптимизации динамических систем, основную роль в преодолении которой играет не столько простое применение самого численного метода, сколько наличие у пользователя опыта и глубинных знаний предметной области. Понимание этого факта диктовало необходимость дальнейшего усовершенствования методов и средств решения ЗОУ. В частности, вместо использования численного метода в виде последовательности шагов было предложено разработать интеллектновычислительный метод, представляющий собой процесс логического анализа, формирующего ту или иную последовательность вычислений, причем отдельные вычисления, в свою очередь, «встроены» в процесс анализа. Сам метод оптимизации в этом случае перестает существовать в традиционном его понимании и превращается в гибрид метода логического вывода и простых вычислений [Коршунов, Коткин, 1991]. Одним из малоисследованных классов ЗОУ, требующих применения экспертного опыта в процессе численного решения, является класс задач с вычислительными особенностями, вызывающими аварийные отказы («АВОСТы») оптимизационных алгоритмов, и, как следствие, не допускающих прямое применение существующих средств оптимизации.
На основании рассмотренных выше задач и требований можно выделить следующие актуальные направления в разработке методов численного решения сложных прикладных ЗОУ с использованием современных программных систем:
1. Исследование класса задач оптимального управления с вычислительными особенностями (ЗОУВО).
2. Формализация накопленного экспертами опыта решения задач рассматриваемого класса.
3. Разработка высокоадаптивных интеллектуальных технологий, позволяющих интегрировать экспертные знания в существующие средства численной оптимизации.
Целью работы является повышение эффективности и надежности существующих средств оптимизации сложных динамических систем рассматриваемого класса путем применения методов искусственного интеллекта, в частности методов продукционной логики. Для этого необходимо решить следующие задачи:
создание структур данных и алгоритмов, реализующих расчетные методики эксперта при решении задач рассматриваемого класса;
разработка интеллектуальных программных компонент, осуществляющих принятие решений в ходе управления вычислительным процессом;
адаптация существующих программных средств под современные интеллектуализации;
проверка работоспособности предложенных вычислительных технологий на тестовых, модельных и содержательных задачах.
Методы и средства исследования. При выполнении работы использовались методы теории оптимального управления, элементы теории построения экспертных систем, метод вычислительного эксперимента, методы построения комплексов прикладных программ, методы искусственного интеллекта и инструментальная среда для разработки экспертных систем CLIPS.
Научная новизна:
1. На множестве ЗОУ выделен класс задач с вычислительными особенностями, описаны подходы к их регуляризации и сформулированы количественные критерии эффективности численного решения.
2. Впервые предложено семейство интеллектуальных алгоритмов, формализующих механизм принятия решения экспертом-вычислителем при численном решении задач рассматриваемого класса.
3. Впервые для оценки и повышения эффективности функционирования средств численной оптимизации динамических систем разработан и применен интеллектуальный динамический планировщик (ИДП).
4. Сформирована оригинальная коллекция задач рассматриваемого класса, включающая в себя как известные, так и специально сконструированные тестовые задачи.
Практическая значимость диссертационной работы состоит в разработке и реализации технологий, совершенствующих существующие средства численного анализа сложных систем с использованием современных методов искусственного интеллекта. Результаты диссертации использованы при реализации проектов, поддержанных грантами РФФИ № 00-01-00731-а «Многометодные процедуры оптимального управления», № 02-01-00889-а «Приближенные методы решения вырожденных задач оптимального управления», № 02-07-90343-в «Internet-технология поддержки удаленного пользователя пакета прикладных программ «OPTCON-2» при решении сложных задач оптимального управления», № 05-01-00477-а «Алгоритмы локально-оптимального синтеза управления с использованием нетейлоровских аппроксимаций условий Кротова и уравнения ГамильтонаЯкобиБеллмана», № 05-01-00659-а «Автоматизация интеллектуального обеспечения методов решения задач оптимального управления», № 09-07-00267-а «Вычислительные технологии интеллектуального анализа временных рядов на основе математических методов теории управления», РГНФ № 09-02- «Разработка компьютеризованных методик для исследования социально значимых медико-экологических проблем региона». Практическая значимость работы подтверждена Актами о практическом использовании в ИАиЭ СО РАН и в ИК им. Борескова СО РАН. Результаты диссертационного исследования используются в учебном процессе НГУ (при подготовке студентов по направлению 230100 – «Информатика и вычислительная техника»).
Достоверность полученных результатов. Разработка и реализация интеллектуального динамического планировщика, представленного в диссертации, проведена с использованием признанного инструментария и в соответствии с теорией построения экспертных систем. Достоверность результатов вычислений обусловлена корректным применением математического аппарата и зарекомендовавших себя программных средств для решения ЗОУ. Для всех решенных задач условия оптимальности (линеаризованный принцип максимума Понтрягина) проверены и выполняются. Работоспособность разработанных технологий подтверждена вычислительными экспериментами на пакете тестовых задач.
Апробация работы. Основные результаты диссертации докладывались и обсуждались на российских и международных конференциях и школахсеминарах: XI Байкальская школа-семинар «Методы оптимизации и их приложения» (Иркутск, 1998), 10-я юбилейная международная конференция по вычислительной механике и современным прикладным программным средствам (Переславль-Залесский, 1999), XII Байкальская международная конференция «Методы оптимизации и их приложения» (Иркутск, 2001), Международная конференция «Математика, ее приложения и математическое образование» (Улан-Удэ, 2002), IV конференция молодых ученых «Навигация и управление движением» (Санкт-Петербург, 2002), школа-семинар молодых ученых «Математическое моделирование и информационные технологии»
(ИркутскАнгасолка, 2002), конференция ИДСТУ СО РАН «Ляпуновские чтения» (Иркутск, 2002), Международная конференция «Вычислительные и информационные технологии в науке, технике и образовании» (Алматы, Казахстан, 2004, 2008), Всероссийская конференция «Математика, информатика, управление» (Иркутск, 2004), Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям (Кемерово, 2005), Всероссийская конференция «Информационные и математические технологии в науке, технике и образовании», (Северобайкальск, 2005), Международная конференция «Алгоритмический анализ неустойчивых задач» (Екатеринбург, 2008), XIII Байкальская Всероссийская конференция «Информационные и математические технологии в науке и управлении» (Иркутск, 2008), Международная конференция «Вычислительные и информационные технологии в науке, технике и образовании» (Копаоник, Врнячка Баня, Сербия, Будва, Черногория, 2009, 2011).
Публикации. По теме диссертации опубликовано 16 научных работ, в том числе 3 статьи в рекомендованных ВАК научных журналах, 1 в научном периодическом издании и 12 статей и тезисов в сборниках трудов конференций различного уровня.
Структура работы. Диссертация состоит из введения, четырех глав, заключения и списка литературы, содержащего 103 наименования. Общий объем работы составляет 149 страниц, в тексте содержится 24 рисунка.
Основные защищаемые положения:
1. Структуры данных и алгоритмы их обработки, реализующие расчетные методики эксперта при исследовании задач оптимального управления с вычислительными особенностями.
2. Вычислительная технология, позволяющая решать задачи оптимального управления рассматриваемого класса в автоматизированном режиме.
3. Архитектура и программная реализация интеллектуального динамического планировщика и программных интерфейсных компонент, позволяющих конструктивно преодолевать нештатные ситуации, возникающие при работе алгоритмов оптимизации.
СОДЕРЖАНИЕ РАБОТЫ
Во введении обосновывается актуальность работы, ставятся цели и задачи исследования и приводятся основные положения.
Первая глава посвящена рассмотрению задач оптимального управления с вычислительными особенностями и методов, позволяющих успешно находить их решения. В разделах 1.1 и 1.2 приводится общая постановка задач оптимального управления, содержится обзор существующих теоретических разработок и программных комплексов, освещаются проблемы, возникающие при численном исследовании ЗОУ.
Пусть задан отрезок времени T = [t 0,t1 ], на котором определены векторфункции u (t ) R m, x(t ) R n, t T, задающие управление и фазовое состояние некоторого объекта в момент времени t и удовлетворяющие системе дифференциальных уравнений Вектор-функция x(t ) предполагается кусочно-дифференцируемой, а u (t ) обозначают через D. На множестве D задан целевой функционал I = F ( x(t1 )).
Решение задачи оптимального управления состоит в поиске улучшающей называются оптимальной траекторией и оптимальным управлением соответственно. Все итерационные алгоритмы численного решения ЗОУ предполагают априорное наличие некоторой допустимой пары, состоящей из начального управления u 0 (t ) и соответствующей ему траектории x 0 (t ), являющихся стартовым элементом улучшающей последовательности {x s (t ), u s (t )} D, генерируемой алгоритмами.
особенностями будем понимать ЗОУ, которая:
1. Имеет решение (множество допустимых не пусто).
2. Имеет хотя бы одно управление, при котором в системе (1) возникает одно из условий: а) нарушены условия роста1, гарантирующие существование решения на всем промежутке времени; б) нарушены области определения элементарных математических функций, входящих в правую часть; в) значения переменных выходят за границы возможностей машинного представления чисел с плавающей точкой.
Филлипов А.Ф. Дифференциальные уравнения с разрывной правой частью.
При решении такого типа задач с использованием программных комплексов в улучшающей последовательности {x s (t ), u s (t )} D, генерируемой алгоритмом оптимизации, порождается элемент, использование которого в последующих процедурах вычислительного метода приводит к аварийному завершению работы («АВОСТу»).
Одним из подходов, позволяющих успешно решать ЗОУВО, можно назвать метод продолжения по параметру2. В разд. 1.3 приводится описание нескольких классов постановочных параметров, изменяющих постановку задачи и погружающих ее в семейство аппроксимирующих вспомогательных задач. Например, вместо управляемой системы (1) рассматривается система («pf-параметризация») Здесь p = { pi } векторный параметр, p i (0,1], i = 1, n, n размерность фазового пространства. Очевидно, что при p1 = p2 =... = pn = 1 система (3) полностью идентична исходной. На практике, обычно, рассматривается частный случай построения вектора параметра, когда p1 = p2 =... = pn = p.
Далее, значение параметра p, при котором соответствующая ему задача идентична исходной, будем обозначать p*. Помимо представленного выше вида параметризации в разделе описаны такие методы построения аппроксимирующего семейства, как изменение начальных условий задачи Коши (1), изменение границ областей определения элементарных функций, входящих в правую часть динамической системы, ослабление или усиление ресурса управления путем параметризации ограничений (2), построение составных целевых функционалов специального вида, учитывающих специфику задачи и др. Далее формулируется итерационный метод нахождения оптимального управления в исходной задаче на основе решений серии задач из параметрического семейства. В основе метода лежит экспертная гипотеза о том, что две задачи из параметрического семейства, порождаемые двумя близкими по значению параметрами, имеют также близкие решения. Как правило, путем вычислительного эксперимента в аппроксимирующем семействе удается найти последовательность ЗОУ, решение каждой из которых позволяет строить «хорошее» начальное управление для последующей, а в итоге и для исходной задачи. Информация о возможных способах параметризации задачи и применения метода продолжения по параметру носит экспертный характер, а значит метод не может быть применен пользователем, не имеющим достаточной квалификации.
Во второй главе формализуется ряд расчетных методик эксперта при решении ЗОУВО методом продолжения по параметру. В разделах 2.1 и 2. описаны основные структуры данных: локальные вычислительные схемы и Холодниок М., Клич А., Кубичек М., Марек М. Методы анализа нелинейных динамических моделей.
вычислительные стратегии. Пусть последовательность ЗОУ параметрического семейства порождается значениями параметра p, изменяющимися в пределах отрезка Pi = pi0, piki, i = 0, N 1, внутри каждого из которых два соседних значения параметра pij, pij +1 отличаются на фиксированную величину pi, которую назовем шагом по параметру на данном участке.
локальными вычислительными схемами. Пусть последовательностью значений параметра pij, j = 0, k i этой схемы, обрабатывается алгоритмом «продолжения по параметру» в штатном режиме (без возникновения «АВОСТа»).
Вычислительной стратегией назовем упорядоченное множество, состоящее из N локальных вычислительных схем s = {S 0, S1,..., S N 1 } = {Si }iN 1 на отрезке P. Оно определяет ход всего процесса решения исходной ЗОУ, задавая начальное значение постановочного параметра p = p0 и дальнейший «кусочнопостоянный» шаг его изменения на всем интервале P. Пример вычислительной стратегии представлен на рис. 2.
p0 = p Будем говорить, что вычислительная стратегия успешна, если все составляющие ее локальные схемы успешны.
Далее в разд. 2.3 вводится три критерия сравнения вычислительных стратегий. В разд. 2.4 расчетные методики формализуются в виде многовариантных итерационных алгоритмов «улучшения» с использованием введенных критериев. Алгоритмы имеют структуру «если-то», что позволяет реализовать их в виде правил-продукций. Нахождение первой успешной вычислительной стратегии эквивалентно построению решения исходной ЗОУВО.
соответствующая некоторому значению параметра p с начальным управлением u 0. Выражением оптимального управления u * в задаче Z { p, u 0 }. u 0 начальное управление в исходной задаче. В таких обозначениях ход метода продолжения по параметру в пределах некоторой локальной вычислительной схемы S = ( p 0, p M, p) описывается последовательностью задач Если локальная схема успешна, то Z {S, vS } vS.
Аналогично, ход метода продолжения по параметру, задаваемый s = {Si }iN 1, можно описать последовательностью задач Z {s, u 0 } = {Z {S i, v S i }}i = 0, где vS 0 = u 0, vSi = vS i1. Если вычислительная стратегия s успешна, то vS N 1 оптимальное управление в исходной задаче.
Алгоритмы поиска успешной стратегии разбиты на 3 группы:
1-я группа: Сужение области поиска в пространстве вычислительных стратегий. Алгоритмы данного этапа являются наиболее простыми и всего лишь устанавливают границы возможного варьирования значений параметра и направление обхода их последовательности в зависимости от выбранного способа параметризации исходной задачи. Например, если: pf-параметризация, то: P = [ p 0,1], 0 < p0 < 1, pik < pik +1.
2-я группа: Выбор значения p0 с одновременным генерированием начальной вычислительной стратегии s0 путем выдвижения и последующей проверки через вычислительный эксперимент соответствующих экспертных гипотез.
2.1. Полагаем p0 =0,9. Если Z {0,9, u 0 }, то переходим к п. 2.2, иначе p найдено, в качестве s0 выбирается стратегия (0,9; 1; 0,1) и осуществляется переход на этап ее улучшения.
2.2. Построим итерационную процедуру поиска p0. Обозначим через p0k ) и ( s0k ) соответственно приближение p0 и начальную стратегию s0 на k-й итерации, положив p00) = p * = 1, s00) пусто.
2.3. Пусть проведено k итераций. Последовательно выдвигаются и проверяются s0 = {s0k ), (0,5 p0k ) ; 0,6 p0k ) ; 0,1 p0k ) ), (0,6 p0k ) ; p0k ) ; 0,2 p0k ) ) };
полагая p0 = 0,2 p0k ) и s0 = {s0k ), (0,2 p0k ) ; p0k ) ; 0,2 p0k ) ) };
s0 = {s0, (0,1 p0 ; 0,4 p0 ; 0,1 p0 ), (0,4 p0 ; p0 ; 0,2 p0 ) };
s0k +1) = { s0k ), (0,1 p0k ) ; 0,2 p0k ) ;0,05 p0k ) ), (0,2 p0k ) ;0,4 p0k ) ;0,1 p0k ) ), (0,4 p0k ) ; p0k ) ;0,2 p0k ) ) } и пункт 2.3 повторяется (осуществляется переход на следующую итерацию).
3-я группа: Итерационное улучшение полученной на предыдущем этапе вычислительной стратегии s0. Основная задача 3-й группы алгоритмов исключить из начальной вычислительной стратегии неуспешные локальные вычислительные схемы и заменить их найденными успешными. Обозначим через s( k ) = {Si( k ) }i=k0 вычислительную стратегию на k-й итерации, состоящую из N k локальных вычислительных схем Si(k ) с шагом pi(k ). Обозначим также через m(pi(k ) ) мантиссу шага pi(k ). Приведем общую схему алгоритмов 3-й группы. Пусть проведено k итераций.
3.1. Если Z {s( k ), u 0 } u *, то s(k ) успешна и u * найдено, 3.2. Последовательно выдвигаются и проверяются 2 или 3 гипотезы об эффективном уменьшении шагов по параметру в локальных схемах S (j k ), S (j +1 :
p j = ap (jk ), p j +1 = bp (jk 1, где а и b выбираются из таблицы:
m(p (k ) ) 2 a={0.5; 0.25; 0.1} a={0.5; 0.25; 0.1} a={0.5; 0.25; 0.1} 3.3.
s( k +1) = {S 0 k ),..., S (j 1, S, S j +1,..., S Nkk)1} и процесс переходит на следующую если a Z {S j, vS ( k ) }, то 1) локальная вычислительная схема S (k ) разбивается на M одношаговых схем {S ij }iM01 с фиксированным p (k ), где s( k +1) = {S 0 k ),..., S (j 1, S 0, S 1,..., S M 1, S j +1,..., S Nkk)1} и процесс переходит на следующую итерацию с п. 3.1.
«