Subscribe to DSC Newsletter

Simulated Annealing: How to boost performance through Matrix Cost rescaling

One of the most widely algorithm used in Machine Learning is the Simulated Annealing (SA).
The reason of its celebrity lays in:

  • Simplicity of implementation
  • broad spectrum of applicability

 ... click here to read the entire post

The experiments
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.

 ... click here to read the entire post

Results
All experiments as usual as been done through "home made" application written in Mathematica.

SA launched with beta= 15. After 5000 cycles the sub optimal solution found has cost = 14

h matrix cost rescaled after 2000 cycles found better solution (same initialization of the above experiment)

 ... click here to read the entire post

A larger test has been done to understand the statistical behavior:

The blue line represents the solution costs of the traditional SA.
The red line represents the solution costs of the SA with matrix cost rescaled 

And to conclude, here you are the results obtained with higher complexity (50 towns).

ATSP (50 towns) comparison between traditional SA and SA with rescaled matrix cost


The assumption seems to be confirmed: the new strategy performs better than the traditional SA even if the number of cycles is higher. 

Conclusion
  1. Often the accuracy/performance of an algorithms depends on the way you feed it with the data! Rescaling your data is quite always essential!
  2. The strategy requires further tests and validation.
...We will discuss about the function used to rescale the matrix costs and some other application of SA on different problems in the next posts.
cheers & stay tuned

 

 
 
 

Views: 727

Comment

You need to be a member of AnalyticBridge to add comments!

Join AnalyticBridge

On Data Science Central

© 2020   TechTarget, Inc.   Powered by

Badges  |  Report an Issue  |  Privacy Policy  |  Terms of Service