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

ANALYSIS OF ALGORITHMS SEARCHING FOR SOLUTIONS IN AGENT-BASED 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

We give the concept of agent used in the modeling of artificial intelligence systems. Are the most well-known types of agents and search algorithms for the best solutions in agent-based systems. A comparison of search algorithms for optimal solutions, completeness and speed.

Ключевые слова: агент, поиск решений, информированный поиск, локальный максимум, алгоритм А*, пространство состояний.

Keywords: agent, search for solutions, informed search, a local maximum, the algorithm A *, the state space.

В теории искусственного интеллекта существует такое понятие как агент. Под агентом при этом подразумевается любая сущность, которая может воспринимать окружающую среду с помощью датчиков и взаимодействовать с нею с помощью специальных механизмов [1; 4]. Существует множество различных типов агентов, которые отличаются друг от друга не только исполнительными функциями, но и целями для которых они используются, начальной информацией и возможностями сбора данных. Существуют следующие типы агентов: простой рефлексивный агент; рефлексивный агент, основанный на модели; рефлексивный агент, основанный на полезности; рефлексивный агент, основанный на цели [5; 8; 9]. Для каждого агента существуют свои методы достижения целей, при этом используются известные алгоритмы поиска решений. Алгоритм поиска решений зависит от условия задачи, информации получаемой из внешней среды и из базы знаний. Принято алгоритмы поиска подразделять на два типа: неинформированный поиск и информированный поиск [2; 3]. Неинформированный поиск позволяет находить решения задач путем выполнения систематической выработки новых состояний и их проверки применительно к цели. В большинстве случаев неинформированный поиск не дает оптимальный результат, поэтому считается мало эффективным. Информированный поиск строится на выборе действия из знаний, которые относятся исключительно к искомой задаче [6; 7].

Рассмотрим довольно распространённый алгоритм поиска решений – «жадный» алгоритм. В этом алгоритме предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели, так как велика вероятность того, что это приведет к нужному решению [1; 5; 9]. При таком поиске оценка узлов производится с использованием только эвристической функции: f(n) = h(n). Суть данного алгоритма состоит в том, что на каждом шаге развертывается пространство состояний и определяется наилучшее по стоимости, после чего развертывается следующий уровень и так пока не дойдет до необходимой цели. При этом процедура минимизации функции h(n) восприимчива к фальстартам [2; 7; 8]. Алгоритм «жадного» поиска напоминает поиск в глубину, поскольку он действует также, то есть алгоритм идет по одному пути, и если заходит в тупик, то возвращается к предыдущим узлам. Алгоритм «жадного» поиска обладает теми же недостатками, что и алгоритм поиска в глубину, то есть алгоритм не является оптимальным. Кроме того, этот алгоритм не является полным, потому что идет по одному пути, отбрасывая остальное пространство возможных решений [4; 5; 6]. При таком алгоритме в худшем случае оценка временной и пространственной сложности составит О(b^m), где m – максимальная глубина пространства поиска. Но если будет использована подходящая эвристическая функция, то это сократит сложность алгоритма. Величина сокращения зависит от конкретной задачи и от самой функции [2; 3].

