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

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

ии^45733Э

Иванов Сергей Владимирович

ПАРАЛЛЕЛЬНОЕ МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ИДЕНТИФИКАЦИИ ПАРАМЕТРИЧЕСКИ СВЯЗАННЫХ МОДЕЛЕЙ СЛОЖНЫХ СИСТЕМ

Специальность 05.13.18 - Математическое моделирование, численные методы и комплексы программ

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

1 2 ДЕН 2003

Санкт-Петербург - 2008

003457339

Работа выполнена в Санкт-Петербургском государственном университете информационных технологий, механики и оптики (СПбГУ ИТМО).

Защита состоится 24 декабря 2008 г. в 14 часов на заседании диссертационного совета Д212.227.06 в Санкт-Петербургском государственном университете информационных технологий, механики и оптики по адресу: 197101, г. Санкт-Петербург, Кронверкский пр., д. 49.

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

Автореферат разослан 24 ноября 2008 г.

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

доктор технических наук Бухановский А.В.

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

Гергель В.П.

доктор технических наук, доцент Бобцов А.А.

Ведущая организация:

Московский государственный институт электроники и математики (МИЭМ)

Ученый секретарь диссертационного совета, доктор технических наук, профессор

Тарлыков В.А.

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

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

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

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

' Примерами сложных систем являются: мировая экосистема, звездная галактика, система государственных органов, нервная система человека, крупный технологический комплекс.

2 Boceara N., Modeling complex systems, Springer, 2004.

3 Когда каждый компонент системы потенциально может взаимодействовать с каждым.

4 Например, для гидрометеорологических сложных систем: мелкомасштабный, синоптический, сезонный, межгодовой, межвековой

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

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

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

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

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

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

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

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

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

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

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

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

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

6 ВИЧ - вирус иммунодефицита человека

• На основе решения задач идентификации получены новые знания в предметных областях, а именно:

1. информация о климатических характеристиках спектральной структуры морского волнения,

2. оценки характера эволюции эпидемии ВИЧ7 с детализацией по группам риска.

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

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

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

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

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

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

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

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

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

Внедрение результатов работы. Результаты работы нашли свое применение при выполнении проектов направления 1.4 «Генерация знаний» ФЦП «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы»: «Высокопроизводительный программный комплекс моделирования и прогноза экстремальных гидрометеорологических явлений и расчета воздействий на морские объекты и сооружения» (НИР 2007-4-1.4-00-06-108) и «Разработка инструментальной оболочки проектирования высокопроизводительных приложений для Грид-архитектур в целях создания прикладных сервисов

7 По данным США, с середины 1970х гт. до наших дней.

компьютерного моделирования и обработки данных» (НИР 2007-4-1.4-20-01025), европроекта б-ой рамочной программы V1ROLAB (EU project, IST-027446). Разработанный высокопроизводительный программный комплекс опробован и внедрен в деятельность ГУ «Гидрометцентр России». В процессе работы получено два свидетельства о государственной регистрации программ для ЭВМ: «Ядро программного комплекса имитационно! о моделирования экстремальных гидрометеорологических явлений «ME2SIM» (свидетельство №2008614624), «Программная система оценивания климатических спектров морского волнения «ME2SPECTRA» (свидетельство №2008614609).

Апробация работы. Изложенные в диссертации результаты обсуждались на 13 международных и российских научных конференциях, семинарах и совещаниях, включая «Управление и информационные технологии» (2003 г., Санкт-Петербург), «Высокопроизводительные параллельные вычисления на кластерных системах» (2005 г., Нижний Новгород), ежегодные Всероссийские научные конференции «Научный сервис в сети Интернет» (2007 и 2008 гг., Новороссийск), ежегодную международную научную конференцию «Параллельные вычислительные технологии» (2008 г., Санкт-Петербург), Всероссийскую научно-методическую конференцию «Телематика» (2003, 2004, 2008 гг., Санкт-Петербург), V межвузовскую научную конференцию молодых ученых (2008 г., Санкт-Петербург), совещание по международному европейскому проекту ECO-NET «Meeting on ECO-NET program No 12599PJ on Wave and Current Interaction in Coastal Environment» (2006 г., Брест, Франция), международную конференцию и выставку по освоению ресурсов нефти и газа Российской Арктики и континентального шельфа СНГ «RAO/CIS Offshore» (2008 г., Санкт-Петербург), конференцию-конкурс «Технологии Microsoft в теории и практике программирования» (2008 г., Нижний Новгород).

