In optimization simulated annealing is a method of approximating global minima of a given problem. The method is applied below to the traveling salesman problem. The traveling salesman problem is an example of a problem in computer science that is NP-complete, which means the problem is both \( \in \) NP and NP-hard. It also means that there is no known algorithm to solve the problem that has a complexity that is \( \in O(n^p) \). Where \( n \) is the size of the input and \( p \) is any positive real number. In other words no solution has been found that runs within polynomial time using a model of computation that is equivalent to a deterministic Turing machine. The problem is: given a list of \(n\) cities, what is the shortest path that visits each exactly once and returns to the original starting city? The simplest approach of trying every possible configuration of cities has a complexity \( \in O(n!) \). So for example if you have a list of \(25\) cities there are \(25!\) or \( 1.55 \times 10^{25}\) possible configurations. Assuming you do a billion calculations a second you would need approximately \( 1.55 \times 10^{16}\) seconds or \(491.5 \times 10^{6}\) years to do the calculation. However using simulated annealing you can get an approximate optimal solution in much less time. The algorithm utilizes randomness to find global minima of cost functions that are trying to be minimized (or maximized). The algorithm essentially configures the list of cities in some way, in this example by flipping the order of a random sub-array of cities, and checks to see if the new configuration is better or worse than the old one. If it's better than the configuration is accepted but if it's worse the configuration is accepted according to some probability function, in this example the function is \[ e^{\frac{-\Delta E}{T} } .\] The reason for this is so that the algorithm can avoid being trapped in a local minima when finding the optimal solution as shown:
