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)

8 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.

3 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!

hey, thanks for the interesting code… I reviewed it, and the genetic algorithm lacks convergence. It seems to find results more or less randomly. This is noticeable with more points. I recommend jump start it with the nearest neighbour and then running algo. Here is the result for N=100 and after 26k of generations

Yes, it’s never guaranteed to find a route or even the best route. And if I remember right, the gene mutations are indeed random. Your observations are on point.

Generally, the TSP is a hard one to tackle and - as far as I know - hasn’t been solved optimally yet. Approaching it with a genetic algorithm is just one way, but poses a couple of inconveniences, like the ones you and other folks have pointed out above.

Five years ago, I was just starting getting serious with programming and wasn’t really aware of much of the challenges and pitfalls involved here. I initially implemented the algorithm, inspired by Shiffman on YouTube, for an academical, architectural project, where only very small point sets where required to be evaluated and finding the most optimized route wasn’t the goal.
I haven’t really revisited the script since.

2 Likes

Avoid genetics at any cost: Slow to the point of been 100% useless for “realistic” N of nodes.

Target, say, 100ms for ~300 nodes. Here I use an ancient I5 (always use the slowest CPU when writing code for more than obvious reasons).

You’re only rehashing what’s been discussed here over and over already. Genetic algorithms, even if slow and unpractical, are still fun to explore and a valid approach for manifold problems.

2 Likes

Given some experience … when coding every battle is won before it’s ever fought (as the greatest strategist of all times clearly stated).

So fun and dead end are not exactly the same thing. Try for instance to deal with one of the hardest challenges around: the Hamiltionian path (or some Steiner graph). Without a robust backtracing approach is simply a waste of coding time.

Moral: using genetics for TSP is kinda attempting to tune a Harley Davidson.

Ah, the Chinese postman problem! I’ve already tackled that one for a creative coding project with recursive backtracking, intersecting and duplicate path avoidance. It’s a C++ implementation that is Rhino agnostic, but it works like a charm.

Btw, I don’t know anything about motorcycles.

Think some crap thing. Multiply by 100 > that’s a Harley Davidson (doesn’t handle/brake/steer etc etc).