Публикации. Г1о теме диссертации опубликовано 30 печатных работ (из них 7 — в изданиях, соответствующих требованиям ВАК РФ к кандидатским диссертациям).

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы (75 наименований) и 2 приложений. Содержит 134 с. текста (из них 116 — основного текста и 18 — приложений), включая 33 рис. и 4 табл.

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

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

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

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

• Неоднородность. Неоднородность измерений возникает в силу различий в постановках экспериментов, методов и средств измерения.

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

В итоге данные измерений можно описать в виде набора векторов ^) = (у!)(у)],/е1...Лг^е1...М, где разрозненные данные измерений по N

источникам и М масштабам изменчивости, а V - пространственная и (или) временная координата. При этом особенности представления моделей связаны со способом представления их параметров. Так, вектор неизвестных (настраиваемых) параметров удобно представить как 3 = (Н1,2г,...,Н>,), где Е,-параметры У -ой модели, которые в общем случае также являются вектором. При моделировании сложных систем в результате иерархической структуры моделей выходные величины моделей более высокого уровня используются как параметры моделей более низкого уровня. Данную особенность сложных систем удобно представить в следующей форме:

Уы = КЬ'Л»)

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

(Н,),...,/^(Нд,) и разрозненными наблюдениями у за поведением реальной системы

^...^„Я-^тт (2)

при заданном наборе ограничений ) е £2,, 1 е 1... N.

Функциональная схема процедуры идентификации, реализующая данную логику, приведена на рис. 1.

Ошибка моделирования

(Я Ё

Модель 1 | ■

Модель Модель '

Л

\У\ \Уг

/ N

I Внешняя Сложная среда Н

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

т

к~^ Л ф Л

\Уг ХУ*

Ошибка измерений

| Наблюдения 1 | I | Наблюдения 2 [ -Наблюдения N }.....

Рис. 1. Функциональная схема процедуры идентификации модели сложной системы

Особенностью данной схемы является неполнота данных наблюдений, относящихся к моделям разного уровня. При этом необходимость оценки всего вектора настраиваемых параметров сохраняется. При такой постановке задачи необходимо учитывать, каким образом связаны между собой отдельные модели в (1), и какие параметры из 5, играют наибольшую роль в процессе моделирования. Результатом процесса идентификации являются оценки вектора параметров Н', принадлежащих некоторому вероятностному8 интервалу, что отражено на рис. 1.

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

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

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

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

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

ч 1 ( дР дР)

/X Эу дх)

где /к = 2£^Бт(ф) - параметр Кориолиса; р - плотность воздуха, О - угловая скорость вращения Земли; <р - широта места, и1 и V — компоненты

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

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

-1 +

(4)

