Traveling Salesman Problem - danielwilczak101/EasyGA GitHub Wiki
The traveling salesman problem is a famous computer science problem. The problem is to find the shortest path through a set of points. Although the problem is considered NP-hard, it is possible to find heuristic (estimated) solutions.
Solution (GitHub source code)
One strategy for estimating solutions is the nearest neighbor strategy, which adds on the nearest point repeatedly until all of the points are used up.
A similar but more efficient strategy would be to add points to the path randomly, but to insert them onto the path which adds as little as possible to the overall length of the path. We refer to this here as greedy insertion.
Using EasyGA, this estimating strategy can be used to further refine estimates to the traveling salesman problem.
The fitness function is just the length of the path.
The population was initialized by applying greedy insertion, starting with nothing.
The crossover of two chromosomes was done by extracting segments of the paths they shared and then greedily inserting the remaining points.
To mutate a chromosome, n1/2 points were removed and then greedily inserted back.
Additionally, a custom adapt population method was used to occasionally check for possible improvements. Particularly, the two-and-a-half-opt method was used.
Once downloaded, the TSP Solver may be used quite easily:
from TSP_Solver import TSP_Solver
# List of points used
data = [...]
# Solver object
solver = TSP_Solver(data)
# Run until termination
solver.evolve()
# Show the best path by the indexes for the data
solver.print_best_chromosome()View the source code for additional details, such as how to make gifs.
View many examples here.
One example involving 1000 points:
