Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , , , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866916441086754816 |
|---|---|
| author | Xiao, Yubin Wang, Di Li, Boyang Chen, Huanhuan Pang, Wei Wu, Xuan Li, Hao Xu, Dong Liang, Yanchun Zhou, You |
| author_facet | Xiao, Yubin Wang, Di Li, Boyang Chen, Huanhuan Pang, Wei Wu, Xuan Li, Hao Xu, Dong Liang, Yanchun Zhou, You |
| contents | The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem with broad real-world applications. Recently, neural networks have gained popularity in this research area because as shown in the literature, they provide strong heuristic solutions to TSPs. Compared to autoregressive neural approaches, non-autoregressive (NAR) networks exploit the inference parallelism to elevate inference speed but suffer from comparatively low solution quality. In this paper, we propose a novel NAR model named NAR4TSP, which incorporates a specially designed architecture and an enhanced reinforcement learning strategy. To the best of our knowledge, NAR4TSP is the first TSP solver that successfully combines RL and NAR networks. The key lies in the incorporation of NAR network output decoding into the training process. NAR4TSP efficiently represents TSP encoded information as rewards and seamlessly integrates it into reinforcement learning strategies, while maintaining consistent TSP sequence constraints during both training and testing phases. Experimental results on both synthetic and real-world TSPs demonstrate that NAR4TSP outperforms five state-of-the-art models in terms of solution quality, inference speed, and generalization to unseen scenarios. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2308_00560 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems Xiao, Yubin Wang, Di Li, Boyang Chen, Huanhuan Pang, Wei Wu, Xuan Li, Hao Xu, Dong Liang, Yanchun Zhou, You Artificial Intelligence The Traveling Salesman Problem (TSP) is a well-known combinatorial optimization problem with broad real-world applications. Recently, neural networks have gained popularity in this research area because as shown in the literature, they provide strong heuristic solutions to TSPs. Compared to autoregressive neural approaches, non-autoregressive (NAR) networks exploit the inference parallelism to elevate inference speed but suffer from comparatively low solution quality. In this paper, we propose a novel NAR model named NAR4TSP, which incorporates a specially designed architecture and an enhanced reinforcement learning strategy. To the best of our knowledge, NAR4TSP is the first TSP solver that successfully combines RL and NAR networks. The key lies in the incorporation of NAR network output decoding into the training process. NAR4TSP efficiently represents TSP encoded information as rewards and seamlessly integrates it into reinforcement learning strategies, while maintaining consistent TSP sequence constraints during both training and testing phases. Experimental results on both synthetic and real-world TSPs demonstrate that NAR4TSP outperforms five state-of-the-art models in terms of solution quality, inference speed, and generalization to unseen scenarios. |
| title | Reinforcement Learning-based Non-Autoregressive Solver for Traveling Salesman Problems |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2308.00560 |