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

Тип работы:
Реферат
Предмет:
Физико-математические науки


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 519. 24:519. 711, 004. 023
ПАРАЛЛЕЛЬНЫЕ ГИБРИДНЫЕ АЛГОРИТМЫ ДЛЯ ЗАДАЧИ ПАРАМЕТРИЧЕСКОЙ ИДЕНТИФИКАЦИИ В СТОХАСТИЧЕСКИХ ЛИНЕЙНЫХ СИСТЕМАХ
© 2011
А. В. Цыганов, кандидат физико-математических наук, доцент, доцент кафедры
«Математический анализ»
О. И. Булычов, ведущий программист компании «Gladiators Software»
Ульяновский государственный педагогический университет имени И. Н. Ульянова, Ульяновск (Россия) Ю. В. Цыганова, кандидат физико-математических наук, доцент, доцент кафедры
«Информационные технологии»
Ульяновский государственный университет, Ульяновск (Россия)
Ключевые слова: параллельные гибридные алгоритмы- параметрическая идентификация- фильтр Калмана- градиентные методы оптимизации.
Аннотация: В работе рассматривается задача параметрической идентификации в стохастических линейных системах. Для оценивания неизвестных параметров системы используется метод максимального правдоподобия. Поиск условного минимума функционала качества выполняется с помощью гибридных алгоритмов, основанных на сочетании параллельных метаэвристических алгоритмов библиотеки HeO (Heuristic Optimization) и точных методов минимизации ньютоновского типа. Приводятся результаты численных экспериментов, подтверждающие эффективность предложенных алгоритмов.
ВВЕДЕНИЕ
Задача параметрической идентификации является одной из важнейших задач, возникающих в различных областях науки и техники, таких как компьютерные сети, архитектура ЭВМ, базы данных, биология и медицина, метеорология и др. (см., например, [1]). К настоящему времени разработаны теоретические основы решения таких задач, а также накоплен опыт по практической реализации методов и алгоритмов параметрической идентификации.
Однако бурное развитие современных программных средств и инструментов, в т. ч. параллельного программирования, стимулирует к разработке новых эффективных алгоритмов параметрической идентификации для систем реального времени. Одним из важных требований для идентификации в системах реального времени является высокая скорость процесса идентификации без потерь в точности найденных оценок. Следовательно, актуальной задачей является разработка эффективных методов параметрической идентификации, которые при практической реализации имели бы высокое качество идентификации.
В данной работе рассматривается решение задачи параметрической идентификации по наблюдаемым данным в стохастических линейных системах, описываемых моделями в пространстве состояний. Для оценивания неизвестных параметров системы используется метод максимального правдоподобия. При этом поиск условного минимума функционала качества выполняется с помощью гибридных алгоритмов, основанных на сочетании параллельных метаэвристических алгоритмов библиотеки НеО [2] и точных методов минимизации ньютоновского типа. Задача параллельных метаэври-стических алгоритмов заключается в отыскании начального приближения для оценки неизвестных параметров, а задача точного численного метода — в уточнении найденного реше-
ния алгоритмами первой группы. Эффективная программная реализация подразумевает применение методов и средств параллельного программирования для повышения вычислительных характеристик гибридных алгоритмов.
Работоспособность предложенных алгоритмов подтверждается результатами вычислительных экспериментов.
ПОСТАНОВКА ЗАДАЧИ
Рассмотрим источник данных в виде линейной стохастической дискретной системы
^ =Я (0)хг+У, (2)
с вектором состояния хІ є ЭТ& quot- и вектором измерения zl є ЭТ& quot-, где {м^м^,…} и {V 1, г2,…} суть-мерная и т-мерная независимые последовательности независимых и одинаково распределенных случайных векторов с нулевыми математическими ожиданиями и ковариациями 0(0) и R (@) соответственно. Эти последовательности не зависят от случайного начального состояния системы х0 є Nх0 ((c)), Р0 ((c))). Предположим, что описывающие систему (1), (2) матрицы зависят от неизвестного параметра (c)єRp, причем элементы указанных матриц являются дифференцируемыми по 0. функциями, где
0. — і-й элемент вектора 0, і=1,…, р.
Предположим, что V (c)є В (& amp-): R ((c)) & gt- 0, Р0 & gt- 0 и Г ((c)) & lt-2(®) Г (0) & gt- 0, Ф (0) — устойчивая матрица, система (1), (2) стабилизируемая, полностью наблюдаемая и полностью управляемая [3].
Важной задачей, возникающей часто в различных областях науки и техники, является разработка эффективных алгоритмов параметрической идентификации для математической модели (1), (2) с учётом высказанных выше предположений. Данная задача заключается в нахождении оценки
неизвестного вектора параметров (c)е^р по данным наблюдений 21 =[г1 12 1 • • •12м], где N — размер выборки, в соответствии с выбранным критерием качества идентификации, который определяется некоторым функционалом J ((c) — 21).
При заданном функционале качества J ((c) — 21) нахождение оценок 0. (-'-=1,…, р) предполагает решение задачи нелинейного программирования с ограничениями:
0″
, = argmin. /(0- Z'-v)
(c)е?& gt-(0)
э (c)
ал,
д0
frB-xdv, яд ?-Л r г яа
дЛв.
¦к+^в7'-дв'-
(4)
Наиболее часто для систем вида (1), (2) оценивание параметров проводят по методу максимального правдоподобия и наименьших квадратов (см. [3, 4] и др.). В этом случае для метода максимума правдоподобия запишем отрицательную логарифмическую функцию правдоподобия [5]:
Jmlf (® — ZN) =1 t {m 1"(2ж)+ln (det B,)+vT b-}
2 t=1 (3)
где вектор невязки измерений vt и его ковариационная матрица Bt при заданных значениях параметра 0 вычисляются по известным уравнениям фильтра Калмана [6]:
Для поиска условного минимума (3), как правило, используются градиентные методы оптимизации или методы ньютоновского типа. Градиентные методы (или методы первого порядка) требуют вычисления целевой функции и её градиента. Методы ньютоновского типа (или методы второго порядка), кроме целевой функции и градиента, дополнительно требуют вычисления матрицы вторых производных. К этой группе относится метод Гаусса-Ньютона, который будем использовать в работе в качестве точного метода. При использовании данного метода для поиска минимума критерия (3) итерационная формула для вычисления оценки параметра 0 имеет вид:
где вк — длина шага вдоль выбранного направления, grad JjMLp- градиент функционала (3), M — информационная матрица Фишера, которая задаётся выражением [5]:
M (0(-Z,") = е/& quot-" '-Г|
а в качестве оценки информационной матрицы Фишера будем использовать выражение:
+ 1"г 2
в: 8лв- ' дв-
дв:
(5)
+ 4tr| Д
дв,
tr В,
де,
Подробно вычислительные аспекты таких методов рассмотрены в [4], [5]. Следуя работе [5], градиента (3) будем вычислять с помощью выражения:
где /=1,…, р, 7=1,… р, 1 г (А) — след матрицы А, (Н*-2*) — /,
7-ый элемент матрицы М?(Н*-), величины V{ и В{ вычисля-
ются по выражениям фильтра Калмана.
тт дк/™ 7
Для вычисления величин /Й0 и
30 и /30 необходимо использовать так называемые уравнения чувствительности фильтра Калмана, которые получаются из уравнений дискретного фильтра Калмана дифференцированием по каждому неизвестному параметру 0. Различные методы построения уравнений чувствительности фильтра Калмана рассмотрены в работах [5, 7−9] и др. Заметим, что практическая реализация выражений (4) и (5) является наиболее трудоёмкой и требует для систем большой размерности значительных вычислительных ресурсов при применении метода Гаусса-Ньютона.
Метод Гаусса-Ньютона является точным методом, то есть сходится за конечное число шагов к оптимальному значению при соблюдении известных условий теорем сходимости [10]. Однако хорошо известно, что на сходимость численных методов влияют различные факторы, в частности, хороший выбор начального приближения. Если начальное приближение выбрано неверно, то алгоритм нахождения оценок оптимальных параметров может расходиться, что означает невозможность идентификации. Одним из важных требований для идентификации в системах реального времени является высокая скорость процесса идентификации без потерь в точности найденных оценок. Следовательно, актуальной задачей является разработка эффективных методов параметрической иденти-
Iterations
Рис. 1. График сходимости оценок а) параметров и б) невязки для алгоритма GA
2. 5
-е1
¦ Н2 '- ---0з

1 ь

'-¦

/
400 600
Iterations
Рис. 2. График сходимости оценок а) параметров и б) невязки для алго-ритма GA^•GN
фикации, которые при практической реализации имели бы высокое качество идентификации (то есть реальную скорость сходимости и точность оценок неизвестных параметров).
Улучшить качество процесса идентификации представляется возможным за счёт поиска начального приближения метаэвристическими алгоритмами оптимизации, которым для отыскания условного минимума совсем необязательно вычислять значение градиента, следовательно, реализация таких методов будет существенно проще, чем точных численных методов первого и второго порядка. Такими методами являются, например, различные модификации генетического алгоритма, метод имитации отжига и т. п. Идея применения метаэвристических алгоритмов для решения задачи параметрической идентификации не является новой. В частности, применение генетического алгоритма для параметрической идентификации ARMAX-модели рассмотрено в [11], а метода
Таблица 1. Установившиеся значения параметров и
невязки
GA GA^GN SA SA^GN
01 0. 2865 0. 3039 0. 2895 0. 3002
02 0. 6884 0. 6668 0. 6797 0. 6746
03 1. 0269 1. 0753 1. 0644 1. 0219
r 0. 2234 0. 1724 0. 1214 0. 0733
имитации отжига для параметрической идентификации линейных стохастических систем, представленных моделями в пространстве состояний, в работе [12]. Однако, описанные там алгоритмы не являются параллельными.
В связи с этим, целью данной работы является разработка и эффективная программная реализация параллельных гибридных алгоритмов параметрической идентификации в линейных стохастических системах по наблюдаемым данным. Данные алгоритмы являются гибридами метаэвристических алгоритмов, задача которых заключается в отыскании начального приближения для оценки неизвестных параметров, и численного метода Гаусса-Ньютона, который при отыскании минимума критерия (3) стартует с найденного начального приближения и уточняет найденное методами первой группы решение. Эффективная программная реализация подразумевает применение методов и средств параллельного программирования для повышения вычислительных характеристик гибридных алгоритмов.
ПРОГРАММНАЯ РЕАЛИЗАЦИЯ АЛГОРИТМОВ
Программная реализация алгоритмов была выполнена в виде проекта ISLSP (Identification of Stochastic Linear System Parameters) на языке C++ с использование библиотеки метаэвристических алгоритмов HeO.
Библиотека HeO (Heuristic Optimization) является про-
iterations
Рис. 3. График сходимости оценок а) параметров и б) невязки для алгоритма SA
2. 5
1. 5
0. 5
-0. 5
A '- ib 9, — «2 -_-e3 ¦
М'-,, 1″ Vі 4
г У y'-iH (щ1 '-І 1 * J '-Vi v.
Ы i
пИ. v/*» u ГТ & quot-V'-I- * V,*ivVi*v-'- //•! _
ч 1 ч rf V 1 Д1 1У yfyh

f 1
500
1000 1500 2000
Iterations
2500
3000
Iterations
Рис. 4. График сходимости оценок а) параметров и б) невязки для алгоритма SA^GN
ектом с открытым исходным кодом и распространяется на основе лицензии MIT. Цель проекта — обеспечить исследователей современными и простыми в использовании средствами для решения широкого круга оптимизационных задач. Официальная страница проекта располагается по адресу: http: //www. code. google. eom/p/heo. Библиотека и демонстрационные проекты доступны через SVN или из раздела Downloads.
В качестве основной модели параллельных вычислений в библиотеке HeO используется мультистартовая модель. В этой модели алгоритм работает в несколько потоков, независимо решающих задачу с возможностью периодической кооперации между потоками. В библиотеке реализованы два режима кооперации: синхронный и асинхронный.
В настоящее время в библиотеке реализованы следующие алгоритмы (солверы): генетический алгоритм (GA -Genetic Algorithm), метод имитации отжига (SA — Simulated Annealing), метод ветвей и границ (BnB — Branch and Bound) и заготовка для пользовательских методов (User). Одним из достоинств библиотеки HeO является возможность простого получения гибридных алгоритмов на основе существующих. Пользователям библиотеки доступны два типа гибридов: «сильные» (strong) и «слабые» (weak). При сильной гибридизации один из алгоритмов рассматривается как оператор другого алгоритма, например, метод имитации отжига, может рассматриваться как один из операторов генетического алгоритма. Набор и порядок выполнения операторов основного алгоритма задаётся пользователем в конфигурационном файле без изменения исходного кода программы (более подробно этот вопрос рассмотрен в [13]. При слабой гибридизации результаты работы одного алгоритма служат начальными данными для другого алгоритма (обмен решениями при этом осуществляется через специальный буфер — пул решений).
В рамках проекта ISLSP были реализованы все необходимые проблемно-зависимые классы алгоритмов GA и SA, а также на основе пользовательского солвера User запрограммирован метод Гаусса-Ньютона (GN). В качестве функции приспособленности для GA и функции стоимости для SA использовался функционал (3). Для выполнения матричных операций использовалась библиотека Armadillo [14], синтаксис которой очень похож на синтаксис языков Matlab и Octave, что позволяет быстро переносить код, разработанный
для Matlab и Octave в программы на языке C++. ПРАКТИЧЕСКИЙ ПРИМЕР
Для демонстрации работы алгоритма рассмотрим пример модели линейной стохастической системы второго порядка без управления:
(6)
(7)
0] ^ ^
где Q=63, R=0. 1, x0 є N (x0,12) (I — единичная матрица размера их"). Необходимо получить оптимальные оценки параметра ® = (Д, 9V въ) Т, входящие в переходную матрицу состояния Ф и в ковариационную матрицу Q. Реализации наблюдений получались компьютерным моделированием при истинных значениях параметров 6^=030, 62*=0. 68, в*=1 и N=100.
Задача решалась в 4 потока на системе с общей памятью следующей конфигурации: процессор — Intel Core 2 Quad Q6600 @ 2.4 ГГц- ОЗУ — 4 Гб- операционная система — MS Windows XP Professional SP 3.
Методика численных экспериментов заключалась в следующем. Для 10 различных реализаций N наблюдений выполнялась идентификация параметров модели (6), (7) при помощи алгоритмов GA, SA и их слабых гибридов с алгоритмом Гаусса-Ньютона (GA^GN, SA^GN). В ходе каждого эксперимента сохранялась история поиска решения. По окончании экспериментов результаты усреднялись и по ним строились графики сходимости полученных оценок и невязки (для усреднения выбирались результаты лучшего из потоков).
На рис. 1 и 2 представлены усреднённые графики сходимости оценок параметров и графики сходимости невязки оценок вектора параметров для алгоритмов GA и GA^GN, а на рис. 3 и 4 представлены аналогичные графики для алгоритмов SA и SA^GN. Невязка вычислялась для каждой итерации к алгоритма по формуле r=||(c)k-(c)k*||.
В таблице 1 приведены установившиеся значения параметров и невязки для каждого из четырёх алгоритмов.
Результаты экспериментов позволяют сделать вывод о том, что для решения задачи параметрической идентификации в стохастических линейных системах могут успешно
применяться параллельные гибридные алгоритмы.
ЗАКЛЮЧЕНИЕ
В работе рассмотрена программная реализация параллельных гибридных алгоритмов параметрической идентификации в линейных стохастических системах по наблюдаемым данным. Разработанные алгоритмы являются гибридами ме-таэвристических алгоритмов, задача которых заключается в отыскании начального приближения для оценки неизвестных параметров, и численного метода Гаусса-Ньютона, который при отыскании минимума критерия идентификации стартует с найденного начального приближения и уточняет найденное решение. Разработанные алгоритмы могут применяться для идентификации параметров моделей систем реального времени, поскольку обладают рядом преимуществ:
1) использование параллелизма метаэвристических алгоритмов позволяет расширить пространство поиска оптимального решения и получать хорошее начальное приближение для численных методов-
2) точность найденного решения гарантируется применением численного метода второго порядка на заключительном этапе поиска оптимального решения.
В ходе дальнейших исследований планируется реализация параллельных гибридных алгоритмов с альтернативными функциями приспособленности и стоимости и другими численными методами оптимизации.
СПИСОК ЛИТЕРАТУРЫ
1. Дорф Р. Современные системы управления /
Р. Дорф, П. Бишоп. — М.: Лаборатория базовых знаний, 2002.
— 832 с.
2. Цыганов А. В., Булычов О. И. HeO: библиотека метаэвристик для задач дискретной оптимизации // Программные продукты и системы. 2009. № 4. с. 148−151.
3. Mosca E. Optimal, predictive and adaptive control.
Prentice-Hall, Inc., 1995. 478 p.
4. Astrom K. J. Maximum Likelihood and Prediction Error Methods // Automatica. 1980. Vol. 16. P. 551−574.
PARALLEL HYBRID ALGORITHMS FOR THE PROBLEM OF PARAMETER IDENTIFICATION IN STOCHASTIC LINEAR SYSTEMS
© 2011
A.V Tsyganov, candidate of physical and mathematical sciences, associate professor of the chair
«Mathematical analysis»
O.I. Bulychov, lead programmer company «Gladiators Software»
Ulyanovsk State Pedagogical University Named After I. N. Ulyanov, Ulyanovsk (Russia)
Yu.V. Tsyganova, candidate of physical and mathematical sciences, associate professor of the chair
«Information technology»
Ulyanovsk State University, Ulyanovsk (Russia)
Keywords: parallel hybrid algorithms- parameter identification- Kalman filter- gradient optimization methods.
Annotation: In the present paper the problem of parameter identification in stochastic linear systems is considered. The maximum likelihood method is used for estimation of the unknown parameters. The search for performance functional minimum is done with the usage of hybrid algorithms based on the combination of the metaheuristic algorithms of the HeO (Heuristic Optimization) library and the exact methods of the Newton type. Numerical results which demonstrate the efficiency of the proposed algorithms are provided.
5. Gupta N. K., Mehra R. K. Computational Aspects of Maximum Likelihood Estimation and Reduction in Sensitivity Function Calculations // IEEE Transactions on Automatic Control. 1974. V. AC-19. No. 6. P. 774−783.
6. Grewal M. S., Andrews A. P. Kalman Filtering: Theory and Practice Using MATLAB, Second Edition / John Wiley & amp- Sons, Inc., 2001. 401 p.
7. Денисов В. И., Чубич В. М., Рябых О. С. Новое обобщённое выражение для информационной матрицы Фишера в задаче активной параметрической идентификации стохастических линейных дискретных систем // Науч. вестник НГТУ 2001. № 2(11), С. 29−42.
8. Hill S. D. Reduced Gradient Computation in Prediction Error Identification // IEEE Transactions on Automatic Control. 1985. V. AC-30. No. 8. P. 776−778.
9. Bierman G. J., Belzer M. R., Vandercraft J. S., Porter D. W. Maximum Likelihood Estimation Using Square Root Information Filters // IEEE Transactions on Automatic Control. 1990. V. 35. No. 12. P. 1293−1299.
10. Васильев В. П. Численные методы решения экстремальных задач / В. П. Васильев. — М.: Мир, 1982. — 372 с.
11. Theofilatos K., Beligiannis G., Likothanassis S. Combining evolutionary and stochastic gradient techniques for system identification // Journal of Computational and Applied Mathematics. 2009. V. 227. P. 147−160.
12. Цыганова Ю. В., Цыганов А. В. Имитационная нормализация в задаче идентификации параметров стохастической линейной системы // Стохастическая оптимизация в информатике / Под. ред. О. Н. Граничина. Т. 6 (Вып. 1). Изд-во Санкт-Петербургского университета. 2010. С. 147−159.
13. Булычов О. И. Использование шаблонного метапрограммирования при реализации параллельных гибридных метаэвристических алгоритмов оптимизации // Вестник УГА-ТУ, 2010 г., Т. 14, № 4(39).
14. Sanderson C. Armadillo: An Open Source C++ Linear Algebra Library for Fast Prototyping and Computationally Intensive Experiments // NICTA Technical Report, 2010.

ПоказатьСвернуть
Заполнить форму текущей работой