Annealing Simulation Algorithm

The simulated annealing algorithm is a general algorithmic method for solving the global optimization problem, especially discrete and combinatorial optimization . One example of Monte Carlo methods .

Content

General Description

Search for a global maximum by simulating annealing. Standard gradient methods ( descent methods ) are not applicable in this case, since there are many local maxima . Over time, the temperature decreases.

The algorithm is based on a simulation of a physical process that occurs during crystallization of a substance , including during annealing of metals . It is assumed that the atoms are already lined up in a crystal lattice , but transitions of individual atoms from one cell to another are still permissible. It is assumed that the process proceeds at a gradually decreasing temperature . The transition of an atom from one cell to another occurs with some probability , and the probability decreases with decreasing temperature. A stable crystal lattice corresponds to the minimum energy of atoms, so the atom either goes into a state with a lower level of energy, or remains in place. (This algorithm is also called the N. Metropolis algorithm, named after its author).

By modeling such a process, a point or a set of points is sought at which a minimum of some numerical function is reached $F({\overline {x}})$ ${\ displaystyle F ({\ overline {x}})}$ where ${\overline {x}}=(x_{1},\;\ldots ,\;x_{m})\in X$ ${\ displaystyle {\ overline {x}} = (x_ {1}, \; \ ldots, \; x_ {m}) \ in X}$ . The solution is sought by sequential point computation. ${\overline {x_{0}}},\;{\overline {x_{1}}},\;\ldots ,\;$ ${\ displaystyle {\ overline {x_ {0}}}, \; {\ overline {x_ {1}}}, \; \ ldots, \;}$ of space $X$ ${\ displaystyle X}$ ; every point starting ${\overline {x_{1}}}$ ${\ displaystyle {\ overline {x_ {1}}}}$ , "Claims" to better approximate the solution than the previous ones. Algorithm takes a point ${\overline {x_{0}}}$ ${\ displaystyle {\ overline {x_ {0}}}}$ as source data. At each step, the algorithm (which is described below) calculates a new point and lowers the value of the value (initially positive), understood as “temperature”. The algorithm stops when it reaches a point that turns out to be zero at a temperature.

Point ${\overline {x_{i+1}}}$ ${\ displaystyle {\ overline {x_ {i + 1}}}}$ according to the algorithm is obtained based on the current point ${\overline {x_{i}}}$ ${\ displaystyle {\ overline {x_ {i}}}}$ in the following way. To the point ${\overline {x_{i}}}$ ${\ displaystyle {\ overline {x_ {i}}}}$ operator applies $\mathrm {A}$ ${\ displaystyle \ mathrm {A}}$ , which randomly modifies the corresponding point, resulting in a new point ${\overline {x^{*}}}$ ${\ displaystyle {\ overline {x ^ {*}}}}$ . Point ${\overline {x^{*}}}$ ${\ displaystyle {\ overline {x ^ {*}}}}$ becomes a point ${\overline {x_{i+1}}}$ ${\ displaystyle {\ overline {x_ {i + 1}}}}$ with probability $P({\overline {x^{*}}},\;{\overline {x_{i+1}}})$ ${\ displaystyle P ({\ overline {x ^ {*}}}, \; {\ overline {x_ {i + 1}}})}$ , which is calculated in accordance with the Gibbs distribution :

P({\overline {x^{*}}}\to {\overline {x_{i+1}}}\mid {\overline {x_{i}}})={\begin{cases}1,&F({\overline {x^{*}}})-F({\overline {x_{i}}})<0\\\exp \left(-{\dfrac {F({\overline {x^{*}}})-F({\overline {x_{i}}})}{Q_{i}}}\right),&{F({\overline {x^{*}}})-F({\overline {x_{i}}})\geqslant 0}\end{cases}}

{\ displaystyle P ({\ overline {x ^ {*}}} \ to {\ overline {x_ {i + 1}}} \ mid {\ overline {x_ {i}}} = {\ begin {cases} 1, & F ({\ overline {x ^ {*}}}) - F ({\ overline {x_ {i}}}) <0 \\\ exp \ left (- {\ dfrac {F ({\ overline { x ^ {*}}}) - F ({\ overline {x_ {i}}})} {Q_ {i}}} \ right), & {F ({\ overline {x ^ {*}}}) -F ({\ overline {x_ {i}}}) \ geqslant 0} \ end {cases}}}

Here $Q_{i}>0$ ${\ displaystyle Q_ {i}> 0}$ - elements of an arbitrary decreasing, converging to zero positive sequence, which sets the analogue of the falling temperature in the crystal. The rate of decrease and the law of decrease can be set at the request of the creator of the algorithm.

The simulated annealing algorithm is similar to gradient descent , but due to the randomness of the choice of an intermediate point, it should fall into local minima less often than gradient descent. The annealing simulation algorithm does not guarantee that the minimum of the function is found, however, with the correct policy for generating a random point in space $X$ ${\ displaystyle X}$ As a rule, the initial approximation improves.

Application

Neural network training
The solution of combinatorial problems, for example, the problem of placing queens
The solution of the traveling salesman problem ^[1]

Notes

↑ The Hamiltonian cycle problem

Literature

Callan Robert. The basic concepts of neural networks. - M .: Williams Publishing House, 2003 .-- 288 p. - ISBN 5-8459-0219-X . - S. 146-148.
Kirsanov M.N. Counts in Maple . - M .: Fizmatlit, 2007 .-- 168 p. - ISBN 978-5-9221-0745-7 . - S. 151-154.
Jones M.T. Programming Artificial Intelligence in Applications. - M .: DMK Press, 2004 .-- 312 p. - ISBN 5-94074-275-0 . - S. 25–42.

Links

[1] The Hamiltonian cycle problem