Анализ и синтез процессов преобразования ресурсов на основе имитационного моделирования и интеллектуальных агентов

-

Проблемы передачи и обработки информации

УДК 004.896

К.А. Аксенов, А.С. Антонова, И.А. Спицина

анализ и синтез процессов преобразования ресурсов на основе имитационного моделирования

и интеллектуальных агентов

Задачи анализа и синтеза организационно-технических систем

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

Формализованное решение задач анализа и синтеза представляет интерес с точки зрения автоматизации работы аналитиков и лиц, принимающих решения (ЛПР).

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

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

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

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

Задача бенчмаркинга близка задаче РБП. Цель процессного бенчмаркинга - реорганизация БП на предприятии согласно эталонной модели БП. Эталонная модель основывается на комбинации

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

Анализ моделей динамического моделирования ситуаций

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

Автоматизация РБП с использованием методов ИМ и искусственного интеллекта позволит:

снизить требования к опыту аналитика по проведению анализа и синтеза систем за счет использования формализованного опыта экспертов и применения методов математического моделирования;

провести оценку выработанных решений реинжиниринга и выбор наиболее эффективного решения на модели объекта управления (модели ОТС).

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

Рассмотрим задачу выбора модели формализации ОТС. В ходе исследования были выделены следующие модели динамического моделирования ситуаций, поддерживающие агентное представление ОТС: модель GAIA, модель Д.Ю. Бу-гайченко, модель А.В. Маслобоева, имитационная модель взаимодействия интеллектуальных агентов (ИМВИА), модель Ресурсы-Действия-Операции (РДО), модель мультиагентных процессов преобразования ресурсов (МППР).

Модель GAIA [2] предложена М. Вулдриджем, Н. Дженнингсом и предназначена для описания системы как искусственной организации, состоящей из разнородных агентов, взаимодействующих друг с другом для достижения глобальной цели. Наиболее абстрактной сущностью в иерар-

хии концептов GAIA является система, следующий уровень иерархии это роли. Ролям ставятся в соответствие типы агентов системы. Функционал агента описывается при помощи модели служб, в которой каждая служба сопоставляется с деятельностью роли.

Модель Д.Ю. Бугайченко [3] описывает интеллектуальных агентов, имеющих ментальную (BDI) архитектуру. Свойства МАС автор модели описывает при помощи разработанной формальной логики MASL - метода логической спецификации мультиагентных систем с временными ограничениями, способных к накоплению и анализу опыта.

Модель А.В. Маслобоева [4] расширяет существующую InteRRap-архигектуру ИА за счет добавления в ее состав проблемно-ориентированной подсистемы непрерывного имитационного моделирования (комплекса системно-динамических моделей), которую агенты используют для имитации сценариев развития ситуаций и прогнозирования последствий своих действий.

Имитационная модель взаимодействия интеллектуальных агентов [5] разработана Г.В. Рыбиной и С.С. Паронджановым с целью формализации коммуникативной деятельности ИА с помощью моделирования отдельных компонентов коммуникации: состава участников взаимодействия, коммуникативной среды, проблемной области, языка взаимодействия, сценариев диалога. Взаимодействие ИА осуществляется путем диалога, включающего глобальную, тематическую и локальную структуры. Для описания взаимодействия авторами модели используется теория речевых актов (ТРА).

Модель РДО [6] предназначена для описания сложных дискретных систем и протекающих в них событий с целью изучения статических и динамических характеристик событий. Система в модели на концептуальном уровне представима в виде множества ресурсов, выполняющих определенные действия. Действия описываются операциями, представляющими собой модифицированные продукционные правила, учитывающие временные связи. Операция с нулевым временным интервалом называется «точкой решения» и является аналогом реактивного агента, хранящего в базе знаний ответные реакции на воздействие среды.

Модель МППР [7] разработана на основе расширения модели процесса преобразо-

Интерфейс с внешним миром

Внешняя среда

Имитационная модель

Реактивная подсистема

Внутреннее поведение А

Логический вывод по ТБЗ

Тактическая база знаний

Планирующая подсистема

-N

Логический

вывод по СБЗ

Стратегическая база знаний

Подсистема кооперации с другими агентами

Рис. 1. Гибридная архитектура агента МППР

вания ресурсов (ППР) интеллектуальными агентами и предназначена для моделирования организационно-технических и бизнес-процессов и поддержки принятия управленческих решений. Агент модели МППР имеет гибридную архитектуру InteRRap, представленную на рис. 1.

Сравнительный анализ рассмотренных моделей динамического моделирования ситуаций приведен в табл. 1. Для проведения сравнительного анализа были выбраны следующие критерии сравнения систем: модель преобразователя ресурсов (модель дискретного бизнес-процесса); модель системы массового обслуживания (СМО) -инструмент, хорошо зарекомендовавший себя при анализе дискретных стохастических систем; модель реактивного агента и модель ИА (инструмент для описания моделей ЛПР).

Как следует из табл. 1, полный функционал ИА реализован в моделях Д.Ю. Бугайчен-ко, А.В. Маслобоева и МППР. При этом агент у Д.Ю. Бугайченко не отождествляется с ЛПР, а представляет собой программную сущность, работающую независимо от эксперта (аналитика). А.В. Маслобоев использует в качестве средства прогнозирования действий агентов комплекс непрерывных системно-динамических моделей, не поддерживающих описание дискретных процессов, протекающих в исследуемых ОТС. Модель ИМВИА ориентирована прежде всего на исследование способов коммуникаций между агентами и не поддерживает интеграцию моделей агентов с системой ИМ. Модель GAIA объединяет в себе

модели преобразователя информационных ресурсов и ИА, однако по реализованному функционалу данная модель уступает РДО и МППР.

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

Таким образом, наиболее полным функционалом формализации модели ОТС обладает модель МППР и реализующие модель продукты семейства BPsim (www.bpsim.ru).

Алгоритм анализа и синтеза

Анализ системы в рамках решения задач управления предприятием подразумевает построение аналитиком различных моделей (представлений) системы, отражающих требуемые аспекты ее поведения. Синтез построенных моделей направлен на получения альтернативных вариантов развития системы путем объединения в единый вариант различных подмножеств элементов модели. Будем различать параметрический синтез, при котором исходная модель преобразуется в ряд мо-

Таблица 1

Сравнительный анализ моделей динамического моделирования ситуаций

Критерии сравнения Модель Бугайченко А Модель Маслобоева Модель Рыбиной Модель ОА1А Модель РДО Модель МППР

Модель преобразователя ресурсов

вход/выход/условия запуска/длительность + 1 + 1+1 НЕТ + / + /+/ + + / + /+/ +

иерархическая модель преобразователя НЕТ НЕТ НЕТ НЕТ НЕТ +

временное прерывание операций НЕТ НЕТ +

Модель системы массового обслуживания НЕТ НЕТ НЕТ НЕТ + +

Модель реактивного агента (форма представления знаний) Темпоральная логика МАЗЬ Продукции Раскрашенные сети Петри НЕТ Продукции Продукции

Модель интеллектуального агента

наличие у агента целей + + + + +

прогнозирование действий + + НЕТ НЕТ +

анализ и планирование действий + + + + +

модель самообучения агентов + + + НЕТ +

технология реализации компонент планирования, прогнозирования, обучения ЭС на основе разрешающих диаграмм Системно-динамическое ИМ ЭС ЭС НЕТ Фреймовая ЭС

язык обмена сообщениями ТРА / Сигналы ТРА ТРА Сигналы Сигналы

модель кооперации агентов + + + + +

Программная реализация модели Тестовая реализация Прототип MAC Прототип MAC ИМВИА НЕТ Тестовая реализация РДО-имитатор Коммерческая реализация ВРвШ!

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

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

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

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

Реализация предложенного алгоритма анализа и синтеза модели осуществлялась с помощью технологии ИА продуктов семейства BPsim. Рассмотрим описание концептуальной модели предметной области агента:

MIA=< Wizard, User, MPPR, ExpertModel, Exp, ExpOut, Analysis, Synthesis, SynthesisOut >,

где Wizard - множество визардов (ИА), разработанных пользователями; User - множество пользователей; MPPR - множество элементов модели МППР; ExpertModel - множество элементов экс-

Средняя очередь

заявок к операции Q0p ср

Средняя загруженность операции U0p ср

Простой Простой

операции из-за операции из-за

отсутствия отсутствия

средств РмесИОр ресурсов Рцеюр

Средняя загруженность средства UMech с,

Операторы синтеза

Удаление

---1 ) параллельной

операции

Удаление 2 ) средства из модели

Уменьшение количества сродства

Увеличение

4 ) количества г" средства

Добавление

5 ) параллельной операции

Увеличение количества ресурса

Увеличение

4 ) количества средства

Добавление

5 ) параллельной операции

Рис. 2. Граф поиска решений применения операторов синтеза, реализуемый в интеллектуальном агенте

пертной модели; Exp - множество экспериментов с моделью МППР; ExpOut - множество элементов результата эксперимента; Analysis - множество правил анализа моделей; Synthesis - множество правил синтеза моделей; SynthesisOut - множество элементов результата синтеза.

Разработка структуры ИА анализа и синтеза осуществлялась в среде BPsim.MSS, поддерживающей построение DFD-диаграмм, диаграмм классов, диаграмм прецедентов и диаграмм последовательностей UML, а также настройку экранных форм пользовательского интерфейса.

Применение интеллектуальных агентов анализа и синтеза ОТС

Продукты линейки BPsim использовались в ходе работе над проектом по анализу БП и разработке технического задания (ТЗ) на единую информационную систему (ЕИС) вуза УГТУ-УПИ. Вуз относится к предприятиям, имеющим сложную организационную структуру (факультеты, кафедры, филиалы и представительства), следовательно, успех автоматизации бизнес-процессов вуза зависит от качества их обследования и полного представления модели предприятия. Обследование БП выявило неоптимальность выполнения некоторых процессов УГТУ-УПИ, в частности, «Движение контингента». Кратко рассмотрим этот процесс [8].

В системе динамического моделирования ситуаций (СДМС) BPsim.MAS была построена ИМ процесса движения контингента «как было» (рис. 3). Данные для модели были получены в результате опроса сотрудников личного стола студентов (ЛСС), отдела автоматизированных систем управления (АСУ) и четырех деканатов. Узлы модели представляют собой этапы обработки документов. Узлы 1-10 моделируют обработку документа на факультетах, узлы 11-14 - обработку в ЛСС накопившихся за неделю документов, подготовленных факультетами. Использование ИА анализа и синтеза позволило установить ряд проблем. Рассмотрим их подробнее.

1. ИА анализа и синтеза выявил в ИМ наличие двух видов идентичных заявок. Аналитик установил, что сотрудники деканата формировали в разное время два схожих по содержанию документа -заявление и выписку в приказ. Рекомендация -привести их к единому виду.

2. ИА анализа и синтеза диагностировал нали-

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

3. Аналитик установил участие в рассматриваемом БП сотрудников отдела АСУ, которые выполняют проводки приказа в базе данных. Рекомендация - автоматизация процесса, внесение изменений в базу данных только сотрудниками, ответственными за информацию и устранение несвойственной функции отдела АСУ.

В результате анализа и синтеза были предложены следующие изменения процесса «Движение контингента»:

1) во время написания заявления студентом сотрудник деканата создает его электронный аналог в единой БД (разделение ресурсов в модели);

2) предлагается отказаться от формирования выписки в приказ, вся необходимая информация для издания приказа заносится в единую БД, следовательно, сбор виз будет проводиться один раз (сокращение видов заявок, результат автоматизации БП);

3) сотрудники ЛСС будут работать с электронной формой заявления и смогут сами его корректировать, т. е. не будет теряться время на отправление документов в деканат для переоформления (разделение ресурсов в модели между участниками - с точки зрения имитационной модели это соответствует увеличению количества ресурса);

4) появится возможность формировать и хранить дела студентов в электронном виде (история по студенту) (новое качество БП, появившееся в результате автоматизации);

5) у проректора будет подписываться только заявление (для некоторых видов заявлений достаточно визы декана) и приказ по УГТУ-УПИ (сокращение видов документов (заявок), сокращение нагрузки за счет устранения лишних операций в БП, связанных с петлями обратной связи);

6) в информационной системе можно будет отслеживать маршрут и стадии прохождения документов по процессу (новое качество БП, появившееся в результате автоматизации);

14 Рассылка выписок из приказа

Рис. 3. Модель процесса «Движение контингента»

