A project for my artificial intelligence module in my final year at university. The task was to pick any technique to derive optimal solutions to a dataset representing a Travelling Salesman Problem.

‍

The following is an excerpt from my report

‍

Simulated annealing, unlike other algorithms, can sometimes accept a worse path in an iteration depending on some factors, this is done to ensure a larger coverage of the search space, and can prevent the algorithm from getting stuck in a local minimum.

‍

The following is the iterative loop which is used in simulated annealing to find the optimal path:-

‍

1. Randomize the initial path
2. Swap two cities in the path
3. Calculate the cost difference
4. If the cost difference is negative (more optimal path), accept the path
5. If the cost difference is positive (less optimal path), decide on whether to keep the path based on a randomized comparison.

‍

Below is the statement to calculate a random probability, and it’s comparison to a random number between 0 and 1.

‍

cost difference ^{-cost difference / temperature} > random(0, 1)

‍

6. If the cost difference is neither negative nor is chosen to be kept based on probability, the path is reverted to its previous state.

‍

The stop condition for the loop is based on the “temperature”; a variable that decreases to 99% of its previous value upon each iteration.

Through testing, I have derived the optimal starting temperature to be 1000, and the stopping temperature to be 0.001.

‍

A final note on simulated annealing, as the algorithm uses a randomized initial path, it is not guaranteed to deliver the same result on each run. A remedy to this problem is fine tuning the parameters such as the temperature and the probability, but those can affect the total run time of the program.

‍

Training sets results

‍

‍

‍

‍

References

‍

1. Walker, J. (2018) Simulated annealing, Simulated Annealing: The Travelling Salesman Problem. Available at: https://www.fourmilab.ch/documents/travelling/anneal/ (Accessed: November 12, 2022).
2. ‍Simulated annealing (2022) Rosetta Code. Rosetta Code. Available at: https://rosettacode.org/wiki/Simulated_annealing#J (Accessed: November 12, 2022).