Test-Time Augmentation for Traveling Salesperson Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914788302389248 |
|---|---|
| author | Ishiyama, Ryo Shirakawa, Takahiro Uchida, Seiichi Matsuo, Shinnosuke |
| author_facet | Ishiyama, Ryo Shirakawa, Takahiro Uchida, Seiichi Matsuo, Shinnosuke |
| contents | We propose Test-Time Augmentation (TTA) as an effective technique for addressing combinatorial optimization problems, including the Traveling Salesperson Problem. In general, deep learning models possessing the property of invariance, where the output is uniquely determined regardless of the node indices, have been proposed to learn graph structures efficiently. In contrast, we interpret the permutation of node indices, which exchanges the elements of the distance matrix, as a TTA scheme. The results demonstrate that our method is capable of obtaining shorter solutions than the latest models. Furthermore, we show that the probability of finding a solution closer to an exact solution increases depending on the augmentation size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_04767 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Test-Time Augmentation for Traveling Salesperson Problem Ishiyama, Ryo Shirakawa, Takahiro Uchida, Seiichi Matsuo, Shinnosuke Machine Learning Artificial Intelligence We propose Test-Time Augmentation (TTA) as an effective technique for addressing combinatorial optimization problems, including the Traveling Salesperson Problem. In general, deep learning models possessing the property of invariance, where the output is uniquely determined regardless of the node indices, have been proposed to learn graph structures efficiently. In contrast, we interpret the permutation of node indices, which exchanges the elements of the distance matrix, as a TTA scheme. The results demonstrate that our method is capable of obtaining shorter solutions than the latest models. Furthermore, we show that the probability of finding a solution closer to an exact solution increases depending on the augmentation size. |
| title | Test-Time Augmentation for Traveling Salesperson Problem |
| topic | Machine Learning Artificial Intelligence |
| url | https://arxiv.org/abs/2405.04767 |