Муравьиный алгоритм

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

Самая важная задача для колонии муравьев - это поиск пищи. Еда может располагаться далеко от муравейника, путь к ней может быть извилист - поэтому ищут ее “всем миром”. Добытчики пищи - фуражиры - уходят в поисках пищи на расстояние до 200 метров от муравейника. Если он найдет еду так далеко от дома, то остальным муравьям придется повторить его путь, чтобы доставить припасы. Как же они это делают?

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

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

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

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

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

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

• как движется каждый муравей и что он ищет
• сколько всего муравьев и где они расположены
• как много выделяется феромона и как он испаряется

Такой подход применяется в задачах оптимизации различных областей, но самое очевидное - это транспортная логистика: надо придумать, что куда и когда отправить самым рациональным образом. Но этот алгоритм нашел применение и в задачах планирования ресурсов, и в календарном планировании, и в создании конструкции антенн.

Конечно, у муравьиного алгоритма есть и недостатки. В частности, он не гарантирует оптимальности выбранного решения: могут существовать и другие, более качественные варианты, до которых муравьи просто не добрались. Но современный мир очень быстр, поэтому скорость получения решения часто выходит на первый план. В таких случаях лучше “хорошо, но сейчас”, нежели “прекрасно, но через год” - и муравьиный алгоритм вполне для этого подходит.