A Comparison of GA Crossover and Mutation Methods for the Traveling Salesman Problem
Peer reviewed, Journal article
Accepted version

View/ Open
Date
2021Metadata
Show full item recordCollections
- Institutt for IKT og realfag [620]
- Publikasjoner fra CRIStin - NTNU [40058]
Original version
Advances in Intelligent Systems and Computing. 2021, 1189 529-542. 10.1007/978-981-15-6067-5_60Abstract
The traveling salesman problem is a very popular combinatorial optimization problem in fields such as computer science, operations research, mathematics and optimization theory. Given a list of cities and the distances between any city to another, the objective of the problem is to find the optimal permutation (tour) in the sense of minimum traveled distance when visiting each city only once before returning to the starting city. Because many real-world problems can be modeled to fit this formulation, the traveling salesman problem has applications in challenges related to planning, routing, scheduling, manufacturing, logistics, and other domains. Moreover, the traveling salesman problem serves as a benchmark problem for optimization methods and algorithms, including the genetic algorithm. In this paper, we examine various implementations of the genetic algorithm for solving two examples of the traveling salesman problem. Specifically, we compare commonly employed methods of partially mapped crossover and order crossover with an alternative encoding scheme that allows for single-point, multipoint, and uniform crossovers. In addition, we examine several mutation methods, including Twors mutation, center inverse mutation, reverse sequence mutation, and partial shuffle mutation. We empirically compare the implementations in terms of the chosen crossover and mutation methods to solve two benchmark variations of the traveling salesperson problem. The experimental results show that the genetic algorithm with order crossover and the center inverse mutation method provides the best solution for the two test cases.