Коллектив Авторов - Цифровой журнал «Компьютерра» № 166

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

Создание невидимой феромонной программы начинается с муравья, который сбился с готовой дорожки. Без неё он вынужден хаотично рыскать в окрестностях муравейника, разыскивая еду для колонии. Найдя что-то, заслуживающее внимания, муравей возвращается в гнездо, оставляя за собой пахучий след.

«Внешняя память» муравьёв не застрахована от ошибок. Если феромонный путь замкнётся, муравьи попадут в бесконечный цикл, из которого нет выхода. Каждый новый круг по замкнутому маршруту усиливает запах следа, привлекая всё новых и новых жертв. Так продолжается до тех пор, пока муравьи не погибнут от истощения.

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

И вот тут есть интересная подробность: муравьи далеко не сразу выстраиваются гуськом и идут друг за другом след в след. Пока запах слабый, они добираются до цели как придётся и часто отклоняются от траектории, по которой следовал разведчик и которая, скорее всего, далека от идеала.

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

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

Если найденную дорогу перегородит препятствие, процесс повторится: муравьи ринутся в обход, найдут несколько альтернативных вариантов, кратчайший путь быстрее накопит феромонные следы, победит более длинные и всё вернётся на круги своя. Нарушенная программа скорректируется.

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

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

Для человека поиск решения не составляет труда (достаточно одного взгляда на карту), а вот для компьютера задача коммивояжёра — это грандиозная проблема. Дело в том, что её нельзя решить «в лоб». Маршрутов оказывается невероятно много даже при относительно скромном количестве городов. Так много, что их невозможно перебрать и проанализировать по очереди. Приходится искать лазейки и хитрить.

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

Метод назвали алгоритмом муравьиной колонии. С одной стороны, он положил начало исследованиям в области так называемого «интеллекта роя» — области информатики, изучающей алгоритмы, основанные на тех же принципах, что и самоорганизация и спонтанный порядок в природе. С другой стороны, его хоть и осторожно, но начинают применять на практике.

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