Meta-heuristic Search Algorithms are very efficient optimization techniques when it comes to problems that require large solution space. Instead of giving exact solution, it tries to produce an approximate one that takes less time. These algorithms are problem independent and hence can be applied to a wider variety of problems. Some popular meta-heuristic algorithms in the literature are Genetic Algorithms, Simulated Annealing, Ant Colony Optimization etc.
In this project, we have tried to harness the Genetic Algorithms to solve the travelling salesman problem on ATT48 dataset from TSPLIB and tried to find a solution that has a minimum cost of around 21,000 approx.
- Name: ATT48 TSP Dataset
- Source: TSPLIB
- Contains Aerial Co-ordinates of 48 capital of the US
Name: TSP with GA.cpp
C++
Name: README.pdf
Udit Chakraborty, “Introduction to soft computing Neuro-fuzzy and Genetic Algorithms”, Chapter 12, Page 14, Pearson India, 2013