This assignment, Traveling Salesperson Problem (TSP), consists of the three different parts:
- Part A: Develop a TSP solver;
- Part B: Connect to a database; and
- Part C: Develp a GUI-based TSP solver.
In this blog, I will primarily focus on the development of a TSP solver based on Genetic Algorithm and one of the SQL queries embedded in the solver.
What is TSP?
The goal of TSP is to identify a minimum cost route where a salesperson is expected to visit every n city only once and return (Deng et al., 2015; Sebő and Vygen, 2012). There are two importance conditions to be noted here: first, a salesperson visits every city once and only once; and second, a salesperson returns to the origin city. The first concept on TSP was found in 1759 when Euler was interested in solving the knights’ journey (Jiao and Wang, 2000), followed by a manual originating from 1832 for the scenarios of salesperson travelling 45 German cities without mathematical consideration (Yu et al., 2014). In the 1800s, two mathematicians, Sir William Hamilton and Thomas Kirkman, studied TPS devising mathematical formulations (Matai et al., 2010; Yu et al., 2014). It is, however, noted that the more general form of TSP was initially studied in 1930s by Karl Menger in Vienna and Harvard (Matai et al., 2010). Since then, TSP has fascinated many researchers for several decades as it is a classic non-deterministic polynomial time hard (NP hard) problem.
Why Genetic Algorithm?
I did not know what was TSP before starting this assignment so I started to read about the origin and the available solutions for TSP initially. On the second day, when I was looking at some twitter blogs, this article blogged by Eric Stoltz featured in Towards Data Science series came to my attention. The blog, “Evolution of a salesman: A complete genetic algorithm tutorial for Python”, timely gave me a ‘guidance’ (when I was looking for an algorithm to implement) that my fate was developing a TSP solver based on Genetic Algorithm (GA). With this decision, I started to read some papers (references available at the bottom of this blog) and considered that given the time frame, I would try to customise many specific steps in GA by implementing some approaches from the papers.
What is Genetic Algorithm?
GA is one of the simplest random-based evolutionary algorithms where the core concept stems from the Charles Darwin’s “survival of fittest” theory (Gad, 2018). Evolutionary algorithms are dynamic because they can “evolve” over time over “generations”. In a holistic picture, GA is based on cycles of four steps where each cycle/loop represents an evolution of a generation. The four steps are composed of:
- Crossover; and
Gene in the TSP context is an individual city with its x and y coordinate. Chromosome is a solution consists of the list of genes, hence representing a path of the combined cities where every city is visited only once in the TSP context. Population is a set of chromosomes. In the initialisation step, this would be a set of paths generated from a list of cities for each problem. Individual city was implemented as a class suggested by Eric Stoltz’s blog.
The key concept of the whole evolutions is ‘fitness to survive’. Through reading some papers, this fitness is in general calculated as an inverse of total tour length of cities. The shorter the total tour length is, the better the solution is. This means the fitness score is considered best where it is greater (because fitness is inverse of the tour length).
Based on the aforementioned concepts of gene, chromsome, and fitntess, the following pseudo algorithm is adopted from Dwivedi et al. (2012) to provide an overview of GA.
Initialisation of population
Deng et al. (2015) posits that an initialisation strategy of chromosome and population is important for optimisation. This project implements random and nearest-neighbour initialisation for population.
Razali and Geraghty (2011) noted that selection is one of the important process in GA, experimenting different selection strategies to gauge performance. As a result of the tests, tournament selection strategy was considered to produce best solution quality for small size problems with low computing times than roulette wheel-based selection strategies. However, because of more randomness in this strategy, convergence becomes slower as the size grows. In addition, if the size increases larger, it was found that tournament selection tends to resort to premature convergence. To alleviate this, rank-based roulette wheel selection is used for larger sized problems where paths are assigned with a linear rank function rather than with a proportion of a fitness score. Rank-based roulette wheel selection prevents premature convergence but is considered to be computationally-expensive. Therefore, this project implemented tournament selection strategy for small size TSP and rank-based roulette wheel selection strategy for large size TSP.
This project implemented two crossover methods: simple and edge recombination, which were combined together to create new paths. In simple crossover, two points in the first selected path are determined randomly, passing between-points cities to a new path. Any cities missing from a new path is then filled from the second selected path. Edge recombination, informed by Liu (2014)’s edgy swapping crossover, is implemented based on pseudo algorithm listed on webpage. On step 1, after selecting two existing paths similar to simple crossover, edges of each path is collated. On step 2, a union set is performed to get a unique adjacency matrix. On step 3, initialise the first city from a random parent. Most importantly, on step 4, create a new path in a loop by adding the city with the fewest neighbours or randomly selecting the city if there is no neighbour.
Mutation introduces diversity into paths. In this project, simple swap mutation is implemented.
These were main four steps of the GA process. After the mutation step, the whole evolution process is to be looped through within a specified time frame.
Query to obtain the best result for each TSP
As part of the assignment requirements, the solutions generated were stored in the database. From the database, the query below is to retrieve the solution with a minimum distance for a particular TSP.
With the aforementioned specific implementation, a greater variety of TSPs was run with the parameters of:
- Mixed initialisation strategy;
- Crossover strategy composed of half simple and half edge recombination;
- Mutation threshold rate of 0.6;
- Elitism rate of 0.6;
- Population size of 100,000; and
- Time limit of 600 seconds.
|TSP||eli51.tsp (optimal: 426)||berlin52.tsp(optimal: 7542)||d493.tsp (optimal: 35002)||d1655.tsp (optimal: 62128)||usa13509.tsp (optimal: [19947008, 19982889])|
I have compared some of these results with those of my classmates and the result from the Simulated Annealing approach implemented by one classmate outperformed this GA. Overall, this TSP solver produced a reasonable, but not the best, result for each problem.
This assignment was quite fun to code and taught me a great lesson - programming is not just about coding to solve direct problems. Rather, there were many side aspects to consider to integrate the solver, the database, and the GUI together. Initially, I did not like to work on the GUI, thinking too much to do in order to make a little component of the GUI. However, while I was working on it, the thought process of “If I am a user, how would I behave in this particular situation to achieve my goal?” became a norm and I do think that this is a valuable point in developing a program.
A. Sebő and J. Vygen, “Shorter Tours by Nicer Ears: 7/5-approximation for graphic TSP, 3/2 for the path version, and 4/3 for two-edge-connected subgraphs”, arXiv:1201.1870v3 [cs.DM], Mar. 2012.
B. Johnson, “Genetic Algorithms: The Travelling Salesman Problem”, on Medium, https://medium.com/@becmjo/genetic-algorithms-and-the-travelling-salesman-problem-d10d1daf96a1, accessed on 22nd July 2018.
E. Stortz, “Evolution of a salesman: A complete genetic algorithm tutorial for Python”, on Medium, https://towardsdatascience.com/evolution-of-a-salesman-a-complete-genetic-algorithm-tutorial-for-python-6fe5d2b3ca35, accessed on 22nd July 2018.
J. Yu, D. Yue, D, and F. You, Traveling salesman problems, https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems, last modified on 26th May 2014, accessed on 21st July 2018.
M. Hahsler and K. Hornik, “TSP – Infrastructure for the Traveling Salesperson Problem”, Journal of Statistical Software, vol. 23 issue. 2, p. 1–21, 2007.
N. M. Razali and J. Geraghty, “Genetic Algorithm Performance with Different Selection Strategies in Solving TSP”, Proceedings of the World Congress on Engineering, Jul. 2011.
R. Matai, S. Singh, and M. Lal, “Traveling salesman problem: An overview of applications, formulations, and solution approaches”, In D. Davendra (Ed.), Traveling Salesman Problem, Theory and Applications, InTech, 2010.
V. Dwivedi, T. Chauhan, S. Saxena, and P. Agrawal, “Travelling Salesman Problem using Genetic Algorithm”, National Conference on Development of Reliable Information Systems, Techniques and Related Issues, 2012.
Y. Deng, Y Liu, and D. Zhou, “An Improved Genetic Algorithm with Initial Population Strategy for Symmetric TSP,” Mathematical Problems in Engineering, vol. 2015, Article ID 212794, 6 pages, 2015. https://doi.org/10.1155/2015/212794, accessed on 22nd July 2018.