Модели и метод построения мультиагентных систем поддержки принятия решений для управления распределенными объектами тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Васильев, Николай Владимирович

• Васильев, Николай Владимирович
• кандидат технических наук
• 2009

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

ОБОЗНАЧЕНИЯ И СОКРАЩЕНИЯ.

ВВЕДЕНИЕ.

1. ОСОБЕННОСТИ ПОСТРОЕНИЯ МУЛЬТИАГЕНТНЫХ СППР ДЛЯ

УПРАВЛЕНИЯ РАСПРЕДЕЛЕННЫМИ ОБЪЕКТАМИ.

1.1. Особенности применения мультиагентных СППР в задачах управления распределенными объектами.

1.2. Анализ современных методов построения СППР для управления распределенными объектами с динамической структурой.

1.3. Анализ методов повышения эффективности функционирования мультиагентных СППР для управления распределенными объектами с динамической структурой.

1.4. Метод построения перспективной мультиагентной СППР для управления распределенными объектами и постановка задачи исследования.

ВЫВОДЫ.

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

СОБЫТИЙ НА ОСНОВЕ АЛГЕБРЫ ПРОЦЕССОВ МИЛНЕРА.

2.1. Формализация процесса построения модели распределенного объекта управления.

2.2. Определение основных классов поведений элементов распределенного объекта.

2.3. Модель поведения элементов распределенного объекта управления на основе алгебры процессов Милнера.

2.4. Метод получения графов зависимостей событий на основе алгебры процессов Милнера.

ВЫВОДЫ.

3. РАЗРАБОТКА АЛГОРИТМА РЕСТРУКТУРИЗАЦИИ МУЛЬТИАГЕНТНОЙ СППР ПРИ ВОЗНИКНОВЕНИИ СТРУКТУРНЫХ

ИЗМЕНЕНИЙ РАСПРЕДЕЛЕННОГО ОБЪЕКТА УПРАВЛЕНИЯ.

3.1. Описание целевой функции мультиагентного сообщества СППР для управления распределенным объектом.

3.2. Модификации схемы опроса элементов и взаимодействия агентов.

3.3. Модель процесса реструктуризации мультиагентной СППР для управления распределенным объектом.

3.4. Алгоритм реструктуризации СППР при возникновении структурных изменений распределенного объекта.

ВЫВОДЫ.

4. ПОСТРОЕНИЕ И ЭКСПЕРИМЕНТАЛЬНОЕ ИССЛЕДОВАНИЕ

ФУНКЦИОНИРОВАНИЯ ТИПОВОЙ МУЛЬТИАГЕНТНОЙ СППР ДЛЯ УПРАВЛЕНИЯ РАСПРЕДЕЛЕННЫМ ОБЪЕКТОМ.

4.1. Структура, состав и алгоритмы функционирования типовой МА СППР для управления корпоративной сетью.

4.2. Описание поведения элементов и граф зависимостей событий фрагмента корпоративной сети.

4.3. Структура и состав исследовательского макета мультиагентной СППР для управления фрагментом корпоративной сети.

4.4. Экспериментальная проверка исследовательского макета мультиагентной СППР.

ВЫВОДЫ.

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

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

