Решение задачи коммивояжера с использованием рекуррентной нейронной сети
М.С. Тарков
Институт физики полупроводников им. Акад. А.К. Ржанова Сибирского отделения Российской академии наук, просп. Акад. М.А. Лаврентьева, 13, Новосибирск, 630090
tarkov@isp.nsc.ru
Ключевые слова: задача коммивояжера, нейронная сеть Хопфилда, 2-opt, технология CUDA, LKH-алгоритм
Страницы: 337-347
Аннотация
Предложен новый алгоритм (NWTA-алгоритм) решения задачи коммивояжера. Алгоритм основан на использовании рекуррентной нейронной сети Хопфилда, метода WTA (“Winner takes all”) формирования цикла и метода 2-opt его оптимизации. Особенностью предложенного алгоритма является использование метода частичных (префиксных) сумм для ускорения решения системы уравнений сети Хопфилда. Для получения дополнительного ускорения выполнено распараллеливание предложенного алгоритма на графическом процессоре с использованием технологии CUDA. На ряде примеров из библиотеки TSPLIB с числом городов от 51 до 2392 показано, что NWTA-алгоритм находит приближенные решения задачи коммивояжера (относительное увеличение длины маршрута по сравнению с оптимальной составляет 0.03 ÷ 0.14). При большом числе городов (130 и выше) время работы NWTA-алгоритма в 4 ÷ 24 раз меньше времени работы эвристического алгоритма LKH, посредством которого получены оптимальные решения для всех примеров из TSPLIB.
DOI: 10.15372/SJNM20150308 |
