Рой интеллект - Swarm intelligence

Скопление разведки ( СИ ) является коллективное поведение в децентрализованные , самоорганизующихся систем, природных или искусственных. Концепция используется в работе над искусственным интеллектом . Выражение было введено Херардо Бени и Цзин Ван в 1989 году в контексте клеточных роботизированных систем.

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

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

Модели поведения роя

Боидс (Рейнольдс, 1987)

Boids - это программа искусственной жизни , разработанная Крейгом Рейнольдсом в 1986 году, которая имитирует стайное поведение птиц. Его статья на эту тему была опубликована в 1987 году в трудах конференции ACM SIGGRAPH . Название «боид» соответствует сокращенной версии «птицеподобный объект», который относится к птицеподобному объекту.

Как и большинство искусственных симуляторов жизни, Boids является примером эмерджентного поведения; то есть сложность Boids возникает из-за взаимодействия отдельных агентов (в данном случае boids), придерживающихся набора простых правил. Правила, применяемые в простейшем мире Boids, следующие:

• Разделение : бычок , чтобы избежать скученности местных flockmates
• выравнивание : держитесь к среднему курсу местных собратьев
• сплоченность : держитесь, чтобы двигаться к среднему положению (центру масс) местных сородичей

Могут быть добавлены более сложные правила, такие как избегание препятствий и поиск цели.

Самоходные частицы (Vicsek et al . 1995)

Самоходные частицы (SPP), также называемые моделью Vicsek , были введены в 1995 году Vicsek et al. как частный случай модели боидов, введенной в 1986 г. Рейнольдсом . Рой моделируется в SPP набором частиц, которые движутся с постоянной скоростью, но реагируют на случайные возмущения, принимая при каждом приращении среднее направление движения других частиц в их локальной окрестности. Модели SPP предсказывают, что роящиеся животные обладают определенными свойствами на уровне группы, независимо от типа животных в стае. Системы роения порождают эмерджентное поведение, которое проявляется во многих различных масштабах, некоторые из которых оказываются как универсальными, так и устойчивыми. В теоретической физике стало проблемой найти минимальные статистические модели, отражающие такое поведение.

Метаэвристика

Эволюционные алгоритмы (EA), оптимизация роя частиц (PSO), дифференциальная эволюция (DE), оптимизация колоний муравьев (ACO) и их варианты доминируют в области метаэвристики, вдохновленной природой . В этот список входят алгоритмы, опубликованные примерно до 2000 года. Большое количество более поздних метаэвристических методов, основанных на метафорах, начали привлекать критику в исследовательском сообществе за то, что они скрывают отсутствие новизны за сложной метафорой. Для алгоритмов, опубликованных с того времени, см. Список метаэвристик на основе метафор .

Метаэвристике не хватает уверенности в решении. Когда соответствующие параметры определены и когда достигается достаточная стадия сходимости, они часто находят решение, которое является оптимальным или близким к оптимальному - тем не менее, если оптимальное решение неизвестно заранее, качество решения неизвестно. Несмотря на этот очевидный недостаток, было показано, что эти типы алгоритмов хорошо работают на практике, были тщательно исследованы и разработаны. С другой стороны, этого недостатка можно избежать, рассчитав качество решения для особого случая, когда такой расчет возможен, и после такого прогона известно, что каждое решение, которое, по крайней мере, так же хорошо, как решение, имевшееся в частном случае, имеет, по крайней мере, уверенность в решении, которую имел особый случай. Одним из таких примеров является Ant вдохновил Монте - Карло алгоритм для минимальной обратной связи Arc Set , где это было достигнуто вероятностно с помощью гибридизации Монте - Карло алгоритма с Ant Colony Optimization техники.

Стохастический диффузионный поиск (Бишоп, 1989)

