Saturday, November 25, 2017

Udacity Lab: Simulated Annealing Lab Results

Introduction

I'm currently doing a course at Udacity and I'm using this post to share some results with my peers. We were asked to analyse how changing certain properties of the Simulated Annealing Algorithm would change the solutions of the Traveling Salesman Problem. I produced some histograms which I found interesting enough to share. My apologies if I don't explain anything further.

Changing the Number of Cities

Nobs 100, Min 1426, Max 2450, Mean 1836, Var 63180, Skewness 0.622


Nobs 100, Min 4487, Max 7316, Mean 5840, Var 277449, Skewness 0.0098

By increasing the number of cities in the second graph we increase the complexity of the problem and we see that the algorithm most of the time only finds a sub optimal solution. The optimal solution is at the Min-Value to the left and only with 10 cities we see a graph that is skewed to the right. 

Changing Temperatur

Nobs 100, Min 1426, Max 2501, Mean 1895, Var 86949, Skewness 0.439

Nobs 100, Min 1426, Max 2439, Mean 1853, Var 76739, Skewness 0.391

Nobs 100, Min 1426, Max 2427, Mean 1859, Var 74511, Skewness 0.363

Nobs 100, Min 1426, Max 2436, Mean 1849, Var 73730, Skewness 0.271

Nobs 100, Min 1426, Max 2564, Mean 2040, Var 92452, Skewness -0.450

We see that choosing a very high temperature has not a huge effect. The first two histograms look the same even though the temperature on the first one was significantly higher. But we see in the last two histograms that choosing a too low temperature is not good as we start to skew to the left.

Changing Alpha

Nobs 100, Min 1426, Max 2368, Mean 1693, Var 37448, Skewness 0.587

Nobs 100, Min 1434, Max 2465, Mean 1870, Var 63441, Skewness 0.335

Nobs 100, Min 1426, Max 2548, Mean 2007, Var 82375, Skewness -0.379


Nobs 100, Min 1426, Max 2608, Mean 2065, Var 75604, Skewness -0.545

Nobs 100, Min 1676, Max 2729, Mean 2198, Var 60915, Skewness -0.283

We clearly see that choosing a high alpha value is best as the graph skews to the right while the variance is still the smallest. A high alpha significantly increase the run time therefore alpha and run time have to be carefully balanced.