Содержание к диссертации
Введение
Глава 1. Состояние проблемы 11
1.1. Основные принципы построения САПР 11
1.2. Поддержка жизненного цикла изделия 14
1.3. САПР и особенности современного производства 16
1.4. Анализ многоагентных систем в САПР 20
1.4.1. Понятие агента. Классификация агентов 20
1.4.2. Взаимодействие агентов. Понятие многоагентной системы 24
1.4.3. Применение многоагентных систем в задаче поиска информации в базах данных САПР 27
1.5. Применение средств Интеллектуального Анализа Данных (ИАД) в задачах поиска информации в САПР 32
1.6. Применение генетических алгоритмов в кластеризации 35
1.7. Краткие выводы 39
Глава 2. Исследование архитектур многоагентных систем поиска информации и алгоритмов кластеризации 41
2.1. Стандарты построения многоагентных систем 41
2.1.1. Модель многоагентной системы FIPA 41
2.1.2. Модель многоагентной системы OMG 48
2.2. Анализ систем поиска информации на основе многоагентных систем .. 54
2.2.1. Многоагентные системы поиска информации, основанные на мобильных агентах 54
2.2.2. Многоагентные системы поиска информации, основанные на статических агентах 57
2.3. Исследование современных алгоритмов кластеризации 60
2.4. Краткие выводы 66
Глава 3. Разработка подсистемы поиска информации в системе распределенных САПР на основе многоагентных систем 67
3.1. Построение алгебраической модели подсистемы поиска информации в системе распределенных САПР на основе многоагентных систем 67
3.2. Разработка алгоритма поиска информации в системе распределенных САПР 69
3.3. Структура подсистемы поиска информации в системе распределенных САПР 78
3.3.1. Агент регистрации 80
3.3.2. Каталог агентов и каталог служб 81
3.3.3. Агент онтологии 82
3.3.4. Координатор рабочих групп 83
3.3.5. Интерфейсный агент 84
3.3.6. Поисковый агент 85
3.3.7. Агент-координатор 86
3.3.8. Агент обработки результатов 87
3.4. Работа подсистемы поиска информации 90
3.5. Алгоритм поиска аналогов в базах данных САПР 97
3.6. Краткие выводы 124
Глава 4. Экспериментальные исследования 125
4.1. Разработка подсистемы поиска информации 125
4.1.1. Общие сведения о создании многоагентнои подсистемы поиска информации 125
4.1.2. Разработка подсистемы поиска информации 128
4.2. Общий анализ загруженности каналов передачи данных 130
4.3. Оценка надежности подсистемы поиска информации 132
4.3.1. Методика оценки надежности 132
4.3.2. Оценка надежности подсистемы поиска информации 138
4.4. Исследование основных параметров алгоритма кластеризации 145
4.5. Оценка качества алгоритма кластеризации 147
4.6. Краткие выводы 155
Заключение 157
Литература 159
Приложения 172
- Поддержка жизненного цикла изделия
- Анализ систем поиска информации на основе многоагентных систем
- Разработка алгоритма поиска информации в системе распределенных САПР
- Общий анализ загруженности каналов передачи данных
Введение к работе
Актуальность темы. Системы автоматизированного проектирования (САПР) уже давно являются неотъемлемой частью современного производства. Образовавшись в виде средств решения проектных задач, имеющих четко выраженный расчетный характер, системы автоматизированного проектирования прошли несколько стадий своего развития и выросли до уровня технологий, охватывающих больше, чем просто проектирование.
Современный рынок проектных работ требует дальнейшей модернизации и перехода на новые технологии. От предприятий требуется применение самых современных методов и подходов к созданию и поддержке изделия на всех стадиях его жизненного цикла. Поддержка жизненного цикла изделия, PLM (Product Lifecycle Management), комплексная автоматизация и использование единого информационного пространства становятся ключевыми при выборе средств автоматизации.
Проведение комплексной автоматизации, обеспечивающей не только потребности максимального количества проектных специальностей, но и корректную передачу данных между рабочими местами различного назначения, создание единого информационного пространства является первоочередной задачей проектных организаций. Как результат, повышается качество выпускаемой документации, уменьшается количество ошибок, сокращаются сроки проектирования, а значит, повышается конкурентоспособность предприятия.
При этом задачи единой среды проектирования сводятся к обеспечению коллективной работы проектно-конструкторских подразделений над проектом, хранению и поиску информации в электронных архивах, повторному использованию отработанных и проверенных технических решений, хранящихся в архиве, а также исключению ошибок за счет устранения нескольких источников для хранения одной и той же информации.
Однако на пути построения единого информационного пространства возникают определенные трудности. Современное производство зачастую имеет высокую степень географической разрозненности. Нередки случаи, когда над одним изделием трудятся специалисты из разных частей света, находящиеся на тысячи и даже десятки тысяч километров друг от друга. При такой отдаленности построение локальных корпоративных сетей и организации на их основе единой среды проектирования является довольно сложной задачей.
Кроме того, такая географическая удаленность вовсе не является единственной проблемой. Проектирование и производство сложных изделий зачастую требует кооперации и, как следствие, гетерогенности состава САПР, используемого каждой из сторон кооперации. В результате для проектирования и выпуска одного изделия используется гетерогенное программное обеспечение, что вызывает определенные сложности.
Различные САПР имеют различные форматы и способы хранения данных, хотя зачастую содержат схожую информацию (библиотеки компонент и их различные модели, готовые решения и др.). При рассмотрении процесса проектирования с точки зрения поддержки жизненного цикла изделия, необходимо обеспечить использование абсолютно всей информации, связанной с
изделием, всеми участниками его жизненного цикла, т.е. всеми САПР и другими системами, которые участвуют в процессе проектирования, создания и поддержки изделия. Однако при переходе от одной системы к другой возникают определенные сложности, связанные с отсутствием прямой совместимости форматов данных и возможности поиска информации в сторонних базах данных (не являющимися базами данных конкретной САПР). При этом важной задачей для САПР с точки зрения поддержки жизненного цикла изделия является возможность поиска и использования данных не только в базах данных и знаний этой САПР, но и в базах данных и знаний тех САПР, которые наряду с ней участвуют в проектировании изделия.
Таким образом, одной из основных проблем на пути комплексной автоматизации производства является использование несовместимых платформ и информационно несогласованных программных решений, географически распределенных друг от друга, а также построение подсистемы поиска информации в системе таких гетерогенных САПР. Одним из путей решения данной проблемы является применение принципов многоагентных систем.
Поиск информации в САПР можно разделить на две задачи: поиск по параметрам и поиск аналогов. И если первый (поиск по параметрам) является довольно тривиальной задачей, то поиск аналогов в САПР - задача более сложная. Для поиска аналогов объектов используют различные алгоритмы интеллектуального анализа данных (ИАД), а в частности алгоритмы кластеризации, которые позволяют разбить все множество исследуемых объектов на ряд групп на основе схожести их признаков.
Однако большинство алгоритмов кластеризации работают только с числовыми или только с категориальными данными. Однако как показывает практика, базы данных САПР зачастую содержат смешанную информацию. К тому же, большинство алгоритмов кластеризации требуют задания для своей работы ряда специфичных свойств, требующих от аналитика наличия определенных знаний о предметной области и способе кластеризации. Таким образом, нужны новые решения, позволяющие проводить кластеризацию смешанных наборов данных с минимальным участием в процессе человека.
Из всего вышеизложенного следует, что задача разработки подсистемы поиска информации в системе гетерогенных САПР на основе подхода многоагентных систем является довольно актуальной.
Целью диссертационной работы является разработка подсистемы поиска информации в системе гетерогенных САПР на основе многоагентных систем, которая позволяет объединять информацию из баз данных этих САПР для осуществления поиска решений. При этом важным условием является сохранение всех основных свойств САПР в контексте поддержки жизненного цикла изделия.
Для достижения поставленной цели в работе необходимо решить следующие задачи:
Провести анализ современных архитектур и выявить их основные недостатки для построения подсистемы поиска информации в базах данных гетерогенных САПР.
Провести анализ современных алгоритмов кластеризации, используемых для больших наборов данных и выявить их основные ограничения для
использования в подсистеме поиска информации в базах данных гетерогенных САПР.
Разработать новую модифицированную архитектуру подсистемы поиска информации САПР, позволяющую САПР взаимодействовать с различными базами данных.
Разработать алгоритм поиска аналогов в системе баз данных САПР.
Создать подсистему поиска информации в базах данных системы гетерогенных САПР.
Для решения поставленных задач использовались следующие методы исследований: анализ построения единого информационного пространства в задачах проектирования, анализ многоагентных систем, алгоритмов, множеств и генетических алгоритмов.
Научная новизна работы заключается в следующем:
Разработана модель поиска информации в системах различных источников данных на основе многоагентных систем;
Разработана архитектура системы поиска информации в системе баз данных гетерогенных САПР на основе принципов многоагентных систем;
Разработан алгоритм кластеризации, позволяющий работать с категориальными и числовыми данными.
Разработаны проблемно-ориентированные модифицированные генетические операторы для алгоритма кластеризации, позволяющие получать допустимые решения рассматриваемой задачи.
Практическая ценность работы заключается в реализации программного комплекса на основе многоагентных систем для поиска и кластеризации информации в системе распределенных баз данных. Алгоритмы реализованы на языке С# под ОС Windows. Данный программный комплекс позволяет производить поиск и кластеризацию различных данных инженерам, не обладающим навыками программирования и анализа данных.
Реализация и внедрение результатов работы. Основные теоретические и практические результаты диссертационной работы использованы в использовались в госбюджетной работе №12354 «Разработка теории и принципов построения интеллектуальных систем принятия решений при проектировании на основе квантовых вычислений и бионических методов поиска», в госбюджетной работе №12355 «Разработка теории и принципов интеллектуального анализа данных при построении систем поддержки принятия решений», а также в научно-исследовательских работах, выполненных по гранту РФФИ №07-01-00174 «Разработка теории и исследование эволюционных синергетических и гомеостатических методов принятия решений». Кроме того, материалы диссертации использованы в учебном процессе на кафедре САПР ТТИ ЮФУ при проведении лабораторных и курсовых работ по дисциплинам: «Разработка САПР», «Эволюционное моделирование и генетические алгоритмы», «Автоматизация конструкторского и технологического проектирования». Апробация основных теоретических и практических результатов работы проводилась на научных семинарах кафедры САПР, всероссийской научно-практической конференции молодых ученых, аспирантов и студентов «Информационные технологии, системный анализ и управление» (г. Таганрог, 2006), международной научно-технической конференции «Интеллектуальные
системы (AIS'07)» (с. Дивноморское, 2007 г.), всероссийской конференции студентов, аспирантов и молодых ученых «Технологии Microsoft в теории и практике программирования» (г. Таганрог, 2008 г.), международной научно-технической конференции «Интеллектуальные системы (AIS'08)>> (с. Дивноморское, 2008 г.), научно-практической конференции студентов, аспирантов, молодых ученых и специалистов (г. Коломна, 2009 г.).
Публикации. По теме диссертационной работы опубликовано 16 печатных работ, сделано 7 докладов на Всероссийских и Международных научно-технических конференциях.
Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложений. Работа содержит 158 стр., а также 44 рисунка, 16 таблиц, список литературы из 111 наименований, 18 стр. приложений и актов об использовании.
Поддержка жизненного цикла изделия
Основным направлением развития современного производства является применение современных методов и подходов к созданию и поддержке изделия на всех стадиях его жизненного цикла. [2] Жизненный цикл изделия — это совокупность этапов или последовательность бизнес-процессов, через которые проходит это изделие за время своего существования. [17]
В настоящее время наибольшее распространение получили CALS-технологии (Continuous Acquisition and Life cycle Support). [18] Рідеология GALS состоит в отображении реальных бизнес-процессов на виртуальную информационную среду, где эти процессы реализуются в виде компьютерных систем, а информация существует только в электронном виде. [19] Важным моментом CALS-технологий является то, что жизненный цикл конечного продукта рассматривается с учетом жизненного цикла входящих в него компонентов. [20]
Основу современных CALS-технологий составляет построение открытых распределенных автоматизированных систем для проектирования и управления в промышленности. [10] При этом главной проблемой построения таких систем является обеспечение единообразия представления данных, независимо от места и времени их получения в общей системе, стандартизация проектной, технологической и эксплуатационной документации, языков ее представления. Только при этом становится реальной успешная работа над общим проектом разных рабочих коллективов, разделенных во времени и пространстве и использующих разные системы.
Итак, повышение эффективности работы предприятия, повышение конкурентоспособности выпускаемой продукции возможно за счет интеграции систем проектирования, управления и документооборота на основе CALS-технологий. Такая интеграция лежит в основе создания комплексных систем автоматизации, в которых помимо функций собственно САПР реализуются средства для автоматизации функций управления проектированием, документооборота, планирования производства, учета и т.п.
Одним из результатов применения CALS-технологий на производстве является создание систем поддержки жизненного цикла изделия - PLM (Product Lifecycle Management). Под PLM понимается интегрированная информационная модель всех этапов жизненного цикла изделия: от проектирования и изготовления до установки, технического обслуживания и демонтажа. Наличие такой модели (в случае ее успешной реализации) позволит осуществлять доступ к информации об изделии всем заинтересованным службам предприятия, а также поставщикам и заказчикам. [21-24]
Технологии PLM являются основой, интегрирующей информационное пространство, в котором функционируют различные автоматизированные системы многих предприятий, такие как: 1. CAD (Computer Aided Design) - проектирование изделий; 2. САМ (Computer Aided Manufacturing) — разработка управляющих программ для станков с ЧПУ; 3. САЕ (Computer Aided Engineering) — инженерные расчеты; 4. ERP (Enterprise Resource Planning System) — система планирования ресурсов предприятия; 5. PDM (Product Data Management) - система управления данными об изделии, предназначена для хранения и управления данными; 6. SCM (Supply Chain Management) - системы управления цепочками поставок; 7. CRM (Customer Relationship Management) - система управления взаимодействием с клиентами, предназначена для повышения уровня продаж, оптимизации маркетинга и улучшения обслуживания клиентов путём сохранения информации о клиентах и истории взаимоотношений с ними, установления и улучшения бизнес-процедур и последующего анализа результатов.
Таким образом, современная САПР должна не только отвечать основным классическим требованиям, предъявляемым к САПР, но также должна иметь возможность использоваться совместно с системами поддержки жизненного цикла изделия.
Анализ систем поиска информации на основе многоагентных систем
В общем виде многоагентная система поиска информации, основанная на теории мобильных агентов состоит из интерфейсного и поискового агента, а также нескольких агентных сред, содержащих базы данных. В случае использования поисковой системы напрямую пользователем, назначение интерфейсного агента заключается в задании параметров поиска и помощи пользователю в формировании поискового запроса. Для подсистем поиска, интегрированных в другие системы, в частности в САПР, назначение интерфейсного агента сводится к обеспечению информационной согласованности на стыке подсистемы поиска и других систем. После формирования запроса, интерфейсный агент передает его (запрос) поисковому мобильному агенту и инициирует начало поиска информации. Когда поисковый агент закончил свое выполнение, он передает результат обратно интерфейсному агенту, который возвращает его пользователю или системе в определенной форме. Таким образом, главными функциями интерфейсного агента являются: формирование поискового запроса на основе параметров, полученных от пользователя или другой информационной системы; установление связи с подсистемой обработки информации и передача ей запроса; инициирование начала процесса поиска информации; возврат результата, полученного в результате поиска информации. Необходимо отметить, что интерфейсный агент вовсе не обязательно должен быть мобильным, так как его функции вовсе не требуют перемещения и работы в различных агентных системах. Другим элементом поисковой системы, основанной на теории мобильных агентов, является поисковый агент, который и осуществляет саму функцию поиска информации. Поисковый агент перемещается между различными агентными системами, содержащими базы данных, и осуществляет поиск информации в этих базах данных. Таким образом, в общем виде многоагентную систему поиска информации на основе мобильных агентов можно представить как MAS = (AI, AS, S, R, О), (2.7) где AI = {ai} - интерфейсный агент, AS = {as} - поисковый агент, S -множество агентных систем, содержащих базы данных, S = (sb s2, s3, ..., sn}, R - множество отношений между агентами, О - множество объектов многоагентной системы. Общая схема работы поисковой системы на основе мобильных агентов представлена на рисунке 2.9. Работа поисковой системы начинается с определения параметров поиска и формирования поискового запроса с помощью интерфейсного агента путем взаимодействия с пользователем или модулем САПР. Когда поисковый запрос сформирован, он передается поисковому мобильному агенту, который и начинает поиск. В процессе своей работы он последовательно обходит все агентные системы содержащие базы данных САПР, начиная с первой (список агентных систем и порядок их обхода зависит от конечной реализации). В случае поиска информации об определенном объекте, параметры которого заданы в поисковом запросе, агент перемещается между агентными системами до тех пор, пока не обнаружит необходимую информацию, после чего он возвращается к интерфейсному агенту и передает ему найденную информацию. Если предполагается поиск информации обо всех объектах, соответствующих заданным параметрам, агент обходит все базы данных, после чего возвращает интерфейсному агенту найденную информацию. Преимущество данного подхода к построению многоагентных поисковых систем состоит в относительно малой загруженности каналов передачи данных при осуществлении поиска информации. Последовательный опрос серверов баз данных и получение от них ответа загружает каналы передачи данных при большом количестве серверов, так как для осуществления операций поиска необходимо обработать 2N запроса, где N - количество баз данных, а коэффициент «2» обусловлен формой коммуникации («запрос»-«ответ»). Применение системы мобильных агентов сократит количество запросов до N+1, так как будут осуществлены N запросов для перемещения агента от одной агентной системы к другой и 1 запрос на возврат полученного результата. Другим преимуществом является то, что такие системы поиска могут использоваться в сетях с нестабильным каналом. Это обусловлено тем, что мобильному агенту необязательно постоянное взаимодействие с интерфейсным агентом, его породившим. Он может последовательно по мере доступности канала перемещаться от одной агентной системы к другой, и возвращать результат своей работы при появлении возможности доступа к интерфейсному агенту. Недостатком же такой системы является большой объем передаваемых запросов, что может убрать все преимущества, связанные с низкой загруженностью канала. Если в процессе своей работы агент обнаружит большое количество записей, то ему придется переносить их вместе с собой от системы к системе. Что касается САПР, то применение системы мобильных агентов в качестве основы поисковой системы не является благоприятной из-за описанных минусов такой системы. К тому же в САПР используется поиск информации, требующий от поисковой системы мгновенного отклика, мгновенного получения результатов. А при большом количестве баз данных время работы такой системы Т будет равно суммарному времени, потраченному на поиск и передачу информации между агентными системами, т.е.
Разработка алгоритма поиска информации в системе распределенных САПР
В общем виде подсистему поиска информации на основе многоагентных систем можно представить в виде системы, состоящей из ряда взаимосвязанных агентов, принадлежащих трем различным типам: Интерфейсные агенты, которые обеспечивают взаимодействие многоагентнои системы с САПР; Агенты-координаторы, координирующие поиск и выполняющие первичную обработку данных; Поисковые агенты, обеспечивающие взаимодействие многоагентнои системы с базами данных и базами знаний САПР. Общая схема взаимодействия агентов такой многоагентнои системы представлена на рисунке 3.1. Необходимо отметить, что количество интерфейсных агентов соответствует количеству САПР, запрашивающих информацию из баз данных или баз знаний, а количество поисковых агентов соответствует числу баз данных и баз знаний САПР. Количество агентов-координаторов ничем не ограничено, однако оно должно быть меньше или равно количеству интерфейсных агентов, в противном случае часть агентов-координаторов будет простаивать без работы. Все агенты многоагентной системы разделяются по специализации. Специализация определяет, какую информацию содержит база данных (например, база данных БИС) и какие агенты будут участвовать в ее поиске. Так на рисунке 3.1 интерфейсный агент 1, агент-координатор 1, поисковый агент 1, поисковый агент 2 и поисковый агент 3 принадлежат одной специализации, а интерфейсный агент 2, интерфейсный агент 3, агент-координатор 2 и поисковый агент 4 принадлежат другой специализации. Такая специализация необходима для первичной фильтрации всех баз данных и баз знаний, отсекая тем самым те источники, которые не могут содержать необходимую информацию. В терминах многоагентной системы специализация означает онтологию, с которой работает данный агент. Алгоритм поиска информации в системе распределенных САПР представляет собой последовательность действий, изображенную на рисунке 3.2. Все действия, выполняемые во время работы алгоритма, принадлежат трем разным уровням абстракции: Уровень клиента; Уровень многоагентной системы; Уровень базы данных. Уровень клиента представляет собой совокупность действий, выполняемых при непосредственном взаимодействии с клиентским приложением, а именно с модулем САПР, который инициирует поиск информации в системе распределенных САПР. Уровень базы данных представляет собой действия, выполняемые при взаимодействии с конкретным источником базы данных. Именно на этом уровне происходит поиск информации в базах данных САПР. Уровню многоагентной системы соответствуют все остальные действия. Таким образом, все эти уровни абстракции соотносятся с распространенной методологией Model-View-Controller, используемой при проектировании и разработке приложений и корпоративных сайтов. Применение данной методологии приводит к формированию следующей цепочки взаимодействия внутри приложения [93]: Пользователь — Граничный объект (View, Уровень клиента) -- Управляющий объект (Controller, Уровень многоагентной системы) — Данные (Model, Уровень базы данных).
Общий анализ загруженности каналов передачи данных
Итак, многоагентная поисковая система представляет собой распределенное приложение, состоящее из четырех частей. Будем считать, что интерфейсная часть располагается у пользователя, а координатор, поисковая и общесистемная части располагаются на высокопроизводительных серверах. При этом компьютер конечного пользователя (интерфейсная часть) зачастую имеет более низкую пропускную способность сети, чем сервера, обеспечивающие большое количество одновременных подключений за счет использования широких каналов передачи данных. В упрощенном виде схема многоагентной поисковой системы изображена на рисунке 4.2. Здесь пунктирными линиями изображены каналы передачи данных со средней и низкой пропускной способностью, а сплошные — каналы связи с высокой пропускной способностью. Для поиска данных в многоагентной поисковой системе интерфейсная часть создает один запрос к каталогу агентов для определения адреса координатора, а затем, после получения ответа, сам поисковый запрос координатору поиска. При этом количество запросов не зависит от количества баз данных, т.е. для проведения одной операции поиска поисковый агент выполняет 2 запроса вне зависимости от количества конечных источников информации. В случае использования непосредственных подключений к базам данных вместо многоагентной поисковой системы количество запросов будет прямо пропорционально количеству источников информации. Таким образом, можно считать, что использование многоагентной поисковой системы снижает нагрузку на каналы передачи данных конечного пользователя. В этом плане она сродни трехзвенной архитектуре построения приложений, бизнес логика которых находится на сервере приложений, и поэтому конкретный поиск (то есть обращения к базам данных) в такой архитектуре выполняет сервер приложений. Конкретный подсчет загруженности сети может быть произведен лишь при выборе средств кодирования и передачи сообщений, т.е. при построении конечной системы. Любая информационная система (ИС) - это сложная программно-аппаратная система, включающая в свой состав аппаратные средства и программное обеспечение. При этом одним из важнейших показателей информационной системы является ее надежность. Говоря о надежности ИС, необходимо учитывать как программную, так и аппаратную составляющие (компьютеры, периферийное оборудование, коммутационное оборудование, кабельное оборудование и др.). При этом для программной части важными показателями надежности являются достоверность информации, ее корректность и правильность интерпретации. Однако такие параметры касаются конкретной реализации информационной системы. Что же касается аппаратной части, то вычисление ее надежности является более доступным для вычисления на этапе построения общей архитектуры приложения. Под надежностью будем понимать способность технического устройства (ТУ) сохранять свои первоначальные технические качества в процессе эксплуатации. В информационных системах надежность технического устройства неразрывно связана с надежностью программного обеспечения. В случае многоагентной поисковой системы техническими устройствами, непосредственно принимающими участие в поиске информации, можно считать следующие группы оборудования вместе с функционирующим на них программным обеспечением: Компьютер пользователя; Канал передачи данных от компьютера пользователя к координатору вместе с сетевым оборудованием и необходимым программным обеспечением; Координатор — сервер, поддерживающий достаточно большое количество одновременных подключений; Канал передачи данных от координатора к базам данных вместе с сетевым оборудованием и программным обеспечением, необходимым для его работы; Сервер базы данных, поддерживающий большое количество обращений к базам данных.
