Роевой интеллект и его наиболее распространённые методы реализации

Вданной статье мы хотели бы описать роевой интеллект и его различные методы. Задачей анализа всевозможных методов роевого интеллекта является сравнение трёх его наиболее популярных способов реализации. Особый акцент сделан на муравьином, пчелином алгоритмах и методе роя частиц. Рассмотрены их особенности, сферы применения и математический аппарат, их реализующий. Кроме того, приведено краткое описание некоторых иных, менее популярных, алгоритмов роевого интеллекта. На основании полученных данных в конце делается вывод о преимуществах перед другими способами реализации, даётся краткое заключение о перспективах развития, а также подведён некий итог разнообразным методам роевого интеллекта.

Ключевые слова: искусственный интеллект, artificial intelligence, роевой интеллект, swarm intelligence, метод роя частиц, particle swarm optimization, муравьиный алгоритм, ant colony optimization, метод пчелиного улья, artificial bee colony optimization

Понятие роевого интеллекта все теснее переплетается с алгоритмами обработки и оптимизации больших количеств и потоков информации. И для проверки актуальности роевого интеллекта в наше время были поставлены следующие цели:

1. Рассмотреть основные алгоритмы роевого интеллекта;
2. Провести сравнительные анализ методов реализации РИ;
3. Проверить актуальность развития алгоритмов реализации.

Ещё давным-давно люди стали интересоваться так называемым “роевым поведением” — каким образом птицы летят на юг огромными косяками, не сбиваясь с курса. Как огромные колонии муравьёв работают так слаженно и возводят структуры, по сложности не уступающие современным мегаполисам. Как пчёлы могут так точно определять и добывать в необходимом для всей колонии питание. Все эти большие группы животных/насекомых можно объединить одним общим словом — рой. Благо, человечество не стоит на месте и, развиваясь, люди стали изобретать компьютеры, при помощи которых инженеры стали моделировать “роевой интеллект” (РИ) — попытки сделать роботизированные, автоматические и автоматизированные рои. Хоть далеко не все попытки были успешными, но, тем не менее, они положили начало созданию РИ, заложив к его основанию некоторые фундаментальные правила. Одним из них является тот факт, что для роевого интеллекта необходимо большое (достаточно) количество агентов, способных взаимодействовать между собой и окружающей их средой локально. Наблюдая за различными естественными примерами роёв, человечество придумало различные модели РИ, чьё поведение основывалось на различных путях взаимодействия с окружающей средой и между собой.

Стоит так же отметить, что непосредственно такой термин как “Роевой интеллект” был введён Ван Цзином и Херардо Бени в 1989 году. Так же модель подразумевает наличие так называемой “многоагентная система”, которая определяется как система, состоящая из множества интеллектуальных агентов — программ, способных самостоятельно на протяжении некого, достаточно длительного промежутка времени, выполнять поставленную задачу.

Предлагаем взглянуть немного подробнее на разнообразные методы реализации роевого интеллекта на рис. 1:

Рис. 1. Общий график методов роевого интеллекта

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

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

– теория иммунной сети;

– теория клональной селекции.

Другие алгоритмы наименее всего распространены и редко используются, поэтому мы лишь перечислим некоторые из них:

– метод капель воды, находящий либо наиболее близкие, либо наиболее оптимальные “пути для воды”, подобно рекам;

– алгоритм кукушки — основан на паразитировании, подобно тому, как некоторые виды кукушек откладывали яйца в чужие гнёзда, со временем научившись имитировать цвета чужих яиц;

– метод альтруизма, основанный на том, что каждый агент “заботится” об окружающих, не обращая внимания на себя;

– метод гравитационного поиска — заключён в соблюдении закона всемирного тяготения (все тела притягиваются друг к другу), а именно в поиска наиболее качественных, “тяжёлых”, агентов.

Метод роя частиц (МРЧ)

Данный метод является методом численной оптимизации, поддерживающий общее количество возможных решений, которые называются частицами или агентами, и перемещая их в пространстве к наилучшему найденному в этом пространстве решению, всё время находящемуся в изменении из-за нахождения агентами более выгодных решений.

Самая первая компьютерная модель МРЧ была придумана ещё в далёком 1986 Крейгом Рейнольдсом. Он, занимаясь созданием графической модели, придумал довольно простые правила поведения для частиц роя, действуя по которым, рой выглядел крайне похожим на реальный аналог птичьего роя.

Если проводить аналогию со стаей, то можно сказать, что все агенты алгоритма (частицы), в стае они могут быть птицами или рыбами, ставят для себя три довольно простых задачи:

– Все агенты должны избегать пересечения с окружающими их агентам;

– Каждая частица должна корректировать свою скорость в соответствии со скоростями окружающих её частиц;

– Каждый агент должен стараться сохранять достаточно малое расстояние между собой и окружающими его агентами.

Рис. 2. Метод работы МРЧ

Как видно на рис.2, алгоритм роя частиц — итеративный процесс, постоянно находящийся в изменении. Для того, чтобы понять, как функционирует алгоритм МРЧ, можно рассмотреть область поиска в виде многомерного пространства с агентами нашего алгоритма. Изначально все агенты находятся в случайных местах пространства и со случайным вектором скорости. В каждой из точек, которую частица посещает, она рассчитывает заданную функцию и фиксирует наилучшее значение искомой функции. Так же все частицы знают местоположение наилучшего результата поиска во всём рое и с каждой итерацией агенты корректируют вектора своих скоростей и их направления, стараясь приблизиться к наилучшей точке роя и при этом быть поближе к своему индивидуальному максимуму. При этом постоянно происходит расчёт искомой функции и поиск наилучшего значения. На рис. 3 приведен пример работы МРЧ.

