Simulated annealing
lastmod 2018-08-17created 2015-10-223 edits
Simulated annealing (Simulated Annealing, SA) is a generic probabilistic metaheuristic for global optimization problems. It provides a good approximation of the global optimum of a given function within a large search space. It was devised by Kirkpatrick, Gelatt, and Vecchi in 1983. In Korean, it is usually called by simply reading the English name as is: 시뮬레이티드 어닐링 (simyulleitideu eonilling).
About
Simulated annealing is sometimes used as a way to escape the problem of getting stuck in a local minimum. Annealing refers to the process of cooling steel that has been heated over a charcoal fire. Carbon atoms wedge themselves appropriately between the iron atoms, and these foreign carbon atoms prevent the iron atoms from slipping, producing hard steel.
Red-hot iron (Fe) atoms vibrate strongly and the gaps between atoms widen, which is why metal expands in volume when heated. As it loses energy from the hot state and cools, the atoms' chaotic vibration decreases and the volume of the lump of iron shrinks. However, if it loses a lot of energy and its temperature drops before the atoms find their proper places without gaps, it freezes with some gaps remaining; in this state, the gaps can no longer be filled even though a gap-free state with lower energy exists. This state is the state of being stuck in a local minimum. To escape this local minimum and reach the global minimum with no gaps at all, heat is applied again so that the iron atoms vibrate and can find the gaps, which makes a completely gap-free state possible.
Likewise, simulated annealing is a technique that randomly perturbs parameter values while training proceeds toward the minimum-energy state, so that it reaches the global energy minimum without getting stuck in a local minimum.