The idea is to provide an easy, short and non-optimized example of an approximate solution to the TSP through a Genetic Algorithm. By no means the aim was to write a well performing algorithm, it's only intended as an example of GAs to give a showcase of their applicability in solving NP-hard problems.
The script works both on python 2.7 and 3. The only dependency is turtle, used for the graphical methods and easily installable through pip.
An acceptable solution is an Hamiltonian path that cycles on the N nodes. Using the permutation encoding paradigm it's representable as an array of length N containing at every i-th position (from 1 to N) the label of the node to visit at the step i. One array is regarded as an individual in the GAs context.
The algorithm starts with a population of N_POPULATION
inviduals, each individual is of length N_CITIES
(N) and generated randomly (abiding to the rules of Hamiltonian paths).
- The fitness function uses the total length of the path to score the quality of each individual.
- Selection occurs through a tournament of size
K_TOURNAMENT
and uniform probability. - Crossover is a single point crossover and takes place between the
P_ELITISM * N_POPULATION
of best fit individuals. - Mutation is a bit string mutation that swaps two values in the array.
The following two examples are both results (with a different seed) of the provided TSP_GA_example.py script. All the parameters are freely modifiable, different values will result in better/worse solutions. The disposition of the points (vertices, cities) can swap between circular and random changing the constant IS_CIRCLE
.
E.g 1 and 2 use 100 nodes with a population of 300 individuals.
The time needed to elapse 6000 generations on a 4RAM/2.2GHz computer with no other processes open is < 5 minutes. If graphical updates are removed the time improves remarkably.
The nodes are placed in circle to highlight the improvements of each generation, it's visibly obvious that the best possible Hamiltonian path is the one that draws the circle itself and in this example, using a circle radius of 200p, the global optimum length (the circumference) is 1256p.
Best individual of the 1st, 1500th, 3000th and 6000th generation (read from left to right):
Same as the previous example, but the placement of the nodes is randomized and it's harder for humans to predict the best global solution.
Best individual of the 1st, 1500th, 3000th and 6000th generation: