Ant System

Ant System (рус. «Муравьиная система») — это один из первых и наиболее известных алгоритмов роевого интеллекта, основанный на моделировании поведения муравьёв при поиске кратчайших путей к источнику пищи. Относится к классу метаэвристических алгоритмов, применяемых для решения задач комбинаторной оптимизации, в первую очередь — задачи коммивояжёра (TSP). Алгоритм был предложен итальянским учёным Марко Дориго в 1992 году в его докторской диссертации и впоследствии опубликован в 1996 году совместно с Витторио Маниеццо и Альберто Колорни.

История и предпосылки

Идея алгоритма возникла из наблюдений за поведением муравьёв в природе. В 1949 году французский энтомолог Пьер-Поль Грассе описал концепцию стигмергии — формы косвенной координации, при которой особи оставляют во внешней среде сигналы (феромоны), влияющие на поведение других особей. В 1959 году Грассе применил эту концепцию к объяснению коллективного строительства термитов. Позднее, в 1989 году, Жан-Луи Денёбур и его коллеги экспериментально показали, что муравьи вида Linepithema humile способны находить кратчайший путь к пище, используя только феромонные следы.

Марко Дориго впервые формализовал этот биологический принцип в виде вычислительного алгоритма. Первая версия, названная Ant System, была представлена в 1991 году на конференции по искусственной жизни (ECAL). В 1992 году вышла диссертация Дориго, где алгоритм был подробно описан и протестирован на задаче коммивояжёра. В 1996 году вышла ставшая классической статья «Ant system: optimization by a colony of cooperating agents» в журнале IEEE Transactions on Systems, Man, and Cybernetics.

Основные принципы

Ant System имитирует поведение колонии муравьёв, решающих задачу поиска кратчайшего маршрута. В алгоритме используются следующие ключевые элементы:

• Искусственные муравьи — агенты, которые перемещаются по графу (сети городов в задаче коммивояжёра). Каждый муравей строит полный маршрут, последовательно выбирая следующий город из числа ещё не посещённых.
• Феромонные следы — числовые значения, присваиваемые рёбрам графа. Чем выше значение феромона на ребре, тем более привлекательным оно считается для муравьёв. Феромоны испаряются со временем, что предотвращает преждевременную сходимость к локальным оптимумам.
• Эвристическая информация — дополнительная информация, обычно обратная расстоянию между городами (так называемая видимость). Используется для учёта локальной выгоды при выборе следующего шага.

Правило перехода

Каждый муравей в момент времени \( t \) находится в городе \( i \) и выбирает следующий город \( j \) из множества ещё не посещённых городов \( N_i^k \) с вероятностью:

\[ p_{ij}^k(t) = \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in N_i^k} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}]^\beta} \]

где:

• \( \tau_{ij}(t) \) — уровень феромона на ребре \( (i, j) \) в момент времени \( t \);
• \( \eta_{ij} = 1/d_{ij} \) — эвристическая информация (обратное расстояние);
• \( \alpha \) и \( \beta \) — параметры, управляющие относительным влиянием феромонного следа и эвристики соответственно.

Обновление феромонов

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

1. Испарение: все феромоны уменьшаются на фиксированный коэффициент \( \rho \) (0 < ρ < 1):

\[ \tau_{ij}(t+1) = (1 - \rho) \cdot \tau_{ij}(t) \]

1. Отложение: каждый муравей \( k \) добавляет феромон на те рёбра, которые входят в его маршрут:

\[ \tau_{ij}(t+1) = \tau_{ij}(t+1) + \sum_{k=1}^m \Delta \tau_{ij}^k \] где \( \Delta \tau_{ij}^k = Q / L_k \), если ребро \( (i, j) \) входит в маршрут муравья \( k \), и 0 в противном случае. Здесь \( Q \) — константа, \( L_k \) — длина маршрута муравья \( k \).

Таким образом, чем короче маршрут, тем больше феромона на его рёбра откладывается.

Разновидности Ant System

Исходный Ant System породил несколько модификаций, улучшающих его производительность:

Elitist Ant System (EAS)

В этой версии наиболее сильный муравей (тот, который нашёл лучший маршрут за всю историю поиска) получает дополнительное усиление: его феромон откладывается с весом \( e \). Это ускоряет сходимость к лучшему решению.

Rank-Based Ant System (ASrank)