Впервые опубликованный в 1989 г. Стохастический диффузионный поиск (SDS) был первым метаэвристическим методом Swarm Intelligence. SDS - это агентно- вероятностный метод глобального поиска и оптимизации, который лучше всего подходит для задач, в которых целевая функция может быть разложена на несколько независимых частичных функций. Каждый агент поддерживает гипотезу, которая итеративно проверяется путем оценки случайно выбранной частичной целевой функции, параметризованной текущей гипотезой агента. В стандартной версии SDS такие частичные оценки функций являются двоичными, в результате чего каждый агент становится активным или неактивным. Информация о гипотезах распространяется среди населения через межагентское взаимодействие. В отличие от стигмергической коммуникации, используемой в ACO, в SDS агенты сообщают гипотезы с помощью стратегии индивидуальной коммуникации, аналогичной процедуре тандемного бега , наблюдаемой у Leptothorax acervorum . Механизм положительной обратной связи гарантирует, что со временем популяция агентов стабилизируется вокруг лучшего в мире решения. SDS - это одновременно эффективный и надежный алгоритм глобального поиска и оптимизации, который подробно описан математически. Недавняя работа включала объединение свойств глобального поиска SDS с другими алгоритмами разведки роя.

Оптимизация колонии муравьев (Дориго, 1992)

Оптимизация колонии муравьев (ACO), представленная Дориго в его докторской диссертации, представляет собой класс алгоритмов оптимизации , смоделированных на основе действий колонии муравьев . ACO - это вероятностный метод, полезный в задачах, связанных с поиском лучших путей через графы. Искусственные «муравьи» - агенты моделирования - находят оптимальные решения, перемещаясь по пространству параметров, представляющему все возможные решения. Природные муравьи откладывают феромоны, направляющие друг друга к ресурсам, исследуя окружающую среду. Смоделированные «муравьи» аналогичным образом записывают свое положение и качество своих решений, чтобы на более поздних итерациях моделирования находили больше муравьев для лучших решений.

Оптимизация роя частиц (Кеннеди, Эберхарт и Ши, 1995)

Оптимизация роя частиц (PSO) - это глобальный алгоритм оптимизации для решения проблем, в котором лучшее решение может быть представлено в виде точки или поверхности в n-мерном пространстве. Гипотезы строятся в этом пространстве и засеваются с начальной скоростью , а также каналом связи между частицами. Затем частицы перемещаются через пространство решений и оцениваются в соответствии с некоторым критерием пригодности после каждого временного шага. Со временем частицы ускоряются по направлению к тем частицам в своей коммуникационной группе, которые имеют лучшие значения пригодности. Основное преимущество такого подхода перед другими стратегиями глобальной минимизации, такими как имитация отжига, состоит в том, что большое количество элементов, составляющих рой частиц, делает метод впечатляюще устойчивым к проблеме локальных минимумов .

Искусственный интеллект роя (2015)

Искусственный интеллект роя (ИСР) - это метод усиления коллективного разума сетевых групп людей с использованием алгоритмов управления, смоделированных по образцу естественных роев. Эта технология, которую иногда называют «роением людей» или «ИИ роя», объединяет группы участников-людей в системы реального времени, которые обдумывают и объединяются в решениях как динамические рои, когда одновременно задают вопрос. бизнес-команды для составления высокоточных финансовых прогнозов, позволяющих спортивным фанатам опередить рынки ставок в Вегасе. ASI также использовался, чтобы группы врачей могли ставить диагнозы со значительно большей точностью, чем традиционные методы.

Приложения

Методы, основанные на Swarm Intelligence, могут использоваться во многих приложениях. Американские военные изучают методы роя для управления беспилотными автомобилями. Европейское космическое агентство думает о орбитальном роя для самосборки и интерферометрии. НАСА изучает возможность использования роевой технологии для картирования планет. В статье 1992 года М. Энтони Льюиса и Джорджа А. Бекей обсуждается возможность использования интеллекта роя для управления нанороботами внутри тела с целью уничтожения раковых опухолей. Напротив, аль-Рифаи и Эйбер использовали стохастический диффузионный поиск, чтобы помочь найти опухоли. Интеллект Swarm также применяется для интеллектуального анализа данных и кластерного анализа . Модели на основе муравьев являются еще одним предметом современной теории управления.

Маршрутизация на основе Ant