7) у сотрудников отдела АСУ исчезнет не свойственная им функция - выполнение проводок приказа в базе данных (перераспределение функций и ответственности в результате автоматизации);

8) в случае списочного приказа, соответствующие информационные объекты в информационной системе формирует сотрудник деканата, в дальнейшем с ними работает сотрудник ЛСС (сокращение видов заявок, результат автоматизации БП).

В результате, в модели «как будет» процесса «Движение контингента» исчезли узлы с номерами 7, 9, 10, 15 (рис. 3). Описание нового БП легло в основу ТЗ на разработку модуля «Движение контингента» ЕИС. Также в ТЗ использовались диаграммы из продукта BPsim.SD (CASE-средства). После разработки и полугодовой эксплуатации была проведена оценка эффективности внедрения

модуля «Движение контингента» ЕИС на основе имеющейся ИМ процесса движения контингента «как было» и «как будет».

Обобщенные результаты экспериментов приведены в табл. 2.

Таким образом, благодаря автоматизации процесса «Движение контингента» производительность сотрудников деканата повысилась на 25 %, а производительность сотрудников ЛСС -на 229 % (более чем в три раза). Экономический эффект от внедрения моделей «как будет» и автоматизации процесса «Движение контингента» составляет 1 027 тыс. руб. в год.

В ходе работы были рассмотрены следующие модели СДМС: Д.Ю. Бугайченко, А.В. Масло-боева, ИМВИА, GAIA, РДО, МППР. Для проведения сравнительного анализа моделей были выбраны следующие представления систем: модель

Таблица 2

Оценка внедрения модуля «Движение контингента»

Показатели Модель «как было» Модель «как будет»

Количество обрабатываемых документов за месяц, шт. 390 1264

Количество потерянных документов за месяц, шт. 12 0

Производительность труда сотрудников деканата, документ/ч 0,4 0,5

Производительность труда сотрудников ЛСС, документ/ч 2,4 7,9

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

Разрабатываемые в рамках программных продуктов BPsim ИА анализа и синтеза МППР предназначены для автоматизации работы аналитика

СПИСОКЛ

1. Андрейчиков, А.В. Интеллектуальные информационные системы [Текст]/А.В. Андрейчиков, О.Н. Андрейчикова.-М.: Финансы и статистика, 2006.-424 с.

2. Wooldridge, M. The Gaia Methodology for Agent-Oriented Analysis and Design [Текст]/М. Wooldridge, N. Jennings, D. Kinny//Journal of Autonomous Agents and Multi-Agent Systems 3.-2000.-P. 285-312.

3. Бугайченко, Д.Ю. Абстрактная архитектура интеллектуального агента и методы ее реализации [Текст]/Д.Ю. Бугайченко, И.П. Соловьев//Системное программирование.-2005.-№1.-С. 36-67.

4. Маслобоев, А.В. Гибридная архитектура интеллектуального агента с имитационным аппаратом [Текст]/А.В. Маслобоев//Вестник МГТУ-2009.-№1. -Т.12.-Вып.1.-Мурманск: МГТУ, 2009.-C. 113-124.

5. Рыбина, Г.В. Моделирование процессов взаи-

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

Работа выполнена в рамках государственного контракта 02.740.11.0512.

модействия интеллектуальных агентов в многоагент-ных системах [Текст]/Г.В. Рыбина, С.С. Паронджанов// Искусственный интеллект и принятие решений. -2008. -№ 3. -С. 3-15.

6. Емельянов, В.В. Введение в интеллектуальное имитационное моделирование сложных дискретных систем и процессов. Язык РДО [Текст]/В.В. Емельянов, С.И. Ясиновский.-М.: АНВИК, 1998.-427 с.

7. Аксенов, К.А. Динамическое моделирование мультиагентных процессов преобразования ресурсов [Текст]/К.А. Аксенов, Н.В. Гончарова-Екатеринбург: ГОУ ВПО УГТУ-УПИ, 2006.-311 с.

8. Результаты обследования и формирования требований на создание единой ИС поддержки учебного процесса (с 15. 05. 2005 по 14. 02. 2006): Отчет по проекту № *01200601073/Г0У ВПО «УГТУ-УПИ» [Текст]/ Руко-вод. работы А.К. Аксенов. -Екатеринбург -2006.-119 с.

УДК 004.855.5

П.В. Трифонов

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

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