Information about Simulated Annealing
Simulated annealing (SA) is a generic probabilistic meta-algorithm for the global optimization problem, namely locating a good approximation to the global optimum of a given function in a large search space. It was independently presented by S. Kirkpatrick, C. D. Gelatt and M. P. Vecchi in 1983, and by V. Černı in 1985. The method is an adaptation of the Metropolis-Hastings algorithm, a Monte Carlo method to generate sample states of a thermodynamic system, invented by N. Metropolis et al in 1953.
The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.
By analogy with this physical process, each step of the SA algorithm replaces the current solution by a random "nearby" solution, chosen with a probability that depends on the difference between the corresponding function values and on a global parameter T (called the temperature), that is gradually decreased during the process. The dependency is such that the current solution changes almost randomly when T is large, but increasingly "downhill" as T goes to zero. The allowance for "uphill" moves saves the method from becoming stuck at local minima—which are the bane of greedier methods.
to a candidate new state 
is specified by an acceptance probability function 
, that depends on the energies 
and 
of the two states, and on a global time-varying parameter 
called the temperature.
One essential requirement for the probability function
is that it must be nonzero when 
, meaning that the system may move to the new state even when it is worse (has a higher energy) than the current one. It is this feature that prevents the method from becoming stuck in a local minimum—a state that is worse than the global minimum, yet better than any of its neighbors.
On the other hand, when goes to zero, the probability must tend to zero if , and to a positive value if 
. That way, for sufficiently small values of , the system will increasingly favor moves that go "downhill" (to lower energy values), and avoid those that go "uphill". In particular, when becomes 0, the procedure will reduce to the greedy algorithm—which makes the move only if it goes downhill.
In the original description of SA, the probability was defined as 1 when — i.e., the procedure always moved downhill when it found a way to do so, irrespective of the temperature. Many descriptions and implementations of SA still take this condition as part of the method's definition. However, this condition is not essential for the method to work, and one may argue that it is both counterproductive and contrary to its spirit.
The function is usually chosen so that the probability of accepting a move decreases when the difference
increases—that is, small uphill moves are more likely than large ones. However, this requirement is not strictly necessary, provided that the above requirements are met.
Given these properties, the evolution of the state depends crucially on the temperature . Roughly speaking, the evolution of is sensitive only to coarser energy variations when is large, and to finer variations when is small.
Another essential feature of the SA method is that the temperature is gradually reduced as the simulation proceeds. Initially, is set to a high value (or infinity), and it is decreased at each step according to some annealing schedule—which may be specified by the user, but must end with 
towards the end of the allotted time budget. In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low-energy regions that become narrower and narrower; and finally move downhill according to the steepest descent heuristic.
Sometimes a problem may arise when one approaches what is known as a local minimum, in this case, a set of numbers that is the best solution for its current region. In an attempt to find a better solution, this technique may use various methods to jump out of the current pit, such as searching for better solutions randomly by a factor of the inverse amount of the previous adjustment.
Keep in mind that implementations of this method are strictly problem specific, and so the way in which one finds a solution will vary from problem to problem.
. The annealing schedule is defined by the call temp(r), which should yield the temperature to use, given the fraction r of the time budget that has been expended so far.
Note that the step s := sn happens only on a small fraction of the moves. Therefore, this variation on the basic method is usually worth the cost, even if state-copying is an expensive operation.
cities has 
(2.5 quintillion) states; yet the neighbor generator function that swaps two consecutive cities can get from any state (tour) to any other state in 
steps.
of the the search graph, one defines a transition probability, which is the probability that the SA algorithm will move to state when its current state is . This probability obviously depends on the current temperature, and is determined by the order in which the candidate moves are generated by the neighbour() function, and by the acceptance probability function P(). (Note that the transition probability is not simply , because the candidates are tested serially).
The transition probabilities and the annealing schedule determine the the likelihood that the SA iteration will reach the global optimum within the alotted time. Therefore, the parameters neighbour(), P(), and temp must be tuned together to maximize the chance of this event.
In the original formulation of the method by Kirkpatrick et. al, the acceptance probability was defined as 1 if , and 
otherwise. This formula was said to come from the Metropolis-Hastings algorithm, where it was used to generate samples from the Maxwell-Boltzmann distribution governing the distribution of energies of molecules in a gas. However, there is no mathematical justification for using this particular formula in SA. Even the physical analogy is misleading: since the neighbours are tested sequentially in the SA algorithm, the actual probability of the SA algorithm moving from a state to a state definitely is not given by that formula. Nevertheless, this formula is quite popular, and is hard-coded in many implementations.
is likely to be similar to that of the current state. This heuristic (which is the main principle of the Metropolis-Hastings algorithm) tends to exclude "very good" candidate moves as well as "very bad" ones; however, the latter are much more common than the former, so the heuristic is generally quite effective.
In the traveling salesman problem above, for example, swapping two consecutive cities in a low-energy tour is expected to have a modest effect on its energy (length); whereas swapping two arbitrary cities is far more likely to increase its length than to decrease it. Thus, the consecutive-swap neighbor generator is expected to perform better than the arbitrary-swap one, even though the latter could provide a somewhat shorter path to the optimum (with
swaps, instead of 
).
A more precise statement of the heuristic is that one should try first candidate states for which 
is large. For the "standard" acceptance function above, it means that 
is on the order of or less. Thus, in the traveling salesman example above, one could use a neighbour() function that swaps two random cities, where the probability of choosing a city pair vanishes as their distance increases beyond .
As a rule, it is impossible to design a candidate generator that will satisfy this goal and also prioritize candidates with similar energy. On the other hand, one can often vastly improve the efficiency of SA by relatively simple changes to the generator. In the traveling salesman problem, for instance, it is not hard to exhibit two tours
, 
, with nearly equal lengths, such that (0) is optimal, (1) every sequence of city-pair swaps that converts to goes through tours that are much longer than both, and (2) can be transformed into by flipping (reversing the order of) a set of consecutive cities. In this example, and lie in different "deep basins" if the generator performs only random pair-swaps; but they will be in the same basin if the generator performs random segment-flips.
Therefore, in practice the ideal cooling rate cannot be determined beforehand, and should be empirically adjusted for each problem. The variant of SA known as thermodynamic simulated annealing tries to avoid this problem by dispensing with the cooling schedule, and instead automatically adjusting the temperature at each step based on the energy difference between the two states, according to the laws of thermodynamics.
, (where is temperature and 
is Boltzmann's constant) and depend only on the height 
of the barriers, it is very difficult for thermal fluctuations to get the system out from such local minima. But quantum tunneling probabilities through a barrier depend not only the height of the barrier, but also on its width 
; if the barriers are thin enough, quantum fluctuations may bring the system out of the shallow local minima surrounded by them.
Stochastic tunneling is a particular successful attempt to overcome the increasing difficulty simulated annealing runs have in escaping from local minima as the temperature decreases. Stochastic tunneling pushes the optimization run out of local minima, 'tunneling' through barriers.
Tabu search (TS) is similar to simulated annealing, in that both traverse the solution space by testing neighbours of the current solution. In order to prevent cycling, the TS algorithm maintains a "tabu list" of solutions already seen, and moves to those solutions are suppressed.
Stochastic hill climbing (SH) runs many hill-climbing searches from random initial locations.
Genetic algorithms (GA) maintain a pool of solutions rather than just one. New candidate solutions are generated not only by "mutation" (as in SA), but also by "combination" of two solutions from the pool. Probabilistic criteria, similar to those used in SA, are used to select the candidates for mutation or combination, and for discarding excess solutions from the pool.
Ant colony optimization (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas.
The cross-entropy method (CE) generates candidates solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.
Harmony search (HS) mimics musicians in improvisation process where each musician plays a note for finding a best harmony all together.
Stochastic optimization is an umbrella set of methods that includes simulated annealing and numerous other approaches.
..... Click the link for more information.
The name and inspiration come from annealing in metallurgy, a technique involving heating and controlled cooling of a material to increase the size of its crystals and reduce their defects. The heat causes the atoms to become unstuck from their initial positions (a local minimum of the internal energy) and wander randomly through states of higher energy; the slow cooling gives them more chances of finding configurations with lower internal energy than the initial one.
By analogy with this physical process, each step of the SA algorithm replaces the current solution by a random "nearby" solution, chosen with a probability that depends on the difference between the corresponding function values and on a global parameter T (called the temperature), that is gradually decreased during the process. The dependency is such that the current solution changes almost randomly when T is large, but increasingly "downhill" as T goes to zero. The allowance for "uphill" moves saves the method from becoming stuck at local minima—which are the bane of greedier methods.
Overview
In the simulated annealing (SA) method, each point s of the search space is compared to a state of some physical system, and the function E(s) to be minimized is interpreted as the internal energy of the system in that state. Therefore the goal is to bring the system, from an arbitrary initial state, to a state with the minimum possible energy.The basic iteration
At each step, the SA heuristic considers some neighbour s' of the current state s, and probabilistically decides between moving the system to state s' or staying put in state s. The probabilities are chosen so that the system ultimately tends to move to states of lower energy. Typically this step is repeated until the system reaches a state which is good enough for the application, or until a given computation budget has been exhausted.The neighbours of a state
The neighbours of each state (the candidate moves) are specified by the user, usually in an application-specific way. For example, in the traveling salesman problem, each state is typically defined as a particular tour (a permutation of the cities to be visited); and one could define the neighbours of a tour as those tours that can be obtained from it by exchanging any pair of consecutive cities.Acceptance probabilities
The probability of making the transition from the current state to a candidate new state is specified by an acceptance probability function , that depends on the energies and of the two states, and on a global time-varying parameter called the temperature.
One essential requirement for the probability function
is that it must be nonzero when , meaning that the system may move to the new state even when it is worse (has a higher energy) than the current one. It is this feature that prevents the method from becoming stuck in a local minimum—a state that is worse than the global minimum, yet better than any of its neighbors.
On the other hand, when
goes to zero, the probability must tend to zero if , and to a positive value if . That way, for sufficiently small values of , the system will increasingly favor moves that go "downhill" (to lower energy values), and avoid those that go "uphill". In particular, when becomes 0, the procedure will reduce to the greedy algorithm—which makes the move only if it goes downhill.
In the original description of SA, the probability
was defined as 1 when — i.e., the procedure always moved downhill when it found a way to do so, irrespective of the temperature. Many descriptions and implementations of SA still take this condition as part of the method's definition. However, this condition is not essential for the method to work, and one may argue that it is both counterproductive and contrary to its spirit.
The
function is usually chosen so that the probability of accepting a move decreases when the difference
increases—that is, small uphill moves are more likely than large ones. However, this requirement is not strictly necessary, provided that the above requirements are met.
Given these properties, the evolution of the state
depends crucially on the temperature . Roughly speaking, the evolution of is sensitive only to coarser energy variations when is large, and to finer variations when is small.
The annealing schedule
)
An image with random pixels, using simulated annealing to swap pairs of pixels. Similar colours attract at short range and repel at slightly less short range. Fast cooling schedule. Possibly resembles an amorphous solid.
)
An image with random pixels, using simulated annealing to swap pairs of pixels. Similar colours attract at short range and repel at slightly less short range. Slow cooling schedule. Possibly resembles a crystalline solid.
is set to a high value (or infinity), and it is decreased at each step according to some annealing schedule—which may be specified by the user, but must end with towards the end of the allotted time budget. In this way, the system is expected to wander initially towards a broad region of the search space containing good solutions, ignoring small features of the energy function; then drift towards low-energy regions that become narrower and narrower; and finally move downhill according to the steepest descent heuristic.
Convergence to the optimum
It can be shown that, for any given finite problem, the probability that the simulated annealing algorithm terminates with the global optimal solution approaches 1 as the annealing schedule is extended. This theoretical result is, however, not particularly helpful, since the annealing time required to ensure a significant probability of success will usually exceed the time required for a complete search of the solution space.In plain English
Given a problem for which no better solution is known than an extensive brute-force search, such as finding a set of 100 numbers that fit some characteristic, this technique attempts to quickly find an approximative solution by adjusting the current set (in this case some random sequence of 100 numbers) until a better answer is found (the way the adjustment is done depends on the problem). The new set of numbers, or "neighbour", if better, is then used as the current set and the process is repeated.Sometimes a problem may arise when one approaches what is known as a local minimum, in this case, a set of numbers that is the best solution for its current region. In an attempt to find a better solution, this technique may use various methods to jump out of the current pit, such as searching for better solutions randomly by a factor of the inverse amount of the previous adjustment.
Keep in mind that implementations of this method are strictly problem specific, and so the way in which one finds a solution will vary from problem to problem.
Pseudo-code
The following pseudo-code implements the simulated annealing heuristic, as described above, starting from state s0 and continuing to a maximum of kmax steps or until a state with energy emax or less is found. The call neighbour(s) should generate a randomly chosen neighbour of a given state s; the call random() should return a random value in the range. The annealing schedule is defined by the call temp(r), which should yield the temperature to use, given the fraction r of the time budget that has been expended so far.
s := s0; e := E(s) // Initial state, energy.
k := 0 // Energy evaluation count.
while k < kmax and e > emax // While time remains & not good enough:
sn := neighbour(s) // Pick some neighbour.
en := E(sn) // Compute its energy.
if P(e, en, temp(k/kmax)) > random() then // Should we move to it?
s := sn; e := en // Yes, change state.
k := k + 1 // One more evaluation done
return s // Return current solution
Saving the best solution seen
As in any metaheuristic, one should keep track of the best solution seen so far, in a separate state variable. Namely:
s := s0; e := E(s) // Initial state, energy.
sb := s; eb := e // Initial "best" solution
k := 0 // Energy evaluation count.
while k < kmax and e > emax // While time remains & not good enough:
sn := neighbour(s) // Pick some neighbor.
en := E(sn) // Compute its energy.
if en < eb then // Is this a new best?
sb := sn; eb := en // Yes, save it.
if P(e, en, temp(k/kmax)) > random() then // Should we move to it?
s := sn; e := en // Yes, change state.
k := k + 1 // One more evaluation done
return sb // Return the best solution found.
Note that the step s := sn happens only on a small fraction of the moves. Therefore, this variation on the basic method is usually worth the cost, even if state-copying is an expensive operation.
Selecting the parameters
In order to apply the SA method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function E(), the candidate generator procedure neighbour(), the acceptance probability function P(), and the annealing schedule temp(). These choices can have a significant impact on the method's effectiveness. Unfortunately, there are no choices of these parameters that will be good for all problems, and there is no general way to find the best choices for a given problem. Indeed, it has been observed that applying the SA method is more an art than a science. The following sections give some general guidelines.Diameter of the search graph
Simulated annealing may be modeled as a random walk on a search graph, whose vertices are all possible states, and whose edges are the candidate moves. An essential requirement for the neighbour() function is that it must provide a sufficiently short path on this graph from the initial state to any state which may be the global optimum. (In other words, the diameter of the search graph must be small.) In the traveling salesman example above, for instance, the search space for cities has (2.5 quintillion) states; yet the neighbor generator function that swaps two consecutive cities can get from any state (tour) to any other state in steps.
Transition probabilities
For each edge of the the search graph, one defines a transition probability, which is the probability that the SA algorithm will move to state when its current state is . This probability obviously depends on the current temperature, and is determined by the order in which the candidate moves are generated by the neighbour() function, and by the acceptance probability function P(). (Note that the transition probability is not simply , because the candidates are tested serially).
The transition probabilities and the annealing schedule determine the the likelihood that the SA iteration will reach the global optimum within the alotted time. Therefore, the parameters neighbour(), P(), and temp must be tuned together to maximize the chance of this event.
Acceptance probabilities
Actually, the parameters neighbour(), P(), and temp are partly redundant. In practice, one uses the same acceptance function P() for all problems, and adjust the other two functions according to the specific problem at hand.In the original formulation of the method by Kirkpatrick et. al, the acceptance probability
was defined as 1 if , and otherwise. This formula was said to come from the Metropolis-Hastings algorithm, where it was used to generate samples from the Maxwell-Boltzmann distribution governing the distribution of energies of molecules in a gas. However, there is no mathematical justification for using this particular formula in SA. Even the physical analogy is misleading: since the neighbours are tested sequentially in the SA algorithm, the actual probability of the SA algorithm moving from a state to a state definitely is not given by that formula. Nevertheless, this formula is quite popular, and is hard-coded in many implementations.
Efficient candidate generation
When chosing the candidate generator neighbour(), one must consider that after a few iterations of the SA algorithm, the current state is expected to have much lower energy than a random state. Therefore, as a general rule, one should skew the generator towards candidate moves where the energy of the destination state is likely to be similar to that of the current state. This heuristic (which is the main principle of the Metropolis-Hastings algorithm) tends to exclude "very good" candidate moves as well as "very bad" ones; however, the latter are much more common than the former, so the heuristic is generally quite effective.
In the traveling salesman problem above, for example, swapping two consecutive cities in a low-energy tour is expected to have a modest effect on its energy (length); whereas swapping two arbitrary cities is far more likely to increase its length than to decrease it. Thus, the consecutive-swap neighbor generator is expected to perform better than the arbitrary-swap one, even though the latter could provide a somewhat shorter path to the optimum (with
swaps, instead of ).
A more precise statement of the heuristic is that one should try first candidate states
for which is large. For the "standard" acceptance function above, it means that is on the order of or less. Thus, in the traveling salesman example above, one could use a neighbour() function that swaps two random cities, where the probability of choosing a city pair vanishes as their distance increases beyond .
Barrier avoidance
When choosing the candidate generator neighbour() one must also try to reduce the number of "deep" local minima — states (or sets of connected states) that have much lower energy than all its neighboring states. Such "closed catchement basins" of the energy function may trap the SA algorithm with high probability (roughly proportional to the number of states in the basin) and for a very long time (roughly exponential on the energy difference between the surrounding state and the bottom of the basin).As a rule, it is impossible to design a candidate generator that will satisfy this goal and also prioritize candidates with similar energy. On the other hand, one can often vastly improve the efficiency of SA by relatively simple changes to the generator. In the traveling salesman problem, for instance, it is not hard to exhibit two tours
, , with nearly equal lengths, such that (0) is optimal, (1) every sequence of city-pair swaps that converts to goes through tours that are much longer than both, and (2) can be transformed into by flipping (reversing the order of) a set of consecutive cities. In this example, and lie in different "deep basins" if the generator performs only random pair-swaps; but they will be in the same basin if the generator performs random segment-flips.
Cooling schedule
The physical analogy that is used to justify SA assumes that the cooling rate is low enough for the probability distribution of the current state to be near thermodynamic equilibrium at all times. Unfortunately, the relaxation time—the time one must wait for the equilibrium to be restored after a change in temperature—strongly depends on the "topography" of the energy function and on the current temperature. In the SA algorithm, the relaxation time also depends on the candidate generator, in a very complicated way. Note that all these parameters are usually provided as black box functions to the SA algorithm.Therefore, in practice the ideal cooling rate cannot be determined beforehand, and should be empirically adjusted for each problem. The variant of SA known as thermodynamic simulated annealing tries to avoid this problem by dispensing with the cooling schedule, and instead automatically adjusting the temperature at each step based on the energy difference between the two states, according to the laws of thermodynamics.
Restarts
Sometimes it is better to move back to a solution that was significantly better rather than always moving from the current state. This is called restarting. To do this we sets and e to sb and eb and perhaps restart the annealing schedule. The decision to restart could be based on a fixed number of steps, or based on the current energy being too high from the best energy so far.
Related methods
Quantum annealing is a method which uses quantum fluctuations instead of thermal fluctuations to explore the state space. It has been demonstrated experimentally as well as theoretically, that quantum annealing can indeed outperform thermal annealing in certain cases, specifically, where the potential energy (cost) landscape consists of very high but thin barriers surrounding shallow local minima. Since thermal transition probabilities are proportional to, (where is temperature and is Boltzmann's constant) and depend only on the height of the barriers, it is very difficult for thermal fluctuations to get the system out from such local minima. But quantum tunneling probabilities through a barrier depend not only the height of the barrier, but also on its width ; if the barriers are thin enough, quantum fluctuations may bring the system out of the shallow local minima surrounded by them.
Stochastic tunneling is a particular successful attempt to overcome the increasing difficulty simulated annealing runs have in escaping from local minima as the temperature decreases. Stochastic tunneling pushes the optimization run out of local minima, 'tunneling' through barriers.
Tabu search (TS) is similar to simulated annealing, in that both traverse the solution space by testing neighbours of the current solution. In order to prevent cycling, the TS algorithm maintains a "tabu list" of solutions already seen, and moves to those solutions are suppressed.
Stochastic hill climbing (SH) runs many hill-climbing searches from random initial locations.
Genetic algorithms (GA) maintain a pool of solutions rather than just one. New candidate solutions are generated not only by "mutation" (as in SA), but also by "combination" of two solutions from the pool. Probabilistic criteria, similar to those used in SA, are used to select the candidates for mutation or combination, and for discarding excess solutions from the pool.
Ant colony optimization (ACO) uses many ants (or agents) to traverse the solution space and find locally productive areas.
The cross-entropy method (CE) generates candidates solutions via a parameterized probability distribution. The parameters are updated via cross-entropy minimization, so as to generate better samples in the next iteration.
Harmony search (HS) mimics musicians in improvisation process where each musician plays a note for finding a best harmony all together.
Stochastic optimization is an umbrella set of methods that includes simulated annealing and numerous other approaches.
See also
- Adaptive simulated annealing
- Markov chain
- Combinatorial optimization
- Automatic label placement
- Multidisciplinary optimization
- Place and route
- Traveling salesman problem
- Reactive search
- Graph cuts in computer vision
References
- S. Kirkpatrick and C. D. Gelatt and M. P. Vecchi, Optimization by Simulated Annealing, Science, Vol 220, Number 4598, pages 671-680, 1983. http://citeseer.ist.psu.edu/kirkpatrick83optimization.html.
- V. Cerny, A thermodynamical approach to the travelling salesman problem: an efficient simulation algorithm. Journal of Optimization Theory and Applications, 45:41-51, 1985
- N. Metropolis, A.W. Rosenbluth, M.N. Rosenbluth, A.H. Teller, and E. Teller. "Equations of State Calculations by Fast Computing Machines". Journal of Chemical Physics, 21(6):1087-1092, 1953. http://dx.doi.org/10.1063/1.1699114
- A. Das and B. K. Chakrabarti (Eds.), Quantum Annealing and Related Optimization Methods, Lecture Note in Physics, Vol. 679, Springer, Heidelberg (2005)
- E. Weinberger, Correlated and Uncorrelated Fitness Landscapes and How to Tell the Difference, Biological Cybernetics, 63, No. 5, 325-336 (1990).
- J. De Vicente, J. Lanchares, R. Hermida, "Placement by Thermodynamic Simulated Annealing”, Physics Letters A,Vol. 317, Issue 5-6, pp.415-423, 2003.
External links
- Simulated Annealing A Java applet that allows you to experiment with simulated annealing. Source code included.
- "General Simulated Annealing Algorithm" An open-source MATLAB program for general simulated annealing exercices. Can be adapted as needed.
- VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include genetic algorithm, ACO, and simulated annealing solutions to TSP.
- Technique Developed for Optimizing Traveling-Wave Tubes A page showing the uses of this method in the space program for long distance communications.
- Adaptive Simulated Annealing (ASA) http://www.ingber.com/#ASA is a free C-language code developed to statistically find the best global fit of a nonlinear constrained non-convex cost-function over a D-dimensional space. This algorithm permits an annealing schedule for "temperature" T decreasing exponentially in annealing-time k,
and has more than 100 options to provide robust tuning over many classes of nonlinear stochastic systems.
- Go to the Wikiversity and teach yourself how to create a simulated annealing program.
A randomized algorithm or probabilistic algorithm is an algorithm which employs a degree of randomness as part of its logic. In common practice, this means that the machine implementing the algorithm has access to a pseudorandom number generator.
..... Click the link for more information.
..... Click the link for more information.
A meta-algorithm is an algorithm that can be usefully considered to have other significant algorithms, not just elementary operations and simple control structures, as its constituents; also an algorithm that has subordinate algorithms as variable and replaceable parameters.
..... Click the link for more information.
..... Click the link for more information.
Global optimization is a branch of applied mathematics and numerical analysis that deals with the optimization of a function or a set of functions to some criteria.
..... Click the link for more information.
General
The most common form is the minimization of one real-valued function in the parameter-space ...... Click the link for more information.
global optimum is a selection from a given domain which yields either the highest value or lowest value (depending on the objective), when a specific function is applied. For example, for the function
..... Click the link for more information.
- f(x) = −x2 + 2,
..... Click the link for more information.
function expresses dependence between two quantities, one of which is given (the independent variable, argument of the function, or its "input") and the other produced (the dependent variable, value of the function, or "output").
..... Click the link for more information.
..... Click the link for more information.
Search space may refer to one of the following.
..... Click the link for more information.
- In optimization, the domain of the function to be optimized
- In search algorithms of computer science, the set of all possible solutions
- In Computational geometry, part of the input data in geometric search problems
..... Click the link for more information.
Metropolis-Hastings algorithm is a rejection sampling algorithm used to generate a sequence of samples from a probability distribution that is difficult to sample from directly. This sequence can be used in Markov chain Monte Carlo simulation to approximate the distribution (i.e.
..... Click the link for more information.
..... Click the link for more information.
Monte Carlo methods are a widely used class of computational algorithms for simulating the behavior of various physical and mathematical systems, and for other computations.
..... Click the link for more information.
..... Click the link for more information.
Annealing, in metallurgy and materials science, is a heat treatment wherein a material is altered, causing changes in its properties such as strength and hardness. It is a process that produces conditions by heating and maintaining at a suitable temperature, and then cooling.
..... Click the link for more information.
..... Click the link for more information.
Metallurgy is a domain of materials science that studies the physical and chemical behavior of metallic elements, their intermetallic compounds, and their compounds, which are called alloys.
..... Click the link for more information.
..... Click the link for more information.
CRYSTAL is a quantum chemistry ab initio program, designed primarily for calculations on crystals (3 dimensions), slabs (2 dimensions) and polymers (1 dimension) using translational symmetry, but it can be used for single molecules.[1] It is written by V.R. Saunders, R.
..... Click the link for more information.
..... Click the link for more information.
crystal defects. The various types of defects are enumerated here.
..... Click the link for more information.
Point defects
Point defects are defects which are not extended in space in any dimension...... Click the link for more information.
atom (Greek ἄτομος or átomos meaning "indivisible") is the smallest particle still characterizing a chemical element.
..... Click the link for more information.
..... Click the link for more information.
In thermodynamics, the internal energy of a thermodynamic system, or a body with well-defined boundaries, denoted by U, or sometimes E, is the total of the kinetic energy due to the motion of molecules (translational, rotational, vibrational) and
..... Click the link for more information.
..... Click the link for more information.
maxima and minima, known collectively as extrema, are the largest value (maximum) or smallest value (minimum), that a function takes in a point either within a given neighbourhood (local extremum) or on the function domain in its entirety (global
..... Click the link for more information.
..... Click the link for more information.
greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimum choice at each stage with the hope of finding the global optimum.
..... Click the link for more information.
..... Click the link for more information.
In physics, the term state is used in several related senses, each of which expresses something about the way a physical system is.
..... Click the link for more information.
- State is sometimes used as a synonym for phase of matter.
..... Click the link for more information.
system has a technical meaning, namely, it is the portion of the physical universe chosen for analysis. Everything outside the system is known as the environment, which in analysis is ignored except for its effects on the system.
..... Click the link for more information.
..... Click the link for more information.
In thermodynamics, the internal energy of a thermodynamic system, or a body with well-defined boundaries, denoted by U, or sometimes E, is the total of the kinetic energy due to the motion of molecules (translational, rotational, vibrational) and
..... Click the link for more information.
..... Click the link for more information.
Probability is the likelihood that something is the case or will happen. Probability theory is used extensively in areas such as statistics, mathematics, science and philosophy to draw conclusions about the likelihood of potential events and the underlying mechanics of
..... Click the link for more information.
..... Click the link for more information.
travelling salesman problem (TSP) is a problem in discrete or combinatorial optimization. It is a prominent illustration of a class of problems in computational complexity theory which are classified as NP-hard.
..... Click the link for more information.
..... Click the link for more information.
For other senses of this word, see permutation (disambiguation).
Permutation is the rearrangement of objects or symbols into distinguishable sequences. Each unique ordering is called a permutation...... Click the link for more information.
In automata theory and sequential logic, a state transition table is a table showing what state (or states in the case of a nondeterministic finite automaton) a finite semiautomaton or finite state machine will move to, based on the current state and other inputs.
..... Click the link for more information.
..... Click the link for more information.
greedy algorithm is any algorithm that follows the problem solving metaheuristic of making the locally optimum choice at each stage with the hope of finding the global optimum.
..... Click the link for more information.
..... Click the link for more information.
Gradient descent is an optimization algorithm. To find a local minimum of a function using gradient descent, one takes steps proportional to the negative of the gradient (or the approximate gradient) of the function at the current point.
..... Click the link for more information.
..... Click the link for more information.
global optimum is a selection from a given domain which yields either the highest value or lowest value (depending on the objective), when a specific function is applied. For example, for the function
..... Click the link for more information.
- f(x) = −x2 + 2,
..... Click the link for more information.
In optimization (a branch of mathematics), a candidate solution is a member of a set of possible solutions to a given problem. A candidate solution does not have to be a likely or reasonable solution to the problem.
..... Click the link for more information.
..... Click the link for more information.
In computer science, brute-force search or exhaustive search is a trivial but very general problem-solving technique, that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.
..... Click the link for more information.
..... Click the link for more information.
graph theory is the study of graphs; mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges
..... Click the link for more information.
..... Click the link for more information.
In the mathematical field of graph theory, the distance between two vertices in a graph is the number of edges in a shortest path connecting them. This is also known as the geodesic distance.
..... Click the link for more information.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