Также было исследовано использование интеллекта роя в телекоммуникационных сетях в форме маршрутизации на основе муравьев . Это было впервые предложено отдельно Дориго и др. и Hewlett Packard в середине 1990-х годов, когда существовало несколько вариантов. По сути, здесь используется таблица вероятностной маршрутизации, которая награждает / усиливает маршрут, успешно пройденный каждым «муравьем» (небольшим контрольным пакетом), наводняющим сеть. Было исследовано усиление маршрута в прямом, обратном направлении и в обоих направлениях одновременно: обратное усиление требует симметричной сети и связывает два направления вместе; вперед подкрепление награждает маршрут до того, как станет известен результат (но тогда нужно будет заплатить за кино, прежде чем узнаешь, насколько хорош фильм). Поскольку система ведет себя стохастически и, следовательно, не имеет повторяемости, существуют большие препятствия для коммерческого развертывания. Мобильные медиа и новые технологии могут изменить порог для коллективных действий из-за интеллекта роя (Rheingold: 2002, P175).

Расположение инфраструктуры передачи для сетей беспроводной связи - важная инженерная проблема, требующая решения конкурирующих задач. Требуется минимальный выбор мест (или участков) при условии обеспечения адекватного покрытия для пользователей. Алгоритм интеллекта роя, вдохновленный совсем другими муравьями, стохастический диффузионный поиск (SDS), был успешно использован для предоставления общей модели для этой проблемы, связанной с упаковкой кругов и покрытием множеств. Было показано, что SDS может применяться для определения подходящих решений даже для крупных проблемных случаев.

Авиакомпании также использовали маршрутизацию на основе муравьев при назначении прибывающих самолетов к выходам в аэропорт. В Southwest Airlines программа использует теорию роя или интеллект роя - идею о том, что колония муравьев работает лучше, чем одна. Каждый пилот ведет себя как муравей, ищущий лучшие ворота аэропорта. «Пилот на собственном опыте узнает, что лучше для него, и оказывается, что это лучшее решение для авиакомпании», - объясняет Дуглас А. Лоусон . В результате «колония» пилотов всегда направляется к воротам, к которым они могут быстро приехать и улететь. Программа может даже предупредить пилота о дублировании самолетов до того, как они произойдут. «Мы можем ожидать, что это произойдет, поэтому у нас будут ворота», - говорит Лоусон.

Симуляция толпы

Художники используют технологию роя как средство создания сложных интерактивных систем или моделирования толпы .

Экземпляры

В кинотрилогии «Властелин колец» во время боевых сцениспользовалась аналогичная технология, известная как Massive (программное обеспечение) . Технология Swarm особенно привлекательна, потому что она дешевая, надежная и простая.

Стэнли и Стелла в фильме « Ломая лед» был первым фильмом, в котором для рендеринга использовалась технология роя, реалистично изображающая движения групп рыб и птиц с использованием системы Boids.

В « Возвращении Бэтмена» Тима Бертона также использовалась технология роя для демонстрации движений группы летучих мышей.

Авиакомпании использовали теорию роя для моделирования посадки пассажиров в самолет. Исследователь Southwest Airlines Дуглас А. Лоусон использовал компьютерную симуляцию на основе муравьев с использованием всего шести правил взаимодействия для оценки времени посадки с использованием различных методов посадки (Miller, 2010, xii-xviii).

Рой людей

С помощью программного обеспечения-посредника, такого как платформа SWARM (формально unu) от Unanimous AI , сети распределенных пользователей могут быть организованы в «человеческие рои» посредством реализации систем управления с обратной связью в реальном времени. Как опубликовано Розенбергом (2015), такие системы реального времени позволяют группам участников-людей вести себя как единый коллективный разум, который работает как единое целое, чтобы делать прогнозы, отвечать на вопросы и вызывать мнения. Было показано, что такие системы, также называемые «искусственным интеллектом роя» (или фирменным названием Swarm AI), значительно усиливают человеческий интеллект, что приводит к ряду громких предсказаний с чрезвычайной точностью. Академическое тестирование показывает, что человеческие рои могут превзойти людей в различных прогнозах реального мира. Известно, что скопление людей использовалось для правильного предсказания суперфекта Кентукки Дерби с вероятностью 541 к 1 в ответ на вызов репортеров.

