Никита Максимов
Дорогой длинной, тропой муравьиной
Жаркий летний полдень. Кажется, все замерло в этот знойный час. Только внимательно приглядевшись, замечаешь, как под ногами в разных направлениях бегут муравьи. На первый взгляд, в их перемещениях нет ничего системного. Торопятся, суетятся, спешат — каждый сам по себе. Но чем дальше наблюдаешь, тем скорее понимаешь, что в их движениях существует некая система. Одни бегут по своим невидимым тропам за листочком или хвоинкой, другие уже возвращаются с добычей.
Сегодня ученые решили применить наши знания об организации перемещения муравьев для целей телекоммуникационных сетей.
Несколько лет назад Жан Луис Денебург из Брюссельского университета и его коллеги выяснили, что появление муравьиных тропинок, которые мы так часто видим в лесу или у себя на кухне, обусловлено тем, что муравьи выделяют особое пахучее вещество-сигнал — феромон.
Помечая этим веществом свои пути, муравьи дают знать сородичам по муравейнику об уже проложенных маршрутах..
Проводя эксперименты с аргентинским муравьем (Linepithema humile), Денебург выстроил конструкцию из двух мостов, которые вели от места расположения муравьев до источника пищи. Один мост был намного короче другого. Естественно, выяснилось, что муравьи выбирают короткий путь. Однако — обнаружили ученые — выбор этот происходит не в результате отличных навигационных способностей муравьев, а просто потому, что по короткому пути шли к пище и возвращались обратно гораздо больше муравьев, чем по длинному. Большее количество — означает большую концентрацию феромона, большую привлекательность для следующих добытчиков именно этого пути.
(Замечу, что если сначала муравьям предложить только один путь — длинный, а уже потом короткий, то. как это не покажется странным, они выберут длинный путь. Просто потому, что больше пометят его и не станут менять свой выбор, даже получив короткий путь к пище.)
Однако, когда ученые решили использовать методы оптимизации маршрутов передвижения у муравьев, они ввели несуществующее в природе условие — пахучее вещество, которым метит живой муравей свой путь, у искусственных муравьев испаряется тем быстрее, чем больше путь.
В первых компьютерных моделях муравьи последовательно исследовали все пространство и, обнаружив источники пищи, выбрали кратчайший маршрут, который состоял из множества мелких отрезков. Причем, если последняя «ветка» пути, которая вела к пище, оказывалась переполненной путниками, рядом прокладывался обходной маршрут.
Продолжая эту модель, Марко Доринго решил попробовать силы муравьев в решении знаменитой математической проблемы, в которой необходимо выбрать кратчайший маршрут посещения за один только раз большого количества городов. Пятнадцать городов и миллиарды возможных перемещений. Отправленные в длительное путешествие искусственные муравьи посетили все пункты и нашли оптимальный маршрут, по которому они и совершали свои следующие прогулки. А тем самым они увеличивали концентрацию пахучего вещества вдоль этого пути, поддерживая его привлекательность, а значит, и эффективность.
Такой муравьиный метод поиска оптимального пути посещения различный пунктов уже сейчас используется для расчета в сложных системах, например — выбор пути перемещения по большим площадям заводов, супермаркетов.
Кстати говоря, эти свойства муравьев можно использовать и при поисках информации в Сети. Чем больше людей ищут ту или иную информацию, тем более «заметным» становится их путь от первого слова в поисковых системах до конечной цели. Используя его, можно существенно сократить путь до конечной цели.
Руд Счондервурд и Джанет Брутен из исследовательской лаборатории Hewlett-Packard использовали в своих работах другое замечательное свойство муравьиного сообщества: реакцию на перегруженность кратчайшего маршрута и прокладывание другого, обходного пути. Они смогли создать модель телекоммуникаций, которая реагирует на повышенное содержание виртуального феромона, остающегося после прохождения каждого телефонного сигнала по тому или иному пути. То есть, если концентрация телефонных звонков через два пункта достигает некоего предела, то автоматически начинает прокладываться второй, более длинный, но менее загруженный маршрут. Однако, как только нагрузка начинает спадать, звонок сразу переадресуется и «идет» по кратчайшему пути. Уже несколько компаний используют подобный метод в своей работе — среди них такие, как France Telecom, British Telecommunications.