Genetic Algorithm for the Travelling Salesman Problem in Python [Completed]

Hi guys,

ORIGINAL POST | 23 Dec. 2018

I’m currently working on a genetic algorithm for the Travelling Salesman Problem. Those of you, who aren’t already familiar with the problem, it asks the following question:

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city? (cf. wikipedia)

Returning to the origin city is not a priority for me. I’m focussing on the genetic algorithm, instead of a lexicographic brute-force approach.

Here’s a short demo of the genetic approach for 12 cities (vectors) :

It takes a couple of seconds and few resources to compute this.
The brute-force approach would probably need up to 479,001,600 (12! = 12 factorial) iterations/trials to find the perfect route, which would be quite expensive.

I’m going to continually update this thread and probably share the script when it’s done.

UPDATE | 27 Dec. 2018

For now, I consider this endeavour done! I have to move on to other projects, but I’m quite satisfied with how my travelling Salesman Python component turned out.

The brute-force algorithm, as well as the genetic algorithm, are both integrated into a single Python component and can be chosen at will. The cities can be provided as an input or the component generates a random set of cities. It accepts 2d and 3d points or vectors as cities. The component runs smoothly, maybe due to the fact that all the distances between the cities are only calculated once and stored for later.

The brute-force algorithm uses lexicograhical order as main principle to sort through everything. It evaluates every possible order of cities of the current Travelling Salesman Problem, whilst always keeping track of the best one so far.
By nature, this algorithm is rather slow. For instance, 8 cities - as shown in the example below - already have 8! (eight factorial equals 40,320) possibilities to go through, in order to find the optimal distance. This takes the algorithm about 9 minutes on my computer.
However, when finished, the brute-force algorithm has certainly found the optimal result.

On the other hand, the genetic algorithm seems to be rather fast. It accomplishes the same task for 8 cities in under 50 seconds. However, it never really knows when it has the optimal result and runs forever, aspiring to find an ever better order, if you let it. I guess it would be nearly impossible, to predict the end result, without running a brute-force approach first, for which you would have to sacrifice speed and time.
The genetic algorithm works, from the get go, with a larger set of initial random orders that get crossed over, mutated and re-evaluated for fitness over generations.

I certainly have achieved what I wanted for now. If I want a quick, but probably not yet optimal evaluation, I run the genetic algorithm for half an hour or more for an increasing number of cities. However, if I need a very precise and optimal result, I patiently run the brute-force algorithm until the bitter end. :wink:

And last but not least, this is how it looks like in 3D:

As promised, here is the definition! Feel free to download it and inspect the code.

travelling_salesman_combined.gh (20.9 KB)

4 Likes

Using a genetic algorithm will not prove that what you found is the shortest distance. Proving with 100% certainty is NP complete, using a genetic algorithm may find the optimal solution for a low number of cities, but is not guaranteed to converge to the optimal solution for any configuration.

2 Likes
2 Likes

Thank you for your feedback, @menno. I guess you’re right. Personally speaking, the project is more about understanding how to create a genetic algorithm to find a useful result than finding the perfect solution to the traveling salesman problem.

I guess that I could re-evaluate the result at a given time/iteration with a brute-force algorithm in order to be more confident about the result.
At the moment, my script doesn’t converge at all, since it has no way of knowing, if its current iteration is the perfect one in the whole scheme of things.

Do you think that it won’t converge at all for a higher number of cities/points even given a long period of time to run?


Thanks, @ChrisK for the interesting article. Neural networks are beyond me tough. :smiley:

Thanks to everybody for visiting! The definition as well as some explanations can now be found above!