Рис. 3. Пример работы роя методом МРЧ

Концепцию данного алгоритма описывает формула, согласно которой корректируется модуль и направление скорости агентов.

⍵ — коэффициент инерции, определяющий баланс между тем, насколько широко будет “заходить” в исследовании агент и тем, насколько сильно агент будет желать остаться рядом с найденными ранее оптимальными решениями;

P_{best —} координаты наилучшей найденной агентом точкой;

g_best — координаты наилучшей роевой точки;

x — текущие координаты точки;

rnd() — случайный коэффициент, принимающий значение от 0 до 1;

c₁, c₂ — постоянные ускорения.

Изначально этот алгоритм применялся для исследований социального психолога, Кеннеди, но самое большое распространение этот алгоритм смог получить при решениях задач оптимизации различных нелинейно-многомерных уравнениях. Этот алгоритм в современном мире применяется в машинном обучении, для решений задач оптимизации и в различных точных и экспериментальных науках, таких как биоинженерия и т. д.

Муравьиный алгоритм

Оптимизационный алгоритм с подражанием колонии муравьев (далее, муравьиный алгоритм) ‒ один из самых эффективных алгоритмов для решения задач по поиску маршрутов в графах и по нахождению приблизительных решений для задачи коммивояжёра.

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

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

Рис. 4. Пример нахождения муравьями нового пути при появлении препятствия

Муравьиный алгоритм представим в виде следующего набора команд:

– Пока (не выполнены условия выхода):

1. Создание агентов;
2. Поиск подходящего решения;
3. Изменение феромона;
4. Вспомогательные действия (не обязательно).

Далее рассмотрим каждый шаг подробнее:

1. Создание агентов:

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

– Также указывается первоначальное значение феромона, чтобы значения не были нулевыми.

2. Поиск подходящего решения:

– Вероятность того, что произойдет переход из вершины i в j, можно определить по формуле: , где τ_ij(t) — уровень феромона, d_ij– эвристическое расстояние, — константные параметры.

– Если = 0, с большей вероятностью выберется ближайший город;

Необходим найденный экспериментальным способом компромисс между этими двумя величинами

3. Изменение феромона

– Уровень феромона изменяется по формуле:, где 𝝆 — интенсивность испарения, L_k(t) — цена текущего решения k-го муравья, Q — параметр, который имеет значение порядка цены оптимального решения, — феромон, который откладывается k-м муравьем, который использует ребро.

4. Вспомогательные действия: в основном используют алгоритмы локального поиска.

Алгоритм искусственной пчелиной колонии

Алгоритм искусственной пчелиной колонии (далее, пчелиный алгоритм) ‒ алгоритм роевого интеллекта, основан на имитации поведения колонии пчел, может использоваться в задачах оптимизации. Необходимым условием для его применения является наличие некоторого топологического расстояния ли его аналога на области решений.

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

Искусственная колония использует алгоритм схожий с добычей нектара медоносными пчелами. Вместо поля с цветами рассмотрим область решений. Вместо нектара используем критерии задачи оптимизации, целевую функцию. На каждой итерации алгоритма выбирается nb областей с лучшим значением целевой функции, они называются “лучшие”, из оставшихся выбирается еще ng лучших, называемых “перспективными”. Можно задать определенное минимальное расстояние между двумя соседними областями. В этом случае, при возникновении наложения, область с худшим значением целевой функции отсекается. Вместо нее выбирается другая область. Данные области запоминаются и при следующей итерации в них посылается определенное количество пчел.

Схема описанного алгоритма представлена на рис. 5.

Рис. 5. Схематичное изображение стратегии алгоритма

Работу алгоритма можно разбить на два этапа:

1. Инициализация

– В простейшем случае используется метод случайного перебора.

2. Локальный поиск

– После формирования списков лучших и перспективных областей, в их окрестности отправляются рабочие.

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

– В данном случае, в каждую область высылается фиксированное количество пчел, в зависимости от класса, которому принадлежит данная область.

– Каждую итерацию разведчики отправляются на новые области.

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

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

Заключение

В данной работе были рассмотрены основные используемые алгоритмы роевого интеллекта: метод роя частиц, муравьиный алгоритм, алгоритм искусственной пчелиной колонии. Был проведен их сравнительный анализ, в результате которого были выявлены основные сильные стороны методов, области применения а также перспективы развития каждого из трёх рассматриваемых. А так же кратко рассмотрены истории создания данных методов. Хотелось бы отметить, что все перечисленные в данной статье алгоритмы актуальны на сегодняшний день и несут в себе множество перспектив в развитии.

Литература:

1. Sabu m Thampi SWARM INTELLIGENCE // arxiv.org -
2. Алгоритм роя частиц // habrahabr.ru -
3. Григорьев И. В., Мустафина С. А. РЕАЛИЗАЦИЯ МЕТОДА РОЯ ЧАСТИЦ НА NVIDIA CUDA // Науч.Форум, 2014.
4. Алгоритм роя частиц. Описание и реализации на языках Python и C# // jenyay.net. 2011.
5. Аноп М. Ф., Катуева Е. В., Михаличук В. И. Алгоритмы роя пчел и частиц в задаче обеспечения надежности по постепенным отказам // Наука и Образование. — 2015. — № 1.
6. Лебедев Б. К., Лебедев В. Б. Размещение на основе метода пчелиной колонии // Известия ЮФУ. Технические науки.
7. Чураков М., Якушев А. Муравьиные алгоритмы // 2006.
8. Матренин П.В. Методы стохастической оптимизации: учебное пособие / П.В. Матренин, М.Г. Гриф, В.Г. Секаев // Новосибирск: Изд-во НГТУ, 2016. – 67 с.