A Data Science Central Community
One of the most widely algorithm used in Machine Learning is the Simulated Annealing (SA).
The reason of its celebrity lays in:
I considered two instances of the problem, the first one with 10 towns and the second one with 50 towns.
Even if for this kind of problem there are more efficient algorithms to face TSP, I chose the simulated annealing just to show how versatile it is and to show how much therescaling operation is essential in order to maximize the performance of your algorithm.
Why rescaling? (I'll try to be technical as little as possible)
The SA bases its powerful on the ability to overcome the local minimum through the acceptance at time "t" of a bad solution respect a better solution found at the time "t-1". It assigns an acceptance probability based on the sigmoidal function that decrease if the cost of the new solution is higher respect the current solution.
h matrix cost rescaled after 2000 cycles found better solution (same initialization of the above experiment)
A larger test has been done to understand the statistical behavior:
The blue line represents the solution costs of the traditional SA.
And to conclude, here you are the results obtained with higher complexity (50 towns).