Рассмотрим следующий вид поиска решения – поиск А* (читается как «А звездочка») [1; 5]. В данном поиске применяется оценка узлов, объединяющая в себе стоимость достижения данного узла g(n) и стоимость прохождения от данного узла до цели h(n): f(n) = g(n) + h(n). Из этого следует следующее утверждение: поскольку g(n) определяет стоимость пути от начального узла до узла n, а функция h(n) определяет оценку стоимости наименее дорогостоящего пути от узла n до цели, то функция f(n) является оценкой стоимости наименее дорогостоящего пути решения, проходящего через узел n. То есть, при поиске наименее дорогостоящего решения нужно проверить узел с наименьшим значением f(n). Данная стратегия поиска является оптимальной и полной при удовлетворении некоторым условиям эвристической функции h(n). Анализ оптимальности поиска A* является несложным, особенно, если этот метод используется с алгоритмом поиска по первому наилучшему значению (Tree-Search) [3; 6]. В таком случае поиск A* является оптимальным, при условии, что h(n) представляет собой допустимую эвристическую функцию, т. е. при условии, что h(n) никогда не переоценивает стоимость достижения цели. Предположим, что появился неоптимальный целевой узел G₂, а стоимость оптимального решения равна С. В таком случае h(G₂) = 0 (справедливо для любого целевого узла) и формула принимает следующий вид: f(G₂) = g(G₂) + h(G₂) = g(G₂) > C. Если функция h(n) не переоценивает стоимость завершения этого пути решения, то справедлива следующая формула: f(n) = g(n) + h(n) ≤ C. Таким образом доказано, что если условие f(n)≤C<f(G₂) выполняется, то узел G₂ не развертывается и поиск A* должен вернуть оптимальное решение [2; 5]. Конечно, если бы вместо дополнительного алгоритма поиска Tree-Search использовался бы алгоритм поиска Graph-Search, то данное утверждение было бы ошибочным, поскольку такой вспомогательный алгоритм поиска не может отобразить путь к повторному состоянию, если он не был сформирован в первую очередь. Существует два способа устранения этого недостатка. Первый способ – это дополнить алгоритм так, чтобы он отбрасывал дорогостоящий путь при нахождении любых двух найденных путей к одному и тому же узлу. Второй способ решения данной проблемы состоит в обеспечении того, чтобы оптимальный путь к любому повторяющемуся состоянию всегда был первым из тех, по которым следует алгоритм, как в случае поиска по критерию стоимости. Простейшим способом сокращения потребностей в памяти для поиска А* состоит в применении эвристического поиска. Реализация этого метода привела к созданию алгоритма A* с итеративным углублением (Iterative-Deepening A* -IDA*) [7; 8]. Основное различие между данным алгоритмом и стандартным алгоритмом состоит в том, что условием останова развертывания служит f-стоимость (g+h), а не глубина. Алгоритм IDA* применяется для решения многих задач с единичными стоимостями этапов и позволяет уменьшить количество издержек, которые появляются из-за отсортированной очереди узлов [8; 9].

Рассмотрим следующий алгоритм поиска решения - рекурсивный поиск по первому наилучшему совпадению (Recursive Best-First Search – RBFS). Данный алгоритм является простым рекурсивным алгоритмом, в котором имитируется работа стандартного алгоритма в линейном пространстве [2; 6]. Структура данного алгоритма походит на структуру рекурсивного поиска в глубину, только в отличие от него, в данном алгоритме используется не бесконечное следование вниз по иерархии, а отслеживание наилучшего альтернативного значения f(n). Если текущий узел превышает данный предел, то на данном этапе рекурсия отменяется и начинается рекурсия с альтернативного пути. Алгоритм RBFS является немного более эффективным по сравнению с IDA*, но он также не лишен недостатка, связанного с частым повторным формированием узлов. RBFS является оптимальным алгоритмом, если его эвристическая функция h(n) допустима. Пространственная сложность данного алгоритма равна O(bd), но с временной сложностью появляются проблемы. Это связанно с тем, что временная сложность зависит от точности эвристической функции и от частоты смены наилучшего пути [3; 7]. RBFS может быть подвержен увеличению сложности из-за поиска по графам, поскольку данный алгоритм не может определять повторяющиеся состояния, то есть данный алгоритм может исследовать одно и тоже состояние несколько раз. Также весомым недостатком данного алгоритма является недостаток памяти. В отличие от алгоритма IDA* используется больше памяти. Память в алгоритме измеряется исключительно O(bd), то есть при доступе к большему количеству памяти, алгоритм все равно не сможет ею воспользоваться. Поэтому появились следующие два алгоритма, которые используют всю доступную память: первый алгоритм – это MA*(Memory-bounded A* – поиск A* с ограничением памяти) и SMA*(Simplified MA* – алгоритм является упрощенной версией поиска MA*). Алгоритм SMA* действует аналогично стандартному алгоритму А*, то есть в начале также развёртываются наилучшие листовые узлы до тех пор, пока есть свободная память. Как только память исчерпывается, алгоритм не может добавить новый узел, пока не удалит старый. Алгоритм удаляет наихудший узел, то есть узел с наибольшим значением f(n). Значение удаленного узла сохраняется в его родителе, таким образом он не полностью удаляется, а скорее забывается на некоторое время. Алгоритм возвращается к забытому узлу в том случае, если считает, что все остальные варианты являются худшими по сравнению с забытым. Данный алгоритм не работает в единственном случае, когда все листовые узлы равны, то есть нет худшего или лучшего результата, что может привести к тому, что будет удаляться один и тот же листовой узел, то есть алгоритм не сможет дать оптимальный ответ из-за недостатка объема памяти. Алгоритм SMA* является полным, то есть если d, глубина поверхностного целевого узла меньше, чем объем памяти. Также алгоритм оптимален, если достижимо оптимальное решение, в противном случае он возвращает наилучший результат [1]. С точки зрения практики данный алгоритм является одним из лучших алгоритмом поиска общего назначения, но при использовании его на сложных задачах он, алгоритм, обеспечивает переход от одного целевого узла к другому, что приводит к тому, что память иссякает. При таком подходе увеличивается время действия алгоритма, которого можно было бы избежать при использовании поиска A* при наличии неограниченной памяти, то есть становится невозможным использование алгоритма SMA*. Ограничение объема памяти делает некоторые задачи трудноразрешимыми с точки зрения времени вычисления [3].

