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

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

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

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

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

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

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

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

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

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

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

<math>P_i=\frac{{l_i}^{q}\cdot {f_i}^{p}}{\sum_{k=0}^{N}{{l_k}^{q}\cdot {f_k}^{p}}}</math>,

где:

<math>P_i</math> — Вероятность перехода дорогой <math>i</math>,

<math>l_i</math> — Длина <math>i</math>-ого перехода,

<math>f_i</math> — Количество феромонов на <math>i</math>-ом переходе,

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

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

<math>q+p=1</math>.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

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

Литература

• Субботін С. О., Олійник А. О., Олійник О. О. Неітеративні, еволюційні та мультиагентні методи синтезу нечіткологічних і нейромережних моделей: Монографія / Під заг. ред. С. О. Субботіна. — Запоріжжя: ЗНТУ, 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, [bibnetwiki.org/wiki/Swarm_Intelligence 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
• [si.cs.up.ac.za Fundamentals of Computational Swarm Intelligence] by Andries Engelbrecht. Wiley & Sons. ISBN 0-470-09191-6
• [www.iste.co.uk/index.php?f=a&ACTION=View&id=194 Nanocomputers and Swarm Intelligence] by Jean-Baptiste Waldner, ISTE, ISBN 9781847040022, 2007.
• Miller, Peter (July 2007), "[www7.nationalgeographic.com/ngm/0707/feature5/ Swarm Theory]", National Geographic Magazine, <www7.nationalgeographic.com/ngm/0707/feature5/> 
• Swarms and Swarm Intelligence by Michael G. Hinchey, Roy Sterritt, and Chris Rouff, [www.computer.org/portal/site/computer/menuitem.5d61c1d591162e4b0ef1bd108bcd45f3/index.jsp?&pName=computer_level1_article&TheCat=1065&path=computer/homepage/April07&file=softtech.xml&xsl=article.xsl Article at IEEE Computer Society]
• [www.nytimes.com/2007/11/13/science/13traff.html?ei=5087&em=&en=2770422853e9f63e&ex=1195102800&pagewanted=print - «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) [www.springer.com/computer/artificial/journal/11721]
• 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

Отрывок, характеризующий Роевой интеллект

– И то, брат, – сказал он; и, сев, достал из ранца обрывок французского синего сукна и стал обвертывать им ногу. – С пару зашлись, – прибавил он, вытягивая ноги к огню.
– Скоро новые отпустят. Говорят, перебьем до копца, тогда всем по двойному товару.
– А вишь, сукин сын Петров, отстал таки, – сказал фельдфебель.
– Я его давно замечал, – сказал другой.
– Да что, солдатенок…
– А в третьей роте, сказывали, за вчерашний день девять человек недосчитали.
– Да, вот суди, как ноги зазнобишь, куда пойдешь?
– Э, пустое болтать! – сказал фельдфебель.
– Али и тебе хочется того же? – сказал старый солдат, с упреком обращаясь к тому, который сказал, что ноги зазнобил.
– А ты что же думаешь? – вдруг приподнявшись из за костра, пискливым и дрожащим голосом заговорил востроносенький солдат, которого называли ворона. – Кто гладок, так похудает, а худому смерть. Вот хоть бы я. Мочи моей нет, – сказал он вдруг решительно, обращаясь к фельдфебелю, – вели в госпиталь отослать, ломота одолела; а то все одно отстанешь…
– Ну буде, буде, – спокойно сказал фельдфебель. Солдатик замолчал, и разговор продолжался.
– Нынче мало ли французов этих побрали; а сапог, прямо сказать, ни на одном настоящих нет, так, одна названье, – начал один из солдат новый разговор.
– Всё казаки поразули. Чистили для полковника избу, выносили их. Жалости смотреть, ребята, – сказал плясун. – Разворочали их: так живой один, веришь ли, лопочет что то по своему.
– А чистый народ, ребята, – сказал первый. – Белый, вот как береза белый, и бравые есть, скажи, благородные.
– А ты думаешь как? У него от всех званий набраны.
– А ничего не знают по нашему, – с улыбкой недоумения сказал плясун. – Я ему говорю: «Чьей короны?», а он свое лопочет. Чудесный народ!
– Ведь то мудрено, братцы мои, – продолжал тот, который удивлялся их белизне, – сказывали мужики под Можайским, как стали убирать битых, где страженья то была, так ведь что, говорит, почитай месяц лежали мертвые ихние то. Что ж, говорит, лежит, говорит, ихний то, как бумага белый, чистый, ни синь пороха не пахнет.
– Что ж, от холода, что ль? – спросил один.
– Эка ты умный! От холода! Жарко ведь было. Кабы от стужи, так и наши бы тоже не протухли. А то, говорит, подойдешь к нашему, весь, говорит, прогнил в червях. Так, говорит, платками обвяжемся, да, отворотя морду, и тащим; мочи нет. А ихний, говорит, как бумага белый; ни синь пороха не пахнет.
Все помолчали.
– Должно, от пищи, – сказал фельдфебель, – господскую пищу жрали.
Никто не возражал.
– Сказывал мужик то этот, под Можайским, где страженья то была, их с десяти деревень согнали, двадцать дён возили, не свозили всех, мертвых то. Волков этих что, говорит…
– Та страженья была настоящая, – сказал старый солдат. – Только и было чем помянуть; а то всё после того… Так, только народу мученье.
– И то, дядюшка. Позавчера набежали мы, так куда те, до себя не допущают. Живо ружья покидали. На коленки. Пардон – говорит. Так, только пример один. Сказывали, самого Полиона то Платов два раза брал. Слова не знает. Возьмет возьмет: вот на те, в руках прикинется птицей, улетит, да и улетит. И убить тоже нет положенья.
– Эка врать здоров ты, Киселев, посмотрю я на тебя.
– Какое врать, правда истинная.
– А кабы на мой обычай, я бы его, изловимши, да в землю бы закопал. Да осиновым колом. А то что народу загубил.
– Все одно конец сделаем, не будет ходить, – зевая, сказал старый солдат.
Разговор замолк, солдаты стали укладываться.
– Вишь, звезды то, страсть, так и горят! Скажи, бабы холсты разложили, – сказал солдат, любуясь на Млечный Путь.
– Это, ребята, к урожайному году.
– Дровец то еще надо будет.
– Спину погреешь, а брюха замерзла. Вот чуда.
– О, господи!
– Что толкаешься то, – про тебя одного огонь, что ли? Вишь… развалился.
Из за устанавливающегося молчания послышался храп некоторых заснувших; остальные поворачивались и грелись, изредка переговариваясь. От дальнего, шагов за сто, костра послышался дружный, веселый хохот.
– Вишь, грохочат в пятой роте, – сказал один солдат. – И народу что – страсть!
Один солдат поднялся и пошел к пятой роте.
– То то смеху, – сказал он, возвращаясь. – Два хранцуза пристали. Один мерзлый вовсе, а другой такой куражный, бяда! Песни играет.
– О о? пойти посмотреть… – Несколько солдат направились к пятой роте.


Пятая рота стояла подле самого леса. Огромный костер ярко горел посреди снега, освещая отягченные инеем ветви деревьев.
В середине ночи солдаты пятой роты услыхали в лесу шаги по снегу и хряск сучьев.
– Ребята, ведмедь, – сказал один солдат. Все подняли головы, прислушались, и из леса, в яркий свет костра, выступили две, держащиеся друг за друга, человеческие, странно одетые фигуры.
Это были два прятавшиеся в лесу француза. Хрипло говоря что то на непонятном солдатам языке, они подошли к костру. Один был повыше ростом, в офицерской шляпе, и казался совсем ослабевшим. Подойдя к костру, он хотел сесть, но упал на землю. Другой, маленький, коренастый, обвязанный платком по щекам солдат, был сильнее. Он поднял своего товарища и, указывая на свой рот, говорил что то. Солдаты окружили французов, подстелили больному шинель и обоим принесли каши и водки.
Ослабевший французский офицер был Рамбаль; повязанный платком был его денщик Морель.
Когда Морель выпил водки и доел котелок каши, он вдруг болезненно развеселился и начал не переставая говорить что то не понимавшим его солдатам. Рамбаль отказывался от еды и молча лежал на локте у костра, бессмысленными красными глазами глядя на русских солдат. Изредка он издавал протяжный стон и опять замолкал. Морель, показывая на плечи, внушал солдатам, что это был офицер и что его надо отогреть. Офицер русский, подошедший к костру, послал спросить у полковника, не возьмет ли он к себе отогреть французского офицера; и когда вернулись и сказали, что полковник велел привести офицера, Рамбалю передали, чтобы он шел. Он встал и хотел идти, но пошатнулся и упал бы, если бы подле стоящий солдат не поддержал его.
– Что? Не будешь? – насмешливо подмигнув, сказал один солдат, обращаясь к Рамбалю.
– Э, дурак! Что врешь нескладно! То то мужик, право, мужик, – послышались с разных сторон упреки пошутившему солдату. Рамбаля окружили, подняли двое на руки, перехватившись ими, и понесли в избу. Рамбаль обнял шеи солдат и, когда его понесли, жалобно заговорил:
– Oh, nies braves, oh, mes bons, mes bons amis! Voila des hommes! oh, mes braves, mes bons amis! [О молодцы! О мои добрые, добрые друзья! Вот люди! О мои добрые друзья!] – и, как ребенок, головой склонился на плечо одному солдату.
Между тем Морель сидел на лучшем месте, окруженный солдатами.
Морель, маленький коренастый француз, с воспаленными, слезившимися глазами, обвязанный по бабьи платком сверх фуражки, был одет в женскую шубенку. Он, видимо, захмелев, обнявши рукой солдата, сидевшего подле него, пел хриплым, перерывающимся голосом французскую песню. Солдаты держались за бока, глядя на него.
– Ну ка, ну ка, научи, как? Я живо перейму. Как?.. – говорил шутник песенник, которого обнимал Морель.
Vive Henri Quatre,
Vive ce roi vaillanti –
[Да здравствует Генрих Четвертый!
Да здравствует сей храбрый король!
и т. д. (французская песня) ]
пропел Морель, подмигивая глазом.
Сe diable a quatre…
– Виварика! Виф серувару! сидябляка… – повторил солдат, взмахнув рукой и действительно уловив напев.
– Вишь, ловко! Го го го го го!.. – поднялся с разных сторон грубый, радостный хохот. Морель, сморщившись, смеялся тоже.
– Ну, валяй еще, еще!
Qui eut le triple talent,
De boire, de battre,
Et d'etre un vert galant…
[Имевший тройной талант,
пить, драться
и быть любезником…]
– A ведь тоже складно. Ну, ну, Залетаев!..
– Кю… – с усилием выговорил Залетаев. – Кью ю ю… – вытянул он, старательно оттопырив губы, – летриптала, де бу де ба и детравагала, – пропел он.
– Ай, важно! Вот так хранцуз! ой… го го го го! – Что ж, еще есть хочешь?
– Дай ему каши то; ведь не скоро наестся с голоду то.
Опять ему дали каши; и Морель, посмеиваясь, принялся за третий котелок. Радостные улыбки стояли на всех лицах молодых солдат, смотревших на Мореля. Старые солдаты, считавшие неприличным заниматься такими пустяками, лежали с другой стороны костра, но изредка, приподнимаясь на локте, с улыбкой взглядывали на Мореля.
– Тоже люди, – сказал один из них, уворачиваясь в шинель. – И полынь на своем кореню растет.
– Оо! Господи, господи! Как звездно, страсть! К морозу… – И все затихло.
Звезды, как будто зная, что теперь никто не увидит их, разыгрались в черном небе. То вспыхивая, то потухая, то вздрагивая, они хлопотливо о чем то радостном, но таинственном перешептывались между собой.

Х
Войска французские равномерно таяли в математически правильной прогрессии. И тот переход через Березину, про который так много было писано, была только одна из промежуточных ступеней уничтожения французской армии, а вовсе не решительный эпизод кампании. Ежели про Березину так много писали и пишут, то со стороны французов это произошло только потому, что на Березинском прорванном мосту бедствия, претерпеваемые французской армией прежде равномерно, здесь вдруг сгруппировались в один момент и в одно трагическое зрелище, которое у всех осталось в памяти. Со стороны же русских так много говорили и писали про Березину только потому, что вдали от театра войны, в Петербурге, был составлен план (Пфулем же) поимки в стратегическую западню Наполеона на реке Березине. Все уверились, что все будет на деле точно так, как в плане, и потому настаивали на том, что именно Березинская переправа погубила французов. В сущности же, результаты Березинской переправы были гораздо менее гибельны для французов потерей орудий и пленных, чем Красное, как то показывают цифры.
Единственное значение Березинской переправы заключается в том, что эта переправа очевидно и несомненно доказала ложность всех планов отрезыванья и справедливость единственно возможного, требуемого и Кутузовым и всеми войсками (массой) образа действий, – только следования за неприятелем. Толпа французов бежала с постоянно усиливающейся силой быстроты, со всею энергией, направленной на достижение цели. Она бежала, как раненый зверь, и нельзя ей было стать на дороге. Это доказало не столько устройство переправы, сколько движение на мостах. Когда мосты были прорваны, безоружные солдаты, московские жители, женщины с детьми, бывшие в обозе французов, – все под влиянием силы инерции не сдавалось, а бежало вперед в лодки, в мерзлую воду.