Архив публикаций

Тезисы

XXXIII-ая конференция

Исследования параллельных реализаций метаэвристического метода муравьиных колоний для решения параметрических задач

Титов Ю.П.

Московский Авиационный Институт (Национальный Исследовательский Университет) Россия, 125993, г. Москва, Волоколамское шоссе, д. 4 E-mail:kalengul@mail.ru

Работа посвящена исследованию и разработке матричных модификаций метода муравьиных колоний (ACO) для эффективного решения параметрических задач на гетерогенных вычислительных системах. Основная идея заключается в представлении алгоритма в виде матричных преобразований, что позволяет задействовать параллельные вычисления на центральных процессорах с использованием SIMD-инструкций (SSE/AVX), параллелизма на основе OpenMP и на графических ускорителях с архитектурой CUDA [1].

Параметрическая задача формулируется как задача поиска оптимальных (или рациональных) значений входных параметров системы, обеспечивающих экстремальные значения заданных критериев качества. В работе исследуется задача дискретной оптимизации в условиях, когда вычисление целевой функции является «чёрным ящиком» и составляет основную вычислительную стоимость. Для решения подобной задачи модификациями метода муравьиных колоний лежит формализация параметрической задачи в виде матрицы значений и соответствующих матриц феромонов и посещений. Разработанный алгоритм разделён на три независимых этапа: подготовка и нормализация матриц, поиск путей популяцией из K муравьёв-агентов, обновление феромонных весов (испарение и добавление). Каждый этап может выполняться параллельно — на CPU или GPU.

Для эффективного использования SIMD-инструкций AVX, требующих кратности данных 4, предложены два подхода: работа с транспонированными матрицами, где внутренние циклы выполняются по количеству слоёв графа, и использование специализированного параметрического графа с количеством вершин в слое, равным 4 [2]. Эксперименты на процессорах Intel 12-13 поколений и AMD Ryzen показали, что матричная модификация с AVX и OpenMP обеспечивает ускорение до 13 раз по сравнению с классическим ACO (например, время снижается с 143.52 мс ± 17.26 до 11.55 мс ± 2.30 на слой на Intel Core i5-12450H при различных размерностях параметрической задачи).

Реализация на GPU с использованием CUDA позволила достичь ещё более значительного ускорения. На сервере с NVIDIA Tesla V100 модификация MatrixACO_Optimal выполняет одну итерацию для слоя за 1.58 мс ± 0.08, что в 32.7 раза быстрее базового алгоритма. Максимальное ускорение до 43 раз получено для задачи с 128 параметрами [1]. Разработана также гетерогенная модификация, в которой этапы работы с матрицами выполняются на CPU с AVX, а поиск путей — на GPU. На конфигурации с Intel Core i5-12450H и NVIDIA GeForce RTX 3060 это дало время 5.78 мс ± 1.64 на слой, что соответствует ускорению в 24.8 раза.

Предложенные модификации ACOCNI и ACOCCyN, использующие хэш-таблицы для исключения повторных вычислений целевой функции, успешно применены для решения практической задачи — оптимизации параметров модели SARIMA при прогнозировании пассажирских и грузовых авиаперевозок [3, 4]. В результате получены параметры (p=1, d=2, q=3, P=3, D=0, Q=3), обеспечивающие значительное улучшение критериев по сравнению с методом auto_arima: MAE 90.16 против 942.36, RMSE 114.78 против 1231.19, AIC 569.70 против 589.95.

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

Литература

1. Sudakov V., Titov Y. Matrix-Based ACO for Solving Parametric Problems Using Heterogeneous Reconfigurable Computers and SIMD Accelerators // Mathematics. – 2025. – N13. – V1284. DOI:10.3390/math13081284

2. Титов Ю.П. Исследование структуры гетерогенного реконфигурируемого вычислителя для эффективной работы матричного метода муравьиных колоний // Современные информационные технологии и ИТ-образование, [S.l.]. –2025. Т. 21, № 2, http://sitito.cs.msu.ru/index.php/SITITO/article/view/1191

3. Titov Yu.P., Sinitsyn I.N. Control of Set of System Parameter Values by the Ant Colony Method // Automation and Remote Control – 2023. – Vol. 84, No. 8. – P. 893-903. DOI:10.1134/S0005117923080106.

4. Titov Yu.P., Sudakov V.A. Investigation of the Parametric Graph Model in the Ant Colony Method // Mathematical Models and Computer Simulations. – 2025. – V. – 17, N. 2, – p.126–136 DOI:10.1134/S2070048224700996

• открыть в PDF формате (на английском языке) (PDF)