Рассмотренные алгоритмы поиска решения были разработаны специально для агентов. Такие алгоритмы подходят для различных задач, но являются ли они полностью оптимальными сказать сложно. Агенты могут обучаться самостоятельно, при этом используется метод обучения, который опирается на важную концепцию, называемую пространством состояний, рассматриваемым на метауровне, или метауровневом пространстве состояний. Каждое состояние на метауровне отражает состояние программы, выполняющей поиск в пространстве состояний, рассматриваемом на уровне объектов, или в объектно-уровневом пространстве состояний [4; 5; 6]. Внутренним состоянием алгоритма А* является текущее дерево поиска, а каждое действие на метауровневом пространстве состояний представляет собой этап вычислений. Алгоритм метауровневого обучения способен накапливать опыт, который получает за счет выполнения неудачно развертываемых узлов, преобразовывать его и на его основе обучаться, что может помочь в дальнейшем избегать исследований бесперспективных поддеревьев. Целью обучения данного алгоритма является минимизация суммарной стоимости решения задачи, а также нахождение баланса между стоимостью пути и вычислительными издержками.

Все рассмотренные алгоритмы служат для систематического исследования пространств поиска. То есть пока алгоритм следует по одному пути, алгоритм хранит в памяти всю информацию об узлах уже исследованных и о путях неисследованных [2; 8]. Если путь к цели не интересен для агента, то есть не представляет ценности, то могут быть использованы алгоритмы локального поиска, в которых не требуются данные о путях, и, которые действуют с учетом единственного текущего состояния и переход предусматривается только в соседние состояния. Хотя сам алгоритм локального поиска не предусматривает исследования пространства, но он обладает двумя важными свойствами: первое – это огромный запас памяти, причем практически все время и второе – алгоритмы позволяют находить приемлемые решения. Кроме поиска целей алгоритм локального поиска является полезным средством решения чистых задач оптимизации, назначение которых состоит в поиске наилучшего значения с точки зрения целевой функции [2; 5; 7].

Рассмотрим один из алгоритмов локального поиска – поиск с восхождением к вершине. Данный алгоритм представляет собой обычный цикл, в котором постоянно происходит перемещение в направлении возрастания некоторого значения, т. е. подъем. Алгоритм заканчивает свою работу после достижения «пика» значений, которого не достигает ни одно из соседних состояний. В алгоритме не осуществляется прогнозирование за пределами состояний, которые являются соседними по отношению к текущему состоянию. К сожалению, поиск с восхождением к вершине часто приводит к тупиковой ситуации из-за наличия локальных максимумов. Локальный максимум это пик, который является более высоким по сравнению с соседними состояниями, но меньше чем глобальный максимум. Когда достигается локальный максимум, то поиск заходит в тупик, из которого больше нет пути, чтобы двигаться дальше [1].

Рассматривая причины, из-за которых алгоритм может привести поиск решения в тупик, приходим к выводу что большинство тупиковых ситуаций можно решить, если допустить при поиске движение в сторону, то есть переход к состоянию на той же вершине [2]. Это будет решением большинства проблем, хотя есть опасность попадания в бесконечные циклы, после того, как алгоритм достигнет ещё одного локального максимума, не являющегося уступом. Разработано множество вариантов поиска с восхождением к вершине. При стохастическом поиске с восхождением к вершине осуществляется выбор случайным образом одного из движений вверх, вероятность такого выбора может зависеть от крутизны движения вверх. Обычно этот алгоритм сходится медленнее по сравнению с вариантом, который предусматривает более высокий подъем. Также есть вариант поиска решения к вершине с выбором варианта, который реализует стохастический поиск с восхождением к вершине путем формирования приемников случайным образом, пока не будет сформирован приемник, лучший по сравнению с текущим [3]. Также существует реализация поиска решения с восхождением к вершине с перезапуском случайным образом. В этом алгоритме создаётся несколько сформированных состояний, по которым идет поиск. Если поиск решения достиг поставленной цели, то алгоритм прекращает свою работу, а если нет, то создается несколько новых состояний и продолжается поиск. Критерием выхода из алгоритма является нахождения оптимального решения.

Список литературы:

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.