Solution Process

Simulated annealing, as a heuristic process, seeks to optimize a cost function consisting of perhaps a large set of variables, and is analogous to physical systems that are in thermal equilibrium at many different temperatures. Determining the low-temperature state of a system under a number of different scenarios is the basis for the search process. Annealing is simply the heating of a material above its melting point, then cooling it in such a way that all of the particles are arranged, or rearranged, into a lattice. In doing so, the particles seek minimum energy configurations. The annealing process is ideally done in such a way (i.e., slowly) that defects are minimized; cooling a material too quickly could lead to numerous defects, or less than optimal conditions.

The probability of occurrence of each state of the system at thermal equilibrium, bounded between 0 and 1, is known as the Boltzmann-Gibbs distribution, or

where kB is the Boltzmann constant, T is the temperature of the annealing process, x is a given state of the system, Tr is the sum over all possible configurations of the particles in the system, and E(x) is an energy function (see Boltzman Learning). Transitions from state to state can be estimated by assuming that, on average, the probability of moving from x1 to x2 is the same as moving from X2 to xi. The Metropolis algorithm then defines the transition probability as

P(xi ! x2) = e-ae'kbt when the transition is from a lower state to a higher state. If the transition is from a lower state to an even lower state (i.e., for the better), the probability of the transition is 1. The probability of the change in energy from one state (x1) to an even less desirable state (x2) is the condition used in combinatorial optimization to add randomness to the search process; that is, not every change in solution quality is for the better, some changes are for the worse, but are occasionally desirable to allow the search process to move into, and out of, local optima.

As with most heuristic search processes, simulated annealing begins with one solution (usually suboptimal), and iteratively adjusts the solution until the rules that guide the search indicate no further adjustments are possible. The best solution that was located during the adjustment process is then reported. Rules of thumb, or sets of logic, are used to make the adjustments to each subsequent solution. Simulated annealing uses logic similar to Monte Carlo simulation, in that random adjustments in the neighborhood of an existing solution are selected and considered. However, simulated annealing will not allow every randomly selected adjustment to be incorporated into a solution that is being developed; rather, it relies on a test to determine whether to accept or decline certain adjustments (those that lead to a less desirable state).

As we have indicated, where iterative solutions generated do not improve on the previous solutions, the change that is made is decided probabilistically. A random number drawn from a uniform distribution in the interval (0,1) is compared to the result of the equation for P(AE):

where AE is the difference between the current and previous solution values. If the random number is less than P(AE), the change made to the solution is accepted, even though the quality of the solution declined.

A simulated annealing search process can begin with an undefined starting solution (often this is a null set of solution values), or more commonly with a randomly defined feasible solution to a problem (Figure 1). An initial annealing temperature (usually the system of measurement (Celsius or Fahrenheit) is not defined) is determined, as are the number of iterations (adjustments) that the search process will model at each temperature, and the cooling rate of the temperature. These three parameters are typically user-defined, and require some trial runs of the heuristic to arrive at the acceptable values. Typically, better objective function values are obtained by using a slow-cooling schedule. Alternatively, the parameters can be determined as a function (or percentage in the case ofthe initial temperature) of the initial solution, but this is the exception to the general rule.

Figure 1 A typical simulated annealing search process.


Report best


Figure 1 A typical simulated annealing search process.

As each adjustment to the solution is assessed in the simulated annealing process, a decision is made as to whether to change the temperature. The simulated annealing search process stops when the temperature cools below a certain level, and the best solution to the problem that was located during the search is then reported.

Was this article helpful?

0 0
Project Earth Conservation

Project Earth Conservation

Get All The Support And Guidance You Need To Be A Success At Helping Save The Earth. This Book Is One Of The Most Valuable Resources In The World When It Comes To How To Recycle to Create a Better Future for Our Children.

Get My Free Ebook

Post a comment