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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

[править | править код]

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

[править | править код]

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

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

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

[править | править код]

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

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

,

где:

 — Вероятность перехода дорогой ,
 — Длина -ого перехода,
 — Количество феромонов на -ом переходе,
 — Величина, определяющая «жадность» алгоритма,
 — Величина, которая определяет «стадность» алгоритма і
.

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

[править | править код]

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

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

[править | править код]

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

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

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

[править | править код]

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

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

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

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

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

[править | править код]

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

[править | править код]

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

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

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

[править | править код]

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

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

[править | править код]

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

[править | править код]

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

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

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

[править | править код]

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

[править | править код]

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

[править | править код]

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

[править | править код]

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

[править | править код]

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

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

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

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

[править | править код]

Литература

[править | править код]
  • Саймон Д. Алгоритмы эволюционной оптимизации. — М.: ДМК Пресс, 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 Архивная копия от 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

Примечания

[править | править код]
  1. 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)
  2. В том числе в главе «Гипотеза Лауды» присутствует фраза «рой преобразуется в такой вот „тучемозг“» (rój układa się w ten jakiś „chmuromózg”).
  3. Parsopoulos, KE; Vrahatis, M. N. Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization (англ.) // Natural Computing[англ.] : journal. — 2002. — Vol. 1, no. 2—3. — P. 235—306. — doi:10.1023/A:1016568309421.
  4. Particle Swarm Optimization Архивная копия от 22 февраля 2014 на Wayback Machine by Maurice Clerc, ISTE, ISBN 1-905209-04-5, 2006.
  5. Karaboga, Dervis (2010) Artificial bee colony algorithm Архивная копия от 3 апреля 2014 на Wayback Machine Scholarpedia, 5(3): 6915.
  6. de Castro, Leandro N.; Timmis, Jonathan. Artificial Immune Systems: A New Computational Intelligence Approach (англ.). — Springer, 2002. — P. 57—58. — ISBN 1852335947, 9781852335946.
  7. https://www.mql5.com/ru/users/joo Популяционные алгоритмы оптимизации: Оптимизация Стаей Серых Волков (Grey Wolf Optimizer - GWO). www.mql5.com (2 декабря 2022). Дата обращения: 19 июля 2023. Архивировано 25 марта 2023 года.
  8. Altruism helps swarming robots fly better Архивная копия от 15 сентября 2012 на Wayback Machine genevalunch.com, 4 May 2011.
  9. 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. doi:10.1371/journal.pbio.1000615
  10. Shah-Hosseini, Hamed. The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm (англ.) // International Journal of Bio-Inspired Computation : journal. — 2009. — Vol. 1, no. 1/2. — P. 71—79.
  11. R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).