Анализ поведения колонии муравьев может дать лучшие алгоритмы для сетевых коммуникаций

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

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

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

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

“Это интуитивно, если группа людей случайным образом будут ходит вокруг области, сколько раз они сталкиваются друг с другом и будет являться оценкой плотности населения,” говорит Камерон Musco, выпускник MIT в области электротехники и вычислительной техники и соавтор на новой бумаге. “То, что мы делаем, дает строгий анализ этой интуиции, а также о том, что является очень хорошей оценкой, а не какой-то грубой оценки. В зависимости от времени, она становится все более и более точным, и она идет почти так же быстро, как вы могли бы ожидать, что вы могли бы когда-нибудь сделать “.

Случайные блуждания

Musco и его соавторы-его советник, NEC профессор программного обеспечения науки и техники Нэнси Линч, и Синь-Хао Су, постдок в Линча группе, характеризуют среду муравьев как сеть , с некоторым количеством других муравьев , разбросанных случайным образом в нём. Интерес к муравьям, это исследование начинается в какой – то ячейки сети и, с равной вероятностью, переходит к одной из соседних ячеек. Тогда, с равной вероятностью, она перемещается в одну из ячеек , примыкающих к этому, и так далее. В статистике это называется “блужданием”. Исследователь считает количество других муравьев, которые посещают каждую клетку.

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

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

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

Повторные встречи

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

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

“Если вы случайно блуждаете вокруг сети, вы не собираетесь побывать во всех клетках, потому что вы не собираетесь пересечь всю сеть,” говорит Musco. “Так что есть кто-то на противоположной стороне сетки, что у меня есть довольно много нулевой процентный шанс встретится с ним. Но пока я буду посещать близлежащие клетки, я буду чаще натыкаться на местных парней. Мне нужно подсчитать все мои взаимодействие с местными членами, чтобы компенсировать тот факт, что есть такие далекие ребята, что я никогда не буду посещать, это своего рода прекрасно уравновешивает, это очень легко доказать, но это не очень интуитивно, поэтому нам нужно некоторое время, чтобы понять это “.

Обобщения

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

Графы базы данных

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

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

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

Кроме того, в новой работе исследователи анализируют случайные блуждания, выполненные одним исследователем. Объединение средств наблюдения из многих исследователей сходились бы на точной оценке более быстро. “Если бы они были роботы вместо муравьев, они могли бы получить прибыль, разговаривая друг с другом и говорят:” О, это моя оценка, “говорит Musco.

“Поле Нэнси является распределенным вычислением, которая имеет различные стратегии и методы, которые в значительной степени неизвестны биологам,” говорят Анна Dornhaus, доцент кафедры экологии и эволюционной биологии в Университете штата Аризона, который изучает социум насекомых. “Нэнси [Линч] находится на переднем крае, понимая, что эти инструменты могут быть на самом деле очень полезно для биологов. Она пытается сделать это междисциплинарные исследования и действительно позволяют нам, возможно, сделать шаг вперед в понимании биологических систем.”

“Люди всегда обсуждают или муравьёв или пчел, как они могут распознавать других людей,” объясняет Dornhaus. ” В данной работе показано , что по крайней мере , в этом контексте, что это не нужно. Для меня это главное неожиданный результат здесь. Но, конечно, они могут также доказать математически, насколько точна стратегия” .

Ps. По ошибкам и неточностям в переводе обращаться ниже в комментариях или в личку.