Параллельное математическое обеспечение идентификации параметрически связанных моделей сложных систем тема диссертации и автореферата по ВАК РФ 05.13.18, кандидат технических наук Иванов, Сергей Владимирович

• Иванов, Сергей Владимирович
• кандидат технических наук
• 2008

Оглавление диссертации кандидат технических наук Иванов, Сергей Владимирович

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 1. ОСОБЕННОСТИ ИДЕНТИФИКАЦИИ МОДЕЛЕЙ СЛОЖНЫХ СИСТЕМ.

1.1. Постановка задачи идентификации.

1.1.1. Общие аспекты задачи.

1.1.2. Типы реализации.

1.1.3. Построение модели.

1.1.4. Функциональная схема идентификации.

1.2. Сложная система: понятие, свойства, методы и цели исследований.

1.2.1. Понятие сложной системы.

1.2.2. Свойства сложных систем.

1.2.3. Принципы построения.

1.2.4. Методы исследования.

1.2.5. Проблемы моделирования.

1.2.6. Особенности идентификации.

1.3. Алгоритмы идентификации.

1.3.1. Обзор основных методов.

1.3.2. Поисковые методы оптимизации.

1.3.3. Особенности задач многомерной оптимизации.

1.3.4. Алгоритмы случайного поиска.

1.3.5. Комбинированные эвристические процедуры.

1.3.6. Методы глобальной оптимизации.

1.3.7. Использование технологий высокопроизводительных вычислений в оптимизационных алгоритмах.

Выводы к главе 1.

2. ИДЕНТИФИКАЦИЯ ПАРАМЕТРОВ МОДЕЛИ РАСЧЕТА ПОЛЕЙ ПРИВОДНОГО ВЕТРА.

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

2.1.1. Формализация модели в рамках концепции сложных систем.

2.1.2. Подготовка исходных данных.

2.1.3. Подготовка исходных данных.

2.2. Модель расчета полей приводного ветра по полям давления.

2.2.1. Основные подходы к уточнению полей приводного ветра.

2.2.2. Описание физической модели.

2.2.3. Схема идентификации параметров.

2.2.4. Результаты экспериментальных расчетов.

2.2. параллельный алгоритм.

2.3.1. Декомпозиция исходных данных.

2.3.2. Результаты экспериментальных исследований параллельной производительности.

2.3.3. Теоретическая модель производительности. выводы К главе 2.

3. ИДЕНТИФИКАЦИЯ ПАРАМЕТРОВ МОДЕЛИ КЛИМАТИЧЕСКИХ СПЕКТРОВ.

3.1. Концепция вероятностного описания спектрально-волнового климата.

3.1.1. Основные понятия.

3.1.2. Функция спектральной плотности волнения на промежутке квазистационарности

3.1.3. Основные подходы к идентификации параметров спектра ветрового волнения.

3.2. Идентификация параметров.

3.2.1. Идентификация параметров частотно-направленных спектров методом случайного поиска.

3.2.2. Оценка производительности и критерии оптимальности.

3.2.3. Расчет климатических спектров.

3.3. Параллельный алгоритм.

3.3.1. Реализация параллельного алгоритма для кластерных систем.

3.3.2. Реализация параллельного алгоритма для Опс1-систем.

Выводы к главе 3.

4. ИДЕНТИФИКАЦИЯ ПАРАМЕТРОВ ЭПИДЕМИЛОГИЧЕСКОЙ МОДЕЛИ ВИЧ.

4.1. Описание модели.

4.1.1. Применение аппарата комтексных сетей для описания эпидемиологических процессов.

4.1.2. Формальная постановка задачи.

4.1.3. Особенности моделирования динамики ВИЧ.

4.1.4. Структура эпидемиологической контактной сети.

4.1.5. Моделирование динамики инфицированных узлов.

4.1.6. Учет демографического эффекта.

4.1.7. Процедура прямого моделирования методом Монте-Карло.

4.2. Идентификация параметров модели.

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

4.2.2. Аппроксимация решения при помощи системы обыкновенных дифференциальных уравнений.

4.2.3. Результаты моделирования.

4.3. Параллельный алгоритм генерации комплексной сети.