где /к- параметр Кориолиса, (3 = ^и* + V* - скорость гео строфического ветра,

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

Р = —— и а - угол отклонения направления ветра от изобары. В теоретических йг

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

9 Поля давления американского реанализа НСЕР/НСАЯ заданы на ре1улярной сетке 2.5" х 2.5°, а европейского Ега-40 3.75" х 3.75". Сстки покрывают весь Земной шар.

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

Идентификация параметров модели, по сути, разбивается на два этапа, см. рис. 2.

Рис. 2. Общая схема идентификации модели приводного ветра в синоптическом и климатическом диапазонах изменчивости

На первом этапе определяются параметры расчета прямоугольной сеточной области (5*,5_у). В качестве критерия качества идентификации предлагается использовать векторный коэффициент корреляции между геострофическим ветром и измерениями приводного ветра. В качестве алгоритма идентификации был выбран алгоритм случайного поиска, использующий на очередной итерации только значение в текущей точке, а также наилучшее значение целевой функции, полученное на предыдущих шагах. Вторым этапом, как в алгоритме моделирования, так л в процедуре идентификации, является оценка коэффициентов перехода от градиентного ветра к приводному ветру, а также углов отклонения направления ветра от изобары в зависимости от стратификации атмосферы. При расчете данных коэффициентов необходимо, помимо значения модуля и направления смоделированного градиентного ветра, использовать значения температуры воды и воздуха в данной точке акватории (стратификация атмосферы). Коэффициенты перехода (а,Р) определяются через средние многолетние значения отношения измеренного и смоделированного градиентного ветра в соответствующих диапазонах разностей температур воды и воздуха, и силы градиентного ветра. Использование квадратичного критерия качества (сумма квадратов невязок измерений и модели) позволяет построить вероятностный

и

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

Предложенный подход к идентификации параметров модели приводного ветра был использован для расчета ветра в акватории Атлантического океана и в Карском море. Уточнение параметров модели посредством идентификации позволило повысить качество результирующих данных (векторный коэффициент корреляции составляет 0.82 по отношению к измерениям; для данных реанализа МСЕР/Ы САЛ. эта величина составляет 0.74). На рис. 3 приведен пример расчета для Карского моря.

-». 1 1 1 (а)

m (м/с)

У- .... j

а 2

-

>/СГ*~ "1 1 , № (м/с)

Ф*' ' 1 1 г '(б)'. :V

-

- - ' 'у

1 ,1 1 1 1 ф I 1 1

0 5

m (м/с)

С СБ В ЮВ К> ЮЗ 3 СЗ С СБ

06.09.1999 09.09.1999 12.09.1999 15.09.1999 18.09.1999

Рис 3. Результаты уточнения модели скорости ветра в Обской губе (Карское море); (а) модуль скорости ветра в 30 наиболее сильных штормах: (1) наблюдения (V*), непараметрическая (2) и параметрическая (3) регрессия на данные по результатам идентификации; (б) направления скорости ветра в 30 наиболее сильных штормах: данные наблюдений (V4) и реанализа NCEP/NCAR; (в) сопоставление рядов модуля скорости ветра по разным источникам: (1) наблюдения на ГМС; (2) расчет ветра по полям давления NCEP/NCAR; (3) «откорректированные» по регрессии данные ветра NCEP/NCAR; (4) исходные данные ветра NCEP/NCAR

Поскольку поля атмосферного давления и ветра в различные моменты времени являются только локально зависимыми, это позволяет произвести параллельную декомпозицию расчетного алгоритма по времени, учитывая необходимость перекрытия между отдельными фрагментами данных. Его размер зависит от способа интерполяции по времени, что позволяет сохранить точность при определении барической тенденции. Испытания масштабируемости параллельного алгоритма, реализованного в рамках схемы на рис. 2, были проведены для 16, 32 и 128 процессоров. В результате были получены ускорения 14, 27 и 71 раз соответственно, что заметно превышает эффективность распараллеливания непосредственно алгоритма оптимизации10. Базовый модуль расчета полей ветра был написан на языке С++. Внешний модуль декомпозиции данных, удаленного запуска и контроля вычислений был реализован на языке СИ. В качестве средства удаленного запуска модулей на узлах кластера использовались \УЕВ-сервисы.

Третья глава посвящена разработке параллельного математического обеспечения идентификации сложных систем с явным заданием динамических параметрических связей на примере задачи параметризации и оценивания климатических спектров морского волнения. Под климатическим спектром волн понимают характерный элемент ансамбля спектров, имеющий определенную вероятность и обуславливающий некоторые характерные волновые условия на заданной акватории. Функционально подобные классы спектров могут состоять из нескольких волновых систем и могут представлять собой хорошо известные аппроксимации, что позволяет представить спектр 5(со,0) в виде 5(ю,0,Н), где Е - набор параметров. В данной работе рассматривается аппроксимация спектра вида КЖвЧУАР11, классическая запись которого в частотной области о имеет вид

(со-со V

«g <а5

ехр

■1>25(— ю

у®, где 5 = ехр

2а or

(5)

Здесь а - так называемый параметр Филипса (параметр масштаба спектра), у -параметр пиковатости, а - параметр формы, - частота максимума спектра.

Даже при постоянном и устойчивом ветре волны распространяются не в одном фиксированном направлении, а в некотором секторе. Частотно-направленные спектры ветрового волнения и зыби можно представить в форме 5'(сй,0) = 5(ю)2(0), где 5(ш) - частотный спектр волнения, а 0(0) - функция углового (0) распределения энергии

0 — 0 Г*'2 Т'

е(0) = ОДсо5(—)]\где С(*) = {соб^оВ . (6)

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

" Hasselmann, К., et al., Measurements of wind-wave growth and swell decay during the Joint North Sea Wave Project (JONSWAP), Dtsch. Hydrogr. Z., 8(12) {Suppt. A), 1-95,1973.

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

J(S,...SM) = ]¡ 5(со,е)-]Г5,(соДЕ,)

dcodQ

(7)

относительно набора параметров Н, у (М - неизвестное число волновых систем).

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

База данных спектров

/

фГЯ т

IH

г

Идентификация

параметров каждого спектра

/

Сохраняем

У

1,5

Оценка климатических спектров'

' Вероятности перехода между классами спектров Р,

7

Рис. 4. Общая схсма идентификации модели климатических спектров

На рис. 4 приведена схема идентификации модели климатических спектров морского волнения. Ее отличием от аналогичной схемы для расчета полей приводного ветра (рис. 2) является применение процедуры идентификации к наблюдениям синоптического диапазона для получения характеристик в климатическом диапазоне, в то время как для модели расчета полей ветра наблюдения как раз климатического диапазона использовались для настройки модели в синоптическом диапазоне.

Модель (5) различает одно-, двух- и многопиковые (по переменным со и 9 ) спектры. Выделены пять классов климатических спектров: ветровые волны; зыбь (к=2); ветровые волны и близкая по частоте «свежая» зыбь (к=3); ветровые волны и «свежая» зыбь, различающиеся и по частоте, и но направлению (к=4);

ветровые волны и зыбь, близкие (плохо различающиеся) по частоте и направлению (к=5). Каждый класс соответствует устойчивому состоянию к, следовательно, синоптическая изменчивость волнения может быть представлена как марковская цепь к = £(/) с матрицей переходных

вероятностей = р\к{'*п = /1 к0) = у}, /',_/' = 1,/и, и вектором предельной

вероятности п1 = =]}, у' = 1,т. Оценка коэффициентов в матрице переходных вероятностей и векторе предельной вероятности также является частью процедуры идентификации параметров модели.

