Быстрый поиск

Дипломная работа: Использование алгоритмов искусственного интеллекта в процессе построения UFO-моделей

– управление информационными потоками и сетями;

– управление воздушным движением;

– информационный поиск;

– электронная коммерция;

– обучение;

– электронные библиотеки.

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

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

Умные агенты применяются различными способами. Например, существует агент-фильтр, использующийся для фильтрации информации из сети Интернет. Параметры поиска 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).

Рисунок 2.4 – Соединение входа с входом

Выход Out (m) контекстной диаграммы системы может быть присоединен к выходу компонента , если тип Out (m) совпадает с типом . Это условие можно записать в виде равенства (рис. 2.5).