Роевой интеллект

Роевой интеллект (РИ) (англ. Swarm intelligence) описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введён Херардо Бени и Ван Цзином в 1989 году, в контексте системы клеточных роботов. Однако ранее идея подробно рассмотрена Станиславом Лемом в романе «Непобедимый» (1964) и эссе «Системы оружия двадцать первого века, или Эволюция вверх ногами» (1983).

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

Применение роевых принципов в робототехнике называют групповой робототехникой, в то время как понятие «роевой интеллект» относится к более общему набору алгоритмов. «Роевое прогнозирование» применяется в решении некоторых задач прогнозирования.

Примеры алгоритмов

Метод роя частиц

Основная статья: Метод роя частиц

Метод роя частиц, МРЧ (англ. Particle Swarm Optimization, PSO) — метод численной оптимизации, для использования которого не нужно знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Шии, изначально предназначался для имитации социального поведения. Алгоритм был упрощен, и было отмечено, что он пригоден для выполнения оптимизации. Книга Кеннеди и Эберхарта описывает много философских аспектов МРЧ и так называемого роевого интеллекта. Большое исследование приложений МРЧ сделано Поле.

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

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

Основная статья: Муравьиный алгоритм

Муравьиный алгоритм (алгоритм оптимизации муравьиной колонии, англ. ant colony optimization, ACO) — один из эффективных полиномиальных алгоритмов для нахождения приближенных решений задачи коммивояжера, а также аналогичных задач поиска маршрутов на графах. Подход предложенный бельгийским исследователем Марко Дориго (Marco Dorigo).

Суть подхода заключается в анализе и использовании модели поведения муравьёв, ищущих пути от колонии до еды. В основе алгоритма лежит поведение муравьиной колонии — маркировка удачных дорог большим количеством феромона. Работа начинается с размещения муравьёв в вершинах графа (городах), затем начинается движение муравьёв — направление определяется вероятностным методом, на основании формулы:

$P_{i}={\frac {{l_{i}}^{q}\cdot {f_{i}}^{p}}{\sum _{k=0}^{N}{{l_{k}}^{q}\cdot {f_{k}}^{p}}}}$,

где:

$P_{i}$ — Вероятность перехода дорогой $i$,

$l_{i}$ — Длина $i$-ого перехода,

$f_{i}$ — Количество феромонов на $i$-ом переходе,

$q$ — Величина, определяющая «жадность» алгоритма,

$p$ — Величина, которая определяет «стадность» алгоритма і

$q+p=1$.

Пчелиный алгоритм

Основная статья: Алгоритм пчелиной колонии

Искусственный алгоритм пчелиной семьи (англ. artificial bee colony optimization, ABC) — алгоритм роя на основе мета-эвристического алгоритма, введённого Карабогом в 2005 году. Он имитирует поведение кормовых медоносных пчел. Алгоритм ABC состоит из трех этапов: рабочей пчелы, пчелы-надзирателя, и пчелы-разведчика. Пчелы используют алгоритм локального поиска в окрестности решений, выбранных на основе детерминированного отбора рабочими пчелами и вероятностного отбора пчелами-надзирателями. Пчела-разведчик выполняет отказ от истощенных источников питания в кормовом процессе. По этой аналогии решения, которые больше не полезны для поиска решения, отбрасываются и добавляются новые решения (по аналогии с исследованием новых регионов в поиске источников).

Искусственная иммунная система

Основная статья: Искусственная иммунная система

Искусственная иммунная система (ИИС) — это адаптивная вычислительная система, использующая модели, принципы, механизмы и функции, описанные в теоретической иммунологии, которые применяются для решения прикладных задач.

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

Алгоритм серых волков

Основная статья: Алгоритм серых волков

Алгоритм летучих мышей

Основная статья: Алгоритм летучих мышей

Алгоритм гравитационного поиска

Основная статья: Алгоритм гравитационного поиска

Алгоритм гравитационного поиска (англ. Gravitational Search Algorithm, GSA) — алгоритм поиска, основанный на законе всемирного тяготения и понятиях массового взаимодействия. Алгоритм основывается на теории притяжения из физики Ньютона. В алгоритме в качестве поисковых агентов используются гравитационные массы.

В последние годы были разработаны различные эвристические алгоритмы оптимизации. Многие из этих алгоритмов основаны на природных явлениях. Если сравнивать алгоритм гравитационного поиска с другими алгоритмами, то данный алгоритм - один из самых эффективных в решении различных задач оптимизации нелинейных функций.

Алгоритм альтруизма

Основная статья: Алгоритм альтруизма

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

Светляковый алгоритм

Основная статья: Светляковый алгоритм

Алгоритм капель воды

Основная статья: Алгоритм капель воды

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

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

Метод формирования реки

Основная статья: Метод формирования реки

Метод самоходных частиц

Основная статья: Метод самоходных частиц

Стохастический диффузионный поиск

Основная статья: Стохастический диффузионный поиск

Многороевая оптимизация

Основная статья: Многороевая оптимизация

Алгоритм кукушки

Основная статья: Алгоритм кукушки

Алгоритм кукушки (Cuckoo search) представляет собой оптимизированный алгоритм, разработанный Ян Синьшэ (Xin-She Yang) и Суашем Дебом (Suash Deb) в 2009 году.

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

Некоторые виды кукушек, такие как гнездовые паразиты с Нового мира, например полосатая или четырёхкрылая кукушка (Tapera naevia), эволюционировали таким образом, что самки очень часто специализируются на имитации цветов и структуры яиц избранных видов птиц-хозяев.

Оптимизация передвижением бактерий

Основная статья: Оптимизация передвижением бактерий

См. также

• Групповая робототехника
• Микробный интеллект

Литература

• Саймон Д. Алгоритмы эволюционной оптимизации. — М.: ДМК Пресс, 2020. — 940 с. — ISBN 978-5-97060-812-8.
• Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 2009. — 375 с.
• Миллер, П. Роевой интеллект: Муравьи, пчелы и птицы способны многому нас научить// National Geographic Россия. — 2007. — № 8. — С. 88—107.
• Swarm Intelligence: From Natural to Artificial Systems by Eric Bonabeau, Marco Dorigo and Guy Theraulaz. (1999) ISBN 0-19-513159-2, complete bibliography
• Turtles, Termites, and Traffic Jams: Explorations in Massively Parallel Microworlds by Mitchel Resnick. ISBN 0-262-18162-2
• Swarm Intelligence by James Kennedy and Russell C. Eberhart. ISBN 1-55860-595-9
• Fundamentals of Computational Swarm Intelligence by Andries Engelbrecht. Wiley & Sons. ISBN 0-470-09191-6
• Nanocomputers and Swarm Intelligence by Jean-Baptiste Waldner, ISTE, ISBN 9781847040022, 2007.
• Miller, Peter (July 2007), Swarm Theory, National Geographic Magazine, <http://www7.nationalgeographic.com/ngm/0707/feature5/>  Архивная копия от 10 ноября 2007 на Wayback Machine
• Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff, Article at IEEE Computer Society
• - «From Ants to People: an Instinct to Swarm» — NY Times, 11-13-07
• Swarm Intelligence (Journal) Chief Editor: Marco Dorigo. Springer New York. ISSN 1935-3812 (Print) 1935-3820 (Online) [1]
• Eva Horn, Lucas Marco Gisi (Ed.): Schwärme — Kollektive ohne Zentrum. Eine Wissensgeschichte zwischen Leben und Information, Bielefeld: transcript 2009. ISBN 978-3-8376-1133-5

Примечания