В итоге, задача определения климатических спектров сводится к трем этапам:

• В каждый момент времени I в каждой точке акватории (х,у) необходимо идентифицировать параметры Е' модели (5-6).

• Провести классификацию спектров в каждый момент времени Г на основе идентифицированных параметров Е'(д:,у,() и характерных особенностей климатических спектров.

• Получить параметры модели перемежаемости климатических спектров в форме матрицы переходных вероятностей марковской цепи к = £(;) как статистических характеристик поля Е'(х,у,1).

На рис. 5 приведен пример применения процедуры идентификации к результатам расчетов морского волнения в ЮВ части Северного моря - т.н. «звезда» климатических спектров.

Рис. 5. Звезда частотно-направленных климатических спектров для ЮВ части Северного моря

Несмотря на то, что расчет спектра морского волнения в каждой точке пространства основан на решении дифференциального уравнения баланса волновой энергии в спектральной форме, и, как следствие, представляет собой итеративно связный процесс, обработку спектров в различные моменты времени можно производить независимо. В результате, наиболее простым вариантом распараллеливания процедуры расчета климатических спектров является распараллеливание по данным. Программно реализованы версии параллельного алгоритма идентификации для кластерных систем (распараллеливание для БМР-узлов было выполнено с использованием технологий ОрепМР, высокоуровневое распараллеливание было выполнено на базе технологий \УЕВ-сервисов) и распределенных вычислений (с использованием среды А1сЬет1). Проведенные исследования масштабируемости алгоритма на кластерной системе для 64 и 128 процессоров позволили получить ускорения 62 и 123 раза соответственно'2. Для среды распределенных вычислений в локальной сети с 15 вычислителями было получено ускорение около 12 раз, что свидетельствует о хорошей масштабируемости параллельного алгоритма даже для слабосвязанных параллельных вычислительных архитектур.

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