Медицинское использование роения людей - в 2018 году Медицинская школа Стэнфордского университета и Unanimous AI опубликовали исследования, показывающие, что группы врачей-людей, соединенные вместе алгоритмами роения в реальном времени, могут диагностировать заболевания с гораздо большей точностью, чем отдельные врачи или группы врачей. врачи работают вместе, используя традиционные методы краудсорсинга. В одном из таких исследований группам радиологов-людей, объединенных вместе с помощью платформы SWARM, была поставлена ​​задача диагностировать рентген грудной клетки, и они продемонстрировали снижение диагностических ошибок на 33% по сравнению с традиционными человеческими методами и на 22% улучшение по сравнению с традиционным машинным обучением. .

Грамматики роя

Ройные грамматики - это рой стохастических грамматик, которые можно развить для описания сложных свойств, таких как искусство и архитектура. Эти грамматики взаимодействуют как агенты, действующие в соответствии с правилами интеллекта роя. Такое поведение также может указывать на алгоритмы глубокого обучения , в частности, когда рассматривается отображение таких скоплений на нейронные цепи.

Роевое искусство

В серии работ al-Rifaie et al. успешно использовали два алгоритма интеллекта роя - один имитирует поведение одного вида муравьев ( Leptothorax acervorum ) при поиске пищи ( стохастический диффузионный поиск , SDS), а другой алгоритм имитирует поведение стаи птиц ( оптимизация роя частиц , PSO) - для описания новая стратегия интеграции, использующая свойства локального поиска PSO с глобальным поведением SDS. Результирующий гибридный алгоритм используется для набросков новых рисунков входного изображения, используя художественное противоречие между локальным поведением «стаи птиц» - когда они стремятся следовать входному эскизу - и глобальным поведением «муравьев, собирающих пищу» - поскольку они стремятся побудить стадо исследовать новые области холста. «Творчество» этой гибридной системы роя было проанализировано в философском свете «ризомы» в контексте метафоры Делёза «Орхидея и оса».

В более поздней работе al-Rifaie et al. «Swarmic Sketches and Attention Mechanism» представлен новый подход, использующий механизм «внимания» путем адаптации SDS для выборочного внимания к детализированным областям цифрового холста. Как только внимание роя привлекается к определенной линии на холсте, возможности PSO используются для создания «роевого наброска» наблюдаемой линии. Стаи перемещаются по цифровому холсту, пытаясь удовлетворить свои динамические роли - внимание к областям с более подробной информацией, - связанные с ними через их фитнес-функцию. Связывая процесс рендеринга с концепцией внимания, выполнение участвующих роев создает уникальный, неидентичный эскиз каждый раз, когда рои «художников» приступают к интерпретации входных линейных рисунков. В других работах, в то время как PSO отвечает за процесс создания набросков, SDS контролирует внимание роя.

В аналогичной работе «Swarmic Painting and Color Attention» нефотореалистичные изображения создаются с использованием алгоритма SDS, который в контексте этой работы отвечает за внимание к цвету.

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

Майкл Теодор и Николаус Коррелл используют интеллектуальные инсталляции роя, чтобы исследовать, что нужно, чтобы инженерные системы выглядели реалистично.

Известные исследователи

Смотрите также

использованная литература

дальнейшее чтение

• Бонабо, Эрик; Дориго, Марко; Тераулаз, Гай (1999). Ройный интеллект: от естественных к искусственным системам . ISBN 978-0-19-513159-8.
• Кеннеди, Джеймс; Эберхарт, Рассел К. (2001-04-09). Рой Интеллект . ISBN 978-1-55860-595-4.
• Энгельбрехт, Андрис (16 декабря 2005 г.). Основы вычислительного роевого интеллекта . Wiley & Sons. ISBN 978-0-470-09191-3.

внешние ссылки

• Марко Дориго и Мауро Бираттари (2007). «Рой интеллект» в Scholarpedia
• Антуанетта Браун. Рой Интеллект