Simulated Annealing .*;
- View Java code
-
- Run Javascript example in a new window:
- with 8 cities
- with 14 cities
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