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

В природе некоторые виды муравьёв сначала блуждают случайно, а найдя еду, возвращаются в колонию, оставляя феромонные следы. Если другие особи встречают такую тропу, они с большей вероятностью следуют по ней, возвращаясь и усиливая её, если также находят источник пищи (см. Коммуникация у муравьёв)^[9].

Со временем феромонный след испаряется, уменьшая свою привлекательность. Чем дольше муравей идёт по пути и возвращается, тем больше феромона успевает испариться. Короткий путь оказывается чаще задействован, и плотность феромона на коротких маршрутах растёт быстрее, чем на длинных. Испарение феромона также важно для предотвращения преждевременной сходимости к локальному оптимуму — без испарения первые найденные маршруты стали бы излишне привлекательными и ограничили бы исследование пространства решений. Хотя влияние испарения в реальных муравьиных системах остаётся не до конца изученным, его роль в искусственных муравьиных алгоритмах считается крайне значимой^[10].

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

Новые концепции требуются в условиях, когда «интеллект» распространяется на все мельчайшие объекты — он более не централизован. Традиционный человекоцентричный подход приводил к созданию ИТ-систем, где вычисления и управление фокусируются в едином центре, по аналогии с головным мозгом. Однако будущие амбиентные сети интеллектуальных объектов и диффузные системы на основе нанотехнологий могут изменить это представление: небольшие устройства, сравнимые с насекомыми по «уровню интеллекта», по отдельности имеют ограниченные вычислительные возможности, но при объединении способны проявлять коллективную «колониальную» интеллектуальность, в ряде случаев превосходящую централизованную^[11].

Природа демонстрирует примеры того, как микроорганизмы, подчиняясь простым локальным правилам, создают макроуровневую коллективную интуицию. Социальные насекомые — классический пример кардинально отличной от человеческой модели общества: кооперация независимых элементов с простым и локально неопределённым поведением^[12]. Колонии муравьёв демонстрируют высокую приспособляемость и устойчивость к отказам отдельных особей, что полезно, например, для мобильных самоорганизующихся сетей. Данные, перемещающиеся в сети от одного устройства к другому, подобны муравьям, ищущим оптимальный путь к цели^[13].

Феромонная коммуникация — одна из эффективнейших форм передачи информации, наблюдающихся в природе: её используют муравьи, пчёлы, термиты — как для межагентского, так и группового взаимодействия. Благодаря практичности, этот принцип перенят в мультиагентных и коллективных робототехнических системах. Искусственный феромон реализуется химическими методами^[14][15][16] или физическими (RFID-метки^[17], свет^{[18][19][20][21]}, звук^[22]) средствами. Однако в полной мере ни одна из реализаций пока не воспроизводит все свойства природных феромонов.

Использование проекций света предложено Garnier и соавт. (2007) как эксперимент в изучении феромоновой коммуникации у миниатюрных автономных роботов^[23]. В другом исследовании система феромонов реализована с помощью горизонтального LCD-экрана, по которому перемещались роботы с направленными вниз фотосенсорами для считывания паттернов^[24][25].

После 2017 года были разработаны усовершенствованные методы реализации искусственных феромонов, которые делятся на виртуальные (цифровые) и физические.

Виртуальные системы развивают подход, основанный на использовании LCD-экранов и проекторов. В 2019 году была представлена расширенная система COS-Φ, в которой компьютер симулирует поведение феромонов и отображает их на экране, а камера отслеживает положение роботов. Ключевым нововведением стала симуляция диффузии (распространения) и адвекции (переноса), что позволяет моделировать влияние факторов окружающей среды, таких как ветер^[26]. Дальнейшим развитием стала система ColCOSΦ (2021), позволяющая одновременно использовать несколько типов виртуальных феромонов с помощью оптических сигналов разного цвета. Роботы, оснащённые датчиками цвета, могут распознавать и по-разному реагировать на различные «феромонные следы»^[27]. Другой подход предполагает использование «неполных виртуальных карт» (incomplete virtual pheromone maps), которые каждый робот хранит локально и обновляет при взаимодействии с другими, что повышает отказоустойчивость роя^[28].

Среди физических систем выделяется система Phormica, представленная в 2020 году. В ней роботы, оснащённые ультрафиолетовыми светодиодами, оставляют видимый след на специальной фотохромной поверхности. Этот метод считается более простым и дешёвым решением по сравнению с химическими аналогами^[29].