Значительный вклад в становление и развитие теории построения мультиагентных СППР внесли следующие зарубежные исследователи: М. Вулдридж (Wooldrige М), Н. Дженнингс (Jennings N.\ Д. Вейс (Weiss G.), Т. Сандхольм {Sandholm Т.) , А. Оссовский (Ossowsky S.) и др. Среди отечественных специалистов в области СППР и мультиагентных систем следует отметить Городецкого В.А., Поспелова Д.А., Тарасова В.Б., Трахтенгерца Э.А., Яшина А.И. В области построения систем управления сложными динамическими объектами следует назвать Макарова И.М., Растригина JI.A., Колесникова A.A., Цыпкина Я.З. и других. Результаты данных ученых и их научных школ явились теоретическим базисом для выполнения данного исследования.

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

- аварии на энергосетях, приводящие к частичному уничтожению структурных элементов (серверов) корпоративной СППР;

- изменения структурной топологии (аварии на узлах и пунктах управления) полевых сетей связи МЧС, МО РФ в условиях ликвидации чрезвычайных ситуаций и локальных конфликтов, соответственно;

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

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

Данное противоречие определяет актуальность темы настоящего диссертационного исследования.

Целью диссертационной работы является улучшение научно-методического аппарата ситуационного анализа и методов построения мультиагентных СППР для управления распределенными объектами с динамически изменяемой структурой.

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

1. Системный анализ задачи реструктуризации СППР для управления РОУ с динамически изменяемой структурой;

2. Разработка модели поведения элементов РОУ, обеспечивающей получение верифицируемой автоматной модели поведения распределенного объекта;

3. Разработка метода автоматического получения модели причинно-следственных зависимостей между событиями, порождаемыми элементами РОУ;

4. Разработка модели и алгоритма реструктуризации СППР при возникновении параметрических и структурных изменений распределенного объекта управления;

5. Построение макета типовой мультиагентной СППР для управления РОУ и оценка эффективности предлагаемых решений.

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

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

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

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

Четвертая глава посвящена экспериментальной проверке полученных результатов. Определена структура и состав исследовательского макета МА СППР для управления фрагментом корпоративной сети. Продемонстрировано использование предложенных во второй главе модели поведения элементов распределенных объектов управления и метода получения графов зависимостей событий на основе алгебры процессов Милнера. Приводится описание реализованной имитационной модели подсистемы реструктуризации СППР. Приводятся результаты экспериментального исследования качества решений, " принимаемых подсистемой реструктуризации.

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

К новым научным положениям, разработанным в ходе исследований и выносимым на защиту, относятся следующие:

1. Модель поведения элементов распределенного объекта управления на основе алгебры процессов Милнера.

2. Метод получения графов зависимостей событий на основе алгебры процессов Милнера.

3. Модель и алгоритм реструктуризации СППР при возникновении структурных изменений распределенного объекта управления.

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

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

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

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

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

Достоверность результатов диссертационной работы обеспечена:

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

- реализацией полученных результатов в ОКР и НИР по созданию программно-аппаратного комплекса автоматизации процесса управления распределенными объектами на примере сети связи;

- итогами экспериментальной оценки эффективности макета мультиагентной СППР при стендовых испытаниях;

Результаты диссертационной работы докладывались и обсуждались:

- на ежегодных научно-технических конференциях профессорско-преподавательского состава СПбГЭТУ (2006 - 2009 гг.);

- на военно-научной конференции "Информационная технология в радиоэлектронных системах", 2007 г. (г. Горелово);

- на седьмой всероссийской научно-технической конференции «Новые информационные технологии в системах связи и управления», 2008 г. (г. Калуга).

По теме диссертации опубликовано 7 научных работ, из них - 4 статьи (2 статьи опубликованы в ведущих рецензируемых научных журналах и изданиях, определенных ВАК), 3 работы - в материалах всероссийских научно-технических конференций.

По результатам работы получены акты реализации от следующих организаций: ОАО «Интелтех» (г. Санкт-Петербург), Санкт-Петербургского государственного электротехнического университета "ЛЭТИ" им. В.И. Ульянова (Ленина), Санкт-Петербургского государственного университета телекоммуникаций им. проф. М.А. Бонч-Бруевича.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Васильев, Николай Владимирович

150 ВЫВОДЫ

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

2. Подтверждена гипотеза об адекватности предложенной архитектуры мультиагентной СППР для управления РОУ, а также разработанных моделей поведения элементов РОУ и метода получения графа зависимостей событий на основе алгебры процессов Милнера;

3. Подтверждена гипотеза о необходимом увеличении начальной оптимальной температуры сообщества агентов реструктуризации с ростом сложности РОУ;

4. Отработаны формы WEB - интерфейса для поддержки администратора мультиагентной СППР в процессе решения задач реконфигурирования системы по измененной структуре фрагмента корпоративной сети и предложены методики проверки работоспособности подсистемы реструктуризации и построения структурной и динамической моделей;

5. Проведенное моделирование показало:

- оптимальная начальная температура процесса реструктуризации составляет:

-для 400 узлов - 5°±1°;

- для 700 узлов - 8°± 1°;

-для 1000 узлов - 12° ± 1°;

- для 2000 узлов - 25° ± 1°;

- оптимальное число агентов составляет:

- для 400 узлов - от 5 до 16 агентов;

- для 700 узлов - от 7 до 18 агентов;

- для 1000 узлов - от 10 до 22 агентов;

- для 2000 узлов - от 11 до 26 агентов;

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

ЗАКЛЮЧЕНИЕ

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

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

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

2. Показано, что двухслойная архитектура СППР, предполагающая сочетание иерархического и децентрализованного подходов к организации, позволяет учесть высокую размерность изменяемого во времени пространства" состояний РОУ. Первичность процесса компенсации структурных изменений РОУ по отношению к процессу выработки решения предопределяет верхний управляющий слой, как обеспечивающий решение задачи реструктуризации. Децентрализованный подход к построению как верхнего, так и нижнего слоя учитывает распределенный характер объекта управления. На основании изложенного, предложена архитектура перспективной мультиагентной СППР для управления распределенным объектом.

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

4. Разработана модель поведения элементов РОУ, обеспечивающая получение верифицируемой автоматной модели поведения распределенного объекта. Показано, что для описания поведения элементов РОУ достаточно ввести 3 класса объектов: источники, порождающие события проводники и стоки. Указанные классы объектов моделируются выражениями алгебры процессов Милнера специального вида, которые являются по своей сути символической формой задания автомата.

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

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

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

Практическая значимость полученных результатов состоит в разработке и внедрении научно-методического аппарата проектирования мультиагентных СППР для управления РОУ с динамически перестраиваемой структурой в промышленные НИР и ОКР.

По теме диссертации опубликовано 7 научных работ, из них - 4 статьи (2 статьи опубликованы в ведущих рецензируемых научных журналах и изданиях, определенных ВАК), 3 работы - в материалах всероссийских научно-технических конференций.

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

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

1. Адерсон Д. Дискретная математика и комбинаторика. М.: Вильяме, 2003.-635 с.

2. Арсеньев Б.П. , Яковлев С.А. Интеграция распределенных баз данных. -М: Лань, 2001,-460 с.

3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. -М.: Мир, 1979. 535 с.

4. Ачасова С.М., Бандман О.Л. Корректность параллельных вычислительных процессов. Новосибирск.Наука, 1990. -253 с.

5. Беллман Р. Введение в теорию матриц.- М.Наука, 1969. 368 с.

6. Бломмерс Джон OpenView Network Node Manager: Разработка и реализация корпоративного решения. М. .Интернет - Университет Информационных Технологий,2005. - 265 е., ил.

7. Борщев A.B., Карпов Ю.Г., Рудаков В.В. О корректности параллельных алгоритмов // Программирование. 1996. - №4. - С. 5 - 17.

8. Буч Г. Объектно-ориентированный анализ и проектирование. М.: Бином; СПб.: Невский диалект, 1998. - 560с.

9. Варшавский В.И. Коллективное поведение автоматов. М.: Наука, 1973.-340 с.

10. Варшавский В.И., Поспелов Д.А. Оркестр играет без дирижера. М.: Наука, 1984.-180 с.

11. Васильев Н.В., Смирнова H.H. Аналитический подход к верификации комплексов взаимодействующих процессов// Мехатроника, Автоматизация, Управление М. 2007г., №5 - С. 31-35.

12. Васильев, Н.В., Смирнова, H.H. Аналитический подход к исследованию поведения протокольных объектов//Актуальные вопросы ракетно-космической техники и технологий СПб.: Изд-во БГТУ "Военмех", 2006г. - Вып.4 - С. 175 - 178.