Муравьи помогут улучшить работу компьютерных сетей

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

Исследование, опубликованное в "Journal of Experimental Biology" ("Журнале экспериментальной биологии"), показало, что, вопреки ожиданиям, аргентинские муравьи (Linepithema humile), встречая препятствие, не поворачивают назад. Вместо этого они начинают локализованный поиск с учетом изначально выбранного направления. Поскольку многие современные программы сетевого управления имитируют поисковое поведение именно этих видов муравьев, похоже, что системным инженерам (программистам) предстоит еще многому у них поучиться.

В дикой природе муравьи-разведчики помечают дорогу между источником пищи и муравейником феромонами. Прочие обитатели муравейника следуют за ними, ориентируясь по этим отметкам, и усиливают их за счет своих собственных феромонов. Но поскольку феромонам свойственно постепенно испаряться, их концентрация на более длинных дорожках, где муравьи растягиваются в редкую цепочку, существенно отличается от концентрации на дорожках покороче. А так как именно феромоны заставляют муравьев выбирать определенный путь, длинные тропы с более слабой концентрацией феромонов вполне естественно отвергаются в пользу более коротких! Ссылки Запрещены!/uploads/posts/2010-12/1293533613_ants. jpg" style="color: rgb(47, 47, 47); text-decoration: underline; ">


Виртуальные разведчики

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

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

Я предполагал, что у аргентинских муравьев должен быть какой-то другой способ преодоления препятствий, не подразумевающий начало поиска с нуля", говорит один из инициаторов исследования, поведенческий биолог из Сиднейского Университета в Австралии Крис Рид.

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

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

Блокировка пути

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

На следующем этапе исследователи перекрыли короткие пути лабиринта и открыли для прохождения другой маршрут. К концу следующего часа почти 86% других колоний нашли и оставили отметки вдоль нового кратчайшего пути.

"То, что муравьи способны решить головоломку башни Ханоя довольно неожиданное открытие", говорит Саймон Робсон, биолог из университета Джеймса Кука в Таунсвилле, Австралия.

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

"Когда я впервые услышал о том, что вместо того, чтоб поворачивать назад, муравьи начали изучать близлежащие маршруты, подумал, что это просто потрясающе", делится впечатлениями Дэвид Брумхед, директор Центра междисциплинарного вычислительного и динамического анализа Манчестерского Университета, Великобритания.

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

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

Было изменено: 11:17 10/01/2011.