Simulated annealing
담금질 기법(Simulated Annealing, SA)은 전역 최적화 문제에 대한 일반적인 확률적 메타 알고리즘이다. 이 기법은 광대한 탐색 공간 안에서, 주어진 함수의 전역 최적해에 대한 좋은 근사를 준다. 커크패트릭, 젤라트, 베키가 1983년에 고안했다. 보통 영어를 그냥 읽어서 시뮬레이티드 어닐링이라고 부른다.
About
지역최소값에 빠지는 문제점을 빠져나가기 위한 방법의 일종으로 시뮬레이티드 어닐링 방법을 사용하기도 한다. 담금질은 숯불에 뜨겁게 달군 강철을 식히는 과정을 뜻한다. 철원자들 사이에 탄소 원자가 적절히 끼어들어서 철원자의 미끄러짐을 이종 원자인 탄소 원자가 방지하여 단단한 강철을 만드는 것이다.
뜨겁게 벌겋게 달구어진 철(Fe) 원자는 강하게 진동하며 원자들간의 틈새는 넓어지게 되며 이러한 이유로 금속을 뜨겁게 가열하면 부피가 늘어 난다. 뜨거운 상태에서 에너지를 잃고서 식어가면 원자들의 난잡한 진동도 줄어들게 되어 쇠뭉치의 부피도 줄어든다. 그러나, 빈틈없이 제자지를 찾아가기 전에 에너지를 많이 잃고서 온도가 떨어지면 약간의 빈틈도 있는 상태로 얼어버리는데 이러한 상태는 더 낮은 에너지를 가진 빈 틈없는 상태가 있음에도 불구하고 더 이상 빈 틈을 메울 수는 없다. 이러한 상태가 지역 최소값에 빠진 상태이다. 이러한 지역 최소값 상태를 벗어나서 빈 틈이 전혀 없는 전역적 최소값에 도달하려면 다시 열을 가해서 철원자가 빈 틈을 찾아갈 수 있도록 진동하게 하면 빈 틈이 전혀 없는 상태로 만들 수 있다.
이와 같이, 에너지가 최소의 상태를 향해서 학습이 진행되는 동안에 파라미터의 값을 임의로 진동시켜서 지역 최소값에 빠지지 않고 전역적인 에너지 최소값에 도달하도록 만드는 기법이 시뮬레이티드 어닐링 방법이다.