Эпидемиологическая динамика ВИЧ описывается моделью комплексной сети, в которой каждый узел представляет собой отдельного человека, находящегося в одном из трех основных состояний: восприимчивый к вирусу (¿'), зараженный (/), удаленный из сети в результате диагностики СПИД или смерти (/?). Сетевые связи (ребра графа) указывают на наличие контактов между людьми, которые могут приводить к новым случаям заражения. Для корректного описания динамики вируса внутри отдельного человека между состояниями зараженный и удаленный вводится ряд дополнительных промежуточных состояний, описываемых нестационарной марковской моделью специального вида'3. Нсстационарность модели определяется наличием факторов, оказывающих влияние на вероятность заражения, эффектом диагностики и лечения.

11 Массив данных состоит из 8898 спектров. Каждый спектр содержит 36 точек по направлению и 21 точку по частоте в диапазоне от 0.0442 до 0 5 Гц.

" Sloot, Р. М. A., Ivanov, S. V., Boukhanovsky, А. V., Van De Vijver, D A. M С and Boucher, CAB. Stochastic simulation of HIV population dynamics through complex network modeling // International Journal of Computer Mathematics, 2008,1175-1187

Комплексная сеть задается набором {G, З}, где G - ориентированный граф со множествами вершин V и ребер Е, а 3 - эволюционный оператор, определяющий изменение сети за интервал времени I:

(8)

Эволюционный оператор (8) может быть представлен как композиция нескольких различных операторов 3 = ®3t, соответствующих различным

динамическим факторам (процессу распространения инфекции, динамике ребер и динамике узлов). В общем случае такие операторы являются некоммутативными.

Процедура моделирования эпидемиологической динамики ВИЧ задается следующей последовательностью шагов:

1. Сгенерировать сеть в соответствии с выбранным распределением степеней вершин и начальным числом инфицированных р0.

2. Заразить узлы, имеющие общие ребра с инфицированными узлами, с вероятностью X для каждого узла независимо.

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

СПИД, из сети удаляются.

4. Применить демографическое правило (часть узлов удаляется из сети, а часть добавляется в соответствии с демографическим балансом).

5. Зафиксировать текущее состояние узлов и сгенерировать новую сеть.

6. Повторять (2)-(5) необходимое число раз.

Все шаги моделирования основаны на генерации случайных чисел, поэтому метод моделирования относится к классу Монте-Карло. Однако данная модель включает в себя набор неизвестных параметров, которые могут быть оценены только на основе экспериментальных данных и процедуры идентификации. В частности, к ним относится вероятность заражения X, начальное число инфицированных р0 и демографический коэффициент d. Это позволяет сформулировать задачу идентификации модели комплексной сети как задачу оптимизации (2), на каждом шаге которой выполняется численное решение (8)

2007

ХМ-л/ш;]2 min. (9)

(-1981 (М.Р»)

Здесь AIDS, - ежегодное число официально регистрируемых случаев СПИД в конкретной стране; в силу специфики AIDS, как интегральной характеристики по большой выборке, в силу центральной предельной теоремы в (9) допустимо применять евклидову метрику для критерия качества. Общая схема идентификации, иллюстрирующая предложенный подход, приведена на рис. 6.

Идентификация

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

Особенностью схемы, приведенной на рис. 6, является необходимость проведения всего цикла моделирования для идентификации неизвестных параметров, что порождает параметрическую зависимость между моделями. При этом неизвестные параметры относятся как к микромасштабу (вероятность заражения индивидуума), так и к макромасштабу (демографический коэффициент, размер начальной популяции) модели. При этом данные наблюдений (как интегральное количество заболевших) относятся исключительно к макромасштабу. Для идентификации параметров модели были использованы данные по случаям СПИД в США (доступны с 1981 года). На рис. 7(а,б) приведены характерные формы комплексных сетей для гомо- и гетеросексуальных групп риска, а на рис. 7(в,г) - интегральные характеристики эпидемиологической ситуации - количество заболевших СПИД и количество ВИЧ-инфицированных. Стоит отметить, что число случаев ВИЧ невозможно измерять прямыми методами, так как многие носители вируса не знают о своем статусе. Даже в случае диагностики восстановить по клиническим данным точное время заражения невозможно, однако моделирование позволяет сделать оценки реального числа случаев ВИЧ в масштабе популяции не только к текущему моменту, но и восстановить ход развития эпидемии в прошлом. Таким образом, данную модель сложной системы можно рассматривать как виртуальную измерительную систему.

А)

