Simulated Annealing Algorithm

Let's now look at how the metaphor of cooling a molten substance can be used to solve a problem. The simulated annealing algorithm is very simple and can be defined in five steps (see Figure 2.1).

Figure 2.1: Simulated annealing algorithm.

Initial Solution

For most problems, the initial solution will be a random one. This is loaded into what is called the current solution. Another alternative is to load the initial solution with an existing solution, possibly one found in a previous run. This gives the algorithm a base from which to search for a more optimal solution to the problem.

Assess Solution

Assessing the solution consists of decoding the current solution and then performing whatever action is necessary to evaluate it against the given problem. Note that the encoded solution may simply consist of a set of variables. These variables would be decoded from the current solution and the energy of the solution assessed based upon how well it solved the given problem.

Randomly Tweak Solution

Tweaking the solution begins by copying the current solution into what is called the working solution. We then randomly modify the working solution. How the working solution is modified depends upon the encoding. Consider an encoding of the Traveling Salesman Problem (TSP), where each element represents a unique city. To tweak this working solution, we pick two elements and swap them. This keeps the solution consistent by not allowing duplicates of cities or any cities from being removed from the solution.

Once the working solution has been tweaked, we assess the solution as defined in the previous step. This random trial is based upon the Metropolis algorithm (discussed later in detail).

Acceptance Criteria

At this point in the algorithm, we have two solutions. The first is our original solution called the current solution and the second is the tweaked version called the working solution. Each has an associated energy, which is the strength of the solution (let's say that the lower the energy, the better the solution).

Our working solution is then compared to the current solution. If the working solution has less energy than the current solution (i.e., is a better solution), then we copy the working solution to the current solution and move on to temperature reduction.

However, if the working solution is worse than the current solution, we evaluate the acceptance criteria to figure out what to do with the current working solution. The probability of acceptance is based on Equation 2.1 (which is based upon the law of thermodynamics ).

(2.1)  

What this means is more easily visualized in Figure 2.2. At high temperatures (> 60 degrees Celsius), worse solutions are accepted more often than they are rejected. If the delta energy is lower, the probability is even higher for acceptance. As the temperature decreases, so does the probability for accepting a worse solution. With decreasing temperature, higher delta energies contribute to lower acceptance probabilities.

Figure 2.2: Visualization of Acceptance Probability.

At higher temperatures, simulated annealing permits acceptance of worse solutions in order to search more of the available solution landscape. As the temperature decreases, the search allowable also decreases until equilibrium is reached when the temperature reaches 0 degrees C.

Reduce Temperature

After some number of iterations through the algorithm at this temperature, we reduce the temperature by a small amount. Large varieties of cooling schedules exist, but in this example we'll use a simple geometric function (see Equation 2.2):

(2.2)  

Constant a is less than one. Many other cooling strategies are possible, including linear and non-linear functions.

Repeat

A number of iterations will be performed at a single temperature. When that set of iterations is complete, the temperature is reduced and the process continues until the temperature reaches zero.