Роевой интеллект (РИ) () описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введён и в 1989 году, в контексте системы клеточных роботовBeni, G., Wang, J. Swarm Intelligence in Cellular Robotic Systems, Proceed. NATO Advanced Workshop on Robots and Biological Systems, Tuscany, Italy, June 26-30 (1989). Однако ранее идея подробно рассмотрена Станиславом Лемом в романе «Непобедимый» (1964)В том числе в главе «Гипотеза Лауды» присутствует фраза «рой преобразуется в такой вот „тучемозг“» (rój układa się w ten jakiś „chmuromózg”). и эссе «Системы оружия двадцать первого века, или Эволюция вверх ногами» (1983).

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

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

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

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

Метод роя частиц, МРЧ () — метод численной оптимизации, для использования которого не нужно знать точного градиента оптимизируемой функции. МРЧ был доказан Кеннеди, Эберхартом и Шии, изначально предназначался для имитации социального поведения. Алгоритм был упрощен, и было отмечено, что он пригоден для выполнения оптимизации. Книга Кеннеди и Эберхарта описывает много философских аспектов МРЧ и так называемого роевого интеллекта. Большое исследование приложений МРЧ сделано ПолеParticle Swarm Optimization by Maurice Clerc, ISTE, ISBN 1-905209-04-5, 2006..

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

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

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

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

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

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

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

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

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

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

Алгоритм оптимизации серых волков (Gray Wolf Optimizer, GWO) является мета-эвристическим алгоритмом оптимизации, который был предложен С. Мирамуничем и Дж. Р. Мирамуничем в 2014 году. В основе этого алгоритма лежит имитация социального поведения и иерархии волков в природе.

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

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

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

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

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

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

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

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

Исследователи из Швейцарии разработали алгоритм, основанный на правиле Гамильтона семейной селекции. Алгоритм показывает, как альтруизм особи в рое может со временем развиваться и приведет к более эффективному поведению рояAltruism helps swarming robots fly better genevalunch.com, 4 May 2011.Waibel M, Floreano1 D and Keller L (2011) «A quantitative test of Hamilton’s rule for the evolution of altruism» PLoS Biology, 9(5): e1000615. .

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

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

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

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

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

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

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

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

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

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

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

Некоторые виды кукушек, такие как гнездовые паразиты из Нового Света, например полосатая или четырёхкрылая кукушка (Tapera naevia), эволюционировали таким образом, что самки очень часто специализируются на имитации цветов и структуры яиц избранных видов птиц-хозяевR. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005)..

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

См. также Групповая робототехника Микробный интеллект

Литература

Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 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.

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) 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

Примечания

* Категория:Алгоритмы оптимизации Категория:Эвристические алгоритмы