^ЗииИИ^г

В)

45 ООО

q: 40000 °о

s с 35000 •

u 30000

3" С 25000 20000

о 15000

с 10000

у 5000 /

0 У

Год

Рис. 7. Результат моделирования динамики ВИЧ в США; (а) визуализация сети для гомосексуальной популяции; (б) визуализация сети для гетеросексуальной популяции; (в) результат моделирования и данные измерений пол случаям СПИД; (г) модельная кривая случаев ВИЧ (для гомосексуальной популяции)

Моделирование эпидемиологической динамики ВИЧ, в силу (8), является эволюционным процессом. В результате распараллеливание такой модели по времени не представляется возможным. Потому алгоритм моделирования (и использующий его алгоритм идентификации) основаны на распараллеливании наиболее трудоемкой процедуры - генерации графа комплексной сети. Учитывая, что комплексная сеть является статистически однородной, то количество ребер между двумя блоками сети одинакового размера должно быть в пределе одинаковым; следовательно, для любой пары блоков ребра можно генерировать независимо. Соответствующий параллельный алгоритм реализован для систем с общей памятью и кластерных систем. Получены удовлетворительные показатели производительности. Так, для двух- и четырехядерных систем были получены эффективности ускорения 89% и 71% соответственно. Для вычислительных систем с разделенной памятью эффективность распараллеливания несколько ниже и составила около 45% для системы из четырех двухпроцессорных модулей.

80000 70000 I 60000 I 50000 I 40000 Ö 30000 £ 20000 х 10000 о

/ / / f # ##

Основные результаты диссертационной работы состоят в следующем:

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

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

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

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

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

Публикации по теме диссертационной работы

1. Иванов C.B. Параллельные алгоритмы моделирования комплексных сетей / C.B. Иванов, И.И. Колыхматов, A.B. Бухановский // Известия высших учебных заведений. Приборостроение. - №10. — 2008. - С. 5-12. (по перечню ВАК)

2. Высокопроизводительный программный комплекс моделирования экстремальных гидрометеорологических явлений. Часть I: Постановка задачи, модели, методы и параллельные алгоритмы / A.B. Бухановский, C.B. Иванов [и др.] // Научно-технический вестник СПбГУ ИТМО. Выпуск 54. Технологии высокопроизводительных вычислений и компьютерного моделирования. - СПб.: СПбГУ ИТМО, 2008. - С. 56-63. (по перечню ВАК)

3. Высокопроизводительный программный комплекс моделирования экстремальных гидрометеорологических явлений. Часть II: Разработка и оценка программной архитектуры / C.B. Ковальчук, C.B. Иванов [и др.] // Научно-технический вестник СПбГУ ИТМО. Выпуск 54. Технологии высокопроизводительных вычислений и компьютерного моделирования. -СПб.: СПбГУ ИТМО, 2008. - С. 64-71. (по перечню ВАК)

4. Высокопроизводительный программный комплекс моделирования экстремальных гидрометеорологических явлений. Часть III: Интерпретация и использование результатов расчетов / C.B. Иванов [и др.] // Научно-технический вестник СПбГУ ИТМО. Выпуск 54. Технологии

высокопроизводительных вычислений и компьютерного моделирования. -СПб.: СПбГУ ИТМО, 2008. - С. 72-79. (по перечню ВАК)

5. Особенности проектирования высокопроизводительных программных комплексов для моделирования сложных систем / C.B. Ковальчук, C.B. Иванов [и др.] // Информационно-управляющие системы. - 2008. - №3. -С. 10-18. (по перечню ВАК)

