Интеллект роя агентов для работы с данными

В статье исследователей из Бельгии, Англии и США (авторы статьи D. Martens, B. Baesens и T. Fawcett) дается обзор и структурирование методов на основе интеллекта роя агентов в применении к обработке данных. Интеллект роя агентов является относительно новым направлением в области многоагентных систем и искусственного интеллекта, которое изучает возникновение коллективного мышления в группах простых агентов. Это направление основано на поведении в социуме, которое можно наблюдать в природе, например, в колониях муравьев, стаях птиц, косяках рыб и ульях пчел, где группа индивидуумов, возможности каждого из которых ограничены, может прийти к общему интеллектуальному решению сложных проблем, таких, как избежание столкновения с хищником и поиск кратчайшего пути. В системах, основанных на поведении роя, индивидуумы взаимодействуют локально друг с другом и с окружающей их средой. При этом рой изначально использует формы децентрализованного управления и самоорганизации для достижения своих целей. Например, муравьи общаются только косвенно, через окружающую среду, оставляя на пройденных ими путях пахучее вещество, называемое феромоном, которое улавливают другие муравьи. Основываясь на этих косвенных связях, колонии муравьев отыскивают кратчайшие пути между источником пищи и гнездом даже в случаях изменения окружающей среды и неудачи отдельных муравьев. Пчелы ищут новое место для их улья, отправляя нескольких разведчиков для поиска возможных потенциальных мест. Вернувшись, разведчики выполняют специфический танец, который в кодах передает направление к найденному новому месту. Сила танца пчелы указывает на степень приоритета конкретного места. Как только достаточно разведчиков проголосует за одно и то же место, весь рой перемещается.

Успешное применение методов на основе интеллекта роя включает моделирование поведения агентов (например, большое количество сражающихся единиц в батальных сценах в фильме «Властелин Колец»), а также решение различных проблем оптимизации, таких как маршрутизация пакетов по Интернет-сетям, задача нахождения оптимального пути коммивояжера, планирование, робототехника и обработка данных.

Наиболее широкое применение получили такие методы, как оптимизация колонией муравьев (ACO, Ant Colony Optimization), метод роя частиц (PSO, Particle Swarm Optimization) и модели добычи (Prey models). На рис. 1 представлена обобщающая структура, которая характеризует алгоритмы обработки данных, основанные на интеллекте роя агентов. В этих методах можно выделить две категории задач: 1) выполнение эффективного поиска и 2) упорядочивание данных. В первой категории модельные агенты движутся в пространстве поиска и ищут наиболее подходящие решения, при этом используются методы АСО или PSO. Для метода ACO пространство поиска является дискретным, и решение определяется косвенным образом, используя путь, пройденный модельным муравьем. Для метода PSO пространство поиска непрерывно и местоположения решений в пространстве поиска обновляются в явном виде. Во второй категории используются сортировка по аналогии с поведением муравьев и модели добычи. Основное внимание в статье уделяется методу оптимизации колонией муравьев (АСО).

Рис. 1. Обобщающая структура методов на основе интеллекта роя агентов для обработки данных. Effective search – эффективный поиск: рой действует в пространстве решений. В этом подходе используются следующие методы: оптимизация колонией муравьев (ACO, Ant Colony Optimization) и метод роя частиц (PSO, Particle Swarm Optimization). Data organizing – организация данных: рой действует в двумерном пространстве характеристик (свойств, признаков). К этой категории относятся сортировка на основе поведения муравьев (Ant-based sorting) и модель добычи (Prey model).

Рис. 2. Выбор пути муравьями, использующими феромон.

