Simulated Annealing

· Annealing is a process of producing very strong glass or metal, which involves heating the material to a very high temperature and then allowing it to cool very slowly.

· In this way, the atoms are able to form the most stable structures, giving the material great strength.

· Simulated annealing is a local search metaheuristic based on this method and is an extension of a process called metropolisMonteCarlo simulation.

· Simulated annealing is applied to a multi-value combinatorial problem where values need to be chosen for many variables to produce a particular value for some global function, dependent on all the variables in the system.

· This value is thought of as the energy of the system, and in general the aim of simulated annealing is to find a minimum energy for a system.

· Simple Monte Carlo simulation is a method of learning information (such as shape) about the shape of a search space. The process involves randomly selecting points within the search space.

· An example of its use is as follows: A square is partially contained within a circle. Simple Monte Carlo simulation can be used to identify what proportion of the square is within the circle and what proportion is outside the circle. This is done by randomly sampling points within the square and checking which ones are within the circle and which are not.

· Metropolis Monte Carlo simulation extends this simple method as follows: Rather than selecting new states from the search space at random, a new state is chosen by making a small change to the current state.

· If the new state means that the system as a whole has a lower energy than it did in the previous state, then it is accepted.

· If the energy is higher than for the previous state, then a probability is applied to determine whether the new state is accepted or not. This probability is called a

            Boltzmann acceptance criterion and is calculated as follows: e(_dE/T) where T is the current temperature of the system, and dE is the increase in energy that has been

            produced by moving from the previous state to the new state.

· The temperature in this context refers to the percentage of steps that can be taken that lead to a rise in energy: At a higher temperature, more steps will be accepted that lead to a rise in energy than at low temperature.

· To determine whether to move to a higher energy state or not, the probability e(_dE/T) is calculated, and a random number is generated between 0 and 1. If this

random number is lower than the probability function, the new state is accepted. In cases where the increase in energy is very high, or the temperature is very low, this means that very few states will be accepted that involve an increase in energy, as e(_dE/T) approaches zero.

· The fact that some steps are allowed that increase the energy of the system enables the process to escape from local minima, which means that simulated annealing often can be an extremely powerful method for solving complex problems with many local maxima.

· Some systems use e(_dE/kT) as the probability that the search will progress to a state with a higher energy, where k is Boltzmann’s constant (Boltzmann’s constant is

approximately 1.3807 _ 10_23 Joules per Kelvin).

· Simulated annealing usesMonte Carlo simulation to identify the most stable state (the state with the lowest energy) for a system.

· This is done by running successive iterations of metropolis Monte Carlo simulation, using progressively lower temperatures. Hence, in successive iterations, fewer and fewer steps are allowed that lead to an overall increase in energy for the system.

· A cooling schedule (or annealing schedule) is applied, which determines the manner in which the temperature will be lowered for successive iterations.

· Two popular cooling schedules are as follows:

                                      Tnew = Told _ dT

                                     Tnew = C _ Told (where C < 1.0)

· The cooling schedule is extremely important, as is the choice of the number of steps of metropolis Monte Carlo simulation that are applied in each iteration.

· These help to determine whether the system will be trapped by local minima (known as quenching). The number of times the metropolis Monte Carlo simulation is applied per iteration is for later iterations.

· Also important in determining the success of simulated annealing are the choice of the initial temperature of the system and the amount by which the temperature is

decreased for each iteration.

· These values need to be chosen carefully according to the nature of the problem being solved. When the temperature, T, has reached zero, the system is frozen, and if the simulated annealing process has been successful, it will have identified a minimum for the total energy of the system.

· Simulated annealing has a number of practical applications in solving problems with large numbers of interdependent variables, such as circuit design.

· It has also been successfully applied to the traveling salesman problem.

Uses of Simulated Annealing

· Simulated annealing was invented in 1983 by Kirkpatrick, Gelatt, and Vecchi.

· It was first used for placing VLSI* components on a circuit board.

· Simulated annealing has also been used to solve the traveling salesman problem, although this approach has proved to be less efficient than using heuristic methods that know more about the problem.

· It has been used much more successfully in scheduling problems and other large combinatorial problems where values need to be assigned to a large number of variables to maximize (or minimize) some function of those variables.

Real-Time A*

· Real-time A* is a variation of A*.

· Search continues on the basis of choosing paths that have minimum values of f(node) = g(node) + h(node). However, g(node) is the distance of the node from the current node, rather than from the root node.

· Hence, the algorithm will backtrack if the cost of doing so plus the estimated cost ofsolving the problem from the new node is less than the estimated cost of solving the problem from the current node.

· Implementing real-time A* means maintaining a hash table of previously visited states with their h(node) values.

Iterative-Deepening A* (IDA*)

· By combining iterative-deepening with A*, we produce an algorithm that is optimal and complete (like A*) and that has the low memory requirements of depth-first

search.

· IDA* is a form of iterative-deepening search where successive iterations impose a greater limit on f(node) rather than on the depth of a node.

· IDA* performs well in problems where the heuristic value f (node) has relatively few  possible values.

· For example, using the Manhattan distance as a heuristic in solving the eight-queens problem, the value of f (node) can only have values 1, 2, 3, or 4.

· In this case, the IDA* algorithm only needs to run through a maximum of four iterations, and it has a time complexity not dissimilar from that of A*, but with a

significantly improved space complexity because it is effectively running depth-first search.

· In cases such as the traveling salesman problem where the value of f (node) is different for every state, the IDA* method has to expand 1 + 2 + 3 + . . . + n nodes =

O(n2) where A* would expand n nodes.