Все муравьи ранжируются по длине найденных маршрутов. Только \( w \) лучших муравьёв (обычно \( w = 6 \)) откладывают феромон, причём каждый — с весом, пропорциональным его рангу.

Max-Min Ant System (MMAS)

Разработан Томасом Штюцле и Хольгером Хоосом в 2000 году. В этой версии феромоны ограничены интервалом \( [\tau_{min}, \tau_{max}] \), что предотвращает их чрезмерное накопление на одних рёбрах и полное исчезновение на других. Кроме того, после каждого обновления феромонов все рёбра инициализируются значением \( \tau_{max} \), что стимулирует исследование.

Ant Colony System (ACS)

Предложен Марко Дориго и Лукой Гамбарделлой в 1997 году. Отличается от базового Ant System тремя основными изменениями:

• Используется «правило псевдослучайного пропорционального выбора»: с вероятностью \( q_0 \) муравей выбирает ребро с максимальным произведением \( \tau \cdot \eta^\beta \), а с вероятностью \( 1 - q_0 \) — по вероятностному правилу.
• Локальное обновление феромонов: каждый муравей сразу после перехода уменьшает феромон на пройденном ребре, что стимулирует других муравьёв исследовать альтернативные пути.
• Глобальное обновление феромонов производится только для лучшего маршрута (глобально лучшего или лучшего в текущей итерации).

Применение

Ant System и его производные нашли применение в широком спектре задач оптимизации:

• Задача коммивояжёра (TSP) — классическая тестовая задача, на которой алгоритм был впервые протестирован и показал хорошие результаты для малых и средних размеров (до 1000 городов).
• Задача маршрутизации транспорта (VRP) — оптимизация доставки товаров с учётом ограничений на грузоподъёмность и временные окна.
• Задача о назначениях — например, квадратичная задача о назначениях (QAP).
• Планирование задач (Job Shop Scheduling) — составление расписаний для производственных процессов.
• Маршрутизация в телекоммуникационных сетях — алгоритмы AntNet, адаптирующие принципы Ant System для динамической маршрутизации пакетов в сетях с коммутацией пакетов.
• Биоинформатика — задачи выравнивания последовательностей и предсказания структуры белков.

Критика и ограничения

Несмотря на широкую популярность, Ant System имеет ряд недостатков:

• Медленная сходимость — по сравнению с некоторыми другими метаэвристиками (например, генетическими алгоритмами), Ant System может требовать большего числа итераций для нахождения качественного решения.
• Чувствительность к параметрам — эффективность алгоритма сильно зависит от выбора параметров \( \alpha \), \( \beta \), \( \rho \), \( Q \) и количества муравьёв. Оптимальные значения часто подбираются экспериментально.
• Преждевременная сходимость — при неудачном выборе параметров или на сложных задачах алгоритм может сходиться к локальному оптимуму, не исследуя другие области пространства решений.
• Масштабируемость — для задач с большим числом узлов (более 10 000) производительность Ant System может снижаться, хотя существуют гибридные подходы, частично решающие эту проблему.

Интересные факты

• Термин «Ant System» часто используется как синоним для всего семейства алгоритмов муравьиной колонии (Ant Colony Optimization, ACO), хотя исторически Ant System является лишь первой конкретной реализацией этой парадигмы.
• В 2000 году Марко Дориго и Томас Штюцле основали конференцию ANTS, посвящённую алгоритмам роевого интеллекта.
• Алгоритмы семейства ACO, включая Ant System, применялись для решения реальных логистических задач, в частности, для оптимизации маршрутов доставки в компании Procter & Gamble и для планирования движения поездов в Швейцарских железных дорогах.

Источники

• Dorigo, M., Maniezzo, V., & Colorni, A. (1996). Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics), 26(1), 29–41.
• Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
• Dorigo, M., & Gambardella, L. M. (1997). Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation, 1(1), 53–66.
• Stützle, T., & Hoos, H. H. (2000). MAX–MIN ant system. Future Generation Computer Systems, 16(8), 889–914.
• Grassé, P.-P. (1959). La reconstruction du nid et les coordinations interindividuelles chez Bellicositermes natalensis et Cubitermes sp. La théorie de la stigmergie: Essai d'interprétation du comportement des termites constructeurs. Insectes Sociaux, 6(1), 41–80.