4.3.1. Вероятностная модель комплексной сети.

4.3.2. Способ генерации комплексной сети по заданному закону распределения степеней вершин.

4.3.3. Базовый параллельный алгоритм.

4.3.4. Отображение алгоритма на вычислительную архитектуру.

Выводы к главе 4.

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

Развитие методов и технологий компьютерного моделирования стимулирует интерес исследователей к изучению так называемых сложных систем (complex systems). Под сложной системой подразумевается система, которая (а) состоит из большого числа компонентов; (б) допускает «дальние» связи между компонентами; (в) обладает многомасштабной (в том числе пространственно-временной) изменчивостью. Перечисленные свойства порождают ряд специфических проблем компьютерной реализации моделей сложных систем. Так, большое число компонентов отражается на ресурсоемкости вычислительных процедур и повышенных требованиях к объемам оперативной памяти для храпения структур данных. Применение параллельных вычислений требует учета дальних связей в системе и предварительного решения проблемы связности, затрудняющей или даже приводящей к невозможности распараллеливания формальными методами. Дополнительно, многомасштабность сложных систем требует использования для их описания параметрически связанных моделей, описывающих иерархию смежных диапазонов изменчивости.

В силу условности выделения границ диапазонов изменчивости, процедуры связывания или замыкания таких моделей традиционно используют эмпирические закономерности и коэффициенты, значения которых определяются посредством идентификации. Задача идентификации моделей заключается в определении их структуры и параметров по результатам наблюдений над входными и выходными переменными реальной системы, и решается методами оптимизации. Основные результаты в области идентификации систем общего вида заложены работами Я.З. Цыпкина, P. Eykhoff, L. Ljung, D. Graupe и др.

Применительно к сложным многомасштабным системам проблема идентификации усложняется фрагментарностью наблюдений, обычно относящихся только к одному из диапазонов изменчивости, а также существенной ресурсоемкостью вычислительной процедуры. Потому практическая реализация задачи идентификации сложных систем, по-видимому, затруднительна без использования параллельных методов оптимизации. В этой области существенный задел сформирован работами Р.Г. Стронгина, В.П. Гергеля, А.Б. Барского, Y. Censor, G. Talbi, P.M. Pardalos, H. Adeli и др. Однако, применительно к данной области, распараллеливание самого алгоритма оптимизации, без учета свойств сложной системы и характерных особенностей связей между описывающими ее моделями, далеко не всегда эффективно. Таким образом, это требует разработки специализированного информационного, алгоритмического и программного обеспечения, что и определяет актуальность темы диссертации.

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

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

Задачи исследования. Достижение поставленных целей подразумевает решение следующих задач:

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

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

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

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

Научная новизна результатов работы состоит в том, что:

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

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

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

Практическую ценность работы составляют:

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

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

• Справочные гидрометеорологические данные — характеристики климатических спектров для Азовского, Балтийского, Черного, Средиземного и Северного морей.

На защиту выносятся следующие положения:

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

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

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

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

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

1 По данным США, с середины 1970х гг. до наших дней. физической модели расчета полей приводного ветра как элемента сложной системы «океан-атмосфера», предлагается схема идентификации параметров модели и разрабатывается параллельный вычислительный алгоритм.

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

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

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

Заключение диссертации по теме «Математическое моделирование, численные методы и комплексы программ», Иванов, Сергей Владимирович

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

Заключение

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

1. Zadeh L.A., From circuit theory to system theory // Proc. 1.E, 50, 856-865, 1962

2. Ljung L.: System Identification — Theory For the User, 2nd ed // PTR Prentice Hall, Upper Saddle River, N.J., 1999

3. Jer-Nan Juang: Applied System Identification II Prentice Hall, Upper Saddle River, N J., 1994

4. Oliver N.: Nonlinear System Identification II Springer, 2001

5. Daniel G.: Identification of Systems, II Van Nostrand Reinhold, New York, 2nd ed., Krieger Publ. Co., Malabar, FL, 1976

6. Цыпкин ЯЗ., Информационная теория идентификации И М. Наука Изд. фирма "Физ.-мат. лит.", 1995

7. Эйкхофф П., Основы идентификации систем управления // М.:Мир, 1975

