“`html
Новое решение для проблемы коммивояжера (TSP) – CycleFormer
Множество новаторских моделей, включая ChatGPT, Bard, LLaMa, AlphaFold2 и Dall-E 2, появились в различных областях с момента появления трансформера в обработке естественного языка (NLP). Попытки решить комбинаторные задачи оптимизации, такие как проблема коммивояжера, с использованием глубокого обучения прогрессировали логически от сверточных нейронных сетей (CNN) к рекуррентным нейронным сетям (RNN), и, наконец, к моделям на основе трансформера.
Практические решения и ценность
Использование координат N городов (узлов, вершин, токенов) для определения кратчайшего гамильтонова цикла, проходящего через каждый узел, представляет собой сложную задачу с экспоненциально растущей вычислительной сложностью. Несмотря на это, исследователи из Сеульского национального университета представили CycleFormer, решение TSP на основе трансформеров, которое способно превзойти существующие модели благодаря уникальным характеристикам и улучшениям.
С учетом экспериментальных результатов, CycleFormer может превзойти лучшие модели на основе трансформеров, сохраняя форму трансформера в TSP-50, TSP-100 и TSP-500. Отличие в оптимальности между SOTA и TSP-500 во время декодирования множественного запуска составляет от 3,09% до 1,10%, что является улучшением в 2,8 раза благодаря CycleFormer.
Предложенная модель CycleFormer имеет потенциал превзойти существующие альтернативы, такие как Pointerformer, и может быть доработана с использованием дополнительных подходов LLM, таких как увеличение размерности вложения и добавление нескольких блоков внимания, для улучшения производительности. Кроме того, планируется включение MCTS в качестве пост-обработки в будущих исследованиях для дальнейшего улучшения производительности CycleFormer.
Для получения дополнительной информации, ознакомьтесь с исследованием.
“`