Новым направлением в управлении поведением роя стала интеграция с большими языковыми моделями (LLM). Этот подход, получивший развитие в 2024—2025 годах, позволяет определять поведение агентов в реальном времени с помощью текстовых инструкций (промптов), что обеспечивает гибкость и адаптивность по сравнению с жёстко заданными правилами^[30]. Также разрабатываются методы автоматического проектирования коллективного поведения, например, метод Habanero, который позволяет генерировать эффективные модели поведения на основе стигмергии^[31].

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

процедура ACO_MetaHeuristic есть
    пока не выполнено_условие_завершения делать
        сгенерироватьРешения()
        действияДемона()
        обновлениеФеромонов()
    повторять
конец процедуры

Для построения решения муравью нужно выбирать ребро, по которому он пойдёт следующим. При этом учитываются длина рёбра и уровень феромона на каждом варианте. На каждом шаге муравей k переходит из состояния x в состояние y с вероятностью, зависящей от двух величин: привлекательности ${\displaystyle \eta _{xy}}$ (эвристически оценивается, например, как ${\displaystyle 1/d_{xy}}$) и «уровня следа» ${\displaystyle \tau _{xy}}$ (количество феромона на переходе x→y):

${\displaystyle p_{xy}^{k}={\frac {(\tau _{xy}^{\alpha })(\eta _{xy}^{\beta })}{\sum _{z\in \mathrm {allowed} _{y}}(\tau _{xz}^{\alpha })(\eta _{xz}^{\beta })}}}$

где ${\displaystyle \tau _{xy}}$ — уровень феромона, ${\displaystyle \alpha \geq 0}$ — вес влияния феромонов, ${\displaystyle \eta _{xy}}$ — привлекательность (обычно ${\displaystyle 1/d_{xy}}$), ${\displaystyle \beta \geq 1}$ — вес эвристики.

После завершения прохождения всеми муравьями увеличиваются или уменьшаются феромоны на рёбрах маршута: усиливаются хорошие решения, ослабляются плохие.

${\displaystyle \tau _{xy}\leftarrow (1-\rho )\tau _{xy}+\sum _{k}^{m}\Delta \tau _{xy}^{k}}$

где ${\displaystyle \rho }$ — коэффициент испарения феромона, m — число муравьёв, ${\displaystyle \Delta \tau _{xy}^{k}}$ — вклад k-го муравья, который для задачи коммивояжёра обычно:

${\displaystyle \Delta \tau _{xy}^{k}={\begin{cases}Q/L_{k}&{\mbox{если муравей }}k{\mbox{ прошёл по дуге }}xy\\0&{\mbox{иначе}}\end{cases}}}$

где ${\displaystyle L_{k}}$ — длина пути k-го муравья, ${\displaystyle Q}$ — константа.

Ниже приведены основные варианты реализаций муравьиных алгоритмов.

Первая реализация, соответствующая приведённому выше описанию, разработана Марко Дориго^[32].

Модификация базового алгоритма в трёх аспектах:

1. Выбор рёбер смещён к эксплуатации (то есть увеличена вероятность выбора наиболее коротких рёбер с высоким уровнем феромона);
2. В процессе построения решения муравьи локально обновляют феромон на проходящих рёбрах;
3. В конце каждой итерации обновление феромонов по глобальному правилу выполняет только лучший муравей^[33].

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

В этой версии управление диапазоном уровней феромона на каждом ребре осуществляется через ограничение [τ_min, τ_max], обновления проводит только лучший глобальный или итерационный маршрут. При сближении к стагнации все рёбра вновь инициализируются максимальным феромоном^[34].

Решения ранжируются по длине, только фиксированное число лучших муравьёв обновляют феромон. Величина феромона пропорциональна качеству маршрута.

Группы искусственных муравьёв взаимодействуют по каналам связи, феромон обновляется между группами по 7 схемам — применяется для задачи коммивояжёра^[35].

Позволяет эффективно исследовать решения в непрерывном пространстве с помощью ортогональных проектирующих методов и адаптивного изменения радиуса поиска^[36].

Рекурсивное разбиение задачи на поддомены с отдельной оптимизацией, лучшие решения продолжают поиск на детализации до достижения требуемой точности^[37][38].

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

Одним из ключевых направлений стало создание гибридных алгоритмов, сочетающих ACO с другими подходами для повышения эффективности.

• Генетические алгоритмы (GA): Гибридизация с GA является наиболее распространённой. Существуют различные подходы: использование GA для динамической оптимизации параметров ACO в процессе его работы^[39], применение ACO для генерации качественной начальной популяции для GA^[40] или более глубокая интеграция, где агенты-муравьи используют генетическую информацию при построении пути^[41]. Примерами таких гибридов являются Red-Black Ant Colony System (RB-ACS)^[42] и Genetic Ant System (GAS)^[43].
• Другие метаэвристики: ACO также комбинируют с другими алгоритмами, например, с оптимизатором на основе серых волков (ACO-GWO)^[44], алгоритмом искусственной пчелиной колонии (ACO-ABC)^[45] и имитацией отжига (ACO-SA)^[46].
• Локальный поиск: Распространённой практикой является сочетание ACO с методами локального поиска, такими как эвристика 2-opt, для уточнения найденных решений^[43].

Для улучшения базового алгоритма были предложены различные модификации, направленные на повышение его адаптивности и эффективности.

• Saltatory Evolution Ant Colony Optimization (SEACO): Представленный в 2022 году, этот алгоритм ускоряет оптимизацию за счёт построения модели, предсказывающей эволюцию матрицы феромонов. Это позволяет «перескакивать» через множество итераций, что особенно эффективно при работе с большими наборами данных^[47].
• Адаптивные механизмы: Разработаны подходы с динамической настройкой параметров алгоритма, таких как веса влияния феромонов и эвристики (α и β), в процессе работы^[48]. Также были предложены новые стратегии обновления феромонов, например, механизм диффузии, при котором феромон распространяется на соседние области^[40], и многопопуляционные стратегии с разделением муравьёв на «элитных» и «обычных»^[40].

В последние годы муравьиные алгоритмы начали интегрировать с передовыми технологиями в области искусственного интеллекта.

• Нейронные сети (NN): Появились гибриды ACO и искусственных нейронных сетей (ANN) для задач моделирования пользователей^[49], а также интеграция с графовыми нейронными сетями (GNN) для решения задачи маршрутизации транспорта^[50].
• Обучение с подкреплением (RL): Разработаны системы, объединяющие ACO и RL, например, для прогнозирования тенденций в цифровой экономике, где ACO используется для извлечения признаков, а RL — для уточнения модели^[51].
• Квантовые вычисления: Одним из новейших направлений является Quantum Ant Colony Optimization (QACO). В 2024 году был представлен гибридный квантово-классический алгоритм, сочетающий QACO с методами кластеризации, который показал высокую производительность и устойчивость к вычислительным шумам при решении крупномасштабных задач оптимизации^[52].

Для ряда разновидностей алгоритма доказана сходимость (то есть возможность нахождения глобального оптимума за конечное время): сперва это было показано для графовой версии Ant System (2000), затем для ACS и MMAS. Детальная теоретическая оценка скорости сходимости сложна; производительность параметрически чувствительна, особенно к коэффициенту испарения феромона^[53]. В 2004 году отмечено сходство с методом стохастического градиентного спуска и алгоритмами оценки распределений.

Современные исследования сходимости сосредоточены не столько на доказательстве самой возможности нахождения оптимума, сколько на практических аспектах: ускорении сходимости и предотвращении преждевременной стагнации (застревания в локальных оптимумах)^[54]. Ключевые теоретические свойства муравьиных алгоритмов, включая сходимость, были обобщены в обзоре основоположника метода Марко Дориго и Томаса Штюцле, опубликованном в 2019 году^[55]. Для улучшения баланса между исследованием пространства решений и скоростью сходимости были предложены гибридные подходы. Например, алгоритм Greedy-Levy ACO (2020) использует полёты Леви для балансировки поиска, а DBACS (2020) применяет динамическую кластеризацию и механизм обратного отслеживания для выхода из локальных оптимумов^[54][56]. С 2021 года наметилась тенденция к интеграции с обучением с подкреплением для управления процессом построения решений^[57].

В области теоретического анализа были получены новые результаты для муравьиных алгоритмов с зависимостью от времени. В частности, для варианта GBAS/tdev (Graph-based Ant System с зависящей от времени скоростью испарения) было доказано, что получаемое решение сходится к оптимальному с вероятностью 1. При этом анализ показал, что другие адаптации, например n-ANT/tdlb (с изменяемой нижней границей феромона), могут достигать полиномиального времени выполнения для некоторых задач, в то время как для GBAS/tdev оценка времени выполнения оказалась сверхполиномиальной^[58].

Муравьиные алгоритмы применяются к разнообразным задачам комбинаторной оптимизации. Классические области включают задачу коммивояжёра, маршрутизацию транспорта, квадратичное присваивание, свёртку белков и интеллектуальный анализ данных^[59]. Преимущество над методами имитационного отжига и генетическими алгоритмами проявляется в динамически изменяющихся графах: муравьиный алгоритм продолжает работу и адаптируется в реальном времени, что особенно ценно в сетевой и транспортной маршрутизации^[60].

Первая версия — ant system — решала задачу коммивояжёра: требуется найти кратчайший обход всех городов по кругу. Муравьи формируют множество вариантов маршрута, на каждом шаге делают выбор на основе эвристики и интенсивности феромонов:

1. Каждый город посещается ровно один раз;
2. К дальнему городу вероятность перехода меньше (эвристика видимости);
3. Чем интенсивнее феромоновый след на ребре между двумя городами, тем выше вероятность его выбора;
4. По сверхкороткому маршруту муравей увеличивает феромон на всех своих рёбрах;
5. После каждой итерации уровень феромона на рёбрах испаряется.

С 2020-х годов сфера применения муравьиных алгоритмов значительно расширилась, охватив новые высокотехнологичные отрасли.

Биоинформатика и медицина Алгоритмы используются для решения сложных задач в биоинформатике и медицине. К ним относятся построение причинно-следственных биологических сетей на основе данных фМРТ^[61], сегментация медицинских изображений^[62], а также отбор признаков для предсказания функций белка^[63].

Робототехника и управление роями БПЛА Одной из наиболее активно развивающихся областей стало управление группами БПЛА и мобильными роботами. ACO применяется для кооперативного планирования путей при инспекции инфраструктуры^[64], оптимизации строя роя дронов для экономии энергии^[65] и определения маршрутов в точном земледелии^[63]. Инновационным подходом является использование «обратного феромона», который отталкивает дроны от уже посещённых участков, что полезно для мониторинга динамичной городской среды^[66].

Гибридизация с машинным обучением Ключевой тенденцией стала гибридизация ACO с методами машинного и глубокого обучения. Такие гибридные модели используются для решения задач в различных сферах, включая оптимизацию энергетических сетей, обнаружение аномалий в системах кибербезопасности и персонализацию маркетинговых стратегий^[67].

Распределённые системы и федеративное обучение Новым вектором применения стало федеративное обучение, где данные распределены по множеству устройств. Муравьиные алгоритмы используются для отбора наиболее информативных признаков на стороне клиента, что снижает сложность моделей и затраты на коммуникацию^[68].

Другие области Среди прочих современных приложений выделяются:

• Обработка изображений: выделение границ, сегментация и сжатие изображений^[69].
• Планирование туристических маршрутов: создание персонализированных планов поездок с учётом различных типов объектов (достопримечательности, рестораны, отели) и возможности их многократного посещения^[70].
• Киберфизические системы: оптимизация распределения задач^[63].
• Квантовые и объяснимые ACO: перспективными направлениями являются разработка квантово-вдохновлённых муравьиных алгоритмов (Quantum ACO) и методов, делающих процесс принятия решений алгоритмом более прозрачным для человека (Explainable ACO)^[71].

• Задача последовательного упорядочивания (SOP)^[72]
• Задача пооперационного планирования (JSP)^[73]
• Задача открытого расписания (OSP)^[74][75]
• Расписание потокового производства с перестановками (PFSP)^[76]
• Одномашинная задача минимизации опозданий (SMTTP)^[77]
• Одномашинная задача минимизации взвешенных опозданий (SMTWTP)^[78][79][80]
• Задача расписания с ограничением ресурсов (RCPSP)^[81]
• Групповое расписание (GSP)^[82]
• Одномашинная задача с учётом наладки (SMTTPDST)^[83]
• Многостадийный потоковый расчёт с переналадкой (MFSP)^[84]
• Планирование сборочных последовательностей (ASP)^[85]

• Задача маршрутизации с ограничениями вместимости (CVRP)^[86] и др.

• Квадратичная задача присваивания (QAP)
• Обобщённая задача присваивания (GAP)^[87]
• Задача размещения частот

Муравьиные алгоритмы применяются также для:

• Обнаружение границ на изображениях (edge detection)^[88][89] и др.
• Интеллектуальный анализ данных^[73][90]
• Задачи энергообеспечения и проектирования электрических сетей^[91]
• Синтез антенн^[92]
• Биоинформатика и свёртывание белков^[93][94]
• Оптимизация электронных схем^[95]
• Классификация, прогнозирование банкротства

В муравьиных алгоритмах кратчайший путь между двумя точками A и B строится как комбинация лучших участков различных маршрутов^[96]. Точное определение принадлежности того или иного метода к муравьиным алгоритмам нередко варьируется у разных авторов. В общем случае под ними понимается класс популяционных метаэвристик, где решение представлено траекторией муравья в поисковом пространстве^[97] и используется вероятностное распределение для переходов между состояниями^[98]. Отличительной чертой считается именно конструктивный способ построения решений — итеративное конструирование^[99]. Коллективное поведение социальных насекомых вдохновило формирование категории роевого интеллекта^[11], в которую входят муравьиные алгоритмы.

На практике множество алгоритмов именуют себя «муравьиными», не всегда следуя каноническому подходу оптимизации через феромонные тропы^[100]. Чаще достаточно заложить принцип обмена информацией через среду (стигмергия), чтобы алгоритм считался муравьиным. В литературе описаны и другие взаимосвязанные методы поиска, построенные на мотивациях муравьиных алгоритмов, вроде поиска пищи, сортировки личинок, разделения труда^[101].

Генетические алгоритмы

Поддерживают популяцию решений, комбинируя и мутируя их по аналогии с эволюцией; худшие варианты отбрасываются.

Алгоритмы оценки распределений

Эволюционный способ, заменяющий традиционные операторы репродукции модельно-ориентированными^[102].

Имитация отжига

Переходит в соседние решения, всегда принимая лучшие и с определённой вероятностью — худшие.

Реактивные алгоритмы поиска

Объединяют машинное обучение и оптимизацию, используя внутреннюю обратную связь для автонастройки алгоритма.

Поиск с запретами (Tabu search)

Исследует множество мутаций решения, поддерживает список «запретов» для предотвращения циклов.

Искусственная иммунная система

Алгоритм роя частиц

Intelligent Water Drops

Гравитационный оптимизационный алгоритм

Ant colony clustering method (расширение подхода к задаче кластеризации)

Стохастический диффузионный поиск

• 1959 — Пьер-Поль Грассе формулирует теорию стигмергии^[103];
• 1983 — Денёбур и др. исследуют коллективное поведение муравьёв^[104];
• 1988 — описание самоорганизации у муравьёв (Moyson, Manderick)^[105];
• 1989 — работа Goss, Aron, Deneubourg, Pasteels о «коротких путях» аргентинских муравьёв^[106];
• 1991 — Марко Дориго предлагает ant system (AS) в диссертации;
• 1994 — первая практическая реализация муравьиных агентов для телекоммуникационных сетей (Appleby, Steward)^[107];
• 1995—1997 — серия усовершенствованных вариантов (Ant-Q, ACS, MMAS);
• 1998—2001 — появление многокритериальных, параллельных и стохастических расширений^[108];
• 2000 — доказательство сходимости для графовой версии (Gutjahr)^[109];
• 2004 — фундаментальная монография «Ant Colony Optimization» (Dorigo, Stützle);
• 2005—2006 — Активное развитие алгоритма AntHocNet для маршрутизации в динамических мобильных самоорганизующихся сетях (MANETs)^[110];
• 2008 — Кшиштоф Соха и Марко Дориго представляют алгоритм ACOR (Ant Colony Optimization for Continuous domains), адаптирующий ACO для решения задач в непрерывных пространствах^[111]. В этот же период (2005—2009) получают развитие подходы к многокритериальной оптимизации (MOACO)^[112];
• 2014 — Предложен UACOR (Unified Ant Colony Optimization), унифицированный фреймворк для алгоритмов непрерывной оптимизации^[113];
• 2015—2024 — Период активного развития гибридных методов, в частности, сочетания ACO с генетическими алгоритмами (например, Genetic Ant System) и методами локального поиска (например, эвристикой 2-opt), а также разработки адаптивных механизмов для динамической настройки параметров^[43][114].