Дипломная работа: Использование алгоритмов искусственного интеллекта в процессе построения UFO-моделей
Множество продукционных правил образует базу правил, каждое из которых представляет обособленный фрагмент знаний о решаемой проблеме. Психологи называют такие фрагменты чанками (от англ. chunk). Считается, что чанк – это объективно существующая единица знаний, выделяемая человеком в процессе познания окружающего мира.
Предпосылка правила часто рассматривается как образец. Образец – это некоторая информационная структура, определяющая обобщенную ситуацию окружающей действительности, при которой активизируется правило. Рабочая память отражает конкретные ситуации, возникающие во внешней среде. Информационная структура, представляющая конкретную ситуацию внешней среды в рабочей памяти, называется образом [35].
Интерпретатор реализует логический вывод. Процесс вывода является циклическим и называется поиском по образцу. Рассмотрим его в упрощенной форме. Текущее состояние моделируемой предметной области отражается в рабочей памяти в виде совокупности образов, каждый из которых представляется посредством фактов. Рабочая память инициализируется фактами, описывающими задачу. Затем выбираются те правила, для которых образцы, представляемые предпосылками правил, сопоставимы с образами в рабочей памяти. Данные правила образуют конфликтное множество. Все правила, входящие в конфликтное множество могут быть активизированы. В соответствии с выбранным механизмом разрешения конфликта активизируется одно из правил. Выполнение действия, содержащегося в заключении правила, приводит к изменению состояния рабочей памяти. В дальнейшем цикл управления выводом повторяется. Указанный процесс завершается, когда не окажется правил, предпосылки которых сопоставимы с образами рабочей памяти [36].
Таким образом, процесс вывода, основанный на поиске по образцу, состоит из четырех шагов:
– выбор образа;
– сопоставление образа с образцом и формирование конфликтного набора правил;
– разрешение конфликтов;
– выполнение правила.
Широкое применение продукционных моделей определяется следующими основными достоинствами:
– универсальностью (практически любая область знаний может быть представлена в продукционной форме);
– модульностью (каждая продукция представляет собой элемент знаний о предметной области, удаление одних и добавление других продукций выполняется независимо);
– декларативностью (продукции определяют ситуации предметной области, а не механизм управления);
– естественностью процесса вывода заключений, который во многом аналогичен процессу рассуждений эксперта;
– асинхронностью и естественным параллелизмом, который делает их весьма перспективным для реализации на параллельных ЭВМ.
Однако продукционные системы не свободны от недостатков:
– процесс вывода имеет низкую эффективность, так как при большом числе продукций значительная часть времени затрачивается на непроизводительную проверку условия применения правил;
– проверка непротиворечивости системы продукций становится весьма сложной из-за недетерминированности выбора выполняемой продукции из конфликтного множества.
В системах, основанных на правилах, часто акцент делается на системах прямого логического вывода. Например, в качестве правил и начальных фактов используется ряд примеров, что позволяет встроить систему с правилами в более крупную систему и задействовать ее для создания системы управления сенсорами, устойчивой к ошибкам [37].
1.2.4 Нечеткая логика
Ту роль, которую в классической теории множеств играет двузначная булева логика, в теории нечетких множеств играет многозначная нечеткая логика, в которой предположения о принадлежности объекта множеству, например Быстрый("Порш"), могут принимать действительные значения в интервале от 0 до 1. Возникает вопрос, а как, используя концепцию неопределенности, вычислить значение истинности сложного выражения, такого как Не(Быстрый("Шевроле")).
По аналогии с теорией вероятности, если F представляет собой нечеткий предикат, операция отрицания реализуется по формуле Не(F)=1–F.
Но аналоги операций конъюнкции и дизъюнкции в нечеткой логике не имеют никакой связи с теорией вероятностей [38]. Рассмотрим следующее выражение: ""Порш" является быстрым, представительским автомобилем".
В классической логике предположение (Быстрый("Порш")) И (Представительский ("Порш")) является истинным в том и только в том случае, если истинны оба члена конъюнкции. В нечеткой логике существует соглашение: если F и G являются нечеткими предикатами, то f(FÙG)(X)=min(fF(X), fG(X)).
Таким образом, если Быстрый("Порш")=0,9 и Представительский("Порш")=0,7, то (Быстрый("Порш"))И(Представительский ("Порш")) = 0,7.
А теперь рассмотрим выражение (Быстрый("Порш")) И Не(Быстрый("Порш")). Вероятность истинности этого утверждения равна 0, но в нечеткой логике значение этого выражения будет равно 0,1. Какой смысл имеет это значение? Его можно считать показателем принадлежности автомобиля к нечеткому множеству среднескоростных автомобилей, которые в чем-то близки к быстрым, а в чем-то – к медленным.
Смысл выражения Быстрый("Порш")=0,9 заключается в том, что мы только на 90% уверены в принадлежности этого автомобиля к быстрым именно из-за неопределенности самого понятия "быстрый автомобиль". Вполне резонно предположить, что существует некоторая уверенность в том, что "Порш" не принадлежит к быстрым. Например, он медленнее автомобиля, принимающего участие в гонках "Формула-1".
Аналог операции дизъюнкции в нечеткой логике определяется следующим образом: f(FÚG)(X)=max(fF(X), fG(X)).
Операторы обладают свойствами коммутативности, ассоциативности и взаимной дистрибутивности. Как к операторам в стандартной логике, к ним применим принцип композитивности, т.е. значения составных выражений вычисляются только по значениям выражений-компонентов. В этом операторы нечеткой логики составляют полную противоположность законам теории вероятностей, согласно которым при вычислении вероятностей конъюнкции и дизъюнкции величин нужно принимать во внимание условные вероятности [39].
Нечеткая логика имеет дело с ситуациями, когда и сформулированный вопрос, и знания, которыми мы располагаем, содержат нечетко очерченные понятия. Однако нечеткость формулировки понятий является не единственным источником неопределенности. Иногда мы просто не уверены в самих фактах. Если утверждается: "Возможно, Иван сейчас в Киеве", то говорить о нечеткости понятий Иван и Киев не приходится. Неопределенность заложена в самом факте, действительно ли Иван находится в Киеве.
Теория возможностей является одним из направлений в нечеткой логике, в котором рассматриваются точно сформулированные вопросы, базирующиеся на неточных знаниях.
На основе нечеткой логики часто строятся системы управления. Например, в модели зарядного устройства для батарей функции содержат не только стандартные операторы нечеткой логики, но и вспомогательные функции, которые поддерживают создание функций нечеткой логики [40].
1.2.5 Умные агенты
Агент – это аппаратная или программная сущность, способная действовать в интересах достижения целей, поставленных перед ним владельцем и/или пользователем [41].
Проблематика интеллектуальных агентов и мультиагентных систем имеет уже почти 40-летнюю историю и сформировалась на основе результатов, полученных в рамках работ по распределенному искусственному интеллекту, распределенному решению задач и параллельному искусственному интеллекту. Но, пожалуй, лишь в последнее десятилетие она выделилась в самостоятельную область исследований и приложений и все больше претендует на одну из ведущих ролей в рамках интеллектуальных информационных технологий. Спектр работ по данной тематике весьма широк, интегрирует достижения в области компьютерных сетей и открытых систем, искусственного интеллекта и информационных технологий и ряда других исследований, а результаты уже сегодня позволяют говорить о новом качестве получаемых решений.
В настоящее время множество исследовательских лабораторий, университетов, фирм и промышленных организаций работают в этой области, и список их постоянно расширяется. Он включает мало известные имена и небольшие коллективы, уже признанные исследовательские центры и организации, а также огромные транснациональные компании. Областями практического использования агентных технологий являются:
– управление информационными потоками и сетями;
– управление воздушным движением;
– информационный поиск;
– электронная коммерция;
– обучение;
– электронные библиотеки.
К построению агентно-ориентированных систем можно указать два подхода: реализация единственного автономного агента или разработка мультиагентной системы. Автономный агент взаимодействует только с пользователем и реализует весь спектр функциональных возможностей, необходимых в рамках агентно-ориентированной программы. В противовес этому мультиагентные системы являются программно-вычислительными комплексами, где взаимодействуют различные агенты для решения задач, которые трудны или недоступны в силу своей сложности для одного агента. Часто такие мультиагентные системы называют агентствами, в рамках которых агенты общаются, кооперируются и договариваются между собой для поиска решения поставленной перед ними задачи.
Агентные технологии обычно предполагают использование определенных типологий агентов и их моделей, архитектур мультиагентных систем и опираются на соответствующие агентные библиотеки и средства поддержки разработки разных типов мультиагентных систем.
Умные агенты применяются различными способами. Например, существует агент-фильтр, использующийся для фильтрации информации из сети Интернет. Параметры поиска Web-агента задаются в простом файле конфигурации. Затем агент автономно собирает новости через протокол NNTP и предоставляет их пользователю с помощью HTTP-протокола, действуя аналогично Web-серверу [42].
1.2.6 Алгоритм муравья
Алгоритмы муравья – это сравнительно новый метод, который может использоваться для поиска оптимальных путей по графу. Данные алгоритмы симулируют движение муравьев в окружающей среде и используют модель ферментов для коммуникации с другими агентами [43].
Хотя муравьи и слепы, они умеют перемещаться по сложной местности, находить пищу на большом расстоянии от муравейника и успешно возвращаться домой. Выделяя ферменты во время перемещения, муравьи изменяют окружающую среду, обеспечивают коммуникацию, а также отыскивают обратный путь в муравейник.
Самое удивительное в данном процессе – это то, что муравьи умеют находить самый оптимальный путь между муравейником и внешними точками. Чем больше муравьев используют один и тот же путь, тем выше концентрация ферментов на этом пути. Чем ближе внешняя точка к муравейнику, тем больше раз к ней перемещались муравьи. Что касается более удаленной точки, то ее муравьи достигают реже, поэтому по дороге к ней они применяют более сильные ферменты. Чем выше концентрация ферментов на пути, тем предпочтительнее он для муравьев по сравнению с другими доступными. Так муравьиная "логика" позволяет выбирать более короткий путь между конечными точками.
Алгоритмы муравья интересны, поскольку отражают ряд специфических свойств, присущих самим муравьям. Муравьи легко вступают в сотрудничество и работают вместе для достижения общей цели. Алгоритмы муравья работают так же, как муравьи. Это выражается в том, что смоделированные муравьи совместно решают проблему и помогают другим муравьям в дальнейшей оптимизации решения.
Рассмотрим пример [15]. Два муравья из муравейника должны добраться до пищи, которая находится за препятствием. Во время перемещения каждый муравей выделяет немного фермента, используя его в качестве маркера.
При прочих равных каждый муравей выберет свой путь. Пусть первый муравей выбирает путь, который в два раза длиннее, чем путь, выбранный вторым муравьем. Так как путь второго муравья в два раза короче пути первого муравья, то, когда второй муравей достигнет цели, первый муравей в этот момент пройдет только половину пути.
Когда муравей достигает пищи, он берет один из объектов и возвращается к муравейнику по тому же пути. Когда второй муравей вернется в муравейник с пищей, первый муравей еще только достиг пищи.
При перемещении каждого муравья на пути остается немного фермента. Для первого муравья за это время путь был покрыт ферментом только один раз. В то же самое время второй муравей покрыл путь ферментом дважды. Когда первый муравей вернется в муравейник, второй муравей уже успеет еще раз сходить к еде и вернуться. При этом концентрация фермента на пути второго муравья будет в два раза выше, чем на пути первого. Поэтому первый муравей в следующий раз выберет путь второго муравья, поскольку там концентрация фермента выше.
В этом и состоит базовая идея алгоритма муравья – оптимизация путем непрямой связи между автономными агентами.
1.3 Постановка задачи
Проведенный анализ современного состояния проблемы показывает, что:
– в современных технологиях построения систем процесс построения моделей приходится осуществлять проектировщику вручную, основываясь на своем опыте и интуиции с помощью CASE-средств;
– современные прикладные методы и технологии искусственного интеллекта ориентированы не столько на копирование поведения человека, сколько на достижение результатов, аналогичных человеческим результатам;
– для автоматического построения моделей систем целесообразно применить алгоритм муравья.
Целью данной магистерской аттестационной работы является исследование возможности использования алгоритмов искусственного интеллекта в процессе построения UFO-моделей.
Достижение сформулированной цели связано с решением следующих задач:
– адаптация алгоритма муравья к процессу построения UFO-модели из заданных компонентов;
– использование Microsoft Excel в процессе построения UFO-модели из заданных компонентов;
– применение полученных результатов в процессе UFO-моделирования.
2. Адаптация алгоритма муравья к задаче построения UFO-модели из заданных компонентов
2.1 Начальное размещение муравья
Пусть задана контекстная диаграмма системы, определяющая ее множество входов и выходов (рис. 2.1).
Рисунок 2.1 – Контекстная диаграмма системы
Изначально муравей может находиться в одной из двух видов точек [44]:
– в конце любой входной стрелки In (n) (n = 1, 2, …, N);
– в начале любой выходной стрелки Out (m) (m = 1, 2, …, M).
Например, контекстная диаграмма системы может иметь два входа (In (1), In (2)) и три выхода (Out (1), Out (2), Out (3)), а муравей – находиться в конце входной стрелки In (1). Данная ситуация иллюстрируется рис. 2.2, на котором муравей условно изображен жирной точкой.
Рисунок 2.2 – Пример начального размещения муравья
2.2 Правила соединения UFO-компонентов
Пусть задана библиотека
компонентов 
, из которых необходимо
собрать систему, заданную контекстной диаграммой, изображенной на рис. 2.1.
Каждый компонент 
библиотеки тоже
характеризуется своим множеством входов 
,
а также – своим множеством выходов 
(рис.
2.3).
Рисунок 2.3 – Контекстная
диаграмма компонента 
Входы и выходы
контекстной диаграммы системы и компонентов имеют такую характеристику как тип.
Существуют следующие правила соединения входов и выходов [11]. Вход In (n)
контекстной диаграммы системы может быть присоединен к входу 
компонента 
, если тип In (n) совпадает
с типом 
. Это условие совпадение
типов можно записать в виде равенства 
(рис.
2.4).
