담금질 기법

담금질 기법(영어: Simulated Annealing, 줄여서 SA)은 전역 최적화 문제에 대한 일반적인 확률적 메타 알고리즘이다. 이 기법은 광대한 탐색 공간 안에서, 주어진 함수의 전역 최적해에 대한 좋은 근사를 준다. 커크패트릭, 젤라트, 베키가 1983년에 고안했다. 보통 영어를 그냥 읽어서 시뮬레이티드 어닐링이라고 부른다.

담금질 기법이라는 말은 금속 공학의 담금질(annealing)에서 왔다. 담금질은 금속재료를 가열한 다음 조금씩 냉각해 결정을 성장시켜 그 결함을 줄이는 작업이다. 열에 의해서 원자는 초기의 위치(내부 에너지가 극소점에 머무르는 상태)로부터 멀어져 에너지가 더욱 높은 상태로 추이된다. 천천히 냉각함으로써 원자는 초기 상태보다 내부 에너지가 한층 더 극소인 상태를 얻을 가능성이 많아진다.

SA 알고리즘은 해를 반복해 개선함으로써, 현재의 해 근방에 있는 해를 임의로 찾는데, 그때에 주어진 함수의 값과 전역 인자 T (온도를 의미한다)가 영향을 준다. 그리고 앞에서 기술한 물리 과정과 비슷한 원리로. T(온도)의 값은 서서히 작아진다. 따라서, 처음에는 T가 크기 때문에 해가 크게 변화하지만, T가 0에 가까워짐에 따라 변화가 줄어든다. 처음은 간단하게 비탈을 올라갈 수 있으므로, 등산법으로 문제가 되는 지역 최적점에 빠졌을 때의 대책을 생각할 필요가 없다.