Новости

Июн 6, 2018

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


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

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

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

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

Игры

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

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

 

Далее...