담금질 기법
위키백과 ― 우리 모두의 백과사전.
담금질 기법(영어: Simulated Annealing)는,포괄적 최적화문제에 대한 일반적인 확률적 메타·알고리즘이다.광대한탐색 공간안의 주어진함수의포괄적 최적해답에 대해서, 좋은 근사를 준다.S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi등이 1983년에 고안 했다.
그 명칭은 금속 공학에 있어서의 annealing로부터 와 있다. annealing는 금속재료를 가열한 다음에 조금씩 냉각해, 결정을 성장시켜 그 결함을 줄이는 작업이다. 열에 의해서원자는 초기의 위치(내부 에너지가 로컬에 극소인 상태)로부터 멀어져 에너지가 보다 높은 상태를 추이한다. 천천히 냉각하는 것으로 원자는 초기 상태보다 내부 에너지가 한층 더 극소인 상태를 얻을 가능성이 많아진다.
SA알고리즘은 해답을 반복해 다시 요구하기에 즈음하고, 현재의 해답의 랜덤인 근방의 해답을 요구하지만, 그 때에게 줄 수 있었던 함수의 수치와 글로벌인 파라미터 T (온도를 의미한다)가 영향을 준다. 그리고 annealing의 물리 과정과의 유사에 의해서, T(온도)의 값은 서서히 작게 되어 간다.이 때문에, 처음은T가 크기 때문에 해답은 대담하게 변화하지만, T가 제로에 가까워지는 것에 따라 수습해 나간다. 처음은 간단하게 구배를 올라서 갈 수 있으므로, 등산법으로 문제가 되는로컬인 극소에 빠졌을 때의 대책을 생각할 필요가 없다.