6. Иванов C.B. Идентификация параметрически связанных моделей сложных систем. / C.B. Иванов // Научно-технический вестник СПбГУ ИТМО. Выпуск 54. Технологии высокопроизводительных вычислений и компьютерного моделирования. - СПб.: СПбГУ ИТМО, 2008. - С. 100-107. (по перечню ВАК)

7. Моделирование экстремальных явлений в атмосфере и океане как задача высокопроизводительных вычислений / A.B. Бухановский, C.B. Иванов [и др.] // Вычислительные методы и программирование. - 2008. - Том 9. -С. 141-153.

8. Высокопроизводительный программный комплекс моделирования экстремальных гидрометеорологических явлений: эффективное управление параллельными вычислениями и представление результатов расчетов / C.B. Ковальчук, C.B. Иванов [и др.] // Научный сервис в сети Интернет: решение больших задач: Труды Всероссийской научной конференции (22-27 сентября 2008 г., г. Новороссийск). - М.: Изд-во МГУ. -2008.-С. 106-108.

9. Ковальчук C.B. Проектирование и разработка высокопроизводительного программного комплекса моделирования экстремальных явлений в атмосфере и океане на основе распределенных технологий .NET / C.B.Ковальчук, С.В.Иванов, A.B.Бухановский // Технологии Microsoft в теории и практике программирования. Материалы конференции (Нижний Новгород, 19-20 марта 2008 г.). - Нижний Новгород: Изд-во Нижегородского госуниверситета, 2008. - С. 171-173.

10. Колыхматов И.И. Высокопроизводительные технологии синтеза, эволюционного моделирования и визуализации комплексных сетей в среде Microsoft Compute Cluster Server / И.И. Колыхматов, C.B. Иванов, A.B. Бухановский // Технологии Microsoft в теории и практике программирования. - Материалы конференции (Нижний Новгород, 19-20 марта 2008 г.). - Нижний Новгород: Изд-во Нижегородского госуниверситета. - 2008. - С. 174-175.

11. Моделирование экстремальных явлений в атмосфере и океане как задача высокопроизводительных вычислений / A.B. Бухановский, C.B. Иванов [и др.] // Параллельные вычислительные технологии (ПаВТ2008): Труды международной научной конференции (Санкт-Петербург, 28 января - 1 февраля 2008 г.). - Челябинск: Изд-во ЮУрГУ. - 2008. - С. 57-68.

12. Иванов C.B. Параллельные алгоритмы моделирования комплексных сетей / C.B. Иванов, И.И. Колыхматов, A.B. Бухановский // Параллельные вычислительные технологии (Г1аВТ2008): Труды международной научной

конференции (Санкт-Петербург, 28 января - 1 февраля 2008 г.). -Челябинск: Изд-во ЮУрГУ, 2008. - С. 395-402.

13. Иванов C.B. Моделирование эволюционной динамики ВИЧ / C.B. Иванов, И.И. Колыхматов, A.B. Бухановский // Труды XV Всероссийской научно-методической конференции Телематика'2008. СПб, Том 1. - СПб.: СПбГУ ИТМО, 2008. - С. 103-104.

14. Иванов C.B. Моделирование эволюционной динамики ВИЧ / C.B. Иванов, A.B. Бухановский // Труды XV Всероссийской научно-методической конференции Телематика'2008. СПб. - Том 1. - СПб.: СПбГУ ИТМО, 2008. -С. 104-105.

15. Проблемы переноса вычислительных приложений кластерного уровня в среду Грид на примере Grid Programming Environment / A.B. Ларченко, С.В.Иванов [и др.] // Научный сервис в сети Интернет: многоядерный компьютерный мир. 15 лет РФФИ: Труды Всероссийской научной конференции (24-29 сентября 2007 г., г. Новороссийск). - М.: Изд-во МГУ, 2007. - С. 134.

16. Справочные данные по режиму ветра и волнения Балтийского, Северного, Черного, Азовского и Средиземного морей / A.B. Бухановский, C.B. Иванов [и др.] // Российский Морской регистр судоходства. - СПб. -2006.-450 с.

