Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2022
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866916555036557312 |
|---|---|
| author | Goh, Yong Liang Lee, Wee Sun Bresson, Xavier Laurent, Thomas Lim, Nicholas |
| author_facet | Goh, Yong Liang Lee, Wee Sun Bresson, Xavier Laurent, Thomas Lim, Nicholas |
| contents | The traveling salesman problem is a fundamental combinatorial optimization problem with strong exact algorithms. However, as problems scale up, these exact algorithms fail to provide a solution in a reasonable time. To resolve this, current works look at utilizing deep learning to construct reasonable solutions. Such efforts have been very successful, but tend to be slow and compute intensive. This paper exemplifies the integration of entropic regularized optimal transport techniques as a layer in a deep reinforcement learning network. We show that we can construct a model capable of learning without supervision and inferences significantly faster than current autoregressive approaches. We also empirically evaluate the benefits of including optimal transport algorithms within deep learning models to enforce assignment constraints during end-to-end training. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2203_00903 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem Goh, Yong Liang Lee, Wee Sun Bresson, Xavier Laurent, Thomas Lim, Nicholas Machine Learning Artificial Intelligence Optimization and Control The traveling salesman problem is a fundamental combinatorial optimization problem with strong exact algorithms. However, as problems scale up, these exact algorithms fail to provide a solution in a reasonable time. To resolve this, current works look at utilizing deep learning to construct reasonable solutions. Such efforts have been very successful, but tend to be slow and compute intensive. This paper exemplifies the integration of entropic regularized optimal transport techniques as a layer in a deep reinforcement learning network. We show that we can construct a model capable of learning without supervision and inferences significantly faster than current autoregressive approaches. We also empirically evaluate the benefits of including optimal transport algorithms within deep learning models to enforce assignment constraints during end-to-end training. |
| title | Combining Reinforcement Learning and Optimal Transport for the Traveling Salesman Problem |
| topic | Machine Learning Artificial Intelligence Optimization and Control |
| url | https://arxiv.org/abs/2203.00903 |