Принципы поведения муравьев при поиске пищи продемонстрированы на рис. 2. Два муравья начинают поиски от их гнезда (слева) и ищут путь к источнику пищи (справа). Муравьи оставляют на своем пути феромон, который привлекает других муравьев. Последующие муравьи будут выбирать пути с более высоким уровнем феромона. Феромон испаряется, следовательно, те пути, по которым муравьи мало ходят, будут менее привлекательны в дальнейшем. Считаем, что изначально феромона нет на обеих тропах, так что сначала вероятности выбора одного из двух возможных путей равны. Предположим, один муравей выберет нижнюю тропу, а другой отправится по верхней тропе. Муравей, который выбрал нижнюю, более короткую тропу, вернется в гнездо быстрее, в результате чего на нижней тропе останется в два раза больше феромона, чем на верхней. То есть, вероятность того, что следующий муравей выберет нижний, короткий, путь, оставив еще больше феромона, будет в два раза выше, поэтому больше муравьев выберут этот путь. И, в конце концов, практически все муравьи будут выбирать короткий путь. Такая косвенная коммуникация между муравьями позволяет колонии муравьев с ограниченным объемом памяти и возможностями отдельных муравьев прийти к разумному решению сложных проблем.

Эти же идеи применяются в искусственных системах муравьев. Один из первых алгоритмов, который следовал принципам ACO, моделировал систему муравьев, решавшую известную задачу коммивояжера (traveling salesman problem). Эта NP-полная задача состоит в нахождении кратчайшего пути, следуя которому, нужно посетить каждый город из заданного множества лишь один раз. Граф связей городов соответствует карте городов. Каждый город на графе является узлом, а связь между городами – ребрами. Модельный муравей перемещается в один из ближайших, но не посещенных ранее, городов, оставляя за собой след феромона. При выборе следующего города учитывается как расстояние до него, так и количество феромона, оставленного на ребре графа между городами. В результате итеративной процедуры постепенно формируется достаточно короткий путь посещения всех городов.

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

Интересное приложение метода АСО – формирование логических правил для систем классификации данных.

В поведении некоторых видов муравьев наблюдается применение принципов сортировки. Чтобы навести порядок в гнезде, муравьи собирают в группы мертвых муравьев в так называемом захоронении. На рис. 3 показана динамика таких захоронений, сформированных муравьями типа Messor sancta: в течение нескольких часов беспорядочно рассеянные мертвые муравьи четко группируются в несколько захоронений. Такой процесс сортировки наблюдается и при кластеризации (группировании) личинок, где меньшие личинки помещаются ближе к центру, а более крупные направляются к краю кластера (группы).

Рис. 3. Беспорядочно рассеянные останки муравьев сгруппированы в захоронения в течение нескольких часов. Отражены различные этапы процесса группировки: 0, 3, 6 и 36 часов после начала эксперимента.

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

Рис. 4. Различные этапы кластеризации данных на основе поведения муравьев.

Стаи птиц и косяки рыб демонстрируют увлекательное скоординированное коллективное поведение. Птицы, перемещаясь в произвольном порядке, ищут себе пропитание и одновременно следят за кем-либо другим и тем, кто ближе к еде. Способность собираться в стаи имеет ряд преимуществ для индивидуумов: увеличивается эффективность поиска пищи, усовершенствуется избегание хищников, повышаются возможности спаривания. Вместе с каждым индивидуумом, использующим только локальную информацию, вся стая демонстрирует изменчивое когерентное (связное) движение, которое выглядит идеально синхронизированным. Такое подобное стае движение может быть смоделировано на базе трех основных принципов поведения, в которых используется только информация от соседей: 1) избегать столкновений с ближайшими особями из стаи, 2) подбирать скорость в соответствии со скоростями особей, движущимися рядом и 3) стараться оставаться на малом расстоянии от ближайших особей.

Метод роя частиц (PSO, Particle Swarm Optimization) был первоначально разработан для графического моделирования хореографии стаи птиц, в дальнейшем он был развит для различных прикладных задач. В то время как метод ACO разработан для решения дискретных задач оптимизации, метод PSO предназначен для решения непрерывных задач. В методе PSO каждая частица имеет определенное местоположение и скорость в пространстве поиска и, таким образом, характеризует определенное решение. Подобно птицам, перемещающимся в окружающей среде в поисках пищи или при уклонении от хищников, частицы пролетают через пространство поиска, изыскивая высококачественные решения.

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

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