담금질 기법
담금질 기법은 지역 최적점에 갇히지 않도록 비용이 증가하는 이동도 온도에 따른 확률로 허용하는 최적화 방법이다 확률적 메타휴리스틱 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중...
| 분류 | 알고리즘 · 확률적 메타휴리스틱 |
|---|---|
| 주요 목적 | 지역 최적점에 갇히지 않도록 비용이 증가하는 이동도 온도에 따른 확률로 허용하는 최적화 방법이다 |
| 핵심 방법 | 현재 상태의 이웃을 생성하고 개선되면 수용하며 악화되는 경우에도 보통 exp(-Δ/T)에 비례한 확률로 수용한다 |
| 복잡도 | 반복 횟수·냉각 스케줄·이웃 생성 비용에 따라 달라진다 |
| 적용 조건 | 비용 함수·이웃 상태 생성·냉각 스케줄과 유효한 상태 조건을 정해야 한다 |
| 참고 자료 | 기술 자료 |
| 관련 분야 | 자료구조, 계산 복잡도 |
담금질 기법은 지역 최적점에 갇히지 않도록 비용이 증가하는 이동도 온도에 따른 확률로 허용하는 최적화 방법이다 확률적 메타휴리스틱 분야의 대표적인 기술로, 데이터의 표현과 입력 조건에 맞는 계산 절차를 정의한다. 적용 목적이 유사한 다른 방법과 비교할 때 정확성 보장과 결과의 해석이 중요하다.[1]
핵심 작동은 다음과 같다. 현재 상태의 이웃을 생성하고 개선되면 수용하며 악화되는 경우에도 보통 exp(-Δ/T)에 비례한 확률로 수용한다. 온도 T를 점차 낮추면 후반 탐색은 개선 이동에 집중한다. 이 절차에서 각 단계에 유지되는 값의 의미를 정의하고 자료구조 또는 수치 표현에 따라 처리 순서를 구현한다.
계산 특성은 반복 횟수·냉각 스케줄·이웃 생성 비용에 따라 달라진다 실제 구현에는 비용 함수·이웃 상태 생성·냉각 스케줄과 유효한 상태 조건을 정해야 한다 단계마다 유지되어야 하는 불변식, 종료 조건과 입력 경계를 검사하면 수학적 모델을 프로그램의 동작과 연결할 수 있다.
활용과 다른 기법과의 관계에서는 조합 최적화·배치·스케줄링에 사용한다. 열처리의 물리적 담금질에 착안했으나 유한 시간 전역 최적 보장은 설정에 달려 있다. 실제 시스템에서는 시간·메모리 사용, 입출력 비용, 정밀도와 저장 형식이 성능에 영향을 줄 수 있다. 필요한 경우 가장 작은 입력과 중복·퇴화 상태도 시험해야 한다.[2]