СРАВНЕНИЕ АЛГОРИТМОВ ПОИСКА ОПТИМАЛЬНЫХ РЕШЕНИЙ В АГЕНТНЫХ СИСТЕМАХ

MАTCHING ALGORITHMS SEARCH FOR OPTIMAL SOLUTIONS IN AGENT SYSTEMS

Oksana Melikhova

candidate of Science, assistant professor, assistant professor of the Southern Federal University,

Russia, Taganrog

Andrey Grigorash

postgraduate of the Southern Federal University,

Russia, Taganrog

Sergey Dzhambinov

student of the Southern Federal University,

Russia, Taganrog

Vladimir Chumichev

student of the Southern Federal University,

Russia, Taganrog

Anatoly Gaidukov

student of the Southern Federal University,

Russia, Taganrog

АННОТАЦИЯ

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

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.