HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Introduction
Simulated annealing is a technique of finding a global maximization/extremization for large scale problems where there are many local extremas defined. The classic example of a problem that is practically "solved" by simulated annealing is the NP-Complete Traveling Salesman problem. The other example is the design of Integrated Circuits which essentially involves selection of an arrangement of hundreds of thousands of circuit elements in such an arrangement that minimizes overall interference among the connected wires.
The above two examples are cases of combinatorial minimizations with the objective function on N variables. However the N variables are not continuous variables, but discrete. Hence the set of values of these N variables is considered as a "System Configuration" and has an value of the Objective Function. The number of such possible configurations is prohibitively large for evaluation of each configuration for finding the extrema. Simulated annealing technique proposes a strategy for finding such an extrema without the need for evaluation of each configuration.
Background
Annealing is the process of slow cooling that allows time for molecules to orient themselves in such a way that the overall stored energy is minimum. This is the process of formation of crystals.
In nature the Annealing in thermodynamic systems follow the classic Bolzmann Probability Distribution.
p = e^{( -(E2-E1)/kt) )} where k is the Bolzmann Constant, T is the temperature and the system is currently at the Energy level E1. The probability of system changing from energy state E1 to E2 is given by the formula. If E2 < E1, the probability is considered 1.
The classic simulation of Annealing process for non thermodynamic systems is done using the MetroPolis Algorithm? at the heart of which is the assertion that for any system with configurations En and a "reward function" indicating the reward upon moving from E1 to E2 will "sometimes" move from one configuration to another even when the reward is negative.
Formulation
Followings steps need to be undertaken to formulate a non thermodynamic system in order to apply the Metropolis algorithm over it.
- Describe the System Configuration, i.e. identify all the parameters and the set of values these can take up. Each valid set identifies a System Configuration.
- A generator of random changes in the configurations i.e. the function that makes the system undergo configuration changes.
- Objective function E (analogous to Energy E) the minimization of which is the goal of the procedure.
- Control parameter T (analogous to Temperature T) and an annealing schedule e.g. after how many configuration changes a step is taken, how large is that step.
Comments
