Linear Function Approximation as a Resource Efficient Method to Solve the Travelling Salesman Problem
DOI:
https://doi.org/10.47611/jsrhs.v10i4.2143Keywords:
Linear Function Approximation, Travelling Salesman Problem, Combinatorial Optimization, Machine Learning, Reinforcement LearningAbstract
This paper presents an approach to combinatorial optimization problems using linear function approximation (LFA) to solve the Travelling Salesman Problem (TSP). We create a reinforcement learning model in which we parameterize our policy using linear function approximation instead of the more commonly used neural networks. We then evaluated our models based on two factors: training time and optimality. When we compared our results with a state-of-the-art neural network solver, we found that our model was able to solve the TSP accurately while using drastically less computational resources and time to train than the neural network algorithm (Kool et al., 2019).
Downloads
References or Bibliography
Applegate, D., Bixby, R., Chvatal, V., and Kool, W. (2003). Concorde tsp solver.
Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. (2017). Neural combinatorial optimization with reinforcement learning.
Cappart, Q., Chételat, D., Khalil, E., Lodi, A., Morris, C., and Velickovíc, P. (2021). Combinatorial optimization and reasoning with graph neural networks.
Cappart, Q., Moisan, T., Rousseau, L.-M., Pr ́emont-Schwarz, I., and Cire, A. (2020). Combining reinforcement learning and constraint programming for combinatorial optimization.
Drori, I., Kharkar, A., Sickinger, W. R., Kates, B., Ma, Q., Ge, S., Dolev, E., Dietrich, B., Williamson, D. P., and Udell, M. (2020). Learning to solve combinatorial optimization problems on real-world graphs in linear time.
Gurobi Optimization, LLC (2021). Gurobi Optimizer Reference Manual.
Joshi, C. K., Laurent, T., and Bresson, X. (2019). An efficient graph convolutional network technique for the travelling salesman problem.
Kool, W., van Hoof, H., and Welling, M. (2019). Attention, learn to solve routing problems!
Mazyavkina, N., Sviridov, S., Ivanov, S., and Burnaev, E. (2020). Reinforcement learning for combinatorial optimization: A survey.
Mulder, S. and Wunsch, D. (2003). Million city traveling salesman problem solution by divide and conquer clustering with adaptive resonance neural networks.
Published
How to Cite
Issue
Section
Copyright (c) 2022 Rolan Guang; Sajad Khodadian
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Copyright holder(s) granted JSR a perpetual, non-exclusive license to distriute & display this article.
