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

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

Роевой интеллект (РИ) (англ. Swarm intelligence) описывает коллективное поведение децентрализованной самоорганизующейся системы. Рассматривается в теории искусственного интеллекта как метод оптимизации. Термин был введен Херардо Бени и Ван Цзином в 1989 году, в контексте системы клеточных роботов[1].

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

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

Примеры алгоритмов[править | править вики-текст]

Метод роя частиц[править | править вики-текст]

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

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

Муравьиный алгоритм[править | править вики-текст]

Муравьиный алгоритм (алгоритм оптимизации муравьиной колонии, англ. 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.

Пчелиный алгоритм[править | править вики-текст]

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

Искусственная иммунная система[править | править вики-текст]

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

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

Алгоритм серых волков[править | править вики-текст]

Алгоритм летучих мышей[править | править вики-текст]

Алгоритм гравитационного поиска[править | править вики-текст]

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

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

Алгоритм альтруизма[править | править вики-текст]

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

Светляковый алгоритм[править | править вики-текст]

Алгоритм капель воды[править | править вики-текст]

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

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

Метод формирования реки[править | править вики-текст]

Метод самоходных частиц[править | править вики-текст]

Стохастический диффузионный поиск[править | править вики-текст]

Многороевая оптимизация[править | править вики-текст]

Алгоритм кукушки[править | править вики-текст]

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

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

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

Оптимизация передвижением бактерий[править | править вики-текст]

См. также[править | править вики-текст]

Литература[править | править вики-текст]

Примечания[править | править вики-текст]

  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. Parsopoulos, KE (2002). «Recent Approaches to Global Optimization Problems Through Particle Swarm Optimization». Natural Computing 1 (2-3): 235–306. DOI:10.1023/A:1016568309421.
  3. Particle Swarm Optimization by Maurice Clerc, ISTE, ISBN 1-905209-04-5, 2006.
  4. Karaboga, Dervis (2010) Artificial bee colony algorithm Scholarpedia, 5(3): 6915.
  5. de Castro Leandro N. Artificial Immune Systems: A New Computational Intelligence Approach. — Springer, 2002. — P. 57–58. — ISBN 1852335947, 9781852335946.
  6. Altruism helps swarming robots fly better genevalunch.com, 4 May 2011.
  7. 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
  8. 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.
  9. R. B. Payne, M. D. Sorenson, and K. Klitz, The Cuckoos, Oxford University Press, (2005).