WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте

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

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

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

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

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

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

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

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

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

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

,

где:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Литература

Примечания

  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, MN (2002). “Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization”. Natural Computing. 1 (2—3): 235—306. DOI:10.1023/A:1016568309421.
  4. Particle Swarm Optimization by Maurice Clerc, ISTE, ISBN 1-905209-04-5, 2006.
  5. Karaboga, Dervis (2010) Artificial bee colony algorithm Scholarpedia, 5(3): 6915.
  6. de Castro, Leandro N. Artificial Immune Systems: A New Computational Intelligence Approach. Springer, 2002. — P. 57–58. ISBN 1852335947, 9781852335946.
  7. Altruism helps swarming robots fly better genevalunch.com, 4 May 2011.
  8. 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
  9. Shah-Hosseini, Hamed (2009). “The intelligent water drops algorithm: a nature-inspired swarm-based optimization algorithm”. International Journal of Bio-Inspired Computation. 1 (1/2): 71—79.
  10. R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2020
WikiSort.ru - проект по пересортировке и дополнению контента Википедии