8. Venkatesh S., Dahleh М.А. System Identification of Complex Systems: Problem Formulation and Results // Proceedings of the 36th Conference on Decision and Control. San Diego,С A., December 1997

9. Katayama Т., Subspace Methods for System Identification // Springer, 2005

10. Robbins H., Monro S., A stochastic Approximation MethodII Ann. Math. Statist., 22, 400407, 1951

11. Kiefer J., Wolfowitz J., Stochastic Approximation of the Maximum of a regression function И Ann. Math. Statist., 23, 462-466,1952

12. Реклейтис Г.Рейвиндран А., Рэгсдел К., Оптимизация в технике: В 2 кн. Кн. 1 // М.: Мир, 1986

13. Luus R., Jaakola T.H.I. Optimization by direct search and systematic reduction of the size of search region II AlChe J., 19, 760-766, 1973

14. Schummer M.A., Steiglitz K., Adaptive step size random search II IEEE Trans., AC-13, 270276, 1968

15. Kirkpatrick S., Gelatt C. D., Vecchi M. P. Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983

16. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. // М.: Мир, 1985

17. Dixon L. С. W., Nonlinear Optimization II English Univ. Press, London, 1972

18. Powell MJ.D, A survey of numerical methods for unconstrained optimization II SIAM Review, 12, 1970

19. Wilde D.J, Beightler C.S., Foundation of optimization// Prentice-Hall, Englewood Cliffs, N.J, 1967

20. Censor Y., Zenios S.A., Parallel Optimization: Theory, Algorithms, and Applications, Oxford University Press 11 New York, 1997

21. Talbi E., Parallel Combinatorial Optimization (Wiley Series on Parallel and Distributed Computing) И Wiley-Interscience, 2006

22. Strongin R.G., Global Optimization with Non-Convex Constraints Sequential and Parallel Algorithms (Nonconvex Optimization and its Applications Volume 45) И Springer; 1 edition, October 31, 2000

23. Pardalos P.M., Nonlinear Assignment Problems: Algorithms and Applications (Combinatorial Optimization) II Springer; 1 edition, 2000

24. Adeli H., Sarma K.C., Cost Optimization of Structures: Fuzzy Logic, Genetic Algorithms, and Parallel Computing II Wiley, 2006

25. Ingber L., Simulated annealing: Practice versus theory II Mathematical Computer Modelling, 18, pp. 29-57, 1993

26. Тарасенко Г.С. Исследование релаксационных алгоритмов случайного поиска общего вида II Пробл. случайного поиска (Рига), 1978, вып. 7, с. 67-96

27. Gergel V.P., Sergeyev Ya.D. Sequential and parallel global optimization algorithms using derivatives II Computers & Mathematics with Applications, 1999, 37(4/5), 163-180,

28. Gergel V.P. A Global Optimization Algorithm for Multivariate Functions with Lipschitzian First Derivatives II Journal of Global Optimization 1997, 10, pp.257-281

29. Стронгин Р.Г., Гергель В.П. АБСОЛЮТ. Программная система для исследований и изучения методов глобальной оптимизации. Учебное пособие. И Нижний Новгород: Изд-во Нижегородского университета, 1998. 141 с.

30. Box M.J., A new method of constrained optimization and comparison with other methods II Computer J., 8, 42-52, 1965

31. Boukhanovsky A.V., Ivanov S.V. Stochastic simulation of inhomogeneous metocean fields. Part III: High-performance parallel algorithms // Lect. Notes in Comput. Sciences, Springer. 2003. - v. 2658. - pp. 234-244.

32. Растригин JI.А., Адаптация сложных систем II Рига: Зинатне, 1981

33. BoccaraN., Modeling complex systems II Springer, 2004

34. Bar-Yam Y., Dynamics of Complex Systems // Westview Press, 864 pp., 1997

35. Foster I., Designing and Building Parallel Programs II Addison-Wesley, 1995

36. Ilachinski A., Cellular Automata: A Discrete Universe И World Scientific Publishing Co. Pte. Ltd., 2001

37. Bak P., How nature works: the science of self-organized criticality II Springer-Verlag New York, Inc., 19963839,40,41.