Алгоритмы муравьёв -- применение

Задача коммивояжёра

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

Муравьи нашли идеальное решение задачи коммивояжёра (нахождение оптимального маршрута, между несколькими пунктами с возвратом назад).

Алгоритм муравьиной колонии послужил толчком к исследованиям «роевого интеллекта». Сегодня такие системы уже используются в реальности.

Игры

Уилл Райт, создал известный симулятор муравья в колонии под названием SimAnt. Впечатляющий результат вдохновил экспериментатора-программиста разработать ещё одну игру.

Мало кто знает, но прототипом для игры Sims послужил муравейник. Каждый объект в ней испускает так называемые виртуальные феромоны: питание, одежда, сон, сила. Если у героя возникает какая-то необходимость, он идёт по самому «благоухающему» пути соответствующего типа.

 

Оптимальные маршруты

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

Компания Air Liquide специализируется на производстве сжиженного газа. Множество заводов по всей Америке и необходимость транспортировки своего товара в 6000 пунктов, натолкнуло основателей компании на мысль об использовании муравьиного алгоритма. Программа управляет четырёхстами грузовиками, железной дорогой и несколькими трубопроводами и учитывает стоимость энергии.

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

Группы автономных роботов

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

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