Содержание к диссертации
Введение
ГЛАВА 1. Проблемы конструирования информационных систем учётно-финансового профиля 15
1.1. Определение системы учётно-финансового профиля 15
1.2. Анализ жизненного цикла информационных систем учётно-финансового профиля 17
1.3. Анализ современных технологий и средств разработки прикладных информационных систем 22
1.3.1. Базовые технологии разработки программного обеспечения 22
1.3.2. Современные средства разработки программного обеспечения 25
1.4. Методы агентно-ориентированного программирования 29
1.4.1. Определения и терминология 29
1.4.2. Примеры прикладных агентных систем 35
1.5. Использование мультиагентных систем для разработки и сопровождения прикладного программного обеспечения 37
1.6. Цель и задачи исследования 39
1.7. Основные результаты и выводы по главе 40
ГЛАВА 2. Парадигма агенто-ориентированного конструирования прикладного программного обеспечения 42
2.1. Объектная модель среды конструирования 42
2.2. Обобщённая модель агента — элемента конструирования 50
2.3. Функциональная модель агентной среды конструирования 55
2.4. Реализация интеллектуальной составляющей агента 60
2.4.1. Описание конструкторской МАС в виде фреймовой сети 60
2.4.2. Описание MAC с помощью интенсиональных отношений 64
2.4.3. Машина вывода агентской конструкторской среды 67
2.4.4. Обучение интеллектуальных агентов на примерах 70
2.5. Организация межагентных взаимодействий 72
2.5.1. Язык взаимодействия агентов системы 73
2.5.2. Подсистема общения 78
2.6. Организация человеко-машинного взаимодействия 82
2.7. Основные результаты и выводы по главе 84
ГЛАВА 3. Алгоритмическое обеспечение агентской конструкторской среды 86
3.1. Алгоритм построения графа прецедента 86
3.2. Алгоритм сортировки графов по критерию максимального изоморфного пересечения 89
3.2.1. Характеристика задач поиска изоморфизма 89
3.2.2. Алгоритм Макгрэгора для поиска максимального изоморфного пересечения 92
3.2.3. Алгоритм Дюранда-Пасари для поиска максимального изоморфного пересечения 94
3.2.4. Сравнение производительности алгоритмов поиска максимального изоморфного пересечения на графах с различными параметрами 96
3.2.5. Реализация алгоритма поиска максимального изоморфного пересечения для сортировки прецедентов 100
3.3. Анализ функционирования подсистемы общения конструкторской мультиагентной системы 103
3.4. Основные выводы по главе 106
ГЛАВА 4. Программно-инструментальный комплекс конструирования прикладных информационных систем .108
4.1. Выбор базовых средств разработки инструментальной системы конструирования 108
4.2. Программные средства инструментальной системы конструирования прикладного программного обеспечения «UnivControls» 112
4.2.1. Состав и структура программного обеспечения инструментальной системы конструирования 112
4.2.2. Функции интерфейса среды конструирования 116
4.2.3. Особенности реализации основных компонентов инструментальной конструкторской системы «Univ-Controls» 123
4.3. Использование конструкторской среды «Univ-Controls» для разработки и сопровождения «АРМ Автотранспорт и механизмы» 125
4.3.1. Постановка задачи 125
4.3.2. Разработка «АРМ Автотранспорт и механизмы» 127
4.3.3. Внедрение «АРМ Автотранспорт и механизмы» 128
4.3.4. Сопровождение «АРМ Автотранспорт и механизмы» 129
4.4. Выводы по главе 129
Заключение 131
Список использованных источников 133
- Анализ современных технологий и средств разработки прикладных информационных систем
- Функциональная модель агентной среды конструирования
- Алгоритм сортировки графов по критерию максимального изоморфного пересечения
- Анализ функционирования подсистемы общения конструкторской мультиагентной системы
Введение к работе
В настоящее время компьютеризации подвергается всё больше сфер человеческой деятельности. Связанная с этим повышенная потребность в прикладном программном обеспечении (ПГТО) не может удовлетворяться старыми методами разработки информационных систем [42,99].
Большинство современных технологий автоматизации процесса конструирования прикладных программ являются итерационными [74]. На различных этапах создания ПГТО заняты специалисты из разных профессиональных областей (программисты, системные аналитики, специалисты в конкретной предметной области, конечные пользователи). При этом непосредственно внесение изменений в систему возможно только на этапе конструирования специалистами в области программирования. Все же другие участники процесса разработки ППО могут влиять на изменения системы только опосредованно.
Таким образом, любое изменение системы обязательно влечёт за собой прохождение всех итераций процесса разработки. К тому же, вследствие автономности отдельных этапов разработки и внедрения программного продукта, терминологические и понятийные различия специалистов различных прикладных областей зачастую приводят к неправильному пониманию требований как к отдельным элементам ПО, так и системы в целом, что приводит к новому итерационному повторению всех этапов модификации системы.
Таким образом, разработка конечного продукта затягивается, а полученные результаты обычно не в полной мере удовлетворяют требованиям заказчика. [42,26]
Кроме того, вследствие меняющихся социально-экономических и производственных условий, а также изменения требований и представлений конечных пользователей о возможностях имеющихся средств и своих потребностях, возникает проблема адаптации и развития уже готовых систем,
что в рамках традиционных технологий также требует итерационного взаимодействия (см. рис. 1.1). Особенно остро эта проблема стоит в области сопровождения ППО учётно-финансового профиля, где частые изменения в налоговой, экономической и социальной сферах приводят к частым переделкам системы.
Таким образом, в течение процесса разработки и функционирования программный продукт практически не может быть "отчужден" от специалистов по программированию и требует постоянного сопровождения на протяжении всего жизненного цикла.
В силу перечисленных причин современный рынок разработки ППО испытывает значительный недостаток квалифицированных программистов-разработчиков информационных систем. Притом, что количество программистов быстро растёт за счёт притока специалистов из смежных областей производства, западные фирмы прибегают к технологии оффшорного программирования [60], вовлекая в процесс разработки всё большее количество специалистов из других стран.
Разнообразные подходы, связанные с универсализацией программного обеспечения или генерацией программного кода, призванные смягчить остроту данной проблемы, хотя и ускоряют различные этапы проектирования, конструирования или сопровождения программного продукта, но не исключают итерационности всего процесса, а также не разрешают коренное противоречие традиционной технологии разработки ППО - отстраненность конечного пользователя от ряда этапов жизненного цикла прикладных систем обработки данных.
Сложившаяся ситуация заставляет искать новые подходы и методы, позволяющие в сжатые сроки создавать функционально-полные системы с развитым пользовательским интерфейсом, а также эффективные технологии модернизации и сопровождения уже готового программного обеспечения.
Цель и содержание поставленных задач.
В рамках данной работы предлагается объединить среду конструирования и сопровождения ППО и экспертные знания о процессе разработки информационных систем в рамках единой интеллектуальной конструкторской среды разработки ППО учётно-финансового профиля.
Целью диссертационной работы является разработка алгоритмического и программного обеспечения интеллектуального инструментального комплекса разработки ППО учётно-финансового профиля.
Для достижения поставленной цели необходимо решить следующие задачи:
Исследование процессов конструирования и сопровождения ППО, а также современных средств автоматизации этих процессов, и постановка задачи разработки инструментальной среды конструирования и сопровождения ИС.
Разработка парадигмы конструирования ППО на базе интеллектуальных агентов. Разработка объектной и агентной модели среды конструирования. Описание принципов организации и механизмов взаимодействия базовых конструкторских элементов. Описание средств накопления хранения и манипулирования знаниями, интеллектуальными агентами.
Разработка алгоритмов, моделей и методов, необходимых для функционирования интеллектуальной конструкторской среды (ИСК) разработки ППО. Исследование корректности и эффективности функционирования разработанных алгоритмов.
Разработка программно-инструментального комплекса реализующего предложенную парадигму конструирования ППО. Решение этой задачи подразумевает выбор базовой среды разработки, создание средств и конструкторских элементов, необходимых для конструирования и сопровождения ИС учётно-финансового профиля.
5. Апробация разработанного инструментального комплекса при конструировании прикладной информационной системы. Анализ эффективности применения разработанной ИСК.
Методы исследования
В работе использованы методы системного анализа, математического моделирования, теории графов, комбинаторного анализа, искусственного интеллекта, теории мультиагентных систем (MAC).
При разработке программного обеспечения использованы методы системного и прикладного программирования, объектно-ориентированного программирования, технологии интранет и клиент-сервер, а также современные технологии хранения и манипуляции данными.
Научную новизну полученных в работе результатов определяют:
Новая хмультиагентная парадигма конструирования ППО.
Функциональная, объектная и агентная модели среды конструирования ППО.
Обобщённая модель агента - конструкторского элемента, включающая алгоритмы и принципы построения основных интеллектуальных составляющих агента.
Результаты сравнения эффективности основных алгоритмов поиска максимального изоморфного пересечения графов с различными параметрами, используемые при создании алгоритма сортировки прецедентов.
Принципы и требования к организации межагентного взаимодействия в конструкторской системе и оптимальные параметры обслуживания заявок подсистемой межагентного взаимодействия.
Результаты исследования эффективности функционирования инструментальной среды конструирования, реализующей предлагаемую агентно-ориентированную парадигму на примере разработки прикладной ИС УФП.
Практическая ценность работы заключается в следующем: Разработана интеллектуальная среда конструирования прикладного программного обеспечения «Univ-Controls», реализованная на базе пакета
Visual Studio .NET и функционирующая под управлением ОС Windows2000, позволяющая эффективно разрабатывать и сопровождать функционально-полные информационные Интернет/Интранет системы учётно-финансового профиля. Объём созданного оригинального исходного кода на языке С# составляет более 9000 строк.
Реализован также необходимый и достаточный набор интеллектуальных элементов конструирования (программных агентов), обладающих высокой степенью автономности и адаптивным* поведением, готовых к применению при разработке широкого круга информационных систем.
Разработанная мультиагентная конструкторская среда «Univ-Controls» внедрена в лаборатории ОСУ КЦ ТПУ и используется в ряде разработок лаборатории при создании информационных систем учётно-финансового профиля. Созданная с помощью данной конструкторской среды при личном участии автора информационная система «АРМ Автотранспорт и механизмы» внедрена на предприятии ОАО «Сибмост». Результаты внедрения подтверждены соответствующими актами.
На защиту выносятся следующие тезисы:
Разработанная автором агентная парадигма конструирования позволяет повысить эффективность процесса создания и сопровождения ППО учётно-финансового профиля по сравнению с существующими технологиями.
Предложенный механизм самообучения агентов на основе использования прецедентов обеспечивает накопление и повторное использование знаний разработчиков.
Выбранные параметры функционирования подсистемы межагентского взаимодействия обеспечивают корректную и эффективную работу мультиагентной среды конструирования.
Созданные алгоритмические и программные средства интеллектуальной системы конструирования ППО «Univ-Controls», базирующиеся на агентной парадигме конструирования, позволяют создавать и сопровождать, функционально-полные ИС учётно-финансового профиля.
Апробация результатов работы:
Разработанная конструкторская среда была внедрена в лаборатории ОСУ КЦ ТПУ и используется для разработки информационных систем учётно-финансового профиля. Созданные программные средства были использованы при разработке «АРМ Автотранспорт и механизмы». Результаты были внедрены в ОАО «Сибмост». Результаты внедрений подтверждены соответствующими актами.
Публикации:
Основные результаты работы были представлены в виде докладов на
следующих конференциях: Международный научный семинар
«Инновационные технологии - 2001» (г. Красноярск, 2001 г.), Международный
заочный симпозиум молодых ученых, студентов и специалистов
«Интеллектуальные процессы, модели и системы получения информации.
Информационный менеджмент и маркетинг» (г. Пенза, 2001 г.), Пятый научно-
практический семинар «Новые информационные технологии» (г. Москва, 2002
г.), Международный научный симпозиум «KORUS-98» (г. Томск, 1998 г.),
Международный научный симпозиум «KORUS-2001» (г. Томск, 1998 г.).
Результаты работы также опубликованы в сборниках «Кибернетика и вуз»
(№29, 30), Всероссийская научно-практическая конференция
«Информационные технологии и математическое моделирование» (г.Анджеро-Судженск, 2002 г.), 5-я Всероссийская научная конференция молодых ученых и аспирантов «Новые информационные технологии. Разработка и аспекты применения» (г. Таганрог, 2002 г.), 8-я Республиканская дистанционная открытая научная конференция «Современные проблемы информатизации» (г. Воронеж, 2003 г.), 9-я Международная научно-практическая конференция молодых учёных «Современная техника и технологии 2003» (г. Томск, 2003 г.).
Всего по теме диссертации опубликовано 12 работ, из них 8 статей и 4 тезиса.
Личный вклад автора:
Мультиагентная парадигма конструирования ППО, модели и алгоритмы функционирования её основных частей разработаны лично автором.
Программная реализация инструментальной системы конструирования ППО выполнялась на базе лаборатории ОСУ КЦ ТПУ лично автором.
Анализ процесса разработки внедрения и сопровождения ППО учётно-финансового профиля проводился совместно с Ю.Г.Авдошиным.
Формализация среды конструирования и выделение перечня необходимых конструкторских элементов осуществлялись совместно с Ю.Г.Авдошиным, Э.Г.Клейбортом и В.И.Михалевым.
Разработка и внедрение информационной системы «АРМ Автотранспорт и механизмы» в ОАО «СибМост» проведены автором в составе Лаборатории ОСУ КЦ ТПУ совместно с В.Н.Сороковиковым и Р.И.Наурузовым.
Структура диссертации:
Во введении обосновывается актуальность диссертационного исследования, формулируются основные цели и задачи работы, её основные положения, научная новизна и практическая ценность, перечисляются выносимые на защиту тезисы.
Первая глава посвящена описанию проблемной ситуации и постановке проблемы исследования. Рассматривается процесс разработки, сопровождения и модернизации прикладного программного обеспечения (ППО). Раскрываются особенности разработки и функционирования информационных систем учётно-финансового профиля (УФП). Приводится обобщённая схема жизненного цикла ППО УФП и описывается проблема сокращения его итерационности.
Анализируются современные системы и средства разработки приложений в разрезе их конструкторской составляющей. Рассматриваются существующие на сегодняшний день технологии призванные облегчить разработку программного обеспечения. Обозначаются основные недостатки традиционных подходов к разработке и сопровождению ППО УФП не позволяющие сократить итерационность жизненного цикла ППО.
Формулируются необходимые определения и положения агентно-ориентированного программирования. Приводится классификация агентов разработанная в соответствии с их основными свойствами. Определяется место разрабатываемой мультиагентной конструкторской системы в приведённой классификации. Описывается современное состояние развития агентной методологии, на основе обзора существующих агентных систем.
Исследуются перспективы применения агентно-ориентированного подхода для интеллектуализации конструирования ППО. Описывается изменение жизненного цикла ППО и его отдельных этапов в связи с его применением.
На основе анализа проблемной ситуации и современных средств конструирования и сопровождения ППО, а также на основе рассмотрения методологии создания мультиагентных систем, сформулированы цель и задачи исследований в диссертационной работе.
Во второй главе описывается предлагаемая парадигма конструирования ППО основанная на использовании адаптивных агентных моделей.
Приводятся основные требования к инструментальным средствам конструкторской системы. Предлагается объектная модель среды конструирования, состоящая из небольшого количества универсальных конструкторских элементов покрывающих все потребности разработчика при конструировании ППО УФП. Приводится гибридная объектно-агентная иерархия элементов конструирования.
Предлагается обобщённая модель интеллектуального агента-элемента конструирования. Описывается структура и принципы функционирования его основных компонентов.
Формулируются принципы реализации интеллектуальной составляющей агента. Приводится описание мультиагентной среды конструирования с точки зрения теории фреймов и архитектуры BDI. Описывается процесс вывода на знаниях. Рассмотрен процесс обучения агентов на основе прецедентов их использования в конструкторской системе.
Разрабатывается функциональная модель мультиагентной среды конструирования. Описываются основные виды агентов конструкторской системы их иерархические и онтологические взаимосвязи. Рассматриваются процессы совместного функционирования агентов при конструировании экранного документа.
Описывается структура и принципы функционирования подсистемы общения агентов. Описывается структура фраз и перечень лексем языка межагентного взаимодействия, базирующихся на языке KQML. Рассматривается процесс обработки запроса в подсистеме межагентного взаимодействия агента. Рассматриваются возможные проблемы общения агентов в мультиагентной системе и предлагаются способы их преодоления.
Описываются принципы и средства взаимодействия агентов с пользователем. Вырабатываются основные требования к организации человеко-машинного взаимодействия в конструкторской MAC.
Отражаются основные интеллектообразующие механизмы среды конструирования. Структура представления и манипулирования знаниями в системе.
Третья глава посвящена разработке алгоритмического обеспечения ИСК ГШО и анализу корректности и эффективности функционирования основных компонентов MAC.
Вводится понятие прецедента использования агента. Предлагается алгоритм формализации состояния агентной среды в виде графа - прецедента.
Рассматривается проблема поиска похожих прецедентов, описываются и анализируются пути её решения. Близость прецедентов предлагается определять по величине максимального изоморфного пересечения их графов (МИПГ).
Даётся характеристика задачам поиска МИПГ и описываются основные алгоритмы решения этой задачи. Приводятся результаты исследования производительности алгоритмов на графах с различными параметрами. На основе сопоставления и экспериментального исследования существующих
алгоритмов поиска МИПГ осуществляется выбор оптимального, для условий решаемой задачи, алгоритма. Описывается реализация алгоритма поиска максимального изоморфного пересечения для сортировки прецедентов.
Приводятся результаты моделирования работы подсистемы общения конструкторской MAC при выполнении наиболее характерных задач конструирования. Определяются и экспериментально проверяются параметры обработки запросов подсистемы общения агентов. Показывается устойчивость функционирования подсистемы общения на реальных и модельных данных.
В четвёртой главе описывается программная реализация ИСК ППО и анализируется её функционирование.
На основе результатов проведенного анализа существующих средств разработки программного обеспечения, обосновывается выбор базовой среды конструирования, а также средств управления базами данных, клиентского и серверного программного обеспечения.
Описываются состав и структура программного обеспечения ИСК «Univ-Controls», оцениваются требования программного обеспечения к аппаратным* ресурсам клиентских рабочих станций и сервера.
Приводится описание диалоговых функций интерфейса мультиагентной среды конструирования «Univ-Controls». Описываются принципы функционирования и особенности реализации агентской конструкторской системы на базе среды конструирования Visual Studio.Net.
Приводятся результаты использования ИСК ППО «Univ-Controls» для создания информационной системы «АРМ Автотранспорт и механизмы». Описываются процессы внедрения и сопровождения информационной системы на предприятии ОАО «Сибмост» с использованием «Univ-Controls».
По результатам внедрения и эксплуатации разработанной прикладной информационной системы делаются выводы об эффективности предложенных алгоритмов и парадигмы конструирования, а также об их влиянии на жизненный цикл информационной системы учётно-финансового профиля.
Анализ современных технологий и средств разработки прикладных информационных систем
Существуют разнообразные подходы, призванные смягчить остроту описанной выше проблемной ситуации. Один из основных, и наиболее распространённых в настоящее время, подходов нацелен на автоматизацию конструирования и связан с автоматической генерацией программного кода [90,14]. К этому подходу относятся как системы визуального проектирования и генерации ПО (такие как ErWin [40] или PowerBuilder [63]), так и среды визуального конструирования (Delphi [55], MS Visual Studio [58]).
Основным направлением развития этого подхода является повторное использование кода. Первым шагом в этом направлении, несомненно, была технология процедурного программирования [12], предлагающая разделять текст программы на функционально-завершенные параметризированные блоки с унифицированным механизмом вызова и передачи параметров. Технология процедурного программирования позволила рассматривать процедуры как чёрный ящик, требующий подачи на вход некоторых данных и производящий на выходе некоторые заранее известные действия. Она и заложила базу для появления последующих технологий автоматизации конструирования. Появление технологии процедурного программирования открыло дорогу разработке крупных информационных систем, создание которых до этого было исключительно трудоёмким процессом.
Следующим шагом в развитии технологии разработки ПО была объектно-ориентированная технология программирования [62, 70]. В отличие от процедурной технологии она позволила совместить в рамках одного программного модуля данные и процедуры их обработки, увеличив тем самым самодостаточность отдельных программных компонентов. Теперь разработчику не нужно было заботиться о логике взаимодействия программы и данных, так как она была уже реализована в теле объекта. Объект можно представить в виде формулы: где D0 - данные, принадлежащие объекту, Р0 — процедуры их обработки.
Появление объектной технологии значительно облегчило повторное использование кода и позволило привлекать к процессу разработки ПО большое число разработчиков. Однако в процессе разработки функционально -наполненного ППО количество разрабатываемых конструкторских элементов растёт достаточно быстро. Возникает ситуация, когда программисту тяжело изучить особенности использования всех, уже созданных, конструкторских элементов. Тем более, что документация не всегда безупречна. Брукс в своей книге «Мифический человеко-месяц» [13] указывает на объём документации как на теоретический барьер на пути создания сложных программных систем.
Большим шагом в сторону совершенствования конструирования ПО было создание средств визуального конструирования [68, 28], называемых также WYSIWYG. Объектно-ориентированная парадигма дополнилась средствами визуального отображения и модификации на этапе конструирования как самого объекта, так и принадлежащих ему данных. Таким образом, визуальный конструкторский элемент может быть представлен формулой: где Do - данные принадлежащие объекту, Ро - процедуры их обработки, СЕ - средства конструирования, О — базовый объект.
Типичными представителями этой технологии являются объекты ActiveX [27], OpenDoc [82], Java Beans [19]. С точки зрения традиционной технологии, рассмотренный подход автоматизирует этап кодирования, позволяя лишь в более сжатые сроки предлагать конечному пользователю варианты решения его постановки задачи. Но не сокращает итерационность всего процесса разработки ППО. Большинство инструментальных средств, создаваемых на основе таких подходов, функционируют как генераторы программного кода, не уделяя должного внимания проблемам интеллектуального конструирования систем, а также вопросам корректировки, настройки и адаптации программного обеспечения непосредственно на этапе его эксплуатации.
Вторым подходом к решению проблем традиционной технологии является предоставление конечному пользователю инструментальных средств для настройки и адаптации ПО к изменяющимся условиям в ходе решения конкретных задач. При этом пользователю предлагается спектр средств, с помощью которых он может самостоятельно (без привлечения программистов) изменить интерфейс ПО в рамках гибкости, заложенной разработчиками системы. Этот подход способен до некоторой степени уменьшить количество итераций традиционной технологии. Однако пропорционально - гибкости, закладываемой в разрабатываемое ПО, возрастает и трудоёмкость его конструирования. Таким образом, в этом случае всегда приходится находить баланс между предоставляемой пользователю гибкостью ППО и сложностью конструирования такого ПО
Функциональная модель агентной среды конструирования
В соответствии с определением парадигмы, кроме структуры отдельного агента, необходимо также описать иерархию и способы взаимодействия агентов в рамках системы в целом.
Функциональная иерархия применяемых в конструкторской системе агентов представлена на рисунке 2.6.
Как уже говорилось в предыдущих главах, функционирующие в рамках среды разработки, агенты делятся на следующие виды: агенты менеджеры, сервисные агенты, контейнеры, элементы конструирования (контролы), и функциональные агенты. Рассмотрим подробнее функциональное назначение и процесс работы агентов каждого из этих видов. Агент Контрол - представляет собой основной строительный блок предлагаемой среды конструирования. С помощью трёх представителей этого вида агентов (ValueAgent, ControlAgent, GridAgent) реализуется всё многообразие содержания экранных документов. Агенты этого вида являются визуальными как на этапе конструирования, так и на этапе выполнения. Функциональный агент - является-визуальным только на этапе конструирования, однако представлены как на этапе конструирования, так и на этапе выполнения. Единственный представитель этого вида DataSource Agent выступает в роли источника данных для других агентов. Агенты менеджеры - представлены исключительно на этапе конструирования. На этот вид агентов возложены координирующие функции в рамках всего приложения, в рамках профиля пользователя, в рамках текущего экранного документа. Соответственно существует три представителя этого типа агентов: ApplicationAgent, User Agent, Page Agent. Первые два условно относятся к агентам топ-менеджерам, ибо они функционируют в рамках конструкторской системы в целом, не привязываясь к конкретному экранному документу, хотя и добавляются на страницу подобно другим конструкторским элементам. Агенты топ-менеджеры обладают знаниями об относящихся к данному проекту базах данных используемой в проекте антологии, правах предоставленных текущему пользователю и пр. PageAgent - осуществляет непосредственно координацию и мониторинг текущих действий пользователя и является разным для каждого экранного документа. Кроме прочего, на PageAgent возлагается ведение протокола модификаций системы, и некоторая оптимизация конструируемого экранного документа (отслеживание дубликатов агентов, контроль версий и пр.). Агент контейнер - сочетает в себе как свойства агента контрола так и некоторые возможности агента менеджера. Этот вид агента, в зависимости от выбранных настроек, может быть не представлен на этапе функционирования. Единственный представитель этого вида агентов ContainerAgent отображается в виде прямоугольной рамки и позволяет группировать несколько агентов-контролов, сервисных агентов и функциональных агентов в самостоятельную структуру. Может перекрывать для вложенных агентов присутствующего на странице PageAgent или, наоборот, делегировать ему свои полномочия. Сервисный агент — представлен исключительно на этапе конструирования. Содержит данные и процедуры, необходимые для автоматизации этапа конструирования. К этому типу агентов относятся StyleAgent, содержащий знания и процедуры для контроля и изменения оформления визуальных агентов в соответствии с принятыми для приложения стандартами внешнего вида. И SafeAgent - отвечающий за своевременное сохранение экранного документа, авторизацию пользователя и отслеживающий ситуации, способные привести к потере данных.
Следует отметить, что наличие какого-либо типа агентов при разработке экранного документа опционально. Так, любой агент-контрол способен функционировать самостоятельно, без агентов менеджеров или сервисных агентов, наличие которых лишь облегчает его использование. Это свойство агентов позволяет использовать их для модернизации готовых систем, создававшихся обычным способом. В этом случае обычные объекты, используемые в рамках экранного документа, сопрягаются не с самим агентом, а с его базовым объектом.
Опишем взаимосвязи, возникающие в агентной системе, в которой представлены все виды агентов.
Если на странице нет агентов менеджеров, система предлагает их добавить и запомнить по аналогии с имевшими место прецедентами или новым способом
Алгоритм сортировки графов по критерию максимального изоморфного пересечения
Как сказано в предыдущих главах, обучение агента ведётся с использованием механизма обработки прецедентов. Прецедентом, в рамках данной работы, называется совокупность состояний самого агента и окружающей его среды. Состояние окружающей среды описывается в виде обыкновенного помеченного на вершинах графа, в узлах которого находятся агенты среды, а рёбрами отражается наличие между ними явной связи, (подробнее процедура формирования графа описана в главе 3.1). Прецедент использования агента считается легитимным и заносится в базу знаний только в случае успешного, подтверждённого пользователем применения агента. В дальнейшем при применении агента в новом экранном документе пользователю может быть предложен перечень успешных прецедентов использования данного агента в сходных условиях выбрав из которых, пользователь может инициировать процесс автоматического конструирования экранного документа на базе сохранённого в базе знаний прецедента.
Для реализации перечисленных функций интеллектуальной конструкторской системы необходимо создать специализированную процедуру определения близости графов прецедентов и отображения соответствующих вершин одного графа в другой. Для этой цели на базе алгоритма нахождения максимального изоморфного пересечения графов (МИПГ) [43] был разработан специализированный алгоритм сортировки обыкновенных, помеченных на вершинах графов по критерию МИПГ с графом - эталоном. Для прояснения математических методов, лежащих в основе описываемого алгоритма, рассмотрим задачу распознавания изоморфизма графов (РИГ) в неориентированных графах, как наиболее общую задачу данного типа, решаемую на графах. Два графа называются изоморфными, если один из них можно отобразить в другой с точностью до перенумерации узлов, т.е. для двух изоморфных графов GI( I M) и G2(A2,.r2) должно существовать взаимно однозначное множества вершин соответствующих графов и he.Xl,Y2&X2 _ МН0Жества их рёбер. Для того, чтобы задача распознавания изоморфизма считалась решённой, необходимо указать изоморфную подстановку для вершин одного из графов или признать графы неизоморфными, (рис. 3.2) Задача РИГ является одной из основных комбинаторных задач теории графов. Хотя принадлежность этой задачи к классу NP-полных не доказана, до сих пор не известно точных способов её решения с полиномиальной сложностью, для произвольных графов [43]. Ещё одной задачей этого типа является задача распознавания изоморфного вложения одного графа в другой. Эта задача известна как классический пример NP-полной задачи. Чтобы решить задачу изоморфного вложения подграфа с использованием алгоритмов РИГ, необходимо разработать процедуру выделения в графе G, подмножества вершин Icl„ равномощного с множеством вершин Х2 графа G2. Данная процедура включает кх действий, где ҐР kx= l , 1=1 (, = 1 1. Следовательно, раз необходимо применить и алгоритм РИГ. Таким образом, в дополнение к этому необходимо выполнить к2
На настоящий момент наилучшие результаты при решении описанных задач показывают переборные алгоритмы, вычисляющие для каждой из вершин графа набор характеристик инвариантных относительно их изоморфизма. Например, выписывание в лексикографическом порядке степени вершины графа, степеней, связанных с ней вершин, степеней вершин, связанных с этими вершинами, и т.д., позволит, в конце концов, присвоить ей индивидуальный маркер и найти инвариантную ей вершину в изоморфном графе. Очевидно, что для большого количества графов можно найти все инварианты за гораздо меньшее количество шагов, чем 0(п!).
Наконец, третья классическая задача этого типа, задача поиска максимального изоморфного пересечения графов (МИПГ) (см. рисунок 3.3), в вычислительном аспекте значительно сложнее и задачи РИГ и задачи поиска изоморфного вложения. Эта задача, по существу, является задачей целочисленной оптимизации, на каждом шаге которой решаются задачи РИГ и ИВГ. К тому же использование в ней инвариантов сильно ограничено
Анализ функционирования подсистемы общения конструкторской мультиагентной системы
С целью проверки работоспособности агентной системы, необходимо исследовать не только функционирование отдельных её элементов и процессов, но и их взаимодействие во время конструирования экранных документов ИС.
Как уже говорилось в главе 2.5.2, основную интегрирующую роль в разрабатываемой системе играют межагентные взаимодействия, и в частности, подсистема общения. С целью анализа функционирования системы и выбора оптимальных параметров подсистемы общения было исследовано функционирование МАС на реальных и модельных данных. Для выявления влияния дисциплины обслуживания поступающих сообщений на параметры системы, эксперименты проводились по четырём дисциплинам обслуживания: FIFO, LIFO, случайная очерёдность, приоритетная очерёдность. В ходе экспериментов (рис. ЗЛО) было выявлено, что при использовании приоритетной дисциплины обработки сообщений требуется значительно меньшая длина очереди. Показатели приоритетов присваиваются сообщениям таким образом, чтобы первыми выполнялись сообщения, ведущие к сокращению количества обрабатываемых заявок (сообщения об ошибках и пр.). Затем сообщения, не требующие создания дополнительных запросов (оповещения и пр.). Сообщения на удаление агента. И самым низким приоритетом обладают запросы на выполнение каких-либо действий (полный перечень команд и соответствующих им приоритетов обслуживания приведён в гл.2.5). На рисунке 3.12 показано максимальное и среднее время ожидания заявок в стеке ожидающих сообщений. Из диаграммы видно, что наиболее оперативно обслуживаются заявки при использовании приоритетной дисциплины и дисциплины LIFO. Совместно с приоритетной дисциплиной обслуживания входящих сообщений применяется дисциплина LIFO, т.е. среди сообщений с одинаковым уровнем приоритета в первую очередь обрабатываются те, что поступили последними. Такая гибридная дисциплина обслуживания позволяет также минимизировать количество ожидающих сообщений.
Кроме системы приоритетов, необходимо подобрать соответствующий размер входных очередей агентов таким образом, чтобы в ситуациях, характерных для разрабатываемой системы, они не переполнялись слишком быстро.
Результаты экспериментов показывают, что при приоритетной дисциплине обслуживания сообщений максимальная длина очереди пропорциональна количеству участвующих в общении агентов. Из расчёта хмаксимальной длины очереди в наихудшем возможном случае, длина очереди принимается L=4 N, где N количество участвующих во взаимодействии агентов.
Определение хмаксимальной длины очереди необходимо также для определения зацикливания системы. Зацикливание может появиться в случае ошибки програхМхМирования агента, когда агент А посылает запрос агенту В, которому для ответа необходимо обратиться к агенту А, или если для выполнения более простого запроса требуется выполнить более сложный (более многошаговый). В первом случае выполнение неизбежно приведёт к переполнению стека ожидающих сообщений (рис.3.12), а во втором - к переполнению входной очереди. Чтобы достаточно быстро выявить такую ошибочную ситуацию, и необходимо определить лимит для очередей агента, превышение которых будет указывать на возникновение ошибки. 3.4. Основные выводы по главе 2 Введено понятие прецедента использования агента. Предложен алгоритм формализации состояния агентной среды в виде графа - прецедента. 3 Рассмотрена проблема поиска похожих прецедентов, описаны и проанализированы пути её решения. Близость прецедентов предложено определять по величине максимального изоморфного пересечения их графов (МИГТГ). 4 На основе сопоставления и экспериментального исследования существующих алгоритмов поиска МИПГ осуществлён выбор оптимального, для условий решаехМой задачи, алгоритма, им является алгоритм Макгрэгора. Рассмотрено влияние различных параметров поиска на скорость его функционирования. 5 Приведены результаты хмоделирования работы подсистехМЫ общения конструкторской МАС при выполнении наиболее характерных задач конструирования. Определены и экспериментально проверены параметры обработки запросов подсистемы общения агентов. Показана устойчивость функционирования подсистемы общения на реальных и модельных данных
Похожие диссертации на Интеллектуализация конструирования информационных систем на базе адаптивных агентных моделей
