Исследователи из Массачусетского технологического института (MIT) выяснили, как муравьи отыскивают удачные места для новых муравейников без планирования, коммуникации, организации и даже понимания того, что происходит. Метод, который используют эти насекомые, может оказаться очень полезен при работе с распределёнными самоорганизующимися сетями.
Когда муравьи переселяются, важно выбрать такое место, где не слишком велика конкуренция. Если окрестности нового муравейника будут кишеть посторонними муравьями, ничего хорошего не выйдет. Чтобы избежать этого, нужно понимать, где муравьёв много, а где их мало.
Но откуда возьмётся такое понимание? Муравьи определённо не могут разбить карту на квадраты и организованно прочесать местность, периодически проводя замеры численности населения. У них нет карт и плохо не только с пространственным мышлением, но и с мышлением вообще. В нервной системе муравья всего 250 тысяч нейронов. Это очень мало. Даже у таракана миллион!
Очевидно, что ответ должен быть очень простым. Учёные из MIT предположили, что даже единственный муравей, блуждая по окрестностям без всякой логики и цели, может составить очень точное представление о населённости каждого участка.
Они построили модель, в которой местность представлена в виде равномерной сети. На каждом шаге муравей-исследователь собирает информацию о текущей клетки, после чего ползёт в следующую. При этом выбор направления совершенно случаен. Он может шагнуть назад, продолжить движение вперёд или повернуть в ту или другую сторону.
Нет никакой гарантии, что этот муравей обойдёт заметную долю карты. Он вполне способен застрять на одном участке, а другой — пропустить вовсе. Но, как оказалось, это не помеха. Учёные обнаружили, что с каждым шагом точность получаемого им результата быстро растёт.
Скорость, с которой оценка муравья-исследователя приближается к истинной величине, была сравнима с теоретическиv максимумом. Сбор информации о состоянии сети при помощи случайного блуждания оказался почти таким же быстрым и эффективным, как случайная выборка.
Это очень ценное открытие, и не только для муравьёв. На практике выборка не всегда применима. Она требует точного представления о топологии сети и возможности обратиться к произвольному элементу. Грубо говоря, нужна карта, информация и организация. Что делать, когда их нет?
Представьте распределённую сеть, состоящую из тысяч датчиков, покрывающих сельскохозяйственное поле. Это, к слову, не фантастика: за шанс занять долю рынка «больших данных» в сельском хозяйстве корпорации вроде Monsanto платят миллиарды.
Эффективное извлечение информации, собираемой гигантской сетью датчиков — очень непростая задача. Очевидный выход — построить иерархическую структуру, в которой каждый датчик общается со своим головным устройством, те передают информацию уровнем выше, и так далее. Проблема в том, что такая система хрупка, ненадёжна и очень дорого стоит.
Муравьиный алгоритм позволяет организовать датчики в распределённую сеть, лишённую иерархии, не нуждающуюся в головных устройствах и сложной структуре. По отдельности каждый датчик не знает топологию сети и поддерживает связь только с ближайшими соседями. Однако запустив сбор информации от одного из узлов сети, которую они образуют, при помощи случайного блуждания можно добиться быстрого и точного результата.
Это лишь один пример. Сетка, моделирующая местность, по которой блуждает муравей, — это частный случай графа. Это значит, что тот же алгоритм можно использовать для анализа любых данных, представленных в виде графа, в том числе и в тех случаях, когда есть доступ лишь к малой его части.
Авторы работы, которая будет представлена в июле на Симпозиуме по принципам распределённых вычислений, который проводит международная Ассоциация вычислительной техники (ACM), полагают, что предложенный метод может быть полезен для анализа социальных сетей, управления роями автономных роботов и при работе с самоорганизующимися сетями.
Подробнее об алгоритмах, которые позволяют простым организмам демонстрировать сложнейшее поведение, «Хакер» рассказывал в статье «Искусственная тупость».
