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