A Comparative Study on Genetic algorithm and Reinforcement Learning to Solve the Traveling Salesman Problem

Abstract

Machine Learning (ML) and Evolutionary Computing (EC) are the two most popular computational methodologies in computer science to solve learning and optimization problems around us, respectively. It is of research interest in the literature, for exploring these two methodologies and to formulate algorithmic frameworks with 'EA for ML' and 'ML for EA' where EA stands for Evolutionary Algorithm. The objective of this paper is on exploring this dimension of research. The Traveling Salesman Problem (TSP) is one of the NP-hard (nondeterministic polynomial time hard) problems in combinatorial optimization problems. The solution for a TSP is the shortest path covering all the nodes in a given city. This paper compares two algorithms, "Genetic Algorithm (GA)" of the EC domain and "Epsilon-Greedy Q-Learning Algorithm (EQLA)" of the ML domain on solving TSP. The detailed design methodology involved in both these algorithms is discussed in this paper. The experiments are carried out on two different data sets (random and ATT48) to compare the speed and accuracy of the algorithms. The comparative results reveal that the GA could solve the TSP more effectively than EQLA. The obtained inferences along with the limitations are presented in this paper.