Simulated Annealing .*;

Traveling Salesman Problem Example 1

This is a rendition of the classic Traveling Salesman Problem, where the shortest tour needs to be found among all cites without visiting the same one twice.  The algorithm works out the minimum Cartesian distance through eight cities named 0, 1, 2, 3, 4, 5, 6 and 7.  There are 88 (or, 16,777,216) possible combinations, and with simulated annealing we'll only need to explore 82 or 83.

 

Example Results 1

Eight cities. One iteration at temperature.

Current Solution Energy: 125.27019020397186
Working Solution Energy: 125.27019020397186
Best Solution Energy: 105.73803621780543
Temperature: 32.27649936777375
Distance: 153.71932977871714
Current Solution Energy: 125.27019020397186
Working Solution Energy: 125.27019020397186
Best Solution Energy: 105.73803621780543
Temperature: 31.953734374096015
Distance: 109.57192798240996
Current Solution Energy: 109.57192798240996
Working Solution Energy: 109.57192798240996
Best Solution Energy: 105.73803621780543
Temperature: 31.634197030355054
Distance: 131.396525705262


...abbreviated listing...

Current Solution Energy: 86.62998956150375
Working Solution Energy: 86.62998956150375
Best Solution Energy: 86.62998956150375
Temperature: 0.5187419922806178
Distance: 121.1755653761822
Current Solution Energy: 86.62998956150375
Working Solution Energy: 86.62998956150375
Best Solution Energy: 86.62998956150375
Temperature: 0.5135545723578117
Distance: 99.99543531546844
Current Solution Energy: 86.62998956150375
Working Solution Energy: 86.62998956150375
Best Solution Energy: 86.62998956150375
Temperature: 0.5084190266342336
Distance: 109.57192798240996
Current Solution Energy: 86.62998956150375
Working Solution Energy: 86.62998956150375
Best Solution Energy: 86.62998956150375
Temperature: 0.5033348363678912
Distance: 111.28160986963346
Current Solution Energy: 86.62998956150375
Working Solution Energy: 86.62998956150375
Best Solution Energy: 86.62998956150375
Temperature: 0.4983014880042123
1, 0, 7, 6, 5, 4, 3, 2, 
Best solution is: Correct

 

Example Results 2

14 cities. One iteration at temperature.

...abbreviated listing...

Current Solution Energy: 123.38697574321749
Working Solution Energy: 123.38697574321749
Best Solution Energy: 123.38697574321749
Temperature: 0.5187419922806178
Distance: 201.93784791207023
Current Solution Energy: 123.38697574321749
Working Solution Energy: 123.38697574321749
Best Solution Energy: 123.38697574321749
Temperature: 0.5135545723578117
Distance: 142.46693864917904
Current Solution Energy: 123.38697574321749
Working Solution Energy: 123.38697574321749
Best Solution Energy: 123.38697574321749
Temperature: 0.5084190266342336
Distance: 169.31880124505432
Current Solution Energy: 123.38697574321749
Working Solution Energy: 123.38697574321749
Best Solution Energy: 123.38697574321749
Temperature: 0.5033348363678912
Distance: 172.95690066037935
Current Solution Energy: 123.38697574321749
Working Solution Energy: 123.38697574321749
Best Solution Energy: 123.38697574321749
Temperature: 0.4983014880042123
0, 13, 12, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 1, 
Best solution is: Not Correct


The number of iterations at temperature does matter. The larger the search space, the more local minima there are to get stuck in. Increasing the number of iterations at temperature can fix this.

 

Example Results 3

14 cities. Four iterations at temperature.

...abbreviated listing...

Current Solution Energy: 85.96891662694654
Working Solution Energy: 85.96891662694654
Best Solution Energy: 85.96891662694654
Distance: 104.90112991881264
Current Solution Energy: 85.96891662694654
Working Solution Energy: 85.96891662694654
Best Solution Energy: 85.96891662694654
Temperature: 0.5033348363678912
Distance: 147.7184636678694
Current Solution Energy: 85.96891662694654
Working Solution Energy: 85.96891662694654
Best Solution Energy: 85.96891662694654
Distance: 164.25003986424775
Current Solution Energy: 85.96891662694654
Working Solution Energy: 85.96891662694654
Best Solution Energy: 85.96891662694654
Distance: 95.80927483277746
Current Solution Energy: 85.96891662694654
Working Solution Energy: 85.96891662694654
Best Solution Energy: 85.96891662694654
Distance: 128.60277531271979
Current Solution Energy: 85.96891662694654
Working Solution Energy: 85.96891662694654
Best Solution Energy: 85.96891662694654
Temperature: 0.4983014880042123
2, 1, 0, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 
Best solution is: Correct

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}