17. Бухановский A.B. Подходы, опыт и некоторые результаты исследований волнового климата океанов и морей. I. Постановка задачи и входные данные / A.B. Бухановский, Л.И. Лопатухин, C.B. Иванов // Вестник СПбГУ. - сер. 7. - вып. 3. - 2005. - С. 62-74. (по перечню ВАК)

18. Иванов C.B. Приближение частотно-направленных спектров морского волнения методом Монте-Карло в исследованиях спектрально-волнового климата / C.B. Иванов // Сборник трудов международной школы-конференции молодых ученых, аспирантов и студентов "Изменение климата и окружающая среда". - СПб.: Изд-во "Гранд", 2005. - С. 248-253.

19. Нечаев Ю.И. Виртуальное моделирование динамики судна на морском волнении в интеллектуальных тренажерах / Ю.И. Нечаев, A.B. Бухановский, C.B. Иванов // Искусственный интеллект №3. - 2004. -С. 350-359.

20. Нечаев Ю.И. Виртуальное моделирование динамики судна на морском волнении в интеллектуальных тренажерах / Ю.И. Нечаев, A.B.Бухановский, С.В.Иванов // Материалы международной научно-технической конференции "Искусственный интеллект, интеллектуальные и многопроцессорные системы". - т.1. - 2004. - С. 159-164.

21. Богданов A.B. Особенности организации систем хранения и обработки данных с использованием высокопроизводительных вычислительных комплексов / A.B. Богданов, A.B. Бухановский, C.B. Иванов //Труды XI Всероссийской научно-методической конференции Телематика'2004. -СПб.-2004.-С. 163.

22. Нечаев Ю.И. Визуализация динамических сцен в интеллектуальных обучающих системах / Ю.И. Нечаев, A.B. Бухановский, C.B. Иванов //

Труды XI Всероссийской научно-методической конференции Телематика'2004. - СПб. - 2004. - С. 359-361.

23. Бухановский А.В. Параллельна« обработка данных в информационно-управляющих системах / А.В. Бухановский, С.В. Иванов // УИТ-2003. -Сборник докладов в 2-х томах. - Том 2. - СПб. - 2003. - С. 64-69.

24. Распределённый интеллектуальный кардиологический комплекс нового поколения на базе суперкомпьютеров семейства "СКИФ" / А.В. Бухановский, С.В. Иванов [и др.] // УИТ-2003. Сборник докладов в 2-х томах. - Том 2 . - СПб. - 2003 . - С. 243-248.

25. Телемедицинский комплекс на базе суперкомпьютерных технологий / А.В. Бухановский, С.В. Иванов [и др.] // Труды X Всероссийской научно-методической конференции Телематика'2003. - СПб. - 2003. - С. 288-289.

26. Иванов С.В. Особенности технологий обработки больших объёмов информации на параллельных суперкомпьютерах / С.В. Иванов // БИКАМП-2003. - Сборник докладов. - СПб. - 2003. - С. 181-185.

27. Бухановский А.В. Особенности оптимизации распределения вычислительной нагрузки в задачах параллельной обработки информации и имитационного моделирования / А.В. Бухановский, С.В. Иванов // ИММЮД-2003. - Сборник докладов в 2-х томах. - Том 1. - СПб. - 2003. -С. 69-75.

28. Stochastic simulation of HIV population dynamics through complex network modeling / P.M.A. Sloot, S.V. Ivanov [et al.] // International Journal of Computer Mathematics. - 2008,- pp. 1175-1187.

29. Hindcasting of Wind and Wave Climate of Seas Around Russia / L.J. Lopatukhin, S.V. Ivanov [et al.] // 8th International Workshop on Wave Hindcasting and Forecasting. - North Shore, Oahu, Hawaii. - November 14-19. - 2004. - http://www.waveworkshop.org/8thWaves/Papers/D2.pdf

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

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел. (812) 233 4669 объем 1 п.л. Тираж 100 экз.

СОДЕРЖАНИЕ.

ВВЕДЕНИЕ.

ГЛАВА 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х гг. до наших дней. физической модели расчета полей приводного ветра как элемента сложной системы «океан-атмосфера», предлагается схема идентификации параметров модели и разрабатывается параллельный вычислительный алгоритм.

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

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

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

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

Заключение

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.