Математическое моделирование, численные методы и комплексы программ

Метод муравьиных колоний для решения параметрических задач на векторных SIMT-ускорителях

В. А. Судаков^ab, Ю. П. Титов<sup>a

a</sup> Московский авиационный институт (национальный исследовательский университет), г. Москва, 125993, Россия
^b Институт прикладной математики им. М.В. Келдыша РАН, г. Москва, 125047, Россия

Аннотация: Работа посвящена исследованию возможностей параллельной реализации метода оптимизации муравьиными колониями (ACO) на SIMT-ускорителях. Известные модификации параллельного метода муравьиных колоний демонстрируют эффективность при решении задач коммивояжера (TSP) и квадратичного размещения (QAP). Однако необходимость синхронизации и обмена данными ограничивает производительность, достигая максимальной эффективности в крупнозернистых алгоритмах, где каждый поток выполняет полную версию ACO. В связи с развитием и повышением доступности SIMT-ускорителей в работе предложена модификация метода муравьиных колоний, основанная на матричной формализации вычислительного процесса. Предложенный подход расширяет область применения метода на параметрические задачи, направленные на поиск оптимальных значений параметров, минимизирующих или максимизирующих целевую функцию. Разработан алгоритм с поддержкой параллельных вычислений, минимизирующий информационный обмен между агентами. Алгоритм включает три этапа: подготовка матриц для движения муравьев-агентов, определение путей муравьев-агентов, обновление матриц на основе найденных решений. Снижение вычислительной сложности достигается за счет представления оптимизационной задачи в виде параметрического графа с декомпозицией множества значений параметров на подслои. Среди исследованных модификаций метода муравьиных колоний рассматривались ACOCNI и ACOCCyI с усовершенствованной вероятностной формулой для повышения алгоритмической эффективности и использованием хэш-таблицы для улучшения этапа исследования. Предложенные модификации реализованы на графических процессорах с применением технологии CUDA. В результате экспериментальных исследований получено ускорение параллельного метода муравьиных колоний более чем в 15 раз при поиске оптимума многоэкстремальных функций. Перспективы дальнейших исследований связаны с реализацией предложенного алгоритма на гетерогенных вычислительных системах, сочетающих SIMT- и MIMD-компоненты.

Ключевые слова: метод муравьиных колоний, SIMT, CUDA, параметрический граф, оптимизация, параллельные вычисления

УДК: 519.854

MSC: 65Y05, 68W10, 90C27

Получение: 1 июля 2025 г.
Исправление: 29 сентября 2025 г.
Принятие: 20 октября 2025 г.
Публикация онлайн: 19 ноября 2025 г.

DOI: 10.14498/vsgtu2244

Реферативные базы данных:

•