что такое роевой интеллект
Коллективный разум бактерий или роевой интеллект
Приветствую тебя, коллективный хабраразум, поздравляю с Новым Годом! УРА!
Некоторое время назад я решил постичь всемогущий Actionscript 3.0. Дабы сразу опробовать этот инструмент, я взялся за написание небольшой программки, которая бы имитировала жизнь бактерий. Как мне пришла эта мысль в голову — точно уже не вспомню, но результат оказался для меня неожиданным и довольно интересным.
Под катом — много картинок и мало текста. Описание программки и пара опытов.
Суть проста — в ограниченном пространстве (500×500 пикселей) «живут» бактерии. Каждая бактерия изображается синим или красным пикселем на белом фоне в зависимости от принадлежности к синей или красной популяции. Сразу оговорюсь, что цвета здесь играют чисто декоративный характер. Красные бактерии живут так, будто нет синих и наоборот. 
Бактерия сама по себе примитивна. Она ползет в случайном направлении и случайным образом чуть-чуть изменяет свой вектор скорости.
Через случайный промежуток времени бактерия делится на две бактерии, при этом скорость «детей» наследуется от бактерии, их породившей (примитивная передача генов).
Если много бактерий скапливается в одном месте, то они начинают погибать (имитация нехватки пищи).
В программке предусмотрен режим (оставлять след), когда предыдущий кадр анимации не стирается, а новый рисуется поверх старого. Благодаря этому можно наблюдать маршруты, по которым движутся бактерии. Вот, как выглядит движение одной бактерии с последующим её делением: 
Но жизнь бактерий была бы прекрасна, если бы не было нас — ученых, которые жаждут исследований и опытов. Именно для нас, справа предусмотрены несколько инструментов влияния на жизнь в «чашке Петри».
Можно задать течение среды в какую-нибудь сторону, чтобы бактерии начало сносить: 
Можно закручивать бактерии в вихре, будто их сливают в унитаз 🙂 
Можно сделать, чтобы бактерии раскидывало в стороны от щелчка мыши: 
Так же, кликом мышки можно создавать новых бактерий по одной: 
Можно управлять скоростью течения времени, увеличивать его, замедлять или совсем останавливать: 
К сожалению, из-за оптимизации, при изменении этого параметра расчет количества ближайших бактерий работает не совсем точно.
Ну и уже известная настройка, стирать ли предыдущие кадры: 
Кнопка обновить стирает все предыдущие кадры один раз.
Приступаем к самому интересному — к опытам
Дадим бактериям расплодиться на всю территорию. К слову — внизу отображаются численности популяций.
После чего включим не очень сильное течение в сторону. Бактерий начнет сносить в угол, где они будут погибать из-за «нехватки пищи». Но всякий раз оказывается, что есть бактерии, которые двигаются против течения. Их не много, но их не сносит в гибельный угол и они порождают таких же, как они сами — стойких к новым условиям. Через некоторое время всю отведенную территорию займет новая популяция, средняя скорость которой будет направлена против течения. Тем самым все будет выглядеть так, будто течения нет СОВСЕМ.
Отключаем течение — бактерий начинает сносить в обратную сторону. Но снова выживают «сильнейшие»…
Таким образом, можно говорить о некотором привыкании к новым внешним условиям. При этом алгоритм привыкания не был заложен изначально.
Бактерии даже могут привыкнуть к не очень сильному «вихрю — смыву в унитаз», или наоборот к разбрасыванию «смерчем» в разные стороны.
Возможно, привыкание, приспособление реальных организмов в некоторых случаях имеет похожую природу. Может быть благодаря этим механизмам у нас сейчас 4 руки и три глаза.
А может быть, тайна искусственного интеллекта кроется за системами роевого интеллекта. Скоро узнаем!
Собственно сама flash-программка:
вконтакте
Для тех, кто не зарегистрирован вк:
тут
P.S.
Для тех, кого не тронула «интеллектуальность» бактерий: можно просто пофантазировать и порисовать интересные картинки: 
P.P.S
Перед написанием этого топика я немного поискал общей информации по похожим темам.
Роевой интеллект в Википедии
Немного практического применения:
Алгоритм роя частиц на Хабре
Муравьиные алгоритмы на Хабре
UPD
добавляю исходники. FlashDevelop.
Код кривоватый т.к. писал с целью разобраться в AS3, однако довольно понятный
исходники
Роевой интеллект
Системы роевого интеллекта, как правило, состоят из множества агентов (Многоагентная система) локально взаимодействующих между собой и с окружающей средой. Сами агенты обычно довольно просты, но все вместе, локально взаимодействуя, создают так называемый роевой интеллект. Примером в природе может служить колония муравьев, рой пчел, стая птиц, рыб…
Содержание
Примеры алгоритмов
Аппроксимационные алгоритмы, представленные ниже, относятся к классу метаэвристик. Существуют их вариации как для задач одно-, так и многокритериальной оптимизации.
См. также
Литература
Примечания
Полезное
Смотреть что такое «Роевой интеллект» в других словарях:
Вычислительный интеллект — (англ. Computational intelligence (CI)) ответвление искусственного интеллекта. Как альтернатива классическому искусственному интеллекту, основанному на строгом логическом выводе, он опирается на эвристические алгоритмы, используемые,… … Википедия
Искусственный интеллект — Запрос «ИИ» перенаправляется сюда; см. также другие значения. Искусственный интеллект (ИИ, англ. Artificial intelligence, AI) наука и технология создания интеллектуальных машин, особенно интеллектуальных компьютерных программ. ИИ… … Википедия
Игровой искусственный интеллект — (англ. Game artificial intelligence) набор программных методик, которые используются в компьютерных играх для создания иллюзии интеллекта в поведении персонажей, управляемых компьютером. Игровой ИИ, помимо методов традиционного… … Википедия
Групповая робототехника — Группа роботов IRobot Create в Технологическом институте Джорджии. Групповая робототехника представляет собой новый подход к координации систем многих роботов, которые с … Википедия
Мягкие вычисления — Мягкие вычисления термин, введенный Лотфи Заде в 1994 году[1], обозначающий совокупность неточных, приближенных методов решения задач, зачастую не имеющих решение за полиномиальное время. Такие задачи возникают в области биологии, медицины … Википедия
Тест Тьюринга — Стандартная интерпретация теста Тьюринга Тест Тьюринга эмпирический тест, идея которого была предложена Аланом Тьюрингом в статье «Вычислительные машины и разум» (англ. … Википедия
Естественная информатика — это научное направление, изучающее процессы обработки информации, протекающие в природе, мозге и человеческом обществе. Она опирается на такие классические научные направления, как теории эволюции, морфогенеза и биологии развития, системные… … Википедия
Перл, Джуда — Джуда Перл Judea Pearl Дата рождения: 1936 год(1936) Место рождения: Тель Авив, Израиль Страна … Википедия
Поспелов, Дмитрий Александрович — В Википедии есть статьи о других людях с такой фамилией, см. Поспелов. Дмитрий Александрович Поспелов Дата рождения: 19 декабря 1932(1932 12 19) (80 лет) Научная сфера: Искусственный интеллект и интеллектуальные системы Альма матер … Википедия
Искусственная нейронная сеть — У этого термина существуют и другие значения, см. Нейронная сеть (значения). Схема простой нейросети. Зелёным цветом обозначены входные нейроны, голубым скрытые нейроны, жёлтым выходной нейрон … Википедия
Роевой интеллект
Системы роевого интеллекта, как правило, состоят из множества агентов (боидов) локально взаимодействующих между собой и с окружающей средой. Идеи поведения, как правило, исходят от природы, а в особенности, от биологических систем. Каждый боид следует очень простым правилам и, несмотря на то, что нет какой-то централизованной системы управления поведения, которая бы указывала каждому из них на то, что ему следует делать, локальные и, в некоторой степени, случайные взаимодействия приводят к возникновению интеллектуального группового поведения, неконтролируемого отдельными боидами. Точное определение роевого интеллекта всё еще не сформулировано. В целом, РИ должен представлять собой многоагентную систему, которая бы обладала самоорганизующимся поведением, которое, суммарно, должно проявлять некоторое разумное поведение.
Применение роевых принципов в робототехнике называют групповой робототехникой, в то время как понятие «роевой интеллект» относится к более общему набору алгоритмов. «Роевое прогнозирование» применяется в решении некоторых задач прогнозирования.
Связанные понятия
Упоминания в литературе
Связанные понятия (продолжение)
В обучении машин и распознавании образов признак — это индивидуальное измеримое свойство или характеристика наблюдаемого явления. Выбор информативных, отличительных и независимых признаков является критическим шагом для эффективных алгоритмов в распознавании образов, классификации и регрессии. Признаки обычно являются числовыми, но структурные признаки, такие как строки и графы, используются в синтаксическом распознавании образов.
Сети адаптивного резонанса — разновидность искусственных нейронных сетей, основанная на теории адаптивного резонанса Стивена Гроссберга и Гейла Карпентера. Включает в себя модели обучения с учителем и без учителя, которые используются при решении задач распознавания образов и предсказания.
Под гибридной интеллектуальной системой (ГиИС) принято понимать систему, в которой для решения задачи используется более одного метода имитации интеллектуальной деятельности человека. Таким образом ГиИС — это совокупность.
Алгоритм роя частиц
Введение
Стая птиц представляет собой прекрасный пример коллективного поведения животных. Летая большими группами, они почти никогда не сталкиваются в воздухе. Стая двигается плавно и скоординировано, словно ей кто-то управляет. А любой, кто вешал в своем дворе кормушку, знает, что спустя несколько часов его найдут все птицы в округе.
Дело тут отнюдь не в вожаке, отдающем приказы – в стаях многих видов птиц его просто нет. Как и колония муравьев или пчел, стая представляет собой роевой интеллект. Птицы в ней действуют согласно определенным – довольно простым – правилам. Кружа в небе, каждая из птиц следит за своими сородичами и координирует свое движение согласно их положению. А найдя источник пищи, она оповестит их об этом.
На последнем факте следует остановиться подробнее, поскольку он играет одну из ключевых ролей в рассматриваемом методе оптимизации. Причины такого «альтруизма» птиц (и других животных, действующих сходным образом) являлись предметом исследования многих социобиологов. Одним из наиболее популярных объяснений этого феномена является то, что преимущества от такого поведения каждой особи стаи больше, чем такие очевидные недостатки, как необходимость борьбы за найденную пищу с другими особями.
Источники пищи обычно расположены случайным образом, поэтому в одиночестве птица вполне может погибнуть, не найдя ни один в течение долгого времени. Однако если все птицы будут «играть по правилам», делясь с сородичами информацией о находках, то шансы каждой из них на выживание резко повышаются. Таким образом, будучи неэффективной для отдельной особи, такая стратегия является залогом эффективности стаи и вида в целом.
Boids
Наблюдение за птицами вдохновило Крейга Рейнольдса (Craig Reynolds) на создание в 1986 году компьютерной модели, которую он назвал Boids. Для имитации поведения стаи птиц, Рейнольдс запрограммировал поведение каждой из них в отдельности, а также их взаимодействие. При этом он использовал три простых принципа. Во-первых, каждая птица в его модели стремилась избежать столкновений с другими птицами. Во-вторых, каждая птица двигалась в том же направлении, что и находящиеся неподалеку птицы. В-третьих, птицы стремились двигаться на одинаковом расстоянии друг от друга.
Результаты первых же симуляций удивили самого создателя: несмотря на простоту лежащих в основе программы алгоритмов, стая на экране выглядела крайне правдоподобно. Птицы сбивались в группы, уходили от столкновений и даже хаотично метались точь-в-точь как настоящие.
Как специалист в области компьютерной графики, Крейг Рейнольдс был в первую очередь заинтересован визуальной стороной результатов созданной им имитации. Однако, в посвященной Boids статье он также отметил, что разработанная им поведенческая модель может быть расширена введением дополнительных факторов – таких, как поиск пищи или боязнь хищников [1].
Классический алгоритм роя частиц
В 1995 году Джеймс Кеннеди (James Kennedy) и Рассел Эберхарт (Russel Eberhart) предложили метод для оптимизации непрерывных нелинейных функций, названный ими алгоритмом роя частиц [2]. Вдохновением для них послужила имитационная модель Рейнольдса, а также работа Хеппнера (Heppner) и Гренадера (Grenader) на схожую тему [4]. Кеннеди и Эберхарт отметили, что обе модели основаны на управлении дистанциями между птицами – а, следовательно, синхронность стаи является в них функцией от усилий, которые птицы прилагают для сохранения оптимальной дистанции.
Разработанный ими алгоритм довольно прост и может быть реализован буквально в нескольких десятках строчек кода на любом высокоуровневом языке программирования. Он моделирует многоагентную систему, где агенты-частицы двигаются к оптимальным решениям, обмениваясь при этом информацией с соседями.
Текущее состояние частицы характеризуется координатами в пространстве решений (то есть, собственно, связанным с ними решением), а также вектором скорости перемещения. Оба этих параметра выбираются случайным образом на этапе инициализации. Кроме того, каждая частица хранит координаты лучшего из найденных ей решений, а также лучшее из пройденных всеми частицами решений – этим имитируется мгновенный обмен информацией между птицами.
На каждой итерации алгоритма направление и длина вектора скорости каждой из частиц изменяются в соответствие со сведениями о найденных оптимумах:
,
где – вектор скорости частицы ( 
– его i-ая компонента), , – постоянные ускорения, – лучшая найденная частицей точка, – лучшая точка из пройденных всеми частицами системы, – текущее положение частицы, а функция возвращает случайное число от 0 до 1 включительно.
После вычисления направления вектора , частица перемещается в точку 
. В случае необходимости, обновляются значения лучших точек для каждой частицы и для всех частиц в целом. После этого цикл повторяется.
Модификации классического алгоритма
Алгоритм роя частиц появился относительно недавно, однако различными исследователями уже был предложен целый ряд его модификаций, и новые работы на эту тему не перестают публиковаться. Можно выделить несколько путей улучшения классического алгоритма, реализованных в большинстве из них. Это соединение алгоритма с другими алгоритмами оптимизации, уменьшение вероятности преждевременной сходимости путем изменения характеристик движения частиц, а также динамическое изменение параметров алгоритма во время оптимизации. Ниже рассмотрены наиболее примечательные из модификаций.
LBEST
Позже в том же 1995 году была опубликована статья Кеннеди и Эберхарта, в которой они назвали оригинальный алгоритм “GBEST”, поскольку он использует глобальное лучшее решение (global best) для формирования векторов скоростей, а также предложили его модификацию, названную ими “LBEST”. При обновлении направления и скорости движения частицы в LBEST используют информацию о решениях соседних с ними частиц:
,
где – лучший результат среди частицы и ее соседей. Соседними считаются либо частицы, отличающихся от данной индексом не более чем на некоторое заданное значение, либо частицы, расстояние до которых не превышает заданного порога.
Данный алгоритм более тщательно исследует пространство поиска, однако является более медленным, чем оригинальный. При этом, чем меньшее число соседей учитывается при формировании вектора скорости, тем ниже скорость сходимости алгоритма но тем эффективней он избегает субоптимальных решений.
Inertia Weighted PSO
В 1998 году Юхи Ши (Yuhui Shi) и Рассел Эберхарт предложили модификацию, на первый взгляд совсем незначительно отличающуюся от классического алгоритма [5]. В своей статье Ши и Эберхарт заметили, что одной из главных проблем при решении задач оптимизации является баланс между тщательностью исследованием пространства поиска и скоростью сходимости алгоритма. В зависимости от задачи и характеристик поискового пространства в ней, этот баланс должен быть различным.
С учетом этого, Ши и Эберхарт предложили изменить правило обновления векторов скоростей частиц:
,
Коэффициент , названный ими коэффициентом инерции, определяет упомянутый баланс между широтой исследования и вниманием к найденным субоптимальным решениям. В случае, когда 1″/>, скорости частиц увеличиваются, они разлетаются в стороны и исследуют пространство более тщательно. В противном случае, скорости частиц со временем уменьшаются, и скорость сходимости в таком случае зависит от выбора параметров и .
Time-Varying Inertia Weighted PSO
В своей работе 1998 года, Ши и Эберхарт отметили, что инерция не обязательно должна быть положительной константой: она может изменяться во время работы алгоритма по линейному и даже нелинейному закону [5]. В статье 1999 года и более поздних работах они наиболее часто использовали линейный закон убывания, как достаточно эффективный и вместе с тем простой [6]. Тем не менее, разрабатывались и успешно применялись и другие законы изменения инерции.
Значение коэффициента инерции может как убывать, так и расти. При его убывании, частицы сначала исследуют область поиска экстенсивно, находя множество субоптимальных решений, и со временем все более концентрируются на исследовании их окрестностей. Возрастание инерции способствует сходимости алгоритма на поздних стадиях работы.
Canonical PSO
В 2002 году Марис Клер (Maurice Clerc) и Джеймс Кеннеди предложили свою модификацию алгоритма роя частиц, которая стала настолько популярной, что теперь ее принято называть каноническим алгоритмом роя частиц [7]. Он позволяет избавиться от необходимости «угадывать» подходящие значения регулируемых параметров алгоритма, контролируя сходимость частиц.
Клер и Кеннеди изменили способ вычисления векторов скоростей частиц, введя в него дополнительный множитель:
,
где , а коэффициент сжатия равен:
.
Такой подход гарантирует сходимость алгоритма без необходимости явно контролировать скорость частиц.
Fully Informed Particle Swarm
В своей работе 2004 года Руи Мендес (Rui Mendes), Джеймс Кеннеди и Жозе Невес (José Neves) заметили, что принятое в каноническом алгоритм роя частиц допущение о том, что на каждую из частиц влияет только наиболее успешная, не соответствует лежащим в его основе природным механизмам и, возможно, ведет к снижению эффективности алгоритма [8]. Они предположили, что из-за чрезмерного внимания алгоритма к единственному решению может быть потеряна важная информация о структуре пространства поиска.
Исходя из этого, они решили сделать все частицы «полностью информированными», то есть получающими информацию от всех соседних частиц. Для этого они изменили в каноническом алгоритме закон изменения скорости:
,
где – множество соседей частицы, 
– лучшая из пройденных k-ым соседом точек. – весовая функция, которая может отражать любую характеристику k-ой частицы, которая считается важной: значение целевой функции в точке, в которой она находится, дистанцию от нее до данной частицы и так далее.
Заключение
В первой статье, описывающей алгоритм роя частиц, Джеймс Кеннеди и Рассел Эберхарт высказывали идею использования алгоритм для имитации социального поведения – Кеннеди, как социального психолога, крайне привлекала эта идея [1]. Однако наибольшее распространение алгоритм получил в задачах оптимизации сложных многомерных нелинейных функций.
Алгоритм роя частиц широко применяется, в числе прочих, в задачах машинного обучения (в частности, для обучения нейросетей и распознавания изображений), параметрической и структурной оптимизации (форм, размеров и топологий) в области проектирования, в областях биохимии и биомеханики. По эффективности он может соперничать с другими методами глобальной оптимизации, а низкая алгоритмическая сложность способствует простоте его реализации.
Наиболее перспективными направлениями дальнейших исследований в данном направлении следует считать теоретические исследования причин сходимости алгоритма роя частиц и связанных с этим вопросов из областей роевого интеллекта и теории хаоса, комбинирование различных модификаций алгоритма для решения сложных задач, рассмотрение алгоритма роя частиц как многоагентной вычислительной системы, а также исследование возможностей включения в него аналогов более сложных природных механизмов.