Решение задачи коммивояжера с использованием рекуррентной нейронной сети

Предложен новый алгоритм (NWTA-алгоритм) решения задачи коммивояжера. Алгоритм основан на использовании рекуррентной нейронной сети Хопфилда, метода WTA (“Winner takes all”) формирования цикла и метода $2$-opt его оптимизации. Особенностью предложенного алгоритма является использование метода частичных (префиксных) сумм для ускорения решения системы уравнений сети Хопфилда. Для получения дополнительного ускорения выполнено распараллеливание предложенного алгоритма на графическом процессоре с использованием технологии CUDA. На ряде примеров из библиотеки TSPLIB с числом городов от 51 до 2392 показано, что NWTA-алгоритм находит приближенные решения задачи коммивояжера (относительное увеличение длины маршрута по сравнению с оптимальной составляет $0.03\div0.14$). При большом числе городов (130 и выше) время работы NWTA-алгоритма в $4\div24$ раз меньше времени работы эвристического алгоритма LKH, посредством которого получены оптимальные решения для всех примеров из TSPLIB.