Муравьиный алгоритм
Свойства и структура алгоритма
Общее описание алгоритма
Муравьиный алгоритм (Ant Colony Optimization, ACO) — это вероятностный метаэвристический алгоритм для нахождения приближённых решений сложных задач комбинаторной оптимизации. Алгоритм принадлежит к классу методов роевого интеллекта и инспирирован поведением муравьёв, которые, находя пути к источнику пищи, оставляют на земле след феромона [1]. Другие муравьи, обнаруживая этот след, с большей вероятностью следуют по нему, усиливая феромонную метку, если находят пищу. Таким образом, коллективное поведение колонии приводит к нахождению кратчайшего пути.
Основная область применения ACO — задачи, которые могут быть сведены к поиску оптимальных путей на графах: задача коммивояжёра (TSP), маршрутизация в сетях, задача о назначениях, раскройка и упаковка и многие другие [2].
Математическое описание алгоритма
Пусть дан взвешенный граф [math]\displaystyle{ G = (V, E) }[/math], где [math]\displaystyle{ V }[/math] — множество вершин (городов), а [math]\displaystyle{ E }[/math] — множество рёбер (путей) с весами [math]\displaystyle{ d_{ij} }[/math] (расстояниями). Цель — найти гамильтонов цикл минимальной длины.
В основе алгоритма лежат два основных правила [1]:
Правило построения пути: Вероятность [math]\displaystyle{ p_{ij}^k(t) }[/math] того, что k-й муравей в момент времени t перейдёт из вершины i в вершину j, вычисляется по формуле:
[math]\displaystyle{
p_{ij}^k(t) = \frac{[\tau_{ij}(t)]^\alpha \cdot [\eta_{ij}]^\beta}{\sum_{l \in J_i^k} [\tau_{il}(t)]^\alpha \cdot [\eta_{il}]^\beta}, \quad \text{если } j \in J_i^k
}[/math]
где:
[math]\displaystyle{ \tau_{ij}(t) }[/math] — количество феромона на ребре (i, j) в момент времени t.
[math]\displaystyle{ \eta_{ij} = 1/d_{ij} }[/math] — эвристическая желательность перехода (обратная расстоянию).
[math]\displaystyle{ \alpha }[/math] и [math]\displaystyle{ \beta }[/math] — параметры, определяющие влияние феромона и эвристики соответственно.
[math]\displaystyle{ J_i^k }[/math] — множество вершин, которые муравей k ещё не посетил из вершины i.
Правило обновления феромона: После того как все муравьи построили свои пути, уровень феромона обновляется:
[math]\displaystyle{
\tau_{ij}(t+1) = (1 - \rho) \cdot \tau_{ij}(t) + \Delta \tau_{ij}
}[/math]
где:
[math]\displaystyle{ \rho \in (0, 1] }[/math] — коэффициент испарения феромона.
[math]\displaystyle{ \Delta \tau_{ij} = \sum_{k=1}^{m} \Delta \tau_{ij}^k }[/math] — суммарное количество феромона, отложенного всеми m муравьями на ребре (i, j).
[math]\displaystyle{ \Delta \tau_{ij}^k }[/math] обычно равно [math]\displaystyle{ Q / L_k }[/math], если k-й муравей прошёл по ребру (i, j), и 0 в противном случае. Здесь [math]\displaystyle{ Q }[/math] — константа, а [math]\displaystyle{ L_k }[/math] — длина пути k-го муравья.
Вычислительное ядро алгоритма
Вычислительное ядро муравьиного алгоритма состоит из двух основных, итеративно повторяющихся процессов [2]:
- . Построение решений (путей) каждым муравьём: Для каждого муравья и на каждом шаге его пути производится вероятностный выбор следующей вершины. Этот процесс требует вычисления вероятностей для всех возможных переходов, что связано с операциями умножения, возведения в степень и суммирования.
- . Обновление феромонов на всех рёбрах графа: После построения всех путей производится испарение феромона на всех рёбрах и добавление нового феромона на рёбра, входящие в построенные пути. Этот этап включает операции умножения (на (1-ρ)) и сложения.
Макроструктура алгоритма
Алгоритм можно представить в виде следующих макроопераций [3]:
- Инициализация: Задание начального уровня феромона на всех рёбрах, размещение муравьёв в начальных вершинах.
- Цикл по итерациям (пока не выполнен критерий остановки):
- Цикл по муравьям: Для каждого муравья построить полный путь.
- Цикл по шагам пути: Для каждого шага пути муравья рассчитать вероятности перехода и выбрать следующую вершину (например, с помощью правила рулетки).
- Вычисление длин путей для каждого муравья.
- Обновление глобального лучшего решения (если найден более короткий путь).
- Обновление феромона на всех рёбрах (испарение и добавление).
Ключевые макрооперации: вероятностный выбор (правило рулетки), вычисление длины пути (суммирование весов рёбер), обновление матрицы феромонов.
Схема реализации последовательного алгоритма
- Ввод данных: Задать граф (матрица расстояний [math]\displaystyle{ D }[/math]), параметры [math]\displaystyle{ \alpha, \beta, \rho, Q, m }[/math], количество итераций [math]\displaystyle{ iter_{max} }[/math].
- Инициализация:
[math]\displaystyle{ \tau_{ij}(0) = \tau_0 }[/math] для всех [math]\displaystyle{ i, j }[/math] (обычно [math]\displaystyle{ \tau_0 \gt 0 }[/math]).
[math]\displaystyle{ L_{best} = \infty }[/math] (длина лучшего пути). - Для [math]\displaystyle{ iter }[/math] от 1 до [math]\displaystyle{ iter_{max} }[/math]:
- Для каждого муравья [math]\displaystyle{ k }[/math] от 1 до [math]\displaystyle{ m }[/math]:
- Выбрать случайную начальную вершину для муравья [math]\displaystyle{ k }[/math].
- [math]\displaystyle{ path^k = [start] }[/math] (инициализировать путь муравья).
- Пока путь [math]\displaystyle{ path^k }[/math] не содержит все вершины:
- [math]\displaystyle{ i }[/math] = текущая вершина муравья.
- [math]\displaystyle{ J_i^k }[/math] = множество непосещённых вершин из [math]\displaystyle{ i }[/math].
- Для каждой вершины [math]\displaystyle{ j }[/math] в [math]\displaystyle{ J_i^k }[/math]:
- Вычислить вероятность [math]\displaystyle{ p_{ij}^k }[/math] по формуле правила построения пути.
- Выбрать следующую вершину [math]\displaystyle{ j }[/math] случайно, с вероятностями [math]\displaystyle{ p_{ij}^k }[/math] (например, методом колеса рулетки).
- Добавить [math]\displaystyle{ j }[/math] в [math]\displaystyle{ path^k }[/math].
- Вычислить длину пути [math]\displaystyle{ L_k }[/math].
- Найти муравья с наименьшей длиной пути [math]\displaystyle{ L_{min} }[/math] в этой итерации.
- Если [math]\displaystyle{ L_{min} \lt L_{best} }[/math], то [math]\displaystyle{ L_{best} = L_{min} }[/math], [math]\displaystyle{ path_{best} = path^{min} }[/math].
- Для каждого ребра [math]\displaystyle{ (i, j) }[/math]:
- [math]\displaystyle{ \Delta \tau_{ij} = 0 }[/math]
- Для каждого муравья [math]\displaystyle{ k }[/math] от 1 до [math]\displaystyle{ m }[/math]:
- Если ребро [math]\displaystyle{ (i, j) }[/math] входит в [math]\displaystyle{ path^k }[/math]:
- [math]\displaystyle{ \Delta \tau_{ij} \mathrel{+}= Q / L_k }[/math]
- [math]\displaystyle{ \tau_{ij} = (1 - \rho) \cdot \tau_{ij} + \Delta \tau_{ij} }[/math]
- Если ребро [math]\displaystyle{ (i, j) }[/math] входит в [math]\displaystyle{ path^k }[/math]:
- Вывод: [math]\displaystyle{ path_{best} }[/math], [math]\displaystyle{ L_{best} }[/math].
Последовательная сложность алгоритма
Сложность одной итерации алгоритма оценивается как [math]\displaystyle{ O(m \cdot n^2 + n^2) }[/math], где [math]\displaystyle{ n }[/math] — число вершин в графе, [math]\displaystyle{ m }[/math] — число муравьёв [2].
- Построение пути одним муравьём: на каждом из [math]\displaystyle{ n }[/math] шагов необходимо вычислить вероятности для [math]\displaystyle{ O(n) }[/math] возможных вершин. Сложность для одного муравья — [math]\displaystyle{ O(n^2) }[/math], для всех [math]\displaystyle{ m }[/math] муравьёв — [math]\displaystyle{ O(m \cdot n^2) }[/math].
- Обновление феромона: требует просмотра всех [math]\displaystyle{ O(n^2) }[/math] рёбер и для каждого ребра проверки вклада от [math]\displaystyle{ m }[/math] муравьёв, что дает [math]\displaystyle{ O(m \cdot n^2) }[/math]. Однако на практике часто обновляют феромон только для рёбер, входящих в построенные пути, что может снизить сложность. В худшем случае сложность этапа обновления — [math]\displaystyle{ O(m \cdot n^2) }[/math].
Таким образом, общая сложность [math]\displaystyle{ T }[/math] итераций составляет [math]\displaystyle{ O(T \cdot m \cdot n^2) }[/math]. Основное время работы приходится на этап построения путей муравьями.
Информационный граф
Информационный граф муравьиного алгоритма имеет иерархическую и сильно разветвлённую структуру.
- Верхний уровень: Итерационный процесс. Каждая итерация зависит от результатов предыдущей через глобальную матрицу феромонов.
- Внутри итерации:
- Уровень муравьёв: Процессы построения путей каждым муравьём являются независимыми (в пределах одной итерации) и могут выполняться параллельно. Они читают общую матрицу феромонов [math]\displaystyle{ \tau_{ij} }[/math], но не записывают в неё.
- Уровень шагов муравья: Для каждого муравья построение пути — последовательный процесс. Выбор следующей вершины на шаге [math]\displaystyle{ t+1 }[/math] зависит от текущего частичного пути (множества посещённых вершин) и матрицы феромонов.
- Синхронизация: После завершения всеми муравьями построения путей происходит операция обновления феромонов. Эта операция требует данных от всех муравьёв (построенные пути и их длины).
Граф можно представить как последовательность итерационных блоков. Внутри каждого блока — веер из [math]\displaystyle{ m }[/math] независимых ветвей (муравьи), которые затем сходятся в узле обновления феромона.
Ресурс параллелизма алгоритма
Параллельная сложность одной итерации алгоритма определяется самым длинным последовательным участком [4][5].
- Массовый параллелизм: Построение путей отдельными муравьями в пределах одной итерации полностью независимо и может выполняться параллельно. Таким образом, доступен параллелизм степени [math]\displaystyle{ O(m) }[/math]. Вычисление вероятностей для одного муравья на одном шаге также может быть распараллелено по непосещённым вершинам, что даёт параллелизм степени [math]\displaystyle{ O(n) }[/math].
- Скошенный параллелизм: Внутри процесса построения пути одним муравьём параллелизм отсутствует, так как шаги строго последовательны.
- Глобальное обновление феромона: Операции обновления феромона для разных рёбер теоретически независимы и могут выполняться параллельно, обеспечивая параллелизм степени [math]\displaystyle{ O(n^2) }[/math]. Однако необходимо суммирование вкладов от разных муравьёв для каждого ребра, что требует либо редукции, либо разделения данных.
Таким образом, теоретически, при неограниченном числе процессоров, длительность одной итерации может быть сведена к [math]\displaystyle{ O(n) }[/math] (время построения пути одним муравьём) плюс [math]\displaystyle{ O(\log m) }[/math] (время сбора информации от муравьёв для обновления феромона) плюс [math]\displaystyle{ O(1) }[/math] (параллельное обновление рёбер). На практике доминирующим является параллелизм на уровне муравьёв ([math]\displaystyle{ O(m) }[/math]).
Входные и выходные данные алгоритма
Входные данные [6]:
- Матрица расстояний [math]\displaystyle{ D }[/math] размером [math]\displaystyle{ n \times n }[/math]. Для задачи TSP это плотная матрица, для других задач может быть разреженной.
- Параметры алгоритма: [math]\displaystyle{ \alpha, \beta, \rho, Q, m, iter_{max} }[/math]. Скаляры.
- Начальный уровень феромона [math]\displaystyle{ \tau_0 }[/math] (скаляр).
Объем входных данных: Доминирующий объём — матрица расстояний, [math]\displaystyle{ n^2 }[/math] элементов. Параметры — константное число скаляров.
Выходные данные:
- Вектор [math]\displaystyle{ path_{best} }[/math] длины [math]\displaystyle{ n }[/math], представляющий собой последовательность вершин лучшего найденного гамильтонова цикла.
- Скаляр [math]\displaystyle{ L_{best} }[/math] — длина лучшего найденного пути.
Объем выходных данных: [math]\displaystyle{ n + 1 }[/math] элемент.
Свойства алгоритма
- Соотношение последовательной и параллельной сложности: Последовательная сложность — [math]\displaystyle{ O(T \cdot m \cdot n^2) }[/math]. Параллельная сложность (идеализированная) — [math]\displaystyle{ O(T \cdot n) }[/math]. Выигрыш от параллелизации значителен и ограничен в основном числом муравьёв [math]\displaystyle{ m }[/math] [5].
- Вычислительная мощность: Алгоритм выполняет большое количество операций ([math]\displaystyle{ O(T \cdot m \cdot n^2) }[/math]) по отношению к объёму входных ([math]\displaystyle{ n^2 }[/math]) и выходных ([math]\displaystyle{ n }[/math]) данных. Мощность высокая — [math]\displaystyle{ O(T \cdot m) }[/math], что благоприятно для реализации на ускорителях [4].
- Устойчивость: Алгоритм стохастичен и не гарантирует нахождения глобального оптимума [2]. Результаты могут незначительно меняться от запуска к запуску из-за случайного выбора. Устойчивость к малым изменениям в входных данных зависит от конкретной задачи и параметров.
- Сбалансированность: На этапе построения путей нагрузка между муравьями сбалансирована, так как каждый строит путь одинаковой длины [math]\displaystyle{ n }[/math]. Однако, время выбора вершин может незначительно варьироваться из-за стохастичности. Этап обновления феромона хорошо сбалансирован при параллелизации по рёбрам.
- Детерминированность: Алгоритм является недетерминированным ввиду вероятностного характера построения пути [3]. Разные запуски с одним и тем же начальным состоянием могут давать разные результаты.
- Степень исхода вершин информационного графа:
- Матрица феромонов имеет высокую степень исхода — её данные используются всеми муравьями на каждом шаге построения пути.
- Данные о лучшем пути имеют низкую степень исхода (используются только для вывода).
- "Длинные" дуги: Глобальная матрица феромонов создаёт длинные дуги от операции обновления на итерации [math]\displaystyle{ t }[/math] ко всем операциям выбора пути на итерации [math]\displaystyle{ t+1 }[/math].
Программная реализация алгоритма
Особенности реализации последовательного алгоритма
- Для эффективности часто используют "кандидатские списки" — для каждой вершины хранят список ближайших соседей, чтобы сократить перебор при вычислении вероятностей [2].
- Важно оптимизировать вычисление вероятностей, чтобы избежать многократных вычислений знаменателя.
- Для хранения матрицы феромонов и расстояний используют двумерные массивы. При больших [math]\displaystyle{ n }[/math] необходимо следить за использованием памяти.
- Разрядность: для большинства задач достаточно точности `float` для хранения феромонов и вероятностей, что ускоряет вычисления и экономит память. Для вычисления длин путей может потребоваться `double`.
Возможные способы и особенности параллельной реализации алгоритма
- Распараллеливание по муравьям (Data Parallelism): Наиболее естественный способ [4]. Каждому потоку/процессу назначается подмножество муравьёв. После построения путей требуется глобальная редукция для обновления лучшего пути и матрицы феромонов. Хорошо подходит для OpenMP (на многоядерных CPU) и CUDA/OpenCL (на GPU). Необходимо обеспечить атомарность при обновлении лучшего решения.
- Распараллеливание по графу (Task Parallelism): При очень больших графах можно распределить вершины или рёбра между процессами. Это более сложно из-за необходимости коммуникации при построении пути муравьём, который "переходит" между разными частями графа. Может быть эффективно для распределённых систем с помощью MPI.
- Гибридные подходы: Комбинация MPI для распределения муравьёв по узлам кластера и OpenMP для параллельной обработки муравьёв внутри узла [5].
Результаты прогонов
Выводы для классов архитектур
- Многоядерные CPU (OpenMP): Алгоритм хорошо масштабируется с числом муравьёв [4]. Критическим местом является этап обновления феромона, который может стать узким местом из-за необходимости синхронизации доступа к общей памяти. Рекомендуется использовать локальные копии матрицы феромонов для каждого потока с последующей редукцией.
- GPU (CUDA/OpenCL): Идеальная платформа благодаря массовому параллелизму на уровне муравьёв. Каждый муравей может быть представлен как отдельный поток. Необходимо тщательно управлять доступом к глобальной памяти (матрица феромонов) для избежания конфликтов. Использование разделяемой памяти и кандидатских списков может значительно повысить производительность.
- Кластеры (MPI): Эффективность зависит от балансировки нагрузки между узлами. Широковещательная рассылка матрицы феромонов после каждой итерации может создать значительный сетевой трафик. Рекомендуется использовать асинхронные коммуникации и, возможно, уменьшать частоту глобального обновления [5].
Литература
- ↑ 1,0 1,1 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, 26(1), 29-41.
- ↑ 2,0 2,1 2,2 2,3 2,4 Dorigo, M., & Stützle, T. (2004). Ant Colony Optimization. MIT Press.
- ↑ 3,0 3,1 Blum, C. (2005). Ant colony optimization: Introduction and recent trends. Physics of Life reviews, 2(4), 353-373.
- ↑ 4,0 4,1 4,2 4,3 Randall, M., & Lewis, A. (2002). A parallel implementation of ant colony optimization. Journal of Parallel and Distributed Computing, 62(9), 1421-1432.
- ↑ 5,0 5,1 5,2 5,3 Pedemonte, M., Nesmachnow, S., & Cancela, H. (2011). A survey on parallel ant colony optimization. Applied Soft Computing, 11(8), 5181-5197.
- ↑ Stützle, T., López-Ibáñez, M., & Dorigo, M. (2010). A Concise Overview of Applications of Ant Colony Optimization. In Wiley Encyclopedia of Operations Research and Management Science.