Сравнение алгоритмов поиска оптимальных решений в агентных системах
Аннотация
Рассмотрены основные понятия теории агентов: тип агентов, основные задачи агентов, суть поиска решения агентом в пространстве состояния системы. Для реализации алгоритмов поиска используются граф, построенный на основе начальных состояний и пространство доступных действий. Для поиска решения агент может использовать различные стратегии, которые определяют тот или иной тип поиска: поиск в ширину или поиск в глубину. В работе приводится сравнение этих типов поиска решений в агентной системе.
Ключевые слова: агент, алгоритм поиска агентов, поиск в глубину, поиск в ширину.
Abstract
The basic concepts of the theory of agents: the type of agents, the main agent problem, the essence of search agent solutions in the space of states of the system. For the implementation of search algorithms used graph constructed on the basis of the initial states and the space available actions. To find the solution agent may use a variety of strategies that define a particular type of search: search in width or depth-first search. The paper presents a comparison of these types of solutions in search of an agent based system.
Keywords: agent, agents search algorithm, depth-first search, the search width.
К искусственному интеллекту, относятся такие направления науки как онтология, нейронные сети, распознавание образов, нечеткая логика и т. д.
Одним из основных понятий в искусственном интеллекте является понятие агента [1; 3; 5]. Под агентом подразумевается все, что может воспринимать среду с помощью датчиков и воздействовать на нее, используя исполнительные механизмы. Существует несколько видов агентов, которые разделяются не только по функциям, но и по решаемым задачам. Например, простой рефлексивный агент, у которого есть только датчики и механизмы воздействия на среду используется для простых однотипных задач, которые обычно строго структурированы, в отличие от него агент, основанный на моделях используется уже для более сложных задач, ведь кроме датчиков и механизмов воздействия на окружающую среду, у него также заложено в программу понятие состояния и изменения окружающей среды, что в значительной степени увеличивает возможности данного типа агентов [2; 4; 6]. Все множество агентов принято подразделять на следующие типы: простой рефлексивный агент, агент, основанный на модели, агент, основанный на цели, агент, основанный на полезности [7; 8; 9].
Каждый из агентов в независимости от задачи, нацелен не только на достижения цели, но и на оптимизацию параметров. Задача агента состоит в нахождении наилучшей последовательности действий, которая приведет к основной цели. Первым шагом решения задачи является формулировка цели с учетом текущей ситуации и показателей производительности агента [1; 4]. Формулировка задачи - это процесс определения того, какие действия и состояния следует рассматривать с учетом заданной цели. Конечно, существуют такие ситуации, при которых агенту понадобится найти последовательность действий вначале с неизвестной стоимостью, после чего действия приведут к нужному результату [2; 7]. Процесс определения последовательностей называется поиском. Любой алгоритм поиска принимает в качестве входных данных задачу и выдает решение в форме последовательности действий. Алгоритм может выдавать рекомендуемые действия, которые помогают достичь не только основную цель, но и второстепенные. В большинстве случаев, когда используется алгоритм поиска, учитываются особенности среды (является ли она статической или динамической), формируются этапы поведения агента и возможные действия. В большинстве случаев учитывается наблюдаемость среды, является ли она дискретной, детерминированной [8; 9]. Такая система агента со средой называется системой с разомкнутой обратной связью, поскольку агент игнорирует результаты восприятия, а это приводит к отсутствию обратной связи между агентом и средой. Одним из самых главных критериев является начальное состояние системы, то есть положение, в котором агент приступает к работе, затем следует описание возможных действий, доступных агенту или функция определения преемника [3; 7]. Вместе начальное состояние и доступные действия задают пространство состояний задачи - множество всех состояний, достижимых из начального состояния. Пространство состояний образует граф, в котором узлами являются состояния агента, а дугами действия. Путем в пространстве состояний является последовательность состояний. Также важным критерием является проверка цели, которая позволяет определить, является ли данное конкретное состояние целевым состоянием. И последним критерием является функция пути, которая задает числовое значение стоимости каждого пути, а агент уже сам выбирает по какому из путей пойти в зависимости от его внутреннего показателя производительности. Оценивание пути происходит по сумме стоимости каждого этапа. Под стоимостью этапа понимаются изменения, связанные с переход из одного состояния в другое путем исполнения действий [4; 6].
Для реализации алгоритмов поиска обычно задается дерево поиска. Оно создается на основе начального состояния и пространства доступных действий. Рассмотрим задачу, в которой есть множество возможных решений. Предположим, что мы находимся в городе N, нам нужно попасть в город S, в который можно попасть различными способами. Поскольку у нас конкретная цель попасть в город S, то мы будем искать путь с наименьшей "стоимостью". Для того, чтобы найти такой путь, нужно использовать процедуру развертывания текущего состояния, то есть применить функцию определения преемника к текущему состоянию и сформировать новые множества состояний. Эти действия повторяются. Собственно, в этом и есть суть поиска решений агентом, то есть выбрать один вариант и отложить другие. Снова выбирать, проверять и развертывать узлы пока не найдется целевое решение. Порядок, в котором происходит развертывание состояний, определяется стратегией поиска [2; 5; 8]. Между пространством состояний и деревом поиска нужно проводить строгое различие. В пространстве состояний для решения нашей задачи могут быть только города, через которые можно попасть из города N в город S. Нужно разделять понятия узла и состояния. Узел - это учетная структура данных, применяемая для представления дерева поиска, а под состоянием понимается конфигурация мира [6; 7; 8]. Также необходимо представить коллекцию узлов, которые были сформированы, но не развернуты, такая коллекция называется периферией. Каждый элемент периферии представляет собой листовой узел, то есть узел, который не имеет преемников на дереве. Простейшим представлением периферии может служить множество узлов. В таком случае стратегия поиска будет представляться в виде функции, которая выбирает действие из множества узлов, подлежащих развертыванию. Данный подход является не очень сложным в реализации, но он может быть дорогостоящим с точки зрения вычислительной мощности, поскольку каждый элемент периферии может оказаться потенциально в качестве лучшего, то есть приходится применять функцию определения преемников к огромному множеству узлов для выбора лучшего. Предполагается, что коллекция узлов реализована в виде очереди [3; 4; 7].
Существует понятие неинформированного поиска (или его часто называют слепым поиском). Данный тип поиска не использует дополнительной информации, кроме той, которая дана в определении задачи. Такой тип поиска способен только на то, чтобы вырабатывать преемников и отличать целевое состояние от нецелевого [1; 2; 3].
Одной из основных стратегий такого поиска является поиск в ширину. Поиск в ширину является одной из простейших стратегий, в которой сначала развертывается корневой узел, после чего развертываются все преемники корневого узла, затем развертываются преемники этих преемников и т. д. Если проанализировать данный метод поиска, то можно утверждать, что он является полным, то есть поверхностный целевой узел находится на некоторой конечной глубине, в итоге поиск приведет к результату не обязательно оптимальному. Также из недостатков данного метода можно выделить то, что он является очень затратным по памяти, так как ему придется хранить все узлы, поскольку каждый предыдущий узел является предком следующего возможного варианта. Пространственная сложность так же увеличивается, как временная, с добавлением узла в корень дерева поиска [4; 5; 6].
Следующим рассмотрим поиск по критерию стоимости. Поскольку поиск в ширину, как следует из выше указанного, слишком дорогостоящий и не всегда приводит к оптимальному решению, то с помощью обычного дополнения можно создать алгоритм, который является оптимальным при любой функции распределения. В отличие от поиска в ширину, который развертывается до первого подходящего узла, поиск по критерию стоимости обеспечивает развертывание узла n с наименьшей стоимостью пути [7; 8; 9]. Следует отметить, что при равенстве стоимости этапов такой поиск ничем не отличается от поиска в ширину. При таком поиске учитывается не количество этапов, имеющихся в пути, а только их суммарная стоимость. Данный алгоритм поиска может привести к бесконечному циклу, если стоимость одного из действий будет равна нулю, при этом можно гарантировать полноту поиска путем введения переменной, равной определенному положительному значению. Если по мере выполнения алгоритма, "стоимость" прохождения растет, то из этого следует, что алгоритм выдаст варианты, удовлетворяющие условию увеличения стоимости пути, то есть первый целевой узел будет оптимальным [3; 6; 9].
Следующим рассмотрим поиск в глубину. При поиске в глубину всегда развертывается самый глубокий узел в текущей периферии дерева поиска. Поиск проходит на самый глубокий уровень дерева, на котором уже узлы не имеют преемников. По мере того как эти узлы развертываются, они удаляются из периферии, поэтому дальнейший поиск начинается со следующего самого поверхностного узла, который все еще имеет неисследованных преемников. Поиск в глубину не очень требовательный к мощности компьютера, и имеет не очень большие потребности в памяти. Поиск хранит только единственный путь от корня до листового узла, наряду с остальными не развернутыми узлами для пути. То есть, если исследован определенный узел, то он удаляется из памяти, поскольку скоро будут исследованы его потомки, которые дадут более оптимальное решение [2; 4; 8].
Существует множество вариантов поиска в глубину. Одним из таких алгоритмов является поиск с возвратами, который использует еще меньше памяти. В данном поиске развертываются не все преемники. Этот вариант поиска имеет дополнительное улучшение, которое сокращает потребление памяти, путем модификации преемника при его формировании, не осуществляя предварительное копирование. Недостатком этого вида поиска является то, что можно сделать не правильный выбор, кроме того имеется опасность вхождения в тупик, которая связана с прохождением вниз по бесконечному пути [1; 2; 4; 6]. граф агентный алгоритм
Одним из решений проблемы поиска в глубину является установление максимального предела глубины - это поиск с ограничением глубины. То есть, если алгоритм доводит до предельной глубины, то узел максимальной глубины рассматривается так, как будто у него нет преемников. Поиск с ограничением глубины может быть реализован как простая модификация общего алгоритма поиска в дереве или рекурсивного алгоритма поиска в глубину [3; 7; 9].
Рассмотрим поиск в глубину с итеративным углублением. Он представляет общую стратегию, которая применяется со стандартным поиском в глубину для нахождение наилучшего предела. Данный метод использует постепенное увеличение предела глубины до нахождения максимально нужной. То есть изначально глубина является равно 0, после развертывания всех узлов на данной глубине происходит увеличение глубины до 1 и так далее, пока не будет найдено оптимальное решение. В поиске с итеративным углублением сочетаются преимущества поиска в глубину с преимуществами поиска в ширину. Поиск с итеративным углублением является не требовательным к памяти (особенность поиска в глубину), также он является конечным, то есть обладает показателем полноты, если коэффициент ветвления конечен и "стоимость" пути представляет собой неубывающую функцию. Поиск итеративным углублением может на первый взгляд показаться расточительным, поскольку одни и те же состояния формируются несколько раз на разных уровнях, но как показали исследования, такой подход является не настолько затратным, как может показаться вначале. Поскольку узлы на глубине формируются в единичном размере, то на предыдущей глубине узел будет сформирован дважды и так далее до начальной глубины. Эксперты утверждают, что итеративное углубление - это предпочтительный метод неинформированного поиска в случае, когда имеется большое пространство поиска, а глубина решений заранее неизвестна [4; 5; 7; 9].
Список литературы
- 1. Мелихова О. А., Мелихова З. А. Дискретная математика: учебное пособие. - Таганрог: издательство ТРТУ, 2006. - 172 с. 2. Мелихова О. А. Процесс познания в терминах математической логики // Информатика вычислительная техника и инженерное образование. 13.10.2014. URL: http://digital-mag. tti. sfedu. ru (Дата обращения: 5.12.2015). 3. Мелихова О. А. Нейронные сети, как составная часть систем искусственного интеллекта // Информатика вычислительная техника и инженерное образование. 6.09.2015. URL:http://digital-mag. tti. sfedu. ru (Дата обращения: 1.12.2015). 4. Мелихова О. А., Гайдуков А. Б., Джамбинов С. В., Чумичев В. С. Методы поддержки принятия решений на основе нейронных сетей // Актуальные проблемы гуманитарных и естественных наук. - Москва, № 09 (80). Ч. 1. 2015. - С. 52-59. 5. Мелихова О. А., Григораш А. С., Джамбинов С. В., Чумичев В. С., Гайдуков А. Б. Некоторые аспекты теории нейронных систем // Молодой ученый. - Казань. № 16 (96), 2015. - С. 196-199. 6. Мелихова О. А., Григораш А. С., Джмбинов С. В, Чумичев В. С, Гайдуков А. Б. Методы обучения в системах искусственного интеллекта // Технические науки - от теории к практике / Сб. ст. по материалам LII междунар. науч.-практ. конф № 11 (47). Новосибирск: Изд. АНС "Сибак", 2015 - С. 19-29. 7. Мелихова О. А., Вепринцева О. В., Чумичев В. С., Джамбинов С. В., Гайдуков А. Б. Понятие агента в системах искусственного интеллекта // Технические науки - от теории к практике / Сб. ст. по материалам LIII междунар. науч.-практ. конф № 12 (48). Новосибирск: Изд. АНС "Сибак", 2015 - С. 44-51. 8. Мелихова О. А., Вепринцева О. В., Чумичев В. С., Джамбинов С. В., Гайдуков А. Б. Модели агентов в интеллектуальных системах // Технические науки - от теории к практике / Сб. ст. по материалам LIV междунар. науч.-практ. конф № 1 (49). Новосибирск: Изд. АНС "Сибак", 2016 - С. 49-56. 9. Мелихова О. А., Вепринцева О. В., Чумичев В. С., Джамбинов С. В., Гайдуков А. Б. Режимы обучения в искусственных нейронных сетях // Инновации в науке / Сб. ст. по материалам LIII междунар. науч.-практ. конф № 1 (50). Часть 1. Новосибирск: Изд. АНС "Сибак", 2016. - С. 16-23.
Похожие статьи
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Обзор и анализ существующих программных решений Из доступных программных решений можно выделить пару программ. Первая программа SusaninLab 1.2 -...
-
Системы поддержки принятия решений - Системы поддержки принятия решений
Система поддержки принятия решений или СППР (Decision Support Systems, DSS) -- это компьютерная система, которая путем сбора и анализа большого...
-
Введение - Система поддержки принятия решений
Современные системы поддержки принятия решения (СППР) представляют собой системы, максимально приспособленные к решению задач повседневной управленческой...
-
Экспертные информационные системы - Системы поддержки принятия решений
Наибольший прогресс среди компьютерных информационных систем отмечен в области разработки экспертных систем. Экспертные системы дают возможность...
-
Для ускорения процесса конструирования регулятора в пространстве состояний в Matlab была разработана функция, которая, при должной настройке, позволяет...
-
Обзор классического подхода Приведем теорему для формирования линейного закона управления с обратной связью в пространстве состояний [3]: Дан объект,...
-
Деревья решений - это способ представления иерархической, последовательной структуры организованной по определенным правилам, где каждому объекту...
-
Общее описание программного обеспечения, реализующего разработанный алгоритм Основной идеей дипломного проекта, является реализация алгоритма...
-
Сеть хранения данных - Выбор оптимального решения для виртуализации
Является архитектурным решением для подключения внешних устройств хранения данных, например ленточные библиотеки, массивы итд, для того чтобы...
-
Red Hat - Выбор оптимального решения для виртуализации
Red Hat (RHEV) - это решение для управления серверами и рабочими станциями, первая платформа с открытым исходным кодом. Решение основано на гипервизоре...
-
Заключение - Системы поддержки принятия решений
Первые информационные системы появились в 50-х гг. В эти годы они были предназначены для обработки счетов и расчета зарплаты, а реализовывались на...
-
Нет необходимости для детального рассмотрения предлагающихся разнообразных направлений классификации информации. Выделим только те признаки информации,...
-
Разработаем алгоритм одного из основных методов, используемого в данной программе. Private void pictureBox1_MouseDown(objects sender, MouseEventArgs e)...
-
Корпоративная интеграционная подсистема на базе IBM WebSphere Business Integration Message Broker [28] отвечает за выстраивание корпоративной...
-
Для того, чтобы использовать симметричные алгоритмы шифрования, необходимо безопасно обменяться ключами. Протокол Диффи - Хеллмана позволяет двум и более...
-
Описание используемых методов и алгоритмов - Выбор оптимального маршрута для строительства дороги
В данном пункте нужно проанализировать используемый алгоритм поиска кратчайшего пути. Алгоритм Дейкстры Находит кратчайший путь от одной из вершин графа...
-
ОСНОВНЫЕ ПОЛОЖЕНИЯ, ОПРЕДЕЛЕНИЯ И ПОНЯТИЯ Совокупность управляющих воздействий, направленных на то, чтобы действительный ход процесса соответствовал...
-
Хочу описать все плюсы и минусы использования традиционного подхода к организации рабочих мест с использованием персональных компьютеров и посмотреть,...
-
Операционная система Dell Wyse для тонких вычислений - Выбор оптимального решения для виртуализации
Wyse позволяет сделать выбор из четырех операционных систем для использования тонких клиентов в многопользовательских системах или в виртуализорованных...
-
Программный алгоритм визуальный гаусс В программу включены следующие процедуры: "gauss1", "gaussj", "New1Click", "Button1Click", "Button2Click",...
-
Основные компоненты - История создания и развития автоматизированных информационных систем
Основными компонентами информационной технологии, используемой в экспертной системе, являются (рис. 3.2.2): интерфейс пользователя, база знаний,...
-
Предложенный подход к решению задач исследования Используя в качестве основы присутствующее в наличии программное обеспечение, которое применимо к...
-
Классификации СППР - Система поддержки принятия решений
Для СППР отсутствует не только единое общепринятое определение, но и исчерпывающая классификация. Разные авторы предлагают разные классификации. На...
-
Возможность использования формул и функций является одним из важнейших свойств программы обработки электронных таблиц. Это, в частности, позволяет...
-
Анализ рисков по защите информации - Выбор оптимального решения для виртуализации
При разработанной аппаратной инфраструктуре, система реализуется таким образом, что если произойдет отключение электричества в здании, то тогда будут...
-
Поиск информации В проектах этого типа учащиеся должны использовать различные источники информации (электронные или бумажные) для решения задач. Такой...
-
Если в результате поиска на схеме по данным из таблицы будет найдено несколько экземпляров оборудования (т. е. с одинаковой маркировкой или...
-
Решения по пользовательскому интерфейсу в части серверного приложения (вебсайт) Для реализации требований к серверному приложению (Сайту), объединяющему...
-
Сетевое хранилище данных - Выбор оптимального решения для виртуализации
Сетевое хранилище представляет собой компьютер, который построен на произвольной архитектуре. Основной задачей является предоставление сервисов для...
-
Языки и системы программирования, их эволюция - Автоматизация решения задач пользователя
Язык программирования - это способ записи программ решения различных задач на ЭВМ в понятной для компьютера форме. Процессор компьютера непосредственно...
-
После выполнения задачи по Подбору и анализу литературы, настало время поиска и сравнительного анализа уже существующих решений задачи контроля...
-
Информационно-поисковые системы - Осуществление хранения и поиска документов
ПС с большим набором функций и возможностей обычно входят в состав СУБД и именуются информационно-поисковыми системами. Они также создаются и...
-
Входная информация разделяется на условно-постоянную и оперативно-учетную информацию. - Условно-постоянная информация включает в себя справочные данные о...
-
Продукт Лицензия VDI (на одного пользователя) Лицензия VDA и CAL(покупается каждый год) Лицензия MS Terminal Server и CAL(покупается один раз) Vmware...
-
Трудоемкость производство алгоритм excel Трудоемкость годовой производственной программы Трудоемкость по профессии и разряду, ч. 4145,00 Структура...
-
1. НА 7 ПК ИСПОЛЬЗУЕТСЯ microsoft Windows xp sp2. 2. на 1 используется Altlinux 5 3. Программы офисного назначения: A) Microsoft Office Excel 2003 B)...
-
Математическое обеспечение позволяет использовать методы автоматизированного поиска оптимальных вариантов при проектировании системы. Часто при решении...
-
Citrix XenDesktop - Выбор оптимального решения для виртуализации
Представляет собой решение для виртуализации рабочего стола и приложений Windows в услугу по запросу, которая доступна пользователю из любого места и по...
-
Доставка ОС и приложений, Облачные вычисления - Выбор оптимального решения для виртуализации
Доставка ОС и приложений является мощным третьим вариантом в области виртуализации. Хотя приложения в виртуальном представлении и клиентской...
Сравнение алгоритмов поиска